文章目录

• 重做题 501 ，502，507,508,509,516,517,519,523，524,525,526,528,530,531，538,539,540到563全部丢失，564
• 1. 键盘行
• 1. 二叉搜索树中的众数
• 1. IPO
• 1. 下一个更大元素 II(单调栈)
• 1. 相对名次
• 1. 完美数
• 1. 出现次数最多的子树元素和
• 1. 斐波那契数（记忆化）
• 1. 二叉搜索树中的中序后继 II
• 1. 找树左下角的值
• 1. 在每个树行中找最大值
• 1. 最长回文子序列（dp********************）
• 1. 超级洗衣机
• 1. 零钱兑换 II
• 1. 随机翻转矩阵
• 1. 检测大写字母
• 1. 连续的子数组和
• 1. 通过删除字母匹配到字典里最长单词
• 1. 连续数组
• 1. 优美的排列
• 1. 按权重随机选择
• 1. 二叉搜索树的最小绝对差
• 1. 孤独像素 I
• 1. 数组中的K-diff数对
• 1. 从字符串生成二叉树
• 1. 把二叉搜索树转换为累加树
• 1. 最小时间差（先排序）
• 1. 01 矩阵(dfs,bfs)
• 1. 二叉树的直径
• 1. 朋友圈（并查集）
• • 并查集 https://blog.csdn.net/zjy\_code/article/details/80634149
• 1. 和为K的子数组
• 1. 寻找最近的回文数
• 1. 字符串的排列
• 1. 另一个树的子树
• 1. 出界的路径数
• 1. 两个字符串的删除操作
• 1. 最长和谐子序列(哈希)

重做题 501 ，502，507,508,509,516,517,519,523，524,525,526,528,530,531，538,539,540到563全部丢失，564

500. 键盘行

class Solution {
public:
    vector<string> findWords(vector<string>& words) {
        unordered_map<char,int> mp={
    {
    'q',0},{
    'w',0},{
    'e',0},{
    'r',0},{
    't',0},{
    'y',0},{
    'u',0},{
    'i',0},{
    'o',0},{
    'p',0},{
    'a',1},{
    's',1},{
    'd',1},{
    'f',1},{
    'g',1},{
    'h',1},{
    'j',1},{
    'k',1},{
    'l',1},{
    'z',2},{
    'x',2},{
    'c',2},{
    'v',2},{
    'b',2},{
    'n',2},{
    'm',2},{
    'Q',0},{
    'W',0},{
    'E',0},{
    'R',0},{
    'T',0},{
    'Y',0},{
    'U',0},{
    'I',0},{
    'O',0},{
    'P',0},{
    'A',1},{
    'S',1},{
    'D',1},{
    'F',1},{
    'G',1},{
    'H',1},{
    'J',1},{
    'K',1},{
    'L',1},{
    'Z',2},{
    'X',2},{
    'C',2},{
    'V',2},{
    'B',2},{
    'N',2},{
    'M',2}};
        vector<string> res;
        for(auto&w:words)
        {
            bool b = true;
            for(int i = 0;i<w.size()-1;i++)
            {
                if(mp[w[i]]!=mp[w[i+1]]){
    b=false;break;}
            }
            if(b)res.push_back(w);
        }
        return res;
    }
};

501. 二叉搜索树中的众数

思路：二叉搜索树的中序遍历是一个升序序列，逐个比对当前结点(root)值与前驱结点（pre)值。更新当前节点值出现次数(curTimes)及最大出现次数(maxTimes)，更新规则：若curTimes=maxTimes,将root->val添加到结果向量(res)中；若curTimes>maxTimes,清空res,将root->val添加到res,并更新maxTimes为curTimes。

作者：junstat
链接：https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/solution/er-cha-sou-suo-shu-zhong-de-zhong-shu-by-junstat/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

