leetcode解题思路分析（七十二）633 - 639 题

待我称王封你为后i 2022-11-18 01:38 263阅读 0赞
  1. 平方数之和
    给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。

费马平方和定理：一个非负整数 cc 能够表示为两个整数的平方和，当且仅当 cc 的所有形如 4k+34k+3 的质因子的幂次均为偶数。

  1. class Solution { 
  2. public:
  3.     bool judgeSquareSum(int c) 
  4.     { 
  5.         for (int i = 2; i * i <= c; i++) { 
  6.             int count = 0;
  7.             if (c % i == 0) 
  8.             { 
  9.                 while (c % i == 0) 
  10.                 { 
  11.                     count++;
  12.                     c /= i;
  13.                 }
  14.                 if (i % 4 == 3 && count % 2 != 0)
  15.                     return false;
  16.             }
  17.         }
  18.         return c % 4 != 3;
  19.     }
  20. };
  1. 函数的独占时间
    给出一个非抢占单线程CPU的 n 个函数运行日志，找到函数的独占时间。

栈的简单运用

  1. class Solution { 
  2. public:
  3.     vector<int> exclusiveTime(int n, vector<string>& logs) { 
  4.         vector<int> result(n, 0);
  5.         stack<pair<int, int>> stk;
  6.         for (string &log : logs) { 
  7.             size_t pos1 = log.find(':');
  8.             size_t pos2 = log.rfind(':');
  9.             int currId = stoi(log.substr(0, pos1));
  10.             string currAction = log.substr(pos1+1, pos2-pos1-1);
  11.             int currTimestamp = stoi(log.substr(pos2+1));
  12.             if (currAction == "start") { 
  13.                 stk.push(make_pair(currId, currTimestamp));
  14.             } else { 
  15.                 int duration = currTimestamp - stk.top().second + 1;
  16.                 result[currId] += duration;
  17.                 stk.pop();
  18.                 if (!stk.empty()) { 
  19.                     result[stk.top().first] -= duration;
  20.                 }
  21.             }
  22.         }
  23.         return result;
  24.     }
  25. };
  1. 二叉树的层平均值
    给定一个非空二叉树, 返回一个由每层节点平均值组成的数组。

层序遍历加上一个平均值求值即可

  1. /** * 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) {} * }; */
  2. class Solution { 
  3. public:
  4.     vector<double> averageOfLevels(TreeNode* root) 
  5.     { 
  6.         int size = 0;
  7.         double val = 0.0;
  8.         queue<TreeNode*> tmpStack;
  9.         vector<double> ret;
  10.         TreeNode* ptr = NULL;
  12.         if (root == NULL) return ret;
  13.         tmpStack.push(root);
  15.         while (tmpStack.size())
  16.         { 
  17.             size = tmpStack.size();
  18.             for (int i = 0; i < size; ++i)
  19.             { 
  20.                 ptr = tmpStack.front();
  21.                 tmpStack.pop();
  22.                 val += ptr->val;
  24.                 if (ptr->left) tmpStack.push(ptr->left);
  25.                 if (ptr->right) tmpStack.push(ptr->right);
  26.             }
  27.             val = val / (double)size;
  28.             ret.push_back(val);
  29.             val = 0;
  30.         }
  32.         return ret;
  33.     }
  34. };
  1. 大礼包
    在LeetCode商店中， 有许多在售的物品。然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。
    现给定每个物品的价格，每个大礼包包含物品的清单，以及待购物品清单。请输出确切完成待购清单的最低花费。每个大礼包的由一个数组中的一组数据描述，最后一个数字代表大礼包的价格，其他数字分别表示内含的其他种类物品的数量。任意大礼包可无限次购买。

