最新打卡动态-跟着帅地玩副业，开拓第二曲线PlayOffer

ShadowyHalo 永久会员 2025年7月29日下午3:28

本打卡对应问题：【二分查找专题】剑指 Offer 11. 旋转数组的最小数字
具体打卡内容：

打卡
class Solution {
public int inventoryManagement(int[] stock) {
int low = 0;
int high = stock.length – 1;
while(low < high){
int mid = low + (high – low) / 2;
if(stock[mid] < stock[high]){
high = mid;
}else if(stock[mid] > stock[high]){
low = mid + 1;
}else{
high -= 1;
}
}
return stock[low];
}
}

ShadowyHalo 永久会员 2025年6月7日下午7:51

本打卡对应问题：【基本数据结构】剑指 Offer 09. 用两个栈实现队列
具体打卡内容：

class MyQueue {
Deque inStack;//存后入的元素，后入后出
Deque outStack;//为空时将in压入out

public MyQueue() {
    inStack = new ArrayDeque<Integer>();
    outStack = new ArrayDeque<Integer>();
}

public void push(int x) {
    inStack.push(x);
}

public int pop() {
    if (outStack.isEmpty()) {
        in2out();
    }
    return outStack.pop();
}

public int peek() {
       if (outStack.isEmpty()) {
        in2out();
    }
    return outStack.peek();
}

public boolean empty() {
    return inStack.isEmpty() && outStack.isEmpty();
}

 private void in2out() {
    while (!inStack.isEmpty()) {
        outStack.push(inStack.pop());
    }
}

}

/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue obj = new MyQueue();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.peek();
* boolean param_4 = obj.empty();
*/

ShadowyHalo 永久会员 2025年6月7日下午4:14

本打卡对应问题：【基本数据结构】LeetCode 225. 用队列实现栈
具体打卡内容：

class MyStack {
Queue queue1;//对应栈
Queue queue2;//操作队列

public MyStack() {
    queue1 = new LinkedList<Integer>();
    queue2 = new LinkedList<Integer>();
}

/**2放置新元素，然后1存储整个队列，将1传入2后再传回去 */
public void push(int x) {
    queue2.offer(x);
    while(!queue1.isEmpty()){
        queue2.offer(queue1.poll());
    }
    //交换队列
    Queue<Integer> temp = queue1;
    queue1 = queue2;
    queue2 = temp;
}

public int pop() {
    return queue1.poll();
}

public int top() {
    return queue1.peek();
}

public boolean empty() {
    return queue1.isEmpty();
}

}

/**
* Your MyStack object will be instantiated and called as such:
* MyStack obj = new MyStack();
* obj.push(x);
* int param_2 = obj.pop();
* int param_3 = obj.top();
* boolean param_4 = obj.empty();
*/

G 永久会员 2025年4月22日下午8:36

本打卡对应问题：【链表专题】剑指 Offer 35. 复杂链表的复制
具体打卡内容：

“`java 在每一个节点的后面复制一个值一样的节点
class Solution {
public Node copyRandomList(Node head) {
if(head == null){
return null;
}
// 复制链表节点
Node cur = head;
while(cur != null){
Node next = cur.next;
cur.next = new Node(cur.val);
cur.next.next = next;
cur = next;
}

    // 复制随机节点
    cur = head;
    while(cur != null){
        Node curNew = cur.next;
        // 随机节点指向原链表节点的随机节点的复制节点
        curNew.random = cur.random == null ? null : cur.random.next;
        cur = cur.next.next;
    }

    // 拆分,比如把 A->A1->B->B1->C->C1拆分成 A->B->C和A1->B1->C1
    Node headNew = head.next;
    cur = head;
    Node curNew = head.next;
    while(cur != null){
        cur.next = cur.next.next;
        cur = cur.next;
        curNew.next = cur == null ? null : cur.next;
        curNew = curNew.next;
    }

    return headNew;
}

}

“`
时间复杂度O(N),额外空间复杂度为O(1)

Yui 永久会员 2025年4月22日下午7:05

本打卡对应问题：【链表专题】剑指 Offer 35. 复杂链表的复制
具体打卡内容：

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null){
            return null;
        }

        Node cur = head;
        while(cur != null){
            //复制一个结点挂在原结点后面
            Node next = cur.next;
            cur.next = new Node(cur.val);
            cur.next.next = next;
            cur = next;
        }


        cur = head;
        while(cur != null){
            Node curNew = cur.next;
            curNew.random = cur.random == null ? null : cur.random.next;
            cur = cur.next.next;
        }

        Node headNew = head.next;
        cur = head;
        Node curNew = head.next;
        while(cur != null){
            cur.next = cur.next.next;
            cur = cur.next;
            curNew.next = cur == null ? null : cur.next;
            curNew = curNew.next;
        }

        return headNew;
    }
}

解题思路：本题主要使用复制拆分思想，先将原链表每个结点后面复制一个新节点，再在这个新链表中表示新节点的新random指针，最后将其拆成原链表和新链表，难点在与如何写好复制和拆分的操作。
时间复杂度：O(n)，空间复杂度：O(1)

重明鸟永久会员 2025年4月22日下午6:54

本打卡对应问题：【链表专题】剑指 Offer 35. 复杂链表的复制
具体打卡内容：

用Map集合做的，时间和空间都是和O(n)

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null) {return null;}
        Node cur = head;
        Map<Node, Node> map = new HashMap<>();
        while(cur != null) {
            Node node = new Node(cur.val);
            map.put(cur, node);
            cur = cur.next;
        } 
        cur = head;
        while(cur != null) {
            Node node = map.get(cur);
            node.next = map.get(cur.next);
            node.random = map.get(cur.random);  
            cur = cur.next;
        }
        return map.get(head);
    }
}

Aatorx 永久会员 2025年4月22日下午3:57

本打卡对应问题：【链表专题】剑指 Offer 35. 复杂链表的复制
具体打卡内容：

class Solution {
public:
    Node* copyRandomList(Node* head) {
        if(!head) return NULL;
        Node* cur = head;
        while(cur) {
            Node* temp = new Node(cur->val);
            temp->next = cur->next;
            cur->next = temp;
            cur = cur->next->next;
        }
        cur = head;
        while(cur) {
            if(cur->random) {
                cur->next->random = cur->random->next;
            }
            cur = cur->next->next;
        }
        cur = head->next;
        Node* pre = head;
        Node* res = head->next;
        while(cur->next != NULL) {
            pre->next = pre->next->next;
            cur->next = cur->next->next;
            cur = cur->next;
            pre = pre->next;
        }
        pre->next = NULL;
        return res;
    }
};

时间复杂度O(N)，空间复杂度O(1)。

魂牵梦萦永久会员 2025年4月22日下午2:47

本打卡对应问题：【链表专题】剑指 Offer 35. 复杂链表的复制
具体打卡内容：

看了题解才有的思路，太厉害了…惯性思维一直导致我在想怎么遍历一遍还能做到复制random，完全没想到map。

