leetcode解题思路分析（六十六）559 - 565 题

小鱼儿 2022-10-31 04:16 113阅读 0赞

1.  N叉树的最大深度  
    给定一个 N 叉树，找到其最大深度。

**和二叉树并无区别，层次遍历即可，深度优先亦可**

/* // Definition for a Node. class Node { public: int val; vector<Node*> children; Node() {} Node(int _val) { val = _val; } Node(int _val, vector<Node*> _children) { val = _val; children = _children; } }; */
    
    class Solution { 
    public:
        int maxDepth(Node* root) 
        { 
            int ret = 0;
            int size = 0;
            std::queue<Node*> m_queue;
    
            if (root == NULL) return ret;
    
            m_queue.push(root);
            while (m_queue.size())
            { 
                ret++;
                size = m_queue.size();
    
                for (int i = 0; i < size; i++)
                { 
                    Node* ptr = m_queue.front();
                    m_queue.pop();
    
                    if (ptr->children.size() == 0) continue;
    
                    for (auto n : ptr->children)
                    { 
                        m_queue.push(n);
                    }
                }
            }   
    
            return ret; 
        }
    };

1.  和为k的子数组  
    给定一个整数数组和一个整数 k，你需要找到该数组中和为 k 的连续的子数组的个数。

**本题解法是在双指针滑动的基础上加上一个数组用于记忆，从而平均了时空复杂度。为了便于输出，选择哈希表作为前缀和记忆。从i到j的和可以表述为sum\[j\] - sum\[i - 1\] = k，变形为sum\[i - 1\] == sum\[j\] - k，问题转化为找到有多少个和为sum\[j\] - k即可**

class Solution { 
    public:
        int subarraySum(vector<int>& nums, int k) { 
            unordered_map<int, int> mp;
            mp[0] = 1;
            int count = 0, pre = 0;
            for (auto& x:nums) { 
                pre += x;
                if (mp.find(pre - k) != mp.end()) { 
                    count += mp[pre - k];
                }
                mp[pre]++;
            }
            return count;
        }
    };

1.  数组拆分1  
    给定长度为 2n 的整数数组 nums ，你的任务是将这些数分成 n 对, 例如 (a1, b1), (a2, b2), …, (an, bn) ，使得从 1 到 n 的 min(ai, bi) 总和最大。返回该 最大总和 。

**排序取偶数位即可**

class Solution { 
    public:
        int arrayPairSum(vector<int>& nums) 
        { 
            if (nums.size() == 0) return 0;
    
            int ret = 0;
            sort(nums.begin(), nums.end());
    
            for (int i = 0; i < nums.size(); i += 2)
            { 
                ret += nums[i];
            }
    
            return ret;
        }
    };

1.  二叉树的坡度  
    给定一个二叉树，计算 整个树 的坡度 。一个树的 节点的坡度 定义即为，该节点左子树的节点之和和右子树节点之和的 差的绝对值 。如果没有左子树的话，左子树的节点之和为 0 ；没有右子树的话也是一样。空结点的坡度是 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 { 
    public:
        int helper(TreeNode* root, int &tilt)
        { 
            if (root == NULL) return 0;
            int left = helper(root->left, tilt);
            int right = helper(root->right, tilt);
            tilt+=abs(left - right);
            return left + right + root->val;
        }
        
        int findTilt(TreeNode* root) { 
            int tilt = 0;
            helper(root, tilt);
            return tilt;
        }
    };

1.  寻找最近的回文数  
    给定一个整数 n ，你需要找到与它最近的回文数（不包括自身）。“最近的”定义为两个整数差的绝对值最小。

