leetcode解题思路分析（六十七）566 - 572 题

野性酷女 2022-11-03 11:18 8阅读 0赞

1.  重塑矩阵  
    如果具有给定参数的reshape操作是可行且合理的，则输出新的重塑矩阵；否则，输出原始矩阵。

**没啥好说的，直接输出转换即可**

class Solution { 
    public:
        vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) { 
            int m = nums.size();
            int n = nums[0].size();
            if (m * n != r * c) { 
                return nums;
            }
    
            vector<vector<int>> ans(r, vector<int>(c));
            for (int x = 0; x < m * n; ++x) { 
                ans[x / c][x % c] = nums[x / n][x % n];
            }
            return ans;
        }
    };

1.  字符串的排列  
    给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。换句话说，第一个字符串的排列之一是第二个字符串的子串。

**我们在保证区间长度为 nn 的情况下，去考察是否存在一个区间使得 \\textit\{cnt\}cnt 的值全为 00。反过来，还可以在保证 \\textit\{cnt\}cnt 的值不为正的情况下，去考察是否存在一个区间，其长度恰好为 nn。初始时，仅统计 s\_1s 1中的字符，则 \\textit\{cnt\}cnt 的值均不为正，且元素值之和为 -n−n。然后用两个指针 \\textit\{left\}left 和 \\textit\{right\}right 表示考察的区间 \[\\textit\{left\},\\textit\{right\}\]\[left,right\]。\\textit\{right\}right 每向右移动一次，就统计一次进入区间的字符 xx。为保证 \\textit\{cnt\}cnt 的值不为正，若此时 \\textit\{cnt\}\[x\]>0cnt\[x\]>0，则向右移动左指针，减少离开区间的字符的 \\textit\{cnt\}cnt 值直到 \\textit\{cnt\}\[x\] \\le 0cnt\[x\]≤0。注意到 \[\\textit\{left\},\\textit\{right\}\]\[left,right\] 的长度每增加 11，\\textit\{cnt\}cnt 的元素值之和就增加 11。当 \[\\textit\{left\},\\textit\{right\}\]\[left,right\] 的长度恰好为 nn 时，就意味着 \\textit\{cnt\}cnt 的元素值之和为 00。由于 \\textit\{cnt\}cnt 的值不为正，元素值之和为 00 就意味着所有元素均为 00，这样我们就找到了一个目标子串**

class Solution { 
    public:
        bool checkInclusion(string s1, string s2) { 
            int n = s1.length(), m = s2.length();
            if (n > m) { 
                return false;
            }
            vector<int> cnt(26);
            for (int i = 0; i < n; ++i) { 
                --cnt[s1[i] - 'a'];
            }
            int left = 0;
            for (int right = 0; right < m; ++right) { 
                int x = s2[right] - 'a';
                ++cnt[x];
                while (cnt[x] > 0) { 
                    --cnt[s2[left] - 'a'];
                    ++left;
                }
                if (right - left + 1 == n) { 
                    return true;
                }
            }
            return false;
        }
    };

1.  另一个树的子树  
    给定两个非空二叉树 s 和 t，检验 s 中是否包含和 t 具有相同结构和节点值的子树。s 的一个子树包括 s 的一个节点和这个节点的所有子孙。s 也可以看做它自身的一棵子树。

**本题可以使用中序、前序等遍历改为字符串，然后采取KMP/BM等方法找是否存在子串。更优的做法是采取哈系树，查找是否有等值的哈希子树。**