class Solution {
    Map<Node, Node> map = new HashMap<>();
    public Node copyRandomList(Node head) {
        if(head == null) return null;

        Node cur = head;
        while(cur != null) {
            map.put(cur, new Node(cur.val));
            cur = cur.next;
        }

        cur = head;
        while(cur != null) {
            Node dup = map.get(cur);
            dup.next = map.get(cur.next);
            dup.random = map.get(cur.random);
            cur = cur.next;
        }
        return map.get(head);
    }
}

芒种永久会员 2025年4月22日上午10:18

本打卡对应问题：【链表专题】剑指 Offer 35. 复杂链表的复制
具体打卡内容：

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
         if (head == null)
            return null;
        Node cur = head;
        while (cur != null) {
            Node copy = new Node(cur.val);
            copy.next = cur.next;
            cur.next = copy;
            cur = copy.next;
        }
        cur = head;
        while (cur != null) {
            if (cur.random != null) {
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        cur = head;
        Node copyHead = head.next;
        Node copyCur = copyHead;
        while (cur != null) {
            cur.next = copyCur.next;
            cur = cur.next;
            if (cur != null) {
                copyCur.next = cur.next;
                copyCur = copyCur.next;
            }
        }
        return copyHead;
    }
}

时间复杂度O(n)
空间复杂度O(1)

夏目永久会员 2025年4月21日下午11:07

本打卡对应问题：【链表专题】剑指 Offer 35. 复杂链表的复制
具体打卡内容：

class Solution {
    public Node copyRandomList(Node head) {
        HashMap<Node,Node> map = new HashMap<>();
        Node virtureHead = new Node(-1);
        Node p = head,q = virtureHead;
        while(p != null){
            Node node = new Node(p.val);
            q.next = node;
            q = q.next;
            map.put(p,q);
            p = p.next;
        }
        p = head;
        q = virtureHead.next;
        while(p != null){
            q.random = map.get(p.random);
            p = p.next;
            q = q.next;
        }
        return virtureHead.next;

    }
}

时间复杂度O(n)
空间复杂度O(n)

奈何永久会员 2025年4月21日下午10:38

本打卡对应问题：【链表专题】剑指 Offer 35. 复杂链表的复制
具体打卡内容：

class Solution {
    public Node copyRandomList(Node head) {
        Node ans = new Node(-1);
        Map<Node, Node> map = new HashMap<>();
        Node p = head;
        while(p != null){
            map.put(p, new Node(p.val));
            p = p.next;
        }
        p = ans;
        while(head != null){
            p.next = map.get(head);
            p = p.next;
            p.random = map.get(head.random);
            head = head.next;
        }
        return ans.next;
    }
}

时间复杂度O(n)
空间复杂度O(n)

. 永久会员 2025年4月21日下午8:48

本打卡对应问题：【链表专题】剑指 Offer 35. 复杂链表的复制
具体打卡内容：

class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) {
            return head;
        }

        Node cur = head;
        Node next = null;

        while (cur != null) {
            next = cur.next;
            cur.next = new Node(cur.val);
            cur.next.next = next;
            cur = next;
        }

        cur = head;

        while (cur != null) {
            next = cur.next.next;
            cur.next.random = cur.random == null ? null : cur.random.next;
            cur = next;
        }

        Node h = head.next;
        cur = head;
        while (cur != null) {
            next = cur.next.next;
            Node node = cur.next;
            cur.next = next;
            node.next = next == null ? null : next.next;
            cur = next;
        }

        return h;
    }
}

时间复杂度O(n)

空间复杂度O(1)

??? 永久会员 2025年4月21日下午7:45

本打卡对应问题：【链表专题】剑指 Offer 35. 复杂链表的复制
具体打卡内容：

class Solution {
    public Node copyRandomList(Node head) {
        if (head == null)
            return null;
        //进行节点的复制
        Node cur = head;
        while (cur != null) {
            Node tmp = new Node(cur.val);
            tmp.next = cur.next;
            cur.next = tmp;
            cur = tmp.next;
        }
        //进行随机指向的复制
        cur = head;
        while (cur != null) {
            if (cur.random != null) {
                cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }
        //进行拆分
        cur = head.next;
        Node pre = head;
        Node res = head.next;
        while (cur.next != null) {

            pre.next = pre.next.next;
            cur.next = cur.next.next;
            pre = pre.next;
            cur = cur.next;
        }
        pre.next = null;
        return res;

    }
}

shuaidi 永久会员 2025年4月21日上午1:20

本打卡对应问题：【杂题】剑指 Offer 29. 顺时针打印矩阵
具体打卡内容：

测试

為愛而生普通 2025年3月24日下午9:39

本打卡对应问题：【链表专题】字节真题：单链表相加
具体打卡内容：

class Solution {
// 两数相加Ⅱ
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {

    Deque <Integer> stack1 = new ArrayDeque<Integer>();
    Deque <Integer> stack2 = new ArrayDeque<Integer>();
    while (l1 != null) {
        stack1.push(l1.val);
        l1 = l1.next;
    }
    while (l2 != null) {
        stack2.push(l2.val);
        l2 = l2.next;
    }
    int carry = 0;
    ListNode ans = null;
    while (!stack1.isEmpty() || !stack2.isEmpty() || carry != 0) {
        int a = stack1.isEmpty() ? 0 : stack1.pop();
        int b = stack1.isEmpty() ? 0 : stack2.pop();
        int cur = a + b + carry;
        carry = cur / 10;
        cur %= 10;
        ListNode curnode = new ListNode(cur);
        curnode.next = ans;
        ans = curnode;
    }
    return ans;
}

lQl 永久会员 2025年1月18日上午11:01

本打卡对应问题：【回溯专题】剑指 Offer 12. 矩阵中的路径
具体打卡内容：

class Solution {
    public boolean wordPuzzle(char[][] grid, String target) {
        int m = grid.length;// 行数
        int n = grid[0].length;// 列数
        char[] words = target.toCharArray();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (dfs(grid, words, i, j, 0))
                    return true;
            }
        }
        return false;
    }

    boolean dfs(char[][] grid, char[] words, int i, int j, int k) {
        if (i >= grid.length || i < 0 || j >= grid[0].length || j < 0 || grid[i][j] != words[k])
            return false;
        if (k == words.length - 1)
            return true;
        grid[i][j] = '\0';
        boolean res = dfs(grid, words, i + 1, j, k + 1) || dfs(grid, words, i - 1, j, k + 1)
                || dfs(grid, words, i, j + 1, k + 1) || dfs(grid, words, i, j - 1, k + 1);
        grid[i][j] = words[k];
        return res;
    }
}

时间复杂度O(mn4^l)
空间复杂度O(l)

lQl 永久会员 2025年1月18日上午10:34

本打卡对应问题：【排序算法运用】剑指 Offer 51. 数组中的逆序对
具体打卡内容：

