devbox
笔触狂放9
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

leetcode 题解 (500-1000题，持续更新，part 2)

作者：笔触狂放9 | 2024-05-24 02:55:55

赞

踩

leetcode 题解 (500-1000题，持续更新，part 2)

part1(1-500), part3(1000-*)

502. IPO

  1. 题意：给定k，w,profits数组和capital数组。k表示最多可完成的任务数。w是初始资本。profits是各个任务的收益。capital是开始此任务需要的初始资金。每次完成一个任务后，将收益加到资本中。问最多可以达到多少资本。
  2. 题解：贪心。用优先队列。每次选取可以开始的任务中收益最大的。
  3. class Solution {
  4. public:
  5.     
  6.     struct pc{
  7.         int profits;
  8.         int capital;
  9.         pc(int u,int v):profits(u),capital(v){}
  10.  
  11.         bool operator < (const Solution::pc &b) const {
  12.             return profits < b.profits;
  13.         }
  14.     };
  15.     struct cmp{
  16.         bool operator()(struct pc &a,struct pc &b)const {
  17.             if(a.capital != b.capital) return a.capital < b.capital;
  18.             return a.profits > b.profits;
  19.         }
  20.     };
  21.     int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {
  22.         vector<pc> v;
  23.         for(int i = 0;i < Profits.size(); ++i){
  24.             v.push_back(pc(Profits[i],Capital[i]));
  25.         }
  26.         sort(v.begin(),v.end(),cmp());
  27.         
  28.         priority_queue<pc> Q;
  29.         int pos = 0;
  30.         while(pos < v.size() && v[pos].capital <= W){
  31.             Q.push(v[pos++]);
  32.         }
  33.         while(!Q.empty() && k--){
  34.             pc u = Q.top(); Q.pop();
  35.             W += u.profits;
  36.             while(pos < v.size() && v[pos].capital <= W){
  37.                 Q.push(v[pos++]);
  38.             }
  39.         }
  40.         
  41.         return W;
  42.     }
  43. };