void inOrder(TreeNode* root, TreeNode*& pre, int& curTimes, 
             int& maxTimes, vector<int>& res){
    if (!root) return;
    inOrder(root->left, pre, curTimes, maxTimes, res);
    if (pre)
        curTimes = (root->val == pre->val) ? curTimes + 1 : 1;
    if (curTimes == maxTimes)
        res.push_back(root->val);
    else if (curTimes > maxTimes){
        res.clear();
        res.push_back(root->val);
        maxTimes = curTimes;
    }
    pre = root;
    inOrder(root->right, pre, curTimes, maxTimes, res);
}
vector<int> findMode(TreeNode* root) {
    vector<int> res;
    if (!root) return res;
    TreeNode* pre = NULL;
    int curTimes = 1, maxTimes = 0;
    inOrder(root, pre, curTimes, maxTimes, res);
    return res;
}
作者：junstat
链接：https://leetcode-cn.com/problems/find-mode-in-binary-search-tree/solution/er-cha-sou-suo-shu-zhong-de-zhong-shu-by-junstat/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

502. IPO

class Solution {
public:
    int findMaximizedCapital(int k, int W, vector<int>& Profits, vector<int>& Capital) {
        priority_queue<int> p;                                                    // 利润 大根堆
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> c;   // 资本 小根堆
        for (int i = 0; i < Capital.size(); i++) {
            c.emplace(make_pair(Capital[i], Profits[i]));
        }
        for (int i = 0; i < k; i++) {
            while (!c.empty() && c.top().first <= W) {
      // 资本小于等于W的项目，存入利润大根堆
                p.emplace(c.top().second);
                c.pop();
            }
            if(p.empty()) break;
            W += p.top();                         // 每次选利润最大的
            p.pop();
        }
        return W;
    }
};
作者：hdye
链接：https://leetcode-cn.com/problems/ipo/solution/c-you-xian-dui-lie-by-hdye/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

503. 下一个更大元素 II(单调栈)

单调栈是一个很重要的减少时间复杂d

class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        if(nums.empty())return {
    };
        stack<int> st;
        nums.insert(nums.end(),nums.begin(),nums.end());
        st.push(-1);
        vector<int> res;
        for(int i = nums.size()-1;i>=nums.size()/2;i--)
        {
            while(!st.empty() && nums[i]>=st.top())st.pop();
            st.push(nums[i]);
        }
        for(int i = nums.size()/2-1;i>=0;i--)
        {
            while(!st.empty() && nums[i]>=st.top())st.pop();
            if(st.empty())res.push_back(-1);
            else res.push_back(st.top());
            st.push(nums[i]);
        }
        reverse(res.begin(),res.end());
        return res;
    }
};
class Solution {
public:
    vector<int> nextGreaterElements(vector<int>& nums) {
        int len = nums.size();
        vector<int> vt;
        vector<int> res(len,-1);
        for(int i =0 ; i< len*2 ;i++)
        {
            while(!vt.empty()&&nums[i%len]>nums[vt.back()])
            {
                res[vt.back()]=nums[i%len];
                vt.pop_back();
            }
            vt.push_back(i%len);
        }
        return res;
    }
};

506. 相对名次

依旧是使用mp转vector重写sort函数法

class Solution {
public:
    static bool func(pair<int,int>& p1, pair<int,int>& p2)
    {
        return p1.first>p2.first;
    }
    vector<string> findRelativeRanks(vector<int>& nums) {
        int len = nums.size();
        unordered_map<int,int> mp;
        int i=0;
        for(auto num:nums)mp[num]=i++;
        vector<pair<int,int>> order(mp.begin(),mp.end());
        sort( order.begin(),order.end(),func);
        vector<string> res(len);
        for(int i=0;i<len;i++)
        {
            if(i==0){
    res[order[i].second]="Gold Medal";}
            else if(i==1){
    res[order[i].second]="Silver Medal";}
            else if(i==2){
    res[order[i].second]="Bronze Medal";}
            else{
    res[order[i].second]=to_string(i+1);}
        }
        return res;
    }
};

