笨笨小子 永久会员 2024年5月23日 上午9:50

    本打卡对应问题:第一章:如何准备一场算法面试?
    具体打卡内容:

    打卡

    mpweixin用户 普通 2024年5月18日 上午12:21

    本打卡对应问题:什么是二叉堆?
    具体打卡内容:

    阅读打卡

    mpweixin用户 普通 2024年5月16日 下午11:55

    本打卡对应问题:什么是AVL树?
    具体打卡内容:

    阅读打卡

    mpweixin用户 普通 2024年5月14日 上午11:56

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

    使用hashmap打卡成功

    mpweixin用户 普通 2024年5月14日 上午11:56

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

    两种方法都打卡成功

    mpweixin用户 普通 2024年5月14日 上午11:56

    本打卡对应问题:【链表专题】剑指 Offer 06. 从尾到头打印链表
    具体打卡内容:

    打卡成功!

    mpweixin用户 普通 2024年5月14日 上午11:55

    本打卡对应问题:【链表专题】剑指 Offer 52. 两个链表的第一个公共点
    具体打卡内容:

    d打卡成功!

    mpweixin用户 普通 2024年5月14日 上午11:55

    本打卡对应问题:【链表专题】剑指 Offer 25. 合并两个排序的链表
    具体打卡内容:

    打卡成功!!

    mpweixin用户 普通 2024年5月14日 上午11:55

    本打卡对应问题:【链表专题】剑指 Offer 22. 链表中倒数第k个节点
    具体打卡内容:

    打卡成功

    mpweixin用户 普通 2024年5月14日 上午11:54

    本打卡对应问题:【链表专题】剑指 Offer 18. 删除链表的节点
    具体打卡内容:

    打卡成功

    mpweixin用户 普通 2024年5月14日 上午11:54

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

    打卡成功

    mpweixin用户 普通 2024年5月12日 下午12:32

    本打卡对应问题:剑指offer刷题第五期(已结束)
    具体打卡内容:

    kfaebot 普通 2024年5月11日 下午3:49

    本打卡对应问题:【动态规划专题】LeetCode 322. 零钱兑换
    具体打卡内容:
    class Solution {
    public:
        int coinChange(vector<int>& coins, int amount) {
            //dp[j]表示总金额为j时需要的最少硬币个数
            vector<int> dp(amount+1,INT_MAX);
    
            //初始化
            dp[0]=0;
    
            //状态转移方程
            for(int i=0;i<coins.size();i++){//先遍历物品
                for(int j=coins[i];j<=amount;j++){//再遍历背包
                    if(dp[j-coins[i]]!=INT_MAX){
                        dp[j]=min(dp[j-coins[i]]+1,dp[j]);
                    }
                    else{
                        continue;
                    }
                }
            }
            if(dp[amount]==INT_MAX){
                return -1;
            }
            return dp[amount];
        }
    };
    
    kfaebot 普通 2024年5月11日 下午2:42

    本打卡对应问题:【动态规划专题】LeetCode 198. 打家劫舍
    具体打卡内容:
    class Solution {
    public:
        int rob(vector<int>& nums) {
            vector<int>dp(nums.size(),0);
    
            if(nums.size()==1){
                return nums[0];
            }
    
            //初始化
            dp[0]=nums[0];
            dp[1]=max(nums[0],nums[1]);
    
    
            //状态转移方程
            for(int i=2;i<nums.size();i++){
                dp[i]=max(dp[i-2]+nums[i],dp[i-1]);
            }
            return dp[nums.size()-1];
        }
    };
    
    kfaebot 普通 2024年5月11日 上午10:15

    本打卡对应问题:【动态规划专题】剑指 Offer 47. 礼物的最大价值
    具体打卡内容:
    class Solution {
    public:
        int jewelleryValue(vector<vector<int>>& frame) {
            int m=frame.size();
            int 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]=dp[i-1][0]+frame[i][0];
            }
            for(int i=1;i<n;i++){
                dp[0][i]=dp[0][i-1]+frame[0][i];
            }
    
            //状态转移方程
            for(int i=1;i<m;i++){
                for(int j=1;j<n;j++){
                    dp[i][j]=max(dp[i-1][j],dp[i][j-1])+frame[i][j];
                }
            }
            return dp[m-1][n-1];
        }
    };
    
    kfaebot 普通 2024年5月11日 上午9:54

    本打卡对应问题:【动态规划专题】剑指 Offer 63. 股票的最大利润
    具体打卡内容:
    class Solution {
    public:
        int maxProfit(vector<int>& prices) {
            vector<vector<int>> dp(prices.size(),vector<int>(2));
    
            if(prices.size()==1){
                return 0;
            }
    
            //初始化
            dp[0][0]=0;
            dp[0][1]=-prices[0];
    
            //状态转移方程
            for(int i=1;i<prices.size();i++){
                dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);
                dp[i][1]=max(dp[i-1][1],-prices[i]);
            }
            return dp[prices.size()-1][0];
        }
    };
    
    kfaebot 普通 2024年5月10日 下午9:58

    本打卡对应问题:【动态规划】剑指 Offer 42. 连续子数组的最大和
    具体打卡内容:
    class Solution {
    public:
        int maxSales(vector<int>& sales) {
            //明确数组含义dp[i]表示末尾元素为sales[i]的最大子序列和
            vector<int> dp(sales.size());
            //初始化
            dp[0]=sales[0];
            //表达式
            int max_res=dp[0];
            for(int i=1;i<sales.size();i++){
                dp[i]=max(dp[i-1]+sales[i],sales[i]);
                if(max_res<dp[i]){
                    max_res=dp[i];
                }
            }
            return max_res;
        }
    };
    
    kfaebot 普通 2024年5月10日 下午9:39

    本打卡对应问题:【动态规划专题】LeetCode 64. 最小路径和
    具体打卡内容:
    class Solution {
    public:
        int minPathSum(vector<vector<int>>& grid) {
            int m=grid.size();
            int n=grid[0].size();
            int dp[m][n];
    
            //初始值
            dp[0][0]=grid[0][0];
            for(int i=1;i<m;i++){
                dp[i][0]=grid[i][0]+dp[i-1][0];
            }
            for(int i=1;i<n;i++){
                dp[0][i]=grid[0][i]+dp[0][i-1];
            }
    
            //关系式
            for(int i=1;i<m;i++){
                for(int j=1;j<n;j++){
                    dp[i][j]=min(dp[i][j-1],dp[i-1][j])+grid[i][j];
                }
            }
            return dp[m-1][n-1];
        }
    };
    
    kfaebot 普通 2024年5月10日 下午9:35

    本打卡对应问题:【杂题】剑指 Offer 10- II. 青蛙跳台阶问题
    具体打卡内容:
    class Solution {
    public:
        int trainWays(int num) {
            int MOD=1000000007;
            //包含0
            if(num==0){
                return 1;
            }
            if(num>0&&num<=2){
                return num;
            }
            int f1=1;
            int f2=2;
            for(int i=3;i<=num;i++){
                int sum=(f1+f2)%MOD;
                f1=f2;
                f2=sum;
            }
            return f2;
    
        }
    };
    
    kfaebot 普通 2024年5月10日 下午9:18

    本打卡对应问题:【杂题】剑指 Offer 10- I. 斐波那契数列
    具体打卡内容:
    class Solution {
    public:
        int fib(int n) {
            //取模
            int MOD=1000000007;
            if(n<2){
                return n;
            }
            int f0=0;
            int f1=1;
            for(int i=2;i<=n;i++){
                int sum=(f0+f1)%MOD;
                f0=f1;
                f1=sum;
            }
            return f1;
        }
    };
    
    幽小皮 永久会员 2024年5月7日 下午9:23

    本打卡对应问题:【作业11】二叉树层序遍历(变形版)
    具体打卡内容:


    //打卡
    public List<List> decorateRecord(TreeNode root) {
    if(root null){
    return new ArrayList();
    }

        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        int r = 1;
    
        queue.add(root);
        while(!queue.isEmpty()){
            int size = queue.size();
            List<Integer> t = new LinkedList<>();
            for(int i = 0; i < size; i++){
                TreeNode temp = queue.poll();
                if(r % 2 == 1){
                    t.add(temp.val);
                }else{
                    t.addFirst(temp.val);
                }
                if(temp.left != null){
                    queue.add(temp.left);
                }
                if(temp.right != null){
                    queue.add(temp.right);
                }
    
    
    
            }
            r++;
            res.add(t);
        }
        return res;
    }
    

    “java

    Thaddeus 永久会员 2024年5月6日 下午3:18

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

    打卡

    class Solution {
        public int nthUglyNumber(int n) {
            =int a = 0, b = 0, c = 0;
            int[] res = new int[n];
            res[0] = 1;
            for(int i = 1; i < n; i++) {
                int n2 = res[a] * 2, n3 = res[b] * 3, n5 = res[c] * 5;
                res[i] = Math.min(Math.min(n2, n3), n5);
                if(res[i] == n2) a++;
                if(res[i] == n3) b++;
                if(res[i] == n5) c++;
            }
            return res[n - 1];
        }
    }
    
    Thaddeus 永久会员 2024年5月6日 下午3:10

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

    打卡

    class Solution {
        public boolean articleMatch(String s, String p) {
            int n = s.length(), m = p.length();
            boolean[][] dp = new boolean[n + 1][m + 1];
            dp[0][0] = true;
            for(int j = 2; j <= m; j++) {
                if(p.charAt(j - 1) == '*') dp[0][j] = dp[0][j - 2];
            }
    
            for(int i = 1; i <= n; i++) {
                for(int j = 1; j <= m; j++) {
                    if(p.charAt(j - 1) != '*') {
                        if(p.charAt(j - 1) == '.' || p.charAt(j - 1) == s.charAt(i - 1)) dp[i][j] = dp[i - 1][j - 1];
                    } else {
                        if(p.charAt(j - 2) != s.charAt(i - 1) && p.charAt(j - 2) != '.') dp[i][j] = dp[i][j - 2];
                        else dp[i][j] = dp[i][j - 2] || dp[i - 1][j - 2] || dp[i - 1][j];
                    }
                }
            }
            return dp[n][m];
        }
    }
    
    Thaddeus 永久会员 2024年5月6日 上午9:39

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

    打卡

    class Solution {
        public int dismantlingAction(String arr) {
            Map<Character, Integer> dic = new HashMap<>();
            int l = -1, n = arr.length(), res = 0;
            for(int r = 0; r < n; r++) {
                if(dic.containsKey(arr.charAt(r))) {
                    if(dic.get(arr.charAt(r)) < l) l = l;
                    else l = dic.get(arr.charAt(r));
                    //l = Math.max(l, dic.get(arr.charAt(r))); // 将l移动到无重复值的区间左侧,且要最大
                }  // 取最大,是因为可能此时arr[r]对应的字符已经是在l左侧了,不在当前的无重复区间,因此l无需改变
                    // 为什么已经在左侧了呢?因为其他字符重复了,且在它右边,就把它割掉了,此时该字符其实根本就不重复,因此不用更新左边界
                dic.put(arr.charAt(r), r);
                res = Math.max(res, r - l);
            }
            return res;
        }
    }
    
    Thaddeus 永久会员 2024年5月6日 上午9:18

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

    打卡

    class Solution {
        public int jewelleryValue(int[][] frame) {
            int m = frame.length, n = frame[0].length;
            int[] dp = new int[n];
            dp[0] = frame[0][0];
            for(int i = 1; i < n; i++) dp[i] = dp[i - 1] + frame[0][i];
    
            for(int i = 1; i < m; i++) {
                for(int j = 0; j < n; j++) {
                    if(j == 0) dp[j] = dp[j] + frame[i][j];
                    else dp[j] = Math.max(dp[j], dp[j - 1]) + frame[i][j];
                }
            }
    
            return dp[n - 1];
        }
    }
    
    Thaddeus 永久会员 2024年5月6日 上午9:09

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

    打卡

    class Solution {
        public int bestTiming(int[] prices) {
            int res = 0, minPrice = Integer.MAX_VALUE;
            for(int i = 0; i < prices.length; i++) {
                minPrice = Math.min(minPrice, prices[i]);
                res = Math.max(res, prices[i] - minPrice);
            }
            return res;
        }
    }
    
    Deckkker 普通 2024年4月27日 下午4:24

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

    class CQueue:

    def __init__(self):
        self.Stack_In = []
        self.Stack_Out = []
    
    def appendTail(self, value: int) -> None:
        self.Stack_In.append(value)
    
    def deleteHead(self) -> int:
        if self.Is_empty():
            return -1
    
        if self.Stack_Out:
            return self.Stack_Out.pop()
        else:
            while self.Stack_In:
                self.Stack_Out.append(self.Stack_In.pop())
            return self.Stack_Out.pop()
    
    def Is_empty(self):
        return not (self.Stack_In or self.Stack_Out)
    

    时间复杂度: O(1),push 为 O(1),pop 为均摊 O(1)。对于每个元素,至多入栈和出栈各两次(Stack_In和Stack_Out至多各进出栈一次),故均摊复杂度为 O(1)。

    空间复杂度:O(n)。其中 n 是操作总数。对于有 n 次 push 操作的情况,队列中会有 n 个元素,故空间复杂度为 O(n)。

    Deckkker 普通 2024年4月27日 下午4:22

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

    class MyStack:

    def __init__(self):
        self.Que_1 = []
        self.Que_2 = []
    
    def push(self, x: int) -> None:
        # Push element x onto stack. 
        self.Que_1.append(x)
    
    def pop(self) -> int:
        # Removes the element on top of the stack and returns that element.
        while len(self.Que_1)>1:
            self.Que_2.append(self.Que_1.pop(0))
        res = self.Que_1.pop(0)
        self.Que_1, self.Que_2 = self.Que_2, self.Que_1
        self.Que_2.clear()
        return res
    
    def top(self) -> int:
        # Get the top element.
        while len(self.Que_1)>1:
            self.Que_2.append(self.Que_1.pop(0))
        res = self.Que_1[0]
        self.Que_2.append(self.Que_1.pop(0))
        self.Que_1, self.Que_2 = self.Que_2, self.Que_1
        self.Que_2.clear()
        return res
    
    def empty(self) -> bool:
        return not self.Que_1
    

    入栈操作(push):O(1)
    出栈操作(pop):平均情况下接近O(1),最坏情况下O(n)
    获取栈顶元素(top):平均情况下接近O(1),最坏情况下O(n)
    判空操作(empty):O(1)

    Deckkker 普通 2024年4月27日 上午10:51

    本打卡对应问题:剑指 Offer 09. 用两个栈实现队列
    具体打卡内容:

    class CQueue:

    def __init__(self):
        self.Stack_In = []
        self.Stack_Out = []
    
    def appendTail(self, value: int) -> None:
        self.Stack_In.append(value)
    
    def deleteHead(self) -> int:
        if self.Is_empty():
            return -1
    
        if self.Stack_Out:
            return self.Stack_Out.pop()
        else:
            while self.Stack_In:
                self.Stack_Out.append(self.Stack_In.pop())
            return self.Stack_Out.pop()
    
    def Is_empty(self):
        return not (self.Stack_In or self.Stack_Out)
    

    时间复杂度: O(1),push 为 O(1),pop 为均摊 O(1)。对于每个元素,至多入栈和出栈各两次(Stack_In和Stack_Out至多各进出栈一次),故均摊复杂度为 O(1)。

    空间复杂度:O(n)。其中 n 是操作总数。对于有 n 次 push 操作的情况,队列中会有 n 个元素,故空间复杂度为 O(n)。

    Deckkker 普通 2024年4月27日 上午10:22

    本打卡对应问题:【链表专题】百度真题:环形链表分成三等份
    具体打卡内容:

    思路分析

    1. 遍历链表统计长度:首先遍历链表,统计链表的长度。这是为了确定每个部分的长度以及可能存在的剩余节点数。
    2. 计算分割数量和长度:根据给定的分割数量k和链表长度,计算出每个部分的平均长度(即链表长度除以分割数量),以及前面多余的部分的长度(即链表长度对分割数量取余)。
    3. 分割链表:再次遍历链表,根据计算出的长度将链表分割成k个部分,并将每个部分的尾节点的next指针置为空。
    # Definition for singly-linked list.
    # class ListNode:
    #     def __init__(self, val=0, next=None):
    #         self.val = val
    #         self.next = next
    class Solution:
        def splitListToParts(self, head: Optional[ListNode], k: int) -> List[Optional[ListNode]]:
            if not head:
                return [None for _ in range(k)]
    
            length = 0
            node = head
            while node:
                length += 1
                node = node.next
    
            # 计算每段的长度以及多出的部分
            avg_len, extra_len = length//k, length%k 
    
            # 再次遍历链表,根据 avg_len 和 extra_len 将链表分割成 k 个部分
            # 并将每个部分的尾节点的 next 指针置为空。
            res = []
            cur = head
            pre = None
    
            for _ in range(k):
                res.append(cur)
                for _ in range(avg_len+(1 if extra_len > 0 else 0)):
                    pre = cur
                    cur = cur.next
                if pre:
                    pre.next = None
                extra_len -= 1
            return res
    

    复杂度分析

    • 时间复杂度:O(n),其中n是链表的长度,需要遍历链表两次。
    • 空间复杂度:O(1)

    参考力扣725.分隔链表,k恒定为3即可。

    Laboratory 普通 2024年4月18日 上午11:22

    本打卡对应问题:什么是AVL树?
    具体打卡内容:

    阅读打卡

    Laboratory 普通 2024年4月15日 下午11:43

    本打卡对应问题:【基本数据结构】变形题:最小栈的最优解
    具体打卡内容:

    利用差值存入栈中可以保证O(1)的空间复杂度

    Laboratory 普通 2024年4月15日 下午11:29

    本打卡对应问题:【基本数据结构】剑指 Offer 31. 栈的压入、弹出序列
    具体打卡内容:
    class Solution {
        public boolean validateBookSequences(int[] putIn, int[] takeOut) {
            if(putIn.length == 0) {
                return true;
            }
            Deque<Integer> stack = new LinkedList<>();
            int i=0;
            for(int num : putIn) {
                stack.offerLast(num);
                while(!stack.isEmpty() && stack.peekLast() == takeOut[i]) {
                    stack.pollLast();
                    i++;
                }
            }
            return stack.isEmpty();
        }
    }
    

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

    Laboratory 普通 2024年4月15日 下午11:04

    本打卡对应问题:【基本数据结构】剑指 Offer 30. 包含min函数的栈
    具体打卡内容:
    class MinStack {
        Deque<Integer> stack;
        Deque<Integer> minStack;
    
        /** initialize your data structure here. */
        public MinStack() {
            stack = new LinkedList<>();
            minStack = new LinkedList<>();
        }
    
        public void push(int x) {
            stack.offerLast(x);
            if(minStack.isEmpty() || x <= minStack.peekLast()) {
                minStack.offerLast(x);
            }
        }
    
        public void pop() {
            int i = stack.pollLast();
            if(i == minStack.peekLast()) {
                minStack.pollLast();
            }
        }
    
        public int top() {
            return stack.peekLast();
        }
    
        public int getMin() {
            return minStack.peekLast();
        }
    }
    
    /**
     * Your MinStack object will be instantiated and called as such:
     * MinStack obj = new MinStack();
     * obj.push(x);
     * obj.pop();
     * int param_3 = obj.top();
     * int param_4 = obj.getMin();
     */
    

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

    =.= 普通 2024年4月15日 下午9:50

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

    class Solution {
    public int nthUglyNumber(int n) {
    int a = 1, b = 1, c = 1;
    int[] dp = new int[n+1];
    dp[1] = 1;
    for(int i=2; i<=n; i++){
    dp[i] = Math.min(dp[a]2, Math.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];
    }
    

    }

    时间:O(n);
    空间:O(n)

    王位詮釋 普通 2024年4月15日 下午3:10

    本打卡对应问题:【杂题】剑指 Offer 29. 顺时针打印矩阵
    具体打卡内容:
    class Solution {
        public int[] spiralArray(int[][] array) {
            if(array==null||array.length==0){
                return new int[0];
            }
            int m = array.length;
            int n = array[0].length;
            int[] res = new int[m*n];
            int up = 0;//上边界
            int down = m-1;//下边界
            int left = 0;//左边界
            int right = n-1;//右边界
            int index = 0;
            while(up<=down||left<=right){
                //往右走
                for(int i=left;i<=right;i++){
                    res[index++] = array[up][i];
                }
                up++;
                if(up>down){
                    break;
                }
                //往下走
                for(int i=up;i<=down;i++){
                    res[index++] = array[i][right];
                }
                right--;
                if(right<left){
                    break;
                }
                //往左走
                for(int i = right;i>=left;i--){
                    res[index++] = array[down][i];
                }
                down--;
                if(down<up){
                    break;
                }
                //往上走
                for(int i = down;i>=up;i--){
                    res[index++] = array[i][left];
                }
                left++;
                if(left>right){
                    break;
                }
            }
            return res;
        }
    }
    思路:定义左边界、有边界、上边界和下边界,然后可以向右走、向下走、
    向左走和向上走,同时创建一个res数组用来保存访问到的数组元素
    时间复杂度:O(mn)
    空间复杂度:O(1)
    
    =.= 普通 2024年4月15日 下午2:57

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

    class Solution {
    public int dismantlingAction(String arr) {
    int n = arr.length();
    int ans = 0;

        int left = 0;
        int right = 0;
        HashMap<Character, Integer> window = new HashMap<>();
    
        while(right < n){
            char c = arr.charAt(right);
            right++;
            window.put(c, window.getOrDefault(c, 0) + 1);
            if(window.get(c) == 1){
                ans = Math.max(ans, window.size());
            }
    
            while(window.get(c) > 1){
                char d = arr.charAt(left);
                if(window.get(d)>1){
                    window.put(d, window.get(d)-1);
                }
                else{
                    window.remove(d);
                }
                left++;
            }
        }
    
        return ans;
    }
    

    }

    时间:O(n)
    空间:O(n)

    =.= 普通 2024年4月15日 下午2:36

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

    class Solution {
    public int jewelleryValue(int[][] frame) {
    int m = frame.length;
    int n = frame[0].length;

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

    }

    时间:O(mn)
    空间:O(mn)

    =.= 普通 2024年4月15日 下午2:28

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

    class Solution {
    public int bestTiming(int[] prices) {
    int n = prices.length;
    if(n <= 1) return 0;

        int min = prices[0];
        int ans = 0;
    
        for(int i=1; i<n; i++){
            ans = Math.max(ans, prices[i] - min);
            min = Math.min(min, prices[i]);
        }
    
        return ans;
    }
    

    }

    时间:O(n)
    空间:O(1)

    王位詮釋 普通 2024年4月15日 下午2:25

    本打卡对应问题:【杂题】剑指 Offer 04. 二维数组中的查找
    具体打卡内容:
    暴力法:
    class Solution {
        public boolean findTargetIn2DPlants(int[][] plants, int target) {
            //暴力法
            if(plants==null||plants.length==0){
                return false;
            }
            int m = plants.length;
            int n = plants[0].length;
            for(int i=0;i<m;i++){
                for(int j=0;j<n;j++){
                    if(plants[i][j]==target){
                        return true;
                    }
                }
            }
            return false;
        }
    }
    时间复杂度:O(n2)
    空间复杂度:O(1)
    
    最优解:
    class Solution {
        public boolean findTargetIn2DPlants(int[][] plants, int target) {
            if(plants==null||plants.length<=0){
                return false;
            }
            int i = plants.length-1;
            int j = 0;
            while(i>=0&&j<plants[0].length){
                if(plants[i][j]==target){
                    return true;
                }
                if(plants[i][j]<target){
                    j++;
                }else{
                    i--;
                }
            }
            return false;
        }
    }
    时间复杂度:O(m+n)
    空间复杂度:O(1)
    
    王位詮釋 普通 2024年4月15日 下午2:09

    本打卡对应问题:【杂题】剑指 Offer 03. 数组中重复的数字
    具体打卡内容:
    哈希表法:
    class Solution {
        public int findRepeatDocument(int[] documents) {
            Set<Integer> set = new HashSet<>();
            for(int i=0;i<documents.length;i++){
                if(set.contains(documents[i])){
                    return documents[i];
                }else{
                    set.add(documents[i]);
                }
            }
            return -1;
        }
    }
    时间复杂度:O(n)
    空间复杂度:O(n)
    
    排序法:
    class Solution {
        public int findRepeatDocument(int[] documents) {
            Arrays.sort(documents);
            for(int i=1;i<documents.length;i++){
                if(documents[i]==documents[i-1]){
                    return documents[i];
                }
            }
            return -1;
        }
    }
    时间复杂度:O(nlogn)
    空间复杂度:O(1)
    
    下标法:
    class Solution {
        public int findRepeatDocument(int[] documents) {
            int i = 0;
            while(i<documents.length){
                if(documents[i]==i){
                    i++;
                    continue;
                }
                if(documents[documents[i]]==documents[i]){//多个元素对应同一个下标
                    return documents[i];
                }
                int temp = documents[i];
                documents[i] = documents[temp];
                documents[temp] = temp;
            }
            return -1;
        }
    }
    时间复杂度:O(n)
    空间复杂度:O(1)
    
    王位詮釋 普通 2024年4月14日 下午9:05

    本打卡对应问题:【杂题】剑指 Offer 62. 圆圈中最后剩下的数字
    具体打卡内容:
    数学+迭代法:
    class Solution {
        public int iceBreakingGame(int num, int target) {
            int x = 0;
            for (int i = 2; i <= num; i++) {
                x = (x + target) % i;
            }
            return x;
        }
    }
    
    链表法,模拟删除,但是后面会超时:
    class Solution {
        public int iceBreakingGame(int num, int target) {
            Node pre = new Node();
            Node cur = pre;
            //构造环形数组
            for(int i=0;i<num;i++){
                cur.next = new Node(i,null);
                cur = cur.next;
            }
            cur.next = pre.next;//现在cur指向的是最后一个元素
            cur = cur.next;//此时cur指向第一个元素
            while(cur.next!=cur){
                int count = 1;
                while(count<target){
                    cur = cur.next;//往后走一步
                    count++;
                }
                //把cur所指向的节点删除
                cur.val = cur.next.val;
                cur.next = cur.next.next;
            }
            return cur.val;
        }
    }
    class Node{
        int val;
        Node next;
        public Node(){
    
        }
        public Node(int val,Node next){
            this.val = val;
            this.next = next;
        }
    }
    
    王位詮釋 普通 2024年4月14日 下午7:48

    本打卡对应问题:【杂题】剑指 Offer 10- II. 青蛙跳台阶问题
    具体打卡内容:
    class Solution {
        public int trainWays(int num) {
            final int MOD = 1000000007;
            if(num==0){
                return 1;
            }
            if(num<=2){
                return num;
            }
            int first = 1;
            int second = 2;
            for(int i=3;i<=num;i++){
                int temp = first+second;
                first = second;
                second = temp%MOD;
            }
            return second;
        }
    }
    思路:小青蛙一次可以跳一阶,也可以跳两阶,所以如果要知道跳num阶有多少中情况,只需要之后num-1或者num-2有多少阶就好了。
    时间复杂度:O(n)
    空间复杂度:O(1)
    
    王位詮釋 普通 2024年4月14日 下午7:44

    本打卡对应问题:【杂题】剑指 Offer 10- I. 斐波那契数列
    具体打卡内容:
    class Solution {
        public int fib(int n) {
            final int MOD = 1000000007;
            if(n<=1){
                return n;
            }
            int first = 0;
            int second = 1;
            for(int i=2;i<=n;i++){
                int temp = first+second;
                first = second;
                second = temp%MOD;
            }
            return second;
        }
    }
    时间复杂度:O(n)
    空间复杂度:O(1)
    需要注意题意里的取模部分,给我恶心坏了
    
    王位詮釋 普通 2024年4月14日 下午6:24

    本打卡对应问题:【动态规划专题】LeetCode 72. 编辑距离
    具体打卡内容:
    class Solution {
        public int minDistance(String word1, String word2) {
            int m = word1.length();
            int n = word2.length();
            //dp[i][j]表示当word1长度为i,word2长度为j的时候
            //需要的最少的操作数
            int[][] dp = new int[m+1][n+1];
            dp[0][0] = 0;
            //初始化第一行
            for(int i=1;i<n+1;i++){
                dp[0][i] = dp[0][i-1]+1;
            }
            //初始化第一列
            for(int i=1;i<m+1;i++){
                dp[i][0] = dp[i-1][0]+1;
            }
            //把word1转换为word2所需要的最少步数
            for(int i=1;i<m+1;i++){
                for(int j=1;j<n+1;j++){
                    if(word1.charAt(i-1)==word2.charAt(j-1)){//i处的字符与j处的字符相等
                        dp[i][j] = dp[i-1][j-1];
                    }else{
                        int add = dp[i][j-1];//插入一个字符之前
                        int delete = dp[i-1][j];//删除一个字符之前
                        int replace = dp[i-1][j-1];//替换一个字符之前
                        dp[i][j] = Math.min(Math.min(add,delete),replace)+1;
                    }
                }
            }
            return dp[m][n];
        }
    }
    思路:用二维数组记录长度为i的字符串word1转换为长度为j的字符串word2所需要的最少的操作数,如果word1的第i个字符和word2的第j个字符相同,则dp[i][j] =  dp[i-1][j-1],否则就需要看是要怎么操作:添加一个字符、删除一个字符、替换一个字符。
    时间复杂度:O(mn)
    空间复杂度:O(mn)
    优化成一维数组:
    class Solution {
        public int minDistance(String word1, String word2) {
            int m = word1.length();
            int n = word2.length();
            int[] dp = new int[n+1];
            //初始化
            for(int i=1;i<n+1;i++){
                dp[i] = dp[i-1]+1;
            }
            for(int i=1;i<m+1;i++){
                int temp = dp[0];
                dp[0] = dp[0]+1;
                for(int j=1;j<n+1;j++){
                    int pre = temp;
                    temp = dp[j];
                    if(word1.charAt(i-1)==word2.charAt(j-1)){//word1第i个字符和word2第j个字符相等
                        dp[j] = pre;
                    }else{
                        dp[j] = Math.min(Math.min(pre,dp[j-1]),dp[j])+1;
                    }
                }
            }
            return dp[n];
        }
    }
    时间复杂度:O(mn)
    空间复杂度:O(n)
    
    王位詮釋 普通 2024年4月14日 下午5:27

    本打卡对应问题:【动态规划专题】LeetCode 174. 地下城游戏
    具体打卡内容:
    class Solution {
        public int calculateMinimumHP(int[][] dungeon) {
            if(dungeon==null||dungeon.length<=0||dungeon[0].length<=0){
                return 0;
            }
            int m = dungeon.length;
            int n = dungeon[0].length;
            //dp[i][j]表示从i,j位置到终点所需要的最少血量
            int[][] dp = new int[m][n];
            //初始值
            //如果dungeon[m-1][m-1]是正值,说明这里会加血,所以初始值不需要设置
            //如果是负值的话,说明这里会减血,所以需要设置初始值
            dp[m-1][n-1] = Math.max(-dungeon[m-1][n-1],0);
            //设置最后一行的值
            for(int i = n-2;i>=0;i--){
                int needMin = dp[m-1][i+1]-dungeon[m-1][i];
                dp[m-1][i] = Math.max(needMin,0);
            }
            //设置最后一列的值
            for(int i=m-2;i>=0;i--){
                int needMin = dp[i+1][n-1]-dungeon[i][n-1];
                dp[i][n-1] = Math.max(needMin,0);
            }
    
            for(int i=m-2;i>=0;i--){
                for(int j = n-2;j>=0;j--){
                    int needMin = Math.min(dp[i][j+1],dp[i+1][j])-dungeon[i][j];
                    dp[i][j] = Math.max(0,needMin);
                }
            }
            return dp[0][0]+1;
        }
    }
    思路:由于这个题在往后便利过程中会涉及到加血,
    所以i,j位置的值可能是和后面的值有关系,不像之前的题那样,
    i,j位置的值只与左或者上的值有关,所以这个题可以从后往前推,
    如果从后往前推,之前的动归思想都是从开始位置到当前位置的xxx,
    而这里的dp[i][j]表示的就是从当前位置到最后所需要的血量。
    这时候前一位置的血量要根据右边和下边的值来判断,
    所需要的最小血量needMin = Math.min(dp[i+1][j],dp[i][j+1]),
    dp[i][j] = Math.max(needMin-dungeon[i][j],0)
    
    Jimmy 普通 2024年4月14日 下午5:24

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

    子问题: dp[i] = max(dp[i-1],dp[i-2]+nums[i-1]);

    class Solution {
    public:
        int rob(vector<int>& nums) {
            if(nums.size() == 0)
            {
                return 0;
            }
            int N = nums.size();
            vector<int> dp(N+1,0);
            dp[0] = 0;
            dp[1] = nums[0];
            for(int i=2;i<=N;i++)
            {
                dp[i] = max(dp[i-1],dp[i-2]+nums[i-1]);
            }
            return dp[N];
        }
    };
    
    王位詮釋 普通 2024年4月14日 下午3:22

    本打卡对应问题:【动态规划专题】LeetCode 322. 零钱兑换
    具体打卡内容:
    这个题我最开始的时候陷入了一个误区:要凑出来面值为amount,而且同时
    硬币数量还得最少,那就从最大面值的硬币开始分配,这样最后结果就会是
    最小的面值,这种想法本身没问题,但是可能会出现这种情况:一直用最大面值
    硬币匹配导致最后剩下的amount值不足以匹配剩余的硬币,所以这种是有问题的
    class Solution {
        public int coinChange(int[] coins, int amount) {
            //dp[i]表示组成金额i所需要的最少的硬币数量
            //前面凑出来的i的最小的硬币数量可以用来凑后面的i的硬币数量
            //由于后面的i的硬币数量需要依赖前面的i的硬币数量,所以后面的i
            //能凑出来的话dp[i]值一定是小于amount+1的,否则就返回-1
            int[] dp = new int[amount+1];
            Arrays.fill(dp,amount+1);
            dp[0] = 0;
            for(int i=1;i<amount+1;i++){
                for(int j=0;j<coins.length;j++){
                    //防止越界,因为i表示金额值,coins[j]表示第j枚硬币的金额值,i不应该小于coins[j]
                    if(coins[j]<=i){
                        dp[i] = Math.min(dp[i],dp[i-coins[j]]+1);
                    }
                }
            }
            return dp[amount]>amount?-1:dp[amount];
        }
    }
    思路:数组dp[i]表示凑出来面值为i时需要的最少的硬币数量;如果面值为i
    的时候前面的都凑不出来,那i的面值肯定也凑不出来,就返回-1;
    否则就动态计算需要的面值,dp[i] = Math.min(dp[i],dp[i-coins[j]]+1),最后返回结果。
    
    幽小皮 永久会员 2024年4月13日 下午8:46

    本打卡对应问题:【作业8】链表专题:用递归合并排序链表
    具体打卡内容:

    打卡

    “`
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
    if(list1 == null){
    return list2;
    }else if(list2 == null){
    return list1;
    }
    if(list1.val <= list2.val){ list1.next = mergeTwoLists(list1.next, list2); return list1; }else{ list2.next = mergeTwoLists(list1, list2.next); return list2; }

    }```java
    
    heathhou 普通 2024年4月13日 下午3:37

    本打卡对应问题:【动态规划专题】LeetCode 322. 零钱兑换
    具体打卡内容:
    class Solution {
    public:
        int coinChange(vector<int>& coins, int amount) {
            if(coins.size() <= 0){
                return 0;
            }
    
            int Max = amount + 1;
            // 定义 dp[i] 为组成金额 i 所需最少的硬币数量
            // 初始值设置为需要 amount + 1 的硬币,这是最大值了
            vector<int> dp(amount + 1, Max); 
    
            dp[0] = 0;
            for(int i = 1; i <= amount; ++i){
                for(int j = 0; j < coins.size(); ++j){
                    if(coins[j] <= i){
                        dp[i] = min(dp[i], dp[i-coins[j]] + 1);
                    }
                }
            }
            return dp[amount] > amount ? -1 : dp[amount];
        }
    };