LeetCode 34, 202, 46
34. 在排序数组中查找元素的第一个和最后一个位置
题目链接
标签
数组 二分查找
思路
本题需要查找目标区间（值）的左端点和右端点，使用 二分查找 即可，不过不能在 target == nums[mid] 时直接返回 mid，而应该记录这个 mid 作为候选的端点值，继续查找是否有更优的端点值。对于查找 左端点，相等时去 左子区间 查找；对于查找 右端点，相等时去 右子区间 查找。
代码
class Solution {
public int[] searchRange(int[] nums, int target) {
int left = leftBinarySearch(nums, target);
int right = rightBinarySearch(nums, target);
return new int[]{left, right};
}
// 查询最左边的目标值的索引
private int leftBinarySearch(int[] nums, int target) {
int left = 0, right = nums.length - 1;
int candidate = -1; // 候选索引
while (left <= right) {
int mid = left + (right - left >> 1);
if (target < nums[mid]) { // 如果 target < nums[mid]
right = mid - 1; // 则去左子区间查找
} else if (target > nums[mid]) { // 如果 target > nums[mid]
left = mid + 1; // 则去右子区间查找
} else { // 如果 target == nums[mid]
candidate = mid; // 更新候选索引的值
right = mid - 1; // 去左子区间查找
}
}
return candidate; // 返回候选索引，如果能找到目标值，则返回最左边的目标值索引；否则返回-1
}
// 查询最右边的目标值的索引
private int rightBinarySearch(int[] nums, int target) {
int left = 0, right = nums.length - 1;
int candidate = -1; // 候选索引
while (left <= right) {
int mid = left + (right - left >> 1);
if (target < nums[mid]) { // 如果 target < nums[mid]
right = mid - 1; // 则去左子区间查找
} else if (target > nums[mid]) { // 如果 target > nums[mid]
left = mid + 1; // 则去右子区间查找
} else { // 如果 target == nums[mid]
candidate = mid; // 更新候选索引的值
left = mid + 1; // 去右子区间查找
}
}
return candidate; // 返回候选索引，如果能找到目标值，则返回最右边的目标值索引；否则返回-1
}
}
202. 快乐数
题目链接
标签
哈希表 数学 双指针
Set
思路
在求n的每一位的平方之和时，如果发现这个平方和 curr 与之前某个平方和 past 相等，则n就不是快乐数，因为再对 curr 求 有限次 平方和，就会得到 past，而无法得到 1，即它不是快乐数。
可以使用一个集合存储所有的平方和，每次先求平方和，然后判断在集合中是否存在这个平方和，如果存在，就说明 n 不是快乐数，返回 false。 由于不仅要保存 n ，还要保存所有的平方和，所以可以把保存的操作放在求平方和之前。
代码
class Solution {
public boolean isHappy(int n) {
Set<Integer> set = new HashSet<>(); // 存储平方和的集合
while (n != 1) { // 直到 n为1(是快乐数) 才退出循环
set.add(n); // 将当前数字存入集合
n = getNext(n); // 获取平方和
if (set.contains(n)) { // 集合中包含n(不是快乐数)
return false; // 返回false
}
}
return true;
}
// 获取n的每位的平方之和
private int getNext(int n) {
int next = 0; // 保存n的每位的平方之和
while (n > 0) { // 直到n为0才退出循环
int d = n % 10; // 获取n的最后一位
n /= 10; // 将n向后移一位
next += d * d; // 对平方求和
}
return next;
}
}
判圈
思路
本题解的 getNext() 的方法名是有一定意义的：在链表中经常使用 next 作为下一个节点的指针，本题中 根据数字获取其平方和作为下一个数字 的操作很像链表的 next 指针，所以本题引申一下就是 判断链表是否存在环，这里使用的是 Floyd判圈算法 ，不懂的可以去看。
具体操作就是：使用快慢指针，快指针每次走两步，慢指针每次走一步，如果快指针能遍历到链表尾部（对应到本题就是快指针的值为1），那就说明n是快乐数，返回true；如果不能遍历到链表尾部，则快慢指针一定会相遇，说明n不是快乐数，返回false。
代码
class Solution {
public boolean isHappy(int slow) { // slow 为慢指针
int fast = getNext(slow); // 快指针
while (fast != 1) { // 直到 平方和为1(是快乐数) 才退出循环，相当于到链表尾部
slow = getNext(slow); // 更新慢指针
fast = getNext(getNext(fast)); // 更新快指针
if (slow == fast) { // 如果快慢指针相遇，则说明有环，不是快乐数
return false; // 返回false
}
}
return true;
}
// 获取n的每位的平方之和
private int getNext(int n) {
int next = 0; // 保存n的每位的平方之和
while (n > 0) { // 直到n为0才退出循环
int d = n % 10; // 获取n的最后一位
n /= 10; // 将n向后移一位
next += d * d; // 对平方求和
}
return next;
}
}
46. 全排列
题目链接
标签
数组 回溯
思路
本题是一个 针对数组的 记忆的 深度优先搜索，在搜索时，通常有五步操作：
- 判断是否已经完成搜索，如果完成搜索，则直接返回；否则针对数组中的全部元素进行下列操作。
- 判断是否遍历过当前元素，如果遍历过，则跳过它，遍历数组中的下一个元素；否则进行下列操作。
- 标记当前元素已被遍历，对当前元素进行要求的操作。
- 进行更深一层的递归。
- 取消当前元素被遍历的标记，消除对当前元素操作而产生的影响。
第五步 是很关键的，如果没有第五步，则本次的遍历会影响下一次的遍历。
对应到具体题目，使用 boolean[] vis 记录每个元素是否遍历过；在搜索时传入一个栈，这个栈保存了本次搜索遍历过的元素，在 栈的元素数 等于 数组的元素数 时，完成本次的排列，具体的五步操作如下：
- 判断 栈的元素数 是否等于 数组的元素数，如果等于，则将栈中的所有元素作为链表加入到结果中，并返回；否则对数组中的全部元素进行下列操作。
- 判断是否遍历过这个元素，如果遍历过，则跳过它，遍历数组中的下一个元素；否则进行下列操作。
- 标记当前元素已被遍历，将当前元素放到栈中。
- 进行更深一层的递归。
- 取消当前元素被遍历的标记，将当前元素从栈中弹出。
代码
class Solution {
public List<List<Integer>> permute(int[] nums) {
vis = new boolean[nums.length];
dfs(nums, new LinkedList<>());
return res;
}
private boolean[] vis; // 用于判断本次搜索是否遍历过nums中的值
private final List<List<Integer>> res = new ArrayList<>(); // 保存结果的链表
/**
* 对nums进行深度优先搜索
* @param nums 待搜索数组
* @param stack 已搜索的元素组成的栈
*/
private void dfs(int[] nums, LinkedList<Integer> stack) {
if (stack.size() == nums.length) { // 如果 栈的元素个数 与 nums的元素个数 相等，即搜索完整个nums
res.add(new ArrayList<>(stack)); // 将栈中的元素作为链表存入结果链表
return; // 返回
}
for (int i = 0; i < nums.length; i++) { // 遍历nums的每个元素
if (vis[i]) { // 如果本次搜索遍历过这个元素
continue; // 则跳过它
}
// 否则本次搜索没有遍历过这个元素，现在开始遍历这个元素
vis[i] = true; // 标记遍历过这个元素
stack.push(nums[i]); // 将这个元素放到栈中
dfs(nums, stack); // 寻找下一个元素
stack.pop(); // 将这个元素弹出栈
vis[i] = false; // 取消遍历过这个元素的标记
}
}
}
原文地址：https://blog.csdn.net/qq_61350148/article/details/140288099
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！