LeetCode刷题总结 - 面试经典 150 题 -持续更新-程序员宅基地
技术标签： 面试 算法 leetcode 算法+数据结构+设计模式
LeetCode刷题总结 - 面试经典 150 题 - 持续更新
其他系列
这篇文章原本和【LeetCode刷题总结 - 剑指offer系列 - 持续更新】是一篇文章，但由于篇幅过大没法更新，所以就拆成了两篇。
若题中分析出现“上面有总结过…”等字样，且发现本篇文章没有总结，则可以到【LeetCode刷题总结 - 剑指offer系列 - 持续更新】中去寻找
【LeetCode刷题总结 - 剑指offer系列 - 持续更新】
【LeetCode刷题总结 - LeetCode 热题 100 - 持续更新】
数组 / 字符串
88. 合并两个有序数组
分析：
类似于归并排序的merge部分，可以看一下这篇文章【归并排序】
代码：
class Solution {
public void merge(int[] nums1, int m, int[] nums2, int n) {
// 辅助数组，复制nums1的前m个数据
int[] copyFromNums1 = new int[m];
for(int i=0; i<m; i++) {
copyFromNums1[i] = nums1[i];
}
// 指针指向 copyFromNums1
int i=0;
// 指针指向 num2
int j=0;
// 指针指向 nums1
int index = 0;
// 比较 copyFromNums1 和 nums2，更小的放到nums1中
while(i < m && j < n) {
if(copyFromNums1[i] <= nums2[j]) {
nums1[index++] = copyFromNums1[i++];
} else {
nums1[index++] = nums2[j++];
}
}
// 执行到这里，要么 i==m 要么 j==n
// 将剩余的放进nums1（可能已经空了）
while(i < m) {
nums1[index++] = copyFromNums1[i++];
}
// 将剩余的放进nums1（可能已经空了）
while(j < n) {
nums1[index++] = nums2[j++];
}
}
}
27. 移除元素
分析：
- 新增一个指针
left，[0,left)之间的元素就是!=val的 - 遍历数组，判断每个元素是否等于
val，!= val则添加到nums[left]，left++
参考动画：https://leetcode.cn/problems/remove-element/solution/xue-sheng-wu-de-nu-peng-you-du-neng-kan-nk7yy/
代码：
class Solution {
public int removeElement(int[] nums, int val) {
int left = 0;
// 遍历数组，判断每个元素
for(int right=0; right<nums.length; right++) {
if(nums[right] != val) {
nums[left] = nums[right];
left++;
}
}
return left;
}
}
283. 移动零
分析：
跟上题类似，只不过目标值变成了0
代码：
class Solution {
public void moveZeroes(int[] nums) {
int len = nums.length;
int left = 0;
for(int i=0; i<len; i++) {
if(nums[i] != 0) {
nums[left++] = nums[i];
}
}
for(int i=left; i<len; i++) {
nums[i] = 0;
}
}
}
26. 删除有序数组中的重复项
分析：
跟上上一题思路一样，不同点在于比较的对象变成了“最后不重复的元素”
代码：
class Solution {
public int removeDuplicates(int[] nums) {
if(nums.length == 1) {
return 1;
}
/**
* left、right
* left：指向最后不重复的元素
* right：指向当前遍历的元素
*/
int left = 0;
for(int right=1; right<nums.length; right++) {
if(nums[right] != nums[left]) {
nums[left+1] = nums[right];
left++;
}
}
return left+1;
}
}
80. 删除有序数组中的重复项 II
分析：
跟上一题思路一样，不同点在于比较的对象变成了“新数组中的倒数第k个元素”（此题中 k=2）
其实该题就是上一题的升华版，将上一题总结的更通用，上一题可理解为 k=1
代码：
class Solution {
public int removeDuplicates(int[] nums) {
if(nums.length == 1 || nums.length == 2) {
return nums.length;
}
return removeK(nums, 2);
}
public int removeK(int[] nums, int k) {
int left = k - 1;
for(int right=k; right<nums.length; right++) {
if(nums[right] != nums[left-k+1]) {
nums[left+1] = nums[right];
left++;
}
}
return left+1;
}
}
169. 多数元素
分析：
某个值在该数组中的个数超过一半，该值即叫做多数元素，这样的元素在这个数组中肯定只有一个
摩尔投票算法 可以使空间复杂度O(1)，时间复杂度为O(n).
B站上上视频讲解：https://www.bilibili.com/video/BV1Ey4y1n7hb
代码：
public class Solution {
/* 摩尔投票 */
public int MoreThanHalfNum_Solution(int [] arr) {
// 票数
int rating = 0;
// m假设是个数超过一半的那个数
int m = arr[0];
for(int i=0; i<arr.length; i++) {
// 当票数为0时， 将当前数当做m，并且票数设为1
if(rating == 0){
m = arr[i];
rating = 1;
} else {
if(arr[i] == m) // 若与m相同 票数就++
rating++;
else // 不同则--
rating--;
}
}
return m;
}
}
189. 轮转数组
分析：
- 步骤一：整体翻转，
[1,2,3,4,5,6,7]->[7,6,5,4,3,2,1] - 步骤二：数组截断，分成两段，若k=3，则
[7,6,5,4,3,2,1]->[7,6,5]、[4,3,2,1] - 步骤三：分别对两段数组进行翻转，
[7,6,5]、[4,3,2,1]->[5,6,7]、[1,2,3,4] - 步骤四：拼接两段，
[5,6,7]、[1,2,3,4]->[5,6,7,1,2,3,4]
代码：
class Solution {
/**
* 因为我们实际上并没有，分割数组（所有操作都是在原数组上），因此【步骤二】 和 【步骤四】是可以省略的
*/
public void rotate(int[] nums, int k) {
// 注意，该题的k有可能大于数组的长度，因此我们要提前取余
k = k % nums.length;
// 步骤一：整体翻转，[1,2,3,4,5,6,7] -> [7,6,5,4,3,2,1]
reverse(nums, 0, nums.length-1);
// 步骤二：数组截断，分成两段，若k=3，则[7,6,5,4,3,2,1] -> [7,6,5]、[4,3,2,1]
// 步骤三：分别对两段数组进行翻转，[7,6,5]、[4,3,2,1] -> [5,6,7]、[1,2,3,4]
reverse(nums, 0, k-1);
reverse(nums, k, nums.length-1);
// 步骤四：拼接两段，[5,6,7]、[1,2,3,4] -> [5,6,7,1,2,3,4]
}
/**
* 翻转数组中元素 [a,b,c,d] -> [d,c,b,a]
*/
public void reverse(int[] nums, int left, int right) {
while(left < right) {
swap(nums, left, right);
left++;
right--;
}
}
/**
* 交换数组中 index1 和index2 的位置
*/
public void swap(int[] nums, int index1, int index2) {
int temp = nums[index1];
nums[index1] = nums[index2];
nums[index2] = temp;
}
}
121. 买卖股票的最佳时机
分析：
- 需要两个全局变量，
minLowVal：表示历史最低点；maxProfit：历史最大的模拟收益 - 遍历每天的股票，更新
minLowVal，模拟 若当前价格大于历史最低点则卖掉股票，同时更新maxProfit
代码：
class Solution {
public int maxProfit(int[] prices) {
// 历史最低点
int minLowVal = Integer.MAX_VALUE;
// 历史最大的模拟收益
int maxProfit = 0;
for(int i=0; i<prices.length; i++) {
int curPrice = prices[i];
// 更新minLowVal
minLowVal = Math.min(minLowVal, curPrice);
// 若当天价格 高于 前面最低的价格，则模拟卖出股票
if(curPrice > minLowVal) {
int profit = curPrice - minLowVal;
// 更新maxProfit
maxProfit = Math.max(maxProfit, profit);
}
}
return maxProfit;
}
}
122. 买卖股票的最佳时机 II
分析：
这题比上题还简单，(#^.^#)
不同点：
- 上题只能买卖一次，因此需要找到
前面的最低点和后面的最高点 - 这题可以无限买卖，只要
当天价格>昨天价格，我们就可以卖股票（就有收益）,然后收益累加
代码：
class Solution {
public int maxProfit(int[] prices) {
// 若只有一天的，则收益为0
if(prices.length == 1) {
return 0;
}
// 收益是累加的，初始值为0
int maxProfit = 0;
// 从第2天开始遍历
for(int i=1; i<prices.length; i++) {
// 若 当天价格 > 前一天价格，则模拟卖出股票，并且收益累加
if(prices[i] > prices[i-1]) {
int newProfit = prices[i] - prices[i-1];
maxProfit += newProfit;
}
}
return maxProfit;
}
}
55. 跳跃游戏
分析：
参考视频：【LeetCode_55_跳跃游戏】
代码：
class Solution {
public boolean canJump(int[] nums) {
/**
* maxLen：表示历史情况下能够达到的最远下标的位置
* 当到达0时，maxLen指 【0所能到达最远位置】
* 当到达1时，maxLen指 【0所能到达最远位置】 和 【1所能到达最远位置】 的最大值
* 当到达i时，maxLen指 【0所能到达最远位置】 和 【1所能到达最远位置】 ... 【i所能到达最远位置】 的最大值
*/
int maxLen = 0;
for(int i=0; i<nums.length; i++) {
// 如果 maxLen 小于 i，则说明无论怎么跳都不能到达i的，直接返回false
if(i > maxLen) {
return false;
}
// 更新maxLen
maxLen = Math.max(maxLen, i + nums[i]);
}
return true;
}
}
274. H 指数
分析：
- 先排序
- 引用值从大到小进行遍历
- 满足条件就
count++，直到不满足为止
代码：
class Solution {
public int hIndex(int[] citations) {
// 先对数组进行排序，默认是递增
Arrays.sort(citations);
// 记录满足条件的文章数，初始值为0
int count = 0;
// 以 引用值从高到低 进行遍历
for(int i = citations.length-1; i>=0; i--) {
// 在比较的时候，要把当前文章也加上，因此这里是count+1
if(citations[i] >= count+1) {
count++;
} else {
break;
}
}
return count;
}
}
380. O(1) 时间插入、删除和获取随机元素
分析：
- 获取随机值，并且时间复杂度为
O(1)，我们很容易想到使用数组来存储数据 - 而
insert和remove的时间复杂度也为O(1)，我们又可以使用map，key存储对应的值，value存储该元素在数组中的下标
复杂的是remove函数，细细咀嚼吧
代码：
class RandomizedSet {
// 用于存储添加的val
List<Integer> list = new ArrayList();
// key：具体插入的值 value：表示该值在list中的下标
Map<Integer, Integer> map = new HashMap();
// 随机数生成器对象
Random random = new Random();
public RandomizedSet() {
}
public boolean insert(int val) {
if(map.containsKey(val)) {
return false;
}
list.add(val);
map.put(val, list.size()-1);
return true;
}
public boolean remove(int val) {
if(!map.containsKey(val)) {
return false;
}
// 1、获取待删除值的下标
int idx = map.get(val);
// 2、取list中最后一个值：last
int last = list.get(list.size()-1);
// 3、用last覆盖，要删除的值的位置
list.set(idx, last);
map.put(last, idx);
// 4、删除最后一个位置，以及对应值
map.remove(val);
list.remove(list.size()-1);
return true;
}
public int getRandom() {
return list.get(random.nextInt(list.size()));
}
}
238. 除自身以外数组的乘积
分析：
解题思路：
B站上视频连接：https://www.bilibili.com/video/BV1xV411f773
- 利用类似于动态规划的思想，构建
[0,i]的乘积数组，即i及i之前的所有数的乘积 - 利用类似于动态规划的思想，构建
[i,n-1]的乘积数组，即i及i之后的所有数的乘积 - 最终根据题意
res[i] = cj1[i-1] * cj2[i+1]，求最终结果集
代码：
public class Solution {
public int[] multiply(int[] A) {
int n = A.length;
// 用于存放 i及i之前的所有乘积（包含i：[0,i]）
int[] cj1 = new int[n];
// 用于存放 i及i之后的所有乘积（包含i：[i,n-1]）
int[] cj2 = new int[n];
// 用于存放那结果集
int[] res = new int[n];
// 类似于动态规划的求法，求cj1。[0,i]
for(int i=0; i<n; i++) {
// 若i为0，则区A[0] 边界条件
if(i == 0)
cj1[i] = A[0];
else // 动态规划
cj1[i] = cj1[i-1] * A[i];
}
// 类似于动态规划的求法，求cj2。[i,n-1]。 同上
for(int i=n-1; i>=0; i--) {
if(i == n-1)
cj2[i] = A[n-1];
else
cj2[i] = cj2[i+1] * A[i];
}
// 最后根据题意，求结果集
for(int i=0; i<n; i++) {
if(i == 0)
res[i] = cj2[i+1];
else if(i == n-1)
res[i] = cj1[i-1];
else
res[i] = cj1[i-1] * cj2[i+1];
}
return res;
}
}
739. 每日温度
分析：
单调栈 维护 还未找到后面更高温度的日期
参考视频：【单调栈，你该了解的，这里都讲了！LeetCode:739.每日温度】
代码：
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
// 单调递增栈，存放还未找到最近最高温度的日期，存放的是下标
Stack<Integer> stack = new Stack();
// 存放待返回的结果
int[] ret = new int[temperatures.length];
stack.push(0);
// 遍历温度表
for(int i=1; i<temperatures.length; i++) {
int cur = temperatures[i];
// 若栈顶温度 小于 当天温度，则说明当天温度 相对于 栈顶元素来说，就是最近的更高温度
while(!stack.isEmpty() && temperatures[stack.peek()] < cur) {
// 已经为栈顶元素找到了 最近的最高温度，则没必要放到栈中了
int popedIdx = stack.pop();
// 记录天数差
ret[popedIdx] = i - popedIdx;
}
stack.push(i);
}
// 最后stack不为空，则说明stack中的元素 后面找不到更高温度的日期
while(!stack.isEmpty()) {
int popedIdx = stack.pop();
ret[popedIdx] = 0;
}
return ret;
}
}
42. 接雨水
分析：
参考视频：【单调栈，经典来袭！LeetCode:42.接雨水】
建议先做上一题
- 找到
较低点的前一个较大值和后一个较大值，则可以算较低点相对于前、后两个较大点所接的雨水（横向求解，水平求解） - 维护一个
单调栈（存储下标），若当前值大于栈顶元素，则栈顶元素就是较低点，栈顶第二个元素就是较低点的前一个较大点，当前值就是较低点的下一个较大点
代码：
class Solution {
public int trap(int[] height) {
// stack维护一个单调栈（非递减），存储下标
Stack<Integer> stack = new Stack();
// 记录接雨水的总数
int sum = 0;
for(int i=0; i<height.length; i++) {
int cur = height[i];
// 若栈顶元素 小于 当前值则弹出（表示当前值是栈顶元素的后续第一个较大者）
while(!stack.isEmpty() && height[stack.peek()] < cur) {
// nextHeight：下个较大值(下标)
int nextHeight = i;
// mid：就是中间点(下标)
int mid = stack.pop();
if(stack.isEmpty()) {
// 若为空 则直接跳过，不处理
break;
}
// preHeight:前一个较大值(下标)
int preHeight = stack.peek();
// 高度差
int diffY = Math.min(height[preHeight], height[nextHeight]) - height[mid];
// 宽度差
int diffX = nextHeight - preHeight - 1;
// 面积累计
sum += diffX * diffY;
}
stack.push(i);
}
return sum;
}
}
链表
141. 环形链表（基础模板题）
分析：
可以参考我之前总结的这篇文章，很详细【判断单链表是否有环？以及入环节点】
代码：
public class Solution {
public boolean hasCycle(ListNode head) {
if(head == null) return false;
if(head.next == null) return false;
ListNode slow = head.next;
ListNode fast = head.next.next;
while(slow != fast) {
if(fast == null || fast.next == null) {
return false;
}
slow = slow.next;
fast = fast.next.next;
}
return true;
}
}
142. 环形链表 II
分析：
可以参考我之前总结的这篇文章，很详细【判断单链表是否有环？以及入环节点】
代码：
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head == null) return null;
if(head.next == null) return null;
ListNode slow = head.next;
ListNode fast = head.next.next;
while (slow != fast) {
if(fast == null || fast.next == null) {
return null;
}
slow = slow.next;
fast = fast.next.next;
}
slow = head;
while(slow != fast) {
slow = slow.next;
fast = fast.next;
}
return fast;
}
}
202. 快乐数
分析：
参考官方题解：【快乐数】
每个数字都会根据平方和指向另一个数字，所以从任意数字开始进行 各位平方和 的迭代操作，就相当于在链表上游走。
我们猜测最终会有如下三种情况：
- 最终会得到1
- 最终会进入循环
- 值会越来越大，最后接近无穷大（不可能）
其实第3中情况是不可能的，接下来分析一下为什么？
我们想象一下1位数、2位数、3位数…n位数，他们的最大值的next（即各位平方和）是多少：
- 对于 3 位数的数字，它不可能大于 243。这意味着它要么被困在 243 以下的循环内，要么跌到 1。
- 4 位或 4 位以上的数字在每一步都会丢失一位，直到降到 3 位为止。
- 所以我们知道，最坏的情况下，算法可能会在 243 以下的所有数字上循环，然后回到它已经到过的一个循环或者回到 1。但它不会无限期地进行下去，所以我们排除第三种选择。
所以只会出现两种情况，两种情况最终都会成环：
- 以1成环（因为1的各位平方和 = 1，即1.next = 1）
- 不以1成环
步骤：
1、 使用快慢指针来判断成环
2、判断若是以1成环则返回为true，否则false
代码：
class Solution {
public boolean isHappy(int n) {
int slow = getHappy(n);
int fast = getHappy(getHappy(n));
while(fast != slow) {
// 每次走1步
slow = getHappy(slow);
// 每次走两步
fast = getHappy(getHappy(fast));
}
// 若是以1成环，则是快乐数
if(fast == 1) {
return true;
}
return false;
}
/**
* 算出各位平方和
*/
public int getHappy(int n) {
int sum = 0;
while(n > 0) {
int m = n % 10;
sum += m * m;
n /= 10;
}
return sum;
}
}
2. 两数相加
分析：
说白了就是模拟数字的加法运算
注意：
勿忘判断 最后一个进位是否为1，若为1就补上
代码：
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head1 = l1; // 移动指针1，指向链表1
ListNode head2 = l2; // 移动指针2，指向链表2
// 构建结果链表
ListNode resHead = new ListNode();
ListNode temp = resHead;// 移动指针3，指向链表3
// 进位值， 默认是0 （作用域一定要是外面）
int carry = 0;
while(null != head1 || null != head2) {
// 为空取0， 否则取val（核心思想）
int num1 = null==head1 ? 0 : head1.val;
int num2 = null==head2 ? 0 : head2.val;
int sum = num1 + num2 + carry;
// 求模取余 获取当前节点值
int curVal = sum % 10;
// 整除获取进位值
carry = sum / 10;
// 构建当前节点
ListNode curNode = new ListNode(curVal);
// 尾插法
temp.next = curNode; temp = curNode;
// 节点后移，只需要考虑不为null的链表即可，因为为null的话我们默认取0, 不会有影响
if(null != head1)
head1 = head1.next;
if(null != head2)
head2 = head2.next;
}
// 最后节点遍历完后，判断最后一步运算是否进位了，进位则补1，否则不处理
if(carry == 1) {
ListNode lastNode = new ListNode(1);
temp.next = lastNode;
}
return resHead.next;
}
}
21. 合并两个有序链表（模板题）
分析：
- 双指针分别指向 list1 和 list2
- 比较list1 和 list2 的指针指向的节点大小，更小者最拼接到新链表末尾，并且指针后移
- 若某一个链表已经遍历完，那么直接将另一个未遍历完的链表连接到新链表的尾部
直接看代码，代码更清晰
代码：
class Solution {
public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
// 新链表的虚拟头结点
ListNode head = new ListNode(0);
ListNode cur = head;
// 从list1 和 list2 中取更小者拼接到新链表尾部
while(list1 != null && list2 != null) {
if(list1.val <= list2.val) {
cur.next = list1;
list1 = list1.next;
} else {
cur.next = list2;
list2 = list2.next;
}
cur = cur.next;
}
// 能走到这里，只有有两种情况：1、list1合并完了、list2没合并完 2、list1没合并完、list2合并完了
// 合并list1剩余的元素
if(list1 != null) {
cur.next = list1;
}
// 合并list2剩余的元素
if(list2 != null) {
cur.next = list2;
}
return head.next;
}
}
138. 复制带随机指针的链表
分析：
- 第一次遍历原链表：简单复制新的节点（此时新老节点 仅仅是val相同），遍历的过程中将新、老节点的映射关系存储在
map中 - 第二次遍历原链表：复制链表中 next 、 random的指向关系（依赖map中的映射关系）
代码：
class Solution {
public Node copyRandomList(Node head) {
if(head == null) {
return null;
}
Map<Node, Node> map = new HashMap();
Node cur = head;
// 1、 第一次遍历原链表： 创建对应的新节点 并且对应关系存入到map集合中
while(cur != null) {
// 1.1 创建新节点
Node newNode = new Node(cur.val);
// 2.2 并将 以oldNode为key，newNode为value的方式存入到map中 oldNode:newNode
map.put(cur, newNode);
cur = cur.next;
}
// 2、第一次遍历原链表：进行深拷贝
cur = head;
while(cur != null) {
// 2.1 复制对应next节点
map.get(cur).next = map.get(cur.next);
// 2.2 复制对应random节点
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
return map.get(head);
}
}
92. 反转链表 II
分析：
- 方法一：链表先切为三段，然后翻转第二段，然后重新拼接。
- 方法二：双指针头插法。这里看到了一个很优秀的题解，分享一下：【ava-双指针-头插法】
代码：
解法一：
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
ListNode dummyNode = new ListNode(-1);
dummyNode.next = head;
ListNode prev = dummyNode;
for(int i=0; i<left-1; i++) {
prev = prev.next;
}
ListNode end = head;
for(int i=0; i<right-1; i++) {
end = end.next;
}
// 第一段 与 第二段 断开
ListNode oldBegin = prev.next;
prev.next = null;
// 第二段 与 第三段 断开
ListNode thirdBegin = end.next;
end.next = null;
// 反转第二段
ListNode newBegine = reverse(oldBegin);
// 重新拼接三段
prev.next = newBegine;
oldBegin.next = thirdBegin;
return dummyNode.next;
}
// 链表反转
public ListNode reverse(ListNode head) {
ListNode prev = null;
ListNode cur = head;
while(cur != null) {
ListNode nextNode = cur.next;
cur.next = prev;
prev = cur;
cur = nextNode;
}
return prev;
}
}
解法二：
class Solution {
public ListNode reverseBetween(ListNode head, int left, int right) {
// 虚拟头结点
ListNode dummyHead = new ListNode();
dummyHead.next = head;
ListNode guard = dummyHead;
ListNode cur = head;
// 将cur移动到left位置
for(int i=0; i<left-1; i++) {
cur = cur.next;
guard = guard.next;
}
// 将cur的下一元素 以头插法的方式插入到guard后面，循环right-left次
for(int i=0; i<right-left; i++) {
// 1、先拿到cur的下一个元素
ListNode removed = cur.next;
// 2、删除下个元素
cur.next = cur.next.next;
///3、头插法插到guard后面
removed.next = guard.next;
guard.next = removed;
}
return dummyHead.next;
}
}
25. K 个一组翻转链表
分析：
参考讲解视频：【【LeetCode 25. K 个一组翻转链表】 每天一题刷起来！C++ 年薪冲冲冲！】
- 先将前 k 个节点组成的链表进行翻转
- 递归处理剩余的链表
代码：
class Solution {
public ListNode reverseKGroup(ListNode head, int k) {
// 特殊情况一：【链表为null 或者 k==1, 没必要反转】
if(head == null || k == 1) {
return head;
}
// end 指向当前节点
ListNode end = head;
// 下面这一段代码主要用来判断， 链表长度是否小于k
for(int i=1; i<k && end != null; i++) {
end = end.next;
}
if(end == null) {
// 若end为null说明 剩下节点不足k个了，不需要翻转
return head;
}
// 走到此处 [head,end] 其实就是当前需要翻转的k个节点
// 排除完特殊情况 下面就是正常情况了。 此时cur已经指向第k个节点了
// 先保存下一节点（k+1）地址 ， 因为接下来要断开 cur与k+1 节点的连接
ListNode nextListHead = end.next;
// 断开k节点 与 k+1节点的连接 因为接下来要单独反转当前组单链表了
end.next = null;
// 反转当前组 单项链表
ListNode newHead = reverse(head); // 翻转之后，之前的head其实就跑到尾部了
// 递归处理剩余剩下的链表，并拼接在之前的head后面（此时的head指针指向的是尾部）
head.next = reverseKGroup(nextListHead, k);
// 返回反转后的新头节点
return newHead;
}
/**
* 翻转单链表
*/
private ListNode reverse(ListNode head) {
ListNode cur = head;
ListNode prev = null;
while(cur != null) {
ListNode nextNode = cur.next;
cur.next = prev;
prev = cur;
cur = nextNode;
}
return prev;
}
}
19. 删除链表的倒数第 N 个结点
分析：
- 算出链表的长度 -
size - 根据
n和size算出待删除节点的前一个节点位置 - 找到待删除节点的前一个节点
- 调用
cur.next = cur.next.next删除目标节点
为了避免处理边界节点，我们可以在头结点前面加一个虚拟头结点dummyHead
代码：
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
int size = 0;
ListNode cur = head;
// 算出链表的长度
while(cur != null) {
size++;
cur = cur.next;
}
// 计算待删除节点 的 前一个位置
int index = size - n;
// 虚拟头结点（避免处理特殊的边界情况）
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
cur = dummyHead;
// 指针指向待删除节点的前一个节点
for(int i=0; i<index; i++) {
cur = cur.next;
}
// 删除目标节点
cur.next = cur.next.next;
return dummyHead.next;
}
}
82. 删除排序链表中的重复元素 II
分析：
- 涉及到要删除节点，所以我们需要有个
prev（前节点） - 为避免处理边界情况，我们加一个
dummyHead（虚拟头结点）
遍历链表，会存在两种情况：
- 情况一：如果当前节点与下个节点的值相同
- while循环，cur一直后移 ，直到当前值与下个值不相同
- cur后移
- pre.next指向cur，相当于删除中间重复的节点
- 情况二：正常情况
- 前后指针 pre-cur指针后移
代码：
class Solution {
public ListNode deleteDuplicates(ListNode head) {
if(head == null) {
return null;
}
ListNode dummyHead = new ListNode(-101);
dummyHead.next = head;
ListNode prev = dummyHead;
ListNode cur = head;
while(cur != null) {
// 1. 情况一：如果当前节点与下个节点的值相同
if(cur.next != null && cur.val == cur.next.val) {
// cur一直后移 ，直到当前值与下个值不相同
while(cur.next != null && cur.val == cur.next.val) {
cur = cur.next;
}
// cur后移
cur = cur.next;
// pre.next指向cur，相当于删除中间重复的节点
prev.next = cur;
} else {
// 2. 情况二：正常情况
// 前后指针 pre-cur指针后移
cur = cur.next;
prev = prev.next;
}
}
return dummyHead.next;
}
}
61. 旋转链表
分析：
-
首先遍历整个链表，求出链表的长度
count，并找出链表的尾节点tail -
由于
k可能很大，所以我们令k = k % n，然后再次从头节点head开始遍历，找到第n - k个节点p，那么1 ~ p是链表的前n - k个节点，p+1 ~ n是链表的后k个节点 -
接下来就是依次执行（顺序别搞错了）
tail.next = head：尾部与头部相连，连成一个环newHead = p.next：获取新的head节点（这一步一定要在上一步之后，否则p.next可能为null）p.next = null：截断环
-
最后返回
newHead
代码：
class Solution {
public ListNode rotateRight(ListNode head, int k) {
if(head == null || k == 0) {
return head;
}
ListNode cur = head;
ListNode tail = null;
// 算出链表的长度
int count = 0;
while(cur != null) {
count++;
tail = cur;
cur = cur.next;
}
// 算出截断位置
k %= count;
int index = count - k;
ListNode p = head;
for(int i=1; i<index; i++) {
p = p.next;
}
// 先连成环，避免后面 newHead = p.next时，newHead为null
tail.next = head;
// 记录下一个节点（未来新的head）
ListNode newHead = p.next;
// 截断
p.next = null;
// 返回新head
return newHead;
}
}
86. 分隔链表
分析：
- 创建两个新链表，
小链表、大链表 - 遍历原链表，若
val < x，将节点追加到小链表；若val >= x，则将节点追加到大链表 - 最后
小链表的尾部连接大链表的头部
分析：
class Solution {
public ListNode partition(ListNode head, int x) {
if(head == null) {
return head;
}
// 小链表的虚拟头
ListNode smallDummyHead = new ListNode(-1);
ListNode p1 = smallDummyHead;
// 大链表的虚拟头
ListNode bigDummyHead = new ListNode(-1);
ListNode p2 = bigDummyHead;
// 遍历原链表
while(head != null) {
if(head.val < x) {
// 比x小则追加到小链表
p1.next = head;
p1 = p1.next;
} else {
// 都在追加到大链表（包括相等的情况）
p2.next = head;
p2 = p2.next;
}
head = head.next;
}
// 小链表的尾部 连接 大链表的头部
p1.next = bigDummyHead.next;
// 这里一定要断开，否则可能会成环
p2.next = null;
return smallDummyHead.next;
}
}
双指针
125. 验证回文串
分析：
- 双指针：左右指针同步往内移动，若字符（排除掉特殊字符）不同则为
false Character.isLetterOrDigit()：判断是否是数字或者字母字符Character.toLowerCase()：字母转成小写
代码：
class Solution {
public boolean isPalindrome(String s) {
s = s.trim();
if(s.length() == 0) {
return true;
}
int left = 0;
int right = s.length() - 1;
while(left < right) {
// 左侧：left指针，跳过非数字或者字母的字符
while(left < right && !Character.isLetterOrDigit(s.charAt(left))) {
left++;
}
// 右侧：right指针，跳过非数字或者字母的字符
while(left < right && !Character.isLetterOrDigit(s.charAt(right))) {
right--;
}
// 字符都归一化成小写
char leftChar = Character.toLowerCase(s.charAt(left));
char rightChar = Character.toLowerCase(s.charAt(right));
// 若不同 返回false
if(leftChar != rightChar) {
return false;
}
// 同步向内移动
left++;
right--;
}
return true;
}
}
392. 判断子序列
分析：
- 双指针，
p1指向字符串s，p2指向字符串t - 字符遍历，一直遍历，直到
s结束 或者t结束 p2指针每次后后移一步，p1指针只有 两个字符相同时 才会后移
代码：
class Solution {
public boolean isSubsequence(String s, String t) {
if(s.length() == 0) {
return true;
}
if(t.length() == 0) {
return false;
}
int p1 = 0;
int p2 = 0;
// 一直遍历，直到s结束 或者 t结束
while(p1 < s.length() && p2 < t.length()) {
if(s.charAt(p1) == t.charAt(p2)) {
// 若相同，则s的指针-p1也会后移
p1++;
}
// t的指针-p2总会后移一步
p2++;
}
// p1 == s.length() 时，表明s已经遍历完了
return p1 == s.length();
}
}
167. 两数之和 II - 输入有序数组
分析：
B站上视频讲解：https://www.bilibili.com/video/BV1J741157eS
- 左右双指针。左指针-
l初始为0位置，右指针-r初始为length-1。 while(l<r)循环。 若和大于sum则右指针左移；若和小于sum则左指针右移。
代码：
class Solution {
public int[] twoSum(int[] numbers, int target) {
int left = 0;
int right = numbers.length - 1;
while(left < right) {
int sum = numbers[left] + numbers[right];
if(sum == target) {
int[] res = new int[2];
res[0] = left+1;
res[1] = right+1;
return res;
}
if(sum < target) {
left++;
} else {
right--;
}
}
return new int[]{
-1, -1};
}
}
11. 盛最多水的容器
分析：
结论：左右指针，谁的高度越低，谁就往中间移动
- 若向内移动短板，水槽的短板
min(h[i], h[j])可能变大，因此下个水槽面积可能增大 - 若向内移动长板，水槽的短板
min(h[i], h[j])不变或变小，因此下个水槽面积一定变小
流程：
- 初始化：双指针
left，right分列水槽的两端 - 循环收窄：直到双指针相遇则跳出
- 更新面积最大值
max - 选定两板高度中的短板，向中间收窄一格
- 更新面积最大值
- 返回值：返回面积最大值即可
代码：
class Solution {
public int maxArea(int[] height) {
int max = Integer.MIN_VALUE;
int left = 0;
int right = height.length-1;
while(left < right) {
int area = (right - left) * Math.min(height[left], height[right]);
max = Math.max(max, area);
// 谁低谁往中间移动
if(height[left] < height[right]) {
left++;
} else {
right--;
}
}
return max;
}
}
15. 三数之和（已总结）
分析：
- 先排序
- 通过枚举
i确定第一个数，另外两个指针left，right分别从左边i + 1和右边length - 1往中间移动，找到满足nums[left] + nums[right] == -nums[i]的所有组合 - 去重：因为是有序序列，因此我们可以用如下方式去重（重点，看代码细细品味）
代码：
class Solution {
public List<List<Integer>> threeSum(int[] nums) {
List<List<Integer>> res = new ArrayList();
// 先排序
Arrays.sort(nums);
int n = nums.length;
// 遍历每个元素，当做三元组的首个元素
for(int i=0; i<n; i++) {
// 对第一个元素去重
if(i != 0 && nums[i] == nums[i-1]) {
continue;
}
int target = -nums[i];
int left = i+1;
int right = n-1;
while(left < right) {
int sum = nums[left] + nums[right];
if(sum < target) {
left++;
} else if (sum > target) {
right--;
} else {
if(sum == target) {
res.add(Arrays.asList(nums[i], nums[left], nums[right]));
// 因为我们要找到所有 三元组，因此需要继续找
// 找下一个跟 当前tempL不同的值作为新的left（因为数组是有序的，因此这样可以保证去重）
int tempL = nums[left++];
while(left < right && nums[left] == tempL) {
left++;
}
// 找下一个跟 当前tempR不同的值作为新的right（同理）
int tempR = nums[right--];
while(left < right && nums[right] == tempR) {
right--;
}
}
}
}
}
return res;
}
}
区间
228. 汇总区间
分析：
- 双指针
low、high，[low, high]用于维护递增1的有序序列 high每次累加1low每次更新到high
代码：
class Solution {
public List<String> summaryRanges(int[] nums) {
List<String> res = new ArrayList();
if(nums.length == 0) {
return new ArrayList();
}
int len = nums.length;
int low = 0;
// [low, high] 用于维护递增1的有序序列
while(low < len) {
int high = low + 1;
// 若 nums[high-1] + 1 == nums[high] 则high后移，直到不满足条件为止
while(high < len && nums[high-1] + 1 == nums[high]) {
high++;
}
// 此时 nums[high-1] + 1 != nums[high], 则[low, high-1] 就是递增1的有序序列
String s = "";
if(nums[low] == nums[high-1]) {
s = String.valueOf(nums[low]);
} else {
s = nums[low] + "->" + nums[high-1];
}
res.add(s);
// low重置，指向high位置
low = high;
}
return res;
}
}
252. 会议室
分析：
参考文章：【秒懂力扣区间题目：重叠区间、合并区间、插入区间】
因为一个人在同一时刻只能参加一个会议，因此题目实质是判断是否存在重叠区间?，这个简单，将区间按照会议开始时间进行排序，然后遍历一遍判断即可。
代码：
class Solution {
public boolean canAttendMeetings(int[][] intervals) {
// 将区间按照会议开始实现升序排序
Arrays.sort(intervals, (v1, v2) -> v1[0] - v2[0]);
// 遍历会议，如果下一个会议在前一个会议结束之前就开始了，返回 false。
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] < intervals[i - 1][1]) {
return false;
}
}
return true;
}
}
56. 合并区间
分析：
参考文章：【秒懂力扣区间题目：重叠区间、合并区间、插入区间】
- 遍历
intervals - 若
interval与res的最后一个元素区间重合，则合并最后一个区间 - 否则 则直接加入到
res中
代码：
class Solution {
public int[][] merge(int[][] intervals) {
List<int[]> res = new ArrayList();
// 升序排列
Arrays.sort(intervals, (v1,v2) -> v1[0] - v2[0]);
// 遍历intervals，更新res
for(int[] interval: intervals) {
if(!res.isEmpty() && interval[0] <= res.get(res.size()-1)[1]) {
// 重叠了，则更新res的最后一个元素
// 拿到 res的最后一个元素
int[] last = res.get(res.size()-1);
// 更新last[1]
last[1] = Math.max(last[1], interval[1]);
} else {
// 不重叠则直接更新
res.add(interval);
}
}
int[][] res1 = new int[res.size()][2];
for(int i=0; i<res.size(); i++) {
for(int j=0; j<2; j++) {
res1[i][j] = res.get(i)[j];
}
}
return res1;
}
}
57. 插入区间
分析：
用指针去扫 intervals，最多可能有三个阶段：
- 不重叠的前半部分
- 重叠的部分
- 不重叠的后半部分
参考解题思路：【「手画图解」57. 插入区间 | 分成 3 个阶段考察】
代码：
class Solution {
public int[][] insert(int[][] intervals, int[] newInterval) {
List<int[]> res = new ArrayList();
int i=0;
int len = intervals.length;
// 处理第一部分：不重叠的前半部区间
while(i < len && intervals[i][1] < newInterval[0]) {
res.add(intervals[i]);
i++;
}
// 处理第二部分：重叠的区间
while(i < len && intervals[i][0] <= newInterval[1]) {
// 左边界，则取最小值
newInterval[0] = Math.min(intervals[i][0], newInterval[0]);
// 右边界，则取最大值
newInterval[1] = Math.max(intervals[i][1], newInterval[1]);
i++;
}
res.add(newInterval);
// 处理第三部分：不重叠的后半部区间
while(i < len) {
res.add(intervals[i]);
i++;
}
int[][] res1 = new int[res.size()][2];
for(i=0; i<res.size(); i++) {
for(int j=0; j<2; j++) {
res1[i][j] = res.get(i)[j];
}
}
return res1;
}
}
二叉树
104. 二叉树的最大深度
分析：
计算公式：以root为根树的高度 = max(root左子树的高度, root右子树的高度) + 1
很明显想算出以root为根树的高度，就要先算出子树的高度，因此我们很容想到的就是后序遍历
后序遍历特点：先算出左、右子节点结果，再通过回溯的特点往上推，实际上就是自底向上的计算方式
代码：
class Solution {
public int maxDepth(TreeNode root) {
return depth(root);
}
public int depth(TreeNode root) {
if(root == null) {
return 0;
}
// 左子树高度
int leftDepth = depth(root.left);
// 右子树高度
int rightDepth = depth(root.right);
// 代入公式算出 以root为根的树的高度
int depth = Math.max(leftDepth, rightDepth) + 1;
return depth;
}
}
100. 相同的树
分析：
- 深度优先，后序遍历
- 先判断边界条件
p == null && q == null：都为null，则说明遍历到叶子节点了p == null || q == null：到这里，其实p、q一个为null、另一个不为null，因此一定不相同p.val != q.val：值不相同，一定不相同
- 判断左、右子树结果
- 汇总
代码：
class Solution {
public boolean isSameTree(TreeNode p, TreeNode q) {
return isSame(p, q);
}
public boolean isSame(TreeNode p, TreeNode q) {
// 都为null，则说明遍历到叶子节点了
if(p == null && q == null) {
return true;
}
// 到这里，其实 p、q一个为null、另一个不为null，因此一定不相同
if(p == null || q == null) {
return false;
}
// 值不相同，一定不相同
if(p.val != q.val) {
return false;
}
boolean leftIsSame = isSame(p.left, q.left);
boolean rightIsSame = isSame(p.right, q.right);
// 只有左右子树都为相同，才相同
return leftIsSame && rightIsSame;
}
}
101. 对称二叉树
分析：
大体框架与上题一样：
- 这里是把根节点的左右子树当做两棵树
- 然后比较这两棵树是否对称
比较两棵树是否相同的主要代码：
boolean leftIsSame = isSame(root1.left, root2.left);
boolean rightIsSame = isSame(root1.right, root2.right);
比较两棵树是否对称的主要代码：
// 判断对称的外侧，即 左树的左孩子 与 右树的右孩子
boolean outFlag = symmetric(root1.left, root2.right);
// 判断对称的内侧，即 左树的右孩子 与 右树的左孩子
boolean inFlag = symmetric(root1.right, root2.left);
代码：
class Solution {
public boolean isSymmetric(TreeNode root) {
return symmetric(root.left, root.right);
}
public boolean symmetric(TreeNode root1, TreeNode root2) {
if(root1 == null && root2 == null) {
return true;
}
if(root1 == null || root2 == null) {
return false;
}
if(root1.val != root2.val) {
return false;
}
// 判断对称的外侧，即 左树的左孩子 与 右树的右孩子
boolean outFlag = symmetric(root1.left, root2.right);
// 判断对称的内侧，即 左树的右孩子 与 右树的左孩子
boolean inFlag = symmetric(root1.right, root2.left);
return outFlag && inFlag;
}
}
根相同的两棵树root1，root2，判断root2是否是root1的子树？
该题前提：
- root1.val == root2.val
- 是否为子树？我们可理解为 “root1（大树）是否包含root2（小树）？”
分析：
大体框架和【100. 相同的树】类似，只是处理边界逻辑发生改变
// 如果匹配的树为null 则说明匹配到叶子节点了 已经匹配完了
if(subtree == null) {
return true;
}
// 如果root为null 则说明大树匹配到叶子节点了 还没匹配完子树
if(root == null) {
return false;
}
代码：
/**
* 判断subTree是否为root的子树？
*/
public boolean judge(TreeNode root, TreeNode subtree ) {
// 如果匹配的树为null 则说明匹配到叶子节点了 已经匹配完了
if(subtree == null) {
return true;
}
// 如果root为null 则说明大树匹配到叶子节点了 还没匹配完子树
if(root == null) {
return false;
}
// 节点值不同，则直接返回false
if(root.val != subtree.val) {
return false;
}
boolean leftJudge = judge(root.left, subtree.left);
boolean rightJudge = judge(root.right, subtree.right);
return leftJudge && rightJudge;
}
剑指 Offer 26. 树的子结构
分析：
解题步骤：
- 遍历大树
- 若以任意节点为根的树 包含 目标子树，则返回true
注意点：在遍历大树时，别调错递归方法了，调的是isSubStructure，而不是judge
代码：
class Solution {
public boolean isSubStructure(TreeNode root1,TreeNode root2) {
if(root1==null || root2==null) return false;
// 若以当前节点为根的树 包含目标子树，则直接返回true
if(judge(root1, root2)) {
return true;
}
// 下面调isSubStructure是起遍历的作用，别调错成judge了
boolean leftFlag = isSubStructure(root1.left, root2);
boolean rightFlag = isSubStructure(root1.right, root2);
// 存在左右子树任意匹配即可
return leftFlag || rightFlag;
}
/**
* 判断subTree是否为root的子树？
*/
public boolean judge(TreeNode root, TreeNode subtree ) {
// 如果匹配的树为null 则说明匹配到叶子节点了 已经匹配完了
if(subtree == null) {
return true;
}
// 如果root为null 则说明大树匹配到叶子节点了 还没匹配完子树
if(root == null) {
return false;
}
// 节点值不同，则直接返回false
if(root.val != subtree.val) {
return false;
}
boolean leftJudge = judge(root.left, subtree.left);
boolean rightJudge = judge(root.right, subtree.right);
return leftJudge && rightJudge;
}
}
226. 翻转二叉树
分析：
- 遍历大树，并且交换左、右孩子
代码：
class Solution {
public TreeNode invertTree(TreeNode root) {
dfs(root);
return root;
}
/**
* 遍历大树，且交换左、右孩子
*/
public void dfs(TreeNode root) {
if(root == null) {
return;
}
swap(root);
dfs(root.left);
dfs(root.right);
}
/**
* 交换root 的 左子树 和 右子树
*/
public void swap(TreeNode root) {
if(root == null) {
return;
}
TreeNode temp = root.left;
root.left = root.right;
root.right = temp;
}
}
105. 从前序与中序遍历序列构造二叉树
分析：
上面【分治算法-系列】的【剑指 Offer 07. 重建二叉树】
代码：
class Solution {
int[] preorder;
int[] inorder;
// 存储中序遍历 对应值的下标
private HashMap<Integer, Integer> inorderMap = new HashMap();
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
this.inorder = inorder;
for(int i=0; i<inorder.length; i++) {
inorderMap.put(inorder[i], i);
}
return build(0, preorder.length-1, 0, inorder.length-1);
}
public TreeNode build(int left1, int right1, int left2, int right2) {
if(left1>right1 || left2>right2) {
return null;
}
int rootVal = preorder[left1];
TreeNode root = new TreeNode(rootVal);
int idx = inorderMap.get(rootVal);
int leftTreeSize = idx - left2; // 左子树大小
int rightTreeSize = right2 - idx; // 右子树大小
// 构建左孩子
root.left = build(left1+1, left1+leftTreeSize, left2, left2+leftTreeSize-1);
// 构建右孩子
root.right = build(left1+leftTreeSize+1, right1, idx+1, right2);
return root;
}
}
106. 从中序与后序遍历序列构造二叉树
分析：
和上题类思路一致
代码：
class Solution {
int[] postorder;
int[] inorder;
// 存储中序遍历 对应值的下标
private HashMap<Integer, Integer> inorderMap = new HashMap();
public TreeNode buildTree(int[] inorder, int[] postorder) {
this.postorder = postorder;
this.inorder = inorder;
for(int i=0; i<inorder.length; i++) {
inorderMap.put(inorder[i], i);
}
return build(0, postorder.length-1, 0, inorder.length-1);
}
public TreeNode build(int left1, int right1, int left2, int right2) {
if(left1>right1 || left2>right2) {
return null;
}
int rootVal = postorder[right1];
TreeNode root = new TreeNode(rootVal);
int idx = inorderMap.get(rootVal);
int leftTreeSize = idx - left2; // 左子树大小
int rightTreeSize = right2 - idx; // 右子树大小
// 构建左孩子
root.left = build(left1, left1+leftTreeSize-1, left2, left2+leftTreeSize-1);
// 构建右孩子
root.right = build(left1+leftTreeSize, right1-1, idx+1, right2);
return root;
}
}
117. 填充每个节点的下一个右侧节点指针 II
分析：
使用宽度优先遍历
代码：
class Solution {
public Node connect(Node root) {
if(root == null) {
return null;
}
Queue<Node> queue = new LinkedList();
queue.offer(root);
while(!queue.isEmpty()) {
int len = queue.size();
for(int i=0; i<len; i++) {
Node node = queue.poll();
if(node.left != null) {
queue.offer(node.left);
}
if(node.right != null) {
queue.offer(node.right);
}
// next指向下一个节点，但是要判断queue不为空
if(!queue.isEmpty()) {
node.next = queue.peek();
}
// 最后一个要指向null
if(i == len-1) {
node.next = null;
}
}
}
return root;
}
}
114. 二叉树展开为链表
分析：
该方法不是时间复杂度最低的
- 前序遍历将节点放入到
list - 遍历
list，更新左、右子节点的指向关系
代码：
class Solution {
List<TreeNode> list = new ArrayList();
public void flatten(TreeNode root) {
preorderDfs(root);
for(int i=0; i<list.size(); i++) {
TreeNode cur = list.get(i);
cur.left = null;
if(i == list.size()-1) {
cur.right = null;
} else {
cur.right = list.get(i+1);
}
}
}
// 前序遍历
public void preorderDfs(TreeNode root) {
if(root == null) {
return;
}
list.add(root);
preorderDfs(root.left);
preorderDfs(root.right);
}
}
112. 路径总和
分析：
前面已经总结过了【JZ82 二叉树中和为某一值的路径(一)】
代码：
class Solution {
public boolean hasPathSum(TreeNode root, int targetSum) {
if(root == null) {
return false;
}
return dfs(root, targetSum);
}
public boolean dfs(TreeNode root, int target) {
if(root == null) {
return false;
}
target -= root.val;
// 叶子节点：root.left == null && root.right == null
if(root.left == null && root.right == null && target == 0) {
return true;
}
return dfs(root.left, target) || dfs(root.right, target);
}
}
129. 求根节点到叶节点数字之和
分析：
该题上面已总结过：【剑指 Offer II 049. 从根节点到叶节点的路径数字之和】
代码：
class Solution {
int sum = 0;
int pro = 0;
public int sumNumbers(TreeNode root) {
dfs(root);
return sum;
}
public void dfs(TreeNode root) {
if(root == null) {
return;
}
int curVal = root.val;
pro = pro * 10 + curVal;
if(root.left == null && root.right == null) {
sum += pro;
}
dfs(root.left);
dfs(root.right);
pro /= 10;
}
}
222. 完全二叉树的节点个数
分析：
参考视频：【leetcode-树篇 222题 完全二叉树的节点个数】
求完全二叉树深度：
/**
* 完全二叉树深度
*/
public int getDepth(TreeNode root) {
int level = 0;
while(root != null) {
level++;
root = root.left;
}
return level;
}
代码：
其中 1 << leftDepth : 【当前节点数：1】 + 【左子树节点个数】 = 1 + 2^n -1 = 2^n
class Solution {
public int countNodes(TreeNode root) {
if(root == null) {
return 0;
}
// 求左子树的高度
int leftDepth = getDepth(root.left);
// 求右子树的高度
int rightDepth = getDepth(root.right);
if(leftDepth == rightDepth) {
// 此时左子树肯定是完全二叉树
// 1（根节点） + n^2-1（左完全二叉树节点数）+ 右子树节点数量
return (1 << leftDepth) + countNodes(root.right);
} else {
// 此时右子树肯定是完全二叉树
// 1（根节点） + n^2-1（右完全二叉树节点数）+ 右子树节点数量
return (1 << rightDepth) + countNodes(root.left);
}
}
/**
* 完全二叉树深度
*/
public int getDepth(TreeNode root) {
int level = 0;
while(root != null) {
level++;
root = root.left;
}
return level;
}
}
236. 二叉树的最近公共祖先
分析：
上面已经总结过该题：【剑指 Offer 68 - II. 二叉树的最近公共祖先】
代码：
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) {
return null;
}
return dfs(root, p, q);
}
// 【后续遍历】的特点：可以把最终返回的节点 通过递归一直往上推
public TreeNode dfs(TreeNode root, TreeNode p, TreeNode q) {
// 当前节点为null，则肯定找不到，直接返回null
if(root == null) {
return null;
}
// 找到了p 或者 q，则向上返回
if(root == p || root == q) {
return root;
}
// 【左】
TreeNode left = dfs(root.left, p, q);
// 【右】
TreeNode right = dfs(root.right, p, q);
// 【中】
if(left != null && right != null) {
// 若左、右子树都找到了，则当前节点就是最近公共节点
return root;
} else if (left != null && right == null) {
// 左树找到了，但右树没找到，则返回left结果
return left;
} else if(right != null && left == null) {
// 右树找到了，但左树没找到，则返回right结果
return right;
} else {
// 都没找到，则向上返回null
return null;
}
}
}
二叉树层次遍历
199. 二叉树的右视图
分析：
上面已经总结过了
代码：
class Solution {
public List<Integer> rightSideView(TreeNode root) {
if(root == null) {
return new ArrayList();
}
Queue<TreeNode> queue = new LinkedList();
queue.offer(root);
List<Integer> res = new ArrayList();
while(!queue.isEmpty()) {
int length = queue.size();
for(int i=0; i<length; i++) {
TreeNode node = queue.poll();
if(node.left != null) {
queue.offer(node.left);
}
if(node.right != null) {
queue.offer(node.right);
}
if(i == length-1) {
res.add(node.val);
}
}
}
return res;
}
}
637. 二叉树的层平均值
分析：
- 分层遍历（广度优先）
- 每层计算平均值
代码：
class Solution {
public List<Double> averageOfLevels(TreeNode root) {
List<Double> res = new ArrayList();
if(root == null) {
return new ArrayList();
}
Queue<TreeNode> queue = new LinkedList();
queue.offer(root);
while(!queue.isEmpty()) {
int len = queue.size();
double sum = 0;
for(int i=0; i<len; i++) {
TreeNode node = queue.poll();
if(node.left != null) {
queue.offer(node.left);
}
if(node.right != null) {
queue.offer(node.right);
}
sum += node.val;
}
res.add(sum/len);
}
return res;
}
}
102. 二叉树的层序遍历
分析：
一样的模板套路
代码：
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
if(root == null) {
return new ArrayList();
}
List<List<Integer>> res = new ArrayList();
Queue<TreeNode> queue = new LinkedList();
queue.offer(root);
while(!queue.isEmpty()) {
int len = queue.size();
List<Integer> list = new ArrayList();
for(int i=0; i<len; i++) {
TreeNode node = queue.poll();
list.add(node.val);
if(node.left != null) {
queue.offer(node.left);
}
if(node.right != null) {
queue.offer(node.right);
}
}
res.add(list);
}
return res;
}
}
103. 二叉树的锯齿形层序遍历
分析：
- 和上面一样的套路，不同点是插入list的方式。该题 尾插 和 头插 每一行交替操作
list的头插法：list.add(0, node.val)
代码：
class Solution {
public List<List<Integer>> zigzagLevelOrder(TreeNode root) {
if(root == null) {
return new ArrayList();
}
List<List<Integer>> res = new ArrayList();
Queue<TreeNode> queue = new LinkedList();
queue.offer(root);
boolean flag = true;
while(!queue.isEmpty()) {
int len = queue.size();
List<Integer> list = new ArrayList();
for(int i=0; i<len; i++) {
TreeNode node = queue.poll();
if(flag) {
list.add(node.val);
} else {
list.add(0, node.val);
}
if(node.left != null) {
queue.offer(node.left);
}
if(node.right != null) {
queue.offer(node.right);
}
}
res.add(list);
flag = !flag;
}
return res;
}
}
数学
9. 回文数
分析：
- 数字转成字符串
- 判断字符串是否是回文串
- 双指针法
代码：
class Solution {
public boolean isPalindrome(int x) {
String s = String.valueOf(x);
if(s.length() == 0 || s.length() == 1) {
return true;
}
char[] chars = s.toCharArray();
int left = 0;
int right = chars.length - 1;
while(left <= right) {
if(chars[left] != chars[right]) {
return false;
}
left++;
right--;
}
return true;
}
}
66. 加一
分析：
- 从尾到头遍历，模拟
+1 - 遍历
carry来记录上一轮是否进位，因为该题需要+1，因此carry默认值为true - 直到
+1后当前元素 < 10，这可直接返回当前数组 - 若远数组为
[9,9,9,9,9]这种情况，则最终会是[0,0,0,0,0]，需要新创建一个数组，新增一位，第一位设置1即可，最终是[1,0,0,0,0,0]
代码：
class Solution {
public int[] plusOne(int[] digits) {
// carry标记上一轮计算是否进位？因为该题需要我们+1，所以这里默认值我们设为true
boolean carry = true;
for(int i=digits.length-1; i>=0; i--) {
int curVal = digits[i];
if(carry) {
curVal++;
}
if(curVal < 10) {
// 不存在进位，则直接返回结果
digits[i] = curVal;
return digits;
} else {
// 因为是加一，所有进位之后肯定是10，因此当前位为0
carry = true;
digits[i] = 0;
}
}
if(digits[0] == 0) {
// 这种情况肯定是 原数组都是9，例如：99999，加一后100000，但数组中只存储00000
int[] newDigits = new int[digits.length+1];
newDigits[0] = 1; // 此时newDigits -> 100000
return newDigits;
}
return digits;
}
}
172. 阶乘后的零
分析：
参考视频：【【LeetCode 每日一题】172. 阶乘后的零 | 手写图解版思路 + 代码讲解】
该题其实就是求 [1-n]个数，一共存在多少“因子5”？
- 每
5^1出现1个5，每5^2出现2个5，每5^3出现3个5，以此类推 - 则
count = n/5 + n/5^2 + n/5^3 + ....
代码：
class Solution {
public int trailingZeroes(int n) {
int count = 0;
while(n > 0) {
count += n/5;
n /= 5;
}
return count;
}
}
其中n /= 5：分子除以5，等价于分母乘以5
69. x 的平方根
分析：
首先 x^0.5 <= x （肯定的）
所以该题可以看做 从[0,1,2,3...x] 中，找到 n*n <= x 的最大值
[0,1,2,3...x]是个有序序列，因此我们可以使用二分法求解
在判断mid*mid 是否是 小于 x 的最大值时，我们可以这样写：
if(mid < x/mid) {
// 等价于 mid*mid < x
// 【关键判断】：若 mid+1 > x/(mid+1)，则mid*mid 肯定是小于 x 的最大值
if(mid+1 > x/(mid+1)) {
// 等价于 (mid+1)*(mid+1) > x
return mid;
}
left = mid + 1;
}
注意点：
x的范围 0 <= x <= 2^31 - 1
错误写法：n*n <= x (肯定会超出int或者long的范围)
正确写法：n <= x/n (分子、分母同时除以n，n*n <= x 等价于 n <= x/n)
代码：
class Solution {
public int mySqrt(int x) {
if(x == 0) {
return 0;
}
if(x == 1) {
return 1;
}
return binarySearch(x);
}
/**
* 目标： n*n <= x 的 最大值
*/
public int binarySearch(int x) {
// 可以看做从[0,1,2,3...x] 这些元素中查找目标元素
int left = 0;
int right = x;
while(left <= right) {
int mid = (left + right) / 2;
if(mid == x/mid) {
// 等价于 mid*mid == x
return mid;
}
if(mid < x/mid) {
// 等价于 mid*mid < x
// 【关键判断】：若 mid+1 > x/(mid+1)，则mid*mid 肯定是小于 x 的最大值
if(mid+1 > x/(mid+1)) {
// 等价于 (mid+1)*(mid+1) > x
return mid;
}
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
}
50. Pow(x, n)
分析：
上面已经总结过了 【剑指 Offer 16. 数值的整数次方】
错误写法：(这种会超时)
if(n % 2 == 0) {
return myPow(x, n/2) * myPow(x, n/2);
} else {
return myPow(x, n-1) * x;
}
正确写法：（不会超时，但和上面写法是一个思路）
if(n % 2 == 0) {
return myPow(x * x, n/2);
} else {
return myPow(x, n-1) * x;
}
代码：
class Solution {
public double myPow(double x, int n) {
if(n == 0) {
return 1;
}
if(n == 1) {
return x;
}
if(n == -1) {
return 1 / x;
}
if(n % 2 == 0) {
return myPow(x * x, n/2);
} else {
return myPow(x, n-1) * x;
}
}
}
二分查找
模板
参考视频：【最清楚的二分查找！LeetCode34题：在排序数组中查找元素的第一个和最后一】
参考文章：【二分查找算法及其变种详解】
正常搜索目标值：
public int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right) {
int mid = left + ((right - left) >> 1);
if(nums[mid] == target) {
return mid;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return result;
}
变种一：搜索值为target的第一个下标：
/**
* 找第一个目标值
*/
public int binarySearchFirst(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right) {
int mid = left + ((right - left) >> 1);
if(nums[mid] == target) {
// 下面两种情况，都说明是最左侧的target
if (mid == 0 || nums[mid - 1] != target)
return mid;
// 否则继续向左半区间查找
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
变种二：搜索值为target的最后一个下标：
/**
* 找最后一个目标值
*/
public int binarySearchLast(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right) {
int mid = left + ((right - left) >> 1);
if(nums[mid] == target) {
// 下面两种情况，都说明是最右侧的target
if (mid == nums.length-1 || nums[mid + 1] != target)
return mid;
// 否则继续向右半区间查找
left = mid + 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
变种三：查找第一个大于等于 给定值的元素
/**
* 第一个 >=target 的下标
*/
public int binarySearch3(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right) {
int mid = left + ((right - left) >> 1);
if(nums[mid] >= target) {
if(mid == 0 || nums[mid - 1] < target)
return mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
变种四：查找最后一个小于等于给定值的元素
/**
* 最后一个 <=target 的下标
*/
public int binarySearch4(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right) {
int mid = left + ((right - left) >> 1);
if(nums[mid] <= target) {
if(mid == nums.length-1 || nums[mid + 1] > target)
return mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
变种五：查找第一个大于 给定值的元素
/**
* 第一个 >target 的下标
*/
public int binarySearch5(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right) {
int mid = left + ((right - left) >> 1);
if(nums[mid] > target) {
if(mid == 0 || nums[mid - 1] <= target)
return mid;
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
变种六：查找最后一个小于给定值的元素
/**
* 最后一个 <target 的下标
*/
public int binarySearch6(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right) {
int mid = left + ((right - left) >> 1);
if(nums[mid] < target) {
if(mid == nums.length-1 || nums[mid + 1] >= target)
return mid;
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
总结注意点
【注意点一】：若[left,right] 对应 [0,length-1]，当代码中需要mid与相邻元素比较时，要和nums[mid+1]比较，如果和num[mid-1]比较，则nums[mid-1]可能会下标越界
- 若数组只有一个元素，其实
nums[mid+1]也会越界。因此只有一个元素时要单独当做边界条件处理 - 若数组只有两个元素，则
mid = (0+1)/2 = 0，那么nums[mid-1]就会越界，nums[mid+1]则不会越界
35. 搜索插入位置
分析：
该题是个模板题
/**
* 二分查找
*/
public int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right) {
int mid = (left + right) >> 1; // 等价于 (left + right) / 2
if(nums[mid] == target) {
return mid;
}
if(nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
代码：
class Solution {
public int searchInsert(int[] nums, int target) {
return binarySearch(nums, target);
}
/**
* 二分查找
*/
public int binarySearch(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right) {
int mid = (left + right) >> 1; // 等价于 (left + right) / 2
if(nums[mid] == target) {
return mid;
}
if(nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return left;
}
}
34. 在排序数组中查找元素的第一个和最后一个位置
分析：
分别获取 第一个目标值 和 最后一个目标值
代码：
class Solution {
public int[] searchRange(int[] nums, int target) {
int[] res = new int[2];
res[0] = binarySearchFirst(nums, target);
res[1] = binarySearchLast(nums, target);
return res;
}
public int binarySearchFirst(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right) {
int mid = left + ((right - left) >> 1);
if(nums[mid] == target) {
// 下面两种情况，都说明是最左侧的target
if (mid == 0 || nums[mid - 1] != target)
return mid;
// 否则继续向左半区间查找
right = mid - 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
/**
* 找最后一个目标值
*/
public int binarySearchLast(int[] nums, int target) {
int left = 0;
int right = nums.length - 1;
while(left <= right) {
int mid = left + ((right - left) >> 1);
if(nums[mid] == target) {
// 下面两种情况，都说明是最右侧的target
if (mid == nums.length-1 || nums[mid + 1] != target)
return mid;
// 否则继续向右半区间查找
left = mid + 1;
} else if (nums[mid] < target) {
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
}
69. x 的平方根
分析：
首先 x^0.5 <= x （肯定的）
所以该题可以看做 从[0,1,2,3...x] 中，找到 n*n <= x 的最大值
[0,1,2,3...x]是个有序序列，因此我们可以使用二分法求解
在判断mid*mid 是否是 小于 x 的最大值时，我们可以这样写：
if(mid < x/mid) {
// 等价于 mid*mid < x
// 【关键判断】：若 mid+1 > x/(mid+1)，则mid*mid 肯定是小于 x 的最大值
if(mid+1 > x/(mid+1)) {
// 等价于 (mid+1)*(mid+1) > x
return mid;
}
left = mid + 1;
}
注意点：
x的范围 0 <= x <= 2^31 - 1
错误写法：n*n <= x (肯定会超出int或者long的范围)
正确写法：n <= x/n (分子、分母同时除以n，n*n <= x 等价于 n <= x/n)
代码：
class Solution {
public int mySqrt(int x) {
if(x == 0) {
return 0;
}
if(x == 1) {
return 1;
}
return binarySearch(x);
}
/**
* 目标： n*n <= x 的 最大值
*/
public int binarySearch(int x) {
// 可以看做从[0,1,2,3...x] 这些元素中查找目标元素
int left = 0;
int right = x;
while(left <= right) {
int mid = (left + right) / 2;
if(mid == x/mid) {
// 等价于 mid*mid == x
return mid;
}
if(mid < x/mid) {
// 等价于 mid*mid < x
// 【关键判断】：若 mid+1 > x/(mid+1)，则mid*mid 肯定是小于 x 的最大值
if(mid+1 > x/(mid+1)) {
// 等价于 (mid+1)*(mid+1) > x
return mid;
}
left = mid + 1;
} else {
right = mid - 1;
}
}
return -1;
}
}
74. 搜索二维矩阵
分析：
首先题中说明：
每一行都按照从左到右递增的顺序排序
每一列都按照从上到下递增的顺序排序。
那么一看数据是有序的， 那么我们肯定第一时间想到二分查找法。但在着整个二维数组中好像没法直接使用二分查找，但是我们可以使用二分查找的思想。
二分查找思想： 每一轮比较首先获取一个特殊值，然后让目标值与该值进行比较，每次比较都能排除一些数据进而缩小搜索的范围。
解决该题我们用的方法和二叉查找法类似，也是每次都取一个特殊值与目标值比较，每轮都排除一部分数据进而缩小数据的查找范围
B站上讲解视频：
https://www.bilibili.com/video/BV12J411i7A6
https://www.bilibili.com/video/BV1Tt411F7YD?spm_id_from=333.999.0.0
代码：
class Solution {
public boolean searchMatrix(int[][] array, int target) {
// 套路模板 先判空
if(array.length == 0) return false;
// row表示有几行,col表示有几列。
int row = array.length;
int col = array[0].length;
// 我们取右上角的值
int x = 0; int y = col - 1;
// 不断排除一列或者一行，不断缩小范围
while(x <= row-1 && y >= 0) {
if(target > array[x][y]) {
// 排除头一行的数据
x++;
}else if (target < array[x][y]) {
// 排除后一列的数据
y--;
}else {
return true;
}
}
// 若判处完所有数据仍没有找目标值 该值不存在
return false;
}
}
162. 寻找峰值
分析：
参考视频：【【LeetCode 每日一题】162. 寻找峰值 | 手写图解版思路 + 代码讲解】
- 较大的值则有可能是峰值，因此保留，并缩小区间
- 较小的值则不可能为峰值，因此舍弃，并缩小区间
代码：
class Solution {
public int findPeakElement(int[] nums) {
if(nums.length == 1) {
return 0;
}
int left = 0;
int right = nums.length - 1;
while(left < right) {
int mid = (left + right) >> 1;
if(nums[mid] > nums[mid+1]) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
}
JZ11 旋转数组的最小数字（存在重复值）
分析：
参考视频：【剑指Offer.6.旋转数组的最小数字】
序列可被分为两部分递增序列， 第一部分的最小值 >= 第二部分的最最大值
我们每次都取中间下标的值与左右侧的值进行比较
若 min下标的值 > 最右侧的值 ，则说明 min下标处于第一部分，而最小值在第二部分的范围内，因此我们就可以排除 min及左侧的所有数据了，最小值在 [min+1,right] 的范围内
若 min下标的值 < 最右侧的值， 则说明min下标所处第二部分，那么最小值在 [left,min]的范围内
若min下标的值 == 最右侧的值，而对于这种情况，又一种特殊情况，如下图：
直接说结论，若 min下标的值 == 最右侧的值， 则直接 right-- 即可，右指针后移
while循环的条件是 left < right，当left == right时，其实就只有一个数据了，该数据就是最小，最终直接返回array[left] 或者 array[right]
代码：
import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
// 套路模板，先判空
if(array.length == 0) return -1;
return erfen(array, 0, array.length-1);
}
public int erfen(int[] array, int left, int right) {
int min = 0;
while(left < right) {
// 因为当left==right时，其实就是我们要找的目标值，因此这里条件是left<right
min = (left + right) >> 1; // 等同于(left+right)/2
// 因为没有目标值，因此每次都是 中间下标值 与 最右侧的值进行比较
if(array[min] > array[right]) {
// 此情况说明min处于 第一部分的范围
left = min + 1;
}else if(array[min] < array[right]) {
// 此情况说明min处于 第二部分范围 因为可能是最小值 因此right不再是min+1
right = min;
}else {
// 若min 等于 最右侧的值， 直接right往左移一步即可，right--
right--;
}
}
// 最后 left=right 就是我们要找的最小值
return array[left];
}
}
153. 寻找旋转排序数组中的最小值（不包含重复值）
分析：
与上题不同，该题数组元素是不重复的，因此判断逻辑中不需要判断 nums[mid] == nums[right]这种情况
代码：
class Solution {
public int findMin(int[] nums) {
int left = 0;
int right = nums.length - 1;
while(left < right) {
int mid = (left + right) >> 1;
if(nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid;
}
}
return nums[left];
}
}
33. 搜索旋转排序数组
分析：
* 假设turningPointIdx为转折点下标：此时我们知道这两段递增序列范围（若数组本身就没有翻转，则还是一个段[0, nums.length-1]），分别是：
* 第一段：[0,turningPointIdx-1]
* 第二段：[turningPointIdx, nums.length-1]
* "第一段元素" > "第二段元素"
一共分三步：
- 找到转折点下标
- 判断
target所在的标有序区间turningPointIdx == 0，说明nums本身就是有序的，并没有翻转。则target还在[0, nums.length-1]内target >= nums[0]，说明target在[0,turningPointIdx-1]target < nums[0]，说明target在[turningPointIdx, nums.length-1]
- 在有序区间内进行二分查找
代码：
class Solution {
/**
* 假设turningPointIdx为转折点下标：此时我们知道这两段递增序列范围（若数组本身就没有翻转，则还是一个段[0, nums.length-1]），分别是：
* 第一段：[0,turningPointIdx-1]
* 第二段：[turningPointIdx, nums.length-1]
* "第一段元素" > "第二段元素"
*/
public int search(int[] nums, int target) {
// 【一、找到转折点下标】
int turningPointIdx = getTurningPoint(nums);
// 【二、target与nums[0]比较，判断target在 第一段 还是 第二段？】
// turningPointIdx == 0，说明nums本身就是有序的，并没有翻转
int left, right;
if(turningPointIdx == 0) {
left = 0;
right = nums.length - 1;
} else if (target >= nums[0]) {
// target在第一段
left = 0;
right = turningPointIdx - 1;
} else {
// target在第二段
left = turningPointIdx;
right = nums.length - 1;
}
// 【三、在有序范围内进行二分查找】
return binarySearch(nums, left, right, target);
}
/**
* 寻找旋转点的下标（就是找到转折数组的最小值）
* 若没有旋转（本身是有序的），则最终返回的下标肯定是0
*/
public int getTurningPoint(int[] nums) {
int left = 0;
int right = nums.length - 1;
while(left < right) {
int mid = (left + right) >> 1;
if(nums[mid] > nums[right]) {
left = mid + 1;
} else {
right = mid;
}
}
return left;
}
/**
* 在有序数组中进行二分查找
*/
public int binarySearch(int[] nums, int left, int right, int target) {
while(left <= right) {
int mid = (left + right) >> 1;
if(nums[mid] == target) {
return mid;
}
if(nums[mid] > target) {
right = mid - 1;
} else {
left = mid + 1;
}
}
return -1;
}
}
一维动态规划
70. 爬楼梯
分析：
想要跳到第n阶台阶，只有两种情况：（因为每次你只能爬 1 或 2 个台阶）
- 从第
n-1阶跳 - 从第
n-2阶跳
因此 跳到第n阶方法 = 跳到n-1阶方法 + 跳到n-2阶方法
代码：
class Solution {
public int climbStairs(int n) {
if(n == 1) {
return 1;
}
if(n == 2) {
return 2;
}
int[] dp = new int[n];
dp[0] = 1;
dp[1] = 2;
for(int i=2; i<n; i++) {
dp[i] = dp[i-1] + dp[i-2];
}
return dp[n-1];
}
}
198. 打家劫舍
分析：
参考视频：【动态规划，偷不偷这个房间呢？| LeetCode：198.打家劫舍】
dp[n]定义为：考虑第n间房，所能偷的最大值 【但不一定要偷第n间，只是考虑到第n间】（n从0开始）
- 对于第i间来说，有两种选择：1.偷第i间、2.不偷第i间
- 1、偷第
i间房：则不能偷第i-1间房屋，也就不能考虑第n-1间房。则此时value = nums[i] + dp[i-2] - 2、不偷第
i间房：则可以考虑偷第i-1间。则此时value = dp[i-1]
- 1、偷第
- 最终取两种情况的最大值，因此
dp[i] = Math.max(nums[i] + dp[i-2], dp[i-1])
初始化dp：
若只有一间房子肯定要偷第一间，因此dp[0] = nums[0]
有两个房间，不能两个都偷，因此偷最大值，因此 dp[1] = Math.max(nums[0], nums[1])
代码：
class Solution {
public int rob(int[] nums) {
int len = nums.length;
// 只有一个，则肯定偷这一个
if(len == 1) {
return nums[0];
}
// 有两个，则偷最大值
if(len == 2) {
return Math.max(nums[0], nums[1]);
}
// dp[n]定义为：考虑第n间房，所能偷的最大值 【但不一定要偷第n间，只是考虑到第n间】（n从0开始）
int[] dp = new int[len];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for(int i=2; i<len; i++) {
/**
* 有两种选择：1.偷第i间、2.不偷第i间
* 1、偷第i间房：则不能偷第i-1间房屋，也就不能考虑第n-1间房。则此时 value = nums[i] + dp[i-2]
* 2、不偷第i间房：则可以考虑偷第i-1间。则此时 value = dp[i-1]
* 最终取两种情况的最大值，因此 dp[i] = Math.max(nums[i] + dp[i-2], dp[i-1])
*/
dp[i] = Math.max(nums[i]+dp[i-2], dp[i-1]);
}
return dp[len-1];
}
}
139. 单词拆分
分析：
与【零钱对话】和【完全平方数】类似，都可以看成背包问题
- 第一层循环遍历 背包容量（目标字符串）
- 第二层循环遍历 物品（词典里的单词）
代码：
class Solution {
public boolean wordBreak(String s, List<String> wordDict) {
int len = s.length();
boolean[] dp = new boolean[len + 1];
dp[0] = true;
// 遍历背包
for(int i=1; i<=len; i++) {
String curStr = s.substring(0, i);
// 遍历物品
for(String str: wordDict) {
if(curStr.endsWith(str) && dp[i - str.length()]) {
dp[i] = true;
break;
}
}
}
return dp[len];
}
}
322. 零钱兑换
分析：
参考视频：【腾讯二面笔试题~零钱兑换】
若【爬楼梯】的题改成：
每次可爬coins[0]、coins[1] … coins[length-1]个台阶，问最少跳多少次能跳到amount？
其实就和这题一样了
若这题改成:
求兑换零钱的方法总数
其实就变成了【爬楼梯】的进阶版了
定义dp[n]为：兑换n元钱，最少需要的硬币数
dp[n]的状态 来源于 dp[n-coins[i]]，因此
dp[n] = min {
dp[n] = dp[n - coins[0]] + 1
dp[n] = dp[n - coins[1]] + 1
dp[n] = dp[n - coins[2]] + 1
...
dp[n] = dp[n - coins[length-1]] + 1
}
有点类似于【剑指 Offer 60. n个骰子的点数】这题
代码：
class Solution {
public int coinChange(int[] coins, int amount) {
if(amount == 0) {
return 0;
}
/**
* 零钱最小值是1，因此amount最多换amount个硬币。
* 为了考虑换不到零钱的情况，我们这里初始值设置为amount+1。最后dp[n] 和 amount+1比较，若仍等于amount+1，则说明n换不到零钱，最终返回-1
*/
// dp[n]定义：兑换amount最少的兑换次数
int[] dp = new int[amount + 1];
Arrays.fill(dp, amount + 1);
// 当amount为0时，则兑换方法为0
dp[0] = 0;
// 遍历amount（类似于遍历背包容量）
for(int i=1; i<=amount; i++) {
// 遍历金币（类似遍历物品）
for(int j=0; j<coins.length; j++) {
// 若当前金币大于总钱数，则直接continue
if(coins[j] > i) {
continue;
}
// 则算出新值：1 + dp[i - coins[j]]
int newVal = 1 + dp[i - coins[j]];
// 更新dp[i]的最小值
dp[i] = Math.min(newVal, dp[i]);
}
}
return dp[amount] == amount + 1 ? -1 : dp[amount];
}
}
300. 最长递增子序列
分析：
代码：
class Solution {
public int lengthOfLIS(int[] nums) {
// 用于最大返回值
int res = 1;
int len = nums.length;
// dp数组的含义： 以nums[i]结尾的最长递增子序列的长度（必须包含nums[i]）
int[] dp = new int[len];
Arrays.fill(dp, 1);
for(int i=1; i<len; i++) {
// 外层循环填dp[i]的值
for(int j=0; j<i; j++) {
// 内层循环 遍历nums[i]前面的元素
// 如果前面的值小于当前值 才能满足升序
if(nums[j] < nums[i]) {
int newVal = dp[j] + 1;
dp[i] = Math.max(dp[i], newVal);
}
}
// 从以[0,len)结尾的子序列中找到 最长的一个
res = Math.max(res, dp[i]);
}
/**
* 错误写法：return dp[len-1]
* 原因：最终的结果并非一定以len-1结尾的（而是整个nums子序列），因此最终结果并非dp[len-1]
*/
return res;
}
}
多维动态规划
JZ47 礼物的最大价值
代码：
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param grid int整型二维数组
* @return int整型
*/
public int maxValue (int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
// 初始化dp[0][0] 为 grid[0][0]
dp[0][0] = grid[0][0];
// 初始化第一行
for (int i = 1; i < n; i++) {
dp[0][i] = dp[0][i-1] + grid[0][i];
}
// 初始化第一列
for (int i = 1; i < m; i++) {
dp[i][0] = dp[i-1][0] + grid[i][0];
}
for(int i=1; i<m; i++) {
for(int j=1; j<n; j++) {
dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]) + grid[i][j];
}
}
return dp[m-1][n-1];
}
}
120. 三角形最小路径和
分析：
这种题需要找一个终点，一般都是将终点当最终的结果。因为是三角形状，我们最好想的就是，自底向上把顶点当做终点
与 【剑指 Offer 47. 礼物的最大价值】非常类似，只不过这里求得是最小值，而且走的方式不太一样
代码：
class Solution {
public int minimumTotal(List<List<Integer>> triangle) {
int row = triangle.size();
// 该图形是三角形，不是方形，因此这里高度别初始化错了，错误写法：col = triangle.get(0).size() 正确写法：col = row
int col = row;
int[][] dp = new int[row][col];
// 初始化最底部
for(int i=0; i<col; i++) {
dp[row-1][i] = triangle.get(row-1).get(i);
}
// 自顶向上，终点是triangle[0][0]
for(int i=row-2; i>=0; i--) {
for(int j=0; j<=i; j++) {
dp[i][j] = Math.min(dp[i+1][j], dp[i+1][j+1]) + triangle.get(i).get(j);
}
}
return dp[0][0];
}
}
64. 最小路径和
分析：
和上一题一模一样，只不过这题要求的是最小值
代码：
class Solution {
public int minPathSum(int[][] grid) {
int m = grid.length;
int n = grid[0].length;
int[][] dp = new int[m][n];
// 起点初始化为 grid[0][0]
dp[0][0] = grid[0][0];
// 初始化第一行
for(int i=1; i<n; i++) {
dp[0][i] = dp[0][i-1] + grid[0][i];
}
// 初始化第一列
for(int i=1; i<m; i++) {
dp[i][0] = dp[i-1][0] + grid[i][0];
}
for(int i=1; i<m; i++) {
for(int j=1; j<n; j++) {
dp[i][j] = Math.min(dp[i][j-1], dp[i-1][j]) + grid[i][j];
}
}
return dp[m-1][n-1];
}
}
63. 不同路径 II
分析：
有点像【爬台阶】，到达某点的路径 = 到达上面的路径 + 到达左边的路径
不同点：
- 该题是二维的
- 存在障碍物，若某点是障碍物则到达该点的路径为0
- 初始化边界时要注意，若中间遇到障碍物，则后序的点不可能再被到达，因此dp为0
代码：
class Solution {
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
int m = obstacleGrid.length;
int n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
/**
* 初始化第一行。
* 只能 → 从左到右，因此如果中遇见障碍物，后面就走不到了，因此obstacleGrid[0][i]==0写在for循环的条件中，若不满足则终止for循环
* 那么后面的则不能被设置为1，最终就是0，表示到达该点的路径为0
*/
for(int i=0; i<n && obstacleGrid[0][i]==0; i++) {
// 等于0，则说明不是障碍物，可以走
dp[0][i] = 1;
}
// 初始化第一列。只能↓ 从上到下，同上
for(int i=0; i<m && obstacleGrid[i][0]==0; i++) {
// 等于0，则说明不是障碍物，可以走
dp[i][0] = 1;
}
for(int i=1; i<m; i++) {
for(int j=1; j<n; j++) {
// 只有不是障碍物才能到达该点
if(obstacleGrid[i][j] == 0) {
dp[i][j] = dp[i][j-1] + dp[i-1][j];
}
}
}
return dp[m-1][n-1];
}
}
初始化边界时的错误写法：
// 初始化第一行
for(int i=0; i<n; i++) {
// 等于0，则说明不是障碍物，可以走
if(obstacleGrid[0][i] == 0) {
dp[0][i] = 1;
}
}
// 初始化第一列
for(int i=0; i<n; i++) {
// 等于0，则说明不是障碍物，可以走
if(obstacleGrid[i][0] == 0) {
dp[i][0] = 1;
}
}
5. 最长回文子串
解法一：暴力 - 遍历所有字串
建议先做第9题【9. 回文数】
代码：
class Solution {
public String longestPalindrome(String s) {
String longestPalindrome = "";
// 遍历所有的子串，若长度比longestPalindrome长 且 是回文串，则更新longestPalindrome
for(int i=0; i<s.length(); i++) {
for(int j=i; j<s.length(); j++) {
if(j - i + 1 > longestPalindrome.length()) {
if(isPalindrome(s.substring(i, j+1))) {
longestPalindrome = s.substring(i, j+1);
}
}
}
}
return longestPalindrome;
}
// 判断是否是回文字符串
public Boolean isPalindrome(String s) {
// 双指针
int left = 0;
int right = s.length() - 1;
while (left <= right) {
if(s.charAt(left) != s.charAt(right)) {
return false;
}
left ++;
right --;
}
return true;
}
}
总结注意点：
- 第一步：先写出 判断是否回文 的方法
isPalindrome。 （利用双指针的思想） - 第二步：暴力遍历每个子字符串，判断是否回文，更长的则更新
时间复杂度： n^3
解法二：中心扩展法
代码：
class Solution {
// 维护最长回文字符串
public String res;
public String longestPalindrome(String s) {
// 判空处理
if(null == s && s.length() == 0) {
return "";
}
// 初始化res
res = s.substring(0,1);
// 遍历s字符串
for(int i=0; i<s.length(); i++) {
// 考虑 bab 的格式
extendFromCenter(s, i, i);
// 考虑 baab 的格式
extendFromCenter(s, i, i+1);
}
return res;
}
// 中心扩散
public void extendFromCenter(String s, int left, int right) {
// 当 left、right 在区间返回内，且 s[left] == s[right] 才会向外扩散
while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)) {
// 向外扩散
left--;
right++;
}
// 若当前回文串 比 res长 则更新res
if(right - left - 1 > res.length()) {
// 因为最后一次循环 left-- right++了，因此实际上回文字符串是[left+1, right-1]，由于substring是左闭右开[)，因此 res = s.substring(left+1, right)
res = s.substring(left+1, right);
}
}
}
总结注意点：
- 解法一：判断字串是否是回文串，思想是
自外向内的，left ++; right --; - 解法二：寻找属于回文串的字串，且思想是
自内向外扩散的，left--; right++; - 要考虑
bab、baab两种回文串的格式， 因此在遍历到某个字符时，extendFromCenter(s, i, i);extendFromCenter(s, i, i+1);要调两次extendFromCenter
时间复杂度：n^2
买卖股票系列
参考【代码随想录】系列课程：
【动态规划之 LeetCode：121.买卖股票的最佳时机1】
【动态规划，股票问题第二弹 | LeetCode：122.买卖股票的最佳时机II】
【动态规划，股票至多买卖两次，怎么求？ | LeetCode：123.买卖股票最佳时机III】
【动态规划来决定最佳时机，至多可以买卖K次！| LeetCode：188.买卖股票最佳时】
参考题解：【一套模板，几行代码，闭着眼睛轻松默写所有彩票题】
121. 买卖股票的最佳时机
分析：
前面总结过这题，之前的做法是用两个变量，分别维护 股票最低点 以及 最大价值
今天我们用动态规划的方法来解这道题：
定义dp方程：
dp的值表示，当前口袋里有多少钱，默认是没钱的，为0
dp[i][0]：第i天，持有一个股票
dp[i][1] = 第i天，不持有股票
dp[i][0] 可以从下面两个状态转移过来：
- 可能是前一天就持有，因此是
dp[i-1][0] - 前天不持有，然后今天才买的，因此是
0 - prices[i] - 二者求最大值，因此
dp[i][0] = Math.max(dp[i-1][0], 0 - prices[i])
dp[i][1]可以从下面两个状态转移过来：
- 可能是前一天就不持有，因此是
dp[i-1][1] - 也有可能前天持有，然后今天才太卖了，因此是
dp[i][0] + prices[i] - 二者求最大值，因此
dp[i][1] = Math.max(dp[i-1][1], dp[i][0] + prices[i])
初始化：
dp[0][0] = -prices[0]：（第一天就持有，说明第一天就买了，因此是 0 -prices[0] = -prices[0]）dp[0][1] = 0：（第一天不持有，说明第一天没买，因此兜里钱还是0）
代码：
class Solution {
public int maxProfit(int[] prices) {
/**
* dp 的值表示，收益多少钱？（原始是0）
* dp[i][0] = 持有一个股票
* 1.1、 可能是前一天就持有
* 1.2、 前天不持有，然后今天才买的
* dp[i][1] = 不持有股票
* 2.2、可能是前一天就不持有
* 2.2、也有可能前天持有，然后今天才太卖了）
*/
int len = prices.length;
int[][] dp = new int[len][2];
// 初始化dp
dp[0][0] = -prices[0]; // 因为要买股票，所以要花钱，0 - prices[0] = -prices[0]
dp[0][1] = 0; // 不持有说明今天没买，因此没花钱
for(int i=1; i<prices.length; i++) {
// 1.1. 从 “前一天就持有” 的状态推过来的
// 1.2. 从当天才买股票推出来的，因为只能买一次，这次买口袋肯定是0元，因此是0-prices[i]（因为是花钱所以是 -prices[i]）
dp[i][0] = Math.max(dp[i-1][0], 0 - prices[i]);
// 2.1. 从 “前一天就不持有” 的状态推出来的
// 2.2. 从 “前天持有，今天才卖了” 的状态推出来的
dp[i][1] = Math.max(dp[i-1][1], dp[i][0] + prices[i]);
}
// 最后一天股票肯定是不持有状态（已经被卖过了），这样才会有收益，否则就亏钱了
return dp[len-1][1];
}
}
122. 买卖股票的最佳时机 II
分析：
与上一题唯一的不同在于 dp[i][0]的状态转移：
上一题：dp[i][0] = Math.max(dp[i-1][0], 0 - prices[i])
这一题：dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i])
上一题：因为只能买一次，所以dp[i-1][1] - prices[i] -> 其中的dp[i-1][1]（不持有状态）肯定为0，因此就是0 - prices[i]
这一题：因为可以买卖多次，所以dp[i-1][1] - prices[i] -> 其中的dp[i-1][1]可能之前就已经有收益了，因此就是dp[i-1][1] - prices[i]
代码：
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
int[][] dp = new int[len][2];
dp[0][0] = -prices[0];
dp[0][1] = 0;
for(int i=1; i<len; i++) {
dp[i][0] = Math.max(dp[i-1][0], dp[i-1][1] - prices[i]);
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i]);
}
return dp[len-1][1];
}
}
123. 买卖股票的最佳时机 III
分析：
这次定义四个状态：
- dp[i][0]：第i天，持有第1只股票
- dp[i][1]：第i天，不持有第1只股票
- dp[i][2]: 第i天，持有第2只股票
- dp[i][3]: 第i天，不持有第2只股票
dp[i][0]可有dp[i-1][0]和0 - prices[i]推出来，最后求最大值Math.max(dp[i-1][0], 0 - prices[i])dp[i][1]可有dp[i-1][1]和dp[i-1][0] + prices[i]推出来，最后求最大值Math.max(dp[i-1][1], dp[i-1][0] + prices[i])dp[i][2]可有dp[i-1][2]和dp[i-1][1] - prices[i]推出来，最后求最大值Math.max(dp[i-1][2], dp[i-1][1] - prices[i])dp[i][3]可有dp[i-1][3]和dp[i-1][2] + prices[i]推出来，最后求最大值Math.max(dp[i-1][3], dp[i-1][2] + prices[i])
状态转移方程的推导其实和前两题的推导都是一个方法，细细品味吧(#^.^#)
代码：
class Solution {
public int maxProfit(int[] prices) {
int len = prices.length;
int[][] dp = new int[len][4];
/**
* dp[i][0]：第i天，持有第1只股票
* dp[i][1]：第i天，不持有第1只股票
* dp[i][2]: 第i天，持有第2只股票
* dp[i][3]: 第i天，不持有第2只股票
*/
dp[0][0] = -prices[0];
dp[0][1] = 0;
dp[0][2] = -prices[0];
dp[0][3] = 0;
for(int i=1; i<len; i++) {
dp[i][0] = Math.max(dp[i-1][0], 0 - prices[i]);
dp[i][1] = Math.max(dp[i-1][1], dp[i-1][0] + prices[i]);
dp[i][2] = Math.max(dp[i-1][2], dp[i-1][1] - prices[i]);
dp[i][3] = Math.max(dp[i-1][3], dp[i-1][2] + prices[i]);
}
return dp[len-1][3];
}
}
188. 买卖股票的最佳时机 IV
分析：
其实这题是对上一题的一个通用性的总结（升华版）
看代码你就就知道了
代码：
class Solution {
public int maxProfit(int k, int[] prices) {
int len = prices.length;
int[][] dp = new int[len][2*k];
// 初始化dp
for(int i=0; i<2*k; i++) {
dp[0][i] = (i % 2 == 0 ? -prices[0] : 0);
}
for(int i=1; i<len; i++) {
for(int j=0; j<k; j++) {
dp[i][j*2] = Math.max(dp[i-1][j*2], (j == 0 ? 0 : dp[i-1][j*2-1]) - prices[i]);
dp[i][j*2+1] = Math.max(dp[i-1][j*2+1], dp[i-1][j*2] + prices[i]);
}
}
return dp[len-1][2*k-1];
}
}
回溯
回溯章节建议跟随【代码随想录-回溯】课程学习
真心推荐，卡尔讲的很不错
回溯模板
void backtracking(参数) {
if (终止条件) {
存放结果;
return;
}
for (选择：本层集合中元素（树中节点孩子的数量就是集合的大小）) {
处理节点;
backtracking(路径，选择列表); // 递归
回溯，撤销处理结果
}
}
常规回溯题 与 二叉树回溯题的差别
二叉树的回溯整体上确实是回溯的思想，大体思路也差不多。但在处理细节上还是有些不同的，例如【剑指 Offer 34. 二叉树中和为某一值的路径】与【39. 组合总和】相比：
- 二叉树要从根节点处理（每次递归中处理的是当前节点）；而常规回溯题一般不处理根节点（每次递归中处理的都是孩子节点，而且是多孩子）；因此在处理细节上是有差异的
- 二叉树递归代码：
public void backtracking(TreeNode root, int target, List<Integer> path) {
if(root == null) {
return;
}
// 处理当前节点
target -= root.val;
path.add(root.val);
if(target == 0 && root.left == null && root.right == null) {
res.add(new ArrayList(path));
}
// 处理左右孩子节点
backtracking(root.left, target, path);
backtracking(root.right, target, path);
// 状态重置
target += root.val;
path.remove(path.size() - 1);
}
- 常规回溯递归代码：
public void backtracking(List<Integer> path, int startIndex, int[] candidates, int target) {
// 终止条件
if(target == 0) {
res.add(new ArrayList(path));
return;
}
// for循环处理孩子节点
for(int i=startIndex; i<candidates.length; i++) {
// 剪枝：因为我们事先已经为数组排好序了，越往后数字越大，如果当前数字都已经减到负数了，那后面的就没必要在判断了
if(target - candidates[i] < 0) {
break;
}
target -= candidates[i];
path.add(candidates[i]);
backtracking(path, i, candidates, target);
// 状态重置
target += candidates[i];
path.remove(path.size() - 1);
}
}
17. 电话号码的字母组合
分析：
套用上面的模板即可，不细讲了
// 删除最后一个字符
sb.deleteCharAt(sb.length() - 1)
代码：
class Solution {
private List<String> res = new ArrayList();
StringBuilder path = new StringBuilder();
private String[] letters = {
" ","*","abc","def","ghi","jkl","mno","pqrs","tuv","wxyz"};
public List<String> letterCombinations(String digits) {
if (digits.length() == 0) {
return new ArrayList();
}
StringBuilder path = new StringBuilder();
backtracking(0, digits);
return res;
}
public void backtracking(int level, String digits) {
// 不合法（终止条件）
if(path.length() == digits.length()) {
// 此处也可以写成 level == digits.length() 来做为终止条件
res.add(path.toString()); // 添加到结果集
return;
}
// 找到对应的候选集
int index = digits.charAt(level) - '0';
char[] chars = letters[index].toCharArray();
// 因为每层的可选集都是独立的，因此for循环都可以从0开始（不会重复）
for(int i=0; i<chars.length; i++) {
path.append(chars[i]);
backtracking(level + 1, digits);
path.deleteCharAt(path.length() - 1); // 状态重置
}
}
}
77. 组合
分析：
参考视频：【带你学透回溯算法-组合问题（对应力扣题目：77.组合）| 回溯法精讲！】
可以将这题与上题对比来看
相同点：
- 都是组合问题，路径组合不能重复（例如：234 和 324就是重复的）
不同点：
- 上一题，每层的可选集都不一样。例如，输入“23”，第一层的可选集是“a、b、c”，第二层的可选集是“d、e、f”，因此我们在遍历每层的可选集时，都可以从下标0开始遍历（因为是独立的数据集，所以不会重复）
- 而该题，每层的可选集都是一样（都是[1,n]），但是我们要保证路径元素不能重复，所以在处理for循环时就要注意。下面是模拟回溯的多叉树状态，从左往右、从上到下 可选集的返回都会缩小1。这时我们使用
startIndex来记录下一层搜索的起始位置（for循环的初始下标）
回溯的过程的多叉树：
核心代码如下：
for(int i=startIndex; i<=n; i++)：从startIndex开始遍历，保证组合路径不会重复
backtracking(temp, i + 1, n, k)：使用i+1，保证组合中的元素不会重复
// 从左往右看 因为i本身会自增，且递归函数为backtracking(temp, i + 1, n, k)，参数2就是startIndex，因此越往右可选范围越小
// 越往下也是一样，调用backtracking(temp, i + 1, n, k)，越往下可选集范围越小
for(int i=startIndex; i<=n; i++) {
temp.add(i);
backtracking(temp, i + 1, n, k); // 核心
temp.remove(temp.size() - 1);
}
代码：
class Solution {
List<List<Integer>> res = new ArrayList();
List<Integer> path = new ArrayList();
public List<List<Integer>> combine(int n, int k) {
backtracking(1, n, k);
return res;
}
public void backtracking(int startIndex, int n, int k) {
// 终止条件
if(path.size() == k) {
res.add(new ArrayList(path));
return;
}
// 遍历 [startIndex, n]
for(int i=startIndex; i<=n; i++) {
path.add(i); // 操作当前节点
backtracking(i + 1, n, k); // 这里是i+1，不要错写成startIndex+1了
path.remove(path.size() - 1); // 状态重置
}
}
}
39. 组合总和
分析：
组合问题，因此我们也需要一个 startIndex 变量作为遍历的起始位置。这样做是为了避免出现重复的组合（例如：234 和 324就是重复的）
但与上题不同在于，该题可以允许组合中的元素重复，因此在调用递归方法时，startIndex就没必要+1了
剪枝：为了提高效率，我们事先对数组进行排序，越往后数字越大，如果加到某个节点已经超过了目标值，那后面的就没必要在判断了，因为加起来和会更大
代码：
class Solution {
List<List<Integer>> res = new ArrayList();
List<Integer> path = new ArrayList();
public List<List<Integer>> combinationSum(int[] candidates, int target) {
// 排序 后后序剪枝做准备
Arrays.sort(candidates);
backtracking(0, candidates, target);
return res;
}
public void backtracking(int startIndex, int[] candidates, int target) {
// 终止条件
if(target == 0) {
res.add(new ArrayList(path));
return;
}
for(int i=startIndex; i<candidates.length; i++) {
// 剪枝：因为我们事先已经为数组排好序了，越往后数字越大，如果当前数字都已经减到负数了，那后面的就没必要在判断了
if(target - candidates[i] < 0) {
break;
}
target -= candidates[i];
path.add(candidates[i]);
backtracking(i, candidates, target);
// 状态重置
target += candidates[i];
path.remove(path.size() - 1);
}
}
}
剑指 Offer 34. 二叉树中和为某一值的路径
分析：
二叉树的回溯整体上确实是回溯的思想，大体思路也差不多。但在处理细节上还是有些不同的，例如和前面组合问题相比：
- 二叉树要从根节点处理（每次递归中处理的是当前节点）；而常规回溯题一般不处理根节点（每次递归中处理的都是孩子节点，而且是多孩子）；因此在处理细节上是有差异的
- 二叉树代码 ：
public void backtracking(TreeNode root, int target, List<Integer> path) {
if(root == null) {
return;
}
// 处理当前节点
target -= root.val;
path.add(root.val);
if(target == 0 && root.left == null && root.right == null) {
res.add(new ArrayList(path));
}
// 处理左右孩子节点
backtracking(root.left, target, path);
backtracking(root.right, target, path);
// 状态重置
target += root.val;
path.remove(path.size() - 1);
}
- 常规回溯代码：
public void backtracking(List<Integer> path, int startIndex, int[] candidates, int target) {
// 终止条件
if(target == 0) {
res.add(new ArrayList(path));
return;
}
// for循环处理孩子节点
for(int i=startIndex; i<candidates.length; i++) {
// 剪枝：因为我们事先已经为数组排好序了，越往后数字越大，如果当前数字都已经减到负数了，那后面的就没必要在判断了
if(target - candidates[i] < 0) {
break;
}
target -= candidates[i];
path.add(candidates[i]);
backtracking(path, i, candidates, target);
// 状态重置
target += candidates[i];
path.remove(path.size() - 1);
}
}
代码：
class Solution {
private List<List<Integer>> res = new ArrayList();
public List<List<Integer>> pathSum(TreeNode root, int target) {
List<Integer> path = new ArrayList();
backtracking(root, target, path);
return res;
}
public void backtracking(TreeNode root, int target, List<Integer> path) {
if(root == null) {
return;
}
// 处理当前节点
target -= root.val;
path.add(root.val);
if(target == 0 && root.left == null && root.right == null) {
res.add(new ArrayList(path));
}
// 递归调用左右子节点
backtracking(root.left, target, path);
backtracking(root.right, target, path);
// 状态重置
target += root.val;
path.remove(path.size() - 1);
}
}
46. 全排列
分析：
因为不是组合问题，所以我们每层遍历时都不用缩小可选的范围，只需要判断当前路径中是否存在该元素即可
代码：
class Solution {
List<List<Integer>> res = new ArrayList();
List<Integer> path = new ArrayList();
public List<List<Integer>> permute(int[] nums) {
backtracking(nums);
return res;
}
public void backtracking(int[] nums) {
if(path.size() == nums.length) {
res.add(new ArrayList(path));
return;
}
for(int i=0; i<nums.length; i++) {
// 若存在重复元素则不添加
if(path.contains(nums[i])) {
continue;
}
path.add(nums[i]);
backtracking(nums);
path.remove(path.size() -1);
}
}
}
47. 全排列 II
分析：
与上题不同，该题中提到序列中可能有重复的元素，因此我们要考虑对排列去重
整体逻辑可参考视频：【代码随想录：回溯算法求解全排列，如何去重？| LeetCode：47.全排列 II】
去重逻辑可参考视频：【代码随想录：回溯算法中的去重，树层去重树枝去重，你弄清楚了没？| LeetCode:40.组合总和II】
我们使用一个used数组来表示某个下标的元素在当前路径中是否被使用过?
核心代码：
/**
* 树层去重操作， 当前前元素 与 前一个元素相同，且前一个元素在当前路径未使用过
* 树层去重：arr[i] == arr[i-1] && used[i-1] == 0
* 树枝去重：arr[i] == arr[i-1] && used[i-1] == 1
*/
if(i > 0 && arr[i] == arr[i-1] && used[i-1] == 0) {
continue;
}
代码：
class Solution {
List<List<Integer>> res = new ArrayList();
List<Integer> path = new ArrayList();
public List<List<Integer>> permuteUnique(int[] nums) {
int[] used = new int[nums.length];
// 对元素排序，方便去重处理
Arrays.sort(nums);
backtracking(nums, used);
return res;
}
public void backtracking(int[] nums, int[] used) {
if(path.size() == nums.length) {
// 错误写法：res.add(path);
// 正确写法：res.add(new ArrayList(path));
res.add(new ArrayList(path));
return;
}
for(int i=0; i<nums.length; i++) {
// 【去重处理】若树层重复，则直接跳过
if(i > 0 && nums[i-1] == nums[i] && used[i-1] == 0) {
continue;
}
// 已使用过则跳过
if(used[i] == 1) {
continue;
}
path.add(nums[i]);
used[i] = 1;
backtracking(nums, used);
used[i] = 0;
path.remove(path.size() - 1);
}
}
}
51. N 皇后
分析：
参考视频：【这就是传说中的N皇后？ 回溯算法安排！| LeetCode：51.N皇后】
参考题解：51. N-Queens:【回溯法经典问题】详解
- 用一个二维数组
chessBoard来记录棋盘的状态 - 每往下深入一行，然后遍历各个列，判断 当前点
chessBoard[row][col]是否有效？ - 是否有效判断逻辑：判断当前点
左上方、正上方、右上方是否有皇后，若存在则说明不符合规则 是无效的，就返回false
代码：
class Solution {
List<List<String>> res = new ArrayList();
public List<List<String>> solveNQueens(int n) {
char[][] chessBoard = new char[n][n];
// 初始化棋盘，默认都是'.'
for(char[] chars: chessBoard) {
Arrays.fill(chars, '.');
}
backtracking(chessBoard, n, 0);
return res;
}
public void backtracking(char[][] chessBoard, int n, int row) {
if(row == n) {
res.add(arrayToList(chessBoard));
return;
}
for(int col=0; col<n; col++) {
if(isValid(chessBoard, n, row, col)) {
chessBoard[row][col] = 'Q';
backtracking(chessBoard, n, row + 1);
chessBoard[row][col] = '.';
}
}
}
/**
* 检查 chessBoard[row][col] 的 “正上方”、“左上方”、“右上方” 是否有皇后？
* 存在皇后，说明chessBoard[row][col]是无效的返回false，不存在说明chessBoard[row][col]是有效的，返回true
*/
public boolean isValid(char[][] chessBoard, int n, int row, int col) {
// 检查上方 是否有皇后
for(int i=0; i<row; i++) {
if(chessBoard[i][col] == 'Q') {
return false;
}
}
// 检查左上方 是否有皇后
for(int i=row-1, j=col-1; i>=0 && j>=0; i--, j--) {
// 往左上角移动
if(chessBoard[i][j] == 'Q') {
return false;
}
}
// 检查右上方 是否有皇后
for(int i=row-1, j=col+1; i>=0 && j<n; i--, j++) {
// 往右上角移动
if(chessBoard[i][j] == 'Q') {
return false;
}
}
return true;
}
/**
* 二维字符数组 -> 字符串集合
*/
public List arrayToList(char[][] chessBoard) {
List<String> list = new ArrayList();
for(char[] chars: chessBoard) {
list.add(new String(chars));
}
return list;
}
}
22. 括号生成
分析：
参考题解：【虽然不是最秀的，但至少能让你看得懂！】
还是常规的回溯法，一样的配方
- 该题 可以看做 从 数组
[ '(' , ')' ]中进行2*n次排列（该数组仅有左括号和有括号2个元素）
在此树的基础上我们要删除掉不符合的路径，进行剪枝
- 需要满足一定条件才能拼接到
path路径中（剪枝）- 充要条件：
左括号数量<=n并且右括号数量<=左括号数量 - 代码：
left <= n && right <= left
- 充要条件：
代码：
class Solution {
List<String> res = new ArrayList();
public List<String> generateParenthesis(int n) {
StringBuilder sb = new StringBuilder();
backtracking(sb, 0, 0, n);
return res;
}
/**
* left、right 分别指左右括号的数量
*/
public void backtracking(StringBuilder path, int left, int right, int n) {
// 终止条件
if(path.length() == n * 2) {
res.add(path.toString());
return;
}
// 递归处理子孩子（因为只有左、右两种括号，因此就只有两个孩子）
if(isValid(left+1, right, n)) {
// 追加一个“左括号”
path.append('(');
backtracking(path, left + 1, right, n);
path.deleteCharAt(path.length() - 1);
}
if(isValid(left, right+1, n)) {
// 追加一个“右括号”
path.append(')');
backtracking(path, left, right + 1, n);
path.deleteCharAt(path.length() - 1);
}
}
/**
* 判断括号有效的条件
* 若left > n 或者 right > left 那就是无效的
*/
public boolean isValid(int left, int right, int n) {
if(left <= n && right <= left) {
return true;
}
return false;
}
}
分治
108. 将有序数组转换为二叉搜索树
分析：
当看到有序数组，第一印象想到二分
当看到二叉树，第一印象想到中序遍历，但是这题是构造二叉树，因此用不到中序遍历
- 每次都取数组中心元素作为根节点，那么左、右子树的节点个数绝对值相差一定<=1
- 左、右子树其实是规模更小的相同问题，顺其自然想到递归分治的思想
- 分别处理左、右子数组，直到
left > right为止
代码：
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return dfs(nums, 0, nums.length - 1);
}
public TreeNode dfs(int[] nums, int left, int right) {
if(left > right) {
return null;
}
int mid = (left + right) >> 1;
TreeNode root = new TreeNode(nums[mid]);
root.left = dfs(nums, left, mid - 1);
root.right = dfs(nums, mid + 1, right);
return root;
}
}
148. 排序链表
分析：
最简单的做法就是将所有节点放到集合中，然后对集合进行排序（任意排序算法都可以），这里可参考【八大排序算法】
了解排序算法的，会发现归并排序处理链表是非常舒服的，尤其是合并阶段
该题我使用的就是链表版的归并排序，数组版的归并排序可以参考：【归并排序】
归并排序主要分两个阶段：
- 分治：将待排序列二分，一直向下划分，直到只有一个元素为止（只有一个元素相当于已排序）
- 合并：将已排序的两个子序列合并为一个新的有序序列（主要逻辑）
动画排序过程：
该题我拆分了三个小方法：
【获取链表中心元素】
在【LeetCode刷题总结 - 剑指offer系列 - 持续更新】这篇文章中有总结过，当存在偶数个节点时，怎么获取中心左侧的元素？怎么获取中心右侧的元素？
该题中我们要获取的是中心左侧的元素，因为后面我们要断开链表就需要靠左的元素执行 node.next = null
/**
* 返回中心节点
* 若节点个数为偶数，则返回中心左边的节点，例如[1,2,3,4]，最终返回2
*/
public ListNode getMiddle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while(fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
【合并两个有序的链表】
/**
* 归并：将两个有序的链表 合并为一个链表
*/
public ListNode merge(ListNode left, ListNode right) {
// 虚拟头节点
ListNode head = new ListNode(0);
ListNode cur = head;
// 合并（左链表、右链表都存在未合并的元素）
while(left != null && right != null) {
if(left.val <= right.val) {
cur.next = left;
left = left.next;
} else {
cur.next = right;
right = right.next;
}
cur = cur.next;
}
// 能走到这里，只有有两种情况：1、左边合并完了、右边没合并完 2、左边没合并完、右边合并完了
// 合并左链表剩余的元素
if(left != null) {
cur.next = left;
}
// 合并右链表剩余的元素
if(right != null) {
cur.next = right;
}
return head.next;
}
【归并排序整体框架】
public ListNode sort(ListNode head) {
// 终止条件，只有一个元素就不必再排序了
if(head != null && head.next == null) {
return head;
}
// 获取中心节点
ListNode middle = getMiddle(head);
// 从中心断开，left为做链表，right为右链表
ListNode right = middle.next;
middle.next = null;
ListNode left = head;
// 递归划分处理左半段
ListNode sortedLeft = sort(left);
// 递归划分处理右半段
ListNode sortedRight = sort(right);
// 将划分后的排序合并（排序的主要逻辑在这个方法里）
return merge(sortedLeft, sortedRight);
}
代码：
class Solution {
public ListNode sortList(ListNode head) {
if(head == null) {
return null;
}
return sort(head);
}
public ListNode sort(ListNode head) {
// 终止条件，只有一个元素就不必再排序了
if(head != null && head.next == null) {
return head;
}
// 获取中心节点
ListNode middle = getMiddle(head);
// 从中心断开，left为做链表，right为右链表
ListNode right = middle.next;
middle.next = null;
ListNode left = head;
// 递归划分处理左半段
ListNode sortedLeft = sort(left);
// 递归划分处理右半段
ListNode sortedRight = sort(right);
// 将划分后的排序合并（排序的主要逻辑在这个方法里）
return merge(sortedLeft, sortedRight);
}
/**
* 归并：将两个有序的链表 合并为一个链表
*/
public ListNode merge(ListNode left, ListNode right) {
// 虚拟头节点
ListNode head = new ListNode(0);
ListNode cur = head;
// 合并（左链表、右链表都存在未合并的元素）
while(left != null && right != null) {
if(left.val <= right.val) {
cur.next = left;
left = left.next;
} else {
cur.next = right;
right = right.next;
}
cur = cur.next;
}
// 能走到这里，只有有两种情况：1、左边合并完了、右边没合并完 2、左边没合并完、右边合并完了
// 合并左链表剩余的元素
if(left != null) {
cur.next = left;
}
// 合并右链表剩余的元素
if(right != null) {
cur.next = right;
}
return head.next;
}
/**
* 返回中心节点
* 若节点个数为偶数，则返回中心左边的节点，例如[1,2,3,4]，最终返回2
*/
public ListNode getMiddle(ListNode head) {
ListNode slow = head;
ListNode fast = head;
while(fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
}
23. 合并 K 个升序链表
分析：
还是归并排序的思路。
其实归并排序的本质就是，将两个有序的序列合并为一个有序的序列。归并排序是先将长序列 分成无数个小的子序列，其实就是为了得到有序的序列，因为当子序列长度为1时，就可以看做有序的序列了，紧接着在二二合并
该题其实就是给了我们已经排序好的子序列，然后让我们二二合并，而为了提高效率，我们可以参考归并排序使用分治的思想，时间复杂度（nlogk）
代码：
class Solution {
public ListNode mergeKLists(ListNode[] lists) {
if(lists == null || lists.length==0) {
return null;
}
return partition(lists, 0, lists.length-1);
}
/**
* 本质上还是归并排序的框架
*/
public ListNode partition(ListNode[] lists, int left, int right) {
// 终止条件，只有一个链表就没必要再合并了
if(left == right) {
return lists[left];
}
int mid = (left + right) >> 1;
// 递归处理左边
ListNode sortedLeft = partition(lists, left, mid);
// 递归处理右边
ListNode sortedRight = partition(lists, mid+1, right);
// 归并
return merge(sortedLeft, sortedRight);
}
/**
* 归并：将两个有序的链表 合并为一个链表
*/
public ListNode merge(ListNode left, ListNode right) {
// 虚拟头节点
ListNode head = new ListNode(0);
ListNode cur = head;
// 合并（左链表、右链表都存在未合并的元素）
while(left != null && right != null) {
if(left.val <= right.val) {
cur.next = left;
left = left.next;
} else {
cur.next = right;
right = right.next;
}
cur = cur.next;
}
// 能走到这里，只有有两种情况：1、左边合并完了、右边没合并完 2、左边没合并完、右边合并完了
// 合并左链表剩余的元素
if(left != null) {
cur.next = left;
}
// 合并右链表剩余的元素
if(right != null) {
cur.next = right;
}
return head.next;
}
}
位运算
左移(
<<)、右移(>>)、无符号右移(>>>)，不存在无符号左移
【Java中的左移、右移、无符号右移(逻辑右移) 详细分析】
<<表示左移，不分正负数，低位补0 。 例如：r = 20 << 2 = 80；r = -20 << 2 = -80>>表示右移，如果该数为正，则高位补0，若为负数，则高位补1。 例如：r = 20 >> 2 = 5；r = -20 >> 2 = -5>>>表示无符号右移，也叫逻辑右移，即若该数为正，则高位补0，而若该数为负数，则右移后高位同样补0。例如：20 >>> 2=-20 >>> 2= 1073741819
得到数字n的第一位字节
(n & 1) ： 获取第一位字节
同理，若想得到n的第i位的bit值，则先将数字逻辑右移i-1位，再和1求与，即(n >>> (i-1)) & 1
190. 颠倒二进制位
分析：
代码：
public class Solution {
public int reverseBits(int n) {
int rev = 0;
for(int i=0; i<32; i++) {
// 保留第一位字节， 后面的全部补0，相当于 1101 -> 0001 （以4位为例）
int bit = (n & 1);
// 左移 31-i位，相当于 0001 -> 1000 （以4位为例）
bit = bit << (31 - i);
// 相当于把这一位字节 加到结果上，相当于 rev + bit = 0000 + 1000 = 1000 （这里假设rev为0）
rev |= bit;
// 右移一位，相当于删除刚才已经计算的那一位， 相当于 1101 -> 0110 （右移了一位）
n >>>= 1; // 这里要用逻辑右移 >>>
}
return rev;
}
}
191. 位1的个数
分析：
判断每一位是否为1？
是则count++
代码：
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int count = 0;
for(int i=0; i<32; i++) {
// 判断第1位是否为1
if((n & 1) == 1) {
count++;
}
// 无符号右移
n >>>= 1;
}
return count;
}
}
JZ65 不用加减乘除做加法
分析：
简单来说就是： a + b 等价于 (a ^ b) + ((a & b) << 1)
代码：
递归版代码：（更易懂）
class Solution {
/**
* a + b 等价于 (a ^ b) + ((a & b) << 1)
* 因此递归处理
*/
public int add(int a, int b) {
// 若a == 0，则 a + b = b
if(a == 0) return b;
// 若b == 0，则 a + b = a
if(b == 0) return a;
int m = a ^ b;
int n = (a & b) << 1;
// 递归处理 m + n
return add(m, n);
}
}
非递归版代码：
public class Solution {
public int Add(int num1,int num2) {
// 重复加法运算 直到进位和求得为0
while(num2 != 0) {
// 不进位 + ，用 异或操作
int sum = num1 ^ num2;
// 进位 + ， 用 与操作
int c = (num1 & num2) << 1;
// 紧接着 （和s）==（非进位和sum）+（进位c）
num1 = sum; // num1 变sum
num2 = c; // num2 变 c 重复加法运算
}
return num1;
}
}
136. 只出现一次的数字
分析：
这道题主要利用位运算中异或的性质
异或：二进制下用1表示真，0表示假，则异或的运算法则为：0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0（同为0，异为1）
对于这道题，可使用异或运算 ⊕。异或运算有以下三个性质。
- 任何数和 0 做异或运算，结果仍然是原来的数，即
a⊕0=a。 - 任何数和其自身做异或运算，结果是 0，即
a⊕a=0。 - 异或运算满足交换律和结合律，即
a⊕b⊕a =b⊕a⊕a = b⊕(a⊕a) = b⊕0=b。
因为该数组中只有一个数出现一次，其他数都是出现两次，所有若让数组中所有的数参与异或运算，最终的结果肯定是只出现一次的那个数。
代码：
class Solution {
public int singleNumber(int[] nums) {
int res = 0;
for(int i=0; i<nums.length; i++) {
res ^= nums[i];
}
return res;
}
}
剑指 Offer 56 - I. 数组中数字出现的次数
分析：
异或：二进制下用1表示真，0表示假，则异或的运算法则为：0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0（同为0，异为1）
假设这两个数为 res1 和 res2
- 若按照上一题求解，那么最终的结果是
diff = res1 ^ res2（res1 ^ res2：那么二进制每一位分别进行异或运算） - 技巧：
diff &= -diff，最终只有一位为1（00001000这种格式的数据），并且第4位就是diff最低位的1 res1 ^ res2的第4位为1。这能说明什么？res1和res2在这一位是不同的，那么我们就可以根据这一点 将序列分成两组，res1和res2分别在这两个数组中。此刻该题就降级了，就变成和上一题一样了
代码：
class Solution {
public int[] singleNumbers(int[] nums) {
int diff = 0;
for(int i=0; i<nums.length; i++) {
diff ^= nums[i];
}
// 此刻的diff = res1 ^ res2 （^：异或，每一位位运算，相同则0，不同则1）
// 技巧：diff &= -diff，得出的结果是 00001000这种格式的数据 得出diff最低位为1的位置，
// 此刻我们能知道 res1 和 res2在某一位是有差异的，即res1和res2在这一位不同，一个为0，一个为1
diff &= -diff;
int res1 = 0;
int res2 = 0;
for(int i=0; i<nums.length; i++) {
int cur = nums[i];
// 以(cur & diff) == 0为判断条件，将数据分成两组，res1和res2分别在这两组中
if((cur & diff) == 0) {
res1 ^= cur;
} else {
res2 ^= cur;
}
}
return new int[] {
res1, res2};
}
}
JZ64 求1+2+3+…+n
分析：
这里因为不能用while因此用的是递归的方式；
因为不能用if，因此用的是&&来做短路：只有前面第一个逻辑成立才会执行后面的逻辑代码。
代码：
public class Solution {
// res 用于存放累加结果
int res = 0;
public int Sum_Solution(int n) {
// 其实这里的temp是无用的，只是为了充当一个布尔值保证，后面的 && 左右的代码执行
// 后面判断Sum_Solution(n-1) > 0也是无用的， 只是为了执行 Sum_Solution(n-1)这段代码
// 这里只有 n>1 满足后才会执行后面的递归代码 ， 因为 && 也叫做短路运算法
// 效果类似于 if(n>1) Sum_Solution(n-1)
boolean temp = n>1 && Sum_Solution(n-1) > 0;
// 累加n
res += n;
return res;
}
}
201. 数字范围按位与
分析：
实际上要求的是 left 和 right的最长前缀
参考视频：【【LeetCode 每日一题】201. 数字范围按位与 | 手写图解版思路 + 代码讲解】
- 蓝色，前部分二进制位都是相同的，最终相与，前部分结果也一定是相同，一定不变
- 而非蓝色部分（从左往右看，第一个不相同的位开始），从 0xx 累加到 1xx，肯定会经过 011 和 100，这两个数相与 必为0，所以蓝色之后的结果最终肯定为0
- 因此最终的结果就是，最长公共前缀所表示的二进制结果
代码：
class Solution {
public int rangeBitwiseAnd(int left, int right) {
int ret = 0;
for(int i=0; i<32; i++) {
// 如果同时右移i位相同，则说明31-i位就是最长相同前缀
if((left >> i) == (right >> i)) {
// 将前i位补0（非相同前缀位）
ret = (left >> i) << i;
break;
}
}
return ret;
}
}
哈希表
383. 赎金信
分析：
- 利用一个大小为26的数组来表示字母
- 下标用来区分对应的字母。例如： 字母
b， 那么‘b’ - 'a' = 1那么下标1就用来表示字母b；字母z，'z' - 'a' = 25，那么下标25就用来表示z - 数组对应的值用来表示该字母的个数
代码：
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
if(magazine.length() == 0) {
return false;
}
int len1 = ransomNote.length();
int len2 = magazine.length();
// 用数组下标来表示26个英文字母，对应的值表示该字母的个数
int[] arr = new int[26];
for(int i=0; i<len2; i++) {
char cur = magazine.charAt(i);
arr[cur - 'a']++;
}
for(int i=0; i<len1; i++) {
char cur = ransomNote.charAt(i);
if(arr[cur - 'a'] == 0) {
return false;
} else {
arr[cur - 'a']--;
}
}
return true;
}
}
205. 同构字符串
分析：
- 需要维护两个map。
s2tMap用来映射s到t，t2sMap用来映射t到s - 同步遍历两个字符串（s和t）并获取对应的字符
c1、c2 - 若
s2tMap包含c1但是映射的值不等于c2，则返回false；需要满足双向映射。因此若t2sMap包含c2但是映射的值不等于c1，则返回false
代码：
解法一：
class Solution {
public boolean isIsomorphic(String s, String t) {
Map<Character, Character> s2tMap = new HashMap();
Map<Character, Character> t2sMap = new HashMap();
for(int i=0; i<s.length(); i++) {
char c1 = s.charAt(i);
char c2 = t.charAt(i);
// 判断s到t的映射
if(s2tMap.containsKey(c1) && s2tMap.get(c1) != c2) {
return false;
}
// 判断t到s的映射
if(t2sMap.containsKey(c2) && t2sMap.get(c2) != c1) {
return false;
}
s2tMap.put(c1, c2);
t2sMap.put(c2, c1);
}
return true;
}
}
优化：
题中明确说 s 和 t 由任意有效的 ASCII 字符组成，而ASCII的只有128个，因此我们可以用int[128]来表示对应的字符
class Solution {
public boolean isIsomorphic(String s, String t) {
// ASCII 一共 128个数字，这里我们用0-127来表示
int[] s2tMap = new int[128];
int[] t2sMap = new int[128];
Arrays.fill(s2tMap, -1);
Arrays.fill(t2sMap, -1);
for(int i=0; i<s.length(); i++) {
char c1 = s.charAt(i);
char c2 = t.charAt(i);
if(s2tMap[c1] != -1 && s2tMap[c1] != c2) {
return false;
}
if(t2sMap[c2] != -1 && t2sMap[c2] != c1) {
return false;
}
s2tMap[c1] = c2;
t2sMap[c2] = c1;
}
return true;
}
}
290. 单词规律
分析：
其实和上一题【同构字符串】的意思是一样的，因为我们需要维护两个map，保证双向映射（建议先做上一题）
代码：
class Solution {
public boolean wordPattern(String pattern, String s) {
String[] arr = s.split(" ");
if(pattern.length() != arr.length) {
return false;
}
Map<Character, String> p2s = new HashMap();
Map<String, Character> s2p = new HashMap();
for(int i=0; i<pattern.length(); i++) {
char c = pattern.charAt(i);
String str = arr[i];
if(p2s.containsKey(c) && !p2s.get(c).equals(str)) {
return false;
}
if(s2p.containsKey(str) && s2p.get(str) != c) {
return false;
}
p2s.put(c, str);
s2p.put(str, c);
}
return true;
}
}
242. 有效的字母异位词
分析：
用int[26]来表示26个英文字母的个数，和上面【383. 赎金信】这题是类似的
代码：
class Solution {
public boolean isAnagram(String s, String t) {
if(s.length() != t.length()) {
return false;
}
// int[26] 用来表示26个英文字母的个数
int[] arr = new int[26];
char[] arrS = s.toCharArray();
for(int i=0; i<s.length(); i++) {
char c = arrS[i];
arr[c -'a']++;
}
char[] arrT = t.toCharArray();
for(int i=0; i<t.length(); i++) {
char c = arrT[i];
arr[c - 'a']--;
if(arr[c - 'a'] == -1) {
return false;
}
}
return true;
}
}
字母异位词分组
分析：
由于互为字母异位词的两个字符串包含的字母相同，因此对两个字符串分别进行排序之后得到的字符串一定是相同的，故可以将排序之后的字符串作为哈希表的键。
代码：
class Solution {
public List<List<String>> groupAnagrams(String[] strs) {
Map<String, List<String>> map = new HashMap<String, List<String>>();
for (String str : strs) {
char[] array = str.toCharArray();
// 字母异位词 排序后一定相同
Arrays.sort(array);
String key = new String(array);
List<String> list = map.getOrDefault(key, new ArrayList<String>());
list.add(str);
map.put(key, list);
}
return new ArrayList<List<String>>(map.values());
}
}
1. 两数之和
分析：
- 空间换时间的思想，将当前值 以及对应下标信息 存储在map中
核心代码：
// 初始化：存储 某个值 以及 在nums中的位置信息
HashMap<Integer, Integer> tempMap = new HashMap();
// 如果目标值 存在tempMap中，则说明找到了结果
if(tempMap.containsKey(another)) {
res[0] = i;
res[1] = tempMap.get(another);
return res;
}
// 主流程：把当前值 及 对应位置信息存入到map中
tempMap.put(nums[i], i);
代码：
class Solution {
public int[] twoSum(int[] nums, int target) {
// 初始化map： 【值:下标】
HashMap<Integer, Integer> tempMap = new HashMap();
int[] res = new int[2];
for(int i=0; i<nums.length; i++) {
Integer another = target - nums[i];
// 如果目标值 存在tempMap中，则说明找到了结果
if(tempMap.containsKey(another)) {
res[0] = i;
res[1] = tempMap.get(another);
return res;
}
// 将【值:下标】 存储在map中 (常规套路，在写代码时进入for后 就可以先写这一步)
tempMap.put(nums[i], i);
}
return res;
}
}
219. 存在重复元素 II
分析：
关键点：使用一个map来记录，某个值在nums中的下标
代码：
class Solution {
public boolean containsNearbyDuplicate(int[] nums, int k) {
// key：对应值 value：在nums的下标
Map<Integer, Integer> map = new HashMap();
for(int i=0; i<nums.length; i++) {
int cur = nums[i];
if(map.containsKey(cur) && i - map.get(cur) <= k) {
return true;
}
map.put(cur, i);
}
return false;
}
}
128. 最长连续序列
分析：
参考题解：【【超小白】哈希集合/哈希表/动态规划/并查集四种方法，绝对够兄弟们喝一壶的！】
- 首先遍历数组，将数据存储到
set中，set有两个作用：- 作用1：使用
hashSet判断元素是否存在，时间复杂度为O(1) - 作用2：元素去重
- 作用1：使用
- 遍历
set，计算元素连续累加的最大长度。若cur-1存在，则没必要计算，原因：- 原因1：如果
num-1已经在数组中的话，那么num-1肯定会进行相应的+1遍历，然后遍历到num - 原因2：而且从
num-1开始的+1遍历必定比从num开始的+1遍历得到的序列长度更长
- 原因1：如果
代码：
class Solution {
public int longestConsecutive(int[] nums) {
int res = 0;
Set<Integer> set = new HashSet();
for(int num: nums) {
set.add(num);
}
// 遍历去重后的set
for(int num: set) {
int cur = num;
/**
* 若存在 cur-1，那么我们是没必要计算的，因为
* 1. 如果num-1已经在数组中的话，那么num-1肯定会进行相应的+1遍历，然后遍历到num
* 2. 而且从num-1开始的+1遍历必定比从num开始的+1遍历得到的序列长度更长
* 结论：我们便可将在一个连续序列中的元素让其只在最小的元素才开始+1遍历
*/
if(!set.contains(cur-1)) {
// 计算累加连续最大长度
while(set.contains(cur+1)) {
cur++;
}
// 更新最大值
res = Math.max(res, cur - num + 1);
}
}
return res;
}
}
堆
373. 查找和最小的 K 对数字
分析：
其实就是将多个有序序列合并为一个有序序列，不过只需要排前k个值就可以了
有序序列分别为：
- 序列1：
num1[0]+num2[0]、num1[0]+num2[1]、num1[0]+num2[2]、num1[0]+num2[3]、num1[0]+num2[4] - 序列2：
num1[1]+num2[0]、num1[1]+num2[1]、num1[1]+num2[2]、num1[1]+num2[3]、num1[1]+num2[4] - 序列3：
num1[2]+num2[0]、num1[2]+num2[1]、num1[2]+num2[2]、num1[2]+num2[3]、num1[2]+num2[4] - …
- 序列n+1：
num1[n]+num2[0]、num1[n]+num2[1]、num1[n]+num2[2]、num1[n]+num2[3]、num1[n]+num2[4]
解题步骤为：
1、首先将每个队列的首个元素添加到 优先队列中
2、弹出最小值，并将弹出元素的该队列进行后移（类似于指针后移）
3、进行步骤2，直到找到k个元素为止
代码：
class Solution {
public List<List<Integer>> kSmallestPairs(int[] nums1, int[] nums2, int k) {
/**
* 该题可以理解为合并多个有序序列，分别是
* 序列1：num1[0]+num2[0]、num1[0]+num2[1]、num1[0]+num2[2]、num1[0]+num2[3]、num1[0]+num2[4]
* 序列2：num1[1]+num2[0]、num1[1]+num2[1]、num1[1]+num2[2]、num1[1]+num2[3]、num1[1]+num2[4]
* 序列3：num1[2]+num2[0]、num1[2]+num2[1]、num1[2]+num2[2]、num1[2]+num2[3]、num1[2]+num2[4]
* 序列4：num1[3]+num2[0]、num1[3]+num2[1]、num1[3]+num2[2]、num1[3]+num2[3]、num1[3]+num2[4]
* ...
* 序列n+1：num1[n]+num2[0]、num1[n]+num2[1]、num1[n]+num2[2]、num1[n]+num2[3]、num1[n]+num2[4]
*
* 解题步骤为：
* 1、首先将每个队列的首个元素添加到 优先队列中
* 2、弹出最小值，并将弹出元素的该队列进行后移（类似于指针后移）
* 3、进行步骤2，直到找到k个元素为止
*/
List<List<Integer>> res = new ArrayList();
// 优先级队列，保存[idx1, idx2]；其中idx1是num1的下标，idx2是num2的下标
PriorityQueue<int[]> heap = new PriorityQueue<>((a,b) -> ((nums1[a[0]] + nums2[a[1]]) - (nums1[b[0]] + nums2[b[1]])));
// 1、首先将每个队列的首个元素添加到 优先队列中
for(int i=0; i<nums1.length; i++) {
heap.offer(new int[]{
i, 0});
}
// 最多弹出k次
while(k > 0 && !heap.isEmpty()) {
int[] pos = heap.poll();
res.add(Arrays.asList(nums1[pos[0]], nums2[pos[1]]));
// 将idx2 后移
if(pos[1] + 1 < nums2.length) {
pos[1]++;
heap.offer(pos);
}
k--;
}
return res;
}
}
295. 数据流的中位数
分析：
解题思路：
有多种解法，你可以使用插入排序的写法（可以利用前面序列是有序的特性），这种方式我不写了。
接下来说另一种，用一个大根堆 和 一个小跟堆 来实现
- 左边的数据 使用 大根堆
- 右边的数据 使用 小跟堆
其实这个图是有问题的。其实我们不能保证左边和右边的数据是递增有序的。
但是我们要保证：
左侧大根堆的堆顶元素要满足两点：- 大于左侧的所有元素（大根堆性质就是如此，不需要我们来处理）
- 同时小于右侧的所有元素（需要我们自己去维护这个关系）
右侧小根堆的堆顶元素要满足两点：- 小于右侧的所有元素（小根堆性质就是如此，不需要我们来处理）
- 同时大于左侧的所有元素（需要我们自己去维护这个关系）
- 左右两侧数据数量要均衡，我是这样处理的：
- 当整体数量为偶数，
左侧个数=右侧个数 - 当整体数量为奇数，
右侧数量>左侧数量（相差1）
- 当整体数量为偶数，
- 左侧的元素 都比 右侧的元素小（这样一来 大根堆堆顶就是中位数 或者 两个堆顶的平均值是中位数 ）
代码：
class MedianFinder {
// 统计数据流的个数
private int count;
// 维护左侧的大根堆（维护左侧序列）
PriorityQueue<Integer> maxHead = new PriorityQueue(new Comparator<Integer>() {
@Override
public int compare(Integer o1, Integer o2) {
return o2 - o1;
}
});
// 维护右侧的小根堆（维护右侧序列）
PriorityQueue<Integer> minHead = new PriorityQueue();
public MedianFinder() {
}
public void addNum(int num) {
if(count % 2 == 0) {
// 偶数
/**
* 最终添加在右侧序列
* 1、首先将数据添加到左侧的大根堆
* 2、然后将左侧的最大值添加到右侧的小根堆中（最终元素数量增加的是右侧元素）
*/
/**
* 其实1、2 两步可以理解为是一种【过滤操作】，有两个目的：
* 目的1：最终右侧序列新增
* 目的2：最终添加到右侧序列的元素 保证要 大于左侧的所有元素（因此就有了 minHead.offer(maxHead.poll())操作）
*/
maxHead.offer(num);
minHead.offer(maxHead.poll()); // 最终添加在右侧序列
} else {
// 道理同上，只是过滤的方向不一样
minHead.offer(num);
maxHead.offer(minHead.poll()); // 最终添加在左侧序列
}
count++;
}
public double findMedian() {
if(count == 0) {
return 0;
}
return count % 2 == 0 ? (maxHead.peek() + minHead.peek()) / 2.0 : minHead.peek();
}
}
栈
20. 有效的括号
分析：
不算太难哈，直接看代码
代码：
class Solution {
public boolean isValid(String s) {
if(s.isEmpty()) {
return false;
}
Stack<Character> stack = new Stack();
for(char ch: s.toCharArray()) {
if(ch == '(') {
stack.push(')');
} else if (ch == '{') {
stack.push('}');
} else if (ch == '[') {
stack.push(']');
} else if (stack.isEmpty() || ch != stack.pop()) {
return false;
}
}
return stack.isEmpty();
}
}
71. 简化路径
分析：
核心点就是使用栈，模拟..返回上一级目录的操作，如下步骤：
- 使用
path.split("/")函数对原字符串进行分割 - 遍历分割后的数组
- 遇见
..， 则弹栈 - 遇见
.或者""，则不处理 - 其他字符，则压入栈中
- 遇见
- 最后遍历栈，并进行字符串拼接
代码：
class Solution {
public String simplifyPath(String path) {
Stack<String> stack = new Stack();
for(String item: path.split("/")) {
if("..".equals(item)) {
// 遇见 ".." 则弹出上一级目录
if(!stack.isEmpty()) {
stack.pop();
}
} else if (".".equals(item) || "".equals(item)) {
// 遇见"." 或者 "",则不处理
continue;
} else {
// 其他情况都加入到栈中
stack.push(item);
}
}
StringBuilder sb = new StringBuilder("/");
for(String s: stack) {
// 栈的foreach遍历，是和数组一样的，按顺序遍历并非逆序的
sb.append(s + "/");
}
sb.deleteCharAt(sb.length() - 1);
return sb.isEmpty() ? "/" : sb.toString();
}
}
155. 最小栈
分析：
解题步骤：
为了解决要求栈的最小值而且要保证时间复杂度较低的要求，我们需要还需要一个栈区存某一状态下的最小值。因此 这里一共使用两个栈空间，一个栈用于存放普通数据，另一个则用于存放最小值数据
// 该栈就是正常的栈，添加什么数据就压入什么数据
Stack<Integer> normalStack = new Stack();
// 该栈存入的是 相对于normalStack来说 某一状态（状态可以理解为栈的大小）下的最小值（栈顶存最小值）
Stack<Integer> minStack = new Stack();
push方法：
- 首先数据存入到normalStack 中。
- 紧接着该存最小值了。如果minStack是空的，那么直接将插入值压入minStack即可。
- 如果minStack不为空，那么就取出栈顶元素（前个状态的最小值）与插入值进行比较，如果插入值更小就将插入值压入minStack；如果还是前一个状态的最小值更小 就将前个状态的最小值再压入minStack，因为minStack的栈顶元素始终存的都是当前状态的最小值（当前状态可以理解为normalStack当前的深度、大小）
pop方法：
normalStack.pop();
minStack.pop();
两个栈弹出栈顶元素即可（必须都要弹出，要保证minStack与normalStack的状态一致）
top方法：
normalStack.peek();
获取normalStack的栈顶元素即可
min方法：
minStack.peek();
获取minStack的栈顶元素即可
代码：
class MinStack {
// 实际存储数据的栈
Stack<Integer> stack = new Stack();
// 辅助栈，存储当前状态的最小值
Stack<Integer> stack1 = new Stack();
public MinStack() {
}
public void push(int val) {
stack.push(val);
if(stack1.isEmpty()) {
stack1.push(val);
} else {
stack1.push(Math.min(stack1.peek(), val));
}
}
public void pop() {
stack.pop();
stack1.pop();
}
public int top() {
return stack.peek();
}
public int getMin() {
return stack1.peek();
}
}
150. 逆波兰表达式求值
分析：
参考视频：【栈的最后表演！ | LeetCode：150. 逆波兰表达式求值】
- 遇见
+ - * /就从栈中弹出两个数字，进行对应运算 - 然后将运算的结果重新添加到栈中
代码：
class Solution {
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack();
for(String token: tokens) {
if("+".equals(token) || "-".equals(token) || "*".equals(token) || "/".equals(token)) {
int num1 = stack.pop();
int num2 = stack.pop();
if("+".equals(token)) {
stack.push(num2 + num1);
}
if("-".equals(token)) {
stack.push(num2 - num1);
}
if("*".equals(token)) {
stack.push(num2 * num1);
}
if("/".equals(token)) {
stack.push(num2 / num1);
}
} else {
stack.push(Integer.parseInt(token));
}
}
return stack.pop();
}
}
图
dfs
二叉树的dfs：
void dfs(TreeNode root) {
if (root == null) {
return;
}
dfs(root.left);
dfs(root.right);
}
图的dfs：
public void dfs(char[][] grid, int x, int y) {
// 边界条件
if(!inArea(grid, x, y)) {
return;
}
// 其他条件（例如已标记过的，不再处理）
。。。
// 遍历过要加上标记
grid[x][y] = '2';
dfs(grid, x-1, y); // 上
dfs(grid, x+1, y); // 下
dfs(grid, x, y-1); // 左
dfs(grid, x, y+1); // 右
}
public boolean inArea(char[][] grid, int x, int y) {
return x >= 0 && x < grid.length && y >=0 && y < grid[0].length;
}
200. 岛屿数量
分析：
- 遍历所有网格，遇到陆地点，则以该点开始深度优先遍历
- 遍历过的点要打上标记（避免后序重复遍历）
代码：
class Solution {
public int numIslands(char[][] grid) {
int count = 0;
for(int i=0; i<grid.length; i++) {
for(int j=0; j<grid[0].length; j++) {
// 遇到陆地
if(grid[i][j] == '1') {
dfs(grid, i, j);
count++;
}
}
}
return count;
}
public void dfs(char[][] grid, int x, int y) {
// 边界条件
if(!inArea(grid, x, y)) {
return;
}
// 不是岛屿不处理
if(grid[x][y] != '1') {
return;
}
// 遍历过要加上标记
grid[x][y] = '2';
dfs(grid, x-1, y); // 上
dfs(grid, x+1, y); // 下
dfs(grid, x, y-1); // 左
dfs(grid, x, y+1); // 右
}
public boolean inArea(char[][] grid, int x, int y) {
return x >= 0 && x < grid.length && y >=0 && y < grid[0].length;
}
}
463. 岛屿的周长
分析：
参考题解：【「手画图解」463. 岛屿的周长 | 很简单的解法】
核心点就是：
- 从土地到土地，之间不会产生周长
- 从土地迈入海洋，之间会产生 1 个周长
- 从土地迈出矩阵边界，也会产生 1 个周长
代码：
class Solution {
public int islandPerimeter(int[][] grid) {
int count = 0;
for(int i=0; i<grid.length; i++) {
for(int j=0; j<grid[0].length; j++) {
if(grid[i][j] == 1) {
return dfs(grid, i, j);
}
}
}
return 0;
}
/**
* 求周长：
* 1、从陆地到海洋，边长会增加1
*/
public int dfs(int[][] grid, int x, int y) {
// 边界条件（类似于 从陆地到海洋 ）
if(!inArea(grid, x, y)) {
return 1;
}
// 从陆地到海洋
if(grid[x][y] == 0) {
return 1;
}
// 已遍历后的
if(grid[x][y] == 2) {
return 0;
}
// 走到这里，说明当前点为 1，则需要深度优先遍历
// 遍历过要加上标记
grid[x][y] = 2;
return dfs(grid, x-1, y) + dfs(grid, x+1, y) + dfs(grid, x, y-1) + dfs(grid, x, y+1);
}
public boolean inArea(int[][] grid, int x, int y) {
return x >= 0 && x < grid.length && y >=0 && y < grid[0].length;
}
}
130. 被围绕的区域
分析：
参考视频：【【深度优先】——130 被包围的区域】
参考题解：【bfs+递归 dfs+非递归 dfs+并查集】
- 遍历边缘的
O，并进行深度优先遍历，标记连通点为# - 遍历整个网格，原始的
O改成X，#改为O
代码：
class Solution {
public void solve(char[][] board) {
int r = board.length;
int c = board[0].length;
// 从边缘的O开始。标记与外部连通的O，修改为2
for(int i=0; i<r; i++) {
for(int j=0; j<c; j++) {
boolean isEdge = i == 0 || i == r-1 || j == 0 || j == c-1;
if(isEdge && board[i][j] == 'O') {
dfs(board, i, j);
}
}
}
// 重新遍历网格， O->X ， #->O
for(int i=0; i<r; i++) {
for(int j=0; j<c; j++) {
if(board[i][j] == 'O') {
board[i][j] = 'X';
}
if(board[i][j] == '#') {
board[i][j] = 'O';
}
}
}
}
public void dfs(char[][] grid, int x, int y) {
// 边界条件
if(!inArea(grid, x, y)) {
return;
}
// 不是岛屿不处理
if(grid[x][y] != 'O') {
return;
}
// 遍历过要加上标记
grid[x][y] = '#';
dfs(grid, x-1, y); // 上
dfs(grid, x+1, y); // 下
dfs(grid, x, y-1); // 左
dfs(grid, x, y+1); // 右
}
public boolean inArea(char[][] grid, int x, int y) {
return x >= 0 && x < grid.length && y >=0 && y < grid[0].length;
}
}
133. 克隆图
分析：
参考视频：【【LeetCode 每日一题】133. 克隆图 | 手写图解版思路 + 代码讲解】
一共遍历两次：
- 第一次遍历：【拷贝节点】，创建新节点，并将 新节点 和 老节点 的映射关系存储到map中
- 第二次遍历：【拷贝边】，根据map映射关系，拷贝边（即 点 与 点 的指向关系）
和【138. 复制带随机指针的链表】这道题有点相似
代码：
class Solution {
Map<Node, Node> cloneMap = new HashMap();
public Node cloneGraph(Node node) {
// 第一次遍历：【拷贝节点】，创建新节点，并将 新节点 和 老节点 的映射关系存储到map中，
dfs(node);
// 第二次遍历：【拷贝边】，根据map映射关系，拷贝边（即 点 与 点 的指向关系）
for(Map.Entry<Node, Node> entry: cloneMap.entrySet()) {
Node keyNode = entry.getKey();
Node valNode = entry.getValue();
List<Node> cloneNeighbors = new ArrayList();
for(Node item: keyNode.neighbors) {
cloneNeighbors.add(cloneMap.get(item));
}
valNode.neighbors = cloneNeighbors;
}
return cloneMap.get(node);
}
/**
* 深度优先遍历图的所有节点
* 同时创建克隆节点，并将 新节点 和 老节点 的映射关系存储到map中
*/
public void dfs(Node node) {
if(node == null) {
return;
}
// 存入到map中
cloneMap.put(node, new Node(node.val));
// 遍历相邻节点
for(Node item: node.neighbors) {
// 遍历过的就不用再遍历了
if(cloneMap.containsKey(item)) {
continue;
}
// 深度优先
dfs(item);
}
}
}
207. 课程表
分析：
参考视频：【207. 课程表 Course Schedule 【LeetCode 力扣官方题解】】
参考题解：【「图解」拓扑排序 | 课程表问题】
代码：
class Solution {
public boolean canFinish(int numCourses, int[][] prerequisites) {
// 课号和对应的入度
Map<Integer, Integer> inDegreeMap = new HashMap();
for(int i=0; i<numCourses; i++) {
inDegreeMap.put(i, 0);
}
// 依赖关系, 依赖当前课程的后序课程
Map<Integer, List<Integer>> outDegreeCourseMap = new HashMap();
for(int[] arr: prerequisites) {
int prev = arr[1];
int cur = arr[0];
// 更新出度集合列表
if(!outDegreeCourseMap.containsKey(prev)) {
outDegreeCourseMap.put(prev, new ArrayList());
}
outDegreeCourseMap.get(prev).add(cur);
// 更新入度
inDegreeMap.put(cur, inDegreeMap.get(cur) + 1);
}
// BFS，将入度为0（不需要前置课程）的课程放入列表
Queue<Integer> queue = new LinkedList();
for(int key: inDegreeMap.keySet()) {
if(inDegreeMap.get(key) == 0) {
queue.offer(key);
}
}
while(!queue.isEmpty()) {
int cur = queue.poll();
if(!outDegreeCourseMap.containsKey(cur)) {
continue;
}
List<Integer> outDegreeCourse = outDegreeCourseMap.get(cur);
for(int course: outDegreeCourse) {
inDegreeMap.put(course, inDegreeMap.get(course) - 1);
// 入度为0，说该课的前修改已经修完，所以当前课可以修了
if (inDegreeMap.get(course) == 0) {
queue.offer(course);
}
}
}
// 遍历入度, 如果还有课程的入度不为0, 返回fasle
for (int key : inDegreeMap.keySet()) {
if (inDegreeMap.get(key) != 0) {
return false;
}
}
return true;
}
}
210. 课程表 II
分析：
思路和上一题一致
代码：
class Solution {
public int[] findOrder(int numCourses, int[][] prerequisites) {
int[] res = new int[numCourses];
int index = 0;
// 课号和对应的入度
Map<Integer, Integer> inDegreeMap = new HashMap();
for(int i=0; i<numCourses; i++) {
inDegreeMap.put(i, 0);
}
// 依赖关系, 依赖当前课程的后序课程
Map<Integer, List<Integer>> outDegreeCourseMap = new HashMap();
for(int[] arr: prerequisites) {
int prev = arr[1];
int cur = arr[0];
// 更新出度集合列表
if(!outDegreeCourseMap.containsKey(prev)) {
outDegreeCourseMap.put(prev, new ArrayList());
}
outDegreeCourseMap.get(prev).add(cur);
// 更新入度
inDegreeMap.put(cur, inDegreeMap.get(cur) + 1);
}
// BFS，将入度为0（不需要前置课程）的课程放入列表
Queue<Integer> queue = new LinkedList();
for(int key: inDegreeMap.keySet()) {
if(inDegreeMap.get(key) == 0) {
queue.offer(key);
}
}
while(!queue.isEmpty()) {
int cur = queue.poll();
res[index++] = cur;
if(!outDegreeCourseMap.containsKey(cur)) {
continue;
}
List<Integer> outDegreeCourse = outDegreeCourseMap.get(cur);
for(int course: outDegreeCourse) {
inDegreeMap.put(course, inDegreeMap.get(course) - 1);
// 入度为0，说该课的前修改已经修完，所以当前课可以修了
if (inDegreeMap.get(course) == 0) {
queue.offer(course);
}
}
}
// 遍历入度, 如果还有课程的入度不为0, 返回fasle
for (int key : inDegreeMap.keySet()) {
if (inDegreeMap.get(key) != 0) {
return new int[0];
}
}
return res;
}
}
正序
1. 两数之和（难度：简单）
代码：
class Solution {
public int[] twoSum(int[] nums, int target) {
// 初始化map： 【值:下标】
HashMap<Integer, Integer> tempMap = new HashMap();
int[] res = new int[2];
for(int i=0; i<nums.length; i++) {
Integer another = target - nums[i];
// 如果目标值 存在tempMap中，则说明找到了结果
if(tempMap.containsKey(another)) {
res[0] = i;
res[1] = tempMap.get(another);
return res;
}
// 将【值:下标】 存储在map中 (常规套路，在写代码时进入for后 就可以先写这一步)
tempMap.put(nums[i], i);
}
return res;
}
}
总结注意点：
- 空间换时间的思想，将当前值 以及对应下标信息 存储在map中
核心代码：
// 初始化：存储 某个值 以及 在nums中的位置信息
HashMap<Integer, Integer> tempMap = new HashMap();
// 如果目标值 存在tempMap中，则说明找到了结果
if(tempMap.containsKey(another)) {
res[0] = i;
res[1] = tempMap.get(another);
return res;
}
// 主流程：把当前值 及 对应位置信息存入到map中
tempMap.put(nums[i], i);
2. 两数相加（难度：中等）
代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head1 = l1; // 移动指针1，指向链表1
ListNode head2 = l2; // 移动指针2，指向链表2
// 构建结果链表
ListNode resHead = new ListNode();
ListNode temp = resHead;// 移动指针3，指向链表3
// 进位值， 默认是0 （作用域一定要是外面）
int carry = 0;
while(null != head1 || null != head2) {
// 为空取0， 否则取val（核心思想）
int num1 = null==head1 ? 0 : head1.val;
int num2 = null==head2 ? 0 : head2.val;
int sum = num1 + num2 + carry;
// 求模取余 获取当前节点值
int curVal = sum % 10;
// 整除获取进位值
carry = sum / 10;
// 构建当前节点
ListNode curNode = new ListNode(curVal);
// 尾插法
temp.next = curNode; temp = curNode;
// 节点后移，只需要考虑不为null的链表即可，因为为null的话我们默认取0, 不会有影响
if(null != head1)
head1 = head1.next;
if(null != head2)
head2 = head2.next;
}
// 最后节点遍历完后，判断最后一步运算是否进位了，进位则补1，否则不处理
if(carry == 1) {
ListNode lastNode = new ListNode(1);
temp.next = lastNode;
}
return resHead.next;
}
}
总结注意点：
- 常规链表的移动指针，三个移动指针对应三个链表
while(null != head1 || null != head2)循环条件是 || 不是&&（任意一个链表没走完就执行的逻辑）int num1 = null==head1 ? 0 : head1.val当前节点 为null取0，否则取val- 构建进位变量
carry，作用域一定要放到外面；放里面就没法用了 - 考虑最后一步：最后节点遍历完后，判断最后一步运算是否进位了，进位则补1，否则不处理
3. 无重复字符的最长子串（难度：中等）
代码：
class Solution {
public int lengthOfLongestSubstring(String s) {
// 判空处理
if(null == s || s.length() == 0) {
return 0;
}
// 初始化map： 【值:下标】
HashMap<Character, Integer> map = new HashMap();
// 定义滑动窗口最左侧指针
int l = 0;
// 最大长度
int maxLength = 0;
// r可以理解为 滑动窗口最右侧指针
for(int r = 0; r < s.length(); r++) {
char curChar = s.charAt(r);
// 若map中之前存过这个值的下标，则让left指针右移
if(map.containsKey(curChar)) {
// 目的：更新l 为 l、map(curChar)最右侧的下标
// Math.max的好处：我们不需要考虑这个值是否在滑动窗口内
l = Math.max(l, map.get(curChar) + 1);
}
// 更新最大长度
maxLength = Math.max(maxLength, r - l + 1);
// 将【值:下标】 存储在map中 (常规套路，在写代码时进入for后 就可以先写这一步)
map.put(curChar, r);
}
return maxLength;
}
}
解题思路：
该题是一道滑动窗口的问题。
滑动窗口的一般套路：左区间手动改变，有区间for循环累加
B站上视频链接：
https://www.bilibili.com/video/BV1BV411i77g
https://www.bilibili.com/video/BV1w5411E7EP
总结注意点：
- 和第一道题【1. 两数之和】类似点在于，都可以使用 一个map 来记录【值:下标】
- 使用
双指针构建滑动窗口的 经典问题。（套路：左边界手动改变 右边界自动累加） l和r滑动窗口的区间[l,r]表示的就是当前所维护的不重复的字串l = Math.max(l, map.get(curChar) + 1),这里取得是map.get(curChar) + 1，别忘了+1了。如果不+1的话，那么字串可能是abca这种，即第一个字符与后面那个字符重复
4. 寻找两个正序数组的中位数（难度：困难）- 先不做
5. 最长回文子串（难度：中等）
解法一：暴力 - 遍历所有字串
建议先做第9题【9. 回文数】
代码：
class Solution {
public String longestPalindrome(String s) {
String longestPalindrome = "";
// 遍历所有的子串，若长度比longestPalindrome长 且 是回文串，则更新longestPalindrome
for(int i=0; i<s.length(); i++) {
for(int j=i; j<s.length(); j++) {
if(j - i + 1 > longestPalindrome.length()) {
if(isPalindrome(s.substring(i, j+1))) {
longestPalindrome = s.substring(i, j+1);
}
}
}
}
return longestPalindrome;
}
// 判断是否是回文字符串
public Boolean isPalindrome(String s) {
// 双指针
int left = 0;
int right = s.length() - 1;
while (left <= right) {
if(s.charAt(left) != s.charAt(right)) {
return false;
}
left ++;
right --;
}
return true;
}
}
总结注意点：
- 第一步：先写出 判断是否回文 的方法
isPalindrome。 （利用双指针的思想） - 第二步：暴力遍历每个子字符串，判断是否回文，更长的则更新
时间复杂度： n^3
解法二：中心扩展法
代码：
class Solution {
// 维护最长回文字符串
public String res;
public String longestPalindrome(String s) {
// 判空处理
if(null == s && s.length() == 0) {
return "";
}
// 初始化res
res = s.substring(0,1);
// 遍历s字符串
for(int i=0; i<s.length(); i++) {
// 考虑 bab 的格式
extendFromCenter(s, i, i);
// 考虑 baab 的格式
extendFromCenter(s, i, i+1);
}
return res;
}
// 中心扩散
public void extendFromCenter(String s, int left, int right) {
// 当 left、right 在区间返回内，且 s[left] == s[right] 才会向外扩散
while(left>=0 && right<s.length() && s.charAt(left)==s.charAt(right)) {
// 向外扩散
left--;
right++;
}
// 若当前回文串 比 res长 则更新res
if(right - left - 1 > res.length()) {
// 因为最后一次循环 left-- right++了，因此实际上回文字符串是[left+1, right-1]，由于substring是左闭右开[)，因此 res = s.substring(left+1, right)
res = s.substring(left+1, right);
}
}
}
总结注意点：
- 解法一：判断字串是否是回文串，思想是
自外向内的，left ++; right --; - 解法二：寻找属于回文串的字串，且思想是
自内向外扩散的，left--; right++; - 要考虑
bab、baab两种回文串的格式， 因此在遍历到某个字符时，extendFromCenter(s, i, i);extendFromCenter(s, i, i+1);要调两次extendFromCenter
时间复杂度：n^2
7. 整数反转（难度：中等-简单）
代码：
class Solution {
public int reverse(int x) {
// 注意： Math.abs(-2147483648) -> -2147483648 Math.abs(-2147483648L) -> 2147483648
// 因此这里我先把x 转出一个Long 再调用Math.abs
long longNum = Long.parseLong(String.valueOf(x));
Long abs = Math.abs(longNum);
// 取巧调用StringBuilder的reverse方法
StringBuilder reverse = new StringBuilder(Long.toString(abs)).reverse();
Long num = Long.parseLong(reverse.toString());
// 负数 最小是 -2147483648
if (x < 0 && num > 2147483648L) {
return 0;
}
// 正数 最大是 2147483647
if (x > 0 && num > 2147483647L) {
return 0;
}
String strNum = x < 0 ? "-"+num : ""+num;
return Integer.parseInt(strNum);
}
}
总结注意点：
- int类型的范围
-2147483648 <= n <= 2147483647 Math.abs(-2147483648)的结果为： -2147483648Math.abs(-2147483648L)的结果为： 2147483648
9. 回文数（难度：简单）
判断字符串是否为回文字符串？
代码：
class Solution {
public boolean isPalindrome(int x) {
String s = x + "";
int left = 0;
int right = s.length() - 1;
while(left < right) {
if(s.charAt(left) != s.charAt(right)) {
return false;
}
left++;
right--;
}
return true;
}
}
- 先转成字符串，再判断是否为回文字符串
版权声明：本文为博主原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。
智能推荐
Eclipse中配置WebMagic(已配置好Maven)_使用eclipse搭建webmagic工程-程序员宅基地
文章浏览阅读364次。1.WebMagicWebMagic是一个简单灵活的Java爬虫框架。基于WebMagic，你可以快速开发出一个高效、易维护的爬虫。2.在Eclipse中配置WebMagic1.首先需要下载WebMagic的压缩包官网地址为：WebMagic官网最新版本为：WebMagic-0.7.3，找到对应版本，打开下载界面，注意，下载要选择Source code(zip)版本，随便下载到哪里都可以；2.下载好的压缩包需要解压，此时解压到的位置即为后续新建的Eclipse的project位置，比如我的Ecli_使用eclipse搭建webmagic工程
linux启动mysql_linux如何启动mysql服务_linux启动mysql服务命令是什么－系统城-程序员宅基地
文章浏览阅读1.9k次。mysql数据库是一种开放源代码的关系型数据库管理系统，有很多朋友都在使用。一些在linux系统上安装了mysql数据库的朋友，却不知道该如何对mysql数据库进行配置。那么linux该如何启动mysql服务呢？接下来小编就给大家带来linux启动mysql服务的命令教程。具体步骤如下：1、首先，我们需要修改mysql的配置文件，一般文件存放在/etc下面，文件名为my.cnf。2、对于mysql..._linux中 mysql 启动服务命令
php实现在线oj,详解OJ(Online Judge)中PHP代码的提交方法及要点-程序员宅基地
文章浏览阅读537次。详解OJ(Online Judge)中PHP代码的提交方法及要点Introduction of How to submit PHP code to Online Judge SystemsIntroduction of How to commit submission in PHP to Online Judge Systems在目前常用的在线oj中，codeforces、spoj、uva、zoj..._while(fscanf(stdin, "%d %d", $a, $b) == 2)
java快捷键调字体_设置MyEclipse编码、补全快捷键、字体大小-程序员宅基地
文章浏览阅读534次。一、设置MyEclipse编码(1)修改工作空间的编码方式：Window-->Preferences-->General-->Workspace-->Text file encoding(2)修改一类文件的编码方式：Window-->Preferences-->General-->content Types-->修改default Encoding(..._java修改快捷缩写内容
解析蓝牙原理_蓝牙原理图详解-程序员宅基地
文章浏览阅读1.4w次，点赞19次，收藏76次。1.前言市面上关于Android的技术书籍很多，几乎每本书也都会涉及到蓝牙开发，但均是上层应用级别的，而且篇幅也普遍短小。对于手机行业的开发者，要进行蓝牙模块的维护，就必须从Android系统底层，至少框架层开始，了解蓝牙的结构和代码实现原理。这方面的文档、网上的各个论坛的相关资料却少之又少。分析原因，大概因为虽然蓝牙协议是完整的，但是并没有具体的实现。蓝牙芯片公司只负责提供最底层的API_蓝牙原理图详解
从未在一起更让人遗憾_“从未在一起和最终没有在一起哪个更遗憾”-程序员宅基地
文章浏览阅读7.7k次。图/源于网络文/曲尚菇凉1.今天早上出门去逛街，在那家冰雪融城店里等待冰淇淋的时候，听到旁边两个女生在讨论很久之前的一期《奇葩说》。那期节目主持人给的辩论题是“从未在一起和最终没有在一起哪个更遗憾”，旁边其中一个女生说，她记得当时印象最深的是有个女孩子说了这样一句话。她说:“如果我喜欢一个人呢，我就从第一眼到最后一眼，把这个人爱够，把我的感觉用光，我只希望那些年让我成长的人是他，之后的那些年他喝过..._从未在一起更遗憾
随便推点
Spring Cloud Alibaba 介绍_sprngcloud alba-程序员宅基地
文章浏览阅读175次。Spring Cloud Alibaba 介绍Sping体系Spring 以 Bean（对象） 为中心，提供 IOC、AOP 等功能。Spring Boot 以 Application（应用） 为中心，提供自动配置、监控等功能。Spring Cloud 以 Service（服务） 为中心，提供服务的注册与发现、服务的调用与负载均衡等功能。Sping Cloud介绍官方介绍 Tools for building common patterns in distributed systems_sprngcloud alba
测试 数据类型的一些测试点和经验_基础字段的测试点-程序员宅基地
文章浏览阅读3.2k次，点赞4次，收藏21次。我这里是根据之前在测试数据类项目过程中的一些总结经验和掉过个坑，记录一下，可以给其他人做个参考，没什么高深的东西，但是如果不注意这些细节点，后期也许会陷入无尽的扯皮当中。1 需求实现的准确度根据产品需求文档描述发现不明确不详细的或者存在歧义的地方一定要确认，例如数据表中的一些字段，与开发和产品确认一遍，如有第三方相关的，要和第三方确认，数据类项目需要的是细心，哪怕数据库中的一个字段如果没有提前对清楚，后期再重新补充，会投入更大的精力。2 数据的合理性根据业务场景/常识推理，提..._基础字段的测试点
一文看懂：行业分析怎么做？_码工小熊-程序员宅基地
文章浏览阅读491次。大家好，我是爱学习的小xiong熊妹。在工作和面试中，很多小伙伴会遇到“对XX行业进行分析”的要求。一听“行业分析”四个字，好多人会觉得特别高大上，不知道该怎么做。今天给大家一个懒人攻略，小伙伴们可以快速上手哦。一、什么是行业？在做数据分析的时候，“行业”两个字，一般指的是：围绕一个商品，从生产到销售相关的全部企业。以化妆品为例，站在消费者角度，就是简简单单的从商店里买了一支唇膏回去。可站在行业角度，从生产到销售，有相当多的企业在参与工作（如下图）在行业中，每个企业常常扮._码工小熊
LLaMA 简介：一个基础的、650 亿参数的大型语言模型_llma-程序员宅基地
文章浏览阅读1.6w次，点赞2次，收藏2次。还需要做更多的研究来解决大型语言模型中的偏见、有毒评论和幻觉的风险。我们在数万亿个令牌上训练我们的模型，并表明可以仅使用公开可用的数据集来训练最先进的模型，而无需诉诸专有和不可访问的数据集。在大型语言模型空间中训练像 LLaMA 这样的小型基础模型是可取的，因为它需要更少的计算能力和资源来测试新方法、验证他人的工作和探索新的用例。作为 Meta 对开放科学承诺的一部分，今天我们公开发布 LLaMA（大型语言模型元 AI），这是一种最先进的基础大型语言模型，旨在帮助研究人员推进他们在 AI 子领域的工作。_llma
强化学习在制造业领域的应用：智能制造的未来-程序员宅基地
文章浏览阅读223次，点赞3次，收藏5次。1.背景介绍制造业是国家经济发展的重要引擎，其产能和质量对于国家经济的稳定和发展具有重要意义。随着工业技术的不断发展，制造业的生产方式也不断发生变化。传统的制造业通常依赖于人工操作和手工艺，这种方式的缺点是低效率、低产量和不稳定的质量。随着信息化、智能化和网络化等新技术的出现，制造业开始向智能制造迈出了第一步。智能制造的核心是通过大数据、人工智能、计算机视觉等技术，实现制造过程的智能化、自动化...
ansible--安装与使用_pip安装ansible-程序员宅基地
文章浏览阅读938次。系列文章目录文章目录系列文章目录 前言 一、ansible是什么？ 二、使用步骤 1.引入库 2.读入数据 总结前言菜鸟一只，刚开始使用，仅作以后参考使用。边学习，边记录，介绍一下最基础的使用，可能会有理解不到位的地方，可以共同交流，废话不多说，走起。一、ansible 简介？ansible是自动化运维工具的一种，基于Python开发，可以实现批量系统配置，批量程序部署，批量运行命令，ansible是基于模块工作的，它本身没有批量部署的能力，真正.._pip安装ansible