c++ leetcode 500-600

朴灿烈づ我的快乐病毒、 2023-07-20 13:44 5阅读 0赞

### 文章目录 ###

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

# 重做题 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;
        }
    };

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();
     */

# 530. 二叉搜索树的最小绝对差 #

/**
     * 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 res = INT_MAX;
        int pre =-1;
        void dfs(TreeNode* root)
        {
        
            if(!root)return;   
            dfs(root->left);   
            if(pre==-1)
            {
        
                pre = root->val;
            }
            else 
            {
        
                res = min(res,abs(root->val-pre));
                pre = root->val;
            }
            dfs(root->right);
        }
        int getMinimumDifference(TreeNode* root) {
        
            dfs(root);
            return res;
        }
    };

# 531. 孤独像素 I #

class Solution {
        
    public:
        int findLonelyPixel(vector<vector<char>>& picture) {
        
            int m = picture.size();
            int n = picture[0].size();
            vector<int> dp1(m,0);
            vector<int> dp2(n,0);
            for(int i = 0;i<m;i++)
            {
        
                for(int j = 0;j<n;j++)
                {
        
                    if(picture[i][j]=='B')
                    {
        
                        dp1[i]++;
                        dp2[j]++;
                    }
                }
            }
            int res = 0;
            for(int i=0;i<m;i++)
            {
        
                for(int j =0;j<n;j++)
                {
        
                    if(picture[i][j]=='B' && dp1[i]==1 && dp2[j]==1)
                    {
        
                        res++;
                    }
                }
            }
            return res;
    
        }
    };

# 532. 数组中的K-diff数对 #

class Solution {
        
    public:
        int findPairs(vector<int>& nums, int k) {
        
            if(k<0)return 0;
            unordered_map<int,int> mp;
            for(auto&n:nums)mp[n]++;
            int res =0;
            if(k==0)
            {
        
                for(auto&m:mp)
                {
        
                    if(m.second>1)res++;
                }
                return res;
            }
            for(auto&m:mp)
            {
        
                if(mp.find(m.first+k)!=mp.end())res++;
            }
            return res;
        }
    };

# 536. 从字符串生成二叉树 #

思路：使用栈，如果是数字就放入栈中，如果是）ji

/**
     * 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:
    
        TreeNode* str2tree(string s) {
        
            vector<string> vt;
            int i = 0;
            while(i<s.size())
            {
        
    		if (s[i] == '(') {
        
    			vt.push_back("("); i++;
    		}
    	
    		else if (s[i] == ')') {
        
    			vt.push_back(")"); i++;
    		}
                else
                {
        
                    int j = i;
                    while(i<s.size() && isdigit(s[i]))i++;
                    vt.push_back(s.substr(j,i-j));
                }
            }
            stack<TreeNode*> st;
            for(int i = 0;i<vt.size();i++)
            {
        
                if(vt[i]==")")
                {
        
                    auto t = st.top();st.pop();
                    if(!st.top()->left)st.top()->left=t;
                    else st.top()->right=t;
                }
                else if(vt[i]=="("){
        }
                else
                {
        
                    TreeNode* t = new TreeNode(stoi(vt[i]));
                    st.push(t);
    
                }
            }
            while(st.size()>1 )st.pop();
            return st.top();
        }
    };

# 538. 把二叉搜索树转换为累加树 #

先右再左就是中序遍历的倒序了，然后采用累加的手段累加到前面的节点上

BST的中序遍历就是从小到大,那么反过来就是从大到小,然后累加就好了.
    
    class Solution {
        
       int num = 0;
    
        public TreeNode convertBST(TreeNode root) {
        
            if (root != null) {
        
                //遍历右子树
                convertBST(root.right);
                //遍历顶点
                root.val = root.val + num;
                num = root.val;
                //遍历左子树
                convertBST(root.left);
                return root;
            }
            return null;
        }
    }

# 539. 最小时间差（先排序） #

使用了两层循环，没有先排序，是n方的复杂度

class Solution {
        
    public:
        vector<int> func(string s)
        {
        
            int h,m;
            int i = 0;
            while(i<s.size())
            {
        
                int j = i;
                while(i<s.size() && s[i]!=':')i++;
                if(s[i]==':')
                {
        
                    h = stoi(s.substr(j,i-j));
                    i++;
                }
                else
                {
        
                    m = stoi(s.substr(j,i-j));break;
                }
            }
            return {
        h,m};
        }
        int func1(vector<int> a,vector<int> b)
        {
        
            if(b[0]>=a[0])swap(a,b);
            return min((23 - a[0]) * 60 + (60 - a[1]) + b[0] * 60 + b[1], (a[0]==b[0])?(abs(a[1]-b[1])):((a[0] - b[0]-1) * 60 + a[1] + (60 - b[1]))       );
        }
        int findMinDifference(vector<string>& timePoints) {
        
            vector<vector<int>> vt;
            for(auto&t:timePoints)
            {
        
                auto r = func(t);
                vt.push_back({
        r[0],r[1]});
            }
            int res = INT_MAX;
            for(int i = 0;i<vt.size();i++)
            {
        
                for(int j = 0;j<i;j++)
                {
        
                    res = min(res,func1(vt[i],vt[j]));
                }
            }
            return res;
        }
    };

先排序之后，在遍历比较，时间复杂度为nlogn,先排序是减少时复杂度比较重要的技巧

class Solution {
        
    public:
        vector<int> func(string s)
        {
        
            int h,m;
            int i = 0;
            while(i<s.size())
            {
        
                int j = i;
                while(i<s.size() && s[i]!=':')i++;
                if(s[i]==':')
                {
        
                    h = stoi(s.substr(j,i-j));
                    i++;
                }
                else
                {
        
                    m = stoi(s.substr(j,i-j));break;
                }
            }
            return {
        h,m};
        }
        int func1(vector<int> a,vector<int> b)
        {
        
            if(b[0]>=a[0])swap(a,b);
            return min((23 - a[0]) * 60 + (60 - a[1]) + b[0] * 60 + b[1], (a[0]==b[0])?(abs(a[1]-b[1])):((a[0] - b[0]-1) * 60 + a[1] + (60 - b[1]))       );
        }
        static bool cmp(vector<int>a,vector<int>b)
        {
        
            if(a[0]==b[0])return a[1]<b[1];
            return a[0]<b[0];
        }
        int findMinDifference(vector<string>& timePoints) {
        
            vector<vector<int>> vt;
            for(auto&t:timePoints)
            {
        
                auto r = func(t);
                vt.push_back({
        r[0],r[1]});
            }
            int res = INT_MAX;
            sort(vt.begin(),vt.end(),cmp);
            for(int i = 0;i<vt.size()-1;i++)
            {
        
                    res = min(res,func1(vt[i],vt[i+1]));
            }
            res = min(res,func1(vt[0],vt.back()));
            return res;
        }
    };

# 542. 01 矩阵(dfs,bfs) #

dfs超时，推荐dfs

class Solution {
        
    public:
        //dfs的时间复杂度高，当dfs复杂度高用bfs空间复杂度高的试试
        vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        
            int len1 = matrix.size();
            int len2 = matrix[0].size();
            vector<vector<int>> board(len1,vector<int>(len2,0));
            vector<vector<int>> visited(len1,vector<int>(len2,0));//访问数组
            queue<vector<int>> qt;
            for(int i = 0;i<len1;i++)
            {
        
                for(int j =0;j<len2;j++)
                {
        
                    if(matrix[i][j]==0){
        vector<int> t;t.push_back(i);t.push_back(j);visited[i][j]=1;qt.push(t);}
                }
            }
            int num = 1;
            while(!qt.empty())
            {
        
                int len = qt.size();
                for(int c = 0;c<len;c++)
                {
        
                    auto temp = qt.front();qt.pop();
                    int i = temp[0],j = temp[1];
                    if(i-1>=0 && visited[i-1][j]==0){
        board[i-1][j]=num; qt.push({
        i-1,j});visited[i-1][j]=1;}
                    if(j-1>=0 && visited[i][j-1]==0){
        board[i][j-1]=num; qt.push({
        i,j-1});visited[i][j-1]=1;}
                    if(i+1<len1 && visited[i+1][j]==0){
        board[i+1][j]=num; qt.push({
        i+1,j});visited[i+1][j]=1;}
                    if(j+1<len2 && visited[i][j+1]==0){
        board[i][j+1]=num; qt.push({
        i,j+1});visited[i][j+1]=1;}
                }
                num++;
            }
            return board;
        }
    };

在应用题中的dfs经常会遇到一个问题，在查看这个点四周的状态时，下一次递归又会回到这个地方，容易造成无限循环，在这道题中，可以使用不传入引用值，将已经搜索过的数改为其他数的情况，但这种方法并不万能  
这里面值得推荐的一个地方时，利用递归的次数来作为要返回的数量

class Solution {
        
    private:
    int m;
    int n;
    public:
    	int dfs(int i, int j, vector<vector<int>> matrix)
    	{
        
    		if (i < 0 || i >= m || j < 0 || j >= n) return 20000;
    		if (matrix[i][j] == 0)return 0;
    		if (matrix[i][j] == 'A')return 20000;
    		matrix[i][j] = 'A';
    		int num1 = min(dfs(i - 1, j, matrix),dfs(i+1,j,matrix));
    		int num2 = min(dfs(i, j + 1, matrix), dfs(i, j - 1, matrix));
    		
    		
    		return min(num1,num2)+1;
    	}
    	vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        
    		if (matrix.empty()) return matrix;
    		m = matrix.size();
    		n = matrix[0].size();
    		for (int i = 0; i < m; i++)
    		{
        
    			for (int j = 0; j < n; j++)
    			{
        
    				matrix[i][j] = dfs(i, j, matrix);
    			}
    		}
    		return matrix;
    	}
    };

动态规划方法，对于有些问题，很好找到其与旁边的对应关系  
解题思路  
定义dp\[i\]\[j\]表示该位置距离0的最短距离，其实很容易想到dp\[i\]\[j\]要么等于0，要么等于min(dp\[i-1\]\[j\],dp\[i+1\]\[j\],dp\[i\]\[j-1\],dp\[i\]\[j+1\])+1

这个问题棘手的就是，我们更新状态的时候，要么从左上到右下，要么右下到左上，或者更不常见的右上到左下以及左下到右上。无论哪种更新方式都只能依赖两个前置状态（比如从左上到右下时， dp\[i\]\[j\]只能依赖dp\[i-1\]\[j\]和dp\[i\]\[j-1\]）。

这里做两遍dp状态的更新来解决上述问题， 第一次从左上到右下，转移方程为：  
dp\[i\]\[j\] = 0 或  
dp\[i\]\[j\] = min(dp\[i\]\[j-1\]+1, dp\[i-1\]\[j\]+1)  
第二次更新从右下到左上，转移方程为  
dp\[i\]\[j\] = 0 或  
dp\[i\]\[j\] = min(dp\[i\]\[j\], dp\[i\]\[j+1\]+1, dp\[i+1\]\[j\]+1)

齐活

作者：yuexiwen  
链接：https://leetcode-cn.com/problems/01-matrix/solution/c-2bian-dp-jian-dan-yi-dong-by-yuexiwen/  
来源：力扣（LeetCode）  
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

class Solution {
        
    public:
        vector<vector<int>> updateMatrix(vector<vector<int>>& matrix) {
        
            vector<vector<int>> dp(matrix.size(), vector<int>(matrix[0].size(), 0));
            for (int i = 0; i < matrix.size(); ++i) {
        
                for (int j = 0; j < matrix[0].size(); ++j) {
        
                    if (!matrix[i][j]) continue;
                    int t_val = i == 0 ? 10001 : dp[i-1][j] + 1;
                    int l_val = j == 0 ? 10001 : dp[i][j-1] + 1;
                    dp[i][j] = min(t_val, l_val);
                }
            }
            for (int i = matrix.size()-1; i >= 0; --i) {
        
                for (int j = matrix[0].size()-1; j >= 0; --j) {
        
                    if (!matrix[i][j]) continue;
                    int b_val = i == matrix.size()-1 ? 10001 : dp[i+1][j] + 1;
                    int r_val = j == matrix[0].size()-1 ? 10001 : dp[i][j+1] +1;
                    dp[i][j] = min(dp[i][j], min(b_val, r_val));
                }
            }
            return dp;
        }
    };
    
    作者：yuexiwen
    链接：https://leetcode-cn.com/problems/01-matrix/solution/c-2bian-dp-jian-dan-yi-dong-by-yuexiwen/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

# 543. 二叉树的直径 #

只要对每一个结点求出其左右子树深度之和，这个值作为一个候选值，然后再对左右子结点分别调用求直径对递归函数，这三个值相互比较，取最大的值更新结果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:
    int res = 0;
    public:
        int maxDepth(TreeNode* root)
        {
        
            if(root==NULL)return 0;
            return max( maxDepth( root->left),maxDepth( root->right) )+1;
        }
        void maxValue(TreeNode* root)
        {
        
            if(root==NULL)return;
            res = max(res, maxDepth(root->left)+maxDepth(root->right) );
            maxValue(root->left);
            maxValue(root->right);
        }
        int diameterOfBinaryTree(TreeNode* root) {
        
            maxValue(root);
            return res;
        }
    };

# 547. 朋友圈（并查集） #

## 并查集 https://blog.csdn.net/zjy\_code/article/details/80634149 ##

1.  初始化:初始的时候每个结点各自为一个集合,father\[i\]表示结点 i 的父亲结点,如果 father\[i\]=i,我们认为这个结点是当前集合根结点。

void init() {
        
        for (int i = 1; i <= n; ++i) {
        
            father[i] = i;
        }
    }

1.  查找:查找结点所在集合的根结点,结点 x 的根结点必然也是其父亲结点的根结点。

int get(int x) {
        
        if (father[x] == x) {
         // x 结点就是根结点
            return x; 
        }
        return get(father[x]); // 返回父结点的根结点
    }

1.  合并:将两个元素所在的集合合并在一起,通常来说,合并之前先判断两个元素是否属于同一集合。

void merge(int x, int y) {
        
        x = get(x);
        y = get(y);
        if (x != y) {
         // 不在同一个集合
            father[y] = x;
        }
    }

路径压缩

int get(int x) {
        
        if (father[x] == x) {
         // x 结点就是根结点
            return x; 
        }
        return father[x] = get(father[x]); // 返回父结点的根结点，并另当前结点父结点直接为根结点
    }

————————————————  
版权声明：本文为CSDN博主「zjy\_code」的原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接及本声明。  
原文链接：https://blog.csdn.net/zjy\_code/article/details/80634149  
不管是大侠问题还是朋友圈问题，这类问题都用并查集模板来实现，本来想维护一个set，但是很容易陷到无限循环的陷阱中  
并查集模板

struct DSU
    {
        
        std::vector<int> data;
        
        void init(int n) {
         data.assign(n, -1); }
        
        bool unionSet(int x, int y)
        {
        
            x = root(x);
            y = root(y);
            if (x != y)
            {
        
                if (data[y] < data[x])
                {
        
                    std::swap(x, y);
                }
                data[x] += data[y];
                data[y] = x;
            }
            return x != y;
        }
    
        bool same(int x, int y) {
         return root(x) == root(y); }
    
        int root(int x) {
         return data[x] < 0 ? x : data[x] = root(data[x]); }
    
        int size(int x) {
         return -data[root(x)]; }
    };
    class Solution {
        
    public:
        int findCircleNum(vector<vector<int>>& M) 
        {
        
            int ans = M.size();
            DSU dsu;
            dsu.init(M.size());
            for (size_t i = 0; i < M.size(); i++)
            {
        
                for (size_t j = i + 1; j < M.size(); j++)
                {
        
                    if (M[i][j] == 0) continue;
                    ans -= dsu.unionSet(i, j);
                }
            }
            return ans;
        }
    };
    
    作者：ikaruga
    链接：https://leetcode-cn.com/problems/friend-circles/solution/547-by-ikaruga/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
    作者：ikaruga
    链接：https://leetcode-cn.com/problems/friend-circles/solution/547-by-ikaruga/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

很好的解答

/*
    参考思想如下：https://blog.csdn.net/qq_41593380/article/details/81146850
    参考了两份C++实现，改进以后形成以下代码
    */
    class Solution {
        
    public:
        int father[210];
        //查找祖先节点，当节点记录的祖先是自己，则表示查找到祖先了
        int findFather(int x)
        {
        
            while(x!=father[x])
            {
        
                x = father[x];
            }
            return x;
        }
        //合并节点：设置共同祖先
        void Union(int a,int b)
        {
        
            int fa = findFather(a);
            int fb = findFather(b);
            if(fa!=fb)
            {
        
                father[fa] = fb;
            }
        }
        //最开始的时候，每个节点时分散的，都是自己的祖先
        void init()
        {
        
            for(int i=0;i<210;i++)
            {
        
                father[i] = i;
            }
        }
        //主函数
        int findCircleNum(vector<vector<int>>& M) {
        
            init();
            //对N个学生两两做判断
            for(int i=0;i<M.size();i++)
            {
        
                for(int j=i+1;j<M.size();j++) //只遍历少半个矩阵
                {
        
                    if(M[i][j]==1)
                    {
        
                        Union(i,j); //对有关系的进行合并，使其为同一个父节点
                    }
                }
            }
            //一次遍历找到所有祖先节点，即为朋友圈的个数
            int res = 0;
            for(int i=0;i<M.size();i++)
            {
        
                if(i==father[i])
                {
        
                    res++;
                }
            }
            return res;
        }
    };
    
    作者：zhang-zhe
    链接：https://leetcode-cn.com/problems/friend-circles/solution/c-bing-cha-ji-shi-xian-by-zhang-zhe/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

