leetcode解题思路分析（五十二）447 - 453 题

本是古典何须时尚 2022-12-26 08:24 176阅读 0赞

1.  回旋镖的数量  
    给定平面上 n 对 互不相同 的点 points ，其中 points\[i\] = \[xi, yi\] 。回旋镖 是由点 (i, j, k) 表示的元组 ，其中 i 和 j 之间的距离和 i 和 k 之间的距离相等（需要考虑元组的顺序）。返回平面上所有回旋镖的数量。

**使用哈希表存储每个点到其他点的距离，如果距离相等则可以构成。**

class Solution { 
    public:
        int numberOfBoomerangs(vector<vector<int>>& points) { 
          unordered_map<double, int> p_map;
          int count = 0;
          for (int i = 0; i < points.size(); ++i) { 
            // 记得计算下一个点前要先把哈希表清空
            p_map.clear();
            for (int j = 0; j < points.size(); ++j) { 
              double dis = sqrt(pow(points[i][0] - points[j][0], 2) + pow(points[i][1] - points[j][1], 2));
              p_map[dis]++;
              count += (p_map[dis] - 1) * 2;
            }
          }
          return count;
        }
    };

1.  找到所有数组中消失的数字  
    给定一个范围在 1 ≤ a\[i\] ≤ n ( n = 数组大小 ) 的 整型数组，数组中的元素一些出现了两次，另一些只出现一次。找到所有在 \[1, n\] 范围之间没有出现在数组中的数字。

**和前面的题目一样的做法，只要给倍数即可作为原地标记**

class Solution { 
    public:
        vector<int> findDisappearedNumbers(vector<int>& nums) { 
            int size = nums.size();      
            vector<int> ret;
    
            for (auto i : nums)
            { 
                nums[(i - 1) % size] += size;
            }
    
            for (int i = 0; i < size; i++)
            { 
                if (nums[i] <= size)
                    ret.push_back(i + 1);
            }
    
            return ret;
        }
    };

1.  序列化和反序列化二叉搜索树  
    设计一个算法来序列化和反序列化 二叉搜索树 。 对序列化/反序列化算法的工作方式没有限制。 您只需确保二叉搜索树可以序列化为字符串，并且可以将该字符串反序列化为最初的二叉搜索树。

**二叉搜索树能只够通过前序序列或后序序列构造，是因为以下两个因素：  
二叉树可以通过前序序列或后序序列和中序序列构造。  
二叉搜索树的中序序列是递增排序的序列，inorder = sorted(preorder)。  
说明我们只需要直到了前序序列或后序序列相当于我们也知道了中序序列，可以通过排序获得  
。**

/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */
     class Codec { 
    public:
    
        // Encodes a tree to a single string.
        string serialize(TreeNode* root) { 
           ostringstream ss;
           serialize(root, ss);
           return ss.str();
        }
    
        TreeNode* deserialize(string data) { 
           istringstream ss(data);
           return deserialize(ss);
        }
    
    private:
        void serialize(TreeNode* root, ostringstream& ss) { 
            if (!root) { 
                ss << "# "; // Note: cannot miss space after #, stringstream need it to work
                return;
            }
    
            ss << to_string(root->val) << " ";
            serialize(root->left, ss);
            serialize(root->right, ss);
        }
    
        TreeNode* deserialize(istringstream& ss) { 
            TreeNode* root;
            string str;
            ss >> str;
            if (str == "#") { 
                root = nullptr;
            } else { 
                root = new TreeNode(stoi(str));
                root->left = deserialize(ss);
                root->right = deserialize(ss);
            }
    
            return root;
        }
    };
    
    
    // Your Codec object will be instantiated and called as such:
    // Codec* ser = new Codec();
    // Codec* deser = new Codec();
    // string tree = ser->serialize(root);
    // TreeNode* ans = deser->deserialize(tree);
    // return ans;

1.  删除二叉搜索树中的节点  
    给定一个二叉搜索树的根节点 root 和一个值 key，删除二叉搜索树中的 key 对应的节点，并保证二叉搜索树的性质不变。返回二叉搜索树（有可能被更新）的根节点的引用。

**找不到则直接返回，找到了的话则有以下情况 1. 如果是叶子则直接删除即可。2. 如果左、右子树有一个为空，则删除接上即可。3. 如果都不为空，则将左子树放到右子树最左边下面接上，然后右子树替换上即可(除此之外，还可以用右儿子的最左叶子和要删除的节点交换，以其作为新的根节点)**

