最新打卡动态-跟着帅地玩转校招，刷爆各类算法题帅地玩Offer

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;

    }
}

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

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

思路：递归处理

class Solution {
    public int minDistance(String word1, String word2) {

       char[] word1List = word1.toCharArray();
       char[] word2List = word2.toCharArray();

        int[][] ans = new int[word1List.length+1][word2List.length+1];

        for(int i = 0; i < word1List.length+1; i ++){
            // 从 word1[0...i] 转为word2[0]  需要 i 步 
            ans[i][0] = i;
        }

        for(int i = 0; i < word2List.length+1; i ++){
            // 从 word2[0...i] 转为word1[0]  需要 i 步 
            ans[0][i] = i;
        }

        for(int i = 1; i <= word1List.length; i ++){
            for(int j = 1; j <= word2List.length; j ++){
                if(word1List[i-1] == word2List[j-1]){
                    // 当前元素相同
                    ans[i][j] = 1+Math.min(ans[i-1][j-1]-1, Math.min(ans[i-1][j], ans[i][j-1]));
                }else{
                    ans[i][j] = 1+Math.min(ans[i-1][j-1], Math.min(ans[i-1][j], ans[i][j-1]));
                }
            }
        }

        return ans[word1List.length][word2List.length];


    }
}

笨笨小子永久会员 2024年12月30日下午4:15

本打卡对应问题：回溯通用模版🌟🌟🌟🌟🌟
具体打卡内容：

打卡

Aatorx 永久会员 2024年12月30日下午3:52

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

class Solution {
public:
    vector<int> spiralArray(vector<vector<int>>& array) {
        vector<int> res;
        if(array.empty()) {
            return res;
        }
        int b = array.size() - 1;
        int r = array[0].size() - 1;
        int l = 0;
        int t = 0;
        while(true) {
            for(int j = l; j <= r; j++) {
                res.push_back(array[t][j]);
            }
            t++;
            if(t > b) break;
            for(int i = t; i <= b; i++) {
                res.push_back(array[i][r]);
            }
            r--;
            if(r < l) break;
            for(int j = r; j >= l; j--) {
                res.push_back(array[b][j]);
            }
            b--;
            if(b < t) break;
            for(int i = b; i >= t; i--) {
                res.push_back(array[i][l]);
            }
            l++;
            if(l > r) break;
        }
        return res;
    }
};

时间复杂度O(Mn)，空间复杂度O(Mn)。

Aatorx 永久会员 2024年12月30日下午3:20

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

class Solution {
public:
    bool findTargetIn2DPlants(vector<vector<int>>& plants, int target) {
        int i = plants.size() - 1;
        int j = 0;
        while(i >= 0 && j < plants[0].size()) {
            if(plants[i][j] == target) {
                return true;
            }else if(plants[i][j] > target) {
                i--;
            }else{
                j++;
            }
        }
        return false;
    }
};

类似平衡二叉树查找。
时间复杂度O(M+N)，空间复杂度O(1)。

Aatorx 永久会员 2024年12月30日下午3:03

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

class Solution {
public:
    int findRepeatDocument(vector<int>& documents) {
        int res = 0;
        while(res < documents.size()) {
            if(documents[res] == res) {
                res++;
                continue;
            }
            if(documents[documents[res]] == documents[res]) {
                return documents[res];
            }
            swap(documents[documents[res]], documents[res]);
        }
        return -1;
    }
};

原地交换法，时间复杂度O(N)，空间复杂度O(1)。

Aatorx 永久会员 2024年12月30日下午2:39

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

class Solution {
public:
    int iceBreakingGame(int num, int target) {
        int res = 0;
        for(int i = 2; i <= num; i++) {
            res = (res + target) % i;
        }
        return res;
    }
};

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

晓宇普通 2024年12月29日下午3:23

本打卡对应问题：【动态规划专题】剑指 Offer 63. 股票的最大利润
具体打卡内容：

class Solution {
public:
// 思路：出售时刻在购得时刻之后，对于当前时刻，最大收益是在未来最大售价时抛售。从末尾时刻向起始时刻求解，避免在重复序列求最大售价。
    int bestTiming(vector& prices) {
        if(prices.empty()) return 0;
        int n = prices.size();
 
        int res = 0;
        int max_price = prices[n - 1];  // 最大出售价格
        for(int i = n - 2; i >= 0; i--){
            if(prices[i] > max_price) max_price = prices[i];
            res = max(max_price - prices[i], res);
        }
        return res;
    }
    // o(n) o(1)
};