class Solution {
    int cnt = 0;

    public int reversePairs(int[] record) {
        mergeSort(record, 0, record.length - 1);
        return cnt;
    }

    private void mergeSort(int[] record, int l, int r) {
        if (l >= r)
            return;
        int m = (l + r) / 2;
        mergeSort(record, l, m);
        mergeSort(record, m + 1, r);
        merge(record, l, m, r);
    }

    public void merge(int[] record, int l, int m, int r) {
        int[] tmp = new int[r - l + 1];
        int i = l;
        int j = m + 1;
        int t = 0;
        while (i <= m && j <= r) {
            if (record[i] <= record[j]) {
                tmp[t++] = record[i++];
            } else {
                cnt += m - i + 1;
                tmp[t++] = record[j++];
            }
        }
        while (i <= m) {
            tmp[t++] = record[i++];
        }
        while (j <= r) {
            tmp[t++] = record[j++];
        }
        for (int k = 0; k < tmp.length; k++) {
            record[l + k] = tmp[k];
        }
    }
}

时间复杂度O(nlogn)
空间复杂度O(n)

lQl 永久会员 2025年1月16日下午5:30

本打卡对应问题：【排序算法运用】剑指 Offer 41. 数据流中的中位数
具体打卡内容：

class MedianFinder {
    Queue<Integer> A,B;
    /** initialize your data structure here. */
    public MedianFinder() {
        A = new PriorityQueue<>();
        B = new PriorityQueue<>((x,y)->(y-x));
    }

    public void addNum(int num) {
        if(A.size()!=B.size()){
            A.add(num);
            B.add(A.poll());
        }else{
            B.add(num);
            A.add(B.poll());
        }
    }

    public double findMedian() {
        if(A.size()!=B.size()){
            return A.peek();
        }else{
            return (A.peek()+B.peek())/2.0;
        }
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

时间复杂度:查找中位数O(1)
插入元素O(logn)
空间复杂度O(n)

lQl 永久会员 2025年1月16日上午11:33

本打卡对应问题：【排序算法运用】剑指 Offer 40. 最小的k个数
具体打卡内容：

class Solution {
    public int[] inventoryManagement(int[] stock, int cnt) {
        int len = stock.length;
        if (cnt == 0) {
            return new int[0];
        }
        quickSort(stock, 0, len - 1);
        int[] res = new int[cnt];
        for (int i = 0; i < cnt; i++) {
            res[i] = stock[i];
        }
        return res;
    }

    public void quickSort(int[] stock, int l, int r) {
        if (l < r) {
            int pivot = stock[l];
            int i = l;
            int j = r;
            while (i < j) {
                while (i < j && stock[j] >= pivot) {
                    j--;
                }
                stock[i] = stock[j];

                while (i < j && stock[i] < pivot) {
                    i++;
                }
                stock[j] = stock[i];

            }
            stock[i] = pivot;
            quickSort(stock, l, i-1);
            quickSort(stock, i + 1, r);
        }
    }
}

时间复杂度O(nlogn)
空间复杂度O(logn)

岱永久会员 2025年1月10日下午4:29

本打卡对应问题：【二叉树专题】199. 二叉树的右视图
具体打卡内容：

199. 二叉树的右视图

层序遍历。记录每层最后一个

class Solution {
    public List<Integer> rightSideView(TreeNode root) {

        List<Integer> l = new ArrayList<>();
        if(root==null)return l;
        //层序遍历
        Queue<TreeNode> queue =  new LinkedList<TreeNode>();
        queue.add(root);
        while(!queue.isEmpty()){
            for(int i = queue.size();i>0;i--){
                TreeNode node = queue.poll();
                if(i==1)l.add(node.val);
                if(node.left!=null) queue.add(node.left);
                if(node.right!=null) queue.add(node.right);
            }

        }
        return l;
    }
}

递归，记录第一次到某深度

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        List<Integer> ans = new ArrayList<>();
        dfs(root , 0, ans);
        return ans;
    }
    void dfs(TreeNode root,int depth, List<Integer> ans){
        if(root==null)return;
        //深度首次遇到
        if(depth == ans.size()) ans.add(root.val);
        dfs(root.right,depth+1,ans);
        dfs(root.left,depth+1,ans);
    }

}

岱永久会员 2025年1月10日下午2:19

本打卡对应问题：【二叉树专题】543. 二叉树的直径
具体打卡内容：

543. 二叉树的直径

class Solution {
    int ans=0;
    public int diameterOfBinaryTree(TreeNode root) {
        if(root == null) return 0;
        depth(root);
        return ans;
    }

    public int depth(TreeNode node){
        if(node == null) return 0;
        int left = depth(node.left);
        int right = depth(node.right);
        ans= Math.max(ans,left+right);
        return Math.max(left,right)+1;
    }
}

岱永久会员 2025年1月9日下午9:42

本打卡对应问题：【二叉树专题】剑指 Offer 37. 序列化二叉树
具体打卡内容：

