leetcode刷题7月

leetcode378 有序矩阵中第k小的元素 给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第 k 小的元素。 请注意，它是排序后的第 k 小元素，而不是第 k 个不同的元素。

matrix = [ [ 1, 5, 9], [10, 11, 13], [12, 13, 15] ], k = 8, 思路：二分查找 主函数： 统计小于当前mid的数量，>k，说明我们找的数<=mid,令right=mid,反之亦然， check函数： 1.初始位置在 matrix[n - 1][0]matrix[n−1][0]（即左下角）； 2.设当前位置为 matrix[i][j]。若 matrix[i][j]<=mid，则将当前所在列的不大于 mid的数的数量（即 i + 1）累加到答案中，并向右移动，否则向上移动； 3.不断移动直到走出格子为止。

//时间复杂度：O(n\log(r-l))，二分查找进行次数为 O(log(r−l))，每次操作时间复杂度为 O(n)。 class Solution { public: int kthSmallest(vector<vector<int>>& matrix, int k) { int n=matrix.size(); int left=matrix[0][0],right=matrix[n-1][n-1]; while(left<right){ int mid=left+(right-left)/2; if(check(matrix,k,n,mid)){ right=mid; } else{ left=mid+1; } } return left; } int check(vector<vector<int>>& matrix, int k,int n,int mid){ int i=n-1,j=0; int num=0; while(i>=0&&j<n){ if(matrix[i][j]<=mid){ num+=i+1; //表明这一列的元素都比当前的mid元素小，累加 j++; } else{ i--; } } return num>=k; } };

leetcode23 最长有效括号 给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。

示例 1:

输入: “(()” 输出: 2 解释: 最长有效括号子串为 “()” 示例 2:

输入: “)()())” 输出: 4 解释: 最长有效括号子串为 “()()”

