leetcode解题思路分析（五十八）494 - 500 题

水深无声 2023-01-04 14:45 140阅读 0赞

1.  目标和  
    给定一个非负整数数组，a1, a2, …, an, 和一个目标数，S。现在你有两个符号 + 和 -。对于数组中的任意一个整数，你都可以从 + 或 -中选择一个符号添加在前面。返回可以使最终数组和为目标数 S 的所有添加符号的方法数。

**按照题意，其实可以分为正整数子集和负整数子集，其和为总和，差值为目标和，所以2倍正整数子集即总和+目标和。因此题目转化为从数组中取一个子集满足和为二分之一的总和+目标和，即经典的01背包问题**

class Solution { 
    public:
        int findTargetSumWays(vector<int>& nums, int S) { 
            long sum = 0;
            for (const int &it : nums) sum += it;
            if ((S + sum) % 2 == 1 || S > sum) return 0;
            S = (S + sum) / 2;
            int *dp = new int[S + 1];
            memset(dp, 0, (S + 1) * sizeof(int));
            dp[0] = 1;
            for (const int &it : nums) { 
                for (int j = S; j >= it; j--)
                    dp[j] += dp[j - it];
            }
            int ans = dp[S];
            delete[] dp;
            return ans;
        }
    };

1.  提莫冲击  
    在《英雄联盟》的世界中，有一个叫 “提莫” 的英雄，他的攻击可以让敌方英雄艾希（编者注：寒冰射手）进入中毒状态。现在，给出提莫对艾希的攻击时间序列和提莫攻击的中毒持续时间，你需要输出艾希的中毒状态总时长。你可以认为提莫在给定的时间点进行攻击，并立即使艾希处于中毒状态。

**双指针滑动即可**

class Solution { 
    public:
        int findPoisonedDuration(vector<int>& timeSeries, int duration) 
        { 
            int begin = 0, end = 0, ret = 0;
            for (auto n : timeSeries)
            { 
                if (n >= end)
                { 
                    ret   += end - begin;
                    begin  = n;
                    end    = n + duration;
                }
                else
                { 
                    end = n + duration;
                }
            }
            ret += end - begin;
            return ret;
        }
    };

1.  下一个更大元素 I  
    给定两个 没有重复元素 的数组 nums1 和 nums2 ，其中nums1 是 nums2 的子集。找到 nums1 中每个元素在 nums2 中的下一个比其大的值。nums1 中数字 x 的下一个更大元素是指 x 在 nums2 中对应位置的右边的第一个比 x 大的元素。如果不存在，对应位置输出 -1 。

**用单调栈对第二个数组求解，保存在哈希表中，然后遍历第一个数组即可**

class Solution { 
    public:
        vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) { 
            unordered_map<int, int> aMap;
            stack<int> aStack;
    
            // 输出第一个比x大的数 
            for (auto num2 : nums2) { 
                while (!aStack.empty() && num2 > aStack.top()) { 
                    aMap[aStack.top()] = num2;
                    aStack.pop();
                }
                aStack.emplace(num2);
            }
    
            // 没有更大的数
            while (!aStack.empty()) { 
                aMap[aStack.top()] = -1;
                aStack.pop();
            }
    
            vector<int> ans;
            for (auto num1 : nums1)
                ans.emplace_back(aMap[num1]);
    
            return ans;
        }
    };

1.  非重叠矩形中的随机点  
    给定一个非重叠轴对齐矩形的列表 rects，写一个函数 pick 随机均匀地选取矩形覆盖的空间中的整数点。

**二分法的典型应用**

class Solution { 
    public:
    
        vector<vector<int>> rects;
        vector<int> psum;
        int tot = 0;
        //c++11 random integer generation
        mt19937 rng{ random_device{ }()};
        uniform_int_distribution<int> uni;
    
        Solution(vector<vector<int>> rects) { 
            this->rects = rects;
            for (auto& x : rects) { 
                tot += (x[2] - x[0] + 1) * (x[3] - x[1] + 1);
                psum.push_back(tot);
            }
            uni = uniform_int_distribution<int>{ 0, tot - 1};
        }
    
