如何做强企业网站,wordpress文本小工具,建一个互联网平台需要多少钱,一个网站如何工作流程目录 441. 排列硬币题目链接标签思路代码 57. 插入区间题目链接标签思路两个区间的情况对每个区间的处理最终的处理 代码 79. 单词搜索题目链接标签原理思路代码 优化思路代码 441. 排列硬币
题目链接
441. 排列硬币
标签
数学 二分查找
思路
由于本题所返回的 答案在区间… 目录 441. 排列硬币题目链接标签思路代码 57. 插入区间题目链接标签思路两个区间的情况对每个区间的处理最终的处理 代码 79. 单词搜索题目链接标签原理思路代码 优化思路代码 441. 排列硬币
题目链接
441. 排列硬币
标签
数学 二分查找
思路
由于本题所返回的 答案在区间 [1, n] 内并且 答案越大所需要的硬币越大 (有序)所以采用 二分枚举答案 的思想。
由于要找 最多 的完整阶梯的总行数所以使用二分法的 前驱 实现因为一个数的前驱是 最后一个小于该数 的数。不了解二分法的后继与前驱的可以看这篇文章算法——二分法。
代码
class Solution {public int arrangeCoins(int n) {// 二分枚举答案long left 1, right n; // 答案的区间为 [1, n]while (left right) { // 使用二分法的 前驱 实现long mid left (right - left 1 1); // 猜想答案if (n sum(mid)) { // 如果 猜想的答案 太大了right mid - 1; // 则 缩小 猜想的答案} else { // 如果 猜想的答案 太小了 或 猜对了left mid; // 则 扩大 猜想的答案}}return (int) left;}// 获取 layer 层阶梯 需要的硬币总数private long sum(long layer) {return layer * (layer 1) / 2;}
}57. 插入区间
题目链接
57. 插入区间
标签
数组
思路
由于题目中提示 可以不原地修改 intervals所以可以创建一个 Listint[] 类型的变量 list将所有的区间都添加到 list 中同时 合并重叠的区间在最后返回 list 转换为 int[][] 的形式。本题的重点在于如何合并区间。
两个区间的情况 如上图区间 curr 和 区间 new 之间共有 3 中情况
如果 interval[1] left则 curr 在 new 左边。如果 right interval[0]则 curr 在 new 右边。如果以上两种情况都不满足并且有 interval[0] right则 curr 与 new 有交集。注意此情况包含 c u r r ⊂ n e w curr \subset new curr⊂new、 n e w ⊂ c u r r new \subset curr new⊂curr 和 c u r r n e w curr new currnew 这三种特殊情况。
对每个区间的处理
令 新区间newInterval 的左、右端点分别为 left, right从区间的集合 intervals 中取出单个区间 interval其左、右端点分别为 interval[0], interval[1]则对于 新区间 new 和 当前选取的区间 curr根据不同情况可分为以下三种处理方式
当 curr 在 new 左边时直接将 当前区间curr 加入到 list 中。当 curr 在 new 右边时将 新区间new 加入到 list 中并把 当前区间curr 当作 新区间new。当 curr 与 new 有交集时将 当前区间curr 合并到 新区间new 中此时新区间的端点值需要被更新左端点更新为 较小 的左端点右端点更新为 较大 的右端点。
最终的处理
这种处理方式会导致 最后的新区间 没有被加入到 list 中以下针对 倒数第二个区间curr 和 新区间new 做如下讨论证明 最后的新区间 没有被加入到 list 中
当 curr 在 new 左边时只将 倒数第二个区间curr 加入到 list 中而没有将 new 加入到 list 中。当 curr 在 new 右边时只将 新区间new 加入到 list 中而没有将被看作 新区间new 的倒数第二个区间curr 加入到 list 中。当 curr 与 new 有交集时只是更新了 新区间new 的左、右端点而没有将其加入到 list 中。
综上所述最后的新区间 确实没有被加入到 list 中所以在返回结果之前得先把 最后的新区间 加入到 list 中。
代码
class Solution {public int[][] insert(int[][] intervals, int[] newInterval) {if (intervals.length 0){ // 如果 intervals 为空return new int[][]{newInterval}; // 则将 newInterval 作为唯一的区间返回}int left newInterval[0], right newInterval[1]; // left, right 分别为 合并后的新区间的 左端点 和 右端点Listint[] list new ArrayList(intervals.length);for (int[] interval : intervals) {if (right interval[0]) { // 如果 当前区间的左端点 大于 新区间的右端点即 curr 在 new 右边// 注意这里不能直接写 list.add(newInterval)// 因为新区间可能经过合并此时左、右端点可能就与原来不同了list.add(new int[]{left, right}); // 则将新区间加入 list// 将 当前区间 当作 新区间left interval[0];right interval[1];} else if (interval[1] left) { // 如果 当前区间的右端点 小于 新区间的左端点即 curr 在 new 左边list.add(interval); // 将当前区间加入 list} else { // 当前区间与新区间有交集合并它们left Math.min(left, interval[0]); // 取 左端点 的较小值right Math.max(right, interval[1]); // 取 右端点 的较大值}}// 将 最后的新区间 加入 listlist.add(new int[]{left, right});return list.toArray(new int[list.size()][]); // 将 Listint[] 转为 int[][]}
}79. 单词搜索
题目链接
79. 单词搜索
标签
数组 字符串 回溯 矩阵
原理
思路
本题可以使用 深度优先搜索 的思想以矩阵中每个元素作为 word 的起始字符搜索合适的字符串如果能找到合适的字符串则返回 true。步骤如下
如果要遍历一个字符那么它得满足以下 3 个条件如果任意一个不成立则返回 false否则继续匹配。 当前字符在矩阵 board 中当前字符没有被遍历过当前字符与本轮搜索要匹配的 word 中的字符相等 如果当前字符匹配的是 word 中的最后一个字符则可以返回 true代表找到合适的字符串了否则继续匹配。标记当前字符已被遍历过了。分别向上下左右搜索下一个字符如果其中有一个方向匹配成功则直接返回 false。取消遍历过当前字符的标记清除本次搜索对下一次搜索的影响。如果能到这一步则说明没有匹配成功返回 false。
由于 同一个单元格内的字母不允许被重复使用所以 在搜索时得记录每个元素是否遍历过可以使用 boolean[][] 来记录 board 中的每个元素是否遍历过。
代码
class Solution {public boolean exist(char[][] board, String word) {// 对成员变量进行赋值ROW board.length;COL board[0].length;this.vis new boolean[ROW][COL];this.board board;this.word word.toCharArray();// 以矩阵中每个元素作为 word 的起始字符搜索合适的字符串for (int r 0; r ROW; r) {for (int c 0; c COL; c) {if (dfs(r, c, 0)) { // 如果能找到合适的字符串return true; // 则返回 true}}}return false; // 找不到合适的字符串返回 false}// (r, c) 指向 board 中的字符curr 指向 word 中的字符private boolean dfs(int r, int c, int curr) {if (!(r 0 r ROW c 0 c COL) // 如果 (r, c) 指向的元素在矩阵外|| vis[r][c] // 或 (r, c) 指向的元素已被遍历过|| board[r][c] ! word[curr]) { // 或 字符匹配失败return false; // 则返回 false} else if (curr word.length - 1) { // 当前字符匹配成功如果当前字符匹配的是最后一个字符return true; // 则返回 true}vis[r][c] true; // 标记遍历过 (r, c) 指向的元素for (int k 0; k 4; k) { // 枚举四个方向int kr r dir[k][0], kc c dir[k][1]; // (kr, kc) 指向待遍历的元素if (dfs(kr, kc, curr 1)) { // 如果后面的字符都匹配成功了return true; // 则返回 true}}vis[r][c] false; // 取消 遍历过 (r, c) 指向元素的标记return false; // 匹配失败返回 false}private int ROW; // 矩阵的行数private int COL; // 矩阵的列数private char[][] board; // 使用成员变量保存 boardprivate char[] word; // 使用成员变量保存 wordprivate boolean[][] vis; // 判断某个元素是否遍历过private int[][] dir {{1, 0}, {0, 1}, {-1, 0}, {0, -1}}; // 方向数组分别为 向右、向下、向左、向上
}优化
思路
上面的代码运行起来比较慢主要有两个优化点
不使用方向数组 dir而是一个一个地将四个方向写出来。标记是否遍历过某个元素时可以不使用 boolean[][] vis而是将 board 的字符变为一个与英文字母不相关的字符——\0然后再将其还原为原本的字母这样在判断时就将 vis[r][c] 合并到 匹配字符的操作 board[r][c] ! word[curr] 中这样做可以减少时间的浪费。
代码
class Solution {public boolean exist(char[][] board, String word) {// 对成员变量进行赋值ROW board.length;COL board[0].length;this.board board;this.word word.toCharArray();// 以矩阵中每个元素作为 word 的起始字符搜索合适的字符串for (int r 0; r ROW; r) {for (int c 0; c COL; c) {if (dfs(r, c, 0)) { // 如果能找到合适的字符串return true; // 则返回 true}}}return false; // 找不到合适的字符串返回 false}// (r, c) 指向 board 中的字符curr 指向 word 中的字符private boolean dfs(int r, int c, int curr) {if (!(r 0 r ROW c 0 c COL) // 如果 (r, c) 指向的元素在矩阵外|| board[r][c] ! word[curr]) { // 或 字符匹配失败return false; // 则返回 false} else if (curr word.length - 1) { // 当前字符匹配成功如果当前字符匹配的是最后一个字符return true; // 则返回 true}board[r][c] \0; // 标记遍历过 (r, c) 指向的元素boolean res dfs(r, c 1, curr 1) // 向右|| dfs(r 1, c, curr 1) // 向下|| dfs(r - 1, c, curr 1) // 向左|| dfs(r, c - 1, curr 1); // 向上 分别向四个方向搜索能否找到合适的字符串board[r][c] word[curr]; // 取消 遍历过 (r, c) 指向元素的标记return res; // 返回 分别向四个方向搜索能否找到合适的字符串}private int ROW; // 矩阵的行数private int COL; // 矩阵的列数private char[][] board; // 使用成员变量保存 boardprivate char[] word; // 使用成员变量保存 word
}