# 560. 和为K的子数组 #

这道题用哈希实现是太简单了，用新的数组不仅复杂还容易出错。不要用数组去储存前n项和，而是储存在哈希表里，因为这样还能保存次数。虽然子串要求顺序，，但是这和就是连续求的并不影响。  
用一个哈希表来建立连续子数组之和跟其出现次数之间的映射，初始化要加入\{0,1\}这对映射，这是为啥呢，因为我们的解题思路是遍历数组中的数字，用sum来记录到当前位置的累加和，我们建立哈希表的目的是为了让我们可以快速的查找sum-k是否存在，即是否有连续子数组的和为sum-k，如果存在的话，那么和为k的子数组一定也存在，这样当sum刚好为k的时候，那么数组从起始到当前位置的这段子数组的和就是k，满足题意，如果哈希表中事先没有m\[0\]项的话，这个符合题意的结果就无法累加到结果res中，这就是初始化的用途。  
————————————————  
版权声明：本文为CSDN博主「pushup8」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。  
原文链接：https://blog.csdn.net/pushup8/article/details/85341207

class Solution {
        
    public:
        int subarraySum(vector<int>& nums, int k) {
        
            int sum = 0, ans = 0;
            unordered_map<int,int> mp;
            mp[0] = 1;
            for(int i: nums){
        
                sum += i;
                if(mp.find(sum-k) != mp.end()) ans += mp[sum-k];
                mp[sum] ++;
            }
            return ans;
        }
    };
    
    作者：jarvis1890
    链接：https://leetcode-cn.com/problems/subarray-sum-equals-k/solution/qian-zhui-he-shi-xian-jian-dan-by-jarvis1890/
    来源：力扣（LeetCode）
    著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

