二刷List2019年03月30日

162. Set Matrix Zeroes
void setZeroes(vector<vector<int>> &matrix) { // write your code here //用第一行和第一列存 有0的列 和 有 0的行 //先判断记录第一行，第一列里面是否有0，有0的话全行，全列后面变0. const int m = matrix.size(); if(m == 0){ return; } const int n = matrix[0].size(); int firstRow = 0, firstCol = 0; for(int j = 0; j < n; j++){ if(matrix[0][j] == 0){ firstRow = 1; break; } } for(int i = 0; i < m; i++){ if(matrix[i][0] == 0){ firstCol = 1; break; } } for(int i = 1; i < m; i++){ for(int j = 1; j < n; j++){ if(matrix[i][j] == 0){ matrix[i][0] = 0; matrix[0][j] = 0; } } } for(int i = 1; i < m; i++){ if(matrix[i][0] == 0){ for(int j = 1; j < n; j++){ matrix[i][j] = 0; } } } for(int j = 1; j < n; j++){ if(matrix[0][j] == 0){ for(int i = 1; i < m; i++){ matrix[i][j] = 0; } } } if(firstRow){ for(int j = 0; j < n; j++){ matrix[0][j] = 0; } } if(firstCol){ for(int i = 0; i < m; i++){ matrix[i][0] = 0; } } return; }

121. Word Ladder II 提交了无数次，还是不过，看不出原因，先这样吧 sigh
vector<vector<string>> findLadders(string &start, string &end, unordered_set<string> &dict) { // write your code here // BFS找最短路径，然后依据最短路径DFS找所有可能。 //剩下的就看实现了 // Let's go!!! unordered_map<string, vector<string>> next; unordered_map<string, int> steps; vector<vector<string>> res; dict.insert(end); if(dict.size() == 0){ return res; } const int sLen = start.size(); int dist = 1; std::queue<string> q; q.push(start); dict.erase(start); steps[start] = 1; while(!q.empty()){ int sizeQ = q.size(); dist++; int breakFlag = 0; for(int i = 0; i < sizeQ; i++){ string oldTemp = q.front(); q.pop(); //if(oldTemp == end){ // breakFlag = 1; // break; //} string temp = oldTemp; // find match for each char for(int j = 0; j < sLen; j++){ char oldChar = temp[j]; for(char c = 'a'; c <= 'z'; c++){ if(oldChar == c){ continue; } temp[j] = c; if(dict.find(temp) != dict.end()){ q.push(temp); dict.erase(temp); next[oldTemp].push_back(temp); steps[temp] = steps[oldTemp] + 1; } } temp[j] = oldChar; } } if(breakFlag == 1){ break; } } vector<string> resElem; resElem.push_back(start); dfs(start, end, next, steps, res, resElem); return res; } void dfs(string &start, string &end, unordered_map<string, vector<string>> &next, unordered_map<string,int> &steps, vector<vector<string>> &res, vector<string> &resElem){ if(start == end){ res.push_back(resElem); return; } for(auto str : next[start]){ if(steps[str] == steps[start] + 1){ resElem.push_back(str); dfs(str, end, next, steps, res, resElem); resElem.pop_back(); } } }
58. 4Sum  */
vector<vector<int>> fourSum(vector<int> &numbers, int target) { // write your code here // two sum 的办法 //复杂度 O(n^3) vector<vector<int>> res; const int size = numbers.size(); if(size < 4){ return res; } sort(numbers.begin(), numbers.end()); for(int i = 0; i < size; i++){ if(i > 0 && numbers[i] == numbers[i - 1]){ continue; } for(int j = i + 1; j < size; j++){ if(j > i + 1 && numbers[j] == numbers[j - 1]){ continue; } int newTarget = target - (numbers[i] + numbers[j]); int left = j + 1; int right = size - 1; while(left < right){ if(left > j + 1 && numbers[left] == numbers[left - 1]){ left++; continue; } int sum = numbers[left] + numbers[right]; if(sum == newTarget){ vector<int> elem(4, 0); elem[0] = numbers[i]; elem[1] = numbers[j]; elem[2] = numbers[left]; elem[3] = numbers[right]; res.push_back(elem); left++; } else if (sum < newTarget){ left++; } else{ right--; } } } } return res; }
vector<vector<int>> fourSum(vector<int> &numbers, int target) { // write your code here //使用dfs，类似于sum_combination vector<vector<int>> res; const int size = numbers.size(); if(size < 4){ return res; } sort(numbers.begin(), numbers.end()); vector<int> resElem; dfs(numbers, target, res, resElem, 0); return res; } void dfs(vector<int> &numbers, int target, vector<vector<int>> &res, vector<int> &resElem, int start){ if(resElem.size() == 4){ if(target == 0){ res.push_back(resElem); } return; } for(int i = start; i < numbers.size(); i++){ if(i > start && numbers[i] == numbers[i - 1]){ continue; } resElem.push_back(numbers[i]); dfs(numbers, target - numbers[i], res, resElem, i + 1); resElem.pop_back(); } }

36. Reverse Linked List II

ListNode * reverseBetween(ListNode * head, int m, int n) { // write your code here if(head == NULL || head->next == NULL){ return head; } if(m == n){ return head; } ListNode *dummy = new ListNode(0); dummy->next = head; ListNode *copy = dummy; for(int i = 0; i < m - 1; i++){ dummy = dummy->next; } ListNode *preStart = dummy; ListNode *start = dummy->next; dummy = dummy->next; ListNode *pre = NULL; for(int i = 0; i < n - m + 1; i++){ ListNode *temp = dummy->next; dummy->next = pre; pre = dummy; dummy = temp; } start->next = dummy; preStart->next = pre; return copy->next; }