昨天进行了面试，感觉答的一般，今天也没有消息，估计有点寄了。现在把之前没来的寄放上的放上，今天的任务就是做做题，之后晚上回去吃个饭，早点睡觉，明天还是就是正式的找实习过程了，毕竟已经面试过一次了，还是很感谢能够给我这一次面试的机会。
七十四：寻找最长无重复子串
用窗口来做。
class Solution { public: int lengthOfLongestSubstring(string s) { int n = s.size(); if(n <= 1) { return n; } int len = 0; int ret = 0; int left = 0 , right = 0; std::unordered_set<char> mp; while(right < n) { while(left < right && mp.count(s[right])) { mp.erase(s[left]); --len; ++left; } mp.insert(s[right]); ++right; ++len; ret = std::max(ret,len); } return ret; } };用map计数代替插入删除更好一点
class Solution { public: int lengthOfLongestSubstring(string s) { int n = s.size(); if(n <= 1) { return n; } int len = 0; int ret = 0; int left = 0 , right = 0; std::unordered_map<char,int> mp; while(right < n) { while(left < right && mp[s[right]]) { --mp[s[left]]; --len; ++left; } ++mp[s[right]]; ++right; ++len; ret = std::max(ret,len); } return ret; } };七十五：两数相加
别忘了进位就好了
/** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode() : val(0), next(nullptr) {} * ListNode(int x) : val(x), next(nullptr) {} * ListNode(int x, ListNode *next) : val(x), next(next) {} * }; */ class Solution { public: ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) { ListNode* dump = new ListNode(); ListNode* curr = dump; int add = 0; while(l1 || l2) { int value1 = 0 , value2 = 0; if(l1) { value1 = l1->val; l1 = l1->next; } if(l2) { value2 = l2->val; l2 = l2->next; } curr->next = new ListNode((value1+value2+add)%10); add = (value1 + value2 + add) / 10; curr = curr->next; } if(add) { curr->next = new ListNode(add); } return dump->next; } };七十六：单词搜索
这个题要注意一下只有一个单词的条件，因为当只会有一个单词的时候，需要进入下一个dfs来返回true，所以不能再4的for中截断，要把对当前索引的合法性检查放到dfs的开头部分。
class Solution { public: bool dfs(std::vector<std::vector<char>>& board , std::string& word , int x , int y , int(&dir)[4][2] , int idx , std::vector<std::vector<int>>&visited) { if(idx == word.size()) { return true; } int n = board.size() , m = board[0].size(); if(x < 0 || x >= n || y < 0 || y >= m || board[x][y] != word[idx] || visited[x][y]) { return false; } bool ret = false; visited[x][y] = 1; for(int i = 0 ; i < 4 ; ++i) { int now_x = x + dir[i][0]; int now_y = y + dir[i][1]; ret |= dfs(board,word,now_x,now_y,dir,idx+1,visited); } visited[x][y] = 0; return ret; } bool exist(vector<vector<char>>& board, string word) { int n = board.size() , m = board[0].size(); std::vector<std::vector<int>> visited(n,std::vector<int>(m)); int dir[4][2] = {{1,0},{-1,0},{0,1},{0,-1}}; for(int i = 0 ; i < n ; ++i) { for(int j = 0 ; j < m ; ++j) { if(dfs(board,word,i,j,dir,0,visited)) { return true; } } } return false; } };七十七：二叉树展开为链表
先递归展开左，再递归展开右，只有先保存下右，之后把左移动到右上，之后展开右，找到右的最后一个节点，之后把临时保存的右放到右的最后一个节点上。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: void flatten(TreeNode* root) { if(!root) { return; } flatten(root->left); flatten(root->right); TreeNode* tmp = root->right; root->right = root->left; root->left = nullptr; TreeNode* curr = root; while(root->right) { root = root->right; } root->right = tmp; } };七十八：合并二叉树
用root1和root2合并，如果有一个为空就返回另一个，之后可以用root1最为+的返回基点，别忘了把左右返回的重新加到root1的左右子树上
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* mergeTrees(TreeNode* root1, TreeNode* root2) { if(!root1 && !root2) { return nullptr; } else if(!root1) { return root2; } else if(!root2) { return root1; } else { root1->val += root2->val; TreeNode* left = mergeTrees(root1->left,root2->left); TreeNode* right = mergeTrees(root1->right , root2->right); root1->left = left; root1->right = right; } return root1; } };七十九：从前序和中序遍历序列构造二叉树
思路，从前序的头找中序的位置来确认前序和中序中数据的数量，注意需要计算一个相对偏移量。否则会错
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: TreeNode* BuildTreeHelp(std::vector<int>& preorder , std::vector<int>& inorder ,int pre_start , int pre_end,int ino_start,int ino_end , std::unordered_map<int,int>&mp) { if(pre_start > pre_end || ino_start > ino_end) { return nullptr; } TreeNode* root = new TreeNode(preorder[pre_start]); int idx = mp[preorder[pre_start]]; int left_node_count = idx - ino_start; root->left = BuildTreeHelp(preorder,inorder,pre_start+1,pre_start+left_node_count , ino_start,ino_start+left_node_count-1,mp); root->right = BuildTreeHelp(preorder,inorder,pre_start+left_node_count+1,pre_end,ino_start+left_node_count+1,ino_end,mp); return root; } TreeNode* buildTree(vector<int>& preorder, vector<int>& inorder) { if(!preorder.size() || !inorder.size()) { return nullptr; } std::unordered_map<int,int> mp; for(int i = 0 ; i < inorder.size() ; ++i) { mp[inorder[i]] = i; } return BuildTreeHelp(preorder,inorder,0,preorder.size()-1,0,inorder.size()-1,mp); } };八十：二叉树的最大深度
和二叉树的直径两个一起对比一下。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: int maxDepth(TreeNode* root) { if(!root) { return 0; } int left_max = maxDepth(root->left); int right_max = maxDepth(root->right); return std::max(left_max,right_max)+1; } };八十一：二叉树的层序遍历
用一个队列存储，怎么做到确认该层有多少个有数据的，就是用n=deq.size()，如果左端点有值，加入左端点，右端点有值加入右端点。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: vector<vector<int>> levelOrder(TreeNode* root) { std::vector<std::vector<int>> ret; if(!root) { return ret; } std::deque<TreeNode*> deq; deq.push_back(root); while(deq.size()) { int n = deq.size(); std::vector<int> tmp; while(n--) { TreeNode* curr = deq.front(); deq.pop_front(); if(curr) { tmp.push_back(curr->val); if(curr->left) { deq.push_back(curr->left); } if(curr->right) { deq.push_back(curr->right); } } } ret.push_back(tmp); } return ret; } };八十二：对称二叉树
需要注意的是对称二叉树的左右节点，插入的时候先插入左节点的左边，在插入右节点的右边，在插入左节点的右边，在插入右节点的左边。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool isSymmetric(TreeNode* root) { if(!root) { return true; } std::deque<TreeNode*> deq; deq.push_back(root->left); deq.push_back(root->right); while(deq.size()) { TreeNode* left = deq.front(); deq.pop_front(); TreeNode* right = deq.front(); deq.pop_front(); if(!left && !right) { continue; } else if(!left || !right || left->val != right->val) { return false; } deq.push_back(left->left); deq.push_back(right->right); deq.push_back(left->right); deq.push_back(right->left); } return true; } };八十三：验证二叉搜索树
思路就是对于当前节点，先看左右是否符合，之后以该点为边界看左右是否符合
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: bool dfs(TreeNode* root , long long min , long long max) { if(!root) { return true; } if(root->val <= min || root->val >= max) { return false; } return dfs(root->left,min,root->val) && dfs(root->right,root->val,max); } bool isValidBST(TreeNode* root) { return dfs(root,LONG_MIN,LONG_MAX); } };八十四：不同的二叉所搜树
思路就是选取一个节点，之后看他前后能生成多少二叉搜索树dp[i] = dp[j-1] * dp[i-j]这个是以j为头结点的。
class Solution { public: int numTrees(int n) { std::vector<int> dp(n+1); dp[0] = 1; for(int i = 1 ; i <= n ; ++i) { for(int j = 1 ; j <= i ; ++j) { dp[i] += dp[j-1]*dp[i-j]; } } return dp[n]; } };八十五：二叉树的中序遍历
下面会补充一个迭代来做的本质上是一样的，但是要先放所有的左节点，之后处理右节点。
/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode() : val(0), left(nullptr), right(nullptr) {} * TreeNode(int x) : val(x), left(nullptr), right(nullptr) {} * TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {} * }; */ class Solution { public: std::vector<int> ret; void dfs(TreeNode* root) { if(!root) { return; } dfs(root->left); ret.push_back(root->val); dfs(root->right); } vector<int> inorderTraversal(TreeNode* root) { dfs(root); return ret; } };八十六：柱状图中的最大矩形
思路：计算i左边小于i以及右边小于i的索引。通过right - left - 1 * height来计算面积。用stk保证单调栈。
class Solution { public: int largestRectangleArea(vector<int>& heights) { int n = heights.size(); std::vector<int> left(n,-1) , right(n,n); std::stack<int> stk; for(int i = 0 ; i < n ; ++i) { while(!stk.empty()&&heights[i] < heights[stk.top()]) { int idx = stk.top(); stk.pop(); right[idx] = i; } if(!stk.empty()) { left[i] = stk.top(); } stk.push(i); } int max = 0; for(int i = 0 ; i < n ; ++i) { max = std::max(max,heights[i]*(right[i]-left[i]-1)); } return max; } };八十七：最大矩形
看图
class Solution { public: int max_size(std::vector<int> height) { int n = height.size(); std::vector<int> left(n,-1) , right(n,n); std::stack<int> stk; for(int i = 0 ; i < n ; ++i) { while(!stk.empty() && height[i] < height[stk.top()]) { int idx = stk.top(); stk.pop(); right[idx] = i; } if(!stk.empty()) { left[i] = stk.top(); } stk.push(i); } int max = 0; for(int i = 0 ; i < n ; ++i) { max = std::max(max,(right[i] - left[i] - 1)*height[i]); } return max; } int maximalRectangle(vector<vector<char>>& matrix) { int n = matrix.size() , m = matrix[0].size(); std::vector<int> height(m); int max = 0; for(int i = 0 ; i < n ; ++i) { for(int j = 0 ; j < m ; ++j) { if(matrix[i][j] == '1') { ++height[j]; } else { height[j] = 0; } } max = std::max(max,max_size(height)); } return max; } };八十八：两数之和
用哈希表来存储
class Solution { public: vector<int> twoSum(vector<int>& nums, int target) { unordered_map<int, int> hashtable; for (int i = 0; i < nums.size(); ++i) { auto it = hashtable.find(target - nums[i]); if (it != hashtable.end()) { return {it->second, i}; } hashtable[nums[i]] = i; } return {}; } };八十九：子集
注意回溯的时候pop之后也需要dfs一下
class Solution { public: void dfs(std::vector<int>& nums , int curr , std::vector<int>&tmp , std::vector<std::vector<int>>&ret) { if(curr == nums.size()) { ret.push_back(tmp); return ; } tmp.push_back(nums[curr]); dfs(nums,curr+1,tmp,ret); tmp.pop_back(); dfs(nums,curr+1,tmp,ret); } vector<vector<int>> subsets(vector<int>& nums) { std::vector<std::vector<int>> ret; std::vector<int> tmp; dfs(nums,0,tmp,ret); return ret; } };九十：最小覆盖子串
思路就是左右窗口，之后用哈希表判断是不是已经相等了。
class Solution { public: string minWindow(string s, string t) { int n = s.size() , m = t.size(); if(!n || !m) { return ""; } std::unordered_map<char,int> u_map_t , u_map_s; for(int i = 0 ; i < m ; ++i) { u_map_t[t[i]]++; } int cnt = u_map_t.size(); int have = 0; int start = 0 , len = INT_MAX; int left = 0 , right = 0; while(right < n) { if(u_map_t.count(s[right])) { ++u_map_s[s[right]]; if(u_map_s[s[right]] == u_map_t[s[right]]) { ++have; } while(have == cnt) { if(len > right - left +1) { start = left; len = right-left+1; } if(u_map_t.count(s[left])) { --u_map_s[s[left]]; if(u_map_s[s[left]] < u_map_t[s[left]]) { --have; } } ++left; } } ++right; } if(len != INT_MAX) { return s.substr(start , len); } else { return ""; } } };九十一：颜色分类
芬兰国旗详细看我的帖子
class Solution { public: void sortColors(vector<int>& nums) { int n = nums.size(); if(n <= 1) { return; } int ptr_0 = 0 , ptr_1 = 0; for(int i = 0 ; i < n ; ++i) { if(nums[i] == 1) { std::swap(nums[i],nums[ptr_1]); ++ptr_1; } else if(nums[i] == 0) { std::swap(nums[i],nums[ptr_0]); if(ptr_1 > ptr_0) { std::swap(nums[i],nums[ptr_1]); } ++ptr_0; ++ptr_1; } } } };九十二：编辑距离
动规，思路如下
class Solution { public: int minDistance(string word1, string word2) { int n = word1.size() , m = word2.size(); std::vector<std::vector<int>> dp(n+1,std::vector<int>(m+1)); dp[0][0] = 0; for(int i = 0 ; i <= n ; ++i) { for(int j = 0 ; j <= m ; ++j) { if(!i && !j) { continue; } else if(!i || !j) { if(!i) { dp[i][j] = dp[i][j-1]+1; } else { dp[i][j] = dp[i-1][j]+1; } } else if(i && j) { if(word1[i-1] == word2[j-1]) { dp[i][j] = dp[i-1][j-1]; } else { dp[i][j] = std::min(dp[i-1][j],std::min(dp[i-1][j-1],dp[i][j-1]))+1; } } } } return dp[n][m]; } };九十三：爬楼梯
动规
class Solution { public: int climbStairs(int n) { if(n <= 1) { return 1; } int pre_one = 1;//1 int pre_two = 1;//0 for(int i = 2 ; i <= n ; ++i) { int now = pre_one + pre_two; pre_two = pre_one; pre_one = now; } return pre_one; } };九十四：最短无序连续子数组
从左往右遍历找最右边，从右往左遍历找最左边，不断变更最大和最小值
class Solution { public: int findUnsortedSubarray(vector<int>& nums) { int n = nums.size(); if(n <= 1) { return 0; } int left = -1 , right = -1; int left_max = INT_MIN , right_min = INT_MAX; for(int i = 0 ; i < n ; ++i) { if(nums[i] < left_max) { right = i; } else { left_max = nums[i]; } if(nums[n-i-1] > right_min) { left = n - i -1; } else { right_min = nums[n - i -1]; } } return right == -1 ? 0 : right - left + 1; } };九十五：最小路径和
如果用回溯的话会超时，用动规
class Solution { public: int minPathSum(vector<vector<int>>& grid) { int n = grid.size() , m = grid[0].size(); for(int i = 1 ; i < n ; ++i) { grid[i][0] = grid[i-1][0]+grid[i][0]; } for(int j = 1 ; j < m ; ++j) { grid[0][j] = grid[0][j-1] + grid[0][j]; } for(int i = 1 ; i < n ; ++i) { for(int j = 1 ; j < m ; ++j) { grid[i][j] = std::min(grid[i-1][j],grid[i][j-1])+grid[i][j]; } } return grid[n-1][m-1]; } };九十六：不同路径
动态规划，但是可以压缩一下容量
class Solution { public: int uniquePaths(int m, int n) { std::vector<std::vector<int>> dp(m,std::vector<int>(n,1)); for(int i = 1; i < m ; ++i) { for(int j = 1 ; j < n ; ++j) { dp[i][j] = dp[i-1][j] + dp[i][j-1]; } } return dp[m-1][n-1]; } };class Solution { public: int uniquePaths(int m, int n) { std::vector<int> dp(n,1); for(int i = 1; i < m ; ++i) { for(int j = 1 ; j < n ; ++j) { dp[j] += dp[j-1]; } } return dp[n-1]; } };九十七：合并区间
注意先排序，之后再用back来做就好了，和会议室对比一下
class Solution { public: vector<vector<int>> merge(vector<vector<int>>& intervals) { std::vector<std::vector<int>> ret; int n = intervals.size(); if(n <= 0) { return ret; } std::sort(intervals.begin(),intervals.end(),[](const std::vector<int>&u , std::vector<int>&v){ return u[0] < v[0]; }); for(int i = 0 ; i < n ; ++i) { if(!ret.size() || ret.back()[1] < intervals[i][0]) { ret.push_back(intervals[i]); } else { ret.back()[1] = std::max(ret.back()[1],intervals[i][1]); } } return ret; } };九十八：跳跃游戏
又返回和无返回的考虑的不一样，这个考虑的是遍历加能退出
class Solution { public: bool canJump(vector<int>& nums) { int n = nums.size(); int max_len = 0; for(int i = 0 ; i < n ; ++i) { if(i <= max_len) { max_len = std::max(max_len , i+nums[i]); if(max_len >= n-1) { return true; } } } return false; } };九十九：最大子数组和
动态规划，dp[i]是以当前i结尾的。
class Solution { public: int maxSubArray(vector<int>& nums) { int curr = nums[0]; int max = nums[0]; for(int i = 1 ; i < nums.size() ; ++i) { if(curr > 0) { curr += nums[i]; } else { curr = nums[i]; } max = std::max(curr,max); } return max; } };
F 发布 - 数据中心网络操作系统)