完全背包问题，用dp或者回溯+记忆化可解

  1. class Solution { 
  2. public:
  3.     bool valid(const vector<int>& sp, const vector<int>& needs) { 
  4.         for (int i = 0; i < needs.size(); ++i) { 
  5.             if (sp[i] > needs[i]) { 
  6.                 return false;
  7.             }
  8.         }
  9.         return true;
  10.     }
  11.     void backtrace(const vector<int>& price, const vector<vector<int>>& special, vector<int>& needs, int cost, int& res) { 
  12.         if (cost >= res) return;
  13.         int s = accumulate(needs.begin(), needs.end(), 0);
  14.         if (s == 0) { 
  15.             res = min(res, cost);
  16.             return;
  17.         }
  18.         bool match = false;
  19.         for (int i = 0; i < special.size(); ++i) { 
  20.             if (valid(special[i], needs)) { 
  21.                 match = true;
  22.                 for (int j = 0; j < needs.size(); ++j) { 
  23.                     needs[j] -= special[i][j];
  24.                 }
  25.                 backtrace(price, special, needs, cost + special[i].back(), res);
  26.                 for (int j = 0; j < needs.size(); ++j) { 
  27.                     needs[j] += special[i][j];
  28.                 }
  29.             }
  30.         }
  31.         // 如果没有找到任何一个合适的礼包，说明就需要单买了
  32.         if (!match) { 
  33.             for (int i = 0; i < needs.size(); ++i) { 
  34.                 cost += price[i] * needs[i];
  35.             }
  36.             res = min(res, cost);
  37.         }
  38.     }
  40.     int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) { 
  41.         // 先删除掉比单买还不划算的礼包以及个数过大的礼包
  42.         int k = 0;
  43.         for (int i = 0; i < special.size(); ++i) { 
  44.             int s = 0;
  45.             bool match = true;
  46.             for (int j = 0; j < price.size(); ++j) { 
  47.                 s += price[j] * special[i][j];
  48.                 if (special[i][j] > needs[j]) { 
  49.                     match = false;
  50.                     break;
  51.                 }
  52.             }
  53.             if (match && special[i].back() < s) { 
  54.                 special[k++] = special[i];
  55.             }
  56.         }
  57.         if (k < special.size()) { 
  58.             special.erase(special.begin() + k, special.end());
  59.         }
  60.         // 回溯
  61.         int res = INT_MAX;
  62.         backtrace(price, special, needs, 0, res);
  63.         return res;
  64.     }
  65. };
  1. 解码的方法2
    给定一条包含数字和字符’*‘的加密信息，请确定解码方法的总数。

直接遍历一遍做判断，或者用动态规划求解

  1. class Solution { 
  2. public:
  3.     #define M 1000000007;
  4.     int numDecodings(string s) { 
  5.         int len=s.size();
  6.         if(s[0]=='0') return 0;
  7.         //vector<vector<int>> dp(len,vector<int>(11,0));
  8.         long long a=1,b,c=0;
  9.         if(s[0]!='*') b=1;
  10.         else b=9;
  11.         for(int i=1;i<len;++i){ 
  12.             if(s[i]!='*'){ 
  13.                 c=0;
  14.                 if(s[i]!='0') c=b;
  15.                 if(s[i-1]=='1' || s[i-1]=='*') c+=a;
  16.                 if(s[i]>='0' && s[i]<='6' && (s[i-1]=='2' || s[i-1]=='*')) c+=a;
  17.             }
  18.             else{ 
  19.                 c=b*9;
  20.                 if(s[i-1]=='1' || s[i-1]=='*') c+=a*9;
  21.                 if(s[i-1]=='2' || s[i-1]=='*') c+=a*6;
  22.             }
  23.             c%=M;
  24.             a=b;
  25.             b=c;
  26.         }
  27.         if(len==1) return b;
  28.         return c;
  29.     }
  30. };
  1. 求解一个给定的方程，将x以字符串”x=#value”的形式返回。该方程仅包含’+’，’ - ‘操作，变量 x 和其对应系数。