514. Freedom Trail

  1. 题意：给定一个密码环，环上有一些小写字母。通过转动环，然后按按钮输入正确密码才能将门打开。密码是一个字符串。环上的字符以一个字符串给出，按顺时针排列。可以沿着逆时针和顺时针转动，转动一格计一步。按按钮就将位于位置0的字符输入，并计一步。问最少多少步可以将密码输入。
  2. 题解：动态规划。设dp[i][j]表示key从i到结尾，环上字符现在位于j时，要输完密码至少得步数。那么要转动到key[i]字符所在位置k，则dp[i][j] = min{dp[i + 1][k]} + 1。而k只要枚举当前位置最接近的左右两个和key[i]相等的位置即可(由于是小写字母，这个可以在O(32 * ring.length())的时间预先计算出来。接着，由于dp[i]只用到dp[i + 1]的信息，所以可以滚动数组，空间复杂度降为O(Ring.size() + Key.size())
  3. class Solution {
  4. public:
  5.     int findRotateSteps(string ring, string key) {
  6.         
  7.         int n = ring.size();
  8.         int m = key.size();
  9.         if(m == 0) return 0;
  10.         vector<vector<int> > left(n,vector<int>(26)),right(n,vector<int>(26));
  11.         
  12.         vector<int> leftpos(26,-1),rightpos(26,-1);
  13.         for(int i = 0;i < n; ++i){
  14.             leftpos[ring[i] - 'a'] = i;
  15.             rightpos[ring[n - i - 1] - 'a'] = n - i - 1;
  16.         }
  17.         
  18.         for(int i = 0;i < n; ++i){
  19.             leftpos[ring[i] - 'a'] = i;
  20.             rightpos[ring[n - i - 1] - 'a'] = n - i - 1;
  21.             for(int j = 0;j < 26; ++j){
  22.                 left[i][j] = leftpos[j];
  23.                 right[n - i - 1][j] = rightpos[j];
  24.             }
  25.         }
  26.         
  27.         vector<vector<int> > dp(2,vector<int>(n,0));
  28.         
  29.         for(int i = m - 1;i >= 0; --i){
  30.             int c = key[i] - 'a';
  31.             for(int j = 0;j < n; ++j){
  32.                 int L = left[j][c];
  33.                 int R = right[j][c];
  34.                 dp[i & 1][j] = min((j - L + n) % n + dp[1 - i & 1][L],(R - j + n) % n + dp[1 - i & 1][R]) + 1;
  35.             }
  36.         }
  37.         return dp[0][0];
  38.     }
  39. };

517. Super Washing Machines

  1. 题意：给定N堆硬币(可能为空)，每次可以任意选择m堆，从每一堆中那走一个，放到隔壁堆中取。问至少多少次能使所有堆得硬币一样多。
  2. 题解：dp[i]表示前0到i堆至少多少次能把多余的硬币放到右边去，并且除最后一个，都达到了目标值。dp[i + 1] = dp[i] + L +R,其中L和R分别是要从i+1堆向左边和右边拿走的硬币数量。
  3. class Solution {
  4. public:
  5.     int findMinMoves(vector<int>& machines) {
  6.         int n = machines.size();
  7.         if(n <= 1) return 0;
  8.         int tot = 0,ans = 0;
  9.         for(int i = 0;i < n; ++i) tot += machines[i];
  10.         if(tot % n) return -1;
  11.         int ave = tot / n;
  12.         machines.push_back(ave);
  13.         tot = 0;
  14.         tot = machines[0] - ave;
  15.         
  16.         for(int i = 0;i < n; ++i){
  17.             if(tot >= 0)
  18.                 ans = max(tot,ans);
  19.             else{
  20.                 ans = max(ans,max(0,machines[i + 1] + tot - ave) - tot);
  21.             }
  22.             tot += machines[i + 1] - ave;
  23.             machines[i + 1] += tot;
  24.         }
  25.         return ans;
  26.     }
  27. };

546. Remove Boxes

  1. 题意：给定一个整数序列，每个数字表示颜色。每次可以取走若干个连续的同颜色的一段(长度为k)，获得k*k的分数。问怎么取可以使得当序列取完获得的分数最大。
  2. 题解：动态规划。因为连续的肯定是要一起取走的，所以先合并。设dp[i][j][k]表示从位置i到位置j，前面剩下有k个和i相同颜色的位置，那么要么i和前面的合并掉取走，要么一起留下来，和下一个一样的合并。答案是dp[0][n - 1][0]。
  3. //vector会超内存
  4. class Solution {
  5. public:
  6.     
  7.     void merge(vector<int>& boxes,int n,vector<int>&color,vector<int>&length){
  8.         boxes.push_back(-1);
  9.         int curLength = 0;
  10.         for(int i = 0;i < n; ++i){
  11.             ++curLength;
  12.             if(boxes[i] == boxes[i + 1]) continue;
  13.             length.push_back(curLength);
  14.             color.push_back(boxes[i]);
  15.             curLength = 0;
  16.         }
  17.     }
  18.     
  19.     int removeBoxes(vector<int>& boxes) {
  20.         int n = boxes.size();
  21.         if(n <= 1) return n;
  22.         vector<int> color,length;
  23.         
  24.         merge(boxes,n,color,length);
  25.         
  26.         n = color.size();
  27.         if(n == 1) return length[0] * length[0];
  28.         //vector<vector<vector<int>>> dp(n,vector<vector<int>>(n,vector<int>(boxes.size(),0)));
  29.         
  30.         int dp[100][100][100] = {0};
  31.         
  32.         return dfs(dp,color,length,0,n - 1,0);
  33.     }
  34.     
  35.      int dfs(int dp[100][100][100],const vector<int>& color,vector<int>&length,int i,int j,int k){
  36.         if(i > j) return 0;
  37.         if(i == j) return (k + length[i]) * (k + length[i]);
  38.         int &res = dp[i][j][k];
  39.         if(res) return res;
  40.         
  41.         res = dfs(dp,color,length,i + 1,j,0) + (k + length[i]) * (k + length[i]);
  42.         for(int p = i + 1;p <= j; ++p){
  43.             if(color[p] != color[i]) continue;
  44.             res = max(res, dfs(dp, color,length, i + 1, p - 1, 0) + dfs(dp, color,length, p, j, k + length[i]));
  45.         }
  46.         
  47.         
  48.         return res;
  49.     }
  50.     
  51.     
  52. };
  53.

552. Student Attendance Record II

  1. 题意：给定三种字符(A,P,L)给定一个数字n，问长度n由这三种字符组成且的串的共有多少个。限制是其中一种只能有一个(A)，还有一种最多两个连续（L），剩下一个没有限制(P)。
  2. 题解：dp[i][j][k]表示长度为i，A是否出现过，结尾连续L的个数为k的串的个数。然后进行转移即可。由于dp[i]只用到dp[i - 1]的信息，故可以用滚动数组。
  3. class Solution {
  4. public:
  5.     const long long MOD = 1E9 + 7;
  6.     int checkRecord(int n) {
  7.         long long dp[2][2][3] = {0LL}; 
  8.         
  9.         dp[0][0][0] = 1LL;
  10.  
  11.         for(int i = 1;i <= n; ++i){
  12.             for(int k = 0;k < 3; ++k){
  13.                 if(k > 0){
  14.                     dp[i&1][0][k] = dp[1 - i&1][0][k - 1];
  15.                     dp[i&1][1][k] = dp[1 - i&1][1][k - 1];
  16.                 }
  17.                 else{
  18.                     dp[i&1][0][k] = dp[1 - i&1][0][0] + dp[1 - i&1][0][1] + dp[1 - i&1][0][2];
  19.                     dp[i&1][1][k] = dp[1 - i&1][1][0] + dp[1 - i&1][1][1] + dp[1 - i&1][1][2] +
  20.                                   dp[i&1][0][k];
  21.                 }
  22.                 dp[i&1][0][k] %= MOD; 
  23.                 dp[i&1][1][k] %= MOD;
  24.             }
  25.             
  26.         }
  27.        return (dp[n&1][0][0] + dp[n&1][0][1] + dp[n&1][0][2] + dp[n&1][1][0] + dp[n&1][1][1] + dp[n&1][1][2]) % MOD; 
  28.     }
  29. };

564. Find the Closest Palindrome

  1. 题意：给定一个数字字符串，确定和它离最近的那个回文串，如果有两个一样近，输出小的那个。
  2. 题解：取这个字符串的前半段，如果它本身不是回文串，那么取前半段然后镜像构造一个回文串，这个肯定是距离最小的。如果它本身是回文串，将前半段减1，加1两种情况构造回文串。最近那个肯定是这两个中的一个，这个很显然，接着就是细节的问题了。
  3. class Solution {
  4. public:
  5.     
  6.     bool g(string a,string b){ //a > b? true: false;
  7.         if(a == "inf") return true;
  8.         if(b == "inf") return false;
  9.         if(a.length() > b.length()) return true;
  10.         if(a.length() < b.length()) return false;
  11.         
  12.         for(int i = 0;i < a.length(); ++i){
  13.             if(a[i] > b[i]) return true;
  14.             if(a[i] < b[i]) return false;
  15.         }
  16.         return false;
  17.     }
  18.     
  19.     string dis(string a,string b){
  20.         if(a == b) return "inf";
  21.         if(g(a,b)) swap(a,b);
  22.         a = string(b.length() - a.length(),'0') + a;
  23.         
  24.         char tmp = 0;
  25.         string s = "";
  26.         int i = 0;
  27.         for(int i = a.length() - 1;i >= 0; --i){
  28.             char t = b[i] - a[i] - tmp; 
  29.             if(t < 0) tmp = 1, t += 10;
  30.             else tmp = 0;
  31.             s = char('0' + t) + s;
  32.         }
  33.         int pos = 0 ;
  34.         while(pos < s.length() && s[pos] == '0') ++pos;
  35.         s = s.substr(pos);
  36.         
  37.         return s == string("0") ? "inf":s;
  38.     }
  39.     string minor(string s){
  40.         int mid = (s.length() + 1) / 2;
  41.         for(int i = mid; i < s.length() ; ++i)
  42.             s[i] = s[s.length() - 1 - i];
  43.         return s;
  44.     }
  45.     string nearestPalindromic(string s) {
  46.         int pos = 0;
  47.         while(pos < s.length() - 1 && s[pos] == '0') ++pos;
  48.         s = s.substr(pos);
  49.         int n = s.size();
  50.         
  51.         if(n <= 1){
  52.             cout<<"true"<<endl;
  53.             if(s == "") return "0";
  54.             if(s == "0") return "1";
  55.             cout<<"noew"<<(s[0] - 1)<<endl;
  56.             return string("") + char(s[0] - 1);
  57.         }
  58.         
  59.         string s1 = minor(s);
  60.         string diff1 = dis(s,s1);
  61.         int mid = (s.length() - 1) / 2;
  62.         string s2 = s;
  63.         while(mid >= 0 && s2[mid] == '0'){
  64.             s2[mid] = '9';
  65.             --mid;
  66.         }
  67.         if(mid == 0 && *(s2.begin()) == '1'){
  68.             s2.erase(s2.begin());
  69.             s2[(s2.length() - 1) / 2] = '9';   //this is because it's the closer one
  70.         }
  71.         else
  72.             s2[mid] = s2[mid] - 1;
  73.         s2 = minor(s2);
  74.         string diff2 = dis(s,s2);
  75.         
  76.         mid = (s.length() - 1) / 2;
  77.         
  78.         string s3 = s;
  79.         while(mid >= 0 && s3[mid] == '9'){
  80.             s3[mid] = '0';
  81.             --mid;
  82.         }
  83.         if(mid < 0)
  84.             s3 = "1" + s3;
  85.         else
  86.             s3[mid] = s3[mid] + 1;
  87.         
  88.         s3 = minor(s3);
  89.         
  90.         string diff3 = dis(s,s3);
  91.         
  92.         if(!g(diff2,diff1) && !g(diff2,diff3)) return s2;
  93.         if(!g(diff1,diff2) && !g(diff1,diff3)) return s1;
  94.         return s3;
  95.         
  96.     }
  97. };

587. Erect the Fence

  1. 题意：就是求凸包，都是整点，可能有重复，也可以退化成一直线。从最左边开始，逆时针输出。
  2. 题解：Graham扫描
  3. /**
  4.  * Definition for a point.
  5.  * struct Point {
  6.  *     int x;
  7.  *     int y;
  8.  *     Point() : x(0), y(0) {}
  9.  *     Point(int a, int b) : x(a), y(b) {}
  10.  * };
  11.  */
  12. Point operator-(Point &a, Point &b) {
  13.         int x = a.x - b.x;
  14.         int y = a.y - b.y;
  15.         return Point(x,y);
  16. }
  17. class Solution {
  18. public:
  19.     
  20.     
  21.     struct cmp{
  22.         bool operator()(const Point &a, const Point &b){
  23.             if(a.x == b.x) return a.y < b.y;
  24.             return a.x < b.x;
  25.         }
  26.     };
  27.     bool eq(const Point &a, const Point &b){
  28.         return a.x == b.x && a.y == b.y;
  29.     }
  30.     
  31.     int cross(Point &a,Point &b){
  32.         return a.x * b.y - a.y * b.x;
  33.     }
  34.    
  35.     
  36.     vector<int> convexHull(vector<Point>& points){
  37.         
  38.         
  39.         int n = points.size();
  40.         vector<int> S(n,0);
  41.         int end = 0;
  42.         
  43.         for(int i = 1;i < n; ++i){
  44.             if(end == 0){
  45.                 S[++end] = i;
  46.                 continue;
  47.             }
  48.             int top = S[end];
  49.             int pre = S[end - 1];
  50.             Point v1 = points[i] - points[pre];
  51.             Point v2 = points[top] - points[pre];
  52.             if(cross(v1,v2) > 0){
  53.                 --end;
  54.                 --i;
  55.             }else{
  56.                 S[++end] = i;
  57.             }
  58.         }
  59.         vector<int> down(S.begin(),S.begin() + end + 1);
  60.         
  61.         if(down.size() == points.size()) return down;
  62.         
  63.         S[0] = n - 1; end = 0;
  64.         for(int i = n - 2;i >= 0; --i){
  65.             if(end == 0){
  66.                 S[++end] = i;
  67.                 continue;
  68.             }
  69.             int top = S[end];
  70.             int pre = S[end - 1];
  71.             Point v1 = points[i] - points[pre];
  72.             Point v2 = points[top] - points[pre];
  73.             if(cross(v1,v2) > 0){
  74.                 --end;
  75.                 ++i;
  76.             }else{
  77.                 S[++end] = i;
  78.             }
  79.         }
  80.         
  81.         vector<int>up(S.begin() + 1,S.begin() + end);
  82.         
  83.         down.insert(down.end(),up.begin(),up.end());
  84.         return down;
  85.     }
  86.     /*
  87.     int gcd(int a,int b){
  88.         return b == 0 ? a : gcd(b, a % b);
  89.     }
  90.     
  91.     bool inaLine(vector<Point>& points){
  92.         int pos = 1;
  93.         while(pos < points.size() && points[pos].x == points[0].x && points[pos].y == points[0].y) ++pos;
  94.         if(pos == points.size()) return true;
  95.         
  96.         Point tmp = points[pos] - points[0];
  97.         
  98.         int x = tmp.x,y = tmp.y;
  99.         int d = gcd(x,y);
  100.         x /= d; y /= d;
  101.         for(int i = 1;i < points.size(); ++i){
  102.             int px = points[i].x - points[0].x, py = points[i].y - points[0].y;
  103.             if(px == 0 && py == 0) continue;
  104.             d = gcd(px,py);
  105.             px /= d; py /= d;
  106.             if(x != px || y != py) return false;
  107.         }
  108.         
  109.         
  110.         return true;
  111.     }
  112.     */
  113.     vector<Point> outerTrees(vector<Point>& points) {
  114.         if(points.size() <= 1) return points;
  115.         
  116.         sort(points.begin(),points.end(),cmp()); //left to right ,down to up
  117.         //if(inaLine(points)) return points;
  118.         vector<int> convex = convexHull(points);
  119.         vector<Point> ans;
  120.         for(auto pos:convex) ans.push_back(points[pos]);
  121.         return ans;
  122.     }
  123. };

591. Tag Validator

题意：验证一个标签是否合法。

标签以<tagname>起始</tagname终止>，tagname必须是大写字符，且长度不大于9。

形式如下<tagname>tagcontent </tagname>

tagcontent可能包含以下部分，

  1. 一般text(不包含左尖括号<)
  2. CDATA形式为  <![CDATA[CDATA_CONTENT]]>，CDATA_CONTENT可以为任意字符
  3. tag嵌套

题解：模拟题。直接模拟判断过程。懒得写，见代码注释

  1. class Solution {
  2. public:
  3.     bool isValid(string code) {
  4. 		if(code.empty() || code[0] != '<')
  5. 			return false;
  6. 		int index = 0, N = code.length();
  7.         stack<string> tag;
  8.         
  9. 		while(index < N){
  10.             //遇到左括号，三种情况，起始，终止标签和CDATA
  11. 			if(code[index] == '<'){
  12. 				++index;
  13.                 //CDATA部分
  14. 				if(index < N && code[index]== '!'){
  15.                     //不被包含在tag中，则invalid
  16.                     if(tag.empty())
  17.                         return false;
  18. 					++index;
  19.                     //接下是[CDATA[
  20. 					if(code.substr(index, 7) != "[CDATA[")
  21. 						return false;
  22. 					index += 7;
  23.                     //CDATA_CONTENT
  24.                     while(true){
  25.                         //找到一个可能的CDATA_CONTENT结尾
  26. 						while(index < N && code[index] != ']') ++index;
  27. 						if(index < N - 3){
  28. 							if(code.substr(index,3) == "]]>")  break;
  29. 						}else
  30. 							return false;
  31. 						++index;
  32. 					}
  33. 				}else if(index < N && code[index]== '/'){ //tag结尾
  34. 					if(tag.empty())
  35. 						return false;
  36. 					++index;
  37. 					int i = index, len;
  38.                     //标签，len为标签长度
  39. 					while(i < N && code[i] != '>'){
  40. 						len = i - index + 1;
  41. 						if(len > (int)tag.top().length() || code[i] != tag.top()[len - 1])
  42. 							return false;
  43. 						i++;
  44. 					}
  45. 					len = i - index;
  46. 					if(len != (int)tag.top().length())
  47. 						return false;
  48.                     
  49.                     
  50. 					tag.pop();
  51. 					index = ++i;
  52.                     //外层必须是一个tag，而不是两个tag并排
  53.                     if(tag.empty() && index != N)
  54.                         return false;
  55. 				}else{ //起始标签
  56. 					int i = index, len;
  57.                     //tag
  58. 					while(i < N && code[i] != '>'){
  59. 						len = i - index + 1;
  60.     
  61. 						if(code[i] > 'Z' || code[i] < 'A')
  62. 							return false;
  63. 						i++;
  64. 						if(len > 9)
  65. 							return false;
  66. 					}
  67. 					len = i - index;
  68. 					if(i == N || len < 1 || len > 9)
  69. 						return false;
  70. 					tag.push(code.substr(index,len));
  71. 					index = ++i;
  72. 				}
  73. 			}else //其他内容。直接略
  74. 				++index;
  75. 		}
  76. 		return tag.empty();
  77.     }
  78. };

 

 

600. Non-negative Integers without Consecutive Ones

  1. 题意：给定一个数字n，问比它小的，且二进制没有连续1的非负数有多少个。
  2. 题解：注意到，二进制长度为k的没有连续1的非负数的是Fibonacci数。接着，对于一个n，我们分别计算前缀和它一样的那些数有多少，加起来即可。如果它本身也是，加上它本身。另外一种做法是动态规划。dp[i][j]表示前i位,最后一位为j且不大于num前缀的数目。
  3. class Solution {
  4. public:
  5.     
  6.     int findIntegers(int num) {
  7.         int fib[31];
  8.         fib[0] = 1;
  9.         fib[1] = 2;
  10.         for (int i = 2; i < 32; ++i)
  11.             fib[i] = fib[i - 1] + fib[i - 2];
  12.         int ans = 0, k = 30, pre_bit = 0;
  13.         for(int k = 30;k >= 0; --k) {
  14.             if (num & (1 << k)) {
  15.                 ans += fib[k];
  16.                 if (pre_bit) return ans;
  17.                 pre_bit = 1;
  18.             }else
  19.                 pre_bit = 0;
  20.         }
  21.         return ans + 1;
  22.     }
  23. };
  24. 动态规划解法，压缩空间：
  25. public class Solution {
  26.     public int findIntegers(int num) {
  27.         //one:all bit before cur is less than num and no continues 1 and cur bit is at one;
  28.         //zero:all bit before cur is less than num and no continues 1 and cur bit is at zero;
  29.         int one=0,zero=0,temp;
  30.         boolean isNum=true;
  31.         for(int i=31;i>=0;i--){
  32.             temp=zero;
  33.             zero+=one;
  34.             one=temp;
  35.             if(isNum&&((num>>i)&1)==1){
  36.                 zero+=1;
  37.             }
  38.             if(((num>>i)&1)==1&&((num>>i+1)&1)==1){
  39.                 isNum=false;
  40.             }
  41.         }
  42.         return one+zero+(isNum?1:0);
  43.     }
  44. }

629. K Inverse Pairs Array

  1. 题意：给定n，k。问由1 ~n组成的序列中逆序对为k的共有多少种情况
  2. 题解：动态规划。设dp[i][j]为，前面有1~i + 1的序列,逆序对为j的有多少种。那么dp[i][j]
  3. 可以由i + 1所在位置进行递推。dp[i][j] = dp[i - 1][j] + dp[i - 1][j - 1] + ... dp[i - 1][max(0,j - i)]
  4. 和每次预先计算，故时间复杂度为O(nk)
  5. class Solution {
  6. public:
  7.     const int MOD = 1E9 + 7;
  8.     int getsum(int i,int j, vector<int> &sum)const {
  9.         int pre = max(j - i,0) - 1;
  10.         if(pre < 0) return sum[j];
  11.         else return sum[j] - sum[pre];
  12.     }
  13.     
  14.     int kInversePairs(int n, int k) {
  15.         if(k == 0) return 1;
  16.         vector<int> dp(k + 1,0);
  17.         vector<int> sum(k + 1,1);
  18.         
  19.         dp[0] = 1;
  20.         
  21.         for(int i= 0;i < n; ++i){
  22.             for(int j = 1;j <= k; ++j){
  23.                 dp[j] = (getsum(i,j,sum) % MOD + MOD) % MOD;
  24.             }
  25.             for(int j = 1;j <= k; ++j) sum[j] = (sum[j - 1] + dp[j]) % MOD;
  26.         }
  27.         
  28.         return dp[k];
  29.     }
  30. };

630. Course Schedule III

  1. 题意：给定一些课程，以(需要的时间，最迟结束时间）给出。课程之间不能重叠。问最多可以安排多少个课程。
  2. 题解：贪心。先对课程，按最迟结束时间从小到大排序。然后一个个安排。如果可以安排下，那么就放进去。如果安排不下，那么去掉前面(包括自己)一个耗时最多的。这样子肯定是最优的。因为对于前i个，如果这样做事最优的，那么对于第i+1个，这样做也肯定是最优的，不然得出矛盾。
  3. class Solution {
  4. public:
  5.     struct cmp{
  6.         bool operator ()(vector<int> &a, vector<int>&b){
  7.             return a[1] < b[1];
  8.         }
  9.     };
  10.     struct cmp2{
  11.         bool operator ()(pair<int,int> &a,pair<int,int> &b){
  12.           
  13.                return a.first < b.first;
  14.             
  15.         }
  16.     };
  17.     
  18.     int scheduleCourse(vector<vector<int>>& courses) {
  19.         
  20.         sort(courses.begin(),courses.end(),cmp());
  21.         priority_queue<pair<int,int> ,vector<pair<int,int>>, cmp2>Q;
  22.         int endTime = 0;
  23.         for(int i = 0;i < courses.size(); ++i){
  24.             Q.push(make_pair(courses[i][0],courses[i][1]));
  25.             endTime += courses[i][0];
  26.             if(endTime > courses[i][1]){
  27.                 endTime -= Q.top().first;
  28.                 Q.pop();
  29.             }
  30.         }
  31.         return Q.size();
  32.     }
  33. };

632. Smallest Range

  1. 题意：给定k个list，每个list是一个有序int数组。求一个最小的区间，使得这k个数组中每一个都至少存在一个数在这个区间中。
  2. 题解：先合并成一个pair数组(值和所属的list)。然后双指针遍历即可。
  3. class Solution {
  4. public:
  5.     static bool cmp(pair<int,int> &a,pair<int,int> &b){
  6.         return a.first > b.first;
  7.     }
  8.     vector<int> smallestRange(vector<vector<int>>& nums) {
  9.         vector<pair<int,int>> numpair;
  10.         
  11.         int k = nums.size();
  12.         for(int i = 0;i < k; ++i){
  13.             vector<pair<int,int>> tmp;
  14.             for(auto &num:nums[i]){
  15.                 tmp.push_back(make_pair(num,i));
  16.             }
  17.             numpair.resize(numpair.size() + tmp.size());
  18.             merge(numpair.rbegin() + tmp.size(),numpair.rend(),tmp.rbegin(),tmp.rend(),numpair.rbegin(),cmp);
  19.         }
  20.         
  21.         vector<int> counts(k);
  22.         int visn = 0;
  23.         int a = -1,b = -1,minimumS = INT_MAX;
  24.         int pre = 0;
  25.         for(int i = 0;i < numpair.size() ; ++i){
  26.             if(++counts[numpair[i].second] == 1) ++visn;
  27.             
  28.             if(visn == k){
  29.                 while(counts[numpair[pre].second] > 1){
  30.                     --counts[numpair[pre].second];
  31.                     ++pre;
  32.                 }
  33.                 if(numpair[i].first - numpair[pre].first < minimumS){
  34.                     minimumS = numpair[i].first - numpair[pre].first; 
  35.                     a = numpair[pre].first;
  36.                     b = numpair[i].first;
  37.                 }
  38.             }
  39.         }
  40.      return  vector<int>{a,b};   
  41.     }
  42. };

639. Decode Ways II

  1. 题意：字符A-Z能编码成1到26，给定一串编码，问可以解码成多少种情况。其中编码;*;可以代表1-9中任意字符。
  2. 题解：动态规划。dp[i]表示编码串前i个可以解码的种数。然后按当前字符和前一个字符的类别进行状态转移。
  3.  
  4. class Solution {
  5. public:
  6.     long long M = 1000000007;
  7.     int numDecodings(string s) {
  8.         int n = s.size();
  9.         if(n == 0) return 1;
  10.         vector<long long> dp(n + 1,0);
  11.         dp[0] = 1;
  12.         dp[1] = s[0] == '*'? 9 : s[0] != '0';
  13.         if(dp[1] == 0) return 0;
  14.         
  15.         for(int i = 2; i <= n; ++i){
  16.             if(s[i - 2] == '1'){
  17.                 if(s[i - 1] == '0') dp[i] = dp[i - 2];
  18.                 else if(s[i - 1] == '*') dp[i] = 9 * dp[i - 2] + dp[i - 1] * 9;
  19.                 else dp[i] = dp[i - 2] + dp[i - 1];
  20.                 
  21.             }else if(s[i - 2] == '2'){
  22.                 if(s[i - 1] == '0') dp[i] = dp[i - 2];
  23.                 else if(s[i - 1] == '*') dp[i] = 6 * dp[i - 2] + dp[i - 1] * 9;
  24.                 else if(s[i - 1] <= '6' && s[i - 1] >='1') dp[i] = dp[i - 2] + dp[i - 1];
  25.                 else dp[i] = dp[i - 1];
  26.                 
  27.             }else if(s[i - 2] == '*'){
  28.                 if(s[i - 1] == '0') dp[i] = 2 * dp[i - 2]; 
  29.                 else if(s[i - 1] == '*') dp[i] = 15 * dp[i - 2] + dp[i - 1] * 9;
  30.                 else if(s[i - 1] <= '6' && s[i - 1] >= '1') dp[i] = 2 * dp[i - 2] + dp[i - 1];
  31.                 else dp[i] = dp[i - 2] + dp[i - 1];
  32.                 
  33.             }else if(s[i - 2] > '2'){ //s[i - 2] greater than 2
  34.                 if(s[i - 1] == '0') dp[i] = 0;
  35.                 else if(s[i - 1] == '*')
  36.                     dp[i] = 9 * dp[i - 1];
  37.                 else
  38.                     dp[i] = dp[i - 1];
  39.             }else{ //0
  40.                 if(s[i - 1] == '0') dp[i] = 0;
  41.                 else dp[i] = s[i - 1] == '*'? 9 * dp[i - 1] :  dp[i - 1];
  42.             }
  43.             dp[i] = dp[i] % M;
  44.             
  45.         }
  46.         return dp[n];
  47.         
  48.     }
  49. };

644. Maximum Average Subarray II

  1. 题意：给定一个数组和一个数字k。问长度至少为k的连续段的最大平均值为多少。
  2. 题解：一个简单的做法就是二分答案，然后check。
  3.  (nums[i]+nums[i+1]+...+nums[j])/(j-i+1)>=x
  4. =>nums[i]+nums[i+1]+...+nums[j]>=x*(j-i+1)
  5. =>(nums[i]-x)+(nums[i+1]-x)+...+(nums[j]-x)>=0
  6. 相当于检查有没有连续段长度至少为k且和非负。也就是最大k子段和，用单调队列动态规划解决。
  7. 算法复杂度为O(nlogn)。但这不是最优的，利用计算几何的方法，可以达到O(n)。
  8. 首先，计算前缀和P[i]。然后i到j的平均值为(P[j] - P[i - 1]) / (j - i + 1)。
  9. 我们把它看成两个点(i - 1,P[i - 1]),(j,P[j])，显然平均值就是他们两个点的线段斜率。
  10. 接着。我们从左至右，维护一个下凸包，每次就是找凸包的下切线。具体图解见：
  11. http://www.csie.ntnu.edu.tw/~u91029/MaximumSubarray.html
  12. 该问题的一个增强版本是加上限宽度。也就是在单调队列里面加一个操作即可
  13.  
  14. class Solution {
  15. public:
  16.     /*
  17.     bool check(vector<int>& nums, int k,double sum){
  18.         double cur = 0,pre = 0;
  19.        
  20.         for(int i = 0;i < nums.size(); ++i){
  21.             cur += nums[i] - sum;
  22.             if(i >= k) pre += nums[i - k] - sum;
  23.             if(pre < 0) cur -= pre, pre = 0;
  24.             if(i >= k - 1 && cur >= 0) return true;
  25.         }
  26.         return cur >= 0;
  27.     }
  28.     
  29.     double binarySearchSolution(vector<int>& nums, int k){
  30.         double eps = 1e-6;
  31.         double left = INT_MIN,right = INT_MAX,mid;
  32.         while(right - left > eps){
  33.             mid = (left + right) / 2;
  34.             if(check(nums,k,mid)) left = mid;
  35.             else right = mid;
  36.         }
  37.         return right;
  38.     }
  39.     */
  40.     
  41.     double slope(int x,int y, vector<int> &presum){ // the slope of the x,y
  42.         return double(presum[y + 1] - presum[x]) / (y + 1 - x);
  43.     }
  44.         
  45.     
  46.     double convexHullSolution(vector<int>& nums, int k){
  47.         deque<int> Q;
  48.         vector<int> presum(nums.size() + 1);
  49.         presum[0] = 0;
  50.         double ans = INT_MIN;
  51.         for(int i = 0;i < nums.size(); ++i)  presum[i + 1] = presum[i] + nums[i];
  52.         for(int i = k - 1;i < nums.size(); ++i){
  53.             while(Q.size() > 1 && slope(*(Q.end() - 2),Q.back() - 1,presum)  >= slope(*(Q.end() - 2),i - k,presum)) Q.pop_back(); //update the convex
  54.             Q.push_back(i - k + 1);
  55.             while(Q.size() > 1 && slope(Q.front(),Q.at(1) - 1,presum)  <= slope(Q.front(),i,presum)) Q.pop_front();
  56.             ans = max(ans,slope(Q.front(),i,presum));
  57.             
  58.         }
  59.         return ans;
  60.     }
  61.      
  62.     double findMaxAverage(vector<int>& nums, int k) {
  63.         //return binarySearchSolution(nums,k);
  64.         return convexHullSolution(nums,k);
  65.     }
  66. };

664. Strange Printer

题意：有一个stange printer他能做以下的事

  1. 每次只能从一个位置到另一个位置打印同一个字符
  2. 在每一轮的打印中，新打印的会覆盖旧打印的字符

给定一个字符串，问至少需要多少次打印才能得到。比如aba需要两次。先打印aaa，再打印b

题解：动态规划，设dp[i][j]表示i到j子串需要多少次打印。则有以下的情况

首先注意到，第一个字符一定可以在第一轮打印。如果它单独打印显然可以，否则，它和到另外的一个位置k的子串打印，那么显然也可以放在第一次，因为如果不是第一次，那么会覆盖掉前面的打印，把前面的打印的起始位置移到k以后并不会产生差别。所以我们可以分两种情况

  1. i位置单独打印，则次数为dp[i + 1][j] + 1
  2. i和k一起打印（s[i] == s[k]），那么k这个位置就不用管了(相当于和i合一起了)，并且将串分成两部分i  ~ k , k + 1~ j。i~k的打印次数为dp[i][k - 1]，k+1~j的打印次数dp[k + 1][j]。总次数为dp[i][k - 1] + dp[k + 1][j]
  1. class Solution {
  2.     int dp[101][101];
  3.     
  4.     int dfs(int i, int j, string &str){
  5.         if(i > j) return 0;
  6.         if(i == j) return 1;
  7.         if(dp[i][j]) return dp[i][j];
  8.         
  9.         dp[i][j] = dfs(i + 1, j, str) + 1;
  10.         for(int k = i + 1; k < str.length(); ++k){
  11.             if(str[k] == str[i]) dp[i][j] = min(dp[i][j], dfs(i, k - 1, str) + dfs(k + 1, j, str));
  12.         }
  13.             
  14.         return dp[i][j];
  15.     }
  16.     
  17. public:
  18.     int strangePrinter(string s) {
  19.         string str = "";
  20.         for(int i = 0;i < s.length(); ++i){
  21.             str += s[i];
  22.             while(i + 1 < s.length() && s[i + 1] == s[i]) ++i;
  23.         }
  24.         return dfs(0, str.length() - 1, str);
  25.     }
  26. };

668. Kth Smallest Number in Multiplication Table

题意：给定一个m *n的乘法表，求里面第k大的数

题解：二分答案mid，然后判断小于等于mid的有多少对。这个通过枚举第一个乘数就知道了。假设乘数为i，则其中小于等于mid的数为min(n, mid / i)个。（用双指针可能更快点，因为除法比较耗时，而++运算--运算是很快的）

  1. class Solution {
  2. public:
  3.     int findKthNumber(int m, int n, int k) {
  4.         
  5.         int left = 1, right = n * m;
  6.         
  7.         while(left <= right){
  8.             int mid = (left + right) >> 1;
  9.             
  10.             int num = (mid / n) * n;
  11.             for(int i = mid / n + 1; i <= min(m, mid); ++i){
  12.                 num += mid / i;
  13.             }
  14.             
  15.             if(num < k){
  16.                 left = mid + 1;
  17.             }else{
  18.                 right = mid - 1;
  19.             }
  20.         }
  21.         return right + 1;
  22.     }
  23. };

675. Cut Off Trees for Golf Event

题意：给以个网格，表示一个森林，其中0表示障碍物不能通过，其他都能通过，1表示平地，高于1表示有一棵树。从(0,0)位置开始，每次砍最低的树，最少需要多少步

题解：按树高排序，就是从当前位置走到下个树的高度位置的最少步数，bfs可解决。一开始我看成树是不能通过的，只有砍掉才能通过，这样也可以做，稍微修改即可（将排序部分改成优先队列）。

  1. class Solution {
  2.     typedef pair<int, pair<int,int>> height_pos, step_pos;
  3.     //放在外面会快很多
  4.     bool vis[50][50];
  5.     queue<step_pos> Q;
  6.     
  7.     int get_step(const pair<int,int> &s, const pair<int,int> &e, const vector<vector<int>>& forest){
  8.         while(not Q.empty()) Q.pop();
  9.         Q.push(make_pair(0, s));
  10.         //vector<vector<bool>> vis(forest.size(), vector<bool>(forest[0].size(), false));
  11.         memset(vis, 0, sizeof(vis));
  12.         
  13.         int dir_x[] = {1, 0, -1, 0};
  14.         int dir_y[] = {0, 1, 0, -1};
  15.         vis[s.first][s.second] = true;
  16.         while(not Q.empty()){
  17.             step_pos cur = Q.front(); Q.pop();
  18.             int x = cur.second.first, y = cur.second.second;
  19.             if(cur.second == e) return cur.first;
  20.             
  21.             for(int d = 0; d < 4; ++d){
  22.                 int next_x = x + dir_x[d];
  23.                 int next_y = y + dir_y[d];
  24.                 if(next_x < 0 or next_y < 0 or next_x >= forest.size() or next_y >=
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/笔触狂放9/article/detail/615508
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号