# 564. 寻找最近的回文数 #

如果数组的字符串长度 == 1，数字n - 1  
开头为1，9**9为一个候选答案 例：100000，答案为99999  
开头为9, 10**01为一个候选答案 例：99999，答案为100001  
如果本身对称，则把最中间的一个（或两个）位数减（如果0则加）一  
例：123321，答案为122221  
例：120021，答案为121121  
如果不对称：  
把前半部分逆序替换掉后半部分 例：1223，答案为1221  
把最中间的一个（或两个）位数加一 例：1283，答案为1331，而非1221  
把最中间的一个（或两个）位数减一 例：1800，答案为1771，而非1881

# 567. 字符串的排列 #

class Solution {
        
    public:
        bool checkInclusion(string s1, string s2) {
        
            unordered_map<char,int> mp1,window;
            for(auto s:s1)mp1[s]++;
            for(int i = 0;i< s2.size() ;i++)
            {
        
                if(i<s1.size())
                {
        window[s2[i]]++;}
                else
                {
                      
                    window[s2[i]]++;
                    if(window[s2[i-s1.size()]]>1)
                    {
        window[s2[i-s1.size()]]--;}
                    else window.erase(s2[i-s1.size()]);
                }
                if(window==mp1)return true;
            }
            return false;
        }
    };

