记住的经典问题和解法
1，lintcode 95. Validate Binary Search Tree
class Solution { public: /** * @param root: The root of binary tree. * @return: True if the binary tree is BST, or false */ bool isValidBST(TreeNode * root) { // write your code here if(root == NULL){ return true; } if(root->left == NULL && root->right == NULL){ return true; } if(root->left != NULL){ if(root->left->val < root->val){ if(root->left->right != NULL && root->left->right->val >= root->val){//开始debug第一轮，这个条件忽略了。 return false; //注意这个条件，在分问题中不能解决的条件，要放在分前解决 } } else{ return false; } } if(root->right != NULL){ if(root->right->val > root->val){ if(root->right->left != NULL && root->right->left->val <= root->val){ return false; /注意这个条件，在分问题中不能解决的条件，要放在分前解决 } } else{ return false; } } return isValidBST(root->left) && isValidBST(root->right);// debug第二轮，所有的判断为true的条件放在这里，要等左右两边的fasle条件都遍历后，再判断左右子树是否有效！！！ } };
2，66. Binary Tree Preorder Traversal
方法1：
stack
class Solution { public: /** * @param root: A Tree * @return: Preorder in ArrayList which contains node values. */ vector<int> preorderTraversal(TreeNode * root) { // write your code here vector<int> res; if(root == NULL){ return res; } stack<TreeNode*> stk; stk.push(root); while(!stk.empty()){ TreeNode* temp = stk.top(); stk.pop(); res.push_back(temp->val); if(temp->right != NULL){ stk.push(temp->right); } if(temp->left != NULL){ stk.push(temp->left); } } return res; } };
方法2：
recursion
class Solution { public: /** * @param root: A Tree * @return: Preorder in ArrayList which contains node values. */ vector<int> preorderTraversal(TreeNode * root) { // write your code here vector<int> res; if(root == NULL){ return res; } vector<int> left = preorderTraversal(root->left); vector<int> right = preorderTraversal(root->right); res.push_back(root->val); res.insert(res.end(), left.begin(), left.end()); res.insert(res.end(), right.begin(), right.end()); return res; } };
3， 433. Number of Islands
//BFS的模板式运用 // 空间复杂度 O(m * n),时间复杂度O(m * n)
class Solution { public: /** * @param grid: a boolean 2D matrix * @return: an integer */ struct node{ int x, y; node(int a, int b){ x = a; y = b; } }; const vector<int> dx = {-1, 1, 0, 0}; const vector<int> dy = {0, 0, -1, 1}; int numIslands(vector<vector<bool>> &grid) { // write your code here const int m = grid.size(); if(m == 0){ return 0; } int res = 0; const int n = grid[0].size(); for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ if(grid[i][j] == 1){ res++; std::queue<node> q; q.push(node(i, j)); while(!q.empty()){ node temp = q.front(); q.pop(); for(int k = 0; k < 4; k++){ int newX = temp.x + dx[k]; int newY = temp.y + dy[k]; if(newX < 0 || newX >= m || newY < 0 || newY >= n || grid[newX][newY] == 0){ continue; } q.push(node(newX, newY)); grid[newX][newY] = 0; } } } } } return res; } };
DFS模板御用 // 空间复杂度O(1), 时间复杂度O(m * n)
class Solution { public: /** * @param grid: a boolean 2D matrix * @return: an integer */ const vector<int> dx = {-1, 1, 0, 0}; const vector<int> dy = {0, 0, -1, 1}; const int dirNum = 4; int numIslands(vector<vector<bool>> &grid) { // write your code here //用DFS再实现一遍 const int m = grid.size(); if(m == 0){ return 0; } const int n = grid[0].size(); int res = 0; for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ if(grid[i][j]){ ++res; dfs(grid, i, j); } } } return res; } void dfs(vector<vector<bool>> &grid, int i, int j){ if(i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size()){ return; } if(!grid[i][j]){ return; } grid[i][j] = false; for(int k = 0; k < dirNum; k++){ dfs(grid, i + dx[k], j + dy[k]); } } };
struct node{ int x; int y; node(int a, int b){ x = a; y = b; } }; bool hasPath(vector<vector<int>> &maze, vector<int> &start, vector<int> &destination) { // write your code here int m = maze.size(); if(m == 0){ return -1; } int n = maze[0].size(); vector<int> dx = {-1, 1, 0, 0}; vector<int> dy = {0, 0, -1, 1}; // define the left, right, up and down std::queue<node> q; int dis = 0; q.push(node(start[0], start[1])); while(!q.empty()){ int sizeQ = q.size(); dis++; for(int i = 0; i < sizeQ; i++){ node temp = q.front(); q.pop(); maze[temp.x][temp.y] = 2; // flag the visited position for(int i = 0; i < 4; i++){ int newX = temp.x + dx[i]; int newY = temp.y + dy[i]; while(!canStop(maze, newX, newY)){// judge when to stop newX += dx[i]; newY += dy[i]; } newX -= dx[i]; newY -= dy[i]; if(maze[newX][newY] != 2){ if(newX == destination[0] && newY == destination[1]){ return true; } q.push(node(newX, newY)); } } } } return false; } bool canStop(vector<vector<int>> &maze, int x, int y){ if(x < 0 || x >= maze.size() || y < 0 || y >= maze[0].size() || maze[x][y] == 1){ return true; } else{ return false; } }
788. The Maze II
class Solution { public: /** * @param maze: the maze * @param start: the start * @param destination: the destination * @return: the shortest distance for the ball to stop at the destination */ struct node{ int x; int y; node(int a, int b){ x = a; y = b; } }; int shortestDistance(vector<vector<int>> &maze, vector<int> &start, vector<int> &destination) { // write your code here int m = maze.size(); if(m == 0){ return -1; } int n = maze[0].size(); vector<vector<int>> dists(m, vector<int>(n, INT_MAX)); //需要这个来保存结果 vector<int> dx = {-1, 1, 0, 0}; vector<int> dy = {0, 0, -1, 1}; // define the left, right, up and down std::queue<node> q; int dis = 0; q.push(node(start[0], start[1])); dists[start[0]][start[1]] = 0; while(!q.empty()){ int sizeQ = q.size(); //for(int i = 0; i < sizeQ; i++){ { node temp = q.front(); q.pop(); maze[temp.x][temp.y] = 2; // flag the visited position //int minDis = INT_MAX; for(int i = 0; i < 4; i++){ int disTemp = dists[temp.x][temp.y]; int newX = temp.x; int newY = temp.y; while(!canStop(maze, newX, newY)){// judge when to stop newX += dx[i]; newY += dy[i]; disTemp++; } newX -= dx[i]; newY -= dy[i]; disTemp--; //minDis = min(minDis, disTemp); if(maze[newX][newY] != 2 && dists[newX][newY] > disTemp){ dists[newX][newY] = disTemp; q.push(node(newX, newY)); //注意这里在当前路径更短的情况下，把
//节点入栈 } } } } return dists[destination[0]][destination[1]] == INT_MAX ? -1 : dists[destination[0]][destination[1]]; } bool canStop(vector<vector<int>> &maze, int x, int y){ if(x < 0 || x >= maze.size() || y < 0 || y >= maze[0].size() || maze[x][y] == 1){ return true; } else{ return false; } } };
1367. Police Distance
和walls and gates一样，这样额外做一个状态matrix，把police点定义为0，空闲点定义为inf。
还是从所有target/destination点开始，不是从出发点开始。
这种题也可以从每个出发点一个个的找最近的police，但会出现重复搜索。
这里的方法其实是用单独一个状态matrix记忆搜索过的地方，避免重复搜索，用空间复杂度换时间复杂度。class Solution { public: /** * @param matrix : the martix * @return: the distance of grid to the police */ //BFS的典型应用。把这个研究透。 //BFS vs DFS //DFS 剥洋葱，按住一个点，一直剥到里；然后回来从另一个点再剥到里 //BFS 一圈圈的剥，先剥掉整个一圈再剥下一圈。考虑一圈上有很多动手的点，把这些点放入queue里。先把最外层所有的点存入queue，每当剥点最外层的一点后，把次外层的该点存入queue。这样保证最完成的所有点剥完后，开始次外层的点开始剥。 // BFS 是按层的，找最短路径的一般用它。 // DFS 是recursion遍历所有可能的一般用它。 struct node { int x, y; node(int a, int b){ this->x = a; this->y = b; } }; vector<vector<int> > policeDistance(vector<vector<int>> &matrix ) { int dx[4]={-1,1,0,0}; int dy[4]={0,0,-1,1};//matrix找周围四个的典型方法，上下左右 int n = matrix.size(); int m = matrix[0].size(); int sx, sy, ex, ey; vector<vector<int> > ans = matrix; //先把开始着手的点放入queue queue<node>nodequeue; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if(matrix[i][j] == 1) { nodequeue.push(node(i, j)); ans[i][j] = 0; } else { if(matrix[i][j] == 0) { ans[i][j] = INT_MAX; } else { ans[i][j] = -1; } } } } //开始一层层的执行 while(!nodequeue.empty()) { node head = nodequeue.front(); nodequeue.pop(); node New = head; for (int i = 0; i < 4; i++) { New.x = head.x + dx[i]; New.y = head.y + dy[i]; if(New.x < 0 || New.x >= n || New.y < 0 || New.y >= m || matrix[New.x][New.y] == -1 || ans[New.x][New.y] <= ans[head.x][head.y]) {//是否有效的判断条件 case By case，整体框架一样。 continue; } ans[New.x][New.y] = ans[head.x][head.y] + 1; nodequeue.push(New); } } return ans; } };
134. LRU Cache
/*
思路
维护一个HashMap和一个双向链表。
一个key对应到一个node。
每次get或者set的时候，把当前处理的node放到链表的尾巴上（most recent）。
如果链表满了，就把头上的那个node（least recent）删掉，并且在HashMap里也把对应的key删掉。
对于双向链表的处理，用一个dummy head和一个dummy tail，对于写程序会方便很多。
*/
为什么用双向链表？
因为有两个操作分别在头和尾部，头部是least recent，如果满了要删掉；尾部是新get或set的，要放入
尾部。使用双向链表可保证这两个操作都是O(1).而如果只用单向链表，在尾部的操作要遍历整个链表之后，
是O(n).
class node{ public: int val; int key; node *pre; node *next; node(int key, int val){ this->key = key; this->val = val; pre = NULL; next = NULL; } }; class LRUCache { private: unordered_map<int, node*> mp; int capacity; node *head; node *tail; public: /* * @param capacity: An integer */LRUCache(int capacity) { // do intialization if necessary this->capacity = capacity; head = new node(-1, -1); tail = new node(-1, -1); head->next = tail; tail->pre = head; } /* * @param key: An integer * @return: An integer */ int get(int key) { // write your code here if(mp.find(key) == mp.end()){ return -1; } else{ node *res = mp[key]; // delete this node and move to tail node *temp1 = res->next; node *temp2 = res->pre; temp1->pre = temp2; temp2->next = temp1;
//move to tail moveToTail(res); return res->val; } } /* * @param key: An integer * @param value: An integer * @return: nothing */ void set(int key, int value) { // write your code here if(mp.find(key) != mp.end()){ mp[key]->val = value; } if(mp.size() == capacity){ // delete head mp.erase(head->next->key); head->next = head->next->next; head->next->pre = head; } node *added = new node(key, value); mp[key] = added; moveToTail(added); } void moveToTail(node *target){ target->pre = tail->pre; tail->pre->next = target; target->next = tail; tail->pre = target; } };
436. Maximal Square
int maxSquare(vector<vector<int>> &matrix) {
// write your code here
// DP state: f[i][j] the length of square with i-th and j-th element as the right bottom point
// transition, cases:
// 1, if(matrix[i - 1][j - 1] == 1): f[i][j] = min(f[i - 1][j - 1], min(f[i - 1][j], f[i][j - 1])) + 1;
// 2, else: f[i][j] = 0;
// initial: f[0][j] = 0; f[i][0] = 0;
// results: maxLen = max(maxLen, f[i][j]); maxLen * maxLen
// rolling array to optimize the space
// two dimension can be reduced to 1 dimension O(N)
// one dimension to one vairbale O(1)
int m = matrix.size();
if(m == 0){
return 0;
}
int n = matrix[0].size();
int maxLen = 0;
vector<vector<int>> f(1 + 1, vector<int>(n + 1, 0));
for(int i = 1; i < m + 1; i++){
for(int j = 1; j < n + 1; j++){
if(matrix[i - 1][j - 1] == 1){
f[i%2][j] = min(f[(i - 1)%2][j - 1], min(f[i%2][j - 1], f[(i - 1) % 2][j])) + 1;
}
else{
f[i%2][j] = 0;
}
maxLen = max(maxLen, f[i%2][j]);
}
}
return maxLen * maxLen;
}
class Solution { public: /** * @param n: An integer * @return: An integer */ int numTrees(int n) { // write your code here //DP,此DP很难想到，要一个一个递推归纳。找规律 // n = 3，cases: // 个数是左子树的个数*右子树的个数 // 1, root as 3: f[2](left two nodes) * f[0] // 2, root as 2: f[1](left one node) * f[1](right one node) // 3, root as 1: f[0] * f[2](right two nodes) // 规律：f[i] += (f[k] * f[i - 1 - k]), k = 0, ..., i - 1. if(n < 2){ return 1; } std::vector<int> f(n + 1, 0); f[0] = 1; for(int i = 1; i <= n; i++){ for(int j = 0; j < i; j++){ f[i] += f[j] * f[i - 1 - j]; } } return f[n]; } };
106. Convert Sorted List to Binary Search Tree
class Solution { public: /* * @param head: The first node of linked list. * @return: a tree node */ TreeNode * sortedListToBST(ListNode * head) { // write your code here // Divide and conquer //1, slow and fast pointers finding the mid //2, pick the middle as root node //3, Divide //4, conquer if(head == NULL){ return NULL; } if(head->next == NULL){ TreeNode *root = new TreeNode(head->val); return root; } ListNode *dummy = new ListNode(0); dummy->next = head; ListNode *copy = head; ListNode *slow = head; ListNode *fast = head->next; ListNode *pre = dummy; while(fast != NULL && fast->next != NULL){ pre = slow; slow = slow->next; fast = fast->next->next; } pre->next = NULL; TreeNode *root = new TreeNode(slow->val); root->left = sortedListToBST(dummy->next); root->right = sortedListToBST(slow->next); return root; } };
100. Remove Duplicates from Sorted Array 以及follow up,最多允许两个相同的数。
class Solution {
public: /** * @param A: a list of integers * @return : return an integer */ int removeDuplicates(vector<int> &nums) { // write your code here int size = nums.size(); if (size == 0) { return 0; } int count = 0; for (int i = 1; i < size; i++) { if (nums[i] == nums[i - 1]) { count++; } { nums[i - count] = nums[i]; } } return size - count; } };
779. Generalized Abbreviation
vector<string> generateAbbreviations(string word) { vector<string> res{word}; helper(word, 0, res); return res; } void helper(string word, int pos, vector<string> &res) { for (int i = pos; i < word.size(); ++i) { for (int j = 1; i + j <= word.size(); ++j) {//从每一个起点开始，j代表了存在
的数字。
string t = word.substr(0, i); t += to_string(j) + word.substr(i + j); res.push_back(t); helper(t, i + 1 + to_string(j).size(), res);//正常的组合，下个start
就是i + 1,因为这里插入了数字，所以下个start 还要加上 数字的长度。这种类型的是DFS 组合类的变种
。还是从基本的组合类DFS入手，找到规律 } } }
1085. Longest Univalue Path
int longestUnivaluePath(TreeNode * root) { // Write your code here //肯定是recursion，如何recursion //这种在tree中需要找path的题目，定义recursion的返回值就是以root参与进去的path 长度，不是实际要求的结果 if(root == NULL){ return 0; } int res = 0; helper(root, res); return res; } int helper(TreeNode * root, int &res){ if(root == NULL){ return 0; } int left = helper(root->left, res); int right = helper(root->right, res); int curLeft = 0; if(root->left == NULL || root->left->val != root->val){ curLeft = 0; } else{ curLeft = left + 1; } int curRight = 0; if(root->right == NULL || root->right->val != root->val){ curRight = 0; } else{ curRight = right + 1; } res = max(res, curRight + curLeft); return max(curLeft, curRight); }
1272. Kth Smallest Element in a Sorted Matrix
int kthSmallest(vector<vector<int>> &matrix, int k) { // write your code here //找kth 还是要用binary search的 int m = matrix.size(); if(m == 0){ return -1; } int n = matrix[0].size(); int start = matrix[0][0];//最小值 int end = matrix[m - 1][n - 1]; //最大值 while(start + 1 < end){ //binary search int mid = start + (end - start) / 2; if(find(matrix, mid) < k){ //确定mid第几大值 和 k的关系 start = mid; } else{ end = mid; } } if(find(matrix, start) >= k){ return start; } else{ return end; } } int find(vector<vector<int>> &matrix, int target){ //这里很难想到，记住吧，作为这种sorted matrix寻找 target对应第几个元素的方法。 int n = matrix.size(); int i = n - 1; //从左下角开始 int j = 0; int cnt = 0; while(i >= 0 && j < n){ if(matrix[i][j] <= target){ cnt += i + 1; j++; } else{ i--; } } return cnt; }
386. Longest Substring with At Most K Distinct Characters
很有意思的解法：遍历时一直维护一个从当前位置以前，也即是以当前位置结尾的一个最长不同元素个数是K的
subsequence，通过使用hashMap
class Solution { public: /** * @param root: The root of binary tree. * @return: True if the binary tree is BST, or false */ bool isValidBST(TreeNode * root) { // write your code here if(root == NULL){ return true; } if(root->left == NULL && root->right == NULL){ return true; } if(root->left != NULL){ if(root->left->val < root->val){ if(root->left->right != NULL && root->left->right->val >= root->val){//开始debug第一轮，这个条件忽略了。 return false; //注意这个条件，在分问题中不能解决的条件，要放在分前解决 } } else{ return false; } } if(root->right != NULL){ if(root->right->val > root->val){ if(root->right->left != NULL && root->right->left->val <= root->val){ return false; /注意这个条件，在分问题中不能解决的条件，要放在分前解决 } } else{ return false; } } return isValidBST(root->left) && isValidBST(root->right);// debug第二轮，所有的判断为true的条件放在这里，要等左右两边的fasle条件都遍历后，再判断左右子树是否有效！！！ } };
2，66. Binary Tree Preorder Traversal
方法1：
stack
class Solution { public: /** * @param root: A Tree * @return: Preorder in ArrayList which contains node values. */ vector<int> preorderTraversal(TreeNode * root) { // write your code here vector<int> res; if(root == NULL){ return res; } stack<TreeNode*> stk; stk.push(root); while(!stk.empty()){ TreeNode* temp = stk.top(); stk.pop(); res.push_back(temp->val); if(temp->right != NULL){ stk.push(temp->right); } if(temp->left != NULL){ stk.push(temp->left); } } return res; } };
方法2：
recursion
class Solution { public: /** * @param root: A Tree * @return: Preorder in ArrayList which contains node values. */ vector<int> preorderTraversal(TreeNode * root) { // write your code here vector<int> res; if(root == NULL){ return res; } vector<int> left = preorderTraversal(root->left); vector<int> right = preorderTraversal(root->right); res.push_back(root->val); res.insert(res.end(), left.begin(), left.end()); res.insert(res.end(), right.begin(), right.end()); return res; } };
3， 433. Number of Islands
//BFS的模板式运用 // 空间复杂度 O(m * n),时间复杂度O(m * n)
class Solution { public: /** * @param grid: a boolean 2D matrix * @return: an integer */ struct node{ int x, y; node(int a, int b){ x = a; y = b; } }; const vector<int> dx = {-1, 1, 0, 0}; const vector<int> dy = {0, 0, -1, 1}; int numIslands(vector<vector<bool>> &grid) { // write your code here const int m = grid.size(); if(m == 0){ return 0; } int res = 0; const int n = grid[0].size(); for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ if(grid[i][j] == 1){ res++; std::queue<node> q; q.push(node(i, j)); while(!q.empty()){ node temp = q.front(); q.pop(); for(int k = 0; k < 4; k++){ int newX = temp.x + dx[k]; int newY = temp.y + dy[k]; if(newX < 0 || newX >= m || newY < 0 || newY >= n || grid[newX][newY] == 0){ continue; } q.push(node(newX, newY)); grid[newX][newY] = 0; } } } } } return res; } };
DFS模板御用 // 空间复杂度O(1), 时间复杂度O(m * n)
class Solution { public: /** * @param grid: a boolean 2D matrix * @return: an integer */ const vector<int> dx = {-1, 1, 0, 0}; const vector<int> dy = {0, 0, -1, 1}; const int dirNum = 4; int numIslands(vector<vector<bool>> &grid) { // write your code here //用DFS再实现一遍 const int m = grid.size(); if(m == 0){ return 0; } const int n = grid[0].size(); int res = 0; for(int i = 0; i < m; i++){ for(int j = 0; j < n; j++){ if(grid[i][j]){ ++res; dfs(grid, i, j); } } } return res; } void dfs(vector<vector<bool>> &grid, int i, int j){ if(i < 0 || j < 0 || i >= grid.size() || j >= grid[0].size()){ return; } if(!grid[i][j]){ return; } grid[i][j] = false; for(int k = 0; k < dirNum; k++){ dfs(grid, i + dx[k], j + dy[k]); } } };
787. The Maze
There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling
up, down, left or right, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.
Given the ball's start position, the destination and the maze, determine whether the ball could stop at the destination.
The maze is represented by a binary 2D array. 1 means the wall and 0 means the empty space. You may assume that the borders of the maze are all walls. The start and destination coordinates are represented by row and column indexes.
1.There is only one ball and one destination in the maze.
2.Both the ball and the destination exist on an empty space, and they will not be at the same position initially.
3.The given maze does not contain border (like the red rectangle in the example pictures), but you could assume the border of the maze are all walls.
5.The maze contains at least 2 empty spaces, and both the width and height of the maze won't exceed 100.
2.Both the ball and the destination exist on an empty space, and they will not be at the same position initially.
3.The given maze does not contain border (like the red rectangle in the example pictures), but you could assume the border of the maze are all walls.
5.The maze contains at least 2 empty spaces, and both the width and height of the maze won't exceed 100.
Have you met this question in a real interview?
Example
Given:
a maze represented by a 2D array
0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 0 1 1
0 0 0 0 0
start coordinate (rowStart, colStart) = (0, 4)
destination coordinate (rowDest, colDest) = (4, 4)
Return:true
- 找路径题目加了条件的
struct node{ int x; int y; node(int a, int b){ x = a; y = b; } }; bool hasPath(vector<vector<int>> &maze, vector<int> &start, vector<int> &destination) { // write your code here int m = maze.size(); if(m == 0){ return -1; } int n = maze[0].size(); vector<int> dx = {-1, 1, 0, 0}; vector<int> dy = {0, 0, -1, 1}; // define the left, right, up and down std::queue<node> q; int dis = 0; q.push(node(start[0], start[1])); while(!q.empty()){ int sizeQ = q.size(); dis++; for(int i = 0; i < sizeQ; i++){ node temp = q.front(); q.pop(); maze[temp.x][temp.y] = 2; // flag the visited position for(int i = 0; i < 4; i++){ int newX = temp.x + dx[i]; int newY = temp.y + dy[i]; while(!canStop(maze, newX, newY)){// judge when to stop newX += dx[i]; newY += dy[i]; } newX -= dx[i]; newY -= dy[i]; if(maze[newX][newY] != 2){ if(newX == destination[0] && newY == destination[1]){ return true; } q.push(node(newX, newY)); } } } } return false; } bool canStop(vector<vector<int>> &maze, int x, int y){ if(x < 0 || x >= maze.size() || y < 0 || y >= maze[0].size() || maze[x][y] == 1){ return true; } else{ return false; } }
788. The Maze II
There is a ball in a maze with empty spaces and walls. The ball can go through empty spaces by rolling
up, down, left or right, but it won't stop rolling until hitting a wall. When the ball stops, it could choose the next direction.
Given the ball's start position, the destination and the maze, find the shortest distance for the ball to stop at the destination. The distance is defined by the number of empty spaces traveled by the ball from the start position (excluded) to the destination (included). If the ball cannot stop at the destination, return -1.
The maze is represented by a binary 2D array. 1 means the wall and 0 means the empty space. You may assume that the borders of the maze are all walls. The start and destination coordinates are represented by row and column indexes.
1.There is only one ball and one destination in the maze.
2.Both the ball and the destination exist on an empty space, and they will not be at the same position initially.
3.The given maze does not contain border (like the red rectangle in the example pictures), but you could assume the border of the maze are all walls.
4.The maze contains at least 2 empty spaces, and both the width and height of the maze won't exceed 100.
2.Both the ball and the destination exist on an empty space, and they will not be at the same position initially.
3.The given maze does not contain border (like the red rectangle in the example pictures), but you could assume the border of the maze are all walls.
4.The maze contains at least 2 empty spaces, and both the width and height of the maze won't exceed 100.
Have you met this question in a real interview?
Example
Example 1:
Input:
(rowStart, colStart) = (0,4)
(rowDest, colDest)= (4,4)
0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 0 1 1
0 0 0 0 0
Output: 12
Explanation:
(0,4)->(0,3)->(1,3)->(1,2)->(1,1)->(1,0)->(2,0)->(2,1)->(2,2)->(3,2)->(4,2)->(4,3)->(4,4)
Example 2:
Input:
(rowStart, colStart) = (0,4)
(rowDest, colDest)= (0,0)
0 0 1 0 0
0 0 0 0 0
0 0 0 1 0
1 1 0 1 1
0 0 0 0 0
Output: 6
Explanation:
(0,4)->(0,3)->(1,3)->(1,2)->(1,1)->(1,0)->(0,0)
class Solution { public: /** * @param maze: the maze * @param start: the start * @param destination: the destination * @return: the shortest distance for the ball to stop at the destination */ struct node{ int x; int y; node(int a, int b){ x = a; y = b; } }; int shortestDistance(vector<vector<int>> &maze, vector<int> &start, vector<int> &destination) { // write your code here int m = maze.size(); if(m == 0){ return -1; } int n = maze[0].size(); vector<vector<int>> dists(m, vector<int>(n, INT_MAX)); //需要这个来保存结果 vector<int> dx = {-1, 1, 0, 0}; vector<int> dy = {0, 0, -1, 1}; // define the left, right, up and down std::queue<node> q; int dis = 0; q.push(node(start[0], start[1])); dists[start[0]][start[1]] = 0; while(!q.empty()){ int sizeQ = q.size(); //for(int i = 0; i < sizeQ; i++){ { node temp = q.front(); q.pop(); maze[temp.x][temp.y] = 2; // flag the visited position //int minDis = INT_MAX; for(int i = 0; i < 4; i++){ int disTemp = dists[temp.x][temp.y]; int newX = temp.x; int newY = temp.y; while(!canStop(maze, newX, newY)){// judge when to stop newX += dx[i]; newY += dy[i]; disTemp++; } newX -= dx[i]; newY -= dy[i]; disTemp--; //minDis = min(minDis, disTemp); if(maze[newX][newY] != 2 && dists[newX][newY] > disTemp){ dists[newX][newY] = disTemp; q.push(node(newX, newY)); //注意这里在当前路径更短的情况下，把
//节点入栈 } } } } return dists[destination[0]][destination[1]] == INT_MAX ? -1 : dists[destination[0]][destination[1]]; } bool canStop(vector<vector<int>> &maze, int x, int y){ if(x < 0 || x >= maze.size() || y < 0 || y >= maze[0].size() || maze[x][y] == 1){ return true; } else{ return false; } } };
1367. Police Distance
Given a matrix size of
Now please output a matrix size of
n x m, element 1 represents policeman, -1 represents wall and 0 represents empty.Now please output a matrix size of
n x m, output the minimum distance between each empty space and the nearest policeman- Given a matrix size of
n x m，n <= 200，m <= 200. - We guarantee that each empty space can be reached by one policeman at least.
Have you met this question in a real interview?
Example
Given mat =
[
[0, -1, 0],
[0, 1, 1],
[0, 0, 0]
]
return
[[2,-1,1],[1,0,0],[2,1,1]].The distance between the policeman and himself is 0, the shortest distance between the two policemen to other empty space is as shown above
Given mat =
[
[0, -1, -1],
[0, -1, 1],
[0, 0, 0]
]
return
[[5,-1,-1],[4,-1,0],[3,2,1]]还是从所有target/destination点开始，不是从出发点开始。
这种题也可以从每个出发点一个个的找最近的police，但会出现重复搜索。
这里的方法其实是用单独一个状态matrix记忆搜索过的地方，避免重复搜索，用空间复杂度换时间复杂度。class Solution { public: /** * @param matrix : the martix * @return: the distance of grid to the police */ //BFS的典型应用。把这个研究透。 //BFS vs DFS //DFS 剥洋葱，按住一个点，一直剥到里；然后回来从另一个点再剥到里 //BFS 一圈圈的剥，先剥掉整个一圈再剥下一圈。考虑一圈上有很多动手的点，把这些点放入queue里。先把最外层所有的点存入queue，每当剥点最外层的一点后，把次外层的该点存入queue。这样保证最完成的所有点剥完后，开始次外层的点开始剥。 // BFS 是按层的，找最短路径的一般用它。 // DFS 是recursion遍历所有可能的一般用它。 struct node { int x, y; node(int a, int b){ this->x = a; this->y = b; } }; vector<vector<int> > policeDistance(vector<vector<int>> &matrix ) { int dx[4]={-1,1,0,0}; int dy[4]={0,0,-1,1};//matrix找周围四个的典型方法，上下左右 int n = matrix.size(); int m = matrix[0].size(); int sx, sy, ex, ey; vector<vector<int> > ans = matrix; //先把开始着手的点放入queue queue<node>nodequeue; for(int i = 0; i < n; i++) { for(int j = 0; j < m; j++) { if(matrix[i][j] == 1) { nodequeue.push(node(i, j)); ans[i][j] = 0; } else { if(matrix[i][j] == 0) { ans[i][j] = INT_MAX; } else { ans[i][j] = -1; } } } } //开始一层层的执行 while(!nodequeue.empty()) { node head = nodequeue.front(); nodequeue.pop(); node New = head; for (int i = 0; i < 4; i++) { New.x = head.x + dx[i]; New.y = head.y + dy[i]; if(New.x < 0 || New.x >= n || New.y < 0 || New.y >= m || matrix[New.x][New.y] == -1 || ans[New.x][New.y] <= ans[head.x][head.y]) {//是否有效的判断条件 case By case，整体框架一样。 continue; } ans[New.x][New.y] = ans[head.x][head.y] + 1; nodequeue.push(New); } } return ans; } };
134. LRU Cache
Description
中文English
Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations:
get and set.get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.set(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
Have you met this question in a real interview?
Example
Example1
Input:
LRUCache(2)
set(2, 1)
set(1, 1)
get(2)
set(4, 1)
get(1)
get(2)
Output:
[1,-1,1]为什么用双向链表？
因为有两个操作分别在头和尾部，头部是least recent，如果满了要删掉；尾部是新get或set的，要放入
尾部。使用双向链表可保证这两个操作都是O(1).而如果只用单向链表，在尾部的操作要遍历整个链表之后，
是O(n).
class node{ public: int val; int key; node *pre; node *next; node(int key, int val){ this->key = key; this->val = val; pre = NULL; next = NULL; } }; class LRUCache { private: unordered_map<int, node*> mp; int capacity; node *head; node *tail; public: /* * @param capacity: An integer */LRUCache(int capacity) { // do intialization if necessary this->capacity = capacity; head = new node(-1, -1); tail = new node(-1, -1); head->next = tail; tail->pre = head; } /* * @param key: An integer * @return: An integer */ int get(int key) { // write your code here if(mp.find(key) == mp.end()){ return -1; } else{ node *res = mp[key]; // delete this node and move to tail node *temp1 = res->next; node *temp2 = res->pre; temp1->pre = temp2; temp2->next = temp1;
//move to tail moveToTail(res); return res->val; } } /* * @param key: An integer * @param value: An integer * @return: nothing */ void set(int key, int value) { // write your code here if(mp.find(key) != mp.end()){ mp[key]->val = value; } if(mp.size() == capacity){ // delete head mp.erase(head->next->key); head->next = head->next->next; head->next->pre = head; } node *added = new node(key, value); mp[key] = added; moveToTail(added); } void moveToTail(node *target){ target->pre = tail->pre; tail->pre->next = target; target->next = tail; tail->pre = target; } };
436. Maximal Square
Given a 2D binary matrix filled with 0's and 1's, find the largest square containing all 1's and return its area.
Have you met this question in a real interview?
Example
Example 1:
Input:
[
[1, 0, 1, 0, 0],
[1, 0, 1, 1, 1],
[1, 1, 1, 1, 1],
[1, 0, 0, 1, 0]
]
Output: 4
Example 2:
Input:
[
[0, 0, 0],
[1, 1, 1]
]
Output: 1163. Unique Binary Search Trees
中文English
Given n, how many structurally unique BSTs (binary search trees) that store values 1...n?
Have you met this question in a real interview?
Example
Given n = 3, there are a total of 5 unique BST's.
1 3 3 2 1
\ / / / \ \
3 2 1 1 3 2
/ / \ \
2 1 2 3class Solution { public: /** * @param n: An integer * @return: An integer */ int numTrees(int n) { // write your code here //DP,此DP很难想到，要一个一个递推归纳。找规律 // n = 3，cases: // 个数是左子树的个数*右子树的个数 // 1, root as 3: f[2](left two nodes) * f[0] // 2, root as 2: f[1](left one node) * f[1](right one node) // 3, root as 1: f[0] * f[2](right two nodes) // 规律：f[i] += (f[k] * f[i - 1 - k]), k = 0, ..., i - 1. if(n < 2){ return 1; } std::vector<int> f(n + 1, 0); f[0] = 1; for(int i = 1; i <= n; i++){ for(int j = 0; j < i; j++){ f[i] += f[j] * f[i - 1 - j]; } } return f[n]; } };
106. Convert Sorted List to Binary Search Tree
class Solution { public: /* * @param head: The first node of linked list. * @return: a tree node */ TreeNode * sortedListToBST(ListNode * head) { // write your code here // Divide and conquer //1, slow and fast pointers finding the mid //2, pick the middle as root node //3, Divide //4, conquer if(head == NULL){ return NULL; } if(head->next == NULL){ TreeNode *root = new TreeNode(head->val); return root; } ListNode *dummy = new ListNode(0); dummy->next = head; ListNode *copy = head; ListNode *slow = head; ListNode *fast = head->next; ListNode *pre = dummy; while(fast != NULL && fast->next != NULL){ pre = slow; slow = slow->next; fast = fast->next->next; } pre->next = NULL; TreeNode *root = new TreeNode(slow->val); root->left = sortedListToBST(dummy->next); root->right = sortedListToBST(slow->next); return root; } };
100. Remove Duplicates from Sorted Array 以及follow up,最多允许两个相同的数。
class Solution {
public: /** * @param A: a list of integers * @return : return an integer */ int removeDuplicates(vector<int> &nums) { // write your code here int size = nums.size(); if (size == 0) { return 0; } int count = 0; for (int i = 1; i < size; i++) { if (nums[i] == nums[i - 1]) { count++; } { nums[i - count] = nums[i]; } } return size - count; } };
779. Generalized Abbreviation
Write a function to generate the generalized abbreviations of a word.(order does not matter)
Have you met this question in a real interview?
Example
Example 1:
Input:
word = "word",
Output:
["word", "1ord", "w1rd", "wo1d", "wor1", "2rd", "w2d", "wo2", "1o1d", "1or1", "w1r1", "1o2", "2r1", "3d", "w3", "4"]
Example 2:
Input:
word = "today"
Output:
["1o1a1","1o1ay","1o2y","1o3","1od1y","1od2","1oda1","1oday","2d1y","2d2","2da1","2day","3a1","3ay","4y","5","t1d1y","t1d2","t1da1","t1day","t2a1","t2ay","t3y","t4","to1a1","to1ay","to2y","to3","tod1y","tod2","toda1","today"]vector<string> generateAbbreviations(string word) { vector<string> res{word}; helper(word, 0, res); return res; } void helper(string word, int pos, vector<string> &res) { for (int i = pos; i < word.size(); ++i) { for (int j = 1; i + j <= word.size(); ++j) {//从每一个起点开始，j代表了存在
的数字。
string t = word.substr(0, i); t += to_string(j) + word.substr(i + j); res.push_back(t); helper(t, i + 1 + to_string(j).size(), res);//正常的组合，下个start
就是i + 1,因为这里插入了数字，所以下个start 还要加上 数字的长度。这种类型的是DFS 组合类的变种
。还是从基本的组合类DFS入手，找到规律 } } }
1085. Longest Univalue Path
Given a binary tree, find the length of the longest path where each node in the path has the same value. This path may or may not pass through the root.
1.The length of path between two nodes is represented by the number of edges between them.
2.The given binary tree has not more than 10000 nodes. The height of the tree is not more than 1000.
2.The given binary tree has not more than 10000 nodes. The height of the tree is not more than 1000.
Have you met this question in a real interview?
Example
Example 1:
Input:
5
/ \
4 5
/ \ \
1 1 5
Output:
2
Example 2:
Input:
1
/ \
4 5
/ \ \
4 4 5
Output:
2
int longestUnivaluePath(TreeNode * root) { // Write your code here //肯定是recursion，如何recursion //这种在tree中需要找path的题目，定义recursion的返回值就是以root参与进去的path 长度，不是实际要求的结果 if(root == NULL){ return 0; } int res = 0; helper(root, res); return res; } int helper(TreeNode * root, int &res){ if(root == NULL){ return 0; } int left = helper(root->left, res); int right = helper(root->right, res); int curLeft = 0; if(root->left == NULL || root->left->val != root->val){ curLeft = 0; } else{ curLeft = left + 1; } int curRight = 0; if(root->right == NULL || root->right->val != root->val){ curRight = 0; } else{ curRight = right + 1; } res = max(res, curRight + curLeft); return max(curLeft, curRight); }
1272. Kth Smallest Element in a Sorted Matrix
Given a n x n matrix where each of the rows and columns are sorted in ascending order, find the kth smallest element in the matrix.
Note that it is the kth smallest element in the sorted order, not the kth distinct element.
You may assume k is always valid, 1 ≤ k ≤ n^2.
Have you met this question in a real interview?
Example
matrix = [
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
[ 1, 5, 9],
[10, 11, 13],
[12, 13, 15]
],
k = 8,
return 13.
int kthSmallest(vector<vector<int>> &matrix, int k) { // write your code here //找kth 还是要用binary search的 int m = matrix.size(); if(m == 0){ return -1; } int n = matrix[0].size(); int start = matrix[0][0];//最小值 int end = matrix[m - 1][n - 1]; //最大值 while(start + 1 < end){ //binary search int mid = start + (end - start) / 2; if(find(matrix, mid) < k){ //确定mid第几大值 和 k的关系 start = mid; } else{ end = mid; } } if(find(matrix, start) >= k){ return start; } else{ return end; } } int find(vector<vector<int>> &matrix, int target){ //这里很难想到，记住吧，作为这种sorted matrix寻找 target对应第几个元素的方法。 int n = matrix.size(); int i = n - 1; //从左下角开始 int j = 0; int cnt = 0; while(i >= 0 && j < n){ if(matrix[i][j] <= target){ cnt += i + 1; j++; } else{ i--; } } return cnt; }
386. Longest Substring with At Most K Distinct Characters
很有意思的解法：遍历时一直维护一个从当前位置以前，也即是以当前位置结尾的一个最长不同元素个数是K的
subsequence，通过使用hashMap
class Solution { public: int lengthOfLongestSubstringKDistinct(string s, int k) { int res = 0, left = 0; unordered_map<char, int> m; for (int i = 0; i < s.size(); ++i) { ++m[s[i]]; while (m.size() > k) { if (--m[s[left]] == 0) m.erase(s[left]); ++left; } res = max(res, i - left + 1); } return res; } };
Comments
Post a Comment