LCR 156. 序列化与反序列化二叉树

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        if(root==null)return "[]";
        StringBuilder res = new StringBuilder("[");
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(node!=null){
                res.append(node.val+",");
                queue.add(node.left);
                queue.add(node.right);
            }
            else res.append("null,");
        }
        //删除最后一个，
        res.deleteCharAt(res.length() -1 );
        res.append("[");
        return res.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        if(data.equals("[]")) return null;
        String[] val = data.substring(1,data.length()-1).split(",");
        TreeNode root = new TreeNode(Integer.parseInt(val[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int i = 1 ;
        while(!queue.isEmpty()){
            TreeNode node = queue.poll();
            if(!val[i].equals("null")){//不为空
                node.left = new TreeNode(Integer.parseInt(val[i]));
                queue.add(node.left);
            }
            i++;
            if(!val[i].equals("null")){
                node.right = new TreeNode(Integer.parseInt(val[i]));
                queue.add(node.right);
            }
            i++;
        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

岱永久会员 2025年1月8日下午4:43

本打卡对应问题：【二叉树专题】剑指 Offer 68 – I. 二叉搜索树的最近公共祖先
具体打卡内容：

LCR 193. 二叉搜索树的最近公共祖先

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        while(root!=null){
            if(root.val < p.val && root.val < q.val)// p,q 都在 root 的右子树中
            {
                root=root.right;
            }else if(root.val > p.val && root.val > q.val)// p,q 都在 root 的左子树中
            {
                root = root.left;
            }else break;
        }
        return root;
    }
}

岱永久会员 2025年1月8日下午3:30

本打卡对应问题：【二叉树专题】剑指 Offer 54. 二叉搜索树的第k大节点
具体打卡内容：

LCR 174. 寻找二叉搜索树中的目标节点

class Solution {
    int cnt,res;
    public int findTargetNode(TreeNode root, int cnt) {
        this.cnt = cnt;
        dfs(root);
        return res;
    }
    void dfs(TreeNode root){
        if(root==null)return;
        dfs(root.right);
        if(cnt==0)return;
        cnt--;
        if(cnt == 0)res = root.val;
        dfs(root.left);
    }
}

陆狗陆狗普通 2025年1月8日上午10:54

本打卡对应问题：【杂题】剑指 Offer 29. 顺时针打印矩阵
具体打卡内容：

解题思路
– 按照上右下左的顺序进行遍历，注意4个边界的缩减
【题解1】

class Solution {
    public int[] spiralArray(int[][] array) {
        // 【错误】边界判断
        if(array.length==0){
            return new int[0];
        }

        // 思路：正常进行遍历即可，关键是缩减遍历的边界
        int up = 0;
        int down = array.length - 1;
        int left = 0;
        int right = array[0].length - 1;
        int[] result = new int[array.length * array[0].length];
        int cur = 0;
        // 【错误】注意应该是<=,因为array只有一行，up=down=0；只有一列，left=right=0，最终结束的条件就是up和down错位 或者 left和right错位
        while (up <= down && left <= right) {
            // 遍历上边
            for (int j = left; j <= right; j++) {
                result[cur] = array[up][j];
                cur++;
            }
            up++;
            // 遍历右边
            for (int i = up; i <= down; i++) {
                result[cur] = array[i][right];
                cur++;
            }
            right--;

            // 遍历下边
            if (up <= down) {
                for (int j = right; j >= left; j--) {
                    result[cur] = array[down][j];
                    cur++;
                }
                down--;
            }

            // 遍历左边
            if (left <= right) {
                for (int i = down; i >= up; i--) {
                    result[cur] = array[i][left];
                    cur++;
                }
                left++;
            }
        }
        return result;
    }
}

错误点1：边界判断
错误点2：注意应该是<=,因为array只有一行，up=down=0；只有一列，left=right=0，最终结束的条件就是up和down错位或者 left和right错位

陆狗陆狗普通 2025年1月8日上午9:30

本打卡对应问题：【杂题】剑指 Offer 04. 二维数组中的查找
具体打卡内容：

解题思路
– 不能从(0,0)开始遍历，应该从左下角开始遍历。因为左下角满足一个性质，是同一列中的最大值，是同一列中的最小值
【题解1】

class Solution {
    public boolean findTargetIn2DPlants(int[][] plants, int target) {
        // 【错误】临界值
        if (plants.length == 0 || plants[0].length == 0) {
            return false;
        }
        // 从左下角开始遍历。因为左下角满足一个性质，是同一列中的最大值，是同一列中的最小值
        int i = plants.length - 1;
        int j = 0;
        // 【错误】循环条件写成了||，之前想的是可能会出现到了第0行，结果在第0行的右边，但是这种情况&&是能够涵盖的，反而||会导致越界
        while (i >= 0 &&  j <= plants[0].length - 1) {
            if (plants[i][j] == target) {
                return true;
            } else if (plants[i][j] < target) {
                // 小于。右移，因为右边的比较大
                j++;
            } else {
                // 大于。上游，因为上边的比较小
                i--;
            }
        }
        return false;

    }
}

错误点1：临界值的判断
错误点2：循环条件写成了||，之前想的是可能会出现到了第0行，结果在第0行的右边，但是这种情况&&是能够涵盖的，反而||会导致越界

陆狗陆狗普通 2025年1月8日上午9:11

本打卡对应问题：【动态规划专题】LeetCode 322. 零钱兑换
具体打卡内容：

解题思路
– dp[i]表示金额为amount的最少组合次数
– dp[i]和dp[i-coins]的关系，主要是看coins里面有哪些硬币。取最小的+1即可。
– 比如conins的范围是[2,3,5]
– 那么dp[i] 就是 Math.min(dp[i-2],dp[i-3],dp[i-5])+1
【题解1】没参考题解的思路，时间复杂度是O(m*n)

class Solution {
    public int coinChange(int[] coins, int amount) {
        // dp[i]表示金额为amount的最少组合次数
        // dp[i]和dp[i-coins]的关系，主要是看coins里面有哪些硬币。取最小的+1即可。但是要注意-1的场景判断
        // 之所以要+1，是因为amount从0
        int[] dp = new int[amount + 1];
        // 【错误】coins不是顺序的，进行一下排序
        Arrays.sort(coins);
        // 【错误】没有提前赋值
        // 金额为0，那么只需要0个硬币
        dp[0] = 0;

        for (int amountValue = 1; amountValue <= amount; amountValue++) {
            // 初始值
            if (amountValue < coins[0]) {
                dp[amountValue] = -1;
                // 【错误】没有提前返回
                continue;
            }

            // 分情况判断
            int target = -1;
            for (int j = 0; j < coins.length; j++) {
                // 【错误】没有判断是否已经越界
                int preAmountValue = amountValue - coins[j];
                if (preAmountValue < 0) {
                    break;
                }
                int preDp = dp[preAmountValue];
                if (preDp != -1) {
                    target = target == -1 ? preDp + 1 : Math.min(target, preDp + 1);
                }
            }
            dp[amountValue] = target;
        }
        return dp[amount];

    }
}

错误点1：coins不是顺序的，进行一下排序
错误点2：没有提前赋值给dp[0]=0
错误点3：一些初始值没有提前返回
错误点4：没有判断是否已经越界

题解2

class Solution {
    public int coinChange(int[] coins, int amount) {
        // dp[i]表示金额为i的最少硬币数
        int[] dp = new int[amount + 1];

        // 初始化
        for (int i = 1; i <= amount; i++) {
            dp[i] = Integer.MAX_VALUE; // 将所有金额初始化为一个较大的值
        }
        dp[0] = 0; // 凑成金额0需要0个硬币

        // 动态规划计算最少硬币数
        for (int i = 1; i <= amount; i++) {
            for (int coin : coins) {
                if (i >= coin) {
                    int preDp = dp[i - coin];
                    if (preDp != Integer.MAX_VALUE) { // 只有在可达的情况下才更新
                        dp[i] = Math.min(dp[i], preDp + 1);
                    }
                }
            }
        }

        // 如果dp[amount]仍然是初始值，表示无法凑成该金额
        return dp[amount] == Integer.MAX_VALUE ? -1 : dp[amount];
    }
}

岱永久会员 2025年1月7日下午10:12

本打卡对应问题：【二叉树专题】剑指 Offer 33. 二叉搜索树的后序遍历序列
具体打卡内容：

LCR 152. 验证二叉搜索树的后序遍历序列

class Solution {
    public boolean verifyTreeOrder(int[] postorder) {
        return recur(postorder,0,postorder.length-1);
    }

    Boolean recur(int[] postorder,int i ,int j){
        if(i>=j)return true;
        int p = i;
        while(postorder[p]<postorder[j])p++;
        int m = p;
        while(postorder[p]>postorder[j])p++;
        return p == j && recur(postorder,i,m-1) && recur(postorder,m,j-1);
    }
}

陆狗陆狗普通 2025年1月7日下午9:40

本打卡对应问题：【杂题】剑指 Offer 03. 数组中重复的数字
具体打卡内容：

解题思路
– 最简单的思路是使用HashMap，但是需要额外的空间
– 优化就是使用0 ≤ documents[i] ≤ n-1的特性，用原数组进行一些重复性的校验
– 判断当前index=documents[index]
– 不相等，就把当前documents[index]换到正确的下标处，如果那个下标已经有相等的占据了，就说明重复了（如果是完全不重复的，那么理论上可以遍历到最后一个）
【题解1】

class Solution {
    public int findRepeatDocument(int[] documents) {

        int i = 0;
        while (i < documents.length) {
            // 判断当前index=documents[index]
            // 不相等，就把当前documents[index]换到正确的下标处，如果那个下标已经有相等的占据了，就说明重复了
            int curValue = documents[i];
            while (curValue != i) {
                if (documents[curValue] == curValue) {
                    return curValue;
                } else {
                    swap(documents, i, curValue);
                }
                curValue = documents[i];
            }
            i++;
        }
        return -1;
    }

    public void swap(int[] documents, int a, int b) {
        int tmpt = documents[a];
        documents[a] = documents[b];
        documents[b] = tmpt;
    }
}

陆狗陆狗普通 2025年1月7日上午10:32

本打卡对应问题：【杂题】剑指 Offer 62. 圆圈中最后剩下的数字
具体打卡内容：

解题思路
– dp[n] 和 dp[n-1]的关系是什么？dp[n] 表示的是i个数据，dp[n-1]表示的i-1个数据
– 那么只需要dp[n]先把第一轮要去除的数据去除掉，去除后的规模就和dp[n-1]保持一致了
– 去除的点index= (m-1)%n，dp[n-1]’的起点是index= m % n。注意dp[n]=dp[n-1]‘
– 如果我们把dp[n-1]’的起点index= m % n视同是0，dp[n-1]‘=( m%n + dp[n-1] ) ,因为可能越界，dp[n-1]‘=( m%n + dp[n-1] ) % n=dp[n]
【题解1】

class Solution {
    public int iceBreakingGame(int num, int target) {
        // dp[n] 和 dp[n-1]的关系是什么？dp[n] 表示的是i个数据，dp[n-1]表示的i-1个数据
        // 那么只需要dp[n]先把第一轮要去除的数据去除掉，去除后的规模就和dp[n-1]保持一致了
        // 去除的点index= (m-1)%n，dp[n-1]’的起点是index= m % n。注意dp[n]=dp[n-1]‘
        // 如果我们把dp[n-1]'的起点index= m % n视同是0，dp[n-1]‘=( m%n + dp[n-1] ) ,因为可能越界，
        // dp[n-1]‘=( m%n + dp[n-1] ) % n=dp[n]
        // 【错误】index要从0开始计数
        int[] dp = new int[num + 1];
        dp[1] = 0;
        for (int i = 2; i <= num; i++) {
            // 【错误】n是会变动的，就是这里的i
            dp[i] = (target % i + dp[i - 1]) % i;
        }
        return dp[num];
    }
}

错误点1：index要从0开始计数
错误点2：n是会变动的，就是这里的i

陆狗陆狗普通 2025年1月7日上午9:22

本打卡对应问题：【杂题】剑指 Offer 10- II. 青蛙跳台阶问题
具体打卡内容：

解题思路
– 普通的dp，只是需要注意一下边界条件
【题解1】

class Solution {
    public int trainWays(int num) {
        // 【错误】边界问题,并且dp[0]=1
        if (num == 0 || num == 1) {
            return 1;
        }
        // dp[i]=dp[i-1]+dp[i-2],关键是需要大数取模
        int[] dp = new int[num + 1];
        dp[0] = 1;
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= num; i++) {
            dp[i] = (dp[i - 1] + dp[i - 2]) % 1000000007;
        }
        return dp[num];
    }
}

错误点1：边界问题,并且dp[0]=1

3A87 普通 2025年1月5日下午11:02

本打卡对应问题：整数拆分 🌟🌟🌟中等
具体打卡内容：

为什么要切成3?

陆狗陆狗普通 2025年1月3日下午9:33

本打卡对应问题：【杂题】剑指 Offer 10- I. 斐波那契数列
具体打卡内容：

解题思路
– 常规dp的思想，主要是要学会大数取模的表达式
【题解1】

class Solution {
    public int fib(int n) {

        // 主要是大数取模， (x+y)取p= (x取p+y取p)取p
        if (n <= 1) {
            return n;
        }
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        int p = 1000000007;
        for (int i = 2; i <= n; i++) {
            // 【错误】公式写错了，写成了(dp[i - 1] % p) + (dp[i - 2] % p) % p;
            dp[i] = (dp[i - 1] % p + dp[i - 2] % p) % p;
        }
        return dp[n];
    }
}
- 错误点1：公式写错了，写成了(dp[i - 1] % p) + (dp[i - 2] % p) % p;

【题解2】优化了一下取模，因为dp[i]一定是取模放进去的，所以dp[i]%p=dp[i]
class Solution {
    public int fib(int n) {

        // 主要是大数取模， (x+y)取p= (x取p+y取p)取p
        if (n <= 1) {
            return n;
        }
        int[] dp = new int[n + 1];
        dp[0] = 0;
        dp[1] = 1;
        int p = 1000000007;
        for (int i = 2; i <= n; i++) {
            // 【优化】因为dp[i]一定是取模放进去的，所以dp[i]%p=dp[i]
            dp[i] = (dp[i - 1]+ dp[i - 2]) % p;
        }
        return dp[n];
    }
}
【题解3】优化了变量，其实最后只需要3个变量即可
class Solution {
    public int fib(int n) {

        // 主要是大数取模， (x+y)取p= (x取p+y取p)取p
        if (n <= 1) {
            return n;
        }

        int a = 0;
        int b = 1;
        int c = 0;
        int p = 1000000007;
        for (int i = 2; i <= n; i++) {
            c = (a + b) % p;
            a = b;
            b = c;
        }
        return c;
    }
}

陆狗陆狗普通 2025年1月3日上午9:41

本打卡对应问题：【动态规划专题】LeetCode 72. 编辑距离
具体打卡内容：

解题思路
– dp成二维数组，dp[i][j],表示word1的i位的字字符串和word2的j位的子字符串最小编辑距离
– dp[i][j]如何从前序状态变更过来？
– 情形1：如果最后一个字符相同，那么dp[i][j]=dp[i-1][j-1]
– 情形2：如果最后一个字符不相同，还得分情况(那种方式最小就取哪种)
– 情形2.1：如果是可以替换过来，dp[i][j]=dp[i-1]dp[j-1]+1
– 情形2.2：如果是多余的字符，dp[i][j]=dp[i][j-1]+1
– 情形2.3：如果是缺少的字符，dp[i][j]=dp[i-1][j]+1
【题解1】

class Solution {
    public int minDistance(String word1, String word2) {
        // dp成二维数组，dp[i][j],表示word1的i位的字字符串和word2的j位的子字符串最小编辑距离
        // dp[i][j]如何从前序状态变更过来？
        // 情形1：如果最后一个字符相同，那么dp[i][j]=dp[i-1][j-1]
        // 情形2：如果最后一个字符不相同，还得分情况(那种方式最小就取哪种)
        // 情形2.1：如果是可以替换过来，dp[i][j]=dp[i-1]dp[j-1]+1
        // 情形2.2：如果是多余的字符，dp[i][j]=dp[i][j-1]+1
        // 情形2.3：如果是缺少的字符，dp[i][j]=dp[i-1][j]+1
        int m = word1.length();
        int n = word2.length();
        // 因为范围应该是[0,m]和[0,n]，其中0表示空字符串，也要占位
        int[][] dp = new int[m + 1][n + 1];
        dp[0][0] = 0;
        // 第1行
        for (int j = 1; j <= n; j++) {
            dp[0][j] = j;
        }
        // 第1列
        for (int i = 1; i <= m; i++) {
            dp[i][0] = i;
        }
        // 状态转移
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                char w1 = word1.charAt(i - 1);
                char w2 = word2.charAt(j - 1);
                if (w1 <span class="text-highlighted-inline" style="background-color: #fffd38;"> w2) {
                    dp[i][j] = dp[i - 1][j - 1];
                } else {
                    // 【错误】注意，三个数取最小值，只能2个数字进行min比较
                    dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i][j - 1], dp[i - 1][j])) + 1;
                }
            }
        }
        return dp[m][n];
    }
}

