头像

查猪的快乐练习

【學】温暖和给大家带来快乐




离线:19分钟前


新鲜事 原文

图片


新鲜事 原文

泛函
图片


活动打卡代码 AcWing 221. 最大正方形

第一份Explore Chanllenge 的终章Epilogue (仪式感MAXXX!)

(反证法 + 夹逼/三明治定理)(DP)

111.png
这些小红色矩阵里都是1

int maximalSquare(vector<vector<char>>& matrix) {
        int n = matrix.size();
        if (n == 0) return 0;
        int m = matrix[0].size(); //java里用.length
        vector<vector<int>> f(n + 1, vector<int> (m + 1)); //注意cpp里是用vector初始化
        // java里用int[][] f = new int[n + 1][m + 1]; 
        int ans = 0;
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++) {
                int u = i + 1, v = j + 1;
                if (matrix[i][j] == '0') f[u][v] = 0;
                else {
                    f[u][v] = min(f[u - 1][v - 1], min(f[u - 1][v], f[u][v - 1])) + 1;
                    ans = max(ans, f[u][v]);
                }
            }
        return ans * ans;
    }


新鲜事 原文

经过猪猪的测试。AcWing上的评论区宽度为730+到770px. 即截图附在评论时可选730px *n px(不会超过垃圾桶删除键)或770px * n px(css里边框极限距离)


活动打卡代码 AcWing 268. 缺失数字

目录:解法很多。只是缺一个数,那异或也行,减和也行
①和相减
②异或
③利用set
def missingNumber(self, nums: List[int]) -> int:
        n = len(nums)
        res = [-1] * (len(nums) + 1)
        for i in range(n):
            res[nums[i]] = i #不懂的话见模拟。就是[0,n]数,(数组长度为n/n+1)的性质
        for i, item in enumerate(res):
            if item == -1:
                return i

模拟

            # [3, 0, 1]
            # res[3] = 0
            # res[0] = 1
            # res[1] = 2
            # ---
            # [0, 1]
            # res[0] = 0
            # res[1] = 1
            # res[2] = -1

数学法:
直接返回0,n的和减去数组和即是少的那个数

return n*(n + 1)//2 - sum(nums)

②异或:

def missingNumber(self, nums: List[int]) -> int:
        missing = 0
        for i, item in enumerate(nums):
            missing = missing ^ item ^ i + 1
        return missing

更加专业版: 利用Python特性

def missingNumber(self, nums):
    # O(n) TC. O(n) SC
    return reduce(operator.xor, nums + range(len(nums)+1))
def missingNumber(self, nums):
    # O(1) SC
    # 观察异或规律。Xoring 0..n results in [n, 1, n+1, 0][n % 4]
    n = len(nums)
    return reduce(operator.xor, nums) ^ [n, 1, n+1, 0][n % 4]

③利用set

def missingNumber(self, nums: List[int]) -> int:
        return (set(range(len(nums) + 1)) - set(nums)).pop()
        #相减后剩下一个数(的数量为1而不是被减到0),pop()弹出就是它。


新鲜事 原文

优先队列是堆么。(记得好像说是堆实现方式是优先队列?)


新鲜事 原文

知识框架:具体本地写✍🏻️好来!
① (1) (2)


(1)
(2)
...


活动打卡代码 AcWing 63. 不同路径 II

int uniquePathsWithObstacles(vector<vector<int>>& o) {
        //和62多了一点障碍物
        int n = o.size(); //行数
        if (!n) return 0; //LC特色:空的返回0
        int m = o[0].size(); //列数
        vector<vector<int>> f(n, vector<int>(m)); //n行m列
        for (int i = 0; i < n; i++)
            for (int j = 0; j < m; j++)
                if (!o[i][j]){
                    if (!i && !j) f[i][j] = 1; //起点
                    else{ //if (i)即 i != 0
                        if (i) f[i][j] += f[i - 1][j]; //从上到下,
                        if (j) f[i][j] += f[i][j - 1]; //从左到右
                    }
                }
        return f[n - 1][m - 1];
        //由于n,m 初始化和转移时定义为下标
        //所以[n-1]代表抵达第n行的方案
        //总方案就是共n行,m列的状态
    }


新鲜事 原文

懂了原来(if x)记反了。。 $if~(x)$等价于 $if~(x!=0)$ 而$if~(!x)$等价于$if~(x == 0)$ if not x确实,x == 0.反推if (x)即可


活动打卡代码 LeetCode 61. 旋转链表

ListNode* rotateRight(ListNode* head, int k) {
        if (!head) return head; //LC特色,空的时候不用移动直接返回空
        int n = 0;
        ListNode* tail;
        for (auto p = head; p; p=p->next){
            tail = p; //尾节点
            n ++ ;
        }
        // k > n.没意义,直接把它减到(0, n)之间
        k %= n;
        // 移动k次 《=》 把后面的k个节点移到前面
        // 第一步①n - k-1节点指向->∅
        // ②head指向->n - k节点
        // 尾节点->头节点
        if (!k) return head;

        auto p = head;
        for (int i = 0; i < n - k - 1; i++)
            p = p->next;
        //走n-k-1次 抵达节点
        //尾节点->头节点
        tail->next = head;
        head = p->next; // 上行循环后即p是第n-k-1_th节点 所以head指向它后面那个节点就可以了
        p->next = nullptr; //空
        return head;
    }