1339. Maximum Product of Splitted Binary Tree

解题思路：根据题目描述，找出删除一条边之后两棵二叉树的最大乘积。两棵二叉树的最大乘积应该是差值最小的两棵树，所以解题需要知道以每一个节点为根的二叉树的和，所以解题主要分三步：

• 更新树节点为以此节点为根的二叉树的节点和
• 找出差值最小的两棵二叉树的和
• 返回答案

时间复杂度：O(n) / 空间复杂度：O(1)

/**
 * 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 sumNode(TreeNode* node){
        if(node == nullptr){
            return 0;
        }
        node->val += sumNode(node->left) + sumNode(node->right);
        return node->val;
    }
    void traverse(TreeNode* node, int& num, int& curDiff, int sum){
        if(node == nullptr){
            return;
        }
        if(abs(node->val - (sum - node->val)) < curDiff){
            curDiff = abs(node->val - (sum - node->val));
            num = node->val;
        }
        traverse(node->left, num, curDiff, sum);
        traverse(node->right, num, curDiff, sum);
        return;
    }
    int maxProduct(TreeNode* root) {
        int treeSum = sumNode(root);
        int curDiff = INT_MAX;
        int num = 0;
        traverse(root, num, curDiff, treeSum);
        // std::cout << "num: " << num << std::endl;
        return ((long)num * (long)(treeSum - num)) % 1000000007;
    }
};

1338. Reduce Array Size to The Half

解题思路：题目要求是找出最少的元素，使得删除该元素之后的数组的数量顶多为原来的一半，用另外的一种解释就是删除出先次数最多的元素，使数组长度为原来的一半。

解题使用两个数据结构，

• 一个map，统计同一个元素出现的次数
• 一个priority_queue，依次找出出现次数最多的元素

时间复杂度：O(n) / 空间复杂度：O(n)

class Solution {
public:
    int minSetSize(vector<int>& arr) {
        priority_queue<int> pq;
        unordered_map<int, int> dict;
        for(auto a : arr){
            ++dict[a];
        }
        
        for(auto d : dict){
            pq.push(d.second);
        }
        int cnt = 0, size = arr.size(), halfSize = arr.size() / 2;
        while(!pq.empty()){
            ++cnt;
            size -= pq.top();
            if(size <= halfSize){
                return cnt;
            }
            pq.pop();
        }
        return cnt;
    }
};

1337. The K Weakest Rows in a Matrix

解题思路：返回前k个最弱的行(即士兵最少的行)，解题很直观，统计每行士兵的个数并连同索引加入堆中，重写排序函数，然后从堆中找出前k个元素即可。

时间复杂度：O(n) / 空间复杂度：O(1)

class Solution {
public:
    struct compare{
        bool operator()(const pair<int, int>& l, const pair<int, int>& r){
            if(l.first == r.first){
                return l.second > r.second;
            }
            return l.first > r.first;
        }
    };
    vector<int> kWeakestRows(vector<vector<int>>& mat, int k) {
        priority_queue<pair<int, int>, std::vector<pair<int, int>>, compare> pq;
        for(int i = 0; i < mat.size(); ++i){
            int cnt = 0;
            for(int j = 0; j < mat[i].size(); ++j){
                cnt += mat[i][j];
            }
            pq.push({cnt, i});
        }
        vector<int> ret;
        while(k > 0){
            ret.push_back(pq.top().second);
            pq.pop();
            --k;
        }
        return ret;
    }
};

1332. Remove Palindromic Subsequences

解题思路：一道字符串的题目，有三种情况：

• 字符串为空，返回0
• 字符串为回文串，返回1
• 其他情况返回2

时间复杂度：O(1) / 空间复杂度：O(1)

class Solution {
public:
    int removePalindromeSub(string s) {
        return 2 - (s == string(s.rbegin(), s.rend())) - s.empty();
    }
};

1331. Rank Transform of an Array

解题思路：本题求一个数组中各个元素的排序作，主要分为以下几步：

• 开辟另外一块内存对原数组排序，原数组在这一步保持不变
• 对排序好的数组依次遍历放入一个 unordered_map 中
• 遍历原数组，按值将索引作为值一次更新，然后返回

时间复杂度：O(nlogn) / 空间复杂度：O(n)

class Solution {
public:
    vector<int> arrayRankTransform(vector<int>& arr) {
        vector<int> A(arr);
        sort(A.begin(), A.end());
        unordered_map<int, int> rank;
        for(auto a : A){
            rank.emplace(a, rank.size() + 1);
        }
        for(auto& a : arr){
            a = rank[a];
        }
        return arr;
    }
};

41. First Missing Positive

解题思路：数组没有排序，返回第一个丢掉的正整数。遍历数组，通过不断的交换，将数组排序，然后通过再次遍历，找到答案并返回。

时间复杂度：O(n) / 空间复杂度：O(1)

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        for(int i = 0; i < nums.size(); ++i){
            while(nums[i] > 0 && nums[i] <= nums.size() && nums[nums[i] - 1] != nums[i]){
                swap(nums[nums[i] - 1], nums[i]);
            }
        }
        for(int i = 0; i < nums.size(); ++i){
            if(nums[i] != i + 1){
                return i + 1;
            }
        }
        return nums.size() + 1;
    }
};

76. Minimum Window Substring

解题思路：leetcode的经典滑动窗口题目，也是面试高频题。给出了两个字符串S, T，找出在S中包含T的最小子串，顺序随意。

分配两个数组(长度为128，这是ASCII码的长度，因为题目并没有说都是字母)

• 一个保存字符串T的所有字符
• 一个保存字符串S中，当前滑动窗口中的所有字符

在对字符串S进行遍历的时候根据与T中的字符串进行比较做相应的处理：

• 如果当前滑动窗口中包含T中的所有字符
  • 如果当前滑动窗口最小，则更新返回值
  • 将rear指针前移并更新当前滑动窗口中的字符
• 如果当前滑动窗口不包含T中的所有字符，将front指针前移，更新窗口中的字符

时间复杂度：O(m + n) / 空间复杂度：O(1) 算法分配的空间固定

class Solution {
public:
    bool isInclude(vector<int>& coll, vector<int>& dict){
        for(int i = 0; i < coll.size(); ++i){
            if(coll[i] < dict[i]) {
                return false;
            }
        }
        return true;
    }
    
    string minWindow(string s, string t) {
        vector<int> dict(128, 0);
        vector<int> coll(128, 0);
        for(auto ch : t){
            ++dict[ch];
        }
        int front = 0, rear = 0;
        int cur_len = INT_MAX;
        string min_substr;
        while(front <= s.size() && rear <= front){
            if(isInclude(coll, dict)){
                if(front - rear < cur_len){
                    cur_len = front - rear;
                    min_substr = s.substr(rear, front - rear);
                }
                --coll[s[rear]];
                ++rear;
            } else if(front != s.size()){
                ++coll[s[front]];
                ++front;
            } else {
                break;
            }
        }
        return min_substr;
    }
};

1007. Minimum Domino Rotations For Equal Row

解题思路：一道筛子的题目，要求使用最少的交换次数使得上下两个筛子的数字都相同，归纳起来是一道数组配合数据结构的题目。

主要使用三个map来存储相应的信息

• 两个数组的值分别对应的坐标集合
• 两个数组的相同的值对应的坐标，这个是不同的坐标

遍历两个数组，将值与下标索引存入三个map中，然后处理三个数组

如果一个值在两个数组中的下标索引与数组长度相同，则可以得到答案，如果没有这样的值则返回-1

注意，如果两个筛子的值可以通过变换变成一致那么只可能有一种答案。

时间复杂度：O(n) / 空间复杂度：O(1)

class Solution {
public:
    int minDominoRotations(vector<int>& A, vector<int>& B) {
        if(A.size() != B.size()){
            return -1;
        }
        const int size = A.size();
        map<int, int> val_cnt_a;
        map<int, int> val_cnt_b;
        map<int, set<int>> dict;
        for(int i = 0; i < size; ++i){
            dict[A[i]].insert(i);
            dict[B[i]].insert(i);
            ++val_cnt_a[A[i]];
            ++val_cnt_b[B[i]];
        }
        for(auto& d : dict){
            if(d.second.size() == size){
                int common = val_cnt_a[d.first] + val_cnt_b[d.first] - size;
                return min(val_cnt_a[d.first] - common, val_cnt_b[d.first] - common);
            }
        }
        return -1;
    }
};

1325. Delete Leaves With a Given Value

解题思路：删除一个二叉树中值为target的叶节点，当一个节点删除左右孩子变成叶节点之后符合条件也要删除。这是一道典型的二叉树采用分治策略的题目，但是函数的构造使用的是递归的思路，主要分为三个部分：

• 第一部分为返回值
• 第二部分分别求当前节点的左右子树
• 第三部分判断该节点是否符合删除条件

时间复杂度：O(n) / 空间复杂度：O(1)

/**
 * 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* removeLeafNodes(TreeNode* root, int target) {
        if(root == nullptr){
            return nullptr;
        }
        root->left = removeLeafNodes(root->left, target);
        root->right = removeLeafNodes(root->right, target);
        if(root->left == nullptr && root->right == nullptr && root->val == target){
            return nullptr;
        }
        return root;
    }
};

1324. Print Words Vertically

解题思路：字符串处理，将给定的一个字符串按照空格分解成独立的子串，然后将子串的字符按照竖直位置组成新串输出。几个注意事项，独立子串的长度并不一致，所以有的答案会有前置的空格，但后置的空格需要处理掉。

时间复杂度：O(n) / 空间复杂度：O(1)

class Solution {
public:
    vector<string> printVertically(string s) {
        int start = 0;
        int len = 0;
        vector<string> strVec;
        for(int i = 0; i <= s.size(); ++i){
            if(i == s.size() || s[i] == ' '){
                string sub = s.substr(start, i - start);
                len = max(len, i - start);
                strVec.push_back(sub);
                start = i + 1;
            }
        }
        vector<string> ans;
        for(int i = 1; i <= len; ++i){
            string str;
            for(int j = 0; j < strVec.size(); ++j){
                if(strVec[j].size() < i){
                    str.push_back(' ');
                } else {
                    str.push_back(strVec[j][i - 1]);
                }
            }
            while(str.back() == ' '){
                str.pop_back();
            }
            ans.push_back(str);
        }
        return ans;
    }
};