# 572. 另一个树的子树 #

里面有两个值得注意的地方，一个是使用||优化单个节点位空的情况，一个是主递归里必须判断s是否为0，虽然到负递归里不会出错，但是主递归里涉及到了s的子节点所以必须判断

/**
     * 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:
        bool isequal(TreeNode* root1,TreeNode* root2)
        {
        
            if(root1==NULL && root2==NULL)return true;
            //if(root1!= NULL && root2==NULL)return false;
            //if(root1==NULL && root2!=NULL)return false;
            if(root1==NULL || root2==NULL)return false;
            if(root1->val != root2->val)return false;
            return isequal(root1->left,root2->left) && isequal(root1->right,root2->right);
        }
    
        bool isSubtree(TreeNode* s, TreeNode* t) {
        
            if(s==NULL)return false;
            if( isequal(s,t)==true )return true;
            return isSubtree(s->left,t) || isSubtree(s->right,t);
        }
    };

# 576. 出界的路径数 #

超时，但是道理时正确的

class Solution {
        
    int res;
    public:
        void dfs(int m, int n, int N,vector<vector<int>> M, int i, int j,int num)
        {
        
            if(num>N)return;//当步数已经大于N就失效了
            if(  (i<0 || i>=m || j<0 || j>= n) && num<=N ) {
        res++;return;}//到达边界而且满足要求的
            dfs(m,n,N,M,i+1,j,num+1);
            dfs(m,n,N,M,i-1,j,num+1);
            dfs(m,n,N,M,i,j+1,num+1);
            dfs(m,n,N,M,i,j-1,num+1);
        }
    
        int findPaths(int m, int n, int N, int i, int j) {
        
            vector<vector<int>> M(m, vector<int>(n,1));
            int num=0;
            dfs(m,n,N,M,i,j,num);
            return res;
        }
    };

# 583. 两个字符串的删除操作 #

class Solution {
        
    public:
        int minDistance(string word1, string word2) {
        
            int len1 = word1.size();
            int len2 = word2.size();
            vector<vector<int>> dp(len1+1,vector<int>(len2+1,0));
            for(int i =1 ;i<=len1 ;i++)
            {
        
                for(int j =1 ;j <=len2 ;j++)
                {
        
                    if(word1[i-1]==word2[j-1])
                    {
        dp[i][j] = dp[i-1][j-1] + 1;}
                    else
                    {
        dp[i][j] = max(dp[i-1][j],dp[i][j-1]);}
                }
            }
            return len1+len2-2*dp[len1][len2];
        }
    };

# 594. 最长和谐子序列(哈希) #

class Solution {
        
    public:
        int findLHS(vector<int>& nums) {
        
            unordered_map<int,int> mp;
            for(auto num:nums)
            {
        
                if(mp.find(num)!=mp.end())mp[num]++;
                else mp[num]=1;
            }
            int res=0;
            set<int> st(nums.begin(),nums.end());
            for(auto num:st)
            {
        
                if(mp.find(num-1)!=mp.end())
                {
        res = max(res,mp[num]+mp[num-1]);}
                if(mp.find(num+1)!=mp.end())
                {
        res= max(res, mp[num]+mp[num+1]);}
            }
            return res;
        }
    };