ARST打卡第228周[228/521]
Algorithm
lc198_打家劫舍
dp
自己的思路一次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 | class Solution { |
题解思路
和我的思路相似,但比我的更清晰简洁,并且通过只维护前面两个值大幅减少了空间占用。
- 偷窃第 k 间房屋,那么就不能偷窃第 k−1 间房屋,偷窃总金额为前 k−2 间房屋的最高总金额与第 k间房屋的金额之和。
- 不偷窃第 k 间房屋,偷窃总金额为前 k−1 间房屋的最高总金额。
1 | class 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
Share-查询并删除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 | wget https://repo1.maven.org/maven2/com/madgag/bfg/1.14.0/bfg-1.14.0.jar |