网站建设分类方案中山网络公关

网站建设分类方案,中山网络公关,网站界面设计原则,电脑版传奇昨天进行了面试#xff0c;感觉答的一般#xff0c;今天也没有消息#xff0c;估计有点寄了。现在把之前没来的寄放上的放上#xff0c;今天的任务就是做做题#xff0c;之后晚上回去吃个饭#xff0c;早点睡觉#xff0c;明天还是就是正式的找实习过程了#xff0c;毕…昨天进行了面试感觉答的一般今天也没有消息估计有点寄了。现在把之前没来的寄放上的放上今天的任务就是做做题之后晚上回去吃个饭早点睡觉明天还是就是正式的找实习过程了毕竟已经面试过一次了还是很感谢能够给我这一次面试的机会。七十四寻找最长无重复子串用窗口来做。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_setchar 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_mapchar,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((value1value2add)%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::vectorstd::vectorchar board , std::string word , int x , int y , int(dir)[4][2] , int idx , std::vectorstd::vectorintvisited) { 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,idx1,visited); } visited[x][y] 0; return ret; } bool exist(vectorvectorchar board, string word) { int n board.size() , m board[0].size(); std::vectorstd::vectorint visited(n,std::vectorint(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::vectorint preorder , std::vectorint inorder ,int pre_start , int pre_end,int ino_start,int ino_end , std::unordered_mapint,intmp) { 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_start1,pre_startleft_node_count , ino_start,ino_startleft_node_count-1,mp); root-right BuildTreeHelp(preorder,inorder,pre_startleft_node_count1,pre_end,ino_startleft_node_count1,ino_end,mp); return root; } TreeNode* buildTree(vectorint preorder, vectorint inorder) { if(!preorder.size() || !inorder.size()) { return nullptr; } std::unordered_mapint,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; } };八十一二叉树的层序遍历用一个队列存储怎么做到确认该层有多少个有数据的就是用ndeq.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: vectorvectorint levelOrder(TreeNode* root) { std::vectorstd::vectorint ret; if(!root) { return ret; } std::dequeTreeNode* deq; deq.push_back(root); while(deq.size()) { int n deq.size(); std::vectorint 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::dequeTreeNode* 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::vectorint dp(n1); 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::vectorint ret; void dfs(TreeNode* root) { if(!root) { return; } dfs(root-left); ret.push_back(root-val); dfs(root-right); } vectorint inorderTraversal(TreeNode* root) { dfs(root); return ret; } };八十六柱状图中的最大矩形思路计算i左边小于i以及右边小于i的索引。通过right - left - 1 * height来计算面积。用stk保证单调栈。class Solution { public: int largestRectangleArea(vectorint heights) { int n heights.size(); std::vectorint left(n,-1) , right(n,n); std::stackint 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::vectorint height) { int n height.size(); std::vectorint left(n,-1) , right(n,n); std::stackint 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(vectorvectorchar matrix) { int n matrix.size() , m matrix[0].size(); std::vectorint 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: vectorint twoSum(vectorint nums, int target) { unordered_mapint, 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::vectorint nums , int curr , std::vectorinttmp , std::vectorstd::vectorintret) { if(curr nums.size()) { ret.push_back(tmp); return ; } tmp.push_back(nums[curr]); dfs(nums,curr1,tmp,ret); tmp.pop_back(); dfs(nums,curr1,tmp,ret); } vectorvectorint subsets(vectorint nums) { std::vectorstd::vectorint ret; std::vectorint 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_mapchar,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-left1; } 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(vectorint 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::vectorstd::vectorint dp(n1,std::vectorint(m1)); 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(vectorint 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(vectorvectorint 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::vectorstd::vectorint dp(m,std::vectorint(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::vectorint 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: vectorvectorint merge(vectorvectorint intervals) { std::vectorstd::vectorint ret; int n intervals.size(); if(n 0) { return ret; } std::sort(intervals.begin(),intervals.end(),[](const std::vectorintu , std::vectorintv){ 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(vectorint 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 , inums[i]); if(max_len n-1) { return true; } } } return false; } };九十九最大子数组和动态规划dp[i]是以当前i结尾的。class Solution { public: int maxSubArray(vectorint 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; } };