ARST打卡第228周[228/521]

2023-09-16 1554 words 4 minutes

Contents

Algorithm

lc198_打家劫舍

自己的思路一次AC，但复杂了

看完题解发现自己后面想着标记想偏了，想复杂了，不过自己的版本可以简化成题解版本，也记录在下面吧 思路: dp[i-2]+nums[i]> dp[i-1], dp[i]=dp[i-2]+nums[i] else dp[i]=dp[i-1] 这里考虑dp[i]是选了nums[i]，需要打标记的

但是还得分情况考虑。因此改成dp[size][2]表示选没选当下nums[i]的dp最大值。状态转移如下:

没选当前值的最大可以选前面两个所有最大的dp[i][0] = max(dp[i-1][1], dp[i-1][0], dp[i-2][0], dp[i-2][1])
选了当前值的状态转移则加上当前值,并且不能让前面有选择dp[i][1]=max(dp[i-1][0]+nums[i], dp[i-2][1]+nums[i], dp[i-2][0]+nums[i])

进行公式提取，得到简化版本:

选当前值时能拿到前面的最大值 maxWhenCur=max(dp[i-1][0], dp[i-2][1], dp[i-2][0])
选了的 dp[i][1]=maxWhenCur+nums[i]
没选的 dp[i][0]=max(maxWhenCur, dp[i-1][1])

最后算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24


class Solution {
public:
    int rob(vector<int>& nums) {
        int sz = nums.size();
        if (sz == 1) {
            return nums[0];
        }
        if (sz == 2) {
            return max(nums[0], nums[1]);
        }
        vector<vector<int>> dp(sz, vector<int>(2));
        dp[0][0] = 0;
        dp[0][1] = nums[0];
        dp[1][0] = nums[0];
        dp[1][1] = nums[1];
        int maxWhenCur = 0;    
        for (int i = 2; i < sz; i++) {
            maxWhenCur = max(max(dp[i-1][0], dp[i-2][1]), dp[i-2][0]);
            dp[i][1] = maxWhenCur + nums[i];
            dp[i][0] = max(maxWhenCur, dp[i-1][1]);
        }
        return max(dp[sz-1][0], dp[sz-1][1]);
    }
};

题解思路

和我的思路相似，但比我的更清晰简洁，并且通过只维护前面两个值大幅减少了空间占用。

偷窃第 k 间房屋，那么就不能偷窃第 k−1 间房屋，偷窃总金额为前 k−2 间房屋的最高总金额与第 k间房屋的金额之和。
不偷窃第 k 间房屋，偷窃总金额为前 k−1 间房屋的最高总金额。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20


class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) {
            return 0;
        }
        int size = nums.size();
        if (size == 1) {
            return nums[0];
        }
        int first = nums[0], second = max(nums[0], nums[1]);
        for (int i = 2; i < size; i++) {
            int temp = second;
            second = max(first + nums[i], second);
            first = temp;
        }
        return second;
    }
};
// 链接：https://leetcode.cn/problems/house-robber/solutions/263856/da-jia-jie-she-by-leetcode-solution/

Review

Vim registers: The basics and beyond

It has happened to all of us. We yank some text, than delete some other, and when we try to paste the yanked text, it’s not there anymore, vim replaced it with the text that you deleted, then you need to go there and yanked that text again. Well, as I said, vim will always replace the unnamed register, but of course we didn’t lose the yanked text, vim would not have survived that long if it was that dumb, right?

vim automatically populates what is called the numbered registers for us. As expected, these are registers from “0 to “9. “0 will always have the content of the latest yank, and the others will have last 9 deleted text, being “1 the newest, and “9 the oldest. So if you yanked some text, you can always refer to it using “0p.

因此再也不会失去last yank 了。“0p 或者 vim 插入模式 ctrl+r 0。

Tips

git分批上传大文件

查询

1

git rev-list --objects --all | git cat-file --batch-check='%(objecttype) %(objectname) %(objectsize) %(rest)' | awk '/^blob/ {print $3, $4}' | sort -n -k2,2 > file_sort

上面 sort 没生效，按照下面 vim sort 再操作一遍:

打开您想要排序的文本文件：
1

vim your_file.txt
进入 Vim 的命令模式（按 Esc 键）。
选择要排序的文本数据。在文本中移动到您想要排序的行上，并按 Shift + V 进入可视行模式，接着按 : 进入命令行模式。然后，输入以下命令：
1

:'<,'>!sort -n -k1,1
这个命令会对当前选定的文本进行排序，其中 -n 选项表示数值排序，-k1,1 表示按照第一列（第一个字段）进行排序。'<,'> 表示对选中的行进行操作。
按 Enter 键执行排序命令。Vim 将会按照第一列的数值大小对您选择的文本进行排序。
G 跳转到文本最后观察自己的git大文件
如果您需要保存更改，请在命令模式下输入 :w 并按 Enter。
最后，退出 Vim 编辑器。您可以在命令模式下输入 :q 并按 Enter，或者使用 :wq 保存并退出。

这样，您就可以按照文本的第一列数值进行排序。请确保在进行排序之前正确选择要排序的数据。

删除git大文件

专业的BFG删大文件 BFG Repo-Cleaner

本地测试

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19


wget https://repo1.maven.org/maven2/com/madgag/bfg/1.14.0/bfg-1.14.0.jar
vim ~/.aliasrc
❯ tail ~/.aliasrc  -n 1
alias bfg="java -jar /root/download/bfg-1.14.0.jar"
❯ source ~/.aliasrc
❯ bfg --strip-blobs-bigger-than 50M  .

Using repo : /root/code/XXX/./.git

## ...中间一堆信息
BFG run is complete! When ready, run: git reflog expire --expire=now --all && git gc --prune=now --aggressive

❯  git reflog expire --expire=now --all && git gc --prune=now --aggressive
Counting objects: 91623, done.
Delta compression using up to 6 threads.
Compressing objects:  99% (83266/83457)
############################这里压缩可能要等半年（大概40分钟，取决于仓库大小和单核性能，没法多进程）##########################################
Writing objects: 100% (91623/91623), done.
Total 91623 (delta 56130), reused 26304 (delta 0)