错误点1：注意，三个数取最小值，只能2个数字进行min比较

陆狗陆狗普通 2025年1月2日下午10:25

本打卡对应问题：【动态规划专题】LeetCode 174. 地下城游戏
具体打卡内容：

解题思路
– 颠倒写dp[i][j]，表示i，j到终点的最小初始血量
– dp[i][j]=Math.min(dp[i+1][j],dp[i][j+1])dungeon[i][j]，且必须>=1，表示扣掉dungeon[i][j]之后至少要给我留下1点血
【题解1】

class Solution {
    public int calculateMinimumHP(int[][] dungeon) {
        // 颠倒写dp[i][j]，表示i，j到终点的最小初始血量
        // dp[i][j]=Math.min(dp[i+1][j],dp[i][j+1])dungeon[i][j]，且必须>=1
        // 初始值 dp[m][n]=1-dungeon[i][j]，最下边和最右边
        int m = dungeon.length;
        int n = dungeon[0].length;
        int[][] dp = new int[m][n];
        // 【错误】扣掉dungeon[m - 1][n - 1]之后至少要给我留下1点血
        dp[m - 1][n - 1] = Math.max(1 - dungeon[m - 1][n - 1], 1);
        // 最后一行
        for (int j = n - 2; j >= 0; j--) {
            dp[m - 1][j] = Math.max(dp[m - 1][j + 1] - dungeon[m - 1][j], 1);
        }
        // 最后一列
        for (int i = m - 2; i >= 0; i--) {
            dp[i][n - 1] = Math.max(dp[i + 1][n - 1] - dungeon[i][n - 1], 1);
        }
        // dp全循环
        for (int i = m - 2; i >= 0; i--) {
            for (int j = n - 2; j >= 0; j--) {
                int minValue = Math.min(dp[i + 1][j], dp[i][j + 1]) - dungeon[i][j];
                // 【错误】扣掉dungeon[i][j]之后至少要给我留下1点血
                dp[i][j] = Math.max(minValue, 1);
            }
        }

        return dp[0][0];

    }
}