晓宇普通 2024年12月29日下午3:09

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

class Solution {
public:
// 从右上往左下搜索
    bool findTargetIn2DPlants(vector>& plants, int target) {
        if(plants.empty() || plants[0].empty()) return false;
        int m = plants.size();
        int n = plants[0].size();

        for(int i = 0;i < m;i++){
            for(int j = n - 1;j >= 0; j--){
                if(plants[i][j] > target) continue;
                else if(plants[i][j] == target) return true;
                else break;
            }
        }
        return false;
    }
    // o(n+m) o(1)
};

Renasc 普通 2024年12月29日下午1:52

本打卡对应问题：【位运算专题】剑指 Offer 16. 数值的整数次方
具体打卡内容：

时间复杂度O(logN), 空间复杂度O(1)

class Solution {
    public double myPow(double x, int n) {
        double res = 1; // 保存结果
        long y = n; // 取值

        // 如果指数为负数，则取指数的绝对值，并将取底数的倒数
        if (y < 0) {
            y = -y;
            x = 1 / x;
        }

        while (y > 0) {
            // 按照二进制的方式，如果当前位为1，则乘以对应的x^n
            if (y % 2 == 1) {
                res *= x;
            }

            x = x * x;
            y = y / 2;  // y右移
        }

        return res;
    }
}

晓宇普通 2024年12月29日下午12:43

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

// 螺旋遍历
class Solution {
public:
    vector<int> spiralArray(vector<vector<int>>& array) {
        if(array.empty() || array[0].empty()) return vector<int>();
        vector<int> ans;
        int lef = 0,rit = array[0].size() - 1,bot = array.size() - 1,top = 0;
        while(true){
            for(int i = top,j = lef;j <= rit;j++){
                ans.push_back(array[i][j]);
            }
            top += 1; // 下移一层
            if(top > bot) break;
            for(int i = top,j = rit;i <= bot;i++){
                ans.push_back(array[i][j]);
            }
            rit -= 1; // 左移一层
            if(rit < lef) break;
            for(int i = bot,j = rit;j >= lef;j--){
                ans.push_back(array[i][j]);
            }
            bot -= 1; // 上移一层
            if(bot < top) break;
            for(int i = bot,j = lef;i >= top ;i--){
                ans.push_back(array[i][j]);
            }
            if(++lef > rit) break;// 右移一层
        }
        return ans;
    }
    // o(n^2) o(1)
};

Renasc 普通 2024年12月29日上午10:53

本打卡对应问题：【位运算专题】剑指 Offer 15. 二进制中1的个数
具体打卡内容：

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

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int ret = 0;
        while (n != 0) {
            n &= (n-1);  // 消除最右边的一个1
            ret ++;
        }
        return ret;
    }
}

岱永久会员 2024年12月28日下午7:56

本打卡对应问题：【二叉树专题】剑指 Offer 26. 树的子结构
具体打卡内容：

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        // 若A与B其中一个为空,立即返回false
        if(A== null ||B == null) return false;
        // B为A的子结构有3种情况,满足任意一种即可:
        // 1.B的子结构起点为A的根节点,此时结果为recur(A,B)
        // 2.B的子结构起点隐藏在A的左子树中,而不是直接为A的根节点,此时结果为isSubStructure(A.left, B)
        // 3.B的子结构起点隐藏在A的右子树中,此时结果为isSubStructure(A.right, B)
        return recur(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }
    /*
    判断B是否为A的子结构,其中B子结构的起点为A的根节点
    */
    private boolean recur(TreeNode A, TreeNode B) {
        // 若B走完了,说明查找完毕,B为A的子结构
        if(B == null) {
            return true;
        }
        // 若B不为空并且A为空 或者 A与B的值不相等,直接可以判断B不是A的子结构
        if(A == null || A.val != B.val) {
            return false;
        }
        // 当A与B当前节点值相等,若要判断B为A的子结构
        // 还需要判断B的左子树是否为A左子树的子结构 && B的右子树是否为A右子树的子结构
        // 若两者都满足就说明B是A的子结构,并且该子结构以A根节点为起点
        return recur(A.left, B.left) && recur(A.right, B.right);
    }
}