/** * 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:
        static constexpr int MAX_N = 1000 + 5;
        static constexpr int MOD = int(1E9) + 7;
    
        bool vis[MAX_N];
        int p[MAX_N], tot;
        void getPrime() { 
            vis[0] = vis[1] = 1; tot = 0;
            for (int i = 2; i < MAX_N; ++i) { 
                if (!vis[i]) p[++tot] = i;
                for (int j = 1; j <= tot && i * p[j] < MAX_N; ++j) { 
                    vis[i * p[j]] = 1;
                    if (i % p[j] == 0) break;
                }
            }
        }
    
        struct Status { 
            int f, s; // f 为哈希值 | s 为子树大小
            Status(int f_ = 0, int s_ = 0) 
                : f(f_), s(s_) { }
        };
    
        unordered_map <TreeNode *, Status> hS, hT;
    
        void dfs(TreeNode *o, unordered_map <TreeNode *, Status> &h) { 
            h[o] = Status(o->val, 1);
            if (!o->left && !o->right) return;
            if (o->left) { 
                dfs(o->left, h);
                h[o].s += h[o->left].s;
                h[o].f = (h[o].f + (31LL * h[o->left].f * p[h[o->left].s]) % MOD) % MOD;
            }
            if (o->right) { 
                dfs(o->right, h);
                h[o].s += h[o->right].s;
                h[o].f = (h[o].f + (179LL * h[o->right].f * p[h[o->right].s]) % MOD) % MOD;
            }
        }
    
        bool isSubtree(TreeNode* s, TreeNode* t) { 
            getPrime();
            dfs(s, hS);
            dfs(t, hT);
    
            int tHash = hT[t].f;
            for (const auto &[k, v]: hS) { 
                if (v.f == tHash) { 
                    return true;
                }
            } 
    
            return false;
        }
    };

1.  分糖果  
    给定一个偶数长度的数组，其中不同的数字代表着不同种类的糖果，每一个数字代表一个糖果。你需要把这些糖果平均分给一个弟弟和一个妹妹。返回妹妹可以获得的最大糖果的种类数。

**用哈希表求解即可，但是用bitset做则更优**

class Solution { 
    public:
        int distributeCandies(vector<int>& candyType) 
        { 
            int cnt = 0, size = candyType.size();
            unordered_map<int, int> m_map;
    
            for (auto n : candyType)
            { 
                m_map[n]++;
                if (m_map[n] == 1) cnt++;
    
                if (cnt >= size / 2) return size / 2;
            }
    
            return cnt;
        }
    };
    
    class Solution { 
    public:
        int distributeCandies(vector<int>& candies) 
        { 
            bitset<200001> pool;
            
            for(int i=0; i<candies.size(); i++)
            {           
                pool.set(candies[i]+100000);
            }
            
            return min(candies.size()/2, pool.count());       
        }
    };

1.  出界的路径数  
    给定一个 m × n 的网格和一个球。球的起始坐标为 (i,j) ，你可以将球移到相邻的单元格内，或者往上、下、左、右四个方向上移动使球穿过网格边界。但是，你最多可以移动 N 次。找出可以将球移出边界的路径数量。答案可能非常大，返回 结果 mod 109 + 7 的值。

**dp\[i\]\[j\]\[k\]:表示从(i,j)出发第k步出界的路径总数，等价于从外界出发第k步走到(i,j)的路径总数**

class Solution { 
    public:
        int findPaths(int m, int n, int N, int i, int j) { 
           int MOD = 1000000007;
    	if (N == 0) {  return 0; }
    
    	vector<vector<vector<unsigned long long int>>> dp(m + 2, vector<vector<unsigned long long int>>(n + 2, vector<unsigned long long int>(N + 1, 0)));
    	for (int i = 0; i <= m + 1; i++) { 
    		dp[i][0][0] = 1;
    		dp[i][n + 1][0] = 1;
    	}
    	for (int i = 0; i <= n + 1; i++) { 
    		dp[0][i][0] = 1;
    		dp[m + 1][i][0] = 1;
    	}
    	for (int k = 1; k <= N; k++) { 
    		for (int i = 1; i <= m; i++) { 
    			for (int j = 1; j <= n; j++) { 
    				dp[i][j][k] = (dp[i - 1][j][k - 1] + dp[i + 1][j][k - 1] + \
    								dp[i][j - 1][k - 1] + dp[i][j + 1][k - 1]) % MOD;
    			}
    		}
    	}
    	int sum = 0;
    	for (int k = 1; k <= N; k++) { 
    		sum = (sum + dp[i + 1][j + 1][k]) % MOD;
    	}
    	return sum;
        }
    };

1.  最短无序连续子数组  
    给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。请你找出符合题意的 最短 子数组，并输出它的长度。

**本题要点在于找出子数组左右边界。其原理也很简单：寻找右边界：  
从前往后遍历的过程中，用max记录遍历过的最大值，如果max大于当前的nums\[i\]，说明nums\[i\]的位置不正确，属于需要排序的数组，因此将右边界更新为i，然后更新max；这样最终可以找到需要排序的数组的右边界，右边界之后的元素都大于max；  
寻找左边界：  
从后往前遍历的过程中，用min记录遍历过的最小值，如果min小于当前的nums\[j\]，说明nums\[j\]的位置不正确，应该属于需要排序的数组，因此将左边界更新为j，然后更新min；这样最终可以找到需要排序的数组的左边界，左边界之前的元素都小于min；  
（从前往后遍历和从后往前遍历两个过程可以分两次循环完成，也可以放一起完成，这样的话就有：j=len-i-1**

class Solution { 
    public:
        int findUnsortedSubarray(vector<int>& nums) { 
            int n = nums.size();
            int mn = nums[n-1], l = n;
            for (int i = n - 1; i >= 0; --i) { 
                if (nums[i] > mn) { 
                    l = i;
                }
                mn = min(nums[i], mn);
            }
            int mx = nums[0], r = 0;
            for (int i = 0; i < n; ++i) { 
                if (nums[i] < mx) { 
                    r = i;
                }
                mx = max(nums[i], mx);
            }
            return max(r - l + 1, 0);
        }
    };

1.  两个字符串的删除操作  
    给定两个单词 word1 和 word2，找到使得 word1 和 word2 相同所需的最小步数，每步可以删除任意一个字符串中的一个字符。

**本题采用动态规划求解。dp\[i\]\[j\]表示第一个的前i个和第二个的前j个相同需要最小步数，即删除数。因为仅与前一行相关，因此我们可以将二维dp降为一维，然后增加一个辅助一维数组保存前一行即可**

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