已完成阅读

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

70 没有 懂

# 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

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

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]

逆向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];
    }
}

背包变式

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];
    }
}

双指针，巧妙避开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;
    }
}

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

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];
    }
}

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]

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]

双指针

• 时间复杂度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;
    }
}

迭代

• 时间复杂度 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;
    }
}

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;
    }
}

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

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;
    }
}

恶心题，考验基本功

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;
    }
}

同理斐波那契

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;
    }
}

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

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;

    }
}

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

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

无重复的全排列 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;
        }
    }
}

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

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;
    }
}

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

• 时间复杂度 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;
    }
}