class Solution { public: int longestValidParentheses(string s) { stack<int> st; int count=0; st.push(-1); for(int i=0;i<s.size();i++){ if(s[i]=='('){ st.push(i); } else{ st.pop(); if(st.empty()){ st.push(i); //记录最后一个不被匹配的右括号 } else{ count=max(count,i-st.top()); } } } return count; } };

leetcode 11 盛水最多的容器（medium) 给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

思想：贪心+双指针 对O(n)的算法写一下自己的理解，一开始两个指针一个指向开头一个指向结尾，此时容器的底是最大的，接下来随着指针向内移动，会造成容器的底变小，在这种情况下想要让容器盛水变多，就只有在容器的高上下功夫。 那我们该如何决策哪个指针移动呢？我们能够发现不管是左指针向右移动一位，还是右指针向左移动一位，容器的底都是一样的，都比原来减少了 1。这种情况下我们想要让指针移动后的容器面积增大，就要使移动后的容器的高尽量大，所以我们选择指针所指的高较小的那个指针进行移动，这样我们就保留了容器较高的那条边，放弃了较小的那条边，以获得有更高的边的机会。

class Solution { public: int maxArea(vector<int>& heights) { int i=0; int j=heights.size()-1; int ans=0; while(i<j){ ans=max(ans,(j-i)*min(heights[i],heights[j])); if(heights[i]>heights[j]){ j--; } else{ i++; } } return ans; } };

leetcode4. 寻找两个正序数组的中位数(hard) 给定两个大小为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。

请你找出这两个正序数组的中位数，并且要求算法的时间复杂度为 O(log(m + n))。

你可以假设 nums1 和 nums2 不会同时为空。

class Solution { public: int find(vector<int>& nums1, int i, vector<int>& nums2, int j, int k){//从nums1中的i和nums2的j开始 找第k大的数 if(nums1.size() - i > nums2.size() - j) return find(nums2, j, nums1, i, k);//保证第二个大于等于第一个 if(nums1.size() == i) return nums2[j+k-1];//第一个数组为空时 if(k==1) return min(nums1[i],nums2[j]);//递归边界 即为两个最小值 int si = min(int(nums1.size()),i + k/2), sj = j + k - k/2;//每个数组从起点开始的第k/2大数的后一个数的下标 if(nums1[si-1] > nums2[sj-1]){//若前者的该数大于后者的该数 则后者的前部分就没用了 return find(nums1, i, nums2, sj, k - (sj-j));//sj-j即为删去的数的个数 } else return find(nums1, si, nums2, j, k - (si - i));//同理 此时 前者的前部分就没用了 } double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int tot = nums1.size() + nums2.size(); if(tot % 2) {//总数为奇数时的中位数 return find(nums1, 0, nums2, 0, tot/2+1); } else { int l = find(nums1, 0, nums2, 0, tot/2), r = find(nums1, 0, nums2, 0, tot/2 + 1); return (l + r)/2.0; } } };

leetcode42 接雨水（hard) 给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。

//单调递减栈，O(N） O(N) class Solution { public: int trap(vector<int>& height) { stack<int> s; int area=0; for(int i=0;i<height.size();i++){ while(!s.empty()&&height[i]>height[s.top()]){ int curr=s.top(); s.pop(); if(s.empty()){ break; } int j=s.top(); int h=min(height[i],height[j])-height[curr]; area+=(i-j-1)*h; } s.push(i); } return area; } }; 不同的二叉搜索树 II 给定一个整数 n，生成所有由 1 … n 为节点所组成的 二叉搜索树 。 示例：

输入：3 输出： [ [1,null,3,2], [3,2,null,1], [3,1,null,null,2], [2,1,3], [1,null,2,null,3] ] 解释： 以上的输出对应以下 5 种不同结构的二叉搜索树：

1 3 3 2 1 \ / / / \ 3 2 1 1 3 2 / / \ 2 1 2 3

/** * 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<TreeNode*> generateTrees(int n) { return helper(1,n); } vector<TreeNode*> helper(int left,int right){ vector<TreeNode*> ans; if(left>right){ return {}; } if(left==right){ return {new TreeNode(left)}; } for(int i=left;i<=right;i++){ auto left_child=helper(left,i-1); auto right_child=helper(i+1,right); if(right_child.empty()){ for(auto l:left_child){ auto root=new TreeNode(i); root->left=l; ans.push_back(root); } } else if(left_child.empty()){ for(auto r:right_child){ auto root=new TreeNode(i); root->right=r; ans.push_back(root); } } else{ for(auto l:left_child){ for(auto r:right_child){ auto root=new TreeNode(i); root->left=l; root->right=r; ans.push_back(root); } } } } return ans; } }; 分割数组的最大值(hard) 给定一个非负整数数组和一个整数 m，你需要将这个数组分成 m 个非空的连续子数组。设计一个算法使得这 m 个子数组各自和的最大值最小。 注意: 数组长度 n 满足以下条件: 1 ≤ n ≤ 1000 1 ≤ m ≤ min(50, n) 示例: 输入: nums = [7,2,5,10,8] m = 2

输出: 18

思路：对于每个解，他们的各个子数组和的最大值肯定是固定的，而且肯定在left和right之间；其中left=nums数组中的最大值，right=nums的所有元素之和，这样使用二分查找确定各个子数组的最大和，然后判断每个确定的最大值是否满足。

当满足的时候，我们考虑把最大值变小，判断是否还满足 如果还满足，那么我们就继续变小， 如果不满足，那么我们需要把最大值变大，然后再找。

class Solution { public: int splitArray(vector<int>& nums, int m) { long low=0,high=0; for(auto num:nums){ high+=num; //sum(nums) low=num>low?num:low; //max(nums) } while(low<high){ int count=1; int mid=low+(high-low)/2; long temp=0; for(auto num:nums){ temp+=num; if(temp>mid){ temp=num; count++; } } if(count>m){ low=mid+1; } else{ high=mid; } } return low; } };

约瑟夫环：

//模拟循环链表 class Solution { public: struct listnode{ int val; listnode* next; listnode(int x):val(x),next(NULL){} }; int LastRemaining_Solution(int n, int m) { if(n==0||m==0){return -1;} listnode* root=new listnode(0); listnode* head=root; for(int i=1;i<n;i++){ head->next=new listnode(i); head=head->next; } head->next=root; int count=0; listnode* curr=root; listnode* pre; while(curr->next!=curr){ count++; if(count==m){ pre->next=curr->next; curr=curr->next; count=0; } else{ pre=curr; curr=curr->next; } } return curr->val; } };

leetcode93.复原IP地址（medium) 给定一个只包含数字的字符串，复原它并返回所有可能的 IP 地址格式。 有效的 IP 地址正好由四个整数（每个整数位于 0 到 255 之间组成），整数之间用 ‘.’ 分隔。 示例:

输入: “25525511135” 输出: [“255.255.11.135”, “255.255.111.35”]

class Solution { private: vector<string> res; string path; public: vector<string> restoreIpAddresses(string s) { if(s.size() < 4 || s.size() > 12) return {}; dfs(0, s, 0, path); return res; } void dfs(int cur_count, string s, int start, string path){ if(cur_count == 4){ //当达到4个分组，且s已经遍历完时，将结果输出到res中 if(start == s.size()) res.push_back(path); return; } for(int i = 1; i < 4 && start + i <= s.size(); ++i){ //遍历+回溯，每次尝试1、2、3个元素为当前节 string tmp = s.substr(start, i); //必须加上start + i <= s.size()，因为遍历到s末尾后会越界 if(check(tmp)){ if(cur_count < 3) //注意'.'的输出次数 tmp += '.'; dfs(cur_count + 1, s, start + i, path + tmp); //遍历、回溯 if(s[start] == '0') //此处排除0x和0xx的情况 return; } else{ return; //当前所选节是无效的，就得返回 } } } bool check(string str){ //判断是否符合0-255 int tmp = stoi(str); if(tmp >= 0 && tmp <= 255) return true; return false; } };