LeetCode刷题总结 - 剑指offer系列 - 持续更新
这篇文章原本和【LeetCode刷题总结 - 面试经典 150 题 -持续更新】是一篇文章，但由于篇幅过大没法更新，所以就拆成了两篇。
其他系列
【LeetCode刷题总结 - 面试经典 150 题 -持续更新】
【LeetCode刷题总结 - LeetCode 热题 100 - 持续更新】
链表
剑指 Offer II 021. 删除链表的倒数第 n 个结点
【剑指 Offer II 021. 删除链表的倒数第 n 个结点】
分析：
- 双指针：
fast、slow（快、慢指针），fast先走n步，然后fast、slow指针同时往前走 - 当
fast指针为null时，其实slow指针对应的节点就是目标节点
代码：
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode fast = head;
ListNode slow = head;
// 快指针提前移动n次
for(int i=0; i<n; i++) {
fast = fast.next;
}
// 边界情况，此时head就是倒数第n个节点
if(fast == null) {
return head.next;
}
// 若fast.next 为null，其实 slow.next 就是目标节点了（可自行画图模拟）
while(fast.next != null) {
fast = fast.next;
slow = slow.next;
}
// 删除slow.next节点
slow.next = slow.next.next;
return head;
}
}
剑指 Offer II 022. 链表中环的入口节点
分析：
可以参考我之前总结的这篇文章，很详细【判断单链表是否有环？以及入环节点】
- 快慢指针，
fast每次走2步，slow每次走1步。若最终两个指针相遇，则必定成环 - 任意一个指针（
fast、slow都可以）回到head位置，然后每次走1步（相同速度）前行，最终会在入口节点相遇（记住思路即可）
代码：
public class Solution {
public ListNode detectCycle(ListNode head) {
if(head == null) {
return null;
}
ListNode fast = head;
ListNode slow = head;
boolean isCycle = false;
// fast要判空两次，fast、fast.next： fast != null && fast.next != null
while(fast != null && fast.next != null && slow != null) {
// 快指针 一次走两步
fast = fast.next.next;
// 慢指针 一次走一步
slow = slow.next;
// 若最终两指针相遇，则一定成环
if(fast == slow) {
isCycle = true;
break;
}
}
if(!isCycle) {
return null;
}
fast = head;
while(slow != fast) {
slow = slow.next;
fast = fast.next;
}
return fast;
}
}
剑指 Offer II 023. 两个链表的第一个重合节点
【剑指 Offer II 023. 两个链表的第一个重合节点】
版本一
import java.util.*;
/**
* 暴力解法
*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
HashSet<ListNode> set = new HashSet();
// 首先遍历第一个链表的所有节点 并将节点存入带set中
while(pHead1 != null) {
set.add(pHead1);
pHead1 = pHead1.next;
}
// 遍历第二个链表 如果出现节点包含在set中 则说明该节点是链表1和链表2的公共节点
while(pHead2 != null) {
if(set.contains(pHead2)) {
return pHead2;
}
pHead2 = pHead2.next;
}
return null;
}
}
心得：
- 暴力可以解决大多数问题
set.contains(xxx)判断set中是否存在xxx这个对象
版本二
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
int size1 = 0; // 记录链表1的长度
int size2 = 0; // 记录链表2的长度
ListNode cur1 = pHead1;
ListNode cur2 = pHead2;
// 算出链表1 的长度
while(cur1 != null) {
size1++;
cur1 = cur1.next;
}
// 算出链表2 的长度
while(cur2 != null) {
size2++;
cur2 = cur2.next;
}
cur1 = pHead1;
cur2 = pHead2;
// 相当于链表1和链表2 在一个等长的链表上 依次后移，如果两指针相同 则一定是第一个相交点
while(cur1 != cur2) {
// 先走链表2 的长度 再遍历链表1
if(size2 != 0) {
size2--;
}else {
cur1 = cur1.next;
}
// 先走链表1 的长度 再遍历链表2
if(size1 != 0) {
size1--;
}else {
cur2 = cur2.next;
}
}
return cur1;
}
}
心得：
- 有时候解题可以换一种思路
版本三
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
// p1 初始指向pHead1
ListNode p1 = pHead1;
// p2 初始指向pJead2
ListNode p2 = pHead2;
// 遍历 p1 和 p2
while(p1 != p2) {
// 若p1走链表1走到头 则开始走链表2
if(p1 == null)
p1 = pHead2;
else // 没走到头就后移
p1 = p1.next;
// p2 同上
if(p2 == null)
p2 = pHead1;
else
p2 = p2.next;
}
// 最终p1肯定等于p2， 因为他俩要么都是公共点，要么都为null
return p1;
}
}
剑指 Offer II 024. 反转链表（基础模板题）
分析：
- 双指针，前指针-
pre，当前指针-cur - 局部翻转实现整体翻转
代码：
public class Solution {
public ListNode ReverseList(ListNode head) {
ListNode pre = null; // 前一个节点
ListNode cur = head; // 当前节点 （该引用初始指向head头结点）
while(cur != null) {
// 1、创建一个新引用指向当前节点的下个节点
ListNode next = cur.next;
// 2、当前节点指向上个节点（局部反转）
cur.next = pre;
// 3、cur和pre指针后移（先移pre 后移cur，顺序不能反）
pre = cur;
cur = next;
}
return pre;
}
}
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;
}
}
剑指 Offer II 025. 链表中的两数相加
分析：
- 和上一题一样，只是这里链表的顺序和上题正好相反
- 这里使用
栈和头插法来处理
代码：
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
Stack<Integer> satck1 = new Stack();
Stack<Integer> satck2 = new Stack();
ListNode head = new ListNode();
while(l1 != null) {
satck1.push(l1.val);
l1 = l1.next;
}
while(l2 != null) {
satck2.push(l2.val);
l2 = l2.next;
}
int carry = 0;
while(!satck1.isEmpty() || !satck2.isEmpty()) {
int num1 = satck1.isEmpty() ? 0 : satck1.pop();
int num2 = satck2.isEmpty() ? 0 : satck2.pop();
int sum = num1 + num2 + carry;
carry = sum / 10;
int val = sum % 10;
// 头插法
ListNode newNode = new ListNode(val);
newNode.next = head.next;
head.next = newNode;
}
if(carry == 1) {
ListNode newNode = new ListNode(1);
newNode.next = head.next;
head.next = newNode;
}
return head.next;
}
}
876. 链表的中间结点（基础模板题）
分析：
快慢指针，fast一次走两步，slow一次走一步
代码：
class Solution {
public ListNode middleNode(ListNode head) {
// 快慢指针
ListNode fast = head;
ListNode slow = head;
while(fast != null && fast.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
}
思考：
当链表节点为偶数，以[1,2,3,4,5,6]为例
上述代码我们返回的节点其实就是4（下半段的第一个节点），如果我们想返回3（上半段的最后一个节点），那我们该怎么写呢？
在while循环中，我们可这样判断fast.next != null && fast.next.next != null
while(fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
剑指 Offer II 026. 重排链表
分析：
链表的中间结点+反转链表+合并链表，三合一
代码：
class Solution {
public void reorderList(ListNode head) {
// 获取中间节点
ListNode mid = middleNode(head);
ListNode list1 = head;
ListNode list2 = mid.next;
// 原链表从中间截断，分成两段
mid.next = null;
// 反转链表后半段
list2 = reverse(list2);
// 合并
mergeListNode(list1, list2);
}
/**
* 链表反转
*/
public ListNode reverse(ListNode head) {
ListNode pre = null;
ListNode cur = head;
while(cur != null) {
ListNode nextNode = cur.next;
cur.next = pre;
pre = cur;
cur = nextNode;
}
return pre;
}
/**
* 获取中间节点
* 当节点为偶数个时，返回第一段的最后一个节点（这里判断是：fast.next != null && fast.next.next != null）
*/
public ListNode middleNode(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while(fast.next != null && fast.next.next != null) {
slow = slow.next;
fast = fast.next.next;
}
return slow;
}
/**
* 合并链表 list1 + list2 交叉合并
*/
public void mergeListNode(ListNode list1, ListNode list2) {
ListNode p1 = list1;
ListNode p2 = list2;
while(p1 != null && p2 != null) {
// 1、临时节点记录 next节点
ListNode tempNext1 = p1.next;
ListNode tempNext2 = p2.next;
// 2、调整指针指向关系
p1.next = p2;
p2.next = tempNext1;
// 3、两个指针后移
p1 = tempNext1;
p2 = tempNext2;
}
}
}
剑指 Offer II 028. 展平多级双向链表
分析：
参考视频：【leetcode-链表篇 430题 扁平化多级双向链表】
递归 + 模拟
直接看代码注释吧
代码：
class Solution {
public Node flatten(Node head) {
dfs(head);
return head;
}
/**
* 返回 当前层的最后一个节点
*/
public Node dfs(Node node) {
// 若为空 则直接返回null
if(node == null) {
return null;
}
// 记录该链表的最后一个节点， 默认是当前节点
Node last = node;
Node cur = node;
while (cur != null) {
/**
* child 不为null，需要做两步：
* 1、【下层最后节点】 与 【当前层下一个节点】相连
* 2、【当前层当前节点】 与 【下层第一个节点（即它的孩子节点）】相连
*/
if(cur.child != null) {
// 【当前层下一个节点】
Node nextNode = cur.next;
// 递归调用获取【下层最后节点】
Node lastNode = dfs(cur.child);
/**
* 【下层最后节点】 与 【当前层下一个节点】相连
*/
if(nextNode != null) {
nextNode.prev = lastNode;
}
lastNode.next = nextNode;
/**
* 【当前层当前节点】 与 【下层第一个节点（即它的孩子节点）】相连
*/
cur.child.prev = cur;
cur.next = cur.child;
cur.child = null;
}
// 更新last
last = cur;
// cur后移
cur = cur.next;
}
return last;
}
}
剑指 Offer II 029. 排序的循环链表
分析：
官网讲解：https://leetcode.cn/problems/4ueAj6/solution/pai-xu-de-xun-huan-lian-biao-by-leetcode-f566/
- 遍历环形链表，初始值
next = next.head，然后while(next != head)进行遍历处理（包括next后移操作），当next == head时则表明已经遍历一圈了 - 因为要满足一定条件，插入
两个节点之间，因此我们需要双指针，cur（当前节点）、next（下一节点） - 特殊情况：
- 循环链表为空，则直接新建节点，自己指向自己
- 循环链表大小为1，则直接插入即可
- 三种情况可以插入：
cur.val <= 新节点值 <= next.valcur.val > next.val（此时cur、next分别为最大节点 和 最小节点），新值 >= 最大值cur.val > next.val（此时cur、next分别为最大节点 和 最小节点），新值 <= 最小值
代码：
class Solution {
public Node insert(Node head, int insertVal) {
// 特殊情况一：链表为空，则直接创建节点，自己指向自己
if(head == null) {
head = new Node(insertVal);
head.next = head;
return head;
}
// 特殊情况二：链表大小为1，则直接插入
if(head.next == head) {
Node newNode = new Node(insertVal);
head.next = newNode;
newNode.next = head;
return head;
}
// 遍历环形链表
Node cur = head;
Node next = head.next;
// 当next == head相同时，说明已经遍历一圈了
while(next != head) {
// 情况一：cur.val <= 新节点值 <= next.val，则说明找到了目标位置
if(cur.val <= insertVal && insertVal <= next.val) {
break;
}
// 情况二：来到了 最小节点 与 最大节点之间：此时cur为最大值节点；next为最小值节点
// 易错点：不能写成 ur.val >= next.val（cur.val == next.val 并不能说明cur、next分别是 最大、最小值）
if(cur.val > next.val) {
/**
* 这时候，有两种情况都是可插入的
* 1：新值 >= 最大值
* 2：新增 <= 最小值
*/
if(insertVal >= cur.val || insertVal <= next.val) {
break;
}
}
// 双指针后移
cur = cur.next;
next = next.next;
}
// 插入新节点
Node newNode = new Node(insertVal);
cur.next = newNode;
newNode.next = next;
return head;
}
}
树
剑指 Offer II 043. 往完全二叉树添加节点
分析：
审题：其实初始化是给定的原始树就是完全二叉树
CBTInserter：
需要两个队列：queue用来层次遍历完全二叉树，candidate用来存储候选者（完全二叉树可插入的节点）
- 层次遍历完全二叉树
- 然后将
左孩子为空或者右孩子为空的节点，加入到候选者队列中
insert：
- 弹出最前面的候选者
- 添加到该候选者身上（先判断左孩子，若左孩子 和 右孩子 都已经添加完则需要把该候选者从
candidate中移除） - 最后将新节点也加入到
candidate中
get_root：
- 直接弹出根节点即可
代码：
class CBTInserter {
// 记录树的根节点
TreeNode root;
// 完成二叉树，可插入的候选者队列
Queue<TreeNode> candidate = new LinkedList();
public CBTInserter(TreeNode root) {
this.root = root;
// 层次遍历需要的队列
Queue<TreeNode> queue = new LinkedList();
queue.offer(root);
// 遍历给定的初始树
while(!queue.isEmpty()) {
// 层次遍历的套路
TreeNode node = queue.poll();
if(node.left != null) {
queue.offer(node.left);
}
if(node.right != null) {
queue.offer(node.right);
}
// 判断是否应该放到候选者队列中，存在节点为空 即可加入候选队列中
if(node.left == null || node.right == null) {
candidate.offer(node);
}
}
}
public int insert(int v) {
TreeNode newNode = new TreeNode(v);
TreeNode node = candidate.peek();
if(node.left == null) { // 左孩子位置为空，则先插入左孩子
node.left = newNode;
} else {
node.right = newNode;
// 此时左、右孩子都已填充，则直接从候选者列表中删除
candidate.poll();
}
candidate.offer(newNode);
return node.val;
}
public TreeNode get_root() {
return this.root;
}
}
剑指 Offer 32 - II. 从上到下打印二叉树 II（基础模板题）
【剑指 Offer 32 - II. 从上到下打印二叉树 II】
代码：
public class Solution {
// 层次遍历（广度优先）
ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
// 用于存放结果集
ArrayList<ArrayList<Integer>> res = new ArrayList();
// 套路模板
if(pRoot == null) return res;
// 1、 先创建一个队列
Queue<TreeNode> queue = new LinkedList();
// 2、 将头节点放入队列中
queue.offer(pRoot);
// 3、 一直遍历队列 知道队列为空
while(!queue.isEmpty()) {
// 3.1 先获取当前队列的大小，即当前层有多少节点
int length = queue.size();
ArrayList<Integer> curList = new ArrayList();
// 3.2 将当前层的所有节点的值 都放进当前结合中
for(int i=0; i<length; i++) {
TreeNode head = queue.poll(); // 获取队列头节点 并让该节点出队列
curList.add(head.val); // 将该节点的值 放入集合中
// 广度优先的套路 如果存在左右孩子节点 则将他们放入队列中
if(head.left != null) queue.add(head.left);
if(head.right != null) queue.add(head.right);
}
// 走出for循环则说明 当前层已经遍历完 然后将当前集合放入到结果集中
res.add(curList);
}
// 走出while循环则说明 队列中已经没有节点 二叉树已经遍历结束
return res;
}
}
剑指 Offer II 044. 二叉树每层的最大值
分析：
在层次遍历的基础上，判断每次的最大值
代码：
class Solution {
public List<Integer> largestValues(TreeNode root) {
if(root == null) {
return new ArrayList();
}
List<Integer> ret = new ArrayList();
Queue<TreeNode> queue = new LinkedList();
queue.offer(root);
// 层次遍历该树
while(!queue.isEmpty()) {
int length = queue.size();
int min = Integer.MIN_VALUE;
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);
}
// 更新最小值
min = Math.max(node.val, min);
}
ret.add(min);
}
return ret;
}
}
剑指 Offer II 045. 二叉树最底层最左边的值
【剑指 Offer II 045. 二叉树最底层最左边的值】
分析：
也是层次遍历，不过遍历的顺序要变一下，要从右往左遍历。最后一个节点就是最底层 最左边
先添加右孩子，再添加左孩子
代码：
class Solution {
public int findBottomLeftValue(TreeNode root) {
int ret = 0;
Queue<TreeNode> queue = new LinkedList();
queue.offer(root);
// 层次遍历，从右往左
while(!queue.isEmpty()) {
TreeNode node = queue.poll();
// 先遍历右孩子
if(node.right != null) {
queue.offer(node.right);
}
// 再遍历左孩子
if(node.left != null) {
queue.offer(node.left);
}
ret = node.val;
}
return ret;
}
}
剑指 Offer II 046. 二叉树的右侧视图
分析：
也可以用层次遍历来处理，分层遍历，将最后一个节点保留
好爽，还是层次遍历的题，可见层次遍历的模板那么重要，(#.#)
代码：
class Solution {
public List<Integer> rightSideView(TreeNode root) {
List<Integer> ret = new ArrayList();
if(root == null) {
return new ArrayList();
}
Queue<TreeNode> queue = new LinkedList();
queue.offer(root);
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) {
ret.add(node.val);
}
}
}
return ret;
}
}
剑指 Offer II 047. 二叉树剪枝
分析：
- 该题需要用到左、右孩子的结果，很明显要用
后序遍历（向上回溯） - 剪枝的过程就是重构二叉树的过程
- 剪枝的动作就是
return null，相当于剪掉这个节点(剪枝条件就是 左、右子树都被剪掉了，并且当前值为0)
其实后序遍历整个过程就是从低向上的回溯，剪枝的过程其实是从底往上剪的（重要）
代码：
class Solution {
public TreeNode pruneTree(TreeNode root) {
if(root == null) {
return null;
}
// 重构左子树
root.left = pruneTree(root.left);
// 重构右子树
root.right = pruneTree(root.right);
// 若左右孩子都为null，并且当前值为0，则该节点就可以被剪掉了
if(root.left == null && root.right == null && root.val == 0) {
// 这里返回null，就可以理解为剪枝，因为回溯后会被父节点设置给左孩子或者右孩子
return null;
}
return root;
}
}
剑指 Offer II 049. 从根节点到叶节点的路径数字之和
【剑指 Offer II 049. 从根节点到叶节点的路径数字之和】
分析：
- 两个成员变量：
sum（存储累加和） 、globalValue（记录遍历到某个节点时，根节点到当前节点所表示的数字） - 回溯后记得要清除掉当前值对globalValue的影响
代码：
class Solution {
// 存储累加和
int sum = 0;
// 记录遍历到某个节点时，根节点到当前节点所表示的数字
int globalValue = 0;
public int sumNumbers(TreeNode root) {
dfs(root);
return sum;
}
public void dfs(TreeNode root) {
if(root == null) {
return;
}
// 先根据当前值更新全局value
globalValue = globalValue * 10 + root.val;
// 到达叶子节点时，则累加 当前 globalValue
if(root.left == null && root.right == null) {
sum += globalValue;
}
dfs(root.left);
dfs(root.right);
// 回溯到上父节点之前，要清除掉当前值对globalValue的影响
globalValue /= 10;
}
}
剑指 Offer II 050. 向下的路径节点之和
分析：
- 这次“路径”的定义，不一定是从根节点到叶子节点（因此我们要遍历整棵树的每个节点，再以该节点为根调用dfs深度优先，并且目标条件不再判断是否为叶子节点）
- 这次节点值 可以是负数、0、正数（因此我们再找到某条路径后，不能return，还要再往深入走，因为节点值可能为负数）
解题步骤：
- 遍历该树的每个节点
- 以每个节点为根，分别调用深度搜索目标路径，找到目标路径并累加到计数器
代码：
class Solution {
int ret = 0;
public int pathSum(TreeNode root, int targetSum) {
// 遍历二叉树
dfs(root, targetSum);
return ret;
}
/**
* 仅仅是遍历二叉树
*/
public void dfs(TreeNode root, long targetSum) {
if(root == null) {
return;
}
getPath(root, targetSum);
if(root.left != null) {
dfs(root.left, targetSum);
}
if(root.right != null) {
dfs(root.right, targetSum);
}
}
/**
* 找到以root为根，target为目标的路径
*/
public void getPath(TreeNode root, long target) {
if(root == null) {
return;
}
target -= root.val;
// 找到目标点则更新ret
if(target == 0) {
ret++;
}
// 因为节点可能为负数，所以即使上面找到了，也需要向下找
getPath(root.left, target);
getPath(root.right, target);
}
}
滑动窗口
滑动窗口题的特征：
- 连续子数组、连续子串
- 最大、最小（限定词）
结题步骤：
- 初始化窗口左边界为0，或者 右边界为0（根据题意分析）
- 初始化一个
ret的返回值，默认值为0或者 最大值Integer.MAX_VALUE或者 最小值Integer.MIN_VALUE（根据题意分析） - 窗口大小根据题意进行调整
- 最大连续：尽量扩张右边界，直到不满足题意条件再收缩左边界
- 最小连续：尽量收缩左边界，直到不满足题意条件再扩张右边界
- 在执行3操作的过程中，不断与ret进行比较
- 最终返回ret结果即可
剑指 Offer II 008. 和大于等于 target 的最短子数组
【剑指 Offer II 008. 和大于等于 target 的最短子数组】
分析：
滑动窗口：最小连续，尽量扩展左边界，不满足再扩展右边界
代码：
for循环 - 右边界递增：
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0;
int ret = Integer.MAX_VALUE;
int sum = 0;
// for循环递增右边界，模拟扩张右边界
for(int right=0; right<nums.length; right++) {
sum += nums[right];
// 满足限定条件，并尽量收缩左边界
while(sum >= target) {
sum -= nums[left];
// 同时更新ret
ret = Math.min(ret, right - left + 1);
// 左边界收缩
left++;
}
}
// 若 ret == Integer.MAX_VALUE，则返回0
return ret == Integer.MAX_VALUE ? 0 : ret;
}
}
while循环 - 右边界递增：
class Solution {
public int minSubArrayLen(int target, int[] nums) {
int left = 0;
int right = 0;
int ret = Integer.MAX_VALUE;
int sum = 0;
while(right < nums.length) {
sum += nums[right];
while(sum >= target) {
sum -= nums[left];
ret = Math.min(ret, right - left + 1);
left++;
}
right++;
}
return ret == Integer.MAX_VALUE ? 0 : ret;
}
}
以上两种写法都是一样的（同一个意思），看自己的习惯
剑指 Offer 48. 最长不含重复字符的子字符串
分析：
滑动窗口：最大连续，尽量扩展右边界，不满足再收缩做边界
代码：
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s.length() == 0) {
return 0;
}
// 依赖字符对应下标
Map<Character, Integer> charMap = new HashMap();
// 初始值为最小值0
int ret = 0;
int left = 0;
for(int right=0; right<s.length(); right++) {
char cur = s.charAt(right);
// 满足条件
if(!charMap.containsKey(cur)) {
// 满足条件扩张右边界，这里right在for循环会自增，因此我们不必做处理
} else {
// 取这两个值的最大值 也即是最右边的下标 若map中的下标不在滑动窗口范围内left是不变的，这里使用max函数是很巧妙的
left = Math.max(charMap.get(cur) + 1, left);
}
charMap.put(cur, right);
ret = Math.max(ret, right - left + 1);
}
return ret;
}
}
字符串
剑指 Offer 20. 表示数值的字符串
分析：
- 对一些公共方法进行封装，例如：
判断是否数字字符?、判断是否只包含数字字符？ - 根据题目要求进行分类封装，对
【整数】、【小数】、【数值】进行封装
把基础的方法封装好，最终根据条件组装起来，逻辑就很清晰了
代码：
class Solution {
/**
* 【数值】
*/
public boolean isNumber(String s) {
// 去除 头尾字符串
s = s.trim();
if (s.length() == 0) {
return false;
}
// 若是 以 e 或者 E 开头则直接为false
if (s.startsWith("e") || s.endsWith("e")) {
return false;
}
if (s.contains("e") || s.contains("E")) {
s = s.toLowerCase();
String[] strArr = s.split("e");
if (strArr.length != 2) {
return false;
}
// 小数 或者 整数 -> isDecimal(strArr[0]) || isInteger(strArr[0])
// 整数 -> isInteger(strArr[1])
return (isDecimal(strArr[0]) || isInteger(strArr[0])) && isInteger(strArr[1]);
} else {
return isDecimal(s) || isInteger(s);
}
}
/**
* 【整数】
*/
public boolean isInteger(String s) {
if (s.length() == 0) {
return false;
}
char firstChar = s.charAt(0);
if (firstChar == '+' || firstChar == '-') {
String lastStr = s.substring(1);
return onlyNumChar(lastStr);
} else {
return onlyNumChar(s);
}
}
/**
* 【小数】
*/
public boolean isDecimal(String s) {
if (s.length() == 0) {
return false;
}
char firstChar = s.charAt(0);
if (firstChar == '+' || firstChar == '-') {
String lastStr = s.substring(1);
return isOnlyDecimal(lastStr);
} else {
return isOnlyDecimal(s);
}
}
/**
* 【纯小数 不包含 正负号】
*/
public boolean isOnlyDecimal(String s) {
if (s.length() == 0) {
return false;
}
if (s.charAt(s.length() - 1) == '.') {
// 1、 至少一位数字，后面跟着一个点 '.'
String lastStr = s.substring(0, s.length() - 1);
return onlyNumChar(lastStr);
} else if (s.charAt(0) == '.') {
// 2、一个点 '.' ，后面跟着至少一位数字
String lastStr = s.substring(1);
return onlyNumChar(lastStr);
} else {
// 3、至少一位数字，后面跟着一个点 '.' ，后面再跟着至少一位数字
if (!s.contains(".")) {
return false;
}
// 因为split参数是 正则表达是，因此 . 必须转义 "\\."
String[] strArr = s.split("\\.");
if (strArr.length != 2) {
return false;
}
return onlyNumChar(strArr[0]) && onlyNumChar(strArr[1]);
}
}
/**
* 是否只包含数字字符？
*/
public boolean onlyNumChar(String s) {
if (s.length() == 0) {
return false;
}
char[] chars = s.toCharArray();
for (char c : chars) {
// 非数字字符 则直接false
if (!isNumChar(c)) {
return false;
}
}
return true;
}
/**
* 判断字符是否是数字字符
*/
public boolean isNumChar(char c) {
if (c >= '0' && c <= '9') {
return true;
} else {
return false;
}
}
}
剑指 Offer 67. 把字符串转换成整数
分析
判断字符是否是数字：
/**
* 判断字符是否是数字字符
*/
public boolean isNumChar(char c) {
if (c >= '0' && c <= '9') {
return true;
} else {
return false;
}
}
转换方式：
// 这里必须是long，不然res会超出范围
long res = 0;
for (int i = 0; i < str.length(); i++) {
char curChar = str.charAt(i);
res = res * 10 + (curChar - '0');
}
超出范围处理 [-2147483648, 2147483647]：
关键代码(long) Integer.MAX_VALUE + 1，必须强转 否则会变成负数
// 超出范围直接返回，这里一定 用long强转，不然则会超出范围 Integer.MAX_VALUE + 1 = -2147483648
if (!isPlus && (res >= (long) Integer.MAX_VALUE + 1)) {
return Integer.MIN_VALUE;
} else if (res > Integer.MAX_VALUE) {
return Integer.MAX_VALUE;
}
字符串转数字（不包括正负号）：
/**
* 字符串转数字
* @param str：待转的字符串（不包含正负号）
* @param isPlus：是否是 正数
* @return
*/
public int strToNum(String str, boolean isPlus) {
if (str.length() == 0) {
return 0;
}
// 若第一个字符不为数字，则不转换，返回0
if (!isNumChar(str.charAt(0))) {
return 0;
}
// 开始处理 字符串 -> 数字
long res = 0;
for (int i = 0; i < str.length(); i++) {
char curChar = str.charAt(i);
// 遇到非数字字符 则直接break
if (!isNumChar(curChar)) {
break;
}
// 转换方式， res初始为0
res = res * 10 + (curChar - '0');
// 超出范围直接返回，这里一定 用long强转，不然则会超出范围 Integer.MAX_VALUE + 1 = -2147483648
if (!isPlus && (res >= (long) Integer.MAX_VALUE + 1)) {
return Integer.MIN_VALUE;
} else if (res > Integer.MAX_VALUE) {
return Integer.MAX_VALUE;
}
}
// 若不是正数，则最终 res = -1 * res
res = !isPlus ? -1 * res : res;
return (int) res;
}
代码
class Solution {
public int strToInt(String str) {
// 去除空格
str = str.trim();
if (str.length() == 0) {
return 0;
}
if (str.charAt(0) == '-') {
return strToNum(str.substring(1), false);
} else if (str.charAt(0) == '+') {
return strToNum(str.substring(1), true);
} else {
return strToNum(str, true);
}
}
/**
* 字符串转数字
* @param str：待转的字符串（不包含正负号）
* @param isPlus：是否是 正数
* @return
*/
public int strToNum(String str, boolean isPlus) {
if (str.length() == 0) {
return 0;
}
// 若第一个字符不为数字，则不转换，返回0
if (!isNumChar(str.charAt(0))) {
return 0;
}
// 开始处理 字符串 -> 数字
long res = 0;
for (int i = 0; i < str.length(); i++) {
char curChar = str.charAt(i);
// 遇到非数字字符 则直接break
if (!isNumChar(curChar)) {
break;
}
// 转换方式， res初始为0
res = res * 10 + (curChar - '0');
// 超出范围直接返回，这里一定 用long强转，不然则会超出范围 Integer.MAX_VALUE + 1 = -2147483648
if (!isPlus && (res >= (long) Integer.MAX_VALUE + 1)) {
return Integer.MIN_VALUE;
} else if (res > Integer.MAX_VALUE) {
return Integer.MAX_VALUE;
}
}
// 若不是正数，则最终 res = -1 * res
res = !isPlus ? -1 * res : res;
return (int) res;
}
/**
* 判断字符是否是数字字符
*/
public boolean isNumChar(char c) {
if (c >= '0' && c <= '9') {
return true;
} else {
return false;
}
}
}
双指针
剑指 Offer 18. 删除链表的节点
分析：
- 双指针，需要
prev指向前一个节点
代码：
class Solution {
public ListNode deleteNode(ListNode head, int val) {
// 上一节点指针
ListNode prev = new ListNode();
prev.next = head;
ListNode cur = head;
while (cur != null) {
if(cur.val == val) {
prev.next = cur.next;
}
prev = cur;
cur = cur.next;
}
if(head.val == val) {
return head.next;
} else {
return head;
}
}
}
剑指 Offer 52. 两个链表的第一个公共节点
版本一
import java.util.*;
/**
* 暴力解法
*/
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
HashSet<ListNode> set = new HashSet();
// 首先遍历第一个链表的所有节点 并将节点存入带set中
while(pHead1 != null) {
set.add(pHead1);
pHead1 = pHead1.next;
}
// 遍历第二个链表 如果出现节点包含在set中 则说明该节点是链表1和链表2的公共节点
while(pHead2 != null) {
if(set.contains(pHead2)) {
return pHead2;
}
pHead2 = pHead2.next;
}
return null;
}
}
心得：
- 暴力可以解决大多数问题
set.contains(xxx)判断set中是否存在xxx这个对象
版本二
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
int size1 = 0; // 记录链表1的长度
int size2 = 0; // 记录链表2的长度
ListNode cur1 = pHead1;
ListNode cur2 = pHead2;
// 算出链表1 的长度
while(cur1 != null) {
size1++;
cur1 = cur1.next;
}
// 算出链表2 的长度
while(cur2 != null) {
size2++;
cur2 = cur2.next;
}
cur1 = pHead1;
cur2 = pHead2;
// 相当于链表1和链表2 在一个等长的链表上 依次后移，如果两指针相同 则一定是第一个相交点
while(cur1 != cur2) {
// 先走链表2 的长度 再遍历链表1
if(size2 != 0) {
size2--;
}else {
cur1 = cur1.next;
}
// 先走链表1 的长度 再遍历链表2
if(size1 != 0) {
size1--;
}else {
cur2 = cur2.next;
}
}
return cur1;
}
}
心得：
- 有时候解题可以换一种思路
版本三
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
// p1 初始指向pHead1
ListNode p1 = pHead1;
// p2 初始指向pJead2
ListNode p2 = pHead2;
// 遍历 p1 和 p2
while(p1 != p2) {
// 若p1走链表1走到头 则开始走链表2
if(p1 == null)
p1 = pHead2;
else // 没走到头就后移
p1 = p1.next;
// p2 同上
if(p2 == null)
p2 = pHead1;
else
p2 = p2.next;
}
// 最终p1肯定等于p2， 因为他俩要么都是公共点，要么都为null
return p1;
}
}
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
【剑指 Offer 21. 调整数组顺序使奇数位于偶数前面】
解题思路：
- 使用双指针法。左指针找到一个偶数；右指针找到一个奇数。
- 最后交换奇数和偶数的位置。
- 最后左右指针向中间移动
代码实现：
import java.util.*;
public class Solution {
/**
* 该题用的是双指针，有快速排序、字符串反转的类似
*/
public int[] reOrderArrayTwo (int[] arr) {
int left = 0;
int right = arr.length-1;
while(left < right) {
// 左指针右移 直到找到一个 偶数 便会跳出while
while(left<right && (arr[left]&1) == 1) // (arr[l]&1)==1用来判断是否为奇数,注意arr[l]外面要加括号
left++;
// 右指针左移 直到找到一个 奇数 便会跳出while
while(left<right && (arr[right]&1) == 0)
right--;
// 最后偶数与奇数交换位置
int temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
// 最后左右指针向中间移动
left++; right--;
}
return arr;
}
}
- 对于数组或者list返回空的情况 ，最好是return new int[0] 或者 new ArrayList();
- 对于双指针 left、right问题，究竟是left<right还是left<=right要考虑当left==right所表示的含义
- n >> 1是表示除以2， n & 1 == 0 是判断是否为偶数，别记错了
剑指 Offer 57. 和为s的两个数字
分析：
B站上视频讲解：https://www.bilibili.com/video/BV1J741157eS
- 左右双指针。左指针-l初始为0位置，右指针-r初始为length-1。
- while(l<r)循环。 若和大于sum则右指针左移；若和小于sum则左指针右移。
代码：
class Solution {
public int[] twoSum(int[] nums, int target) {
int[] res = new int[2];
if(nums.length < 2) {
return res;
}
int left = 0;
int right = nums.length - 1;
while(left < right) {
int sum = nums[left] + nums[right];
if(sum < target) {
// 小于的情况 左指针右移 让和变大
left++;
} else if (sum > target) {
// 大于的情况 右指针左移 让和变小
right--;
} else {
// 若找到匹配的 则将这俩数放到集合中 然后break
res[0] = nums[left];
res[1] = nums[right];
return res;
}
}
return res;
}
}
剑指 Offer II 007. 数组中和为 0 的三个数
【剑指 Offer II 007. 数组中和为 0 的三个数】
分析：
- 先排序
- 通过枚举
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);
for(int i=0; i<nums.length; i++) {
// 若当前值与上一个相同，则没必要再重新搞一遍了，否则会重复
if(i > 0 && nums[i] == nums[i-1]) {
continue;
}
int target = -nums[i];
int left = i+1;
int right = nums.length-1;
while(left < right) {
int sum = nums[left] + nums[right];
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--;
}
}
if(sum < target) {
left++;
} else if ( sum > target) {
right--;
}
}
}
return res;
}
}
剑指 Offer 58 - I. 翻转单词顺序
分析：
- 根据空格对字符串进行分割
- 使用双指针，左、右单词进行交换位置
- 最终拼接单词
代码：
class Solution {
public String reverseWords(String s) {
s = s.trim();
if(s.length() == 0) {
return s;
}
// 使用空格分割多个单词，正则“( )+” 表示任意空格
String[] strArr = s.split("( )+");
if(strArr.length == 0) {
return s;
}
int left = 0;
int right = strArr.length-1;
while(left < right) {
// 交换单词的位置
String temp = strArr[left];
strArr[left] = strArr[right];
strArr[right] = temp;
left++;
right--;
}
// 最终拼接字符串
StringBuilder sb = new StringBuilder();
for(String str: strArr) {
sb.append(str + " ");
}
return sb.toString().trim();
}
}
剑指 Offer 49. 丑数
分析：
该题使用 三指针 法来求解
丑数从小到大排列顺序为：1,2,3,4,5,6,8,9,10…
丑数有个特点：任意一个丑数都是由小于它的某一个丑数*2，3或者5得到的
那我们便可 使用三个指针 来模拟 三个队列，分别 *2、*3、*5（指针指向丑数有序队列中的某个值）
下图模拟 6轮过程，其中 p2、p3、p5指的都是下标
初始状态：
第一轮：
第二轮：
第三轮：
第四轮：
第五轮：
第六轮：
代码：
class Solution {
public int nthUglyNumber(int n) {
// 这三个数表示数组下标 ，表示下个乘2、乘3、乘5的位置
int p2 = 0;
int p3 = 0;
int p5 = 0;
// 创建一个数组 大小为n，用于存放前n个丑数
int[] ugly = new int[n];
// 第一个丑数是1
ugly[0] = 1;
// 按从小到大的顺序生成后面的丑数
for(int i=1; i<n; i++) {
int n2 = ugly[p2] * 2;
int n3 = ugly[p3] * 3;
int n5 = ugly[p5] * 5;
// 取最小值 因为要求存入到数组中的丑数是有序的
int minValue = Math.min(n5, Math.min(n2, n3));
ugly[i] = minValue;
// 只要 最小值 与 对应指针x2、x3、x5的值相等 则指针后移（若n2 ==n3 == 6,其实p2、p3都会后移，其实就有了去重的效果）
if(minValue == n2) p2++;
if(minValue == n3) p3++;
if(minValue == n5) p5++;
}
return ugly[n-1];
}
}
剑指 Offer II 009. 乘积小于 K 的子数组
【剑指 Offer II 009. 乘积小于 K 的子数组】
分析：
连续子数组，乍一看以为可以用滑动窗口模板来求解呢，但是该题中并没有提到 “最大连续” 或者 “最小连续”，因此我们并不能用那个模板套路求解
换一种思路，一般涉及到子数组，我们都可以利用以x结尾的子数组进行分组求解，
例如数组[1,2,4,6]，我们便可分成 四类:
以1结尾[1]
以2结尾[1,2]、[2]
以4结尾[1,2,4]、[2,4]、[4]
以6结尾[1,2,4,6]、[2,4,6]、[4,6]、[6]
规律点：若数组[2,4,6] 的乘积 < k，则以6结尾的子数组[6]、[4,6]、[2,4,6] （一共3个子数组）都满足 < k。这样以x结尾的子数组，满足 < k的就有 right - left + 1 个（right：右窗口，left：左窗口）
代码：
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
int sum = 0;
int prod = 1;
int left = 0;
// for循环 遍历 right， 模拟以x结尾进行分类
for(int right=0; right<nums.length; right++) {
prod *= nums[right];
// 不满足条件，则缩小数组长度，left++
while(left <= right && prod >= k) {
prod /= nums[left];
left++;
}
// 直到满足条件，再累加结果
sum += (right - left + 1);
}
return sum;
}
}
栈与队列
剑指 Offer 59 - II. 队列的最大值
分析：
借鉴bilibili视频讲解：【小美算法 剑指Offer 59题II 队列的最大值 java版本】
- 新增一个辅助队列，维护最大值，辅助队列头节点，就是最大值
- 辅助队列特点：双端队列、单调递增
- 新增元素时，移除掉 辅助队列中比自己小的值，最终插入到辅助队列队尾
为什么在新增元素时要 “移除掉 辅助队列中比自己小的值，最终插入到辅助队列队尾”呢？
这里我们可以类比一个场景：“篮球队长模型”。高中篮球队需要选队长，假设是根据身高选的，目前队长候选列表是
可以想一下，当前有个新生来了，身高2.00米，比高一、高二的两位学长都要高
问题一：那么这两位学长还有机会吗？
肯定没有了，因为 高二、高一的两位学长会比新生早毕业（更早出队列），因此这两个学长就没必要留在候选者中了（从队列中移除）
问题二：可以撼动队长地位吗？
因为当前队长身高 2.10米，新生身高2.00米，队长比新生高（2.00 < 2.10），因此新生不能撼动队长的地位（比自己大的节点不移除）
但是新生以后是有机会当队长的，因为队长是高三的，所以会比新生早毕业（早出队列），等队长毕业了，新生就有可能当选新队长了（因此新生加入候选者队列）
新生加入队列后的候选者队列为：
代码：
class MaxQueue {
Queue<Integer> queue;
// 双端队列维护最大值，单调递减
Deque<Integer> deque;
public MaxQueue() {
queue = new LinkedList();
deque = new LinkedList();
}
public int max_value() {
if(deque.isEmpty()) {
return -1;
}
// 返回队列头部元素，递增序列 头部最大
return deque.peekFirst();
}
public void push_back(int value) {
queue.offer(value);
// 移除掉队列中比自己小的值（篮球队长模型）
while(!deque.isEmpty() && deque.peekLast() < value) {
deque.pollLast();
}
// 最后添加到队尾
deque.addLast(value);
}
public int pop_front() {
if(queue.isEmpty()) {
return -1;
}
// 若队头元素 就是 最大队列的头部，则移除掉 最大队列头部
if(queue.peek().equals(deque.peek())) {
deque.poll();
}
// 最终调用队列的poll
return queue.poll();
}
}
剑指 Offer 59 - I. 滑动窗口的最大值
分析：
其实思路和上一题是一致的，可以在上一题的基础上进行处理
- 没达到滑动窗口大小时（大小为
K），不需要移除头部元素，直接添加尾部元素（调用push_back） - 达到滑动窗口大小时，存储当前队列最大值（
max_value） - 达到滑动窗口大小后，需要先移除头部元素（
pop_front），再添加尾部元素（push_back），然后存储当前队列最大值（max_value）
代码：
class Solution {
// 存储实际的值
Queue<Integer> queue;
// 双端队列维护最大值，单调递减
Deque<Integer> deque;
public void init() {
queue = new LinkedList();
deque = new LinkedList();
}
public int max_value() {
if(deque.isEmpty()) {
return -1;
}
// 返回队列头部元素，递增序列 头部最大
return deque.peekFirst();
}
public void push_back(int value) {
queue.offer(value);
// 移除掉队列中比自己小的值（篮球队长模型）
while(!deque.isEmpty() && deque.peekLast() < value) {
deque.pollLast();
}
// 最后添加到队尾
deque.addLast(value);
}
public int pop_front() {
if(queue.isEmpty()) {
return -1;
}
// 若队头元素 就是 最大队列的头部，则移除掉 最大队列头部
if(queue.peek().equals(deque.peek())) {
deque.poll();
}
// 最终调用队列的poll
return queue.poll();
}
public int[] maxSlidingWindow(int[] nums, int k) {
// 存储结果
int[] res = new int[nums.length - k + 1];
init();
// 没达到滑动窗口大小时（大小为K），不需要移除最前面元素
for(int i=0; i<k; i++) {
push_back(nums[i]);
}
int index = 0;
res[index++] = max_value();
for(int i=k; i<nums.length; i++) {
pop_front();
push_back(nums[i]);
res[index++] = max_value();
}
return res;
}
}
模拟
剑指 Offer 29. 顺时针打印矩阵
分析：
参考bilibili视频：【LeetCode力扣刷题 | 剑指Offer 29. 顺时针打印矩阵】
代码：
class Solution {
public int[] spiralOrder(int[][] matrix) {
if (matrix == null || matrix.length == 0) {
return new int[0];
}
int[] res = new int[matrix.length * matrix[0].length];
int index = 0;
int top = 0;
int bottom = matrix.length - 1;
int left = 0;
int right = matrix[0].length - 1;
while (true) {
// 打印最上边的
for (int i = left; i <= right; i++) {
res[index++] = matrix[top][i];
}
top++;
if (top > bottom) {
break;
}
// 打印最右边的
for (int i = top; i <= bottom; i++) {
res[index++] = matrix[i][right];
}
right--;
if (right < left) {
break;
}
// 打印最下边的
for (int i = right; i >= left; i--) {
res[index++] = matrix[bottom][i];
}
bottom++;
if (bottom > top) {
break;
}
// 打印最左边的
for (int i = bottom; i >= top; i--) {
res[index++] = matrix[i][left];
}
left++;
if (left > right) {
break;
}
}
return res;
}
}
剑指 Offer 31. 栈的压入、弹出序列
分析：
- 构造一个辅助栈来模拟 压栈 和 弹栈 的过程
- 若最终辅助栈是空的，则说明是对的，否则就是错的
代码：
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
// 辅助栈
Stack<Integer> stack = new Stack();
// 指向 popped的下标
int popIndex = 0;
// 开始模拟
for(int i=0; i<pushed.length; i++) {
// 模拟压栈
stack.push(pushed[i]);
// 模拟弹栈 -> 如果栈顶 跟popped[popIndex]相同 则弹栈
while(!stack.isEmpty() && popped[popIndex] == stack.peek()) {
stack.pop();
popIndex++;
}
}
return stack.isEmpty();
}
}
搜索与回溯算法
剑指 Offer 12. 矩阵中的路径
分析：
深度优先遍历+剪枝- 其实这题 也可以使用
int[][] visited来标记某个坐标是否被访问过？（与下题相似）但是有没必要浪费空间，因为本身char[][] board就能达到相同的效果
参考题解：https://leetcode.cn/problems/ju-zhen-zhong-de-lu-jing-lcof/solution/mian-shi-ti-12-ju-zhen-zhong-de-lu-jing-shen-du-yo/
参考视频：【LeetCode力扣刷题 | 剑指Offer 12. 矩阵中的路径】
代码：
class Solution {
// 结果集
private List<String> res = new ArrayList();
// 某一条路径
private StringBuilder path = new StringBuilder();
private char[] charArr;
public boolean exist(char[][] board, String word) {
charArr = word.toCharArray();
for(int i=0; i<board.length; i++) {
for(int j=0; j<board[0].length; j++) {
backtracking(board, i, j, 0);
if(!res.isEmpty()) {
return true;
}
}
}
return false;
}
// 回溯
public void backtracking(char[][] board, int i, int j, int idx) {
if(!res.isEmpty()) { // 存在一个解，就没必要再找了
return;
}
if(path.length() == charArr.length) { // 找到正确解
res.add(path.toString());
return;
}
if(!inArea(board, i, j)) { // 不在范围内
return;
}
if('#' == board[i][j]) { // 已用过，已遍历过
return;
}
if(charArr[idx] != board[i][j]) { // 与目标字符不同
return;
}
path.append(board[i][j]);
board[i][j] = '#'; // 用'#'标记为已访问
backtracking(board, i + 1, j, idx + 1); // 上
backtracking(board, i - 1, j, idx + 1); // 下
backtracking(board, i, j - 1, idx + 1); // 左
backtracking(board, i, j + 1, idx + 1); // 右
// 重置状态
board[i][j] = charArr[idx];
path.deleteCharAt(path.length() - 1);
}
// 判断是否在有效范围内？
public boolean inArea(char[][] board, int x, int y) {
return x >= 0 && x < board.length && y >= 0 && y < board[0].length;
}
}
剑指 Offer 13. 机器人的运动范围
分析：
- 与上一题不太一样，仔细思考差异点
- 对于公共的变量，为了编码方便，我们可以抽出局部变量
- 这题求得是能到达的点之和，因此不能重复计算（不需要还原标记）
代码：
class Solution {
// 用来记录是否被访问过
private boolean[][] visited;
// 计数
private int count = 0;
public int movingCount(int m, int n, int k) {
visited = new boolean[m][n];
dfs(0, 0, m, n, k);
return count;
}
public void dfs(int x, int y, int m, int n, int k) {
if(x<0 || x>=m || y<0 || y>=n || getSum(x,y)>k || visited[x][y]) {
return;
}
count++;
visited[x][y] = true;
dfs(x, y-1, m, n, k); // 左
dfs(x+1, y, m, n, k); // 下
dfs(x, y+1, m, n, k); // 右
dfs(x-1, y, m, n, k); // 上
// 这里我没不必要 更新visited[x][y]，因为我们统计的是达到格子的总数，是相加的关系，因此不能让重复相加
}
/**
* 求坐标的位数之和
*/
public int getSum(int x, int y) {
int xSum = 0;
int ySum = 0;
while(x != 0) {
xSum += x % 10;
x /= 10;
}
while(y != 0) {
ySum += y % 10;
y /= 10;
}
return xSum + ySum;
}
}
JZ82 二叉树中和为某一值的路径(一)
分析：
常规题
代码：
public class Solution {
/**
*
* @param root TreeNode类
* @param sum int整型
* @return bool布尔型
*/
public boolean hasPathSum (TreeNode root, int sum) {
// 套路
if (root == null) return false;
// dfs 深度优先搜索
return dfs(root, sum);
}
public boolean dfs(TreeNode root, int num) {
// 深度优先 先判空套路
if (root == null) return false;
// 正常情况下的代码逻辑（找寻 符合条件的目标）
// 遇到一个节点 num就减节点对应的值 直到 num为0
num -= root.val;
// 条件:1、要是叶子节点(左右孩子为null) 2、num减到了0
if (root.left == null && root.right == null && num == 0) {
return true;
}
// 左右子树 有一棵找到 即为找到
return dfs(root.left, num) || dfs(root.right, num);
}
}
剑指 Offer 34. 二叉树中和为某一值的路径(二)
分析：
- 对于公共的变量，为了编码方便，我们可以抽出局部变量
- 遍历完一个节点（左、右孩子、当前节点 都遍历完了），最终一定要移除掉当前节点。目的：为了不影响其他路径
代码：
class Solution {
// 路径集合
private List<List<Integer>> res = new ArrayList();
// 单个路径
private List<Integer> path = new ArrayList();
public List<List<Integer>> pathSum(TreeNode root, int target) {
if(root == null) {
return new ArrayList();
}
dfs(root, target);
return res;
}
public void dfs(TreeNode root, int target) {
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));
// 这里没必要return ，因为此处已经是叶子节点了，左、右子节点都是null，而且最终一定要走到path.remove(path.size()-1)代码，如果直接return 反而走不到
}
dfs(root.left, target);
dfs(root.right, target);
// 遍历完一定要移除最后一个节点
path.remove(path.size()-1);
}
}
LCR 050. 路径总和 III
分析：
与上面两题不同的几点：
- 这次“路径”的定义，不一定是从根节点到叶子节点（因此我们要遍历整棵树的每个节点，再以该节点为根调用dfs深度优先，并且目标条件不再判断是否为叶子节点）
- 这次节点值 可以是负数、0、正数（因此我们再找到某条路径后，不能return，还要再往深入走，因为节点值可能为负数）
解题步骤：
- 遍历该树的每个节点
- 以每个节点为根，分别调用dfs深度搜索，找到目标路径并累加到计数器
代码：
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* public TreeNode(int val) {
* this.val = val;
* }
* }
*/
public class Solution {
int count = 0; // 计数器，记录路径总数
// 遍历该树的每个节点，再调用dfs（这一步主要是遍历的作用）
public int FindPath (TreeNode root, int sum) {
// 套路
if(root == null) return count;
// 执行当前节点的逻辑 这里是 dfs(root,sum);
dfs(root,sum);
// 递归遍历 该节点的左右子树
FindPath(root.left, sum);
FindPath(root.right, sum);
// 最终返回计数器 count
return count;
}
// 深度遍历 统计路径条数
void dfs(TreeNode root, int sum) {
// 套路模板 先判空
if(root == null) return;
// 执行当前节点的正常逻辑，这里是：sum-=val，以及找寻目标 sum==0
sum -= root.val;
if(sum == 0) // 这里与前面的题不同的是 不用判断 左右节点为null 因为路径定义不一定非是叶子节点
count++; // 这里为什么不return呢？ 因为节点可以为负数，继续往深处走，可能还满足
// 递归深度搜索左右孩子
dfs(root.left, sum);
dfs(root.right, sum);
}
}
心得：
- 一般先遍历每个节点再将每个节点看做树根操作的，都可以使用两个递归配合操作。先遍历树， 再对每个节点分别操作。
剑指 Offer 54. 二叉搜索树的第k大节点
分析：
- 对于二叉搜索树，中序遍历最终是有序的
代码：
class Solution {
private List<Integer> res = new ArrayList();
public int kthLargest(TreeNode root, int k) {
dfs(root, k);
return res.get(k-1);
}
public void dfs(TreeNode root, int k) {
if(root == null) {
return;
}
// 若res的大小是k，则不用再遍历了
if(res.size() == k) {
return;
}
// 中序遍历搜索树，最终是有序序列
dfs(root.right, k);
res.add(root.val);
dfs(root.left, k);
}
}
剑指 Offer 55 - I. 二叉树的深度
分析：
- 每遍历一层就
+1，代码体现Math.max(dfs(root.left), dfs(root.right)) + 1
代码：
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) {
return 0;
}
return dfs(root);
}
public int dfs(TreeNode root) {
if(root == null) {
return 0;
}
return Math.max(dfs(root.left), dfs(root.right)) + 1;
}
}
剑指 Offer 55 - II. 平衡二叉树
分析：
在求 “二叉树的深度”的基础上进阶的，要熟练掌握求二叉树深度的递归代码
代码：
public class Solution {
public boolean IsBalanced_Solution(TreeNode root) {
if(root == null) {
return true;
}
if(TreeDepth(root) == -1) {
return false;
}
return true;
}
/**
* 返回树的深度 顺带判断是否平衡 如果不平衡则返回-1
* 以 求树深度那个算法 为模板 要熟练掌握求树的深度的算法
*/
public int TreeDepth(TreeNode root) {
// 模板套路：如果节点为空 返回深度0
if(root == null) return 0;
// 递归获取左右子树深度
int leftDepth = TreeDepth(root.left);
// 若子树已经是不平衡的 则没必要再判断了 直接返回-1即可
if(leftDepth == -1)
return -1;
int rightDepth = TreeDepth(root.right);
if(rightDepth == -1)
return -1;
// 如果左右子树深度差的绝对值大于1 则说明树不平衡
// 若不平衡就返回-1 若平衡则返回对应的深度
return Math.abs(leftDepth - rightDepth) > 1 ? -1 : Math.max(leftDepth,rightDepth)+1;
}
}
剑指 Offer 64. 求1+2+…+n
分析：
正常写法：
class Solution {
// 累加和
int sum = 0;
public int sumNums(int n) {
// 遍历 1 - n，累加sum
for(int i=1; i<=n; i++) {
sum += i;
}
return sum;
}
}
但题中要求，不能使用for，因为我们会想到使用回溯来代替for循环
回溯写法：
class Solution {
// 累加和
int sum = 0;
public int sumNums(int n) {
dfs(n);
return sum;
}
public void dfs(int n) {
// 递归边界
if(n > 1) {
// 代替for循环
dfs(n - 1);
}
sum += n;
}
}
但题中说明不能使用if判断，于是我们想到使用&&短路与来代替if操作
class Solution {
// 累加和
int sum = 0;
public int sumNums(int n) {
dfs(n);
return sum;
}
public boolean dfs(int n) {
// 短路与特性： 只有 满足 n > 1 才会执行dfs(n -1)
boolean flag = n > 1 && dfs(n -1);
sum += n;
return true;
}
}
- 这里因为不能用
for因此用的是递归的方式； - 因为不能用
if，因此用的是&&来做短路：只有前面第一个逻辑成立才会执行后面的逻辑代码。
代码：
class Solution {
private int sum = 0;
public int sumNums(int n) {
dfs(n);
return sum;
}
public boolean dfs(int n) {
sum += n;
// 其实这里的flag是无用的，只是为了充当一个布尔值变量，保证后面的 && 左右的代码执行
// 这里只有 n > 0 满足后才会执行后面的递归代码 ， 因为 && 也叫做短路运算法
// 效果类似于 if(n > 0) dfs(n - 1)
boolean flag = n > 0 && dfs(n - 1);
// 其实这个返回值 true也是没有意义的
return true;
}
}
剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
【剑指 Offer 68 - I. 二叉搜索树的最近公共祖先】
分析：
- 二叉搜索树是有序的，可以遍历二叉树查找目标节点（类似于二分查找）
- 目标节点：第一个分叉点
代码：
class Solution {
private TreeNode res;
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) {
return null;
}
dfs(root, p, q);
return res;
}
public void dfs(TreeNode root, TreeNode p, TreeNode q) {
if(root == null) {
return;
}
// 如果已经找到结果了就不必要在搜索了
if(res != null) {
return;
}
if(p.val < root.val && q.val < root.val) {
// 都在root的左侧
dfs(root.left, p, q);
} else if(p.val > root.val && q.val > root.val) {
// 都在root的右侧
dfs(root.right, p, q);
} else {
res = root;
}
}
}
剑指 Offer 68 - II. 二叉树的最近公共祖先
【剑指 Offer 68 - II. 二叉树的最近公共祖先】
分析：
参考视频：【二叉树的最近公共祖先【基础算法精讲 12】】
参考视频：【代码随想录自底向上查找，有点难度！ | LeetCode：236. 二叉树的最近公共祖先】
代码：
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) {
if(root == null || 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;
}
// 左边有结果，则返回左边
if(left != null) {
return left;
}
// 右边有结果，则返回右边
if(right != null) {
return right;
}
// 都没结果返回null
return null;
}
}
剑指 Offer 38. 字符串的排列
分析：
该题没有强调说字符串中的字符不重复，因此字符串中的字符可能是重复的（所以我们要考虑去重）
那么该题与【LCR 084. 全排列 II】几乎是一毛一样的
属于 典型的 有可重复元素的全排列问题
参考视频：【代码随想录：回溯算法求解全排列，如何去重？| LeetCode：47.全排列 II】
去重逻辑参考：【代码随想录：回溯算法中的去重，树层去重树枝去重，你弄清楚了没？| LeetCode:40.组合总和II】
代码：
class Solution {
List<String> res = new ArrayList();
List<Character> path = new ArrayList();
public String[] permutation(String s) {
char[] charArr = s.toCharArray();
// 排序，方便为后面去重
Arrays.sort(charArr);
int[] used = new int[charArr.length];
backtracking(charArr, used);
return res.toArray(new String[res.size()]);
}
public void backtracking(char[] arr, int[] used) {
// 终止条件
if(path.size() == arr.length) {
res.add(charList2String(path));
return;
}
// 遍历子节点
for(int i=0; i<arr.length; i++) {
/**
* 树层去重操作， 当前前元素 与 前一个元素相同，且前一个元素未使用过
* 树层去重：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;
}
// 路径中的元素不能重复使用
if(used[i] == 1) {
continue;
}
path.add(arr[i]);
used[i] = 1;
backtracking(arr, used);
used[i] = 0;
path.remove(path.size() - 1);
}
}
// 字符集合转字符串
private String charList2String(List<Character> path) {
StringBuilder sb = new StringBuilder();
for(int i=0; i<path.size(); i++) {
sb.append(path.get(i));
}
return sb.toString();
}
}
分治算法
剑指 Offer 07. 重建二叉树
分析：
1. 特殊情况处理
2. 构建 根节点
3. 算出根节点在 vin数组中的下标位置
4. 构建左子树
5. 构建右子树
代码：
class Solution {
// 存储中序遍历 对应值的下标
private HashMap<Integer, Integer> idxMap = new HashMap();
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder.length == 0) {
return null;
}
// 初始化idxMap
for(int i=0; i<inorder.length; i++) {
idxMap.put(inorder[i], i);
}
return build(preorder, 0, preorder.length-1, inorder, 0, inorder.length-1);
}
public TreeNode build(int[] preorder, int left1, int right1, int[] inorder, int left2, int right2) {
if(left1>right1 || left2>right2) {
return null;
}
// 构建根节点
int rootVal = preorder[left1];
TreeNode root = new TreeNode(rootVal);
// 获取 中序遍历 中 根节点的坐标
int idx = idxMap.get(rootVal);
int leftTreeSize = idx - left2; // 左子树大小
int rightTreeSize = right2 - idx; // 右子树大小
// 构建左孩子节点
root.left = build(preorder, left1+1, left1+leftTreeSize, inorder, left2, left2+leftTreeSize-1);
// 构建右孩子节点
root.right = build(preorder, left1+leftTreeSize+1, right1, inorder, idx+1, right2);
return root;
}
}
剑指 Offer 16. 数值的整数次方
分析：
快速幂：
以 2^10 为例
pow(2, 10) = pow(2, 5) * pow(2, 5)
pow(2, 5) = pow(2, 4) * 2
pow(2, 4) = pow(2, 2) * pow(2, 2)
pow(2, 2) = pow(2, 1) * pow(2, 1)
pow(2, 1) = 2
B站上视频讲解：https://www.bilibili.com/video/BV1hP4y1b7R4
我的代码和该视频讲解的有些不同，但思想是一样的
代码：
public class Solution {
public double myPow(double base, int exponent) {
if(exponent == 0) return 1; // 为0 返回1
if(exponent == 1) return base; // 为1 时就是递归出口 返回base 例如2^1 = 2
if(exponent == -1) return 1 / base; // 当exponent为-1时，直接 1 / base 即可
if((exponent&1) == 0){ // 判断偶数 相当于 exponent%2 == 0
// 相当于 myPow(base,exponent/2) * myPow(base,exponent/2) 进而实现“二分降幂”
return myPow(base*base, exponent/2);
}else { // exponent为奇数
return myPow(base, exponent-1) * base;
}
}
}
剑指 Offer 33. 二叉搜索树的后序遍历序列
分析：
解题分析：
- 首先该树是一棵
二叉搜索树（二叉排序树）：该树的节点要满足左子树的所有节点都小于根节点，右子树的所有节点都大于根节点 - 后序遍历：后序遍历的后的数组可分为三部分，第一部分是左子树部分，第二部分是右子树部分，而最后一个节点是根节点
那么我们来结合上述两点，得出的结论是：若数组是二叉搜索树的后序遍历序列，那么一定满足可分为三部分，第一部分都小于根节点，第二部分都大于根节点，若不满足上述条件，则不满足，return false
咱们代码的实现方式是，通过一个指针i，从根节点-1开始 往前移动。第一部分的节点值都大于根节点；第二部应该都小于根节点，第二部分若存在大于根节点的情况 则返回false
代码：
public class Solution {
public boolean verifyPostorder(int [] sequence) {
if(sequence.length == 0) return true;
return verify(sequence, 0, sequence.length-1);
}
// 对一个范围的数组 判断手否满足二叉排序树
public boolean verify(int[] sequence, int l, int r) {
// 如果l>=r 则说明整个全部遍历完了 并且满足条件
if(l >= r) return true;
// 后序遍历最右边的元素是 根节点元素
int root = sequence[r];
// i从r-1开始向前移动
int i = r-1;
// 第一部分属于根节点的右子树 根节点
while(i>=l && sequence[i]>=root) {
i--; // i指针前移
}
// 获取到中间的分解点
int nextIndex = i;
// 第二部分若满足是二叉排序树 那么左子树的节点肯定都小于root 若出现大于根节点的情况 那么肯定不符合
while(i>=l) {
if(sequence[i] > root) return false;
i--; // i指针前移
}
// 递归调用左右子树区间。只有左右子树都满足 才 是真正满足 因此这里 && 连接
return verify(sequence, l, nextIndex) && verify(sequence, nextIndex+1, r-1);
}
}
剑指 Offer 17. 打印从1到最大的n位数
分析：
这题比较简单，遍历打印即可
代码：
class Solution {
public int[] printNumbers(int n) {
int max = 1;
while(n > 0) {
max *= 10;
n--;
}
int[] res = new int[max-1];
for(int i=1; i<max; i++) {
res[i-1] = i;
}
return res;
}
}
排序
剑指 Offer 45. 把数组排成最小的数
分析：
代码实现：
- 将int数组转换成字符串数组
- 对字符串数组进行排序，自定义排序，实现Comparator类实现compare方法，return (s1+s2).compareTo(s2+s1)
- 最后对字符串数组进行拼接
代码：
public class Solution {
public String minNumber(int [] numbers) {
// 判空处理
if(numbers == null || numbers.length == 0)
return "";
int len = numbers.length;
String[] nums = new String[len];
// 将 int数组 转换为 字符串数组
for(int i=0; i<len; i++) {
nums[i] = numbers[i] + "";
}
// 对字符串数组进行 自定义排序
Arrays.sort(nums, new Comparator<String>() {
// 自定义排序 （关键）
public int compare(String s1, String s2) {
return (s1+s2).compareTo(s2+s1);
}
});
// 最后拼接字符串数组
StringBuilder str = new StringBuilder();
for(String item: nums) {
str.append(item);
}
return str.toString();
}
}
剑指 Offer 61. 扑克牌中的顺子
分析：
模拟、排序、技巧
看的Krahets的题解：
https://leetcode.cn/problems/bu-ke-pai-zhong-de-shun-zi-lcof/solution/mian-shi-ti-61-bu-ke-pai-zhong-de-shun-zi-ji-he-se/
代码：
class Solution {
public boolean isStraight(int[] nums) {
int joker = 0;
Arrays.sort(nums); // 数组排序
for(int i = 0; i < 4; i++) {
if(nums[i] == 0) joker++; // 统计大小王数量
else if(nums[i] == nums[i + 1]) return false; // 若有重复，提前返回 false
}
return nums[4] - nums[joker] < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
}
}
剑指 Offer 40. 最小的k个数
分析：
利用快速排序的思想，不断的构造轴点元素，当轴点坐标为K时，那么arr的topK就是最小的前K个数
可以参考：【排序算法之快速排序】
代码：
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
int pivotIdx = pivotIndex(arr, 0, arr.length-1);
quickSort(arr, 0, arr.length-1, k);
// 最终只返回前k项
return Arrays.copyOfRange(arr, 0, k);
}
public void quickSort(int[] arr,int left, int right, int k) {
if(left >= right) {
return;
}
int pivotIdx = pivotIndex(arr, left, right);
if(pivotIdx == k) {
// pivotIdx == k，此刻前面的数就是TopK
return;
} else if (pivotIdx > k) {
// 如果pivotIdx > k,递归划分pivotIdx左面的数组，右面无需划分
quickSort(arr, left, pivotIdx-1, k);
} else {
// 如果pivotIdx < k，递归划分pivotIdx右面的数组，左面无需划分
quickSort(arr, pivotIdx+1, right, k);
}
}
// 构建轴点元素，获取其坐标
public int pivotIndex(int[] arr, int left, int right) {
int pivot = arr[left];
while(left < right) {
while(left < right && arr[right] >= pivot) {
right--;
}
if(left < right) {
arr[left] = arr[right];
left++;
}
while(left < right && arr[left] <= pivot) {
left++;
}
if(left < right) {
arr[right] = arr[left];
right--;
}
if(left == right) {
arr[left] = pivot;
}
}
return left;
}
}
215. 数组中的第K个最大元素
分析：
与上一题思路一样
代码：
class Solution {
public int findKthLargest(int[] nums, int k) {
// 因为是第k大，所以最终该值的下标为 k-1
quickSort(nums, 0, nums.length-1, k-1);
return nums[k-1];
}
public void quickSort(int[] nums, int left, int right, int k) {
if(left >= right) {
return;
}
int povitIdx = povitIndex(nums, left, right);
if(povitIdx == k) {
return;
}
if(povitIdx < k) {
quickSort(nums, povitIdx+1, right, k);
} else {
quickSort(nums, left, povitIdx-1, k);
}
}
public int povitIndex(int[] nums, int left, int right) {
int povit = nums[left];
while(left < right) {
while(left < right && nums[right] <= povit) {
right--;
}
if(left < right) {
nums[left] = nums[right];
left++;
}
while(left < right && nums[left] >= povit) {
left++;
}
if(left < right) {
nums[right] = nums[left];
right--;
}
if(left == right) {
nums[left] = povit;
}
}
return left;
}
}
动态规划
剑指 Offer 63. 股票的最大利润
分析：
目标：在最低值买入，在最高点卖出，则会得到最大收益
- 遍历prices，模拟每天
买入股票（当前值 < 历史最小值） 或者卖出股票（当前值 > 历史最小值） - 当模拟卖出股票时，若
当前值-最小值>历史最大利益，则更新历史最大利益
代码：
class Solution {
public int maxProfit(int[] prices) {
// 最大利润初始值
int maxprofit = 0;
// 股票价格最低值
int minPrice = Integer.MAX_VALUE;
for(int i=0; i<prices.length; i++) {
int curPrice = prices[i];
// 若 当前值 小于 历史最低值， 则更新最低值（模拟买入股票）
if(curPrice < minPrice) {
minPrice = curPrice;
} else {
// 当前值 大于 历史最低值，则curPrice - minPrice（模拟卖出股票）
if((curPrice - minPrice) > maxprofit) {
// 若收益 大于 历史最大利益 则更新maxprofit
maxprofit = curPrice - minPrice;
}
}
}
return maxprofit;
}
}
剑指 Offer 42. 连续子数组的最大和
分析：
技巧：像这种最大、最小 的 子数组、子序列，我们在定义动态数组时，大多数这样定义：dp[i] = 以下标i 值为结尾的 子数组 或者 子序列
- 遍历
nums，填写dp数组 dp[i]以nums[i]结尾；若dp[i-1] < 0，则没必要加上dp[i-1]了（因为加上去则会使dp[i]更小），dp[i] = nums[i]；否则dp[i] = nums[i] + dp[i-1]
代码：
class Solution {
public int maxSubArray(int[] nums) {
if(nums.length == 0) {
return 0;
}
// dp定义: 表示以 i下标值 结尾的子数组的和
int[] dp = new int[nums.length];
dp[0] = nums[0];
int maxSubArrayValue = dp[0];
for(int i=1; i<nums.length; i++) {
// 若dp[i-1] 为负数，则以i结尾的子数组就没必要加上前面的了（因为加上去，只会让数组和更小）
if(dp[i-1] < 0) {
dp[i] = nums[i];
} else {
dp[i] = dp[i-1] + nums[i];
}
// 若dp[i] 大于 最大值，则更新最大值
if(dp[i] > maxSubArrayValue) {
maxSubArrayValue = dp[i];
}
}
return maxSubArrayValue;
}
}
JZ85 连续子数组的最大和(二)
分析：
与上题相比，该题让我们返回的是最大和对应的数组，而不是最大和。
因此这里我们不光要记录dp[i] 和 最大和max，还要记录dp[i]的应的数组区间[left,right] 和 最大和数组区间[resl,resr]
代码：
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
*
*
* @param array int整型一维数组
* @return int整型一维数组
*/
public int[] FindGreatestSumOfSubArray (int[] array) {
// write code here
int len = array.length;
int[] dp = new int[len];
dp[0] = array[0];
int max = dp[0];
int left = 0; int right = 0; // 记录dp[i]对应子数组的范围[left,right]
int resl = 0; int resr = 0; // 记录最大dp 的 对应数组范围[resl,resr]
for(int i=1; i<len; i++) {
right = i; // rigth是根据i变化而变化的
// 状态转移方程
if(dp[i-1] < 0) {
dp[i] = array[i];
left = i;
} else {
dp[i] = dp[i-1] + array[i];
}
// 最后比较最大和 以及对应的子数组长度
if(dp[i] > max || (dp[i]==max && (right-left) > (resr-resl))) {
// max改变
max = dp[i];
// 对应的最大和的 数组区间也改变
resl = left; resr = right;
}
}
// 这里注意Arrays.copyOfRange(int[],start,end)是[)的区间 因此是resr+1
return Arrays.copyOfRange(array, resl, resr+1);
}
}
剑指 Offer 47. 礼物的最大价值
分析：
- 要想 到达某个点的路径是最优的， 那么到达这个点的上一步的路径一定也是最优的，这是一道典型的动态规划问题
- 状态转移方程为：
dp[i][j] = max(dp[i-1][j],dp[i][j-1]) + grid[i][j] - 步骤：遍历二维数组，填表
代码：
class Solution {
public int maxValue(int[][] grid) {
int maxvalue = 0;
if(grid.length == 0) {
return 0;
}
if(grid[0].length == 0) {
return 0;
}
int row = grid.length;
int col = grid[0].length;
int[][] dp = new int[row][col];
for(int i=0; i<row; i++) {
for(int j=0; j<col; j++) {
// 这里防止数组下标越界 若取不到就为0
// 上
int up = i - 1 < 0 ? 0 : dp[i-1][j];
// 左
int left = j - 1 < 0 ? 0 : dp[i][j-1];
// 动态转移
dp[i][j] = Math.max(up, left) + grid[i][j];
}
}
return dp[row-1][col-1];
}
}
剑指 Offer 48. 最长不含重复字符的子字符串
分析：
解题思路：
该题是一道滑动窗口的问题。
滑动窗口的一般套路：左区间手动改变，有区间for循环累加
B站上视频链接：
https://www.bilibili.com/video/BV1BV411i77g
https://www.bilibili.com/video/BV1w5411E7EP
代码：
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s.length() == 0) {
return 0;
}
// [key:value] -> [字符:对应下标]
Map<Character, Integer> map = new HashMap();
// 最大长度
int maxLength = 0;
// 滑动窗口左边界
int left = 0;
// [left,right]维护不重复的字符串（滑动窗口）
for(int right=0; right<s.length(); right++) {
char curChar = s.charAt(right);
// 如果当前字符在map中存在，那么有可能该字符就在滑动窗口范围内
if(map.containsKey(curChar)) {
// 改变左边界。
// 取这两个值的最大值 也即是最右边的下标 若map中的下标不在滑动窗口范围内begin是不变的，这里使用max函数是很巧妙的
left = Math.max(left, map.get(curChar) + 1);
}
// 若 当前长度 > 历史最大长度， 则更新
if(right - left + 1 > maxLength) {
maxLength = right - left + 1;
}
// 将当前 字符：位置 存入到map中
map.put(curChar, right);
}
return maxLength;
}
}
剑指 Offer 60. n个骰子的点数
分析：
参考视频：【【剑指Offer最优解】 60. n个骰子的点数 ｜ 没想到这都能用动态规划】
设dp[n, x] 表示n个骰子，点数为x的组合数
假设原有n-1个骰子，此刻添加1个骰子，则新增的骰子 有[1,6]点面（6种可能）
当点数为1时，则n-1个骰子，点数应该是x-1
当点数为2时，则n-1个骰子，点数应该是x-2
。。。
当点数为5时，则n-1个骰子，点数应该是x-5
当点数为6时，则n-1个骰子，点数应该是x-6
则我们推出：dp[n][j] = dp[n-1][j-1] + dp[n-1][j-2] +...+ dp[n-1][j-5] + dp[n-1][j-6]
代码：
class Solution {
public double[] dicesProbability(int n) {
// 存在的点数可能是[n, 6n]
double[] res = new double[5 * n + 1];
// dp含义: n个骰子，点数为i的排列组合
int[][] dp = new int[n+1][6*n+1];
// 初始化db[1][i]
for(int i=1; i<=6; i++) {
dp[1][i] = 1;
}
if (n > 1) {
// 填表格
for(int i=2; i<=n; i++) {
for(int j=i; j<=6*n; j++) {
dp[i][j] = 0;
// 最后一个骰子点数有[1-6]，6种可能
for(int k=1; k<=6; k++) {
// 模拟最后一个骰子的点数为k，则前i-1个骰子为dp[i-1][j-k]
if(j-k < 0) break;
dp[i][j] += dp[i-1][j-k];
}
}
}
}
// 所有排列组合总的情况
double sum = Math.pow(6, n);
int index = 0;
for(int d=n; d<=6*n; d++) {
res[index] = dp[n][d] / sum;
index++;
}
return res;
}
}
位运算
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};
}
}
数学
剑指 Offer 39. 数组中出现次数超过一半的数字
分析：
摩尔投票算法 可以使空间复杂度O(1)，时间复杂度为O(n).
参考视频：【【剑指Offer最优解】 39. 数组中出现次数超过一半的数字 ｜ 摩尔斯投票法】
代码：
class Solution {
public int majorityElement(int[] nums) {
int res = nums[0];
// 票数
int rating = 0;
for(int i=0; i<nums.length; i++) {
// 当票数为0时， 将当前数当做m
if(rating == 0) {
res = nums[i];
}
if(nums[i] == res) {
// 若与m相同 票数就++
rating++;
} else {
// 不同则--
rating--;
}
}
return res;
}
}
剑指 Offer 66. 构建乘积数组
【剑指 Offer 66. 构建乘积数组】
> 分析：
B站上视频连接：https://www.bilibili.com/video/BV1xV411f773
- 利用类似于动态规划的思想，构建
[0,i]的乘积数组，即i及i之前的所有数的乘积 - 利用类似于动态规划的思想，构建
[i,n-1]的乘积数组，即i及i之后的所有数的乘积 - 最终根据题意
res[i] = cj1[i-1] * cj2[i+1]，求最终结果集
代码：
import java.util.ArrayList;
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;
}
}
剑指 Offer 14- I. 剪绳子
分析：
动态规划的思想
参考视频：【剑指Offer.66.剪绳子】
代码：
class Solution {
public int cuttingRope(int n) {
if(n == 1) {
return 1;
}
// target为2 拆分为 1*1 = 1
if(n == 2) {
return 1;
}
// 3 拆分为2*1 或者 1*2 = 2
if(n == 3) {
return 2;
}
// dp[i]表示的意思是对长度为n的绳子 所能做出的最大贡献是多少（可以拆分也可以不拆分）
// i<=3时，对i不拆分,dp[i]结果更大;例如3 拆分的结果最大为2*1=2,而不拆分结果为3
// i>=4时，对i拆分,dp[i]结果更大； 例如5 拆分结果最大为2*3=6，而不拆分结果为5
int[] dp = new int[n+1];
// 当 i<=3 时，不拆分价值更大
dp[1] = 1;
dp[2] = 2;
dp[3] = 3;
// 填dp数组
for(int i=4; i<=n; i++) {
int max = 0;
for(int j=1; j<=i/2; j++) {
// 这里直接取得是max与dp[j]*dp[i-j]的最大值，因为max初始值为0，因此可以这样写
max = Math.max(dp[j]*dp[i-j], max);
}
dp[i] = max;
}
return dp[n];
}
}
剑指 Offer 62. 圆圈中最后剩下的数字
分析：
个人总结：Joseph(约瑟夫环)问题
代码：
class Solution {
public int lastRemaining(int n, int m) {
return ysfh(n, m);
}
public int ysfh(int n, int k) {
if(n == 1) {
return 0;
} else {
return (ysfh(n-1, k) + k) % n;
}
}
}