LeetCode Contest 166
- 2019 年 12 月 11 日
- 筆記
第一次知道LeetCode 也有比赛。
很久没有打过这种线上的比赛，很激动。
直接写题解吧
很弱智
class Solution { public: int subtractProductAndSum(int n) { int num1=0; int num2=1; while(n) { int x = n%10; num1+=x; num2*=x; n/=10; } return num2-num1; } };
第二题 也很简单的，我先排个序。
但是在用c++的快排的时候，被坑了，我一直的习惯是写自定义比较函数，没有写运算符重载，不知道为什么一直RE，浪费了挺多时间
struct Node { int value; int index; Node(){} Node(int value,int index) { this->value = value; this->index = index; } bool operator <(const Node &x)const { return value<x.value; } }; class Solution { public: int vis[1005]; Node a[1005]; vector<vector<int>> groupThePeople(vector<int>& groupSizes) { int len = groupSizes.size(); for(int i=0;i<len;i++) { a[i] = Node(groupSizes[i],i); } sort(a,a+len); vector<vector<int>> ans; vector<int> res; res.push_back(a[0].index); int num=0; for(int i=1;i<len;i++) { if(a[i].value==a[i-1].value) { if(res.size()==a[i].value) { ans.push_back(res); res.clear(); res.push_back(a[i].index); continue; } res.push_back(a[i].index); } else { ans.push_back(res); res.clear(); res.push_back(a[i].index); } } if(res.size()!=0) { ans.push_back(res); } return ans; } };
二分，一次过，没有怎么浪费时间
class Solution { public: int smallestDivisor(vector<int>& nums, int threshold) { int num=0; for(int i=0;i<nums.size();i++) { num=max(num,nums[i]); } int start = 1; int end = num; while(start<=end) { int mid = (start+end)/2; int sum=0; for(int i=0;i<nums.size();i++) { int x; if(nums[i]%mid==0) x = nums[i]/mid; else x = nums[i]/mid +1; sum+=x; } if(sum > threshold) { start = mid + 1; continue; } if(sum <= threshold) { end = mid - 1; continue; } } return start; } };
看着挺唬人的，我一开始纠结是不是DP，但是一看数据，最多只有3啊，暴力搜索，用位运算保存矩阵的状态，然后注意剪枝就过了。但是因为在第二题上耽误了一些时间，导致比赛结束后，才过了第四题，哎。。
class Solution { public: int vis[10005]; int ans[10005]; int map[10][10]; int n,m; int result; int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; int minFlips(vector<vector<int>>& mat) { int len = mat.size(); n=len; m=mat[0].size(); for(int i=0;i<mat.size();i++) { for(int j=mat[i].size()-1;j>=0;j--) { map[i][j] = mat[i][j]; } } result = 9999999; int x = compute(); if(x==0) return 0; vis[x]=1; ans[x]=0; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { fun(i,j,1); map[i][j] ^= 1; for(int k=0;k<4;k++) { int xx = i+dir[k][0]; int yy = j+dir[k][1]; if(xx>=0&&xx<n&&yy>=0&&yy<m) map[xx][yy] ^=1; } } } if(result == 9999999 ) result =-1; return result; } void fun(int x,int y,int res) { map[x][y] ^= 1; for(int i=0;i<4;i++) { int xx = x+dir[i][0]; int yy = y+dir[i][1]; if(xx>=0&&xx<n&&yy>=0&&yy<m) map[xx][yy] ^=1; } int v = compute(); if(vis[v]==1) { if(res>=ans[v]) { return; } else { ans[v]=res; } } if(v==0) { result=min(result,res); return; } vis[v]=1; ans[v]=res; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { fun(i,j,res+1); map[i][j] ^= 1; for(int k=0;k<4;k++) { int xx = i+dir[k][0]; int yy = j+dir[k][1]; if(xx>=0&&xx<n&&yy>=0&&yy<m) map[xx][yy] ^=1; } } } } int compute() { int x=0; for(int i=0;i<n;i++) { for(int j=0;j<m;j++) { x <<= 1; x |= map[i][j]; } } return x; } };
