建设银行官网官方网站,郑州航海路网站建设,缩略图 wordpress,上海企业一户式查询目录
数组
1. LCR 121. 寻找目标值 - 二维数组
2. LCR 120. 寻找文件副本
3. LCR 128. 库存管理 I
4. LCR 131. 砍竹子 I
5. LCR 132. 砍竹子 II
6. LCR 135. 报数
7. LCR 139. 训练计划 I
8. LCR 158. 库存管理 II
9. LCR 159. 库存管理 III
10. LCR 160. 数据流中…目录
数组
1. LCR 121. 寻找目标值 - 二维数组
2. LCR 120. 寻找文件副本
3. LCR 128. 库存管理 I
4. LCR 131. 砍竹子 I
5. LCR 132. 砍竹子 II
6. LCR 135. 报数
7. LCR 139. 训练计划 I
8. LCR 158. 库存管理 II
9. LCR 159. 库存管理 III
10. LCR 160. 数据流中的中位数
11. LCR 164. 破解闯关密码
12. LCR 168. 丑数
13. LCR 170. 交易逆序对的总数
14. LCR 172. 统计目标成绩的出现次数
15. LCR 173. 点名
16. LCR 179. 查找总价格为目标值的两个商品
17. LCR 180. 文件组合
18. LCR 183. 望远镜中最高的海拔
19. LCR 186. 文物朝代判断
20. LCR 189. 设计机械累加器
21. LCR 191. 按规则计算统计结果
字符串
22. LCR 122. 路径加密
23. LCR 138. 有效数字
24. LCR 157. 套餐内商品的排列顺序
25. LCR 167. 招式拆解 I
26. LCR 169. 招式拆解 II
27. LCR 181. 字符串中的单词反转
28. LCR 182. 动态口令
29. LCR 192. 把字符串转换成整数 (atoi)
链表
30. LCR 123. 图书整理 I
31. LCR 136. 删除链表的节点
32. LCR 140. 训练计划 II
33. LCR 141. 训练计划 III
34. LCR 142. 训练计划 IV
35. LCR 171. 训练计划 V
36. LCR 154. 复杂链表的复制
栈和队列
37. LCR 147. 最小栈
38. LCR 125. 图书整理 II
39. LCR 184. 设计自助结算系统
40. LCR 148. 验证图书取出顺序
树
41. LCR 124. 推理二叉树
42. LCR 143. 子结构判断
43. LCR 144. 翻转二叉树
44. LCR 145. 判断对称二叉树
45. LCR 149. 彩灯装饰记录 I
46. LCR 150. 彩灯装饰记录 II
47. LCR 151. 彩灯装饰记录 III
48. LCR 152. 验证二叉搜索树的后序遍历序列
49. LCR 153. 二叉树中和为目标值的路径
50. LCR 155. 将二叉搜索树转化为排序的双向链表
51. LCR 156. 序列化与反序列化二叉树
52. LCR 174. 寻找二叉搜索树中的目标节点
53. LCR 175. 计算二叉树的深度
54. LCR 176. 判断是否为平衡二叉树
55. LCR 193. 二叉搜索树的最近公共祖先
56. LCR 194. 二叉树的最近公共祖先
位运算
57. LCR 133. 位 1 的个数
58. LCR 134. Pow(x, n)
59. LCR 177. 撞色搭配
60. LCR 178. 训练计划 VI
61. LCR 190. 加密运算
动态规划
62. LCR 126. 斐波那契数
63. LCR 127. 跳跃训练
64. LCR 137. 模糊搜索验证
65. LCR 161. 连续天数的最高销售额
66. LCR 165. 解密数字
67. LCR 166. 珠宝的最高价值
68. LCR 185. 统计结果概率
69. LCR 187. 破冰游戏
图
70. LCR 129. 字母迷宫
71. LCR 130. 衣橱整理编辑
72. LCR 146. 螺旋遍历二维数组
贪心算法
73. LCR 188. 买卖芯片的最佳时机
找规律
74. LCR 162. 数字 1 的个数
75. LCR 163. 找到第 k 位数字 数组
1. LCR 121. 寻找目标值 - 二维数组 就是根据矩阵特性来查找矩阵值每行从左到右是递增的每一列从上到下是递增的。
我们可以从数组的右上角 arr[i][j] 开始如果 target 大于arr[i][j]那就 i 往后走如果比它小那就 j-- 往前走如果相等返回 true数组越界了也没找到该值就返回 false。
代码实现
class Solution {public boolean findTargetIn2DPlants(int[][] plants, int target) {// 注意数组没有值的情况if (plants.length 0) return false;// 找到右上角的值int i 0;int j plants[0].length - 1;while (i 0 i plants.length j 0 j plants[0].length) {if (plants[i][j] target) {j--;} else if (plants[i][j] target) {i;} else {return true;}}return false;}
} 2. LCR 120. 寻找文件副本 寻找重复出现数字直接两层遍历暴力破解即可。
或者直接调用库函数给数组排下序然后再相邻两两比较相同就返回。
或者用 set 来做遍历数组如果元素在 set 中存在则返回元素如果不存在就把元素添加进 set 里。
代码实现
class Solution {public int findRepeatDocument(int[] documents) {for (int i 0; i documents.length - 1; i) {for (int j i 1; j documents.length; j) {if (documents[i] documents[j]) {return documents[i];}}}return -1;}
}class Solution {public int findRepeatDocument(int[] documents) {Arrays.sort(documents);for (int i 0; i documents.length - 1; i) {if (documents[i] documents[i 1]) {return documents[i];}}return -1;}
}class Solution {public int findRepeatDocument(int[] documents) {SetInteger set new HashSet();for (int i 0; i documents.length; i) {int x documents[i];if (set.contains(x)) {return x;} else {set.add(x);}}return -1;}
} 3. LCR 128. 库存管理 I 这个简单直接遍历数组找最小元素即可。
也可以用二分查找因为是部分区间是升序的就可以利用二分查找来完成。
以 s[right] 为参照物 用中间值 s[mid] 与 s[right] 比较如果 s[mid] s[right] 如例 1 则说明最小元素在 mid 1, right 区间如果小于则说明最小元素在 left, mid 区间如果相等就无法以判断 right 来判断最小元素在哪里所以 right-- 往前找另一个参照物。最后 left 与 right 重合时就是最小值的下标。
代码实现
class Solution {public int stockManagement(int[] stock) {int min Integer.MAX_VALUE;for (int i 0; i stock.length; i) {if (stock[i] min) {min stock[i];}}return min;}
}// 二分查找
class Solution {public int stockManagement(int[] stock) {int left 0;int right stock.length - 1;while (left right) {int mid (left right) / 2;if (stock[mid] stock[right]) {left mid 1;} else if (stock[mid] stock[right]) {right--;} else {right mid;}}return stock[right];}
} 4. LCR 131. 砍竹子 I 可以用动态规划来做dp[i] 就是长度为 i 的竹子拆分两段或以上的最大乘积 i 拆分分两种情况第一只拆分成 2 段j 和 i - j。 乘积就是 j * (i - j) 第二拆分成两段以上j i - j 还继续拆分乘积就是 j * dp[i - j] 所以 dp[i] 就是上面两种情况的结果集合中最大值。 初始化因为 i 0 和 i 1 时不能拆分所以 dp[0] dp[1] 0。 最后返回 dp[bl] 即可。 代码实现
class Solution {public int cuttingBamboo(int bamboo_len) {// dp[i] 是长度为 i 的竹子拆分为两段或以上的最大乘积int[] dp new int[bamboo_len 1];// 初始化 dp[0] dp[1] 0dp[0] 0;dp[1] 0;for (int i 2; i bamboo_len; i) {// 分两种情况一种是竹子 i 只拆分成两个数字 3 2 1// 分别是 j 和 i - j另一种是 j和 i - j 继续拆分成更细的 3 1 1 1// 所以需要 j 从 i - 1 开始遍历j 》 1然后求以上结果集合中的最大的那一个for (int j i - 1; j 1; j--) {int max Math.max(j * (i - j), j * dp[i - j]);dp[i] Math.max(dp[i], max);}}return dp[bamboo_len];}
} 5. LCR 132. 砍竹子 II 因为范围变大了所以就不能用动态规划了。
看题解大佬的思路是将绳子长度尽可能分为多个 3这样乘积才最大。
所以当 n 4 的时候返回 n - 1当 n 等于 4 的时候返回 4当 n 4 的时候就要切割成 3 的小端只要 n 4就进行切割然后将切割出来的 3 累乘然后取模。
代码实现
class Solution {public int cuttingBamboo(int n) {if (n 4) {return n - 1;} else if (n 4) {return n;} else {long ans 1;while (n 4) {ans * 3;ans % 1000000007;n - 3;}return (int) (ans * n % 1000000007);}}
} 6. LCR 135. 报数 就是算出一共有几个数字然后数组赋值即可。
第二种方法就是全排列参考大佬的解答假如数字特别大就无法用整型来存储数据了那此时就可以用字符串来存储数据要生成从 1 到 10^n - 1 的数我们可以看作是数字 0~9 的排列问题要循环生成 n 位数首先是生成第一位数字第一位一定是 1 ~ 9然后再递归生成剩下的数字从 0 ~ 9 中取值
代码实现
class Solution {public int[] countNumbers(int cnt) {int len (int) Math.pow(10, cnt);int[] arr new int[len - 1];for (int i 0; i arr.length; i) {arr[i] i 1;}return arr;}
}// 全排列
class Solution {int count 0;int ret[];public int[] countNumbers(int cnt) {int len (int) Math.pow(10, cnt) - 1;ret new int[len];// i 表示要生成 i 位数for (int i 1; i cnt; i) {// 首先生成第一位for (char first 1; first 9; first) {// 创建个字符数组存储生成的数字char[] num new char[i];num[0] first;// 然后递归生成剩下的数字dfs(1, num, i);}}return ret;}// digit 表示要生成 digit 位数public void dfs(int index, char[] num, int digit) {if (index digit) {// 接下来要生成 index 下标的数字// 此时说明已经生成了 digit 位数将其存入数组中并返回即可ret[count] Integer.valueOf(String.valueOf(num));return;}// 生成范围是 0 ~ 9for (char i 0; i 9; i) {num[index] i;// 继续生成剩下的数字dfs(index 1, num, digit);}}
} 7. LCR 139. 训练计划 I 这个简单用双指针就行left 从 0 下标开始找偶数right 从最后一个位置开始找奇数然后交换 left 和 right 下标的值然后 left 和 right 再继续往后找下一组直到 left 和 right 相遇。
代码实现
class Solution {public int[] trainingPlan(int[] actions) {// 这个简单int left 0;int right actions.length - 1;while (left right) {// left 往后走找偶数while (left right actions[left] % 2 1) {left;}// right 往前找奇数while (left right actions[right] % 2 0) {right--;}// 此时 left 一定是偶数 right 一定是奇数交换int tmp actions[left];actions[left] actions[right];actions[right] tmp;}return actions;}
} 8. LCR 158. 库存管理 II 这个也简单将数组排序排完序后下标为 arr.length / 2 的元素就一定是出现次数超过一半的数字。还有另一种方法叫做摩尔投票法简单来说就是假设该数是众数 x 那么遇到 x 就 count不是 x 就 count--如果此时 count 为 0 了那么说明 x 一定不是众数因为众数的出现次数大于数组的一半所以遍历完数组最后 count 应该是大于 0 的。
代码实现
class Solution {public int inventoryManagement(int[] stock) {Arrays.sort(stock);return stock[stock.length / 2];}
}// 投票法
class Solution {public int inventoryManagement(int[] stock) {int count 1;int x stock[0];for (int i 1; i stock.length; i) {if (count 0) {// 当票数为 0 时则说明此时 x 不是众数// 就需要重新假设当前数字为众数x stock[i];}if (x stock[i]) {// 数字相同则票数count;} else {// 数字不同则票数--count--;}}return x;}
} 9. LCR 159. 库存管理 III 这个简单就是先排序然后返回范围从 0 到 cnt - 1 下标的数组即可。
也可以用优先级队列来做求前 k 大的元素建立小根堆然后遍历数组前 k 个入队从 第 k1 个元素开始与堆顶元素比较如果 k1 元素大于堆顶元素那么堆顶元素出队第 k1 元素入队遍历完数组后堆顶元素就是第 k 大的元素。求前 k 小元素就建立大根堆与上面思路类似。
代码实现
class Solution {public int[] inventoryManagement(int[] stock, int cnt) {Arrays.sort(stock);return Arrays.copyOfRange(stock, 0, cnt);}
}// 利用优先级队列解决 top-k 问题
class Solution {public int[] inventoryManagement(int[] stock, int cnt) {if (stock null || stock.length 0 || cnt 0) return new int[0];// 或者利用大根堆来做就是 tok-k 问题PriorityQueueInteger queue new PriorityQueue(new ComparatorInteger() {public int compare(Integer o1, Integer o2) {return o2 - o1;}});for (int i 0; i stock.length; i) {if (i cnt) {queue.offer(stock[i]);} else {int top queue.peek();if (top stock[i]) {queue.poll();queue.offer(stock[i]);}}}// 最后队列里就是前 cnt 个小的元素int[] ret new int[cnt];for (int i cnt - 1; i 0; i--) {ret[i] queue.poll();}return ret;}
} 10. LCR 160. 数据流中的中位数 如图题目让你找有序数组中的中位数那就是先定义一个数组 arr 用来存放数据然后再定义 usedSize 记录数组大小然后写新增元素方法那就是先判断数组满没满满了就扩容然后再新增元素写寻找中位数时可以先排序这个数组使用直接插入排序即可然后再来找到中位数。
看了大佬的题解发现可以用两个优先级队列来做队列 A 存储较大的一半数字(小根堆)队列 B 存储较小的一半数字(大根堆)。
新增元素 num 时当 A 的元素个数等于 B 的元素个数时需要往 A 队列增加元素先把 num 添加进 B 队列中然后再让 B 队列的堆顶元素添加进 A 队列中。当 A 的元素个数不等于 B 的元素个数时需要往 B 添加元素将 num 放入 A 队列中然后再将 A 队列的堆顶元素放入 B 队列中。
查找中位数如果两个队列的元素个数不相等那就返回 A 队列的堆顶元素如果元素个数相等那就返回两队列的堆顶元素的和除以 2.0。
代码实现
class MedianFinder {/*** initialize your data structure here.*/int usedSize 0;int[] arr;public MedianFinder() {arr new int[10];}public void addNum(int num) {// 扩容if (usedSize arr.length) {this.arr Arrays.copyOf(arr, arr.length * 2);}arr[usedSize] num;usedSize;}public double findMedian() {if (usedSize 0) {return -1.0;}// 直接插入排序for (int i 1; i usedSize; i) {int j i - 1;int tmp arr[i];for (; j 0; j--) {if (arr[j] tmp) {arr[j 1] arr[j];} else {break;}}arr[j 1] tmp;}if (usedSize % 2 1) {return (double) arr[usedSize / 2];} else {double sum arr[usedSize / 2] arr[usedSize / 2 - 1];return sum / 2;}}
}// 利用两个优先级队列来解决
class MedianFinder {PriorityQueueInteger A, B;/*** initialize your data structure here.*/public MedianFinder() {// A 是小根堆B 是大根堆A new PriorityQueueInteger();B new PriorityQueueInteger(new ComparatorInteger() {public int compare(Integer o1, Integer o2) {return o2 - o1;}});}public void addNum(int num) {if (A.size() B.size()) {// 则需要往 A 队列中添加元素B.offer(num);A.offer(B.poll());} else {// 需要往 B 队列添加元素A.offer(num);B.offer(A.poll());}}public double findMedian() {if (A.size() B.size()) {return (A.peek() B.peek()) / 2.0;} else {return A.peek();}}
}11. LCR 164. 破解闯关密码 这道题本质上就是排序问题字符串之间的排序可以用冒泡排序来写。 比如示例 2 03303459 0 和 3 不需要交换因为 03 30 03303459 3 和 30 需要交换因为 330 303 03033459 3 和 34 不需要交换因为 334 343 03033459 34 和 5 不需要交换因为 345 543 03033459 5 和 9 不需要交换因为 59 95 03033459 那假设数组后面还有个 1 的话033034591
那么 9 和 1 需要交换030334519而 1 很明显应该要在 0 之后所以排序需要多来几趟就可以用冒泡排序根据相邻两个数字的拼接顺序的后的大小来判断两个数字要不要交换。排完序后就再次遍历数组拼接数组中元素然后返回字符串即可。
代码实现
class Solution {public String crackPassword(int[] password) {// 冒泡排序for (int i 0; i password.length - 1; i) {boolean flg true;for (int j 0; j password.length - 1 - i; j) {// 8 和 7 -- 87 和 78 , 87 78, 则需要交换 String s1 password[j] password[j 1];String s2 password[j 1] password[j];if (s1.compareTo(s2) 0) {int tmp password[j];password[j] password[j 1];password[j 1] tmp;flg false;}}if (flg) break;}// 最后遍历数组拼接字符串即可StringBuilder s new StringBuilder();for (int i 0; i password.length; i) {s.append(password[i]);}return s.toString();}
}// 解法二重写排序方法
class Solution {public String crackPassword(int[] password) {ListString arr new ArrayList();for (int num : password) {arr.add(String.valueOf(num));}arr.sort(new ComparatorString() {public int compare(String s1, String s2) {return (s1 s2).compareTo(s2 s1);}});StringBuilder ans new StringBuilder();for (String x : arr) {ans.append(x);}return ans.toString();}
} 12. LCR 168. 丑数 根据题目可以发现第 n 个丑数其实就是通过前面的丑数 * 2或者丑数 * 3或者丑数 * 5并且按照升序排列得到的所以这道题可以用动态规划来做dp[i] 就表示第 i 个丑数的值。
我们可以先定义三个指针p2p3p5。
p2 表示 dp 数组中还没使用过乘 2 机会的数字的下标(p2 前面的下标对应的数字都使用过 * 2 得到了一个丑数)。p3 和 p5 同理。所以在一开始p2 和 p3 和 p5 都指向初始位置 1dp[1] 1。
然后 dp[i] 就等于 还没使用过乘 2 机会的数字 * 2还没使用过乘 3 机会的数字 * 3还没使用过乘 5 机会的数字 * 5中的最小值然后判断使用这三个指针是否得到了 dp[i]如果是那么对应的下标往后走。最后返回 dp[n] 即可。
代码实现
class Solution {public int nthUglyNumber(int n) {int[] dp new int[n 1];dp[1] 1;// p2 表示 dp 数组中还没使用乘 2 机会的第一个数字所对应的下标int p2 1, p3 1, p5 1;for (int i 2; i n; i) {int num2 dp[p2] * 2, num3 dp[p3] * 3, num5 dp[p5] * 5;// dp[i] 就是这三个数字中最小的那个dp[i] Math.min(num2, num3);dp[i] Math.min(dp[i], num5);if (dp[i] num2) {// 当前下标的数字已经使用过乘 2 机会了那么 p2 需要往后走p2;}if (dp[i] num3) {p3;}if (dp[i] num5) {p5;}}return dp[n];}
} 13. LCR 170. 交易逆序对的总数 第一眼看上就就是两次遍历前一个大于后一个那就 count最后返回 count但是超时了。看题解发现能用归并排序来做在合并数组的时候如果 arr[i] (i left i mid)大于 arr[j] (j mid j right) 则说明至少有 mid - i 1 个逆序对用 count 来记录最后返回 count 即可。
代码实现
class Solution {int count 0;public int reversePairs(int[] record) {// 可以用归并排序来做mergeSort(record, 0, record.length - 1);return count;}public void mergeSort(int[] arr, int left, int right) {// 只有一个元素不用排序if (left right) return;// 二分int mid (left right) / 2;// 分割左边mergeSort(arr, left, mid);// 分割右边mergeSort(arr, mid 1, right);// 合并merge(arr, left, mid, right);}public void merge(int[] arr, int left, int mid, int right) {int[] tmpArr new int[right - left 1];// 合并有序数组int i left, j mid 1, k 0;while (i mid j right) {if (arr[i] arr[j]) {tmpArr[k] arr[i];} else {// 因为 arr[i] arr[j]// 所以 left 到 mid 区间的所有元素都比 arr[j] 大// [1,3,5,9] [2,6,7]// 3 2, 所以 3,5,9 也大于 2count (mid - i 1);tmpArr[k] arr[j];}}while (i mid) {tmpArr[k] arr[i];}while (j right) {tmpArr[k] arr[j];}// 拷贝回原数组for (i left; i right; i) {arr[i] tmpArr[i - left];}}
} 14. LCR 172. 统计目标成绩的出现次数 这个很简单直接遍历数组看看当前元素与 target 是否相同相同就 count最后返回 count 即可。还可以用二分查找来做先查找出数组最前面的 target 的下标然后再找出最后面 target 的下标然后返回下标差 1 即可。
代码实现
class Solution {public int countTarget(int[] scores, int target) {int count 0;for (int i 0; i scores.length; i) {if (scores[i] target) {count;}}return count;}
}// 二分查找
class Solution {public int countTarget(int[] scores, int target) {if (scores null || scores.length 0) return 0;// 通过二分查找找出 target 的左边界int left 0, right scores.length - 1;while (left right) {int mid (left right) / 2;if (scores[mid] target) {right mid;} else {left mid 1;}}// 如果没找到说明数组没有 targetif (scores[left] ! target) return 0;int l left;// 通过二分查找找出 target 的右边界left 0;right scores.length - 1;while (left right) {int mid (left right 1) / 2;if (scores[mid] target) {left mid;} else {right mid - 1;}}return right - l 1;}
} 15. LCR 173. 点名 这个简单可以把 n 位同学的学号加起来得到 sum (从 1 加到 n)然后再遍历数组用 sum 减去数组的和就能得到缺席的同学学号。
也可以用哈希表的方法来写记录数组中每个元素的出现次数然后遍历哈希表第一次遇到出现次数为 0 的就是缺失的数字。
也可以看题能得知数组下标与数组学号是相同的如果不相同那么数组下标就是缺失的数字。
也可以用二分查找缺失的元素在数组的右区间如果 mid arr[mid] 则说明左边不存在缺失元素所以会来到 [mid 1 right] 区间来寻找缺失元素。如果不相等则说明缺失元素很可能就是 mid 本身所以 right mid
代码实现
class Solution {public int takeAttendance(int[] records) {int sum 0;for (int i 0; i records.length; i) {sum i;}for (int i 0; i records.length; i) {sum - records[i];}return sum;}
}// 哈希表
class Solution {public int takeAttendance(int[] records) {int[] hash new int[records.length 1];for (int i 0; i records.length; i) {hash[records[i]];}for (int i 0; i hash.length; i) {if (hash[i] 0) return i;}return 0;}
}class Solution {public int takeAttendance(int[] records) {for (int i 0; i records.length; i) {if (i ! records[i]) return i;}return records[records.length - 1] 1;}
}// 二分查找
class Solution {public int takeAttendance(int[] records) {int left 0, right records.length - 1;while (left right) {int mid left (right - left) / 2;if (mid records[mid]) {// 去右边找不见的元素在数组右边left mid 1;} else {right mid;}}// 0 1 2 3 4if (records[left] left) return left 1;return left;}
} 16. LCR 179. 查找总价格为目标值的两个商品 第一眼就是直接用两次遍历完成但是发现超时了可以用双指针来写定义 left 指向数组最左边right 指向数组最右边数组递增如果 arr[left] arr[right] target说明从arr[left] 与 right 往后的值相加得到的结果还是大于 target所以此时 right 应该往前走。如果 arr[left] arr[right] target说明 arr[left] 太小了所以应该 left 往后走当 arr[left] arr[right] target 时直接返回即可。
代码实现
class Solution {public int[] twoSum(int[] price, int target) {int left 0, right price.length - 1;while (left right) {if (price[left] price[right] target) {right--;} else if (price[left] price[right] target) {left;} else {return new int[]{price[left], price[right]};}}return new int[]{0, 0};}
} 17. LCR 180. 文件组合 直接暴力枚举用两层 for 循环搞定。
还可以用滑动窗口来做大致思路就是进窗口判断出窗口。
代码实现
class Solution {public int[][] fileCombination(int target) {ArrayListint[] ret new ArrayList();for (int i 1; i target; i) {int sum i;for (int j i 1; j target; j) {if (sum target) {int[] arr new int[j - i];for (int k i; k j; k) {arr[k - i] k;}ret.add(arr);break;} else if (sum target) {break;} else {sum j;}}}return ret.toArray(new int[ret.size()][]);}
}class Solution {public int[][] fileCombination(int target) {ArrayListint[] ret new ArrayList();int left 1, right 1;int sum 0;while (left target / 2) {// 说明此时值太小需要 right 往后挪动while (right target sum target) {sum right;right;}if (sum target) {// 记录结果int[] arr new int[right - left];for (int i left; i right; i) {arr[i - left] i;}// 此时说明 right 再往后走sum 也一定大于 target// 则需要寻找下一组 sum那么 left 就需要往后走 ret.add(arr);sum - left;left;} else if (sum target) {// 此时值太大需要减去一些值就可以减去 leftsum - left;left;}}return ret.toArray(new int[ret.size()][]);}
} 18. LCR 183. 望远镜中最高的海拔 如图题目明示你用滑动窗口那这道题就可以用滑动窗口来做。
代码实现
class Solution {public int[] maxAltitude(int[] heights, int limit) {// 如果数组没有元素那么返回的数组也不能有元素if (heights.length 0) return new int[0];// left 为窗口起点right 为窗口终点int left 0, right 0;// count 为当前窗口大小int count 0;// 记录返回值k 为 ret 当前存放元素个数int[] ret new int[heights.length - limit 1];int k 0;while (left heights.length - limit) {if (count limit) {// 没到窗口大小那就入元素right;count;} else if (count limit) {// 从窗口起点到终点找最大值int max Integer.MIN_VALUE;for (int i left; i right; i) {max Math.max(max, heights[i]);}ret[k] max;// 出窗口left;count--;} else {// 超过窗口容量出窗口left;count--;}}return ret;}
} 19. LCR 186. 文物朝代判断 问你数组的数字是否连续0 可以当作万能牌问你 5 张牌能不能组成顺子。
看到这我第一想法就是排序然后遍历数组看看数组是否是连续的如果不是那就记录差了多少个数字然后如果万能牌 0 的个数大于等于差的数字个数则说明数组是连续的但是还得注意如果有相同牌并且相同牌不是 0 的话则说明数组不是连续的。
看大佬的题解发现能直接通过找数组最大值和最小值(除 0 外)然后 max - min 5 则说明连续那这样就好办了可以用 set 来判重遍历数组找最大最小值然后判断即可。
代码实现
class Solution {public boolean checkDynasty(int[] places) {// 先排序然后遍历数组Arrays.sort(places);int count 0;int sum 0;for (int i 0; i places.length - 1; i) {if (places[i] 0) {count;} else {// 不能有相同牌有相同牌就不是顺子了if (places[i] places[i 1]) return false;// 0,0,6,7,9if (places[i] 1 ! places[i 1]) {sum places[i 1] - 1 - places[i];}}}if (count sum) return true;else return false;}
}// set 去重
class Solution {public boolean checkDynasty(int[] places) {SetInteger set new HashSet();int min 14;int max 0;for (int x : places) {if (x 0) continue;// 重复牌if (set.contains(x)) {return false;}max Math.max(x, max);min Math.min(x, min);set.add(x);}return max - min 5;}
} 20. LCR 189. 设计机械累加器 我们可以利用短路逻辑用递归来写递归出口就是当 target 1 时那么我们可以利用短路逻辑与当 target 1 (写要执行的代码)最后再将后面部分改成值恒为真的布尔表达式最后再返回即可。
代码实现
class Solution {public int mechanicalAccumulator(int target) {// 用递归可以利用短路逻辑来写// 如果 target 1则递归停止否则返回就相加boolean flg target 1 (target mechanicalAccumulator(target - 1)) 0;return target;}
} 21. LCR 191. 按规则计算统计结果 这道题不算难让你求 arrB[i] 为数组 arrA 中除了 arrA[i] 外所有元素的乘积只需要把 arrA 数组遍历一遍求出除了 0 外所有元素的乘积 mul并记录 arrA 中 0 的个数然后用 mul / arrA[i] 就能得到对应的 arrB[i]然后返回 arrB 即可。
但是有个毒点那就是要考虑 arrA 中含有元素 0 的情况但是这个 0 也要分情况讨论
如果 0 只有一个那么其他元素相乘就都是 0而 0 对应的元素既是其他元素的乘积。
如果 0 有两个及以上那么返回的数组 arrB 的所有元素就都是 0 了。
根据以上思路代码就很好写啦。
还有另一种方法看题解知道的可以创建个数组 left 和 rightleft[i] 表示 arrA[i] 以前的元素乘积(不包括 arrA[i])right[i] 表示 arrA[i] 以后的元素乘积(不包括 arrA[i])这样 arrB[i] left[i] * right[i]。
代码实现
class Solution {public int[] statisticalResult(int[] arrayA) {int mul 1;// 记录数组中 0 的个数int count 0;int[] arrB new int[arrayA.length];// 求出数组每个元素的乘积(除 0 外)for (int i 0; i arrayA.length; i) {if (arrayA[i] 0) {count;continue;}mul * arrayA[i];}if (count 2) {// 说明数组中有两个及以上的 0 ,则值一定全是 0return new int[arrayA.length];}for (int i 0; i arrB.length; i) {if (count 0) {// 此时说明数组中含有一个 0则除 0 外所有数组都是 0if (count 1) {if (arrayA[i] ! 0) {arrB[i] 0;} else {arrB[i] mul;}}} else {// 数组中没 0正常执行arrB[i] mul / arrayA[i];}}return arrB;}
}class Solution {public int[] statisticalResult(int[] arrayA) {// 边界情况if (arrayA null || arrayA.length 0) return new int[0];int[] left new int[arrayA.length];left[0] 1;// 遍历数组初始化 left 的值for (int i 1; i arrayA.length; i) {left[i] left[i - 1] * arrayA[i - 1];}// 记录右边的元素乘积int right 1;for (int i left.length - 1; i 0; i--) {left[i] * right;right * arrayA[i];}return left;}
} 字符串
22. LCR 122. 路径加密 这个很简单遍历判断即可然后用 StringBuilder 即可。
代码实现
class Solution {public String pathEncryption(String path) {StringBuilder str new StringBuilder();for (int i 0; i path.length(); i) {char ch path.charAt(i);if (ch ! .) {str.append(ch);} else {str.append( );}}return str.toString();}
} 23. LCR 138. 有效数字 一种比较简单的做法就是判断该字符串不是有效数字的情况严格按照题目规定的顺序来判断字符串按照 空格(正负号)数字(点)数字(eE数字)空格
定义四个 flg 来判断字符串中是否有数字E/e正负号点。
先从 0 下标开始遍历字符串一直跳过空格。 从非空格的地方开始判断如果是数字那就将数字 flg 置为 true然后跳过这一连续的数字然后判断下标是否已经遍历完字符串如果是就返回 true。 如果当前字符是 E/e如果已经出现过 E/e 之前没有出现过数字则返回 false否则将 E/e flg 置为 true再将其他三个 flg 置为 false往 E 之后重新开始找数字。 如果当前字符是正负号如果已经出现过符号数字点就返回 false否则将 符号 flg 置为 true。 如果当前字符是空格则说明下标已经遍历到字符串末尾的空格或者空格被字符之间夹起来了则退出循环单独判断。 如果是上述以外的字符就返回 false。 出了循环就处理末尾空格的情况一直跳过空格如果 下标为字符串长度并且数字 flg 是 true则返回 true否则返回 false 代码实现
class Solution {public boolean validNumber(String s) {// 是否有数字E正负号点boolean hasNum false;boolean hasE false;boolean hasSign false;boolean hasDot false;// 先跳过开头的空格int index 0, len s.length();while (index len s.charAt(index) ) {index;}// 从非空格的字符开始判断// 顺序严格按照 空格正负号数字(点)数字eE数字 空格while (index len) {if (isNum(s.charAt(index))) {hasNum true;// 如果是数字while (index len isNum(s.charAt(index))) {index;}// 说明字符串全是数字if (index len) return true;}// 到这里就字符就一定是非数字的char c s.charAt(index);if (c e || c E) {// 如果出现多个 E或者之前没有出现过数字if (hasE || !hasNum) {return false;}hasE true;// 将其他三个 flg 置为 false继续从 E 往后找新的数字hasNum false;hasSign false;hasDot false;} else if (c || c -) {// 如果之前出现过符号或者数字或者.则返回 falseif (hasSign || hasNum || hasDot) {return false;}hasSign true;} else if (c .) {// 如果之前出现过点或者 eEif (hasDot || hasE) {return false;}hasDot true;} else if (c ) {// 说明此时可能到了字符串末尾的空格也可能是夹在字符间的空格需要额外处理。break;} else {// 其他非法字符return false;}index;}// 处理末尾空格while (index len s.charAt(index) ) {index;}if (index len hasNum) {return true;}return false;}public boolean isNum(char c) {if (c 0 c 9) return true;return false;}
} 24. LCR 157. 套餐内商品的排列顺序 这道题可以用深搜来做还是用那一套模板定义 flg 数组表示对应的 str[j] 是否被遍历过注意去重可以用 是否是从左往右第一个未被填入的字符来判断( j 0 flg[j - 1] false flg[j - 1] flg[j])所以需要先对数组 str 进行排序再从 0 下标开始遍历如果该字符已经遍历过或者不是从左往右第一个未被填入的字符那就 continue否则就将该字符 append 进 tmp 中然后继续生成下一个位置的字符然后就是回溯将 flg[j] false并且将 str[j] 从 tmp 中删除。递归的出口就是当要生成的字符位置为 str.length 时则说明字符生成完毕将 tmp 添加进结果集合中然后返回。
代码实现
class Solution {ListString arr;boolean[] flg;public String[] goodsOrder(String goods) {arr new ArrayList();int len goods.length();flg new boolean[len];// 用深搜 回溯char[] str goods.toCharArray();Arrays.sort(str);StringBuilder tmp new StringBuilder();dfs(str, 0, len, tmp);String[] ret new String[arr.size()];for (int i 0; i ret.length; i) {ret[i] arr.get(i);}return ret;}public void dfs(char[] str, int i, int len, StringBuilder tmp) {if (i len) {// 说明已经生成完 len 个字符了arr.add(tmp.toString());return;}// 从 0 开始生成第 i 位置的字符一共有 len 中可能性for (int j 0; j len; j) {// 判断是否已经生成过该字符, 是否是从左往右第一个未被填入的字符if (flg[j] || (j 0 !flg[j - 1] str[j - 1] str[j])) {continue;}tmp.append(str[j]);flg[j] true;// 生成下一个字符dfs(str, i 1, len, tmp);// 回溯tmp.deleteCharAt(tmp.length() - 1);flg[j] false;}}
} 25. LCR 167. 招式拆解 I 可以用滑动窗口和哈希表来做定义 count 来记录最长连续不重复字符定义 left 和 right 两个指针指向 0用 set 来记录连续不重复字符如果 arr[right] 是不重复字符则添加到 set 里然后 right直到遇到重复字符那就先判断 set 的大小与 count 谁大如果 set 大则更新 count然后再让 left 跳过重复字符right 跳过重复字符往后开始找新的连续不重复字符最后返回 count 即可。
代码实现
class Solution {public int dismantlingAction(String arr) {if (arr null || arr.length() 0) return 0;// 感觉可以用滑动窗口来做int count 1;int left 0;int right 0;int len arr.length();// set 用来记录连续不重复的字符SetCharacter set new HashSet();while (right len) {// 如果 arr[right] 不在 set 里说明它不是重复字符// 则将 arr[right] 添加进 set 中并让 right 往后走while (right len !set.contains(arr.charAt(right))) {set.add(arr.charAt(right));}if (right len) {break;}// 如果 arr[right] 是重复字符 x 则让 left 一直往后走// 直到跳过这个重复字符然后最后再将重复字符 x 添加进 set 中// right 继续往后找连续不重复字符if (set.contains(arr.charAt(right))) {// 判断更新if (set.size() count) {count set.size();}// 出窗口char ch arr.charAt(right);while (left right arr.charAt(left) ! ch) {set.remove(arr.charAt(left));}// set.remove(arr.charAt(left));// set.add(ch);// left 跳过该重复字符left;// 从重复字符往后开始找新的连续不重复字符right;}}// 还需判断一次防止漏掉最后的连续不重复字符if (set.size() count) count set.size();return count;}
} 26. LCR 169. 招式拆解 II 这个简单用哈希表来做就行记录每个字符出现的次数然后再次遍历字符串第一个出现次数为 1 的字母就是结果如果到最后都没出现则返回空格。
代码实现
class Solution {public char dismantlingAction(String arr) {int[] hash new int[26];for (int i 0; i arr.length(); i) {char ch arr.charAt(i);hash[ch - a];}for (int i 0; i arr.length(); i) {char ch arr.charAt(i);if (hash[ch - a] 1) {return ch;}}char c ;return c;}
} 27. LCR 181. 字符串中的单词反转 这个也简单整体思路就是先将整个字符串逆序然后再分别逆序每个单词可以用双指针来做i 为 单词的开始下标end 为单词的结束下标的下一个先让 i 一直跳过空格找到字母或数字然后 end 从 i 开始只要不是空格end 就往后走当 end 停下来时end - 1 就是单词结尾逆序 i 到 end - 1 范围的字符然后 i 再从 end 开始走。最后 i 重新遍历字符串数组不是空格就一直添加进 ret 中是空格就跳过然后判断 i 是否越界越界就跳出循环然后如果 ret 不为空就添加一个空格到 ret 中最后返回 ret.toString() 即可。
代码实现
class Solution {public String reverseMessage(String message) {char[] arr message.toCharArray();// 逆序整个字符串reverse(arr, 0, arr.length - 1);// 每个单词逆序int i 0;while (i arr.length) {// 跳过空格while (i arr.length arr[i] ) {i;}// 到这里 i 一定是数字或者字母int end i;while (end arr.length arr[end] ! ) {end;}// 到这里 end 一定是空格i 到 end - 1 则是单词reverse(arr, i, end - 1);i end;}StringBuilder str new StringBuilder();for (i 0; i arr.length; ) {while (i arr.length arr[i] ! ) {str.append(arr[i]);}while (i arr.length arr[i] ) {i;}// 防止句尾添加多余空格if (i arr.length) {break;}// 防止开头添加空格if (str.length() ! 0) {str.append( );}}return str.toString();}public void reverse(char[] arr, int left, int right) {while (left right) {char tmp arr[left];arr[left] arr[right];arr[right--] tmp;}}
} 28. LCR 182. 动态口令 这个也很简单直接使用 substring 方法截取字符串最后拼接返回即可。
要是不让使用 substring 方法那就自己遍历字符串即可。这个还可以简化一下通过求余运算来简化。还有另一种方法那就是先逆序整个字符串然后再分别逆序 (0len - t) 和 (len - t len)。
代码实现
class Solution {public String dynamicPassword(String password, int target) {String str2 password.substring(0, target);String str1 password.substring(target);String ret str1 str2;return ret;}
}class Solution {public String dynamicPassword(String password, int target) {StringBuilder ret new StringBuilder();for(int i target; i password.length(); i){ret.append(password.charAt(i));}for(int i 0; i target; i){ret.append(password.charAt(i));}return ret.toString();}
}
// 简化后
class Solution {public String dynamicPassword(String password, int target) {StringBuilder ret new StringBuilder();for(int i target; i password.length() target; i){ret.append(password.charAt(i % password.length()));}return ret.toString();}
}// 逆序
class Solution {public String dynamicPassword(String password, int t) {// a b c d e t 2,len 5// c d e a b (2)// e d c b a (3)// 要从 3 变到 2需要逆序 (0,len - t) 和 (len - t, len)char[] arr password.toCharArray();int len arr.length;reverse(arr, 0, len - 1);reverse(arr, 0, len - 1 - t);reverse(arr, len - t, len - 1);return new String(arr);}public void reverse(char[] arr, int left, int right) {while (left right) {char tmp arr[left];arr[left] arr[right];arr[right--] tmp;}}
} 29. LCR 192. 把字符串转换成整数 (atoi) 直接严格按照题目要求来写 1. 首先跳过字符串的前导空格 2. 然后看下一个字符是不是正号负号 3. 然后再从下一个字符开始一直读数字字符如果该字符不是数字字符就直接返回 4. 将上面读到的数字串转化为 int且跳过前导 0。 5. 如果最后数字大于 int 最大值返回 int 最大值如果数字小于 int 最小值返回 int 最小值如果没有读到数字返回 0。 代码实现
class Solution {public int myAtoi(String str) {int i 0;int len str.length();// 是否是负数boolean flg false;// 记录正负号数量int flgOp 0;// 记录数字串StringBuilder num new StringBuilder();// 跳过前导空格while (i len str.charAt(i) ) {i;}// 下一个字符是否是正负号如果正负号或点号大于等于 2则返回 0if (i len str.charAt(i) -) {flgOp;flg true;i;}if (i len str.charAt(i) ) {flgOp;i;}// 如果该字符不是数字则返回 0if (i len !isNum(str.charAt(i))) {return 0;}// 记录 从 i 开始一直到非数字的整个数字范围int end i;while (end len isNum(str.charAt(end))) {end;}String tmp str.substring(i, end);// 添加进数字字符串中num.append(tmp);// 到这里就是非数字部分直接退出// 正负号数量大于 1则说明字符串不合法if (flgOp 2) {return 0;}double sum 0;// 用 i 遍历 num 数字串i 0;// 根据 num 字符串计算结果// 跳过前导 0while (i num.length() num.charAt(i) 0) {i;}while (i num.length()) {int t num.charAt(i) - 0;sum (sum * 10 t);i;}// 如果是负数if (flg) {sum * -1;}if (sum Integer.MAX_VALUE - 1) {return Integer.MAX_VALUE;} else if (sum Integer.MIN_VALUE) {return Integer.MIN_VALUE;} else {return (int) sum;}}public boolean isNum(char c) {return c 0 c 9;}
} 链表
30. LCR 123. 图书整理 I 这个简单直接翻转链表然后添加到数组中即可。
还可以用递归实现。
代码实现
class Solution {public int[] reverseBookList(ListNode head) {if (head null) return new int[0];// 头插法ListNode prev head;ListNode cur head.next;prev.next null;int len 1;while (cur ! null) {ListNode curNext cur.next;cur.next prev;prev cur;cur curNext;len;}int[] ret new int[len];int i 0;cur prev;while (cur ! null) {ret[i] cur.val;cur cur.next;}return ret;}
}// 递归
class Solution {public int[] reverseBookList(ListNode head) {getList(head);int[] ret new int[arr.size()];for (int i 0; i ret.length; i) {ret[i] arr.get(i);}return ret;}public ListInteger arr new ArrayList();public void getList(ListNode cur) {if (cur null) return;getList(cur.next);arr.add(cur.val);}
} 31. LCR 136. 删除链表的节点 这道题很简单只要删除第一次出现的 val 元素即可定义两个指针 prev 和 curprev 指向 cur 的前一个元素cur 遍历链表如果此时 cur.val val那就删除 cur然后直接返回头节点否则就让 prev 和 head 一直往后走到最后如果 head.val val那就返回 head.next 即可。
代码实现
class Solution {public ListNode deleteNode(ListNode head, int val) {if (head null) return null;ListNode prev head;ListNode cur head.next;while (cur ! null) {if (cur.val val) {prev.next cur.next;cur cur.next;return head;} else {prev cur;cur cur.next;}}if (head.val val) head head.next;return head;}
} 32. LCR 140. 训练计划 II 这个可以用快慢指针来做定义 slow 和 fast 指向 head先让 fast 走 cnt - 1 步然后再让 fast 和 slow 一起走当 fast 走到链表最后一个节点的位置时slow 就是倒数第 cnt 个节点的位置。
代码实现
class Solution {public ListNode trainingPlan(ListNode head, int cnt) {ListNode fast head;ListNode slow head;while (cnt - 1 ! 0) {fast fast.next;if (fast null) {return null;}cnt--;}while (fast.next ! null) {fast fast.next;slow slow.next;}return slow;}
} 33. LCR 141. 训练计划 III 这个简单直接逆序链表采用头插法即可。
代码实现
class Solution {public ListNode trainningPlan(ListNode head) {// 采用头插法即可if (head null || head.next null) return head;ListNode prev head;ListNode cur head.next;// 防止代码成环prev.next null;while (cur ! null) {ListNode curNext cur.next;cur.next prev;prev cur;cur curNext;}return prev;}
} 34. LCR 142. 训练计划 IV 思路跟合并有序链表大差不差。
代码实现
class Solution {public ListNode trainningPlan(ListNode l1, ListNode l2) {if (l1 null) return l2;if (l2 null) return l1;// 虚拟头节点返回时返回 dummy.nextListNode dummy new ListNode(-1);ListNode cur dummy;// 其实跟合并有序数组差不多while (l1 ! null l2 ! null) {if (l1.val l2.val) {cur.next l1;l1 l1.next;cur cur.next;} else {cur.next l2;l2 l2.next;cur cur.next;}}if (l1 ! null) {cur.next l1;}if (l2 ! null) {cur.next l2;}return dummy.next;}
} 35. LCR 171. 训练计划 V 找链表相交节点这个可以用快慢指针来做先让 fast 走差值步然后 fast 和 slow 一起走当 fast 和 slow 相遇时就是链表相交节点。
代码实现
class Solution {ListNode getIntersectionNode(ListNode headA, ListNode headB) {if (headA null || headB null) return null;int countA 0;int countB 0;ListNode fast headA;ListNode slow headB;while (fast ! null) {fast fast.next;countA;}while (slow ! null) {slow slow.next;countB;}fast headA;slow headB;int len countA - countB;if (len 0) {len countB - countA;fast headB;slow headA;}while (len ! 0) {fast fast.next;len--;}while (fast ! slow) {fast fast.next;slow slow.next;}return fast;}
} 36. LCR 154. 复杂链表的复制 让你复制一份链表可以用哈希表来做将老节点与新节点的对应关系存入哈希表中最后重新遍历链表根据哈希表来获取新节点然后建立联系即可。 代码实现
class Solution {public Node copyRandomList(Node head) {if (head null) return null;Node dummy new Node(-1);Node cur head;MapNode, Node hash new HashMap();// 将老节点与新节点的关系存起来while (cur ! null) {Node node new Node(cur.val);hash.put(cur, node);cur cur.next;}cur head;while (cur ! null) {hash.get(cur).next hash.get(cur.next);hash.get(cur).random hash.get(cur.random);cur cur.next;}return hash.get(head);}
} 栈和队列
37. LCR 147. 最小栈 可以用两个栈来实现一个栈当做正常的栈另一个栈来存储最小值的栈。
入栈时正常栈正常入栈如果最小栈为空那么也入栈如果不为空那么入栈的值 val 就需要与最小栈的栈顶元素比较如果小于等于栈顶元素那么 val 就入最小栈。
出栈时首先需要判断两个栈是否为空如果两个栈都为空则不能出栈否则正常栈正常出栈即可。获取栈顶元素也同理。
如果是获取最小栈栈顶元素那还是得先判断最小栈是否为空为空的话返回 -1如果不为空直接返回最小栈.peek() 即可。
代码实现
class MinStack {// 可以用一个栈当正常栈// 一个栈当最小栈StackInteger s1 new Stack();StackInteger s2 new Stack();/*** initialize your data structure here.*/public MinStack() {s1 new Stack();s2 new Stack();}public void push(int x) {s1.push(x);if (s2.empty()) {s2.push(x);} else {int top s2.peek();if (x top) {s2.push(x);}}}public void pop() {if (s1.empty()) {return;}int top s1.pop();if (!s2.empty() s2.peek() top) {s2.pop();}}public int top() {if (s1.empty()) {return -1;}return s1.peek();}public int getMin() {if (s2.empty()) {return -1;}return s2.peek();}
} 38. LCR 125. 图书整理 II 简单来说就是让你用栈实现队列那这个也简单大体思路就是直接定义两个栈固定一个栈 1 入元素另一个栈 2 出元素如果栈 2 为空那么就把栈 1 的所有元素出栈并入到栈 2 2中此时 栈 2 再出栈。
代码实现
class CQueue {// 用栈来实现队列StackInteger s1 new Stack();StackInteger s2 new Stack();public CQueue() {s1 new Stack();s2 new Stack();}public void appendTail(int value) {s1.push(value);}public int deleteHead() {if (s1.empty() s2.empty()) {return -1;}if (s2.empty()) {while (!s1.empty()) {s2.push(s1.pop());}}return s2.pop();}
} 39. LCR 184. 设计自助结算系统 这道题的难点是如何用 O(1) 的时间获取的最大值因为最大值的候补者有许多个如何在删除最大值的时候快速找到下一个最大值。我们可以用普通队列和双端队列实现双端队列用来存储最大值的候补者并将这些最大值的候补者按照降序来排序那么双端队列的第一个元素就一定是最大值。而普通队列就正常进行操作就行但是双端队列进行操作时就需要进行判断。
在新增元素时双端队列如果为空那么该元素可能是最大值则从尾巴入队。如果双端队列不为空就需要判断队列的尾巴元素与当前元素 val 比较如果 val 比尾巴元素要大则说明尾巴元素就一定不可能是最大值了所以一直出队直到遇到尾巴元素比当前元素 val 大或者等于当前元素。那么此时当前元素就可以从尾巴入队了。
删除元素时首先判断正常队列是否为空如果为空则直接返回如果不为空则正常队列出队得到了 top 元素还需要去看看双端队列的头元素是否与 top 相同如果相同则双端队列把头元素出队。
代码实现
class Checkout {// 可以用队列和双端队列实现QueueInteger queue;// 双端队列存储可能是最大值的元素并且按照降序存储DequeInteger maxQueue;public Checkout() {queue new LinkedList();maxQueue new LinkedList();}public int get_max() {if (maxQueue.isEmpty()) {return -1;}// 取出双端队列的头元素就是最大值return maxQueue.peekFirst();}public void add(int value) {queue.offer(value);// 如果双端队列为空则当前元素可能是最大值入队if (maxQueue.isEmpty()) {maxQueue.offerLast(value);return;}// 如果不为空则需要判断如果当前 val 大于双端队列的尾巴元素// 说明此时双端队列的尾巴元素一定不可能是最大值要保持最大值降序排序// 那就把双端队列的尾巴元素删掉然后把 val 添加进来while (!maxQueue.isEmpty() value maxQueue.peekLast()) {maxQueue.pollLast();}maxQueue.offerLast(value);}public int remove() {if (queue.isEmpty()) {return -1;}// 删除时也同理需要判断删除的元素是否与 max 的头元素相同// 如果相同则 max 也需要出队int top queue.poll();if (top maxQueue.peekFirst()) {maxQueue.pollFirst();}return top;}
} 40. LCR 148. 验证图书取出顺序 这道题不难就是遍历入栈数组先将里面的元素入栈然后判断栈顶元素与出栈元素是否相同如果是那就出栈并且用 j 来遍历出栈数组j。
如果最后栈里为空则返回 true否则返回 false。
代码实现
class Solution {public boolean validateBookSequences(int[] putIn, int[] takeOut) {StackInteger stack new Stack();int j 0;for (int i 0; i putIn.length; i) {stack.push(putIn[i]);while (!stack.empty() stack.peek() takeOut[j]) {stack.pop();j;}}if (stack.empty()) {return true;}return false;}
} 树
41. LCR 124. 推理二叉树 代码实现
class Solution {public int preIndex;public TreeNode deduceTree(int[] preorder, int[] inorder) {TreeNode root createTree(inorder, preorder, 0, preorder.length - 1);return root;}public TreeNode createTree(int[] inorder, int[] preorder, int start, int end) {if (start end) return null;TreeNode root new TreeNode(preorder[preIndex]);// 找下标int rootIndex getRootIndex(inorder, start, end, preorder[preIndex]);preIndex;if (rootIndex -1) return root;// 按照前序遍历来创建二叉树root.left createTree(inorder, preorder, start, rootIndex - 1);root.right createTree(inorder, preorder, rootIndex 1, end);return root;}// 在中序遍历中找到根节点public int getRootIndex(int[] inorder, int start, int end, int key) {for (int i start; i end; i) {if (inorder[i] key) {return i;}}return -1;}
} 42. LCR 143. 子结构判断 这道题思路跟找子树差不多区别就是找子树时树 1 和树 2 的结构必须完全相同并且对应的值也必须相同但是这里如图例 2 这里当树 2 为空时树 1 可以不为空。所以在写找子树代码时还可以分以下情况修改修改。
总体思路就是找子树子树要结构相同并且值相同左子树相同并且右子树相同才是子树可以用前序遍历来做每遍历到一个节点都去看看当前节点是否就是子树。但是得注意当两棵树都为空时要返回 false。
代码实现
class Solution {public boolean isSubStructure(TreeNode A, TreeNode B) {// 题目要求如果两棵树都为空则返回 falseif (A null B null) {return false;}if (A null B ! null || A ! null B null) return false;return isSubTree(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);}public boolean isSubTree(TreeNode p, TreeNode q) {// 1. 值相同 2. 结构相同if (p null q null) return true;if (p null q ! null) return false;// 当 q 为空时p 可以不为空if (p ! null q null) return true;// 值不相同if (p.val ! q.val) return false;return isSubTree(p.left, q.left) isSubTree(p.right, q.right);}
} 43. LCR 144. 翻转二叉树 这个很简单就是左子树跟右子树交换即可。用前序遍历每一个节点的左孩子和右孩子交换即可。
代码实现
class Solution {public TreeNode mirrorTree(TreeNode root) {if (root null) return null;TreeNode tmp root.left;root.left root.right;root.right tmp;mirrorTree(root.left);mirrorTree(root.right);return root;}
} 44. LCR 145. 判断对称二叉树 这道题就是判断二叉树是否对称前提条件就是得判断结构对称并且值也得对称并且左孩子 1的左孩子 2 和右孩子 1 的右孩子 2 对称并且左孩子 1 的右孩子 2 与右孩子 1 的左孩子 2 对称。
代码实现
class Solution {public boolean checkSymmetricTree(TreeNode root) {if (root null) return true;return isSymmetricTree(root.left, root.right);}public boolean isSymmetricTree(TreeNode p, TreeNode q) {// 1. 结构相同 2. 值相同if (p null q null) return true;if (p null q ! null || p ! null q null) return false;if (p.val ! q.val) return false;// 对称如图示例一return isSymmetricTree(p.left, q.right) isSymmetricTree(p.right, q.left);}
} 45. LCR 149. 彩灯装饰记录 I 就是二叉树层序遍历利用队列实现即可如果队列不为空那就先出队 top如果左子树不为空那就将左子树入队如果右子树不为空那就将右子树入队然后再将 top 添加到数组中最后返回数组即可。
代码实现
class Solution {public int[] decorateRecord(TreeNode root) {if (root null) return new int[0];QueueTreeNode queue new LinkedList();queue.offer(root);ListInteger arr new ArrayList();while (!queue.isEmpty()) {TreeNode top queue.poll();arr.add(top.val);if (top.left ! null) {queue.offer(top.left);}if (top.right ! null) {queue.offer(top.right);}}int[] ret new int[arr.size()];for (int i 0; i ret.length; i) {ret[i] arr.get(i);}return ret;}
} 46. LCR 150. 彩灯装饰记录 II 与上一题代码基本一致就是在进入循环时判断队列中有多少元素 size队列中 size 的个数就是这一层节点的个数然后循环出队 size 次就把这层节点元素全部拿到了最后添加进数组中然后返回数组即可。
代码实现
class Solution {public ListListInteger decorateRecord(TreeNode root) {ListListInteger ret new ArrayList();if (root null) return ret;QueueTreeNode queue new LinkedList();queue.offer(root);while (!queue.isEmpty()) {ListInteger arr new ArrayList();int size queue.size();while (size ! 0) {TreeNode top queue.poll();arr.add(top.val);if (top.left ! null) {queue.offer(top.left);}if (top.right ! null) {queue.offer(top.right);}size--;}ret.add(arr);}return ret;}
} 47. LCR 151. 彩灯装饰记录 III 跟层序遍历差不多就是逆转了下双数层的值的顺序可以利用 Collections.reverse 方法来完成。
代码实现
class Solution {public ListListInteger decorateRecord(TreeNode root) {ListListInteger ret new ArrayList();if (root null) return ret;QueueTreeNode queue new LinkedList();queue.add(root);boolean flg true;while (!queue.isEmpty()) {int size queue.size();ListInteger arr new ArrayList();while (size ! 0) {TreeNode top queue.poll();arr.add(top.val);if (top.left ! null) {queue.add(top.left);}if (top.right ! null) {queue.add(top.right);}size--;}if (!flg) {Collections.reverse(arr);}flg !flg;ret.add(arr);}return ret;}
} 48. LCR 152. 验证二叉搜索树的后序遍历序列 二叉搜索树就是左子树小于根节点右子树大于根节点所以只需要判断通过递归来判定所有节点都符合上面的要求那么这棵树就是二叉搜索树。先划分左右子树的区间找到第一个右子树的节点(节点值大于根节点)然后再判断右子树区间的值是否全都比根节点大如果不是返回 false如果是则递归去判断左子树和右子树。
代码实现
class Solution {public boolean verifyTreeOrder(int[] postorder) {return verifyTreeOrder(postorder, 0, postorder.length - 1);}public boolean verifyTreeOrder(int[] postorder, int start, int end) {if (start end) return true;// 以 end 为根节点划分左子树和右子树int root postorder[end];// 往后找大于 root 的值, 找到第一个右子树节点int cur start;while (postorder[cur] postorder[end]) cur;// 此时 postorder[cur] 一定大于 rootint mid cur;// mid, end 就是右子树范围while (postorder[cur] postorder[end]) cur;// 到这里start, mid - 1 是左子树, m,end - 1 是右子树return cur end verifyTreeOrder(postorder, start, mid - 1) verifyTreeOrder(postorder, mid, end - 1);}
} 49. LCR 153. 二叉树中和为目标值的路径 可以用深搜来做定义一个数组 arr 来存放遍历的节点定义一个 sum 用来记录当前遍历过所有节点的和用前序遍历去遍历每一个节点先将 root 的值添加进 arr 和 sum 中如果 sum 等于 target 并且此时是叶子节点就添加进返回结果中然后再删除数组 arr 当前节点sum 减等当前节点值最后返回结果其他情况就继续遍历左子树并将遍历的结果添加进返回结果中右子树同理最后再删除 arr 里当前节点值sum 减去当前节点值最后再返回结果即可。
代码实现
class Solution {public ListListInteger pathTarget(TreeNode root, int target) {dfs(root, target);return ret;}public int sum 0;public ListInteger arr new ArrayList();public ListListInteger ret new ArrayList();public void dfs(TreeNode root, int target) {if (root null) return;arr.add(root.val);sum root.val;if (sum target root.left null root.right null) {ret.add(new ArrayList(arr));arr.remove(arr.size() - 1);sum - root.val;return;}dfs(root.left, target);dfs(root.right, target);arr.remove(arr.size() - 1);sum - root.val;}
} 50. LCR 155. 将二叉搜索树转化为排序的双向链表 将二叉搜索树转化为排序的双向链表可以利用二叉搜索树的中序遍历是有序的特点可以定义 cur 和 prev 两个指针prev 是 cur 的中序遍历的前一个节点先递归往 cur 的右边走然后判断 prev 是否为空如果为空说明此时 cur 就是链表头节点记录一下。如果不为空就可以进行修改指向了prev.right cur。 cur.left prev然后再让 prev 往后走继续递归 cur 的右边。递归结束后prev 就是链表的尾巴节点只需要修改一下链表头节点和尾巴节点的指向最后再返回即可。
代码实现
class Solution {public Node treeToDoublyList(Node root) {if (root null) return null;dfs(root);// 最后 prev 一定就是尾巴节点head.left prev;prev.right head;return head;}public Node prev null;public Node head null;// 中序遍历public void dfs(Node cur) {if (cur null) return;dfs(cur.left);if (prev null) {head cur;} else {prev.right cur;}cur.left prev;// prev 往后走prev cur;dfs(cur.right);}
} 51. LCR 156. 序列化与反序列化二叉树 序列化就是将二叉树转化成字符串反序列化就是将字符串转化成二叉树这道题可以用层序遍历来做在序列化时可以将节点为空的情况也添加到字符串中每个节点以逗号分隔。
可以从第一层节点开始从左到右从上到下都编一个号从 0 开始编号那么当前节点 cur 编号为 i则 2*i 1 是 cur 的左孩子2*i 2 是 cur 右孩子根据这个来进行反序列化因为是按照层序遍历的方式序列化的所以也是按照层序遍历的方式来反序列化将创建的节点都添加到队列中先按照 , 来分隔字符串这样每个字符串 str[i] 就都是一个节点i 从 0 开始如果队列不为空就出队一个元素 top如果 top 不为空说明 top 是一个节点就说明 top 可能会有左右孩子就分别判断 2*i 1 和 2*i 2 是否越界如果没有越界并且对应的 str[2*i 1] 不为空和 str[2*i 2] 不为空则说明存在左孩子或者右孩子则将左孩子和右孩子添加进队列中并让 top 的 left 和 right 分别指向左右孩子。然后 i 往后走最后返回 root 即可。
代码实现
public class Codec {// Encodes a tree to a single string.public String serialize(TreeNode root) {if (root null) return [];// 可以利用层序遍历实现QueueTreeNode queue new LinkedList();StringBuilder str new StringBuilder([);queue.offer(root);while (!queue.isEmpty()) {TreeNode top queue.poll();if (top ! null) {str.append(top.val ,);queue.offer(top.left);queue.offer(top.right);} elsestr.append(null,);}str.deleteCharAt(str.length() - 1);str.append(]);return str.toString();}// Decodes your encoded data to tree.public TreeNode deserialize(String data) {if (data.equals([])) {return null;}// 点号分隔那就是每个节点 [1,2,3,null,null,4,5,null,null]String[] arr data.substring(1, data.length() - 1).split(,);TreeNode root new TreeNode(Integer.valueOf(arr[0]));// 用层序遍历的方式解析// 从 0 下标开始编号如果该节点不为空则:// 左子树 2*i 1// 右子树 2*i 2QueueTreeNode queue new LinkedList();queue.offer(root);int i 0;while (!queue.isEmpty()) {TreeNode top queue.poll();if (2 * i 1 arr.length !arr[2 * i 1].equals(null)) {TreeNode left new TreeNode(Integer.valueOf(arr[2 * i 1]));queue.offer(left);top.left left;}if (2 * i 2 arr.length !arr[2 * i 2].equals(null)) {TreeNode right new TreeNode(Integer.valueOf(arr[2 * i 2]));queue.offer(right);top.right right;}// i 去遍历后一个节点i;}return root;}
} 52. LCR 174. 寻找二叉搜索树中的目标节点 一眼看到求第 k 大元素那就可以用优先级队列来解决创建小根堆用前序遍历当小堆元素个数小于 cnt 时那就入堆如果元素个数大于等于 cnt那就判断一下 root.val 与堆顶元素谁大如果 root.val 大那么小堆出队然后将 root.val 添加进小堆中然后继续遍历左子树和右子树。
遍历完成后小堆的堆顶元素就是第 cnt 大元素。
代码实现
class Solution {public int findTargetNode(TreeNode root, int cnt) {PriorityQueueInteger queue new PriorityQueue();getKMax(root, cnt, queue);return queue.peek();}public int i;public void getKMax(TreeNode root, int cnt, PriorityQueueInteger queue) {if (root null) return;if (i cnt) {queue.offer(root.val);} else {int top queue.peek();int val root.val;if (val top) {queue.poll();queue.offer(val);}}i;getKMax(root.left, cnt, queue);getKMax(root.right, cnt, queue);}
}
看了大佬的题解后发现可以利用二叉搜索树的中序遍历是有序的来做,求第 K 大元素那我们就可以中序遍历反着遍历此时遇到的第 K 个元素就是第 K 大元素。
代码实现
class Solution {public int findTargetNode(TreeNode root, int cnt) {getMax(root, cnt);return kMax;}public int i 1;public int kMax 0;public void getMax(TreeNode root, int cnt) {if (root null) return;// 中序: 左根右// 反着来:右根左getMax(root.right, cnt);if (i cnt) {kMax root.val;}i;if (i cnt) return;getMax(root.left, cnt);}
} 53. LCR 175. 计算二叉树的深度 这个很简单让你计算二叉搜索树的高度可以用递归来做整棵树的高度就等于左子树高度和右子树的高度的最大值再加上自己这个节点本身也就是 1 。
代码实现
class Solution {public int calculateDepth(TreeNode root) {if (root null) return 0;int leftHeight calculateDepth(root.left);int rightHeight calculateDepth(root.right);return Math.max(leftHeight, rightHeight) 1;}
} 54. LCR 176. 判断是否为平衡二叉树 这个也很简单可以在计算树的高度的时候去判断是否是平衡二叉树。如果是则正常返回高度如果不是则返回 -1 即可最后只需要判断得到的高度是否大于等于 0。
代码实现
class Solution {public boolean isBalanced(TreeNode root) {// 可以在计算树的高度时也判断是否是平衡二叉树return getHeight(root) 0;}public int getHeight(TreeNode root) {if (root null) return 0;int leftHeight getHeight(root.left);int rightHeight getHeight(root.right);if (leftHeight 0 rightHeight 0 Math.abs(leftHeight - rightHeight) 1) {return Math.max(leftHeight, rightHeight) 1;} else {// 说明不是平衡二叉树那高度返回负数即可return -1;}}
} 55. LCR 193. 二叉搜索树的最近公共祖先 这道题得分情况讨论第一种情况是 p root 或者 q root则此时最近公共祖先就是 root
第二种情况是如果 p 和 q 都在 root 的左边或者 p 和 q 都在 root 的右边如例子2就看谁在前头就是谁。
第三种情况就是 p 和 q 分别在 root 的两边那此时这种情况最近公共祖先就是 root如例子1。
代码实现
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {// 分三种情况第一种是 p 或者 q 中有一个是 root// 一种是 p 和 q 都在 root 的左边或者右边// 另一种是 p 和 q 分别在 root 的两边if (root p || root q) return root;if (root null || p null || q null) return null;TreeNode left lowestCommonAncestor(root.left, p, q);TreeNode right lowestCommonAncestor(root.right, p, q);if (left ! null right ! null) {return root;} else if (left null) {return right;} else {return left;}}
} 56. LCR 194. 二叉树的最近公共祖先 这道题和上面那道题是解法一模一样还有另一种做法。
如图 代码实现
class Solution {public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root null) return null;StackTreeNode s1 new Stack();StackTreeNode s2 new Stack();getPath(root, p, s1);getPath(root, q, s2);int len s1.size() - s2.size();if (len 0) {len s2.size() - s1.size();while (len ! 0) {s2.pop();len--;}} else {while (len ! 0) {s1.pop();len--;}}while (!s1.empty() !s2.empty()) {TreeNode top1 s1.pop();TreeNode top2 s2.pop();if (top1 top2) return top1;}return null;}public boolean getPath(TreeNode root, TreeNode target, StackTreeNode stack) {if (root null) return false;stack.push(root);if (root target) return true;boolean left getPath(root.left, target, stack);if (left) return true;boolean right getPath(root.right, target, stack);if (right) return true;// 到这里说明左子树和右子树都没找到 target// 说明不是路径上的节点, 删除节点返回 falsestack.pop();return false;}
} 位运算
57. LCR 133. 位 1 的个数 这个简单直接利用 n (n - 1) 消除 n 中二进制 1 的个数并且用计数器记录下来即可。
代码实现
public class Solution {// you need to treat n as an unsigned valuepublic int hammingWeight(int n) {int count 0;while (n ! 0) {n (n - 1);count;}return count;}
} 58. LCR 134. Pow(x, n) 可以用快速幂来做就是 x^n (x*x)^(n/2)n 为偶数或者 x*(x*x)^(n/2)
那就可以利用这个来做题。
代码实现
class Solution {public double myPow(double x, int n) {if (x 0.0) return 0.0;// 用快速幂// 2^9 (2)* 4^4 (2)* 16^2 (2)* 256^1 (2*256)* (256*256)^0 512// 用来记录多出来的 x也就是当 n 为奇数时res * xdouble res 1.0;boolean flg false;// n 可能会很大将 n 赋给 tmp 防止越界(-2147483648)long tmp n;if (tmp 0) {tmp -tmp;flg true;}while (tmp ! 0) {if (tmp % 2 1) {res * x;}x x * x;tmp / 2;}if (flg) {return 1.0 / res;}return res;}
} 59. LCR 177. 撞色搭配 这个可以用分组异或的方式来做先将数组所有元素异或一遍 得到 retret 中的二进制为 1 的那一位说明就是两个只出现一次的数字的区分点然后根据这个区分点来分组异或最后返回异或得到的结果即可。
代码实现
class Solution {public int[] sockCollocation(int[] sockets) {int tmp 0;for (int i 0; i sockets.length; i) {tmp ^ sockets[i];}// 分组异或int index 0;while (tmp ! 0) {if (tmp % 2 1) {break;}tmp 1;index;}int num1 0;int num2 0;for (int i 0; i sockets.length; i) {if (((sockets[i] index) 1) 1) {num1 ^ sockets[i];} else {num2 ^ sockets[i];}}return new int[]{num1, num2};}
} 60. LCR 178. 训练计划 VI 这道题可以用哈希表来做不会超时遍历数组记录每个数字出现的次数然后再次遍历数组如果当前数字出现了一次就返回该数字。
代码实现
class Solution {public int trainingPlan(int[] actions) {MapInteger, Integer hash new HashMap();for (int i 0; i actions.length; i) {int value hash.getOrDefault(actions[i], 0);hash.put(actions[i], value 1);}for (int i 0; i actions.length; i) {int value hash.getOrDefault(actions[i], 0);if (value 1) {return actions[i];}}return -1;}
} 61. LCR 190. 加密运算 这个就是让你求两个数的和但是不能使用加减乘除那就可以使用位运算来做a ^ b 就是 a 和 b 不进位相加的和那我们可以定义一个变量来记录 a 和 b 的进位然后就一直进行异或直到进位为 0. 3 和 5 011 3 101 5 001 a b 这就是进位需要往前进位, 001 -- 010所以两数之和 不进位和 进位和 所以进位的计算公式为 (a b) 1 010 (a b) 1 110 a ^ b 100 上面两个异或之后得到不进位和再求进位 100 (a b) 1 进位 0000 上面两个异或之后得到不进位和再求进位 1000 (a b) 1 进位 1000 异或和 0000 进位当进位为 0上面两数之和计算完毕 代码实现
class Solution {public int encryptionCalculate(int dataA, int dataB) {if (dataA 0) return dataB;if (dataB 0) return dataA;// 两个数不进位相加的结果 a ^ bwhile (dataB ! 0) {int carry (dataA dataB) 1; // 计算进位dataA dataA ^ dataB;// 计算两数不进位相加和dataB carry;}return dataA;}
} 动态规划
62. LCR 126. 斐波那契数 这个很简单公式给你了按照公式求解就行。
代码实现
class Solution {public int fib(int n) {if (n 0 || n 1) return n;int a 0;int b 1;int c 0; while (n 2) {c (a b) % 1000000007;a b;b c;n--;}return c;}
} 63. LCR 127. 跳跃训练 这个很简单就是青蛙跳台阶问题跟斐波那契问题的解法一模一样。
代码实现
class Solution {public int trainWays(int num) {if (num 2) return 1;int[] dp new int[num 1];dp[0] 1;dp[1] 1;for (int i 2; i num; i) {dp[i] (dp[i - 1] dp[i - 2]) % 1000000007;}return dp[num];}
} 64. LCR 137. 模糊搜索验证 这道题用动态规划来做大体分两种情况当 input 的第 j-1 个字符是 * 以及不是 * 的情况。
首先是明确 dp[i][j]根据题目可知表示以 article 的第 i 个字符结尾的串与以 input 的第 j 个字符结尾的串是否匹配。然后推导状态转移方程 dp[i][j] ?
当 input[j - 1] ! * 时如果 article[i-1] input[j-1] 或者有个字符是点号则 dp[i][j] dp[i - 1][j - 1] (看以 article 的第 i 个字符结尾的串与以 input 的第 j 个字符结尾的串的状态)
当 input[j - 1] 等于 * 时dp[i][j] dp[i][j-2] (因为 input[j-1] 是 *, 所以关注 intput[j - 2] 结尾的串即可)如果 article[i-1] input[j-2] 或者其中一个字符是* 或者点号则 dp[i][j] dp[i][j] || dp[i - 1][j]。初始化就是当两字符串都是空串时dp[0][0] true。
代码实现
class Solution {public boolean articleMatch(String a, String b) {// 用动态规划来做dp[i][j] 代表在 a 中以 i 个字符结尾的字符串与在 b 中第 j 个字符结尾的字符串是否匹配int len1 a.length();int len2 b.length();boolean[][] dp new boolean[len1 1][len2 1];// 初始化dp[0][0] true;char[] arr1 a.toCharArray();char[] arr2 b.toCharArray();for (int i 0; i len1; i) {for (int j 1; j len2; j) {if (arr2[j - 1] *) {dp[i][j] dp[i][j - 2];if (i 0) {if (charMatch(arr1[i - 1], arr2[j - 2])) {dp[i][j] dp[i][j] || dp[i - 1][j];}}} else {if (i 0 charMatch(arr1[i - 1], arr2[j - 1])) {dp[i][j] dp[i - 1][j - 1];}}}}return dp[len1][len2];}public boolean charMatch(char a, char b) {if (a * || b * || a . || b .) return true;return a b;}
} 65. LCR 161. 连续天数的最高销售额 这道题可以用动态规划来做求连续数组最大和dp[i] 就是以 i 下标结尾天数的最大和。
dp[i] Math.max(sales[i], dp[i - 1] sales[i])因为 sales[i] 可能是负数。
初始化dp[0] sales[0]最后遍历 dp 找最大值并返回即可。
代码实现
class Solution {public int maxSales(int[] sales) {// dp[i] 表示以 i 下标结尾的天数的最大和int[] dp new int[sales.length];dp[0] sales[0];for (int i 1; i dp.length; i) {dp[i] Math.max(dp[i - 1] sales[i], sales[i]);}int max Integer.MIN_VALUE;for (int i 0; i dp.length; i) {if (dp[i] max) {max dp[i];}}return max;}
} 66. LCR 165. 解密数字 这道题也可以用动态规划来做dp[i] 代表以第 i 个数字结尾的字符串有多少种解密方案。 一个数字就代表一个字母但是这个数字范围是 0-25。
所以根据数字这个解密方式 dp[i] dp[i - 1]。当 str[i - 1] 和 str[i] 能够组合数字时(num 10 num 25)则 dp[i] dp[i - 1] dp[i - 2] 。
初始化dp[0] dp[1] 1。那这里跟斐波那契问题有点像就可以定义三个变量 a,b,c 来替代 dp 数组。
代码实现
class Solution {public int crackNumber(int ciphertext) {String str String.valueOf(ciphertext);// int[] dp new int[str.length() 1];// dp[i] 表示以第 i 个字符结尾的解密方案数量int a 1, b 1, c 1;int len str.length();int i 2;while (i len) {c b;// 如果 str[i - 2] 存在, 则可以组合 str[i - 2]str[i - 1]String tmp str.substring(i - 2, i);if (tmp.compareTo(10) 0 tmp.compareTo(25) 0) {c a;}a b;b c;i;}return c;}
} 67. LCR 166. 珠宝的最高价值 可以用动态规划来做先定义 dp[i][j] 为从 frame[0][0] 到 frame[i][j] 的珠宝最大值然后再来推断dp[i][j] ?到达 dp[i][j] 有两种可能第一种是从上面来到第二种是从左边来的。
所以 dp[i][j] Math.max(dp[i - 1][j], dp[i][j - 1]) frame[i][j] 。但还要考虑边界情况比如在左上角和在右上角的情况此时就只有一个方向。最后就是初始化 dp[0][0] frame[0][0]
代码实现
class Solution {public int jewelleryValue(int[][] frame) {int row frame.length;int col frame[0].length;int[][] dp new int[row][col];dp[0][0] frame[0][0];// dp[i][j] 代表到 ij 的最大珠宝值// 1 3 1// 1 5 1// 4 2 1for (int i 0; i row; i) {for (int j 0; j col; j) {dp[i][j] frame[i][j];if (i - 1 0) {dp[i][j] dp[i - 1][j] frame[i][j];}if (j - 1 0) {dp[i][j] Math.max(dp[i][j], dp[i][j - 1] frame[i][j]);}}}return dp[row - 1][col - 1];}
} 68. LCR 185. 统计结果概率 这道题可以去看看大佬的题解。
代码实现
class Solution {public double[] statisticsProbability(int num) {// prev 表示 n - 1 个骰子点数double[] prev {1 / 6d, 1 / 6d, 1 / 6d, 1 / 6d, 1 / 6d, 1 / 6d};for (int i 2; i num; i) {// 第 n 个骰子点数double[] cur new double[5 * i 1];// [n, 6n] - 5*n 1for (int j 0; j prev.length; j) {// 每个骰子有 6 点// 第 n 个骰子点数 第 n-1 个骰子点数 当前骰子点数for (int k 0; k 6; k) {cur[j k] prev[j] * 1 / 6;}}prev cur;}return prev;}
} 69. LCR 187. 破冰游戏 约瑟夫环问题dp[i] (dp[i -1] target) % num.
代码实现
class Solution {public int iceBreakingGame(int num, int target) {// 用动态规划// dp[i] (dp[i - 1] target) % num// dp[i] 表示以 i 个成员为约瑟夫环最后剩下的成员编号int dp 0;for (int i 2; i num; i) {dp (dp target) % i;}return dp;}
} 图
70. LCR 129. 字母迷宫 这种找路径的问题一般用深搜来做因为图中的每个节点都可能是单词开头所以需要遍历图然后对图中的每个节点进行深搜即可。
代码实现
class Solution {public boolean wordPuzzle(char[][] grid, String target) {int row grid.length;int col grid[0].length;char[] arr target.toCharArray();// 遍历图for (int i 0; i row; i) {for (int j 0; j col; j) {boolean[][] flg new boolean[row][col];// 对每个节点进行深搜if (dfs(grid, flg, i, j, row, col, arr, 0)) {return true;}}}return false;}public boolean dfs(char[][] arr, boolean[][] flg, int i, int j, int row, int col, char[] target, int k) {// 越界或者已经访问过或者对应的字符不一致则返回 falseif (i 0 || i row || j 0 || j col || flg[i][j] || arr[i][j] ! target[k]) {return false;}// 标记遍历过flg[i][j] true;if (k target.length - 1) {return true;}// 往四个方向继续boolean ans dfs(arr, flg, i - 1, j, row, col, target, k 1)|| dfs(arr, flg, i 1, j, row, col, target, k 1)|| dfs(arr, flg, i, j - 1, row, col, target, k 1)|| dfs(arr, flg, i, j 1, row, col, target, k 1);// 回溯flg[i][j] false;return ans;}
} 71. LCR 130. 衣橱整理
可以用深搜来做。
代码实现
class Solution {public int wardrobeFinishing(int m, int n, int cnt) {boolean[][] flg new boolean[m][n];return dfs(m, n, 0, 0, flg, cnt);}public int dfs(int m, int n, int i, int j, boolean[][] flg, int cnt) {// 判断越界以及是否遍历过以及是否符合整理要求if (i 0 || i m || j 0 || j n || flg[i][j] || (numSum(i) numSum(j) cnt)) {return 0;}// 标记一下flg[i][j] true;return dfs(m, n, i, j 1, flg, cnt) dfs(m, n, i 1, j, flg, cnt) 1;}public int numSum(int num) {int sum 0;while (num ! 0) {sum num % 10;num / 10;}return sum;}
} 72. LCR 146. 螺旋遍历二维数组 代码实现
class Solution {public int[] spiralArray(int[][] array) {if (array.length 0)return new int[0];int x1 0, y1 0;int x2 array.length - 1, y2 array[0].length - 1;int k 0;int[] ret new int[(x2 1) * (y2 1)];while (x1 x2 y1 y2) {// 第一行for (int i y1; i y2; i) {ret[k] array[x1][i];}// 最后一列for (int i x1 1; i x2; i) {ret[k] array[i][y2];}// 最后一行if (x1 x2) {for (int i y2 - 1; i y1; i--) {ret[k] array[x2][i];}}// 第一列if (y1 y2) {for (int i x2 - 1; i x1; i--) {ret[k] array[i][y1];}}x1;y1;x2--;y2--;}return ret;}
} 贪心算法
73. LCR 188. 买卖芯片的最佳时机 让你求最大值第一眼就是两层遍历搞定。
但是还有另一种方法要想获得利润最大值一般是低买高卖低价买入高价卖出所以我们可以定义一个变量 minPrice 记录股票的最小值再定义一个 max 来记录最大利润只要当前股票 - minPrice 比 max 大max 就更新。最后返回 max 即可。
代码实现
class Solution {public int bestTiming(int[] prices) {int max 0;for (int i 0; i prices.length - 1; i) {for (int j i 1; j prices.length; j) {int tmp prices[j] - prices[i];if (tmp max) {max tmp;}}}return max;}
}class Solution {public int bestTiming(int[] prices) {int max 0;// 记录最低股票值int minPrice Integer.MAX_VALUE;// 低买高卖for (int i 0; i prices.length; i) {if (prices[i] minPrice) {minPrice prices[i];}if (prices[i] - minPrice max) {max prices[i] - minPrice;}}return max;}
} 找规律
74. LCR 162. 数字 1 的个数 可以去看看大佬的题解。
代码实现
class Solution {public int digitOneInNumber(int num) {int digit 1, count 0;int high num / 10, cur num % 10, low 0;while (high ! 0 || cur ! 0) {// 当 cur 和高位都是 0则说明已经遍历完该数字了if (cur 0) {// 当前位是 0count high * digit;} else if (cur 1) {// 当前位是 1count high * digit low 1;} else {count (high 1) * digit;}// 1 2 3 4// high cur lowlow cur * digit;cur high % 10;// 为 high 的最后一位high / 10;digit * 10;}return count;}
} 75. LCR 163. 找到第 k 位数字 可以去看看大佬题解。
代码实现
class Solution {public int findKthNumber(int k) {// 几位数int digit 1;// 从哪里开始long start 1;// digit 位数一共有几个long count 9;// 获取第 k 位数 是几位数while (k count) {k - count;digit;start * 10;count 9 * start * digit;}// 确定 k 所在的数字// start (k - 1) / digit 用来计算从 start 开始跳过多少个完整的数字long num start (k - 1) / digit;return Long.toString(num).charAt((k - 1) % digit) - 0;}
}
