Spermalow 普通 2023年1月27日 下午2:45

    本打卡对应问题:【学习建议】关于做本项目的几点学习建议(视频讲解)
    具体打卡内容:

    已完成阅读

    Spermalow 普通 2023年1月27日 下午2:44

    本打卡对应问题:【重要】如何把本项目写进简历 + 如何准备面试
    具体打卡内容:

    打卡

    Spermalow 普通 2023年1月27日 下午2:37

    本打卡对应问题:【任务1】创建一个属于自己的github仓库
    具体打卡内容:

    gitee项目仓库地址:https://gitee.com/supermalow/from-zero-to-one

    Mumu 普通 2023年1月21日 下午5:18

    本打卡对应问题:【重要】如何把本项目写进简历 + 如何准备面试
    具体打卡内容:

    打卡

    mpweixin用户 普通 2023年1月21日 下午5:15

    本打卡对应问题:【任务1】你目前算法都学过啥?
    具体打卡内容:

    70 没有 懂

    PatNick 普通 2023年1月20日 下午9:10

    本打卡对应问题:【动态规划专题】LeetCode 322. 零钱兑换
    具体打卡内容:
    def coinChange(coins: list[int], amount: int) -> int:
    
        if amount == 0:
            return 0
        dp = [-1 for _ in range(amount + 1)]
    
        # dp[i]代表凑成面值为i的最少硬币个数
        dp[0] = 0
    
        for i in range(1, amount + 1):
            min_ = float("inf")
            # 硬币的面值
            for j in coins:
                if i - j >= 0 and dp[i-j] != -1:
                    min_ = min(dp[i - j] + 1, min_)
    
    
            if min_ != float("inf"):
                dp[i] = min_
    
        return dp[-1]
    
    # 优化:思路同上面一样,但两层for循环首先循环coins,但不太好理解
    def coinChange( coins: list[int], amount: int) -> int:
        dp = [float('inf')] * (amount + 1)
        dp[0] = 0
    
        # 与上面的循环方式不同,这里先循环coins
        for coin in coins:
            #内层循环在coin的基础上可以省去计算根本不用计算的循环步骤
            # 例如2块钱的硬币,如果算dp[1]肯定是-1不用算,所以dp[i]的范围肯定是要比硬币的面值大的
            # 但这种方式就不像上面那样一次性的算出dp[i]的值
            # 例如上面的方法如果计算dp[11]就等于min(dp[10],dp[9],dp[6])+1,这样一次性算出结果
            # 如果按照这个循环方式,计算dp[11]时,首先基于1元硬币的情况下,dp[11]=min(dp[11],dp[11-1]+1),当循环到2元硬币时,dp[11]=min(dp[11],dp[11-2]+1)……直到硬币的面值循环完,就是在循环硬币面值的过程中动态找到dp[10],dp[9],dp[6]的最小值
            for x in range(coin, amount + 1):
                dp[x] = min(dp[x], dp[x - coin] + 1)
        return dp[amount] if dp[amount] != float('inf') else -1
    
    PatNick 普通 2023年1月20日 下午7:43

    本打卡对应问题:【动态规划专题】LeetCode 198. 打家劫舍
    具体打卡内容:
    # dp为一维数组
    def rob(nums: list[int]) -> int:
        if len(nums) == 0:
            return 0
        if len(nums) == 1:
            return nums[0]
    
        dp = [0] * len(nums)
    
        # dp[i]是i时盗窃的最高金额
        dp[0] = nums[0]
        dp[1] = max(nums[0], nums[1])
    
        for i in range(2, len(nums)):
            dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
    
        return dp[-1]
    
    
    
    # 将空间复杂度优化为O(1)
    # dp为单变量,同时还需要一个变量保存i-2的数据
    def rob(nums: list[int]) -> int:
        if len(nums) == 0:
            return 0
        if len(nums) == 1:
            return nums[0]
    
        p = nums[0]
        dp = max(nums[0],nums[1])
    
        # dp[i]是i时盗窃的最高金额
    
    
        for i in range(2, len(nums)):
            temp = dp
            dp = max(p + nums[i], dp)
            p = temp
    
    
        return dp
    
    PatNick 普通 2023年1月20日 下午7:00

    本打卡对应问题:【阅读补充】时间/空间复杂度如何计算?
    具体打卡内容:

    打卡

    PatNick 普通 2023年1月20日 下午6:59

    本打卡对应问题:【动态规划专题】LeetCode 42. 接雨水
    具体打卡内容:
    def trap(height: list[int]) -> int:
        if len(height) == 0:
            return 0
        res = 0
        left = 0
        right = len(height) - 1
    
        # l_max存放【0。left】上的最大值
        l_max = height[0]
        # r_max存放[right,-1]上的最大值
        r_max = height[-1]
    
        while left <= right:
            l_max = max(l_max,height[left])
            r_max = max(r_max,height[right])
    
            if l_max < r_max:
                res += (l_max - height[left])
                left += 1
            else:
                res += (r_max - height[right])
                right -= 1
        return res
    
    PatNick 普通 2023年1月20日 下午4:33

    本打卡对应问题:【动态规划专题】剑指 Offer 60. n个骰子的点数
    具体打卡内容:
    def dicesProbability(n: int) -> list[float]:
        # 定义dp[i][j]含义:当骰子个数为i,点数之和为j时,有dp[i][j]中组合
        dp = [[0 for __ in range(6 * n + 1)] for _ in range(n + 1)]
    
        # n个骰子话,点数之和的取值范围是[n,6n],所以个数就是5n+1
        res = [0] * (5 * n + 1)
        # 初始化
        for _ in range(1, 7):
            dp[1][_] = 1
    
        for i in range(2, n + 1):
            # 注意这里点数和的取值范围是取决于骰子数i的
            for j in range(i, 6 * i + 1):
                # 递推式的含义:i个骰子点数和为j的组合数量可以等于i-1个骰子点数和为j-1的组合数加上一个"1"朝上的骰子,或者是i-1个骰子点数和为j-2的组合数加上一个"2"朝上的骰子,……
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j - 2] + dp[i - 1][j - 3] + dp[i - 1][j - 4] + dp[i - 1][j - 5] + \
                           dp[i - 1][j - 6]
    
    
        # n个骰子,朝上点数之和一共有6^n种组合
        total = pow(6, n)
        index = 0
        for _ in range(n, 6 * n + 1):
            # 计算每种点数和组合数占总组合数的比
            res[index] = dp[n][_] / total
            index += 1
    
        return res
    
    PatNick 普通 2023年1月20日 上午11:48

    本打卡对应问题:【动态规划专题】剑指 Offer 49. 丑数
    具体打卡内容:
    def nthUglyNumber(n: int) -> int:
        if n == 0:
            return None
        if n == 1:
            return 1
        # 规定dp【i】代表第i个丑数
        dp = [0 for _ in range(n+1)]
        dp[1] = 1
        a = b = c = 1
    
        for i in range(2,n+1):
            dp[i] = min(dp[a]*2,dp[b]*3,dp[c]*5)
            if dp[i] == dp[a]*2:
                a += 1
            if dp[i] == dp[b]*3:
                b += 1
            if dp[i] == dp[c]*5:
                c += 1
        return dp[-1]
    
    
    PatNick 普通 2023年1月20日 上午10:31

    本打卡对应问题:【动态规划专题】剑指 Offer 19. 正则表达式匹配
    具体打卡内容:
    m = len(s)
        n = len(p)
        # dp[i][j]表示s长度为i,p长度为j时,s与p是否匹配,因为是从长度为0开始的,所以这里dp的长度为【m+1】【n+1】
        dp = [[False for _ in range(n+1)] for __ in range(m+1)]
    
        # 初始化
        dp[0][0] = True
    
    
        # 注意两个地方,
        # 1、dp中的索引是指长度,所以在对应到字符串中的时候都要减一,
        # 2、for循环遍历的是dp中的索引,所以右边界要加1
        for _ in range(2,n+1):
            if p[_-1] == '*':
                dp[0][_] =dp[0][_-2]
    
    
    
        for i in range(1,m+1):
            for j in range(1,n+1):
                if p[j-1] != "*":
                    if s[i-1] == p[j-1] or p[j-1] == ".":
                        dp[i][j] = dp[i-1][j-1]
    
                else:
                    # 如果和*前一个值不相等(而且不是".")最好的情况就是让*=0——不对前面的时进行重复,那就是和*往前两个的值进行比较
                    if p[j-2] != s[i-1] and p[j-2] != ".":
                        dp[i][j] = dp[i][j-2]
    
                    else:
                        #匹配0个or匹配1个or匹配多个
                        dp[i][j] = dp[i][j-2] or dp[i][j-1] or dp[i-1][j]
    
        return dp[-1][-1]
    
    
    lucca 普通 2023年1月20日 上午12:20

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

    逆向DP

    • 时间复杂度 O(NM)
    • 空间复杂度 O(NM)
    • 从右下到左上遍历,每个点的决策为:
      • 决定向左还是向右(取两点初值的最小值)
      • 考虑当前点的初值,用取到的最小值减去当前点给的血包(或者耗得血量)
      • 如果会加血,可以少设置点初值
      • 如果是耗血,要多设初值
    class Solution {
        public int calculateMinimumHP(int[][] g) {
            int n = g.length, m = g[0].length;
            int[][] f = new int[n+1][m+1];
            for (int i = 0; i <= n; i++) Arrays.fill(f[i], 0x3f3f3f3f);
            f[n][m-1] = f[n-1][m] = 1;
            for (int i = n - 1; i >= 0; i--) {
                for (int j = m - 1; j >= 0; j--) {
                    f[i][j] = Math.max(1, Math.min(f[i+1][j], f[i][j+1]) - g[i][j]);
                }
            }
            return f[0][0];
        }
    }
    
    lucca 普通 2023年1月19日 下午11:26

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

    二维DP 和 字符串DP的典型题

    class Solution {
        public int minDistance(String word1, String word2) {
            char[] c1 = ("." + word1).toCharArray();
            char[] c2 = ("." + word2).toCharArray();
            int n2 = c2.length - 1;
            int n1 = c1.length - 1;
    
            int[][] f = new int[n1+1][n2+1];
            for (int i = 0; i <= n1; i++) f[i][0] = i;
            for (int i = 0; i <= n2; i++) f[0][i] = i;
    
            for (int i = 1; i <= n1; i++) {
                for (int j = 1; j <= n2; j++) {
                    if (c1[i] == c2[j]) f[i][j] = f[i-1][j-1];
                    else {
                        f[i][j] = Math.min(
                            f[i-1][j],
                            Math.min(f[i][j-1], f[i-1][j-1])
                        ) + 1;
                    }
                }
            }
            return f[n1][n2];
        }
    }
    
    lucca 普通 2023年1月19日 下午11:14

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

    背包变式

    class Solution {
        public int coinChange(int[] coins, int amount) {
            int max = amount + 1;
            int[] f = new int[amount + 1];
            Arrays.fill(f, max);
            f[0] = 0;
            for (int i = 0; i < coins.length; i++) {
                for (int j = coins[i]; j <= amount; j++) {
                    f[j] = Math.min(f[j], f[j - coins[i]] + 1);
                }
            }
            return f[amount] == max ? -1 : f[amount];
        }
    }
    
    lucca 普通 2023年1月19日 下午10:58

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

    终于会一道

    class Solution {
        public int rob(int[] nums) {
            int[] f = new int[nums.length + 1];
            f[1] = nums[0];
            for (int i = 2; i <= nums.length; i++) {
                f[i] = Math.max(f[i-1], f[i-2]+nums[i-1]);
            }
            return f[nums.length];
        }
    }
    
    lucca 普通 2023年1月19日 下午10:42

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

    双指针,巧妙避开DP

    • 时间复杂度 O(N)
    • 空间复杂度 O(1)
    • 找到最大值,从左到最大值遍历一次,再从右到最大值遍历一次即可
    • 有多个最大值也没关系,任取一个即可,不影响结果
    class Solution {
        public int trap(int[] height) {
            int sum = 0;
            int maxId = 0;
            for (int i = 1; i < height.length; i++)
                if (height[i] > height[maxId]) maxId = i;
    
            int lmax = 0;
            for (int i = 0; i < maxId; i++) {
                if (lmax <= height[i]) lmax = height[i];
                else sum += (lmax - height[i]);
            }
            int rmax = 0;
            for (int i = height.length - 1; i > maxId; i--) {
                if (rmax <= height[i]) rmax = height[i];
                else sum += (rmax - height[i]);
            }
            return sum;
        }
    }
    
    lucca 普通 2023年1月19日 下午10:13

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

    DP一生之敌

    class Solution {
        public double[] dicesProbability(int n) {
            double[][] f = new double[n + 1][6 * n + 1];
            for (int i = 1; i <= 6; i++) f[1][i] = 1.0 / 6;
            for (int i = 1; i < n; i++) {
                for (int j = i; j <= 6 * i; j++) {
                    for (int k = 1; k <= 6; k++) {
                        f[i + 1][j + k] += f[i][j] / 6; 
                    }
                }
            }
            double[] ans = new double[5 * n + 1];
            for (int i = n, j = 0; i <= 6 * n; i++, j++) {
                ans[j] = f[n][i];
            }
            return ans;
        }
    }
    
    lucca 普通 2023年1月19日 下午9:50

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

    真的难,又是能看一下午的一道题目

    class Solution {
        public int nthUglyNumber(int n) {
            int[] v = new int[n];
            v[0] = 1;
            int i = 0, j = 0, k = 0;
            for (int idx = 1; idx < n; idx++) {
                v[idx] = Math.min(v[i]*2, Math.min(v[j]*3, v[k]*5));
                if (v[idx] == v[i] * 2) i++;
                if (v[idx] == v[j] * 3) j++;
                if (v[idx] == v[k] * 5) k++;
            }
            return v[n-1];
        }
    }
    
    PatNick 普通 2023年1月19日 上午9:35

    本打卡对应问题:【动态规划专题】剑指 Offer 48. 最长不含重复字符的子字符串
    具体打卡内容:
    # 单变量dp
    def lengthOfLongestSubstring2(s: str) -> int:
        if not s:
            return 0
    
        # 以字符s[i]结尾时,不重复子串长度为dp[i]
        dp = 1
    
        # 存放字符串的字符和索引的对应关系的
        map = {s[0]:0}
        res = 1
        for _ in range(1,len(s)):
            if not s[_] in map.keys():
                dp = dp + 1
            else:
                # 如果当前值已经遍历过了
                # 找到上一个出现这个值的索引
                k = map.get(s[_])
    
                # _ - k表示当前值与和它最近的相等的数之间的距离,如果这个距离大于dp[_-k],说明上一个重复的数是在组成dp[_-1]这个情况的子串内的,那dp[_]就要更新
                # 如果这个距离小于dp[_-k],说明上一个重复的数是在组成dp[_-1]这个情况的子串外的,那dp[_] = dp[_-1] + 1
                dp = _ - k if _ - k <= dp else dp + 1
    
            res = max(res,dp)
            map[s[_]] = _
    
    
        return res
    
    PatNick 普通 2023年1月18日 下午6:02

    本打卡对应问题:【动态规划专题】剑指 Offer 47. 礼物的最大价值
    具体打卡内容:
    def maxValue(grid: list[list[int]]) -> int:
        m = len(grid) # 行
        n = len(grid[0]) # 列
    
        # 定义dp,到达dp[i]表示某一行的i列所在位置的最小路径和
        # 每行动态更新
        dp = [-1] * n
        dp[0] = grid[0][0]
        # 初始化dp
        for _ in range(1,n):
            dp[_] = dp[_-1] + grid[0][_]
        for i in range(1,m):
            for j in range(0,n):
                # 对于第一列的元素dp[0]只能向下走,需要单独计算
                if j == 0:
                    dp[j] = dp[j] + grid[i][j]
                else:
                    dp[j] = max(dp[j-1],dp[j]) + grid[i][j]
    
        return dp[-1]
    
    PatNick 普通 2023年1月18日 下午5:57

    本打卡对应问题:【动态规划专题】剑指 Offer 63. 股票的最大利润
    具体打卡内容:
    def maxProfit(prices: list[int]) -> int:
        min = prices[0]
        max_ = 0
    
    <pre><code>for _ in range(1,len(prices)):
        if min > prices[_]:
            min = prices[_]
        else:
            # 更新最大利润
            max_ = max(prices[_] - min,max_)
    
    return max_
    </code></pre>
    
    
    PatNick 普通 2023年1月18日 下午5:13

    本打卡对应问题:【动态规划专题】LeetCode 64. 最小路径和
    具体打卡内容:
    m = len(grid) # 行
        n = len(grid[0]) # 列
    
        # 定义dp,到达dp[i]表示某一行的i列所在位置的最小路径和
        # 每行动态更新
        dp = [-1] * n
        dp[0] = grid[0][0]
        # 初始化dp
        for _ in range(1,n):
            dp[_] = dp[_-1] + grid[0][_]
        for i in range(1,m):
            for j in range(0,n):
                # 对于第一列的元素dp[0]只能向下走,需要单独计算
                if j == 0:
                    dp[j] = dp[j] + grid[i][j]
                else:
                    dp[j] = min(dp[j-1],dp[j]) + grid[i][j]
    
        return dp[-1]
    
    lucca 普通 2023年1月18日 下午3:57

    本打卡对应问题:【动态规划专题】剑指 Offer 19. 正则表达式匹配
    具体打卡内容:

    真的难

    • 时间复杂度 O(NM)
    • 空间复杂度 O(NM)
    class Solution {
        public boolean isMatch(String s, String p) {
            int n = s.length(), m = p.length();
            boolean[][] f = new boolean[n + 1][m + 1];
            f[0][0] = true;
            for (int j = 2; j <= m; j++) {
                if (p.charAt(j-1) == '*') f[0][j] = f[0][j-2];
            }
            for (int i = 1; i <= n; i++) {
                char si = s.charAt(i-1);
                for (int j = 1; j <= m; j++) {
                    char pj = p.charAt(j-1);
                    if (pj != '*') {    // 不为*, 一个一个判断即可
                        if (si == pj || pj == '.') f[i][j] = f[i-1][j-1];
                    } else {    // 为*, 涉及到p前一个字母的判断
                        // 没有前一个字母, *无意义 
                        if (j < 2) continue;
                        char pj2 = p.charAt(j - 2);
                        // 如果和p前一个字母匹配, 则去看s的前一个字母是否也匹配, 如果不匹配, 则看舍弃*是否匹配
                        if (si == pj2 || pj2 == '.') f[i][j] = f[i-1][j] || f[i][j-2];
                        // 如果不匹配, 舍弃*
                        else f[i][j] = f[i][j-2];
                    }
                }
            }
            return f[n][m];
        }
    }
    
    lucca 普通 2023年1月18日 下午2:09

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

    双指针

    • 时间复杂度O(N)
    • 空间复杂度O(N)
    class Solution {
        public int lengthOfLongestSubstring(String s) {
            int n = s.length();
            if (n < 2) return n;
    
            // 队列, 存储最长子字符串
            int[] q = new int[n];
            int hh = 0, tt = -1;
            // 可能不全是小写英文字符, 用map(吐槽一下Java的Map不咋好用)
            Map pos = new HashMap();
    
            int max = 0;
            for (int i = 0; i < n; i++) {
                char c = s.charAt(i);
                // 查找这个字符上一次出现的位置
                int oldP = pos.getOrDefault(c, -1);
                // 如果存好的子串包含了上一次出现的s[i], 则s[i]及之前都要舍弃
                while (hh <= tt && oldP >= q[hh]) hh++;
                // 把当前字符放进字串
                q[++tt] = i;
                // 更新最大长度
                max = Math.max(max, q[tt] - q[hh] + 1);
                // 更新s[i]上一次出现的位置
                pos.put(c, i);
            }
            return max;
        }
    }
    

    更简单的写法

    class Solution {
        public int lengthOfLongestSubstring(String s) {
            int[] last = new int[128];
            for(int i = 0; i < 128; i++) last[i] = -1;
    
            int n = s.length(), max = 0, st = 0;
            for (int i = 0; i < n; i++) {
                char c = s.charAt(i);
                st = Math.max(st, last[c] + 1);
                max = Math.max(max, i - st + 1);
                last[c] = i;
            }
            return max;
        }
    }
    
    lucca 普通 2023年1月18日 下午1:42

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

    和LeetCode 64. 最小路径和 同理,最小值改为最大值即可

    • 时间复杂度 O(NM)
    • 空间复杂度 O(1)
    class Solution {
        public int maxValue(int[][] g) {
            if (g.length == 0 || g[0].length == 0) return 0;
            int n = g.length, m = g[0].length;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (i == 0 && j == 0) continue;
                    if (i == 0) g[i][j] += g[i][j - 1];
                    else if (j == 0) g[i][j] += g[i - 1][j];
                    else g[i][j] += Math.max(g[i][j-1], g[i-1][j]);
                }
            }
            return g[n-1][m-1];
        }
    }
    
    lucca 普通 2023年1月18日 下午1:35

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

    迭代

    • 时间复杂度 O(N)
    • 空间复杂度 O(1)
    // 寻找 max(prices[j] -  prices[i]) [j > i]
    class Solution {
        public int maxProfit(int[] prices) {
            if (prices.length == 0) return 0;
            int min = prices[0];
            int ans = 0;
            for (int num : prices) {
                ans = Math.max(ans, num - min);
                min = Math.min(min, num);
            }
            return ans;
        }
    }
    
    lucca 普通 2023年1月18日 下午1:25

    本打卡对应问题:【动态规划专题】LeetCode 64. 最小路径和
    具体打卡内容:

    DP,类比杨辉三角

    • 时间复杂度 O(MN)
    • 空间复杂度 O(1)
    class Solution {
        public int minPathSum(int[][] g) {
            int n = g.length, m = g[0].length;
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (i == 0 && j == 0) continue;
                    if (i == 0) g[i][j] += g[i][j - 1];
                    else if (j == 0) g[i][j] += g[i - 1][j];
                    else g[i][j] += Math.min(g[i][j - 1], g[i - 1][j]);
                }
            }
            return g[n - 1][m - 1];
        }
    }
    
    lucca 普通 2023年1月18日 下午1:17

    本打卡对应问题:【动态规划专题】剑指 Offer 42. 连续子数组的最大和
    具体打卡内容:

    DP

    • 时间复杂度 O(N)
    • 空间复杂度 O(N)
    class Solution {
        public int maxSubArray(int[] nums) {
            int n = nums.length;
            int[] f = new int[n];
            f[0] = nums[0];
            int max = f[0];
            for (int i = 1; i < n; i++) {
                f[i] = Math.max(0, f[i - 1]) + nums[i];
                max = Math.max(max, f[i]);
            }
            return max;
        }
    }
    
    PatNick 普通 2023年1月18日 上午11:49

    本打卡对应问题:【动态规划专题】剑指 Offer 42. 连续子数组的最大和
    具体打卡内容:
    # 一位数组推导公式 : dp[n] = max(nums[n],nums[n]) + dp[n-1]
    def maxSubArray(nums: list[int]) -> int:
        if len(nums) == 1:
            return nums[0]
    
        m = len(nums)
        # 定义dp[n] 为以nums[n]为结尾的连续子树组最大和
        # 找到就是dp中的最大值
        dp = [None] * m
    
        # 初始化
        dp[0] = nums[0]
        max_ = nums[0]
    
        for n in range(1,m):
            dp[n] = max(nums[n],nums[n] + dp[n-1])
            max_ = max(max_,dp[n])
    
        print(dp)
        return max_
    
    
    # 优化 将dp变成一个单变量
    def maxSubArray1(nums: list[int]) -> int:
        if len(nums) == 1:
            return nums[0]
    
        m = len(nums)
        # 定义dp[n] 为以nums[n]为结尾的连续子树组最大和
        # 找到就是dp中的最大值
        dp = nums[0]
    
        # 初始化
        max_ = nums[0]
    
        for n in range(1,m):
            dp= max(nums[n],nums[n] + dp)
            max_ = max(max_,dp)
        return max_
    
    lucca 普通 2023年1月18日 上午1:05

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

    数学公式,只会背过…..

    class Solution {
        public int lastRemaining(int n, int m) {
            int ans = 0;
            for (int i = 2; i <= n; i++) {
                ans = (ans + m) % i;
            }
            return ans;
        }
    }
    
    lucca 普通 2023年1月18日 上午12:30

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

    原地变换(给每个元素找家)

    • 时间复杂度O(N)
    • 空间复杂度O(1)
    class Solution {
        public int findRepeatNumber(int[] nums) {
            int i = 0;
            // 为每个元素找家, 最终结果 nums[i] = i;
            while (i < nums.length) {
                // 找到家了, 下一位
                if (nums[i] == i) {
                    i++;
                    continue;
                }
                // 家里的人不是这个家该存在的人
                // 如果家里这个人, 他自己的家已经有和他相等的人, 说明他是多余的
                if (nums[i] == nums[nums[i]]) return nums[i];
                // 如果他的家里面的人和他不相等, 送他回家, 把他家的人接过来,进行下一回合
                int t = nums[i];
                nums[i] = nums[t];
                nums[t] = t;
            }
            return -1;
        }
    }
    
    lucca 普通 2023年1月18日 上午12:05

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

    恶心题,考验基本功

    class Solution {
        public int[] spiralOrder(int[][] matrix) {
            if (matrix.length == 0 || matrix[0].length == 0)
                return new int[0];
    
            int n = matrix.length, m = matrix[0].length;
            int[] ans = new int[n * m];
            boolean[][] vis = new boolean[n][m];
    
            int x = 0, y = 0;
            ans[0] = matrix[0][0];
            vis[x][y] = true;
    
            int[] dx = {0, 1, 0, -1};
            int[] dy = {1, 0, -1, 0};
            int d = 0;
    
            for (int i = 1; i < n * m; i++) {
                int nx = x + dx[d], ny = y + dy[d];
                while (!(nx >= 0 && nx < n && 
                         ny >= 0 && ny < m && !vis[nx][ny])) {
                    d = (d + 1) % 4;
                    nx = x + dx[d]; ny = y + dy[d];
                }
                x = nx; y = ny;
                vis[x][y] = true;
                ans[i] = matrix[x][y];
            }
            return ans;
        }
    }
    
    lucca 普通 2023年1月17日 下午11:48

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

    二分

    • 取右上节点,如果比目标值小就下移,如果比目标值大就左移
    • 保证每次都可以至少舍弃一行或一列
    • 最坏情况从右上遍历到坐下
    • 时间复杂度O(M+N)
    • 空间复杂度O(1)
    class Solution {
        public boolean findNumberIn2DArray(int[][] matrix, int target) {
            if (matrix.length == 0) return false;
            int n = matrix.length, m = matrix[0].length;
            int i = 0, j = m - 1;
            while (i < n && j >= 0) {
                if (matrix[i][j] == target) return true;
                if (matrix[i][j] > target) j--;
                else i++;
            }
            return false;
        }
    }
    
    lucca 普通 2023年1月17日 下午11:42

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

    同理斐波那契

    class Solution {
        public int numWays(int n) {
            if (n < 2) return 1;
            int a = 1, b = 1;
            while (n-- > 1) {
                int t = a;
                a = b;
                b += t;
                if (b >= 1000000007) b -= 1000000007;
            }
            return b;
        }
    }
    
    lucca 普通 2023年1月17日 下午11:37

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

    迭代

    class Solution {
        public int fib(int n) {
            if (n < 2) return n;
            int a = 0, b = 1;
            while (n-- > 1) {
                int t = a;
                a = b;
                b += t;
                if (b >= 1000000007) b -= 1000000007;
            }
            return b;
        }
    }
    
    mpweixin用户 普通 2023年1月17日 下午11:15

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

    利用矩阵,需要注意取模精度

    class Solution {
    
      public int fib(int n) {
            if (n<=1) {
                return n;
            }
    
            int p = n-1;
            int [][] res= {{1,0},{0,1}};
            int [][]base = {{0,1},{1,1}};
            while(p>0) {
                if ((p &1) == 1) {
                    res = multi(res, base);
                }
    
                base = multi(base, base);
                p>>=1;
            }
            return  res[1][1];
        }
    
        private int[][] multi(int[][] m1, int[][] m2) {
            int [][]res = new int[2][2];
            for(int i=0; i<2;i++){
                for(int j=0; j<2;j++){
                    long tmp = (long)m1[i][0] * m2[0][j] + (long)m1[i][1] * m2[1][j];
                    res[i][j] = (int)(tmp % 1000000007);
                }
            }
            return res;
    
        }
    }
    
    
    
    PatNick 普通 2023年1月17日 下午10:32

    本打卡对应问题:【回溯专题】剑指 Offer 38. 字符串的排列
    具体打卡内容:
    def permutation1(s: str) -> list[str]:
        result = []
        path = []
        visited = [False] * len(s)
        s = sorted(s)
        def dfs(arr,k):
            if k == len(arr):
                result.append("".join(path))
                return
    
            # 进行n叉树搜索(类似于二叉树搜索)
            # range(len(arr))相当于selectableStr
            for _ in range(len(arr)):
                # 如果已经访问过了
                if visited[_] == True:
                    continue
                # 剪枝
                if _ > 0 and visited[_ - 1] == False and arr[_ - 1] == arr[_]:
                    continue
    
                visited[_] = True
                path.append(arr[_])
                dfs(arr,k+1)
                visited[_] = False
                path.pop(-1)
    
        dfs(s,0)
    
    PatNick 普通 2023年1月17日 下午8:44

    本打卡对应问题:【回溯专题】剑指 Offer 34. 二叉树中和为某一值的路径
    具体打卡内容:
    class TreeNode:
        def __init__(self, val=0, left=None, right=None):
            self.val = val
            self.left = left
            self.right = right
    
    
    class Solution:
        def pathSum(self, root: TreeNode, target: int) -> list[list[int]]:
            result = []
            temp = []
            def dfs(node):
    
                if not node:
                    return
    
                temp.append(node.val)
                if sum(temp) == target and not node.right and not node.left:
                    # 这里不可以直接将temp append到result中,后面temp的改变会使result也改变
                    result.append([_ for _ in temp])
                dfs(node.left)
                dfs(node.right)
                # 回溯时消除上一个节点的元素
                temp.pop(-1)
    
    
    
            dfs(root)
            return result
    
    
    
        # 优化:将target设成动态的new_target -= node.val,来避免每次遍历都需要对temp求和,这样到遍历到叶子节点的时候,如果new_target==0,说明满足temp=target
        def pathSum1(self, root: TreeNode, target: int) -> list[list[int]]:
            result = []
            temp = []
    
            def dfs(node, new_target):
    
                if not node:
                    return
    
                temp.append(node.val)
                new_target -= node.val
                if not node.right and not node.left and new_target == 0:
                    result.append([_ for _ in temp])
    
                dfs(node.left, new_target)
                dfs(node.right, new_target)
                temp.pop(-1)
    
            dfs(root, target)
            return result
    
    
    PatNick 普通 2023年1月17日 下午7:28

    本打卡对应问题:【回溯专题】剑指 Offer 13. 机器人的运动范围
    具体打卡内容:
    class Solution:
        def __init__(self):
            # 这里用set存放标记
            self.invisitedList = set()
            self.m = 0
            self.n = 0
            self.k = 0
    
        def movingCount(self, m, n, k):
            self.m = m
            self.n = n
            # self.invisitedList = [[False for _ in range(n)] for __ in range(m)]
            self.k = k
    
            res = self.dsf(0,0)
    
            return res
    
    
    
    
        def dsf(self,i,j):
            # 越界,已标记,大于k
            if i < 0 or i >= self.m or j < 0 or j >= self.n or (i,j) in self.invisitedList or self.sum(i,j) > self.k:
                return 0
    
            self.invisitedList.add((i,j))
    
            return 1 + self.dsf(i,j+1) + self.dsf(i+1,j) + self.dsf(i,j-1) + self.dsf(i-1,j)
    
    
    
    
        def sum(self,x,y):
            if x // 10:
                sum1 = x // 10 + x % 10
            else:
                sum1 = x
            if y // 10:
                sum2 = y // 10 + y % 10
            else:
                sum2 = y
            return sum2 + sum1
    
    PatNick 普通 2023年1月17日 下午5:22

    本打卡对应问题:【回溯专题】剑指 Offer 12. 矩阵中的路径
    具体打卡内容:
    class Solution:
        def __init__(self):
            self.n = 0
            self.m = 0
            # self.visitedList = []
        def exist(self, board: list[list[str]], word: str) -> bool:
            self.n = len(board)
            self.m = len(board[0])
            # self.visitedList = [[False for _ in range(self.m)] for __ in range(self.n)]
            # 用两层for循环固定单词的第一个值
            for i in range(self.n):
                for j in range(self.m):
                    if self.dfs(board,i,j,word,0):
                        return True
    
            return False
    
        def dfs(self,board,i,j,word,k):
            '''
            深度优先遍历
            Args:
                board:
                i,j:定位board的索引
                word:
                k: 固定word中的第k个元素
            '''
    
            # 终止条件
            # 不越界,未走过,值相等
            # if i < 0 or i >= self.n or j < 0 or j >= self.m or self.visitedList[i][j] or board[i][j] != word[k]:
            # 这里由于在原list中进行标记
            if i < 0 or i >= self.n or j < 0 or j >= self.m or board[i][j] != word[k]:
                return False
    
            if k == len(word)-1:
                return True
            # 对已经走过的路径进行标注
            # self.visitedList[i][j] = True
    
            # 也可以不使用一个专门的二维列表标记路径,而是直接在原列表中将这个元素改成一个不可能是答案的数来作为标记
            board[i][j] = '~~~'
    
            # 遍历每个阶段的可选解集合(规定方向是右,下,左,上)
            res = self.dfs(board,i,j+1,word,k+1) or self.dfs(board,i+1,j,word,k+1) or self.dfs(board,i,j-1,word,k+1) or self.dfs(board,i-1,j,word,k+1)
    
            # 回溯,需要去掉原来走过的路径的标记
            # self.visitedList[i][j] = False
    
            # 如果不用布尔list标记路径,在回溯时,就需要恢复原列表中的该元素,这里能等于word【k】是因为能够回溯说明之前这个位置的值是对的
            board[i][j] = word[k]
            return res
    
    
    mpweixin用户 普通 2023年1月17日 下午2:44

    本打卡对应问题:【重要】如何把本项目写进简历 + 如何准备面试
    具体打卡内容:

    打卡

    lucca 普通 2023年1月16日 下午8:51

    本打卡对应问题:【回溯专题】剑指 Offer 38. 字符串的排列
    具体打卡内容:

    无重复的全排列 DFS

    • 时间复杂度 O(2^N)
    • 空间复杂度 O(N)
    class Solution {
        private char[] c, cs;
        private boolean[] vis;
        private List<String> li = new LinkedList<>();
        private int idx = 0;
        public String[] permutation(String s) {
            this.c = s.toCharArray();
            Arrays.sort(c);
            this.cs = new char[c.length];
            this.vis = new boolean[c.length];
    
            dfs(0);
    
            String[] ans = new String[li.size()];
            int idx = 0;
            for (String str : li) ans[idx++] = str;
            return ans;
        }
    
        private void dfs(int cur) {
            if (cur == c.length) {
                li.add(new String(cs));
                return;
            }
    
            for (int i = 0; i < c.length; i++) {
                if (i > 0 && c[i] == c[i - 1] && !vis[i-1]) continue;
                if (vis[i]) continue;
                vis[i] = true;
                cs[cur] = c[i];
                dfs(cur + 1);
                vis[i] = false;
            }
        }
    }
    
    lucca 普通 2023年1月16日 下午8:33

    本打卡对应问题:【回溯专题】剑指 Offer 34. 二叉树中和为某一值的路径
    具体打卡内容:

    DFS

    • 时间复杂度 O(N)
    • 空间复杂度 O(N)
    class Solution {
    
        private List<List<Integer>> ans = new LinkedList<>();
    
        public List<List<Integer>> pathSum(TreeNode root, int target) {
            if (root == null) return ans;
            LinkedList<Integer> li = new LinkedList<Integer>();
            dfs(root, li, target);
            return ans;
        }
    
        private void dfs(TreeNode root, LinkedList<Integer> li, int target) {
            if (root == null || Math.abs(target - root.val) < 0) return;
    
            li.add(root.val);
            target -= root.val;
    
            if (root.left == null && root.right == null) {
                if (target == 0) ans.add(new ArrayList<>(li));
                li.removeLast();
                return;
            }
    
            dfs(root.left, li, target);
            dfs(root.right, li, target);
            li.removeLast();
        }
    }
    
    PatNick 普通 2023年1月16日 下午8:16

    本打卡对应问题:【排序算法运用】剑指 Offer 51. 数组中的逆序对
    具体打卡内容:
    def reversePairs(num):
        if not num or len(num) == 1:
            return 0
        left = 0
        right = len(num) - 1
    
        return mergeSort(num,left,right)
    
    def mergeSort(arr,left,right):
        # 归并排序,在merge的过程计算逆序的数量
        if left >= right:
            return 0
    
        mid = (right - left) // 2 + left
    
        x1 = mergeSort(arr,left,mid)
        x2 = mergeSort(arr,mid+1,right)
        x3 = merge(arr,left,mid,mid+1,right)
        return x1 + x2 + x3
    def merge(arr,l1,r1,l2,r2):
        i = l1
        j = l2
        l = []
        count = 0
        while i <= r1 and j <= r2:
    
            if arr[j] < arr[i]:
                # 说明当前j与[i:l2]之间的元素都可以组成逆序数组
                count += l2 - i
                l.append(arr[j])
                j += 1
            else:
                l.append(arr[i])
                i += 1
    
    
        while i <= r1:
            l.append(arr[i])
            i +=1
    
        while j <= r2:
            l.append(arr[j])
            j += 1
    
        # 把临时数组赋给数组
        k = 0
        for _ in range(l1,r2+1):
            arr[_] = l[k]
            k += 1
    
        return count
    
    PatNick 普通 2023年1月16日 下午7:02

    本打卡对应问题:【排序算法运用】剑指 Offer 41. 数据流中的中位数
    具体打卡内容:
    from heapq import heapify,heappush,heappop
    class MedianFinder:
    
        def __init__(self):
            """
            initialize your data structure here.
            """
            # 大根堆存放较小的数
            self.bigHeapq = []
            heapify(self.bigHeapq)
            # 小根堆存放较大的数
            self.smallHeapq = []
            heapify(self.smallHeapq)
            self.count = 0
    
        def addNum(self, num: int) -> None:
            self.count += 1
            # 奇数个
            if self.count & 1 == 1:
                # 先添加到小根堆,将堆顶元素弹出放入大根堆中
                heappush(self.smallHeapq,num)
                s = heappop(self.smallHeapq)
                heappush(self.bigHeapq,-1 * s)
            else:
                # 先添加到大根堆,将堆顶元素弹出放入小根堆中
                heappush(self.bigHeapq, -1 * num)
                s = heappop(self.bigHeapq)
                heappush(self.smallHeapq,-1 * s)
    
        def findMedian(self) -> float:
            if self.count & 1 == 1:
                return -self.bigHeapq[0]
            else:
                return (self.smallHeapq[0]-self.bigHeapq[0]) / 2.0
    
    
    lucca 普通 2023年1月16日 下午6:27

    本打卡对应问题:【回溯专题】剑指 Offer 13. 机器人的运动范围
    具体打卡内容:

    BFS

    • 时间复杂度 O(NM)
    • 空间复杂度 O(NM)
    class Solution {
        public int movingCount(int n, int m, int k) {
            if (k == 0) return 1;
    
            int[] r = new int[n], c = new int[m];
            for (int i = 0; i < n; i++) {
                int t = i;
                while (t > 0) {
                    r[i] += t % 10;
                    t /= 10;
                }
            }
            for (int i = 0; i < m; i++) {
                int t = i;
                while (t > 0) {
                    c[i] += t % 10;
                    t /= 10;
                }
            }
    
            int[] dx = {0, 1}, dy = {1, 0};
            boolean[][] vis = new boolean[n][m];
            Queue<int[]> q = new LinkedList<>();
    
            int sum = 1;
            q.add(new int[]{0, 0});
            vis[0][0] = true;
    
            while (!q.isEmpty()) {
                int[] p = q.poll();
                for (int i = 0; i < 2; i++) {
                    int x = p[0] + dx[i], y = p[1] + dy[i];
                    if (x >= 0 && x < n && y >= 0 && y < m && !vis[x][y] && r[x] + c[y] <= k) {
                        vis[x][y] = true;
                        q.add(new int[]{x, y});
                        sum++;
                    }
                }
            }
            return sum;
        }
    }
    
    lucca 普通 2023年1月16日 下午6:13

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

    回溯

    • 时间复杂度O(NM)
    • 空间复杂度O(NM)
    class Solution {
    
        private int[] dx = {0, 1, 0, -1}, dy = {-1, 0, 1, 0};
        private int n, m, k;
        private boolean[][] vis;
        private char[][] g;
        private String word;
        public boolean exist(char[][] board, String word) {
            this.n = board.length;
            this.m = board[0].length;
            this.g = board;
            this.k = word.length();
            this.word = word;
    
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < m; j++) {
                    if (board[i][j] == word.charAt(0)) {
                        vis = new boolean[n][m];
                        vis[i][j] = true;
                        if (dfs(i, j, 1)) return true;
                    }
                }
            }
            return false;
        }
    
    
        private boolean dfs(int i, int j, int cnt) {
            if (cnt == k) return true;
    
            for (int k = 0; k < 4; k++) {
                int x = i + dx[k], y = j + dy[k];
                if (x >= 0 && x < n && 
                    y >= 0 && y < m && 
                    !vis[x][y] && g[x][y] == word.charAt(cnt)) {
                    vis[x][y] = true;
                    if (dfs(x, y, cnt + 1)) return true;
                    vis[x][y] = false;
                }
            }
            return false;
        }
    }
    
    lucca 普通 2023年1月16日 下午5:52

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

    一个大根堆存 <= 中位数,一个小根堆存 > 中位数

    • 时间复杂度 O(NlogN)
    • 空间复杂度 O(N)
    class MedianFinder {
        PriorityQueue<Integer> less, more;
        int cnt = 0;
    
        public MedianFinder() {
            less = new PriorityQueue<>((a, b) -> b - a); 
            more = new PriorityQueue<>();
        }
    
        public void addNum(int num) {
            cnt++;
            if (less.isEmpty()) {
                less.add(num);
                return;
            }
            if (num <= less.peek()) {
                less.add(num);
                if (cnt % 2 == 0) more.add(less.poll());
            } else {
                more.add(num);
                if (cnt % 2 == 1) less.add(more.poll());
            }
        }
    
        public double findMedian() {
            return cnt % 2 == 1 ?
                    less.peek() :
                    (1.0 * less.peek() + more.peek()) / 2;
        }
    }
    
    lucca 普通 2023年1月16日 下午5:35

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

    归并排序

    • 时间复杂度O(NlogN)
    • 空间复杂度O(N)
    class Solution {
        public int reversePairs(int[] nums) {
            return sort(nums, 0, nums.length - 1);
        }
    
        private int sort(int[] a, int l, int r) {
            if (l >= r) return 0;
    
            int mid = l + r >> 1;
            int sum = sort(a, l, mid) + sort(a, mid + 1, r);
    
            int i = l, j = mid + 1;
    
            int[] tmp = new int[r - l + 1];
            int idx = 0;
            while (i <= mid && j <= r) {
                if (a[i] <= a[j]) tmp[idx++] = a[i++];
                else {
                    sum += (mid + 1 - i);
                    tmp[idx++] = a[j++];
                }
            }
            while (i <= mid) tmp[idx++] = a[i++];
            while (j <= r) tmp[idx++] = a[j++];
            idx = 0;
            for (int k = l; k <= r; k++, idx++)
                a[k] = tmp[idx];
            return sum;
        }
    }