LeetCode HOT 100 --- 2021/7/30

我不是女神ヾ 2022-09-02 05:17 148阅读 0赞

### 目录 ###

*  在排序数组中查找元素的第一个和最后一个位置
 *  组合总和
 *  全排列
 *  旋转图像
 *  字母异位词分组
 *  跳跃游戏
 *  合并区间

# 在排序数组中查找元素的第一个和最后一个位置 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70]  
分析：  
  二分查找：一旦查找到target，就从该位置开始向两边扩张，找到边界。  
代码：

class Solution { 
    public:
        vector<int> searchRange(vector<int>& nums, int target) { 
            if(nums.size() == 0) { 
                return { -1, -1};
            }
            if(nums.size() == 1 && nums[0] == target) { 
                return { 0, 0};
            }
            int n = nums.size();
            int l = 0, r = n - 1;
            while(l <= r) { 
                int mid = l + (r - l) / 2;
                if(nums[mid] == target) { 
                    int i = mid, j = mid;
                    while(i >= 0 && nums[i] == target) { 
                        i--;
                    }
                    while(j < n && nums[j] == target) { 
                        j++;
                    }
                    return { i + 1, j - 1};
                }else if(nums[mid] > target) { 
                    r = mid - 1;
                }else { 
                    l = mid + 1;
                }
            }
            return { -1, -1};
        }
    };

# 组合总和 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 1]  
分析：  
  dfs+回溯：每次可以选择跳过当前位置，也可以重复选择当前位置。  
代码：

class Solution { 
    public:
        void dfs(vector<int>& candidates, int target, vector<vector<int>>& res, vector<int>& cur, int ind) { 
            if(ind == candidates.size()) { 
                return;
            }
            if(target == 0) { 
                res.push_back(cur);
                return;
            }
            dfs(candidates, target, res, cur, ind + 1);
            if(target - candidates[ind] >= 0) { 
                cur.push_back(candidates[ind]);
                target -= candidates[ind];
                dfs(candidates, target, res, cur, ind);
                target += candidates[ind];
                cur.pop_back();
            }
        }
        
        vector<vector<int>> combinationSum(vector<int>& candidates, int target) { 
            vector<vector<int>> res;
            vector<int> cur;
            dfs(candidates, target, res, cur, 0);
            return res;
        }
    };

# 全排列 #

[全排列][Link 1]

# 旋转图像 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 2]  
分析：  
  原数组中的(row, col)旋转后，在新数组中的位置为(col, n - row - 1)。  
代码：

class Solution { 
    public:
        void rotate(vector<vector<int>>& matrix) { 
            int n = matrix.size();
            vector<vector<int>> temp(n, vector<int>(n));
            for(int row = 0; row < n; row++) { 
                for(int col = 0; col < n; col++) { 
                    temp[col][n - row - 1] = matrix[row][col];
                }
            }
            for(int row = 0; row < n; row++) { 
                for(int col = 0; col < n; col++) { 
                    matrix[row][col] = temp[row][col];
                }
            }
        }
    };

# 字母异位词分组 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 3]  
分析：  
  对原字符串数组中的每一个字符串进行排序，如果两个字符串是字母异位词，则排序后二者相同。基于这种性质，可以使用哈希表进行存储。  
代码：

class Solution { 
    public:
        vector<vector<string>> groupAnagrams(vector<string>& strs) { 
            vector<vector<string>> res;
            if(strs.size() == 0) { 
                res.push_back({ });
                res[0].push_back("");
                return res;
            }
            //排序+哈希表
            unordered_map<string, vector<string>> mp;
            vector<string> temp;
            for(int i = 0; i < strs.size(); i++) { 
                if(strs[i] == "") { 
                    mp[""].push_back("");
                    continue;
                }
                string s = strs[i];
                sort(s.begin(), s.end());
                mp[s].push_back(strs[i]);
            }
            unordered_map<string, vector<string>>::iterator it = mp.begin();
            for(; it != mp.end(); ++it) { 
                res.push_back(it->second);
            }
            return res;
        }
    };

# 跳跃游戏 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 4]  
分析：  
  贪心算法：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 5]  
代码：

class Solution { 
    public:
        bool canJump(vector<int>& nums) { 
            int n = nums.size();
            int rightmost = 0;
            for(int i = 0; i < n; i++) { 
                if(i <= rightmost) { 
                    rightmost = max(rightmost, i + nums[i]);
                    if(rightmost >= n - 1) { 
                        return true;
                    }
                }
            }
            return false;
        }
    };

# 合并区间 #

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 6]  
分析：  
  将原数组按照左边界升序的原则进行排序，排序后可合并的区间一定是连续的。令结果数组为res，遍历排序后的数组，如果当前res为空，那么应该将当前区间加入；如果res中最后一个区间的右边界小于当前区间的左边界，那么当前区间显然是不能和res中最后一个区间合并的，单独加入；否则就能合并，由于是按照左边界升序排列，所以只需要将res中最后一个区间的右边界进行更新即可。  
代码：

class Solution { 
    public:
        vector<vector<int>> merge(vector<vector<int>>& intervals) { 
            vector<vector<int>> res;
            sort(intervals.begin(), intervals.end());
            int n = intervals.size();
            for(int i = 0; i < n; i++) { 
                if(res.size() == 0 || res.back()[1] < intervals[i][0]) { 
                    res.push_back(intervals[i]);
                }else { 
                    res.back()[1] = max(res.back()[1], intervals[i][1]);
                }
            }
            return res;
        }
    };

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70]: /images/20220829/d60beafe493a4d5fa51173e0818a0122.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 1]: /images/20220829/38fd84eee75849ff95d2176ae80da416.png
[Link 1]: https://blog.csdn.net/Cyril_KI/article/details/118853036
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 2]: /images/20220829/465e138f920d4233ac1cff8d437f3845.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 3]: /images/20220829/52b255a824bc4f22bc230ff96f74eed5.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 4]: /images/20220829/ed65ca2d60964c358c2b66e9ca4c78c3.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 5]: /images/20220829/7dd9701a2a50443d86fec20dab2892b4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L0N5cmlsX0tJ_size_16_color_FFFFFF_t_70 6]: /images/20220829/83bfbfa313a74e7185c201813b28eb89.png