岱永久会员 2024年12月28日下午7:54

本打卡对应问题：【二叉树专题】剑指 Offer 07. 重建二叉树
具体打卡内容：

class Solution {
    HashMap<Integer,Integer> map = new HashMap<>();
    int[] preorder;//保留的先序遍历，方便递归时依据索引查看先序遍历的值
    public TreeNode deduceTree(int[] preorder, int[] inorder) {
        this.preorder = preorder;
        // 将中序遍历的值及索引放在map中，方便递归时获取左子树与右子树的数量及其根的索引
        for(int i = 0; i < inorder.length ; i++){
            map.put(inorder[i],i);
        } 
        //三个索引分别为
        //当前根的的索引
        //递归树的左边界，即数组左边界
        //递归树的右边界，即数组右边界
        return recur(0,0,inorder.length-1);
    }

    TreeNode recur(int pre_root, int in_left , int in_right){
        if(in_left >in_right)return null;
        TreeNode root = new TreeNode(preorder[pre_root]);//获取root节点
        int idx = map.get(preorder[pre_root]);//获取在中序遍历中根节点所在索引，以方便获取左子树的数量
        //左子树的根的索引为先序中的根节点+1
        //递归左子树的左边界为原来的中序in_left
        //递归左子树的右边界为中序中的根节点索引-1
        root.left = recur(pre_root+1,in_left,idx-1);
        //右子树的根的索引为先序中的 当前根位置 + 左子树的数量 + 1
        //递归右子树的左边界为中序中当前根节点+1
        //递归右子树的右边界为中序中原来右子树的边界
        root.right = recur(pre_root+(idx-in_left)+1,idx+1,in_right);
        return root;
    }
}

晓宇普通 2024年12月28日下午6:53

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

// 下标交换
class Solution {
public:
    int findRepeatDocument(vector<int>& documents) {
        for(int i = 0;i < documents.size();i++){
            while(i != documents[i]){ // 多个元素对应同一个下标
                if(documents[i] == documents[documents[i]]){
                    return documents[i];
                }
                // document[i] document[document[i]] 将元素换到正确位置
                int k = documents[documents[i]];
                documents[documents[i]] = documents[i];
                documents[i] = k;
            }
        }
        return -1;
    }
    // o1 on
};

晓宇普通 2024年12月28日下午5:35

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

class Solution {
public:
    int iceBreakingGame(int num, int target) {
        // 每次淘汰后，重新计算环中剩余人数时的 新起始索引 new_idx = (old_idx + tar) % n
        if(num == 0) return num;
        return (iceBreakingGame(num - 1,target) + target) % num;
        // o(n) o(1)
    }
};

class Solution {
public:
    int iceBreakingGame(int num, int target) {
        // 每次淘汰前，重新计算环中淘汰前人数时的 新起始索引 new_idx = (old_idx + tar) % n
        int res = 0; // 初始索引
        for (int i = 2; i <= num; i++) { 
            res = (res + target) % i; 
        }
        return res; 
        // on o1
    }
};
/*****循环链表*****/
struct Node{
    int val;// 节点的值（编号）
    Node *next;  // 指向下一个节点
    Node (int x) : val(x) , next(nullptr){}
};

class Solution {
public:
    int iceBreakingGame(int num, int target) {
        if(num <= 1) return 0;
        if(target == 1) return num - 1;
        // 创建循环链表
        Node *head = new Node(0);
        Node *p = head;
        for(int i = 1; i < num;i++){
            Node *node = new Node(i);
            p->next = node;
            p = p->next;
        }
        p->next = head;
        // 逐一搜索
        Node *cur = head;
        while(cur->next != cur){


            for(int i = 1;i < target - 1;i++){ // 注意是从当前开始数
                cur = cur->next;
            }
            // 移除节点
            Node *toDelete = cur->next;
            cur->next = cur->next->next;
            delete toDelete;

            cur = cur->next;

        }
        int res = cur->val;
        delete cur;
        return res;
        // o(n^2) o(n)
    }
};