错误点1：扣掉dungeon[m – 1][n – 1]之后至少要给我留下1点血
错误点2：扣掉dungeon[i][j]之后至少要给我留下1点血

為愛而生普通 2025年1月2日下午3:48

本打卡对应问题：【链表专题】剑指 Offer 35. 复杂链表的复制
具体打卡内容：

时间On 空间On
class Solution {
public Node copyRandomList(Node head) {
Node cur = head;
Map<Node, Node> map = new HashMap<>();
while(cur != null){
map.put(cur, new Node(cur.val));
cur = cur.next;
}
cur = head;
while(cur != null){
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
return map.get(head);
}
}

Renasc 普通 2025年1月2日下午3:07

本打卡对应问题：【位运算专题】剑指 Offer 56 – I. 数组中数字出现的次数
具体打卡内容：

时间复杂度O(N)，空间复杂度O(1)

class Solution {
    public int[] sockCollocation(int[] sockets) {
        int x = 0, y = 0, z = 0, m = 1;
        // 先找到两个不同的数的异或值
        for (int socket :sockets) {
            z ^= socket;
        }

        // 找到倒数第一个不为0的值
        while ((z & m) == 0) {
            m <<= 1;
        }

        // 根据m划分为两个子数组，每个子数组都与x,y进行异或操作
        for (int socket : sockets) {
            if ((m & socket) == 0) {
                x ^= socket;
            } else {
                y ^= socket;
            }
        }
        return new int[] {x, y};
    }
}

陆狗陆狗普通 2025年1月2日上午9:24

本打卡对应问题：【动态规划专题】LeetCode 198. 打家劫舍
具体打卡内容：

解题思路
– dp[i] 最大的金额
– 如果i-1已经拿取，那么金额为dp[i]=dp[i-1]；如果i-1没有拿取（i-2可能也没拿，但是用dp[i-2]是没问题的），那么金额为dp[i]=dp[i-2]+nums[i]
【题解1】常规的dp写法即可，关键是判断dp[i-1]和dp[i]的过渡关系

class Solution {
    public int rob(int[] nums) {
        // dp[i] 最大的金额
        // 如果i-1已经拿取，那么金额为dp[i]=dp[i-1]；如果i-1没有拿取（i-2可能也没拿，但是用dp[i-2]是没问题的），那么金额为dp[i]=dp[i-2]+nums[i]
        if (nums.length == 1) {
            return nums[0];
        }
        int[] dp = new int[nums.length];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < nums.length; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[nums.length - 1];
    }
}

陆狗陆狗普通 2024年12月31日下午10:00

本打卡对应问题：【动态规划专题】LeetCode 42. 接雨水
具体打卡内容：

解题思路
– 定义2个dp： int[] leftdp 在i时左边的最大值； int[] rightdp 在i时右边的最大值
– 在i点，取 leftdp[i]、rightdp[i]的最小值最为容器的高
– 容量=宽（1）*高，其中高=容器的高-height[i]
【题解1】

class Solution {
    public int trap(int[] height) {
        // 定义2个dp： int[] leftdp 在i时左边的最大值； int[] rightdp 在i时右边的最大值
        // 在i点，取 leftdp[i]、rightdp[i]的最小值最为容器的高
        // 容量=宽1*高，其中高=容器的高-height[i]

        int[] leftdp = new int[height.length];
        leftdp[0] = height[0];
        for (int i = 1; i < height.length; i++) {
            leftdp[i] = Math.max(leftdp[i - 1], height[i]);
        }

        int[] rightdp = new int[height.length];
        rightdp[height.length - 1] = height[height.length - 1];
        // 【错误点】rightdp初始化写成了leftdp
        for (int i = height.length - 2; i >= 0; i--) {
            rightdp[i] = Math.max(rightdp[i + 1], height[i]);
        }

        // 遍历(开头和结尾都没办法接水)
        int result = 0;
        for (int i = 1; i < height.length - 1; i++) {
            // 容器的高
            int boxHeight = Math.min(leftdp[i], rightdp[i]);
            // 能用到的高
            result = result + (boxHeight - height[i]);

        }

        return result;

    }
}

错误点1：rightdp初始化写成了leftdp

晓宇普通 2024年12月31日下午9:22

本打卡对应问题：【动态规划专题】剑指 Offer 49. 丑数
具体打卡内容：

class Solution {
public:
    int nthUglyNumber(int n) {
        // 思路：dp[i] 第i个丑数是多少
        if(n <= 2) return n;
        // 1 2 3 5
        vector<int> dp(n);
        dp[0] = 1;
        int a = 0,b = 0,c = 0;
        for(int i = 1;i < n;i++){
            dp[i] = min(dp[a] * 2,min(dp[b] * 3,dp[c] * 5));
            if(dp[i] == dp[a] * 2) a++;
            if(dp[i] == dp[b] * 3) b++;
            if(dp[i] == dp[c] * 5) c++;
        }
        return dp[n - 1];



    }
    // o(n) o(n)
};

為愛而生普通 2024年12月31日下午5:59

本打卡对应问题：【链表专题】剑指 Offer 24. 反转链表
具体打卡内容：

“`java
//时间On^2 内存On
/**
* 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 trainningPlan(ListNode head) {
if (head == null)
return null;
ListNode p = head;
int cnt = 0;
ListNode reverse = new ListNode();
ListNode cur = reverse;
while (p.next != null) {
p = p.next;
cnt++;
ListNode node = new ListNode();
cur.next = node;
cur = cur.next;
}
cur = reverse;
int tmp = cnt;
for (int i = 1; i <= cnt + 1; i++) { p = head; for (int j = 1; j <= tmp; j++) p = p.next; tmp--; cur.val = p.val; cur = cur.next; } return reverse; } }

Kisara 普通 2024年12月31日上午9:02

本打卡对应问题：【动态规划专题】剑指 Offer 60. n个骰子的点数
具体打卡内容：

dp解法

class Solution {
    public double[] statisticsProbability(int num) {
        double[] dp = new double[6];
        Arrays.fill(dp, 1.0 / 6);


        for (int n = 2; n <= num; n++) {
            double[] temp = new double[5 * n + 1];
            for (int i = 0; i < dp.length; i++) {
                for (int j = 0; j < 6; j++) {
                    temp[i + j] += dp[i] / 6.0;
                }
            }
            dp = temp;
        }

        return dp;
    }
}

Kisara 普通 2024年12月31日上午9:00

本打卡对应问题：【动态规划专题】剑指 Offer 49. 丑数
具体打卡内容：

1

class Solution {
    public int nthUglyNumber(int n) {
        // 定义 dp 数组保存前 n 个丑数
        int[] dp = new int[n];
        dp[0] = 1; // 第一个丑数是 1

        // 定义三个指针分别对应丑数的质因数 2, 3, 5
        int p2 = 0, p3 = 0, p5 = 0;

        for (int i = 1; i < n; i++) {
            // 丑数是前面的丑数分别乘以 2, 3, 5 的最小值
            int next2 = dp[p2] * 2;
            int next3 = dp[p3] * 3;
            int next5 = dp[p5] * 5;

            // 选择最小值作为下一个丑数
            int nextUgly = Math.min(next2, Math.min(next3, next5));
            dp[i] = nextUgly;

            // 更新指针
            if (nextUgly == next2) p2++;
            if (nextUgly == next3) p3++;
            if (nextUgly == next5) p5++;
        }

        return dp[n - 1];
    }
}

陆狗陆狗普通 2024年12月30日下午11:36

本打卡对应问题：【动态规划专题】剑指 Offer 60. n个骰子的点数
具体打卡内容：

解题思路
– dp[n][j] ，n表示是第几个骰子。j表示总点数。这个题目允许存在空间浪费。n肯定比n-1的j的范围要大。比如dp[1]的j的范围是1~6，dp[2]的j的范围是2~12
– dp[n][j] 和dp[n-1][n-1的j]的关系？j的构成要考虑dp[n]点数是1,2,3,4,5,6时和dp[n-1]不同j的组合。
【题解1】

class Solution {
    public double[] statisticsProbability(int num) {
        // dp[n][j] ，n表示是第几个骰子。j表示总点数。这个题目允许存在空间浪费。n肯定比n-1的j的范围要大
       //  dp[n][j] 和dp[n-1][j前面]的关系？j的构成要考虑dp[n]点数是1,2,3,4,5,6时和dp[n-1]的组合
        // 这里长度为什么是+1，是为了写代码理解
        double[][] dp = new double[num + 1][num * 6 + 1];
        // 初始化
        for (int j = 1; j <= 6; j++) {
            dp[1][j] = 1.0 / 6;
        }
        // 骰子个数的循环
        for (int n = 2; n <= num; n++) {
            // 点数的循环
            for (int j = n; j <= n * 6; j++) {
                // 当前骰子的点数
                for (int k = 1; k <= 6; k++) {
                    // 比如当前总点数是2，当前骰子的点数是1，那么上一个的点数是1的有效
                    // 比如当前总点数是3，当前骰子的点数是1，那么上一个的点数是1,2的有效
                    // 总点数-当前点数=上一个骰子的点数和>=上一个dp的最小点数
                    if (j - k >= n - 1) {
                        dp[n][j] = dp[n][j] + dp[n - 1][j - k] * (1.0 / 6);
                    }
                }
            }
        }

        // 目标的数组
        // 目标数组里面骰子总点数的范围 （num~num*6）,因而个数是num * 6 - num + 1=5*num+1
        double[] result = new double[num * 5 + 1];
        for (int j = num; j <= num * 6; j++) {
            // 下标从0开始
            result[j - num] = dp[num][j];
        }
        return result;

    }
}

晓宇普通 2024年12月30日下午10:15

本打卡对应问题：【动态规划专题】剑指 Offer 48. 最长不含重复字符的子字符串
具体打卡内容：

class Solution {
public:
    int dismantlingAction(string arr) {
        if(arr.size() == 0) return 0;
        int num = 1;
        int n = arr.size();
        vector<int> dp(n); // 以i招式为结尾连续不重复的招式数
        unordered_map<char,int> map; //  string idx
        map[arr[0]] = 0; 
        dp[0] = 1;
        for(int i = 1; i < n; i++){
            if(map.find(arr[i]) == map.end()){
                dp[i] = dp[i - 1] + 1; 
            }else{
                int k = map[arr[i]];
                dp[i] = i- k <= dp[i - 1] ? i - k : dp[i-1] + 1;

            }
            num = max(num,dp[i]);
            map[arr[i]] = i;
        }
        return num;
        // o(n) o(n)
    }
};

class Solution {
public:
    int dismantlingAction(string arr) {
        if(arr.size() == 0) return 0;
        int num = 1;
        unordered_map<char,int> map; //  string idx
        map[arr[0]] = 0; 
        int dp = 1;// 以i招式为结尾连续不重复的招式数
        for(int i = 1; i < arr.size(); i++){
            if(map.find(arr[i]) == map.end()){
                dp += 1; 
            }else{
                int k = map[arr[i]];
                dp = i- k <= dp? i - k : dp + 1;

            }
            num = max(num,dp);
            map[arr[i]] = i;

        }
        return num;
        // o(n) o(1)

    }
};

陆狗陆狗普通 2024年12月30日下午10:06

本打卡对应问题：【动态规划专题】剑指 Offer 49. 丑数
具体打卡内容：

解题思路
– 按照顺序去2/3/5的倍数去找
– 初始的2,3,5
– 2：22=4，23=6,25=10
– 3: 32=6,33=9,35=15
– 5：52=10，53=15，55=25
– 存在两个问题，一个是重复，另外一个是可能会跳过一些数字
– 如何解决呢？需要用2,3,5三个独立指针去遍历dp[]。把dp[]作为备选池都可以分别去乘以2,3,5，但是我们需要先把最小的作为新的dp[]追加进去，注意并不是2,3,5依次按顺序去乘以，比如22=4,23=6乘以2次，都比52=10的1次要大。因而2,3，5分别去维护独立的index，然后慢慢去++
【题解1】

class Solution {
    public int nthUglyNumber(int n) {
        // 按照顺序去2/3/5的倍数去找
        // 初始的2,3,5
        // 2：2*2=4，2*3=6,2*5=10
        // 3: 3*2=6,3*3=9,3*5=15
        // 5：5*2=10，5*3=15，5*5=25
        // 存在两个问题，一个是重复，另外一个是可能会跳过一些数字
        // 如何解决呢？把dp[]作为备选池都可以分别去乘以2,3,5，但是我们需要先把最小的作为新的dp[]，注意并不是2,3,5依次按顺序去乘以，比如2*2=4,2*3=6乘以2次，都比5*2=10的1次要大。因而2,3，5分别去维护独立的index，然后慢慢去++
        int[] dp = new int[n];
        dp[0] = 1;
        int n2 = 0;
        int n3 = 0;
        int n5 = 0;
        for (int i = 1; i < n; i++) {
            int nextNumber = Math.min(Math.min(dp[n2] * 2, dp[n3] * 3), dp[n5] * 5);
            dp[i] = nextNumber;
            if (nextNumber == dp[n2] * 2) {
                n2++;
            }
            if (nextNumber == dp[n3] * 3) {
                n3++;
            }
            if (nextNumber == dp[n5] * 5) {
                n5++;
            }
        }
        return dp[n - 1];

    }
}

晓宇普通 2024年12月30日下午9:03

本打卡对应问题：【动态规划专题】剑指 Offer 47. 礼物的最大价值
具体打卡内容：

// 类似最小路径和
class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        if(frame.empty() || frame[0].empty()) return 0;
        // 定义dp
        // 写出dp公式 dp[i][j] += max(dp[i-1][j], dp[i][j-1])
        // 确定初值
        int m = frame.size(), n = frame[0].size();
        vector<vector<int>> dp(m,vector<int>(n));
        dp[0][0] = frame[0][0];
        for(int i = 1; i < m; i++)
            dp[i][0] = frame[i][0] + dp[i - 1][0];
        for(int j = 1; j < n; j++) 
            dp[0][j] += frame[0][j] + dp[0][j - 1];
        for(int i = 1;i < m; i++){
            for(int j = 1;j < n; j++){
                dp[i][j] = frame[i][j] + max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[m - 1][n - 1];
    }
    // o(m * n) o(m * n)
};

class Solution {
public:
    int jewelleryValue(vector<vector<int>>& frame) {
        if(frame.empty() || frame[0].empty()) return 0;
        // 定义dp
        // 写出dp公式 dp[i][j] += max(dp[i-1][j], dp[i][j-1])
        // 确定初值
        // 优化：一维dp,当前行的dp最多只用到上一行
        int m = frame.size(), n = frame[0].size();
        vector <int> dp(n);
        dp[0] = frame[0][0];

        for(int j = 1; j < n; j++) 
            dp[j] += frame[0][j] + dp[j - 1];
        for(int i = 1;i < m; i++){
            dp[0] = dp[0] + frame[i][0];
            for(int j = 1;j < n;j++)
                dp[j] = frame[i][j] + max(dp[j], dp[j - 1]);

        }
        return dp[n - 1];
    }
    // o(m * n) o(m)
};

秋山丽奈普通 2024年12月30日下午8:39

本打卡对应问题：【杂题】剑指 Offer 62. 圆圈中最后剩下的数字
具体打卡内容：

class Solution {
    public int iceBreakingGame(int n, int m) {
        int ans = 0;
        // 最后一轮剩下2个人，所以从2开始反推
        for (int i = 2; i <= n; i++) {
            ans = (ans + m) % i;
        }
        return ans;
    }
}

秋山丽奈普通 2024年12月30日下午8:13

本打卡对应问题：【杂题】剑指 Offer 10- II. 青蛙跳台阶问题
具体打卡内容：

思路：递归+记忆化

class Solution {
    HashMap<Integer, Integer> memo = new HashMap<>();

    public int trainWays(int num) {
        if(num <= 0){
            return 1;
        }

        if(num == 1){
            return 1;
        }

        if(this.memo.getOrDefault(num, -1) != -1){
            return this.memo.get(num);
        }

        int temp = (trainWays(num-1) + trainWays(num-2)) % 1000000007 ;
        this.memo.put(num, temp);
        return temp;

    }
}

秋山丽奈普通 2024年12月30日下午8:09

本打卡对应问题：【杂题】剑指 Offer 10- I. 斐波那契数列
具体打卡内容：

思路：递归+记忆化

class Solution {

    HashMap<Integer, Integer> memo = new HashMap<>();

    public int fib(int n) {
        if(n <= 0){
            return 0;
        }

        if(n == 1){
            return 1;
        }

        if( this.memo.getOrDefault(n, -1) != -1){
            return this.memo.get(n);
        }

        int temp = (fib(n-1) + fib(n-2)) % 1000000007;;
        this.memo.put(n, temp);

        return temp;

    }
}