        vector<int> pick() { 
            int targ = uni(rng);
    
            int lo = 0;
            int hi = rects.size() - 1;
            while (lo != hi) { 
                int mid = (lo + hi) / 2;
                if (targ >= psum[mid]) lo = mid + 1;
                else hi = mid;
            }
    
            auto& x = rects[lo];
            int width = x[2] - x[0] + 1;
            int height = x[3] - x[1] + 1;
            int base = psum[lo] - width * height;
            return { x[0] + (targ - base) % width, x[1] + (targ - base) / width};
        }
    };
    
    
    /** * Your Solution object will be instantiated and called as such: * Solution* obj = new Solution(rects); * vector<int> param_1 = obj->pick(); */

1.  对角线遍历  
    给定一个含有 M x N 个元素的矩阵（M 行，N 列），请以对角线遍历的顺序返回这个矩阵中的所有元素

**画图找规律即可，注意合并奇数行和偶数行**

class Solution { 
    public:
        vector<int> findDiagonalOrder(vector<vector<int>>& matrix) 
        { 
            vector<int> nums;
            int m = matrix.size();
            if (m == 0) return nums;
            int n = matrix[0].size();
            if (n == 0) return nums;
    
            bool bXFlag = true;
            for (int i = 0; i < m + n; i++)
            { 
                int pm = bXFlag ? m : n;
                int pn = bXFlag ? n : m;
    
                int x = (i < pm) ? i : pm - 1;
                int y = i - x;                
    
                while (x >= 0 && y < pn)
                { 
                    nums.push_back(bXFlag ? matrix[x][y] : matrix[y][x]);
                    x--;
                    y++;
                }
    
                bXFlag = !bXFlag;
            }
            return nums;
        }
    };

1.  键盘行  
    给定一个单词列表，只返回可以使用在键盘同一行的字母打印出来的单词。键盘如下图所示。

**初始化函数处理键盘的行，存入哈希表，然后遍历words，对于不满足的不需要检测完，直接break即可，满足的push\_back**

class Solution { 
        unordered_map<char, int> m_map;
    public:
        vector<string> findWords(vector<string>& words) 
        {        
            init();
    
            vector<string> ret;
            bool accept = true;
    
            for (auto& word : words) 
            { 
                int line = m_map[word[0]];
                accept = true;
                for (auto c : word) 
                { 
                    if (line != m_map[c])
                    { 
                        accept = false;
                        break;
                    }
                }
    
                if (accept) 
                { 
                    ret.push_back(word);
                }
            }
            return ret;
        }
    private:
    
        void init()
        { 
            string s0 = "qwertyuiop";
            string s1 = "asdfghjkl";
            string s2 = "zxcvbnm";
    
            setVal(s0, 0);
            setVal(s1, 1);
            setVal(s2, 2);
        }
    
        void setVal(string s, int val)
        { 
            for (auto c : s)
            { 
                m_map[c]      = val;
                m_map[c - 32] = val;
            }
        }
    };

1.  二叉搜索树中的众数  
    给定一个有相同值的二叉搜索树（BST），找出 BST 中的所有众数（出现频率最高的元素）。

**二叉搜索树遍历一遍，然后记录当前最大count，如果一样大则加入结果集，如果更大则清空结果集并填入新的。遍历可以用普通的中序遍历，但是如果想要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 base, count, maxCount;
        vector<int> answer;
    
        void update(int x) { 
            if (x == base) { 
                ++count;
            } else { 
                count = 1;
                base = x;
            }
            if (count == maxCount) { 
                answer.push_back(base);
            }
            if (count > maxCount) { 
                maxCount = count;
                answer = vector<int> { base};
            }
        }
    
        vector<int> findMode(TreeNode* root) { 
            TreeNode *cur = root, *pre = nullptr;
            while (cur) { 
                if (!cur->left) { 
                    update(cur->val);
                    cur = cur->right;
                    continue;
                }
                pre = cur->left;
                while (pre->right && pre->right != cur) { 
                    pre = pre->right;
                }
                if (!pre->right) { 
                    pre->right = cur;
                    cur = cur->left;
                } else { 
                    pre->right = nullptr;
                    update(cur->val);
                    cur = cur->right;
                }
            }
            return answer;
        }
    };