LeetCode 34, 202, 46
目录
- 34. 在排序数组中查找元素的第一个和最后一个位置
- 题目链接
- 标签
- 思路
- 代码
- 202. 快乐数
- 题目链接
- 标签
- Set
- 思路
- 代码
- 判圈
- 思路
- 代码
- 46. 全排列
- 题目链接
- 标签
- 思路
- 代码
34. 在排序数组中查找元素的第一个和最后一个位置
题目链接
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 int mid = left + (right - left > 1); 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 int mid = left + (right - left > 1); if (target nums[mid]) { // 如果 target > nums[mid] left = mid + 1; // 则去右子区间查找 } else { // 如果 target == nums[mid] candidate = mid; // 更新候选索引的值 left = mid + 1; // 去右子区间查找 } } return candidate; // 返回候选索引，如果能找到目标值，则返回最右边的目标值索引；否则返回-1 } }202. 快乐数
题目链接
202. 快乐数
标签
哈希表 数学 双指针
Set
思路
在求n的每一位的平方之和时，如果发现这个平方和 curr 与之前某个平方和 past 相等，则n就不是快乐数，因为再对 curr 求 有限次 平方和，就会得到 past，而无法得到 1，即它不是快乐数。
可以使用一个集合存储所有的平方和，每次先求平方和，然后判断在集合中是否存在这个平方和，如果存在，就说明 n 不是快乐数，返回 false。 由于不仅要保存 n ，还要保存所有的平方和，所以可以把保存的操作放在求平方和之前。
代码
class Solution { public boolean isHappy(int n) { Set 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. 全排列
题目链接
46. 全排列
标签
数组 回溯
思路
本题是一个 针对数组的 记忆的 深度优先搜索，在搜索时，通常有五步操作：
- 判断是否已经完成搜索，如果完成搜索，则直接返回；否则针对数组中的全部元素进行下列操作。
- 判断是否遍历过当前元素，如果遍历过，则跳过它，遍历数组中的下一个元素；否则进行下列操作。
- 标记当前元素已被遍历，对当前元素进行要求的操作。
- 进行更深一层的递归。
- 取消当前元素被遍历的标记，消除对当前元素操作而产生的影响。
第五步 是很关键的，如果没有第五步，则本次的遍历会影响下一次的遍历。
对应到具体题目，使用 boolean[] vis 记录每个元素是否遍历过；在搜索时传入一个栈，这个栈保存了本次搜索遍历过的元素，在 栈的元素数 等于 数组的元素数 时，完成本次的排列，具体的五步操作如下：
- 判断 栈的元素数 是否等于 数组的元素数，如果等于，则将栈中的所有元素作为链表加入到结果中，并返回；否则对数组中的全部元素进行下列操作。
- 判断是否遍历过这个元素，如果遍历过，则跳过它，遍历数组中的下一个元素；否则进行下列操作。
- 标记当前元素已被遍历，将当前元素放到栈中。
- 进行更深一层的递归。
- 取消当前元素被遍历的标记，将当前元素从栈中弹出。
代码
class Solution { public List permute(int[] nums) { vis = new boolean[nums.length]; dfs(nums, new LinkedList()); return res; } private boolean[] vis; // 用于判断本次搜索是否遍历过nums中的值 private final List res = new ArrayList(); // 保存结果的链表 /** * 对nums进行深度优先搜索 * @param nums 待搜索数组 * @param stack 已搜索的元素组成的栈 */ private void dfs(int[] nums, LinkedList stack) { if (stack.size() == nums.length) { // 如果 栈的元素个数 与 nums的元素个数 相等，即搜索完整个nums res.add(new ArrayList(stack)); // 将栈中的元素作为链表存入结果链表 return; // 返回 } for (int i = 0; i
