93: restore IP addresses
92: reverse linked list II
这个题目翻转链表指定范围内的nodes,并且要求O（N）, O(1)空间，这个题目一看就感觉会有很多辅助指针，先找到m所在位置，然后开始翻转链表操作，直到n，最后再对链表进行一些修改，这个题目也是一个dummy node使用的一个例子，因为在这个过程中，链表的头结点可能被修改，所以需要用一个辅助头指针来进行corner case的处理。 这个题目大致算法不难，但是对于指针的 操作还是要小心处理，防止NULL指针的不合理操作。
91： decode way
看到这个题目求 求解方案有多少个，就感觉用一维dp来做，分析后发现和claimbing stairs差不多，一般情况下induction rule = M[i-1] + M[i-2]， 但是有很多条件限制
case1: 第一位不能为'0'
case2: 当前字符如果为'0'，最后那个字符不能decode, 所以此时M[i] 最多 = M[i-2], 否则， M[i] = M[i-1];
case3: 当前字符的前一个字符不为'0', 并且最后两个字符组成的int <= 26 && >= 0, M[i] += M[i-2]
这个题目这里用到一个技巧，对于string的dp，我们通常把DP数组声明成length+1，这样就更方便处理。
78： subset
90： subsetII
这两个问题都属于dfs, 第二个问题是第一个问题的follow up, 如果存在duplicates的话怎么去处理。这个问题还需要注意的一点是题目要求结果是按照升序排序的，所以我们在做之前，需要对这个数组进行sort才能得到正确的结果。
subset的DFS树，其实就是二叉树，分别代表加当前数字和不加当前数字，所以在每一层，call 两次DFS.
对于如果有duplicates的处理，也可以从DFS树看出来， 在不加当前数字那个分叉，如果当前数字 == 后面那个数字，就没有下面那个不加数字的那个分支了，直到出现新的数字为止。所以只需要在原来的基础上添加一个条件判断就可以了。
要注意是在当前层看后面那个元素，来决定当前层是否往右边那个不加元素的分支走，而不是在当前层往前看。
89: grey code
感觉这个题目还是很难发现规律，需要找到递归式推出由n-1 --> n的grey的表示方法。
n的grey表达式 = n-1的grey表达式逆向 + （1 《 (n-1)）, 并且n的grey表达式的前半部分是不需要改变的。每次直接往rst里面push函数就可以了。
class Solution {
public:
vector<int> grayCode(int n) {
vector<int> rst;
rst.push_back(0);
if (n == 0) return rst;
rst.push_back(1);
for (int i = 2; i <= n; i++) {
int size1 = rst.size();
for (int j = size1-1; j >= 0; j--) {
rst.push_back(rst[j] + (1 << (i-1)));
}
}
return rst;
}
};
87: scrambling string
86: partition list
这个题目还算是简单的，但是要注意这种对原链表进行拆分的题目，不要忘记把应该断开的地方断开，不然会形成一个循环链表，死Bug。
85:maximum rectangle
84:largest rectangle in histogram
83: remove duplicates from sorted list I
82: remove duplicates from sorted listII
第一个题目很简单，slow, fast指针的移动操作， 关键是第二题之前一直用的是含有flag的那种slow , fast指针的做法，也能做出来，但是很麻烦，而且效率不高，在网上看了下别人做的solution,确实简单明了不少啊！这里把solution贴出来，很巧妙，每次比较fast 和fast->next的值是否相同，如果相同，那么就一直找，找到一个和fast不相同的值为止，然后pre指向这个值，下次如果cur->val ！= cur->next->val的时候，pre先向前移动一位，说明之前那个值需要留下，也说明是只出现了一次的值。 效率高了不少。从此跟flag那种做法告别了。
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if (head == NULL) return NULL;
ListNode* dummy = new ListNode(0);
dummy->next = head;
ListNode* pre = dummy;
ListNode* cur = head;
while (cur && cur->next) {
if (cur->val == cur->next->val) {
while (cur->next && cur->val == cur->next->val) {
cur = cur->next;
}
pre->next = cur->next;
} else {
pre = cur;
}
cur = cur->next;
}
return dummy->next;
}
};
这个题目的思想应用在sorted array 去重，其实思想理解起来很简单，就是fast ！＝ fast－》next 有两种情况，这两种情况下的处理是不相同的，下面红色部分就是这两种不相同的情况下的处理方式。 每次比较当前和当前的下一个元素。
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if (nums.size() <= 1) return 1;
int slow = -1;
int fast = 0;
for (; fast < nums.size(); fast++) {
if (nums[fast] != nums[fast+1]) {
nums[++slow] = nums[fast];
} else {
while (nums[fast] == nums[fast+1]) {
fast++;
}
nums[slow+1] = nums[fast+1];
}
}
return slow+1;
}
};
81:search in rotated arrayII
这个题目是含有duplicates的情况，我们需要分三种情况讨论，根据left 和 mid值的比较，容易出错的地方在于，当去判断target在不在一个范围内的时候，需要包括左右边界，即 >= left 和 <= right, 这样的话就会包含如果target就是边界数的情况.否则会出现bug.
80: remove duplicates in sorted arrayII
在sorted array里面去重， 保留两个重复字符，去重的题目有很多种类型，保留一个，保留两个，一个不留，这类题目都是可以用快慢指针来对字符串进行处理。保留两个说明一开始不管怎么样，slow可以直接放在idx = 2的位置，然后每次fast 与 slow-2位置字符进行比较。数一个不留的情况下，稍微复杂一些。
79: word search
这个题目是搜索单词，能直接想到的方法是对每一个与word的第一个char相等的位置进行DFS+back tracing, 这里用到back tracing的原因是每次回退到某一个位置，从另一个path走，之前走过的也都是unvisited的，可以再次搜索。因为这里的DFS其实是属于穷尽搜索，需要走遍所有的可能路径去搜索确定的路径。当穷尽搜索的时候，即必须走过所有可能路径的时候我们才需要用到DFS+back tracing， 如果只是一般搜索的时候，就可以用DFS+ mark visitI来做，效果类似BFS。
还要注意一点的是，结束条件要小心，比如这个题目我一开始的结束条件写成了： if (idx == word.size()) return true; 但是后面做的操作，有比较word[idx+1] == ..这样的话如果此时idx == word.size()-1,就会发生越界，所以我们的结束条件，应该是 if (idx == word.size()-1) return true;，所以在写程序的时候不能总是按惯性去写，不同的题目处理问题方式不同，代码也有所改变，要防止发生一些小bug。还有一个地方容易出错就是如果当前访问的node之前已经访问过了，是return true？ false? 这个都要通过含义去判断。
这个题目我觉得比一般的DFS要难一些，因为加上了另外一个条件的判断，需要同时去匹配字符，结束条件相应多了一条，并且对于二维矩阵的DFS mark visited的做法，一般是不需要另外去开辟另一个二维矩阵来mark visited的，可以直接以一个特殊字符比如“#”来代表已经访问过，这样就节省了很多空间。
77: combination
DFS求所有解的问题，画出DFS树出来，然后就能正确地写出程序了。树的每一层代表什么含义，每一层有多个叉。DFS循环调用多少次。还有一个 cur level来记录有没有到达树的最后一层，即一条path有没有结束。
76: minimum window substring
这个题目属于sliding window里面好写的一类题，就是变长的sliding window， 由两个指针模拟窗口，先right指针走，并且同时匹配字符，如果完全匹配，此时固定right， 移动left, 每次移出的元素要在map里面还原，如果还原之后，仍然所有字符match， 那么仍然移动left,并且每次更新最小值，直到不再match，再去移动right，直至right移动到string 尾部。
时间复杂度O（2 *n）,right和left指针都只是从头到尾分别遍历一遍字符串。
75: sorted colors
这个是属于quick sort partition的变形， quick sort partition是一个挡板，一个指针，这个题目是用了两个挡板，1个指针，但是特别需要注意的是sort k colors，不能再继续用挡板法来做了，对于2->k的实现，只要利用分而治之，每次sort好首尾两个颜色，这样时间复杂度O(K/2 * N),空间复杂度为O(1)
88: merge sorted array
这个题目看似简单，但是跟之前merge不同的是，要求inplace merge, 我们不能开辟一个新的数组空间， 但是因为nums1的空间足够大， 我们可以将nums1看做是结果数组，如果从前往后进行merge的话，会出现nums2 覆盖nums1的情况，我们可以从后往前进行merge，这样的话nums1就相当于一个新的数组了。
这个图能够很好地表示这个题目中的思想。3个指针，1个指向nums1 n处, nums2的m处，最后那个指向nums1的n+m-1处。
No comments:
Post a Comment