ARTS 第 3 周

每周一道算法、点评一篇英文技术文章、学习一个技术技巧、分享一个技术观点和思路

Algorithm

Problem: Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Examples:

Given “abcabcbb”, the answer is “abc”, which the length is 3.

Given “bbbbb”, the answer is “b”, with the length of 1.

Given “pwwkew”, the answer is “wke”, with the length of 3.

Note that the answer must be a substring, “pwke” is a subsequence and not a substring.

思路一

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 lengthOfLongestSubstring(String s) {
if(s.length()<2){
return s.length();
}
int length = 1;
int i1 = 0, i2 = 1;
while (i2 < s.length() && i1 + length <= s.length()) {
if (i1 == i2) {
i2++;
continue;
}
String s1 = s.substring(i1, i1 + (i2 - i1));
String s2 = s.substring(i2, i2 + 1);
if (s1.contains(s2)) {
i1++;
} else {
length = (i2 - i1 + 1) > length ? (i2 - i1 + 1) : length;
i2++;
}
}
return length;
}
}

best 97.56%

优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public int lengthOfLongestSubstring(String s) {
int n = s.length(), ans = 0;
Map<Character, Integer> map = new HashMap<>(); // current index of character
// try to extend the range [i, j]
for (int j = 0, i = 0; j < n; j++) {
if (map.containsKey(s.charAt(j))) {
i = Math.max(map.get(s.charAt(j)), i);
}
ans = Math.max(ans, j - i + 1);
map.put(s.charAt(j), j + 1);
}
return ans;
}
}

Review

Pro Git 第二版

Git 与其它版本控制的区别。

大部分系统以文件变更列表的方式存储信息,它们保存的信息看作是一组基本文件和每个文件随时间逐步累积的差异。 存储每个文件与初始版本的差异

Git 更像是把数据看作是对小型文件系统的一组快照,每次你提交更新,或在 Git 中保存项目状态时,它主要对当时的全部文件制作一个快照并保存这个快照的索引。 存储项目随时改变的快照

Git merge 和 rebase 的区别

现在 Git 中有两个分支 experimentmaster

使用 merge 合并,它会把两个分支的最新快照(C3C4)以及二者最近的共同祖先(C2)进行三方合并,合并的结果是生成一个新的快照(并提交)。

merge

还可以使用 rebase 合并,它会提取在 C4 中引入的补丁和修改,然后在 C3 的基础上应用一次。其实就是将提交到某一分支上的所有修改都移至另一分支上。

现在回到 master 分支,进行一次快进合并。

1
2
git checkout master
git merge experiment

以上内容均来源于Pro Git 第二版

Tip

最近在使用 git stash 命令时,遇到了一个问题。

我先使用 git stash 让工作目录保持干净,然后 git pull 更新。现在使用 git stash pop 还原储藏并且将栈上弹出。然后冲突了,解决冲突。

然后使用 git stash list 查看。咦?怎么还存在,我再 git stash pop 好吧,又冲突,再解决。

然后使用 git stash list 查看。咦?怎么还存在,我再 git stash pop 好吧,又冲突,再解决。

……

后来才知道,如果使用 git stash pop 时,发生冲突需要合并时,只还原储藏并不会删除栈。需要手动解决冲突,手动删除储藏。

可以使用 git stash drop 加上将要移除的储藏的名字来移除它。

Share

最近亚马逊上的书打折,看见《重构:改善既有代码的设计》、《领域驱动设计:软件核心复杂性应对之道》、《编程珠玑》等等赫然在列,好想买。 想到去年双十一买的书还有未拆封的,又担心买了不看。不可否认买书是有快感的,因为在买的时候已经安排好了学习计划。等书到了,就懒得看或者只拆开就放一边了。通过书籍来学习是没问题了,现在是只有买没有学,是毫无意义的。与其多买几本书,不如把现有的书看完。

技术类书籍不便宜,要买就要买经典的,不要随便买。

(完)