发现堆排序好像也很好用
利用堆来排序，建立一个优先队列，把分数和其坐标位置放入队列中，会自动按其分数高低排序，然后我们从顶端开始一个一个取出数据，由于保存了其在原数组的位置，我们可以直接将其存到结果res中正确的位置，用一个变量cnt来记录名词，前三名给奖牌，后面就是名次数。

class Solution {
public:
    vector<string> findRelativeRanks(vector<int>& nums) {
        int n = nums.size(), cnt = 1;
        vector<string> res(n, "");
        priority_queue<pair<int, int>> heap;
        for(int i =0; i <n; i++){
            heap.push({
    nums[i], i});
        }
        for(int i = 0; i < n; i++){
            int dx = heap.top().second;
            heap.pop();
            if(cnt == 1) res[dx] = "Gold Medal";
            else if(cnt == 2) res[dx] = "Silver Medal";
            else if(cnt == 3) res[dx] = "Bronze Medal";
            else res[dx] = to_string(cnt);
            cnt++;
        }
        return res;
    }
};

507. 完美数

i从1到sqrt同时计算两个因子

class Solution {
public:
    bool checkPerfectNumber(int num) {
        if(num%2!=0)return false;
        int sum=1;
        int i=2;
        int s=ceil(sqrt(num));
        for(;i<s;++i)
        {
            if(num%i==0)
            {
                sum+=i+num/i;
            }
        }
        if(i*i==num)sum+=i;
        return (num==sum);
    }
};
作者：yukarun
链接：https://leetcode-cn.com/problems/perfect-number/solution/507-wan-mei-shu-by-yukarun/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

508. 出现次数最多的子树元素和

class Solution {
public:
    unordered_map<int, int> freqInfo;
    int maxFreq = 0;
    int dfs(TreeNode * root) {
        if(root != NULL) {
            int sum = root->val + dfs(root->left) + dfs(root->right);
            freqInfo[sum]++;
            maxFreq = std::max(maxFreq, freqInfo[sum]);
            return sum;
        } else {
            return 0;
        }
    }
    vector<int> findFrequentTreeSum(TreeNode* root) {
        dfs(root);
        vector<int> res;
        for(auto & kv : freqInfo) {
            if(kv.second == maxFreq) {
                res.push_back(kv.first);
            }
        }
        return res;
    }
};
作者：haithink
链接：https://leetcode-cn.com/problems/most-frequent-subtree-sum/solution/er-cha-shu-de-ti-mu-yong-bian-li-de-guan-dian-jie-/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

509. 斐波那契数（记忆化）

之前做过这道题，使用的是最直接的递归解法，但是一直不知道超时怎么优化，明白了一种东西叫记忆化把之间算过的记忆下来就可以了

int fibMemo(int N, int* res) {
    if(N==0) return 0;
    if(N==1) return 1;
    if(res[N]==0) {
        res[N] = fibMemo(N-1, res) + fibMemo(N-2, res);
    }
    return res[N];    
}
int fib(int N){
    /* 解法一：无优化递归，展开后存在2^N的节点，存在大量重复计算
    if(N==0) return 0;
    if(N==1) return 1;
    return fib(N-1) + fib(N-2);
    */
    // 解法二 , 记忆化Memo
    int res[N+1];
    for(int i=0; i < N+1; i++) {
        res[i] = 0;
    }
    if(N==0) return 0;
    if(N==1) return 1;
    return fibMemo(N, res);
}
作者：justdoitno1
链接：https://leetcode-cn.com/problems/fibonacci-number/solution/cti-jie-dui-bi-zui-cuo-de-wu-you-hua-di-gui-memoji/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

510. 二叉搜索树中的中序后继 II

/*
// Definition for a Node.
class Node {
public:
    int val;
    Node* left;
    Node* right;
    Node* parent;
};
*/
class Solution {
public:
    Node* findfather(Node* node)
    {
        if(node->parent==NULL)return node;
        return node->parent;
    }
    Node* res;
    bool b = false;
    void dfs(Node* root,Node* node)
    {
        if(root==NULL)return;
        dfs(root->left,node);
        if(b){
    res = root;b=false;}
        if(root==node)b=true;
        dfs(root->right,node);
    }
    Node* inorderSuccessor(Node* node) {
        auto t = node;
        auto root = findfather(node);
        dfs(root,t);
        return res;
    }
};

