leetcode解题思路分析（七十四）652 - 659 题

谁借莪１个温暖的怀抱￠ 2023-01-17 14:54 88阅读 0赞

1.  寻找重复的子树  
    给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。两棵树重复是指它们具有相同的结构以及相同的结点值。

/** * 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 { 
    private:
        // 结果的存储
        vector<TreeNode*> res;
        // 子树的编号，从1开始，用0表示是无效，后续递增来保证唯一
        int index = 1;
        // 子树 val,left,right的字符串 到唯一编号的映射
        unordered_map<string, int> str2index;
        // 唯一编号 到 数量的映射
        unordered_map<int, int> index2cnt;
    
        // 返回值为 当前节点对应的 唯一编号
        int dfs(TreeNode* curr)
        { 
            // 节点为空，返回0表示是无效
            if(!curr)
                return 0;
            string currStr = to_string(curr->val) + "," + to_string(dfs(curr->left)) + "," + to_string(dfs(curr->right));
            // 遇到了新的子树结构，就设立新的元组-编号映射
            if (str2index.find(currStr) == str2index.end())
            { 
                str2index[currStr] = index;
                // 编号被使用，自增一个新的
                ++index;
            }
            // 获取当前子树结构的编号
            int index = str2index[currStr];
            // 编号对应的数量加1
            ++index2cnt[index];
            // 首次发现重复，增加结果里，之后的重复不再需要被记录
            if (index2cnt[index] == 2)
            { 
                res.push_back(curr);
            }
            return index;
        }
    
    public:
        vector<TreeNode*> findDuplicateSubtrees(TreeNode* root) { 
            dfs(root);
            return res;
        }
    };

1.  两数之和  
    给定一个二叉搜索树和一个目标结果，如果 BST 中存在两个元素且它们的和等于给定的目标结果，则返回 true。

**二叉搜索树的一个特性就是已完成排序，所以中序遍历后直接指针滑动即可。**

1.  最大二叉树  
    返回有给定数组 nums 构建的 最大二叉树 。

**二分找最大值，然后左右区间递归即可**

class Solution { 
    public:
        //主函数
        TreeNode* constructMaximumBinaryTree(vector<int>& nums) { 
            return construct(nums,0,nums.size()-1);
        }
    
        /* 将 nums[lo..hi] 构造成符合条件的树，返回根节点 */
        TreeNode* construct(vector<int>& nums,int lo,int hi){ 
            if(lo>hi) return NULL;
    
            // 找到数组中的最大值和对应的索引
            int index=-1,maxVal=-9999;
            for(int i=lo;i<=hi;i++){ 
                if(nums[i]>maxVal){ 
                    index=i;
                    maxVal=nums[i];
                }
            }
    
            auto root=new TreeNode(maxVal);
            // 递归调用构造左右子树
            root->left=construct(nums,lo,index-1);
            root->right=construct(nums,index+1,hi);
    
            return root;
        }
    };

1.  输出二叉树  
    在一个 m\*n 的二维字符串数组中输出二叉树

**比较特殊得输出方式而已，没有本质区别**

/** * 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) {} * }; */
    /** * 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 depth(TreeNode* root){ 
            return root == NULL? -1 : max(depth(root->left), depth(root->right)) + 1;
        }
        vector<vector<string>> printTree(TreeNode* root) { 
            if(root == NULL){ 
                vector<vector<string>> ans;
                return ans;
            }
            int m = depth(root) + 1;
    
            int two[11];    //two[i]：储存2的i次方
            two[0] = 1;
            for(int i = 1; i <= 10; i++){ 
                two[i] = two[i - 1] * 2;
            }
    
            int n = two[m] - 1;
    
            //将树用数组 arr [2 * m] 储存，无需递归，打印时更加直观
            vector<TreeNode*> arr(two[m], nullptr);
            arr[1] = root;
            for(int i = 1; i < two[m - 1]; i++){ 
                if(arr[i] != NULL){ 
                    arr[2 * i] = arr[i]->left;
                    arr[2 * i + 1] = arr[i]->right;
                }
            }
    
            vector<vector<string>> ans(m, vector<string>(n, ""));
            for(int level = 1; level <= m; level++){ 
                int offset = two[m - level] - 1;
                for(int i = 0; i < two[level - 1]; i++){ 
                    TreeNode* temp = arr[two[level - 1] + i];
                    if(temp != NULL){ 
                        ans[level - 1][offset] = to_string(temp->val);
                    }
                    offset +=  two[m - level + 1];
                }
            }
           
            return ans;
        }
    };

1.  机器人能否返回原点  
    在二维平面上，有一个机器人从原点 (0, 0) 开始。给出它的移动顺序，判断这个机器人在完成移动后是否在 (0, 0) 处结束。

**两个flag计算即可**

class Solution { 
    public:
        bool judgeCircle(string moves) { 
            int coloum = 0, row = 0;
    
            for (auto c : moves)
            { 
                switch (c)
                { 
                case 'U':
                    coloum++;
                    break;
                
                case 'D':
                    coloum--;
                    break;
                
                case 'L':
                    row++;
                    break;
    
                case 'R':
                    row--;
                    break;
                }
            }
    
            if (!coloum && !row) 
                return true;
            else return false;
        }
    };

1.  找到K个最接近的元素  
    给定一个排序好的数组 arr ，两个整数 k 和 x ，从数组中找到最靠近 x（两数之差最小）的 k 个数。返回的结果必须要是按升序排好的。

**二分法即可**

class Solution { 
    public:
        vector<int> findClosestElements(vector<int>& arr, int k, int x) { 
            int left = 0;
            int right = arr.size() - k - 1;
            while (left <= right) { 
                int mid = left + (right - left) / 2;
                if (x - arr[mid] > arr[mid + k] - x) { 
                    left = mid + 1;
                } else { 
                    right = mid - 1;
                }
            }
    
            return vector<int>(arr.begin() + left, arr.begin() + left + k);
        }
    };

1.  分割数组为连续子序列  
    给你一个按升序排序的整数数组 num（可能包含重复数字），请你将它们分割成一个或多个长度至少为 3 的子序列，其中每个子序列都由连续整数组成。如果可以完成上述分割，则返回 true ；否则，返回 false 。

**核心思想为贪心法：尽量让子序列集中在一个里面，这样就不需要凑3个数，如果凑不到了那就是有问题了。因此需要两个哈希表，一个统计总数，一个统计每个数为结尾的子序列。然后遍历更新一次，如果更新到某一刻发现不能满足长度为3则false。**

class Solution { 
    public:
        bool isPossible(vector<int>& nums) { 
            unordered_map<int, int> countMap;
            unordered_map<int, int> endMap;
            for (auto& x : nums) { 
                int count = countMap[x] + 1;
                countMap[x] = count;
            }
            for (auto& x : nums) { 
                int count = countMap[x];
                if (count > 0) { 
                    int prevEndCount = endMap[x - 1];
                    if (prevEndCount > 0) { 
                        countMap[x] = count - 1;
                        endMap[x - 1] = prevEndCount - 1;
                        endMap[x] = endMap[x] + 1;
                    } else { 
                        int count1 = countMap[x + 1];
                        int count2 = countMap[x + 2];
                        if (count1 > 0 && count2 > 0) { 
                            countMap[x] = count - 1;
                            countMap[x + 1] = count1 - 1;
                            countMap[x + 2] = count2 - 1;
                            endMap[x + 2] = endMap[x + 2] + 1;
                        } else { 
                            return false;
                        }
                    }
                }
            }
            return true;
        }
    };