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

待我称王封你为后i 2022-11-18 01:38 128阅读 0赞

1.  平方数之和  
    给定一个非负整数 c ，你要判断是否存在两个整数 a 和 b，使得 a2 + b2 = c 。

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

class Solution { 
    public:
        bool judgeSquareSum(int c) 
        { 
            for (int i = 2; i * i <= c; i++) { 
                int count = 0;
                if (c % i == 0) 
                { 
                    while (c % i == 0) 
                    { 
                        count++;
                        c /= i;
                    }
                    if (i % 4 == 3 && count % 2 != 0)
                        return false;
                }
            }
            return c % 4 != 3;
        }
    };

1.  函数的独占时间  
    给出一个非抢占单线程CPU的 n 个函数运行日志，找到函数的独占时间。

**栈的简单运用**

class Solution { 
    public:
        vector<int> exclusiveTime(int n, vector<string>& logs) { 
            vector<int> result(n, 0);
            stack<pair<int, int>> stk;
            for (string &log : logs) { 
                size_t pos1 = log.find(':');
                size_t pos2 = log.rfind(':');
                int currId = stoi(log.substr(0, pos1));
                string currAction = log.substr(pos1+1, pos2-pos1-1);
                int currTimestamp = stoi(log.substr(pos2+1));
                if (currAction == "start") { 
                    stk.push(make_pair(currId, currTimestamp));
                } else { 
                    int duration = currTimestamp - stk.top().second + 1;
                    result[currId] += duration;
                    stk.pop();
                    if (!stk.empty()) { 
                        result[stk.top().first] -= duration;
                    }
                }
            }
            return result;
        }
    };

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) {} * }; */
    class Solution { 
    public:
        vector<double> averageOfLevels(TreeNode* root) 
        { 
            int size = 0;
            double val = 0.0;
            queue<TreeNode*> tmpStack;
            vector<double> ret;
            TreeNode* ptr = NULL;
    
            if (root == NULL) return ret;
            tmpStack.push(root);
    
            while (tmpStack.size())
            { 
                size = tmpStack.size();
                for (int i = 0; i < size; ++i)
                { 
                    ptr = tmpStack.front();
                    tmpStack.pop();
                    val += ptr->val;
    
                    if (ptr->left) tmpStack.push(ptr->left);
                    if (ptr->right) tmpStack.push(ptr->right);
                }
                val = val / (double)size;
                ret.push_back(val);
                val = 0;
            }
            
            return ret;
        }
    };

1.  大礼包  
    在LeetCode商店中， 有许多在售的物品。然而，也有一些大礼包，每个大礼包以优惠的价格捆绑销售一组物品。  
    现给定每个物品的价格，每个大礼包包含物品的清单，以及待购物品清单。请输出确切完成待购清单的最低花费。每个大礼包的由一个数组中的一组数据描述，最后一个数字代表大礼包的价格，其他数字分别表示内含的其他种类物品的数量。任意大礼包可无限次购买。

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

class Solution { 
    public:
        bool valid(const vector<int>& sp, const vector<int>& needs) { 
            for (int i = 0; i < needs.size(); ++i) { 
                if (sp[i] > needs[i]) { 
                    return false;
                }
            }
            return true;
        }
        void backtrace(const vector<int>& price, const vector<vector<int>>& special, vector<int>& needs, int cost, int& res) { 
            if (cost >= res) return;
            int s = accumulate(needs.begin(), needs.end(), 0);
            if (s == 0) { 
                res = min(res, cost);
                return;
            }
            bool match = false;
            for (int i = 0; i < special.size(); ++i) { 
                if (valid(special[i], needs)) { 
                    match = true;
                    for (int j = 0; j < needs.size(); ++j) { 
                        needs[j] -= special[i][j];
                    }
                    backtrace(price, special, needs, cost + special[i].back(), res);
                    for (int j = 0; j < needs.size(); ++j) { 
                        needs[j] += special[i][j];
                    }
                }
            }
            // 如果没有找到任何一个合适的礼包，说明就需要单买了
            if (!match) { 
                for (int i = 0; i < needs.size(); ++i) { 
                    cost += price[i] * needs[i];
                }
                res = min(res, cost);
            }
        }
    
        int shoppingOffers(vector<int>& price, vector<vector<int>>& special, vector<int>& needs) { 
            // 先删除掉比单买还不划算的礼包以及个数过大的礼包
            int k = 0;
            for (int i = 0; i < special.size(); ++i) { 
                int s = 0;
                bool match = true;
                for (int j = 0; j < price.size(); ++j) { 
                    s += price[j] * special[i][j];
                    if (special[i][j] > needs[j]) { 
                        match = false;
                        break;
                    }
                }
                if (match && special[i].back() < s) { 
                    special[k++] = special[i];
                }
            }
            if (k < special.size()) { 
                special.erase(special.begin() + k, special.end());
            }
            // 回溯
            int res = INT_MAX;
            backtrace(price, special, needs, 0, res);
            return res;
        }
    };

1.  解码的方法2  
    给定一条包含数字和字符’\*'的加密信息，请确定解码方法的总数。

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

class Solution { 
    public:
        #define M 1000000007;
        int numDecodings(string s) { 
            int len=s.size();
            if(s[0]=='0') return 0;
            //vector<vector<int>> dp(len,vector<int>(11,0));
            long long a=1,b,c=0;
            if(s[0]!='*') b=1;
            else b=9;
            for(int i=1;i<len;++i){ 
                if(s[i]!='*'){ 
                    c=0;
                    if(s[i]!='0') c=b;
                    if(s[i-1]=='1' || s[i-1]=='*') c+=a;
                    if(s[i]>='0' && s[i]<='6' && (s[i-1]=='2' || s[i-1]=='*')) c+=a;
                }
                else{ 
                    c=b*9;
                    if(s[i-1]=='1' || s[i-1]=='*') c+=a*9;
                    if(s[i-1]=='2' || s[i-1]=='*') c+=a*6;
                }
                c%=M;
                a=b;
                b=c;
            }
            if(len==1) return b;
            return c;
        }
    };

1.  求解一个给定的方程，将x以字符串"x=\#value"的形式返回。该方程仅包含’+’，’ - '操作，变量 x 和其对应系数。

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

//分析形如"10+1x-200x"这样的字符串，累加其中的常数值和未知数系数
    void analy(string&s,int l,int r,int&c,int&x){  //常数值和x的系数传的是引用
        while(l<=r){ 
            int sig=1;
            int val=0;
            while(l<=r&&s[l]<'0'||s[l]>'9'){ 
                if(s[l]=='-')sig=-1;
                ++l;
            }
            while(l<=r&&s[l]>='0'&&s[l]<='9'){ 
                val=val*10+(s[l]^48);
                ++l;
            }
            if(s[l]=='x'){   //如果数字以'x'结尾
                x+=sig*val; //累加到x的系数和
                ++l;        //记得让指针再前进1位
            }else{ 
                c+=sig*val; //累加到常数和
            }
        }
    }
    class Solution { 
    public:
        string solveEquation(string s) { 
            int lc=0,lx=0; //左右未知数系数和常数
            int rc=0,rx=0;
            //printf("%s\n",s.c_str());
            for(int i=0;i<s.size();++i)  //替换 "x" 为 "1x"
                if(s[i]=='x'&&(i==0||(s[i-1]<'0'||s[i-1]>'9')))
                    s.insert(s.begin()+i,'1');
            //printf("%s\n",s.c_str());
            int n=s.size();
            //找中间等号的位置
            int eq_idx=0;
            for(int i=0;i<n;++i){ 
                if(s[i]=='='){ 
                    eq_idx=i;
                    break;
                }
            }
            //提取左右两边的系数（假装是分 治 算 法）
            analy(s,0,eq_idx-1,lc,lx);
            analy(s,eq_idx+1,n-1,rc,rx);
            //printf("%dx %d = %dx %d\n",lx,lc,rx,rc);
            lx-=rx;  //未知数移到左边
            rc-=lc;  //常数项移到右边
            //printf("%dx %d = %dx %d\n",lx,lc,rx,rc);
            if(lx==0)
                if(rc)return "No solution";         // 0x=2
                else return "Infinite solutions";   // 0x=0
            return "x="+to_string(rc/lx);
        }
    };

1.  设计循环双端队列  
    设计实现双端队列。

**双向链表实现即可**

struct _ListNode { 
        int val;
        _ListNode* pre;
        _ListNode* next;
        _ListNode(int value) :val(value) { 
            pre = NULL;
            next = NULL;
        }
    };
    class MyCircularDeque { 
    public:
        int capacity;
        _ListNode* head;
        _ListNode* tail;
        int size;
        /** Initialize your data structure here. Set the size of the deque to be k. */
        MyCircularDeque(int k) { 
            capacity = k;
            size = 0;
            head = NULL;
            tail = NULL;
        }
    
        /** Adds an item at the front of Deque. Return true if the operation is successful. */
        bool insertFront(int value) { 
            if (isFull()) return false;
            _ListNode* newNode = new _ListNode(value);
            newNode->next = head;
            if (head != NULL) head->pre = newNode;
            head = newNode;
            if (++size == 1) tail = newNode;
            return true;
        }
    
        /** Adds an item at the rear of Deque. Return true if the operation is successful. */
        bool insertLast(int value) { 
            if (isFull()) return false;
            _ListNode* newNode = new _ListNode(value);
            newNode->pre = tail;
            if (tail != NULL) tail->next = newNode;
            tail = newNode;
            if (++size == 1) head = newNode;
            return true;
        }
    
        /** Deletes an item from the front of Deque. Return true if the operation is successful. */
        bool deleteFront() { 
            if (isEmpty()) return false;
            _ListNode* node2Delete = head;
            head = head->next;
            if (head != NULL) head->pre = NULL;
            delete node2Delete;
            if (--size == 0) tail = NULL;
            return true;
        }
    
        /** Deletes an item from the rear of Deque. Return true if the operation is successful. */
        bool deleteLast() { 
            if (size == 0) return false;
            _ListNode* node2Delete = tail;
            tail = tail->pre;
            if (tail != NULL) tail->next = NULL;
            delete node2Delete;
            if (--size == 0) head = NULL;
            return true;
        }
    
        /** Get the front item from the deque. */
        int getFront() { 
            return isEmpty() ? -1 : head->val;
        }
    
        /** Get the last item from the deque. */
        int getRear() { 
            return isEmpty() ? -1 : tail->val;
        }
    
        /** Checks whether the circular deque is empty or not. */
        bool isEmpty() { 
            return size == 0;
        }
    
        /** Checks whether the circular deque is full or not. */
        bool isFull() { 
            return size == capacity;
        }
    };