快速网站建设费用,广告艺术设计主要学什么,哪个网站公司做的好,张掖网站设计公司目录 374. 猜数字大小题目链接标签思路代码 128. 最长连续序列题目链接标签Set思路代码 Sort思路代码 17. 电话号码的字母组合题目链接标签思路代码 374. 猜数字大小
题目链接
374. 猜数字大小
标签
二分查找 交互
思路
看到本题的标签 交互 感觉有些奇怪#xff0c;交互… 目录 374. 猜数字大小题目链接标签思路代码 128. 最长连续序列题目链接标签Set思路代码 Sort思路代码 17. 电话号码的字母组合题目链接标签思路代码 374. 猜数字大小
题目链接
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. 最长连续序列
题目链接
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) {SetInteger 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]) { // 如果相邻元素不相等即差为1currLen; // 则当前连续元素的个数1}curr; // 判断下一个元素是否连续}res Math.max(res, currLen); // 更新结果值curr; // 从下一个元素开始判断默认当前元素是连续元素中的第一个元素}return res;}
}17. 电话号码的字母组合
题目链接
17. 电话号码的字母组合
标签
哈希表 字符串 回溯
思路
组合 就是 将多个选择的结果聚合到一起。在本题中字符 2-9 都对应着不同的多个字符本题的组合就是 对于 digits 中的每个数字从其对应的字符中选取一个字符最终拼接而成的字符串。
本题可以使用 深度优先搜索 的思想在 digits 上进行搜索每次搜索都将当前数字对应的所有字符都选取一遍。每次选择完毕一个字符就搜索下一个数字所对应的字符直到将整个 dights 搜索完此时将拼接的字符串加入结果集合。
代码
class Solution {public ListString letterCombinations(String digits) {if (digits.isEmpty()) { // 如果字符串为空return res; // 则返回空集合}dfs(digits.toCharArray(), 0);return res;}private ListString 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与字符的映射
}
