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; } };