class Solution { 
    public:
        string nearestPalindromic(string n) { 
            // 去除前'0'
            removeLeadingZeros(n);
    
            // 特殊情况: 100...00, 100...001
            if(n.size() > 1 && n[0] == '1' && n[n.size() - 1] <= '1')
            { 
                bool isSpecial = true;
                for(int x = 1; x < n.size() - 1; ++x)
                { 
                    if(n[x] != '0')
                    { 
                        isSpecial = false;
                        break;
                    }
                }
                if(isSpecial)
                { 
                    n.erase(n.begin());
                    for(int x = 0; x < n.size(); ++x)
                        n[x] = '9';
                    return n;
                }
            }
    
            long long original = stoll(n);
    
            // 首先将前半部分复制到后半部分
            int i = 0, j = n.size() - 1;
            bool isAlreadyPalidrome = true;
    
            while(i < j)
            { 
                if(n[j] != n[i])
                { 
                    n[j] = n[i];
                    isAlreadyPalidrome = false;
                }
                ++i,--j;
            }
    
            long long diff0 = abs(stoll(n) - original);
    
            // 然后计算当前半部分 +1 后的数值, 并计算差值
            string nAdd = n;
            changeByFrontHalf(nAdd,1);
            long long diffAdd1 = abs(stoll(nAdd) - original);
    
            // 然后计算当前半部分 -1 后的差值, 并计算差值
            string nSub = n;
            changeByFrontHalf(nSub,-1);
            long long diffSub1 = abs(stoll(nSub) - original);
    
            // 如果本来就是回文数，则不包括其自身
            if(isAlreadyPalidrome)
            { 
                if(diffSub1 <= diffAdd1)
                    return nSub;
                else
                    return nAdd;
            }
            else // 否则，找出最小，若相等，则优先级为 -1,0,+1.
            { 
                if(diffSub1 <= diff0 && diffSub1 <= diffAdd1)
                    return nSub;
                if(diff0 <= diffSub1 && diff0 <= diffAdd1)
                    return n;
                else
                    return nAdd;
            }
        }
    
        void removeLeadingZeros(string& n)
        { 
            while(n.size() > 0 && n[0] == '0')
                n.erase(n.begin());
            
            if(n.size() == 0)
                n.push_back('0');
        }
    
        void changeByFrontHalf(string& n, int x)
        { 
            if(x == -1)
            { 
                for(int i = (n.size() - 1) / 2; i >= 0; --i)
                { 
                    if(n[i] != '0')
                    { 
                        n[i] -= 1;
                        removeLeadingZeros(n);
                        break;
                    }
                    else
                        n[i] = '9';
                }
            }
            else // x == 1
            { 
                for(int i = (n.size() - 1) / 2; i >= 0; --i)
                { 
                    if(n[i] != '9')
                    { 
                        n[i] += 1;
                        break;
                    }
                    else
                        n[i] = '0';
                }
    
                if(n[0] == '0')
                    n.insert(n.begin(), '1');
            }
    
            // 改变后半部分，得到回文数
            int i = 0, j = n.size() - 1;
            while(i < j)
            { 
                n[j] = n[i];
                ++i,--j;
            }
        }
    };

1.  数组嵌套  
    索引从0开始长度为N的数组A，包含0到N - 1的所有整数。找到最大的集合S并返回其大小，其中 S\[i\] = \{A\[i\], A\[A\[i\]\], A\[A\[A\[i\]\]\], … \}且遵守以下的规则。假设选择索引为i的元素A\[i\]为S的第一个元素，S的下一个元素应该是A\[A\[i\]\]，之后是A\[A\[A\[i\]\]\]… 以此类推，不断添加直到S出现重复的元素。

**暴力搜索会超时，所以在此基础上加上一个标记数组记录是否访问过即可。**

class Solution { 
    public:
        int arrayNesting(vector<int>& nums) 
        { 
            //初始化res为0，用于存放最终结果
            int res = 0;
            int N = nums.size();//nums的大小
            //定义一个bool类型的vector容器，初始化为N个true
            //表示vector内的相对应nums下标的数组元素没有重复，可以访问
            vector<bool> vistied(N,true);
            for(int i =0; i< N;i++)
            { 
                int path = 0;//用于存放当前结果
                //当vector内对应的位置的元素没有访问过时进行循环体内的操作
                while(vistied[i])
                { 
                    vistied[i] = false;//i位置的元素已经访问过，标记为false以后不能再访问
                    path += 1;
                    i = nums[i];//下一个i为题中给定的条件nums[i]
                }
                res = max(res,path);//返回当前结果与上一步结果中的最大值
            }
            return res;
        }
    };