/** * 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:
        TreeNode* deleteNode(TreeNode* root, int key) { 
            if (root == nullptr) return root; // 第一种情况：没找到删除的节点，遍历到空节点直接返回了
            if (root->val == key) { 
                // 第二种情况：左右孩子都为空（叶子节点），直接删除节点， 返回NULL为根节点
                // 第三种情况：其左孩子为空，右孩子不为空，删除节点，右孩子补位 ，返回右孩子为根节点
                if (root->left == nullptr) return root->right; 
                // 第四种情况：其右孩子为空，左孩子不为空，删除节点，左孩子补位，返回左孩子为根节点
                else if (root->right == nullptr) return root->left; 
                // 第五种情况：左右孩子节点都不为空，则将删除节点的左子树放到删除节点的右子树的最左面节点的左孩子的位置
                // 并返回删除节点右孩子为新的根节点。
                else {   
                    TreeNode* cur = root->right; // 找右子树最左面的节点
                    while(cur->left != nullptr) {  
                        cur = cur->left;
                    }
                    cur->left = root->left; // 把要删除的节点（root）左子树放在cur的左孩子的位置
                    TreeNode* tmp = root;   // 把root节点保存一下，下面来删除
                    root = root->right;     // 返回旧root的右孩子作为新root
                    delete tmp;             // 释放节点内存（这里不写也可以，但C++最好手动释放一下吧）
                    return root;
                }
            }
            if (root->val > key) root->left = deleteNode(root->left, key);
            if (root->val < key) root->right = deleteNode(root->right, key);
            return root;
        }
    };

1.  根据字符出现频率排序  
    给定一个字符串，请将字符串里的字符按照出现的频率降序排列。

**如果想少用内存，则可以仅用一个哈希表计数，然后字符串原地排序。如果想更快，则可以用一个堆存储再输出**

class Solution { 
    public:
        string frequencySort(string s) { 
            unordered_map<char, int> ump;
            for (const auto &c : s) { 
                ++ump[c];
            }
            sort(s.begin(), s.end(), [&](char &a, char &b) {  return ump[a] > ump[b] || (ump[a] == ump[b] && a < b); });
            return s;
        }
    };

class Solution { 
    public:
        string frequencySort(string s) { 
            unordered_map<char, int> ump;
            for (const auto &c : s) { 
                ++ump[c];
            }
            priority_queue<pair<int, char>> pq;
            for (const auto &m : ump) { 
                pq.push({ m.second, m.first});
            }        
            string ret;
            while (!pq.empty()) { 
                auto t = pq.top(); 
                pq.pop();
                ret.append(t.first, t.second);
            }
            return ret;
        }
    };

1.  用最少数量的箭引爆气球  
    给你一个数组 points ，其中 points \[i\] = \[xstart,xend\] ，返回引爆所有气球所必须射出的最小弓箭数。

**但凡区间合并问题，都可以用贪心算法求解。可以按start或者end排序，然后遍历一遍统计即可。**

class Solution { 
    public:
        int findMinArrowShots(vector<vector<int>>& points) { 
            if (points.size() <= 1) { 
                return points.size();
            }
            sort(points.begin(), points.end(), [](const vector<int>& a, const vector<int>& b) { 
                return a[1] < b[1];
            });
    
            // 发射点设置为区间最右侧的点
            int pos = points[0][1];
            int arrows = 1;
            for (int i = 1; i < points.size(); i++) 
            { 
                auto curr = points[i];
                if (curr[0] > pos) 
                { 
                    pos = curr[1];
                    ++arrows;
                }
            }
            return arrows;
        }
    };

1.  最小移动次数使数组元素相等

**本题可用动态规划求解：先排序，然后每次根据dp\[i\] = dp\[i - 1\] + a\[i\] - a\[i - 1\]求解。 更优的做法是数学法：将除了一个元素之外的全部元素+1，等价于将该元素-1，因为我们只对元素的相对大小感兴趣。因此，该问题简化为需要进行的减法次数。显然，我们只需要将所有的数都减到最小的数即可。**

class Solution { 
    public:
        int minMoves(vector<int>& nums) { 
            int moves = 0, minimu = INT_MAX;
            for (int i = 0; i < nums.size(); i++) { 
                minimu = min(minimu, nums[i]);
            }
            for (int i = 0; i < nums.size(); i++) { 
                moves += nums[i] - minimu;
            }
            return moves;
        }
    };