目录
410.分割数组的最大值
4.寻找两个正序数组的中位数
51.N皇后
410.分割数组的最大值
这个题可以运用二分答案的算法来解题。定义一个左指针和一个右指针，令左指针等于数组的最大值，令右指针等于数组所有数之和。即最终的结果一定在他们之间。
long long l = 0, r = 0; for (int i = 0; i < nums.size(); i++) { r += nums[i]; if (l < nums[i]) { l = nums[i]; } }定义一个返回值ans。然后进行二分。
long long ans=0; while(l<=r) { long long mid=(l+r)/2; if(cheak(mid,nums,k)) { ans=mid; r=mid-1; } else { l=mid+1; } }这个题的cheak函数里面需要定义一个值ans初始为1和求和变量sum；然后遍历数组，进行求和当sum大于mid的时候那么ans就进行加一给sum重新赋值。最后进行判断ans与k的大小。
bool cheak(long long mid,vector<int>& nums,int k) { long long sum=0; int ans=1; for(int i=0;i<nums.size();i++) { if(sum+nums[i]>mid) { ans++; sum=nums[i]; } else sum+=nums[i]; } return ans<=k; }完整代码
class Solution { public: int splitArray(vector<int>& nums, int k) { long long l = 0, r = 0; for (int i = 0; i < nums.size(); i++) { r += nums[i]; if (l < nums[i]) { l = nums[i]; } } long long ans=0; while(l<=r) { long long mid=(l+r)/2; if(cheak(mid,nums,k)) { ans=mid; r=mid-1; } else { l=mid+1; } } return ans; } bool cheak(long long mid,vector<int>& nums,int k) { long long sum=0; int ans=1; for(int i=0;i<nums.size();i++) { if(sum+nums[i]>mid) { ans++; sum=nums[i]; } else sum+=nums[i]; } return ans<=k; } };4.寻找两个正序数组的中位数
这个题首先考虑数组是否为空。
int n1 = nums1.size(); int n2 = nums2.size(); int n = n1 + n2; if (n1 == 0 || n2 == 0) { if (n1 == 0 && n2 == 0) { return 0; } else if (n1 == 0) { if (n2 % 2 == 1) return nums2[n2 / 2]; else return (nums2[n2 / 2 - 1] + nums2[n2 / 2]) / 2.0; } else { if (n1 % 2 == 1) return nums1[n1 / 2]; else return (nums1[n1 / 2 - 1] + nums1[n1 / 2]) / 2.0; } }判断之后进行查找那个中位数。
首先需要判断两个数组加起来的数是奇数还是偶数。如果是奇数只需要找一个n/2+1就可以了。
偶数需要找n/2+1和n/2。
else { if (n % 2 == 1) { return twocz(nums1, nums2, n / 2 + 1); } else { return (twocz(nums1, nums2, n / 2) + twocz(nums1, nums2, n / 2 + 1)) / 2.0; } }进行查找，首先我们要定义一个a和b指向两个数组的初始位置。设需要找的中位数位置为k。
令num1[min(a+k/2-1,num1.size()-1)]和num2[min(b+k/2-1,num2.size()-1)]比较大小。小的那一个可以直接排除掉。所以k进去排除的部分。一直进行循环。
直到a==num1.size()或b==num2.size()或k==1;返回相应的值。
int twocz(vector<int> nums1, vector<int> nums2, int k) { int n = nums1.size(); int m = nums2.size(); int a = 0; int b = 0; while (1) { if (a == n) { return nums2[b + k - 1]; } if (b == m) { return nums1[a + k - 1]; } if (k == 1) { return min(nums1[a], nums2[b]); } int c = min(a + k / 2 - 1, n - 1); int d = min(b + k / 2 - 1, m - 1); int j1 = nums1[c]; int j2 = nums2[d]; if (j1 <= j2) { k -= c - a + 1; a = c + 1; } else { k -= d - b + 1; b = d + 1; } } }完整代码
int twocz(vector<int> nums1, vector<int> nums2, int k) { int n = nums1.size(); int m = nums2.size(); int a = 0; int b = 0; while (1) { if (a == n) { return nums2[b + k - 1]; } if (b == m) { return nums1[a + k - 1]; } if (k == 1) { return min(nums1[a], nums2[b]); } int c = min(a + k / 2 - 1, n - 1); int d = min(b + k / 2 - 1, m - 1); int j1 = nums1[c]; int j2 = nums2[d]; if (j1 <= j2) { k -= c - a + 1; a = c + 1; } else { k -= d - b + 1; b = d + 1; } } } class Solution { public: double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) { int n1 = nums1.size(); int n2 = nums2.size(); int n = n1 + n2; if (n1 == 0 || n2 == 0) { if (n1 == 0 && n2 == 0) { return 0; } else if (n1 == 0) { if (n2 % 2 == 1) return nums2[n2 / 2]; else return (nums2[n2 / 2 - 1] + nums2[n2 / 2]) / 2.0; } else { if (n1 % 2 == 1) return nums1[n1 / 2]; else return (nums1[n1 / 2 - 1] + nums1[n1 / 2]) / 2.0; } } else { if (n % 2 == 1) { return twocz(nums1, nums2, n / 2 + 1); } else { return (twocz(nums1, nums2, n / 2) + twocz(nums1, nums2, n / 2 + 1)) / 2.0; } } } };51.N皇后
这个题运用了剪枝回溯法 定义三个bool变量分别判断列和两个对角线。之后与全排列相似。
完整代码
const int N=10; bool f1[10],f2[N+N],f3[N+N],f4[N+N]; void dfs(vector<vector<int>> &z,int n,int x,vector<int> &arr) { if(x==n) { z.push_back(arr); } for(int i=1;i<=n;i++) { if(x+1-i>=0) { if(!f1[i]&&!f2[x+1-i]&&!f4[x+1+i]) { f1[i]=true; f2[x+1-i]=true; f4[x+1+i]=true; arr[x]=i; dfs(z,n,x+1,arr); f1[i]=false; f2[x+1-i]=false; f4[x+1+i]=false; } } else { if(!f1[i]&&!f3[i-x-1]&&!f4[x+1+i]) { f1[i]=true; f3[i-x-1]=true; f4[x+1+i]=true; arr[x]=i; dfs(z,n,x+1,arr); f1[i]=false; f3[i-x-1]=false; f4[x+1+i]=false; } } } } class Solution { public: vector<vector<string>> solveNQueens(int n) { vector<vector<int>> z; vector<int> arr; for(int i=0;i<n;i++) { arr.push_back(0); } dfs(z,n,0,arr); vector<vector<string>> s; for(int i=0;i<z.size();i++) { vector<string>s1; for(int j=0;j<n;j++) { string s2; int a=z[i][j]; for(int z=0;z<n;z++) { if(z==a-1) s2.push_back('Q'); else s2.push_back('.'); } s1.push_back(s2); } s.push_back(s1); } return s; } };
