LeetCode 374, 128, 17
374. 猜数字大小
题目链接
标签
二分查找 交互
思路
看到本题的标签 交互 感觉有些奇怪，交互 意味着需要调用题目给出的方法。我们写的 guessNumber() 是用来猜数字的，而给出的 guess() 则是裁判。
本题可以采用二分法的常规实现——求指定值的位置或其后继的位置，如果不懂二分法的后继和前驱，可以看这篇文章：算法——二分法。
唯一不同于普通二分法的是：没有给出 数组nums 和目标值target，但是给出了 对猜想值大小的判断，即 guess()方法。实际上，二分法 在判断下一次查找是在左子区间还是右子区间时 使用的 if-else 就是 对猜想值大小的判断，例如：target <= nums[mid] 的含义是 目标值小于或等于区间中点，也就是 猜大了 或者 猜对了，即 guess() 返回 -1, 0。
代码
public class Solution extends GuessGame {
public int guessNumber(int n) {
int left = 0, right = n;
while (left < right) {
int mid = left + (right - left >> 1); // mid是猜想的值
if (guess(mid) <= 0) { // 如果guess的结果小于或等于0，即 猜大了 或 猜对了
right = mid; // 让right变小，从而缩小猜想的值
} else { // 如果guess的结果大于0，即 猜小了
left = mid + 1; // 让left变大，从而增大猜想的值
}
}
return left;
}
}
128. 最长连续序列
题目链接
标签
并查集 数组 哈希表
Set
思路
最长连续序列不关心数字的顺序，也不关心数字出现的次数，所以可以对数字做 预处理，即将数字存储到 HashSet 中，这是因为 HashSet 中不存放重复元素，也就是说对数字做了 去重 操作。
将所有数字都放入到 HashSet 中后，就可以遍历整个 HashSet，然后从其中获取元素，并判断这个元素是否存在它的下一个元素、下下一个元素等，直到不存在为止。判断存在性时，需要记录连续元素的最大值，即 判断存在性之前 应该 先获取判断的是哪一个数是否存在，这个数就是连续元素的最大值；此外，还需要使用一个变量来记录连续的元素个数，当退出判断时这个变量就是本次连续元素的长度，将其与结果值中的较大值赋值给结果值。
本题解的精髓不在上面这些基本操作，而是在于 控制时间复杂度。如果真的像上面这样写，则时间复杂度为
O
(
n
2
)
O(n^2)
O(n2)。可以发现，对于 元素num 和 元素num - 1，上面的思路会将这两个元素都判断一遍，但以 num 为起始元素的连续元素的长度 一定比 以 num - 1 为起始元素的连续元素的长度 小
1
1
1。对于获取最大连续元素长度的要求，对 num 的判断 不是必需的。所以在 num - 1 存在时，跳过对 num 的判断，这就将
O
(
n
2
)
O(n^2)
O(n2) 的复杂度转化为
O
(
n
)
O(n)
O(n) 的复杂度了。
代码
class Solution {
public int longestConsecutive(int[] nums) {
Set<Integer> set = new HashSet<>(); // 储存数字的集合
// 先把所有数字都加入集合，即对数字去重
for (int num : nums) {
set.add(num);
}
int res = 0; // 储存结果
for (int num : set) {
if (set.contains(num - 1)) { // 如果集合中存在当前数的上一个数
continue; // 则跳过本次循环，这是O(n)的关键
}
int currNum = num; // 连续数字的最大数
int currLen = 1; // 连续数字的长度
while (set.contains(++currNum)) { // 直到不存在连续的数为止
currLen++; // 增加连续数字的长度
}
res = Math.max(res, currLen); // 取更大的连续数字长度作为结果值
}
return res;
}
}
Sort
思路
HashSet 的操作，例如 add(), contains() 都是外部API调用，在力扣的判题系统中很浪费时间，而上面这种解法需要使用很多次这样的操作，所以需要少调用一些外部API。
本题的核心在于 顺序+去重，HashSet 用自身的不重复性满足了 去重，使用 contains() 满足了 顺序；除此之外，还可以使用 排序 满足 顺序，通过 只有相邻元素之差等于 1 时才让长度加一 的操作来满足 去重。
代码
class Solution {
public int longestConsecutive(int[] nums) {
int n = nums.length; // 存储数组长度
if (n < 2) { // 如果数组长度比2小
return n; // 则直接返回它的长度，不需要判断
}
Arrays.sort(nums); // 对数组进行排序
int res = 0; // 存储结果
// 从第二个元素开始判断，默认第一个元素是为连续元素中的第一个元素
int curr = 1; // 存储 连续元素的最大值的索引
while (curr < n) { // 直到遍历完整个nums才退出循环
int currLen = 1; // 存储当前连续元素的长度
// curr在nums内 并且 相邻元素之差小于等于1 才进行循环
while (curr < n && nums[curr] - nums[curr - 1] <= 1) {
if (nums[curr] != nums[curr - 1]) { // 如果相邻元素不相等，即差为1
currLen++; // 则当前连续元素的个数+1
}
curr++; // 判断下一个元素是否连续
}
res = Math.max(res, currLen); // 更新结果值
curr++; // 从下一个元素开始判断，默认当前元素是连续元素中的第一个元素
}
return res;
}
}
17. 电话号码的字母组合
题目链接
标签
哈希表 字符串 回溯
思路
组合 就是 将多个选择的结果聚合到一起。在本题中，字符 2-9 都对应着不同的多个字符，本题的组合就是 对于 digits 中的每个数字，从其对应的字符中选取一个字符，最终拼接而成的字符串。
本题可以使用 深度优先搜索 的思想：在 digits 上进行搜索，每次搜索都将当前数字对应的所有字符都选取一遍。每次选择完毕一个字符，就搜索下一个数字所对应的字符，直到将整个 dights 搜索完，此时将拼接的字符串加入结果集合。
代码
class Solution {
public List<String> letterCombinations(String digits) {
if (digits.isEmpty()) { // 如果字符串为空
return res; // 则返回空集合
}
dfs(digits.toCharArray(), 0);
return res;
}
private List<String> res = new ArrayList<>(); // 储存结果的集合
private StringBuilder builder = new StringBuilder(); // 存储拼接的字符串
/**
* 对digits进行深度优先搜索
* @param digits 待搜索数组
* @param curr 当前元素的索引
*/
private void dfs(char[] digits, int curr) {
if (curr == digits.length) { // 如果遍历完了整个数组
res.add(builder.toString()); // 则将拼接的字符串放入结果集合
return; // 然后返回
}
for (char ch : mapper[digits[curr] - '2']) { // 取出当前元素映射的所有字符
builder.append(ch); // 先将字符拼接到字符串
dfs(digits, curr + 1); // 然后进行下一个元素的遍历
builder.deleteCharAt(builder.length() - 1); // 最后将这个字符从字符串中删去
}
}
private char[][] mapper = new char[][]{
{'a', 'b', 'c'},
{'d', 'e', 'f'},
{'g', 'h', 'i'},
{'j', 'k', 'l'},
{'m', 'n', 'o'},
{'p', 'q', 'r', 's'},
{'t', 'u', 'v'},
{'w', 'x', 'y', 'z'}
}; // 数字2-9与字符的映射
}
原文地址：https://blog.csdn.net/qq_61350148/article/details/140346201
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！