先找到等号，然后左右字符串解析，提取x的系数和常数项系数并进行比较求解

  1. //分析形如"10+1x-200x"这样的字符串，累加其中的常数值和未知数系数
  2. void analy(string&s,int l,int r,int&c,int&x){  //常数值和x的系数传的是引用
  3.     while(l<=r){ 
  4.         int sig=1;
  5.         int val=0;
  6.         while(l<=r&&s[l]<'0'||s[l]>'9'){ 
  7.             if(s[l]=='-')sig=-1;
  8.             ++l;
  9.         }
  10.         while(l<=r&&s[l]>='0'&&s[l]<='9'){ 
  11.             val=val*10+(s[l]^48);
  12.             ++l;
  13.         }
  14.         if(s[l]=='x'){   //如果数字以'x'结尾
  15.             x+=sig*val; //累加到x的系数和
  16.             ++l;        //记得让指针再前进1位
  17.         }else{ 
  18.             c+=sig*val; //累加到常数和
  19.         }
  20.     }
  21. }
  22. class Solution { 
  23. public:
  24.     string solveEquation(string s) { 
  25.         int lc=0,lx=0; //左右未知数系数和常数
  26.         int rc=0,rx=0;
  27.         //printf("%s\n",s.c_str());
  28.         for(int i=0;i<s.size();++i)  //替换 "x" 为 "1x"
  29.             if(s[i]=='x'&&(i==0||(s[i-1]<'0'||s[i-1]>'9')))
  30.                 s.insert(s.begin()+i,'1');
  31.         //printf("%s\n",s.c_str());
  32.         int n=s.size();
  33.         //找中间等号的位置
  34.         int eq_idx=0;
  35.         for(int i=0;i<n;++i){ 
  36.             if(s[i]=='='){ 
  37.                 eq_idx=i;
  38.                 break;
  39.             }
  40.         }
  41.         //提取左右两边的系数（假装是分 治 算 法）
  42.         analy(s,0,eq_idx-1,lc,lx);
  43.         analy(s,eq_idx+1,n-1,rc,rx);
  44.         //printf("%dx %d = %dx %d\n",lx,lc,rx,rc);
  45.         lx-=rx;  //未知数移到左边
  46.         rc-=lc;  //常数项移到右边
  47.         //printf("%dx %d = %dx %d\n",lx,lc,rx,rc);
  48.         if(lx==0)
  49.             if(rc)return "No solution";         // 0x=2
  50.             else return "Infinite solutions";   // 0x=0
  51.         return "x="+to_string(rc/lx);
  52.     }
  53. };
  1. 设计循环双端队列
    设计实现双端队列。

双向链表实现即可

  1. struct _ListNode { 
  2.     int val;
  3.     _ListNode* pre;
  4.     _ListNode* next;
  5.     _ListNode(int value) :val(value) { 
  6.         pre = NULL;
  7.         next = NULL;
  8.     }
  9. };
  10. class MyCircularDeque { 
  11. public:
  12.     int capacity;
  13.     _ListNode* head;
  14.     _ListNode* tail;
  15.     int size;
  16.     /** Initialize your data structure here. Set the size of the deque to be k. */
  17.     MyCircularDeque(int k) { 
  18.         capacity = k;
  19.         size = 0;
  20.         head = NULL;
  21.         tail = NULL;
  22.     }
  24.     /** Adds an item at the front of Deque. Return true if the operation is successful. */
  25.     bool insertFront(int value) { 
  26.         if (isFull()) return false;
  27.         _ListNode* newNode = new _ListNode(value);
  28.         newNode->next = head;
  29.         if (head != NULL) head->pre = newNode;
  30.         head = newNode;
  31.         if (++size == 1) tail = newNode;
  32.         return true;
  33.     }
  35.     /** Adds an item at the rear of Deque. Return true if the operation is successful. */
  36.     bool insertLast(int value) { 
  37.         if (isFull()) return false;
  38.         _ListNode* newNode = new _ListNode(value);
  39.         newNode->pre = tail;
  40.         if (tail != NULL) tail->next = newNode;
  41.         tail = newNode;
  42.         if (++size == 1) head = newNode;
  43.         return true;
  44.     }
  46.     /** Deletes an item from the front of Deque. Return true if the operation is successful. */
  47.     bool deleteFront() { 
  48.         if (isEmpty()) return false;
  49.         _ListNode* node2Delete = head;
  50.         head = head->next;
  51.         if (head != NULL) head->pre = NULL;
  52.         delete node2Delete;
  53.         if (--size == 0) tail = NULL;
  54.         return true;
  55.     }
  57.     /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
  58.     bool deleteLast() { 
  59.         if (size == 0) return false;
  60.         _ListNode* node2Delete = tail;
  61.         tail = tail->pre;
  62.         if (tail != NULL) tail->next = NULL;
  63.         delete node2Delete;
  64.         if (--size == 0) head = NULL;
  65.         return true;
  66.     }
  68.     /** Get the front item from the deque. */
  69.     int getFront() { 
  70.         return isEmpty() ? -1 : head->val;
  71.     }
  73.     /** Get the last item from the deque. */
  74.     int getRear() { 
  75.         return isEmpty() ? -1 : tail->val;
  76.     }
  78.     /** Checks whether the circular deque is empty or not. */
  79.     bool isEmpty() { 
  80.         return size == 0;
  81.     }
  83.     /** Checks whether the circular deque is full or not. */
  84.     bool isFull() { 
  85.         return size == capacity;
  86.     }
  87. };

发表评论

表情：
评论列表 （有 0 条评论，263人围观）

还没有评论，来说两句吧...

相关阅读