513. 找树左下角的值

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int findBottomLeftValue(TreeNode* root) {
        vector<TreeNode*> cur = {
    root};
        TreeNode* res;
        while(!cur.empty())
        {
            vector<TreeNode*> temp;
            for(auto&c:cur)
            {
                if(c->left)temp.push_back(c->left);
                if(c->right)temp.push_back(c->right);
            }
            if(temp.empty())
            {
                return cur.front()->val;
            }
            else
            {
                cur=temp;
            }
        }
        return 0;
    }
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
vector<int> res;
public:
    void dfs(vector<TreeNode*> cur)
    {
        if(cur.empty())return;
        vector<TreeNode*> next;
        res.push_back(cur[0]->val);
        for(auto i:cur)
        {
            if(i->left)next.push_back(i->left);
            if(i->right)next.push_back(i->right);
        }
        dfs(next);
    }
    int findBottomLeftValue(TreeNode* root) {
        vector<TreeNode*> temp={
    root};
        dfs(temp);
        int len = res.size();
        return res[len-1];
    }
};

515. 在每个树行中找最大值

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> largestValues(TreeNode* root) {
        if(!root)return {
    };
        vector<int> res;
        vector<TreeNode*> cur = {
    root};
        res.push_back(root->val);
        while(!cur.empty())
        {
            vector<TreeNode*> next;
            int m = INT_MIN;
            for(int i = 0 ; i <cur.size();i++)
            {
                if(cur[i]->left)
                {
                    m = max(m,cur[i]->left->val);
                    next.push_back(cur[i]->left);
                }
                if(cur[i]->right)
                {
                    m = max(m,cur[i]->right->val);
                    next.push_back(cur[i]->right);
                }                
            }
            if(!next.empty())res.push_back(m);
            cur=next;
        }
        return res;
    }
};
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
private:
vector<int> res;
public:
    void dfs(vector<TreeNode*> cur)
    {
        if(cur.empty())return;
        int m = INT_MIN;
        vector<TreeNode*> next;
        for(auto i:cur)
        {
            m = max(m,i->val);
            if(i->left)next.push_back(i->left);
            if(i->right)next.push_back(i->right);
        }
        res.push_back(m);
        dfs(next);
    }
    vector<int> largestValues(TreeNode* root) {
        if(root==NULL)return {
    };
        vector<TreeNode*> temp={
    root};
        dfs(temp);
        return res;
    }
};

516. 最长回文子序列（dp********************）

总结一下：

最长公共连续子串(大一圈正常遍历)
这个必须要记住
if(s1[i]==s2[i]) v[i][j] =v[i-1]v[j-1] +1
else v[i][j] = 0
最长回文子串
把这个字符串翻过来然后用和上面一样的方法求就行了
所有的回文子串（从右下开始遍历右上部分）
其实可以从小到大进行遍历，然后也不适用这个dp表达式，而是新写一个回文函数每次进行判断，这样实用性更广
if(s1[i]==s2[j] && ( j-i<=2 || v[i+1][j-1]) v[i][j] = true;
最长公共子序列（大一圈正常遍历）
这个必须要记住
if(s1[i]==s2[j]) v[i][j] = v[i-1][j-1]+1
else v[i][j] = max(v[i-1][j],v[i][j-1])
最长回文子序列
因为是子序列不是子串，所以可以逆置原字符串，采用最长公共子序列LCS来求解。
逆置后公共子序列就是回文子序列。

class Solution {
public:
    int longestPalindromeSubseq(string s) {
        int len = s.size();
        //vector<vector<bool>> v(len, vector<bool>(len, false));
        /*
        int max = 0 ;
        for(int i = len-1; i>=0 ;i--)
        {
            for(int j = i ; j <len ;j++)
            {
                if( s[i]==s[j] && (j-i<=2 || v[i+1][j-1])  )
                {
                    v[i][j] = true;
                    if(j-i+1>max)max = j -i+1;
                }
            }
        }
        return max;
        */
        string s1=s;
        reverse(s1.begin(),s1.end());
        vector<vector<int>> v(len+1, vector<int>(len+1, 0));
        for(int i = 1 ; i<len+1 ;i++)
        {
            for(int j = 1 ; j<len+1 ; j++)
            {
                if(s[i-1]==s1[j-1]) v[i][j] =v[i-1][j-1]+1;
                else v[i][j] = max(v[i-1][j],v[i][j-1]);
            }
        }
        return v[len][len];
    }   
};

517. 超级洗衣机

用当前值减去平均值【差值】，就是每个洗衣机要传入或者传出的数量，正数表示要传出，负数表示要传入
对于第[i]个洗衣机来说，左边要传入或者传出的数量，就是左边所有洗衣机的差值之和，为正表示左边有剩余，需要传到右边，为负表示左边不够，需要右边传过来，不管哪种情况，都要经过[i]节点，算作【流量】
差值 与 流量 的最大值，就是当前洗衣机要传入或者传出的数量
遍历所有洗衣机，找出最大值，即为最少次数

作者：beny-g
链接：https://leetcode-cn.com/problems/super-washing-machines/solution/csi-lu-by-beny-g/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
public:
    int findMinMoves(vector<int>& machines) {
        int sum=0;
        for(int& m:machines) sum+=m;
        int size=machines.size();
        if (sum%size) return -1;
        int avan = sum/size;
        int ba=0, mx, res=0;
        for(int& m:machines){
            ba += m-avan;
            mx = max(m-avan, abs(ba));
            res = max(res, mx);
        };
        return res;
    }
};
作者：beny-g
链接：https://leetcode-cn.com/problems/super-washing-machines/solution/csi-lu-by-beny-g/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

518. 零钱兑换 II

set超时

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        if(amount==0)return 1;
        if(coins.empty())return 0;
        vector<set<multiset<int>>> dp(amount+1);
        for(int i =1;i<=amount;i++)
        {
            for(auto&c:coins)
            {
                if(i>=c)
                {
                    if(dp[i-c].empty())
                    {
                        if(i==c)dp[i].insert({
    c});
                    }
                    else
                    {
                        for(auto&j:dp[i-c])
                        {
                            auto t = j;
                            t.insert(c);
                            dp[i].insert(t);
                        }
                    }
                }
            }
        }
        return dp.back().size();
    }
};

dfs超时

class Solution {
public:
    bool canPartition(vector<int>& nums) {
        int sum = 0;
        for(auto n:nums)sum+=n;
        if(sum%2==1)return false;
        //容量为sum/2,物品容量和价值都为nums
        int N=nums.size();
        vector<vector<int>> dp(N+1,vector<int>(sum/2+1,0));
        for(int i = 1;i<=N;i++)
        {
            for(int j =1;j<=sum/2;j++)
            {
                if(j<nums[i-1]) {
    dp[i][j]=dp[i-1][j];}
                else
                {
                    dp[i][j]=max(  dp[i-1][j],  dp[i-1][j-nums[i-1]]  +  nums[i-1]  );
                }
            }
        }
        return dp[N][sum/2]==sum/2;
    }
};

dp

class Solution {
public:
    int change(int amount, vector<int>& coins) {
        int n = coins.size();
        vector<vector<int>> dp(n + 1, vector<int>(amount + 1));
        //base case:
        for(int i = 0; i <= n; i++) {
            dp[i][0] = 1;
        }
        for(int i = 1; i <= amount; i++) {
            dp[0][i] = 0;
        }
        for(int i = 1; i <= n; i++) {
            for(int j = 1; j <= amount; j++) {
                if(j - coins[i - 1] >= 0) dp[i][j] = dp[i - 1][j] + dp[i][j - coins[i - 1]]; //完全背包，选的情况仍为i
                else dp[i][j] = dp[i - 1][j];
            }
        }
        return dp[n][amount];
    }
};
作者：Komaeda_Nagito
链接：https://leetcode-cn.com/problems/coin-change-2/solution/dp-wan-quan-bei-bao-ji-ben-zuo-fa-c-by-kiritoh/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

519. 随机翻转矩阵

思想还是很值得学习的，因为每次产生一个新的可能会和之前的重复，这样的话会十分耗时，一种方法是维护一个不断减少的值，每次就在小于这个值的地方产生，如果之前产生过的会用一个哈希表进行记录，逻辑上比较难理解

class Solution {
    unordered_map<int,int> map;
    int m, n, num;
    int x, y, pos, prev;
public:
    Solution(int n_rows, int n_cols) {
        m = n_rows;
        n = n_cols;
        num = m*n;
    }
    vector<int> flip() {
        if(num == 0) return {
    };
        pos = rand()%(num);
        num--;//下一轮，减少一个数
        if(map.count(pos))//map包含pos的key
        {
            prev = pos;//记录当前pos
            pos = map[pos];//真实的取走的pos
            if(!map.count(num))//把最后一个位置的数换到当前
                map[prev] = num;
            else//如果最后一个位置有map值，用其值替换
                map[prev] = map[num];
        }
        else//map不包含pos的key
        {
        //pos就是当前位置，只需把末尾的数替换到当前，同上
            if(!map.count(num))
                map[pos] = num;
            else
                map[pos] = map[num];
        }
        x = pos/n;
        y = pos-x*n;
        return {
    x, y};
    }
    void reset() {
        num = m*n;
        map.clear();
    }
};
作者：kobe24o
链接：https://leetcode-cn.com/problems/random-flip-matrix/solution/zhuan-cheng-1wei-suo-xiao-chang-du-ha-xi-mapti-hua/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

520. 检测大写字母

class Solution {
public:
    bool detectCapitalUse(string word) {
        if(word.empty() || word.size()==1)return true;
        bool b0 = (word[0]>='a' && word[0]<='z');
        bool b1 = (word[1]>='a' && word[1]<='z');
        if(word.size()==2 && b0 && !b1)return false;
        for(int i = 2;i<word.size();i++)
        {
            if(  (b0 && !b1)  || ((word[i]>='a' && word[i]<='z')!=b1))return false;
        }
        return true;
    }
};

523. 连续的子数组和

这道题不适合dfs的，因为是子数组这种的直接用dp就可以了，一般子序列用dfs

class Solution {
public:
    bool checkSubarraySum(vector<int>& nums, int k) {
        k=abs(k);
        int len = nums.size();
        vector<int> dp = nums;
        for(int i = 1;i<len;i++)
        {
            dp[i]=dp[i-1]+dp[i];
        }
        int sum=dp.back();
        unordered_set<int> st;
        if(k==0)
        {
            for(int i = 0;i<len;i++)
            {
                for(int j = i+1;j<len;j++)
                {
                    if (i == 0) {
     if (dp[j]==0)return true; }
                    else if ((dp[j]-dp[i-1])==0)return true;
                }
            }            
        }
        else
        {
            for(int i = 0;i<len;i++)
            {
                for(int j = i+1;j<len;j++)
                {
                    if (i == 0) {
     if (dp[j]%k==0)return true; }
                    else if ((dp[j]-dp[i-1])%k==0)return true;
                }
            }
        }
        return false;;
    }
};

524. 通过删除字母匹配到字典里最长单词

dp二维，超时了

class Solution {
public:
bool isok(string a, string b)
{
    int lena = a.size();
    int lenb = b.size();
    vector<vector<int>> dp(lena + 1, vector<int>(lenb + 1, false));
    for (int j = 0; j <= lenb; j++)
    {
        dp[0][j] = true;
    }
    for (int i = 1; i <= lena; i++)
    {
        for (int j = 1; j <= lenb; j++)
        {
            if (a[i - 1] == b[j - 1])
            {
                dp[i][j] = dp[i - 1][j - 1] || dp[i][j - 1];
            }
            else
            {
                dp[i][j] = dp[i][j - 1];
            }
        }
    }
    return dp[lena][lenb];
}
    string findLongestWord(string s, vector<string>& d) {
        vector<string> res;
        int ml= 0;
        for(auto&d1:d)
        {
            if(isok(d1,s))
            {
                if(d1.size()>ml)
                {
                    ml=d1.size();
                    res.clear();
                    res.push_back(d1);
                }
                else if(d1.size()==ml)
                {
                    res.push_back(d1);
                }
            }
        }
        if(res.empty())return "";
        sort(res.begin(),res.end());
        return res.front();
    }
};

双指针一遍遍历的方法高效很多

class Solution {
public:
bool isok(string a, string b)
{
    int lena = a.size();
    int lenb = b.size();
    int i = 0,j=0;
    while(j<lenb)
    {
        if(a[i]==b[j])
        {
            i++;j++;
        }
        else j++;
    }
    return i==lena;
}
    string findLongestWord(string s, vector<string>& d) {
        vector<string> res;
        int ml= 0;
        for(auto&d1:d)
        {
            if(isok(d1,s))
            {
                if(d1.size()>ml)
                {
                    ml=d1.size();
                    res.clear();
                    res.push_back(d1);
                }
                else if(d1.size()==ml)
                {
                    res.push_back(d1);
                }
            }
        }
        if(res.empty())return "";
        sort(res.begin(),res.end());
        return res.front();
    }
};

525. 连续数组

class Solution {
public:
int findMaxLength(vector<int> nums) {
    if(nums.empty())return 0;
    int len = nums.size();
    vector<int> dp(len, 0);
    unordered_map<int,int> mp;
    mp[0]=-1;
    dp[0] = (nums[0] == 0 ? -1 : 1);
    mp[dp[0]]=0;
    int res = 0;
    for (int i = 1; i < len; i++)
    {
        dp[i] = dp[i - 1] + (nums[i] == 0 ? -1 : 1);
        if(mp.find(dp[i])==mp.end())
        {
            mp[dp[i]]=i;
        }
        else
        {
            res = max(res,i-mp[dp[i]]);
        }
    }
    return res;
}
};
class Solution {
public:
    int findMaxLength(vector<int>& nums) {
        unordered_map<int,int> mp;
        mp[0]=-1;
        int sum=0;
        int res=0;
        for(int i = 0 ;i<nums.size() ;i++)
        {
            int num =nums[i];
            sum += (num==0)?-1:1;
            if(mp.find(sum)==mp.end())
            {
    mp[sum]=i;}
            else
            {
    res = max(res, i-mp[sum]);}
        }
        return res;
    }
};

526. 优美的排列

class Solution {
public:
    int res =0;
    vector<int> path;
    vector<int> visited;
    void dfs(int N,int p)
    {
        if(path.size()==N)
        {
            res++;
            return;
        }
        for(int i = 1;i<=N;i++)
        {
            if(visited[i-1]==0 && (i%p==0 || p%i==0))
            {
                visited[i-1]=1;
                path.push_back(i);
                dfs(N,p+1);
                path.pop_back();
                visited[i-1]=0;
            }
        }
    }
    int countArrangement(int N) {
        visited = vector<int>(N, 0);
        dfs(N,1);
        return res;
    }
};

528. 按权重随机选择

class Solution {
public:
    vector<int> dp;
    int sum;
    Solution(vector<int>& w) {
        dp=w;
        for(int i = 1;i<dp.size();i++)
        {
            dp[i]=dp[i-1]+dp[i];
        }
        sum=dp.back();
    }
    int pickIndex() {
        int t = rand()%sum;
        int x= lower_bound(dp.begin(),dp.end(),t) - dp.begin();
        return x;
    }
};
/**
 * Your Solution object will be instantiated and called as such:
 * Solution* obj = new Solution(w);
 * int param_1 = obj->pickIndex();
 */