LeetCode面试题集 和你一起愉快A题 （C++）（持续更新中）

阅读须知

本篇博客是根据 LeetCode101: ALeetCodeGrindingGuide(C++Version) 电子书籍整理而来的版本，参考了部分解题思路，now，一起愉快地A题吧，拿下满意的 Offer~

LeetCode 455. 分发饼干【贪心】

题目描述

有一群孩子和一堆饼干，每个孩子有一个饥饿度，每个饼干都有一个大小。每个孩子只能吃 最多一个饼干，且只有饼干的大小大于孩子的饥饿度时，这个孩子才能吃饱。求解最多有多少孩 子可以吃饱。

解题思路

贪心。对孩子饥饿度和饼干尺寸从小到大排序，然后逐一比较，满足条件就算一个孩子。

AC

class Solution {
public:
    int findContentChildren(vector<int>& g, vector<int>& s) {
        sort(g.begin(),g.end());
        sort(s.begin(),s.end());
        int i=0,j=0,cnt=0;
        while(i<g.size()&&j<s.size()){
            if(s[j]>=g[i]) ++cnt,i++,j++;
            else j++;
        }
        return cnt;
    }
};

LeetCode 135. 分发糖果【贪心】

题目描述

一群孩子站成一排，每一个孩子有自己的评分。现在需要给这些孩子发糖果，规则是如果一 个孩子的评分比自己身旁的一个孩子要高，那么这个孩子就必须得到比身旁孩子更多的糖果；所有孩子至少要有一个糖果。求解最少需要多少个糖果。

解题思路

• 把所有孩子的糖果数初始化为 1； 先从左往右遍历一遍，如果右边孩子的评分比左边的高，则右边孩子的糖果数更新为左边孩子的 糖果数加1；

• 再从右往左遍历一遍，如果左边孩子的评分比右边的高，且左边孩子当前的糖果数 不大于右边孩子的糖果数，则左边孩子的糖果数更新为右边孩子的糖果数加1。

• 通过这两次遍历， 分配的糖果就可以满足题目要求了。这里的贪心策略即为，在每次遍历中，只考虑并更新相邻一 侧的大小关系。

AC

class Solution {
public:
    int candy(vector<int>& ratings) {
        int size = ratings.size();
        if(size<2) return size;
        vector<int> v(size,1);
        //先从左到右遍历
        for(int i=0;i<size-1;i++){
            if(ratings[i+1]>ratings[i])
                v[i+1]=v[i]+1;
        }
        //再从右到左遍历
        for(int i=size-1;i>=1;i--){
            if(ratings[i-1]>ratings[i])
                v[i-1]=max(v[i-1],v[i]+1);
        }
        return accumulate(v.begin(),v.end(),0);
    }
};

LeetCode 435. 无重叠区间【贪心】

题目描述

给定多个区间，计算让这些区间互不重叠所需要移除区间的最少个数。起止相连不算重叠。

解题思路

• 在选择要保留区间时，区间的结尾十分重要：选择的区间结尾越小，余留给其它区间的空间 就越大，就越能保留更多的区间。因此，我们采取的贪心策略为，优先保留结尾小且不相交的区间。
• 具体实现方法为，先把区间按照结尾的大小进行增序排序，每次选择结尾最小且和前一个选 择的区间不重叠的区间。我们这里使用 C++ 的 Lambda，结合 std::sort() 函数进行自定义排序。
• 在样例中，排序后的数组为 [[1,2], [1,3], [2,4]]。按照我们的贪心策略，首先初始化为区间 [1,2]；由于 [1,3] 与 [1,2] 相交，我们跳过该区间；由于 [2,4] 与 [1,2] 不相交，我们将其保留。因此最终保留的区间为[[1,2],[2,4]]。

注意 需要根据实际情况判断按区间开头排序还是按区间结尾排序。

AC

class Solution {
public:
    int eraseOverlapIntervals(vector<vector<int>>& intervals) {
        if(intervals.empty()) return 0;
        int n = intervals.size();
        //按照区间结尾从小到大排序
        sort(intervals.begin(),intervals.end(),[](vector<int> a,vector<int> b){
            return a[1] < b[1];
        });
        int cnt=0,pre=intervals[0][1];
        for(int i=1;i<n;i++){
            if(intervals[i][0]<pre) ++cnt;
            else pre = intervals[i][1];
        }
        return cnt;
    }
};

LeetCode 167. 两数之和 II - 输入有序数组【玩转双指针】

题目描述

在一个增序的整数数组里找到两个数，使它们的和为给定值。已知有且只有一对解。

解题思路

• 因为数组已经排好序，我们可以采用方向相反的双指针来寻找这两个数字，一个初始指向最 小的元素，即数组最左边，向右遍历；一个初始指向最大的元素，即数组最右边，向左遍历。 如果两个指针指向元素的和等于给定值，那么它们就是我们要的结果。
• 如果两个指针指向元 素的和小于给定值，我们把左边的指针右移一位，使得当前的和增加一点。如果两个指针指向元 素的和大于给定值，我们把右边的指针左移一位，使得当前的和减少一点。
• 可以证明，对于排好序且有解的数组，双指针一定能遍历到最优解。证明方法如下：假设最 优解的两个数的位置分别是 l 和 r。我们假设在左指针在 l 左边的时候，右指针已经移动到了 r； 此时两个指针指向值的和小于给定值，因此左指针会一直右移直到到达 l。同理，如果我们假设 在右指针在 r 右边的时候，左指针已经移动到了 l；此时两个指针指向值的和大于给定值，因此 右指针会一直左移直到到达r。所以双指针在任何时候都不可能处于(l,r)之间，又因为不满足条 件时指针必须移动一个，所以最终一定会收敛在 l 和r。

AC

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int le=0,re=numbers.size()-1,sum=0;
        while(le<re){
            sum = numbers[le] + numbers[re];
            if(sum==target) break;
            else if(sum>target) --re;
            else ++le;
        }
        return vector<int>{le+1,re+1};
    }
};

LeetCode 88. MergeSortedArray(Easy)【玩转双指针】

题目描述

给定两个有序数组，把两个数组合并为一个。

解题思路

由于题目要求不借助第三个数组，合并到 nums1 上，就用尾指针，然后逐一比较，运用归并排序的思想来解答。最后判断一下 nums2 数组是否还存在元素，若存在，直接放入（因为数组是有序的）。

AC

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int pos = m+n-1;
        m-=1,n-=1;
        while(m>=0&&n>=0){
            nums1[pos--] = nums1[m] > nums2[n]? nums1[m--]:nums2[n--];
        }
        while(n>=0) nums1[pos--] = nums2[n--];
    }
};

LeetCode 142. Linked List Cycle II【快慢指针】（Floyd判圈法）

题目描述

给定一个链表，如果有环路，找出环路的开始点。

解题思路

对于链表找环路的问题，有一个通用的解法——快慢指针（Floyd判圈法）。给定两个指针， 分别命名为 slow 和 fast，起始位置在链表的开头。每次 fast 前进两步，slow 前进一步。如果 fast 可以走到尽头，那么说明没有环路；如果fast可以无限走下去，那么说明一定有环路，且一定存 在一个时刻slow和fast相遇。当slow和fast第一次相遇时，我们将fast重新移动到链表开头，并 让slow和fast每次都前进一步。当slow和fast第二次相遇时，相遇的节点即为环路的开始点。

AC

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        ListNode *slow = head,*fast = head;
        do{
            //看fast是否走到链表结尾，进而判断是否存在环路
            if(!fast||!fast->next) return NULL;
            fast=fast->next->next;
            slow=slow->next;
        }while(slow!=fast);
        //如果存在，找节点位置
        fast=head;
        while(slow!=fast){
            fast=fast->next;
            slow=slow->next;
        }
        return fast;
    }
};

LeetCode 76. 最小覆盖子串 【滑动窗口】

题目描述

给定两个字符串 S 和T，求 S 中包含T 所有字符的最短连续子字符串的长度，同时要求时间 复杂度不得超过O(n)。

解题思路

需要思考以下四个问题：

1、当移动 right 扩大窗口，即加入字符时，应该更新哪些数据？

2、什么条件下，窗口应该暂停扩大，开始移动left 缩小窗口？

3、当移动 left缩小窗口，即移出字符时，应该更新哪些数据？

4、我们要的结果应该在扩大窗口时还是缩小窗口时进行更新？

如果一个字符进入窗口，应该增加 window计数器；如果一个字符将移出窗口的时候，应该减少 window 计数器；当 cnt满足 need时应该收缩窗口；应该在收缩窗口的时候更新最终结果。

需要注意的是，当我们发现某个字符在window的数量满足了need的需要，就要更新 valid，表示有一个字符已经满足要求。而且，你能发现，两次对窗口内数据的更新操作是完全对称的。

当 cnt == need.size()时，说明T 中所有字符已经被覆盖，已经得到一个可行的覆盖子串，现在应该开始收缩窗口了，以便得到「最小覆盖子串」。

移动 left收缩窗口时，窗口内的字符都是可行解，所以应该在收缩窗口的阶段进行最小覆盖子串的更新，以便从可行解中找到长度最短的最终结果。

参考 ：labuladong 大佬题解

AC

class Solution {
public:
    string minWindow(string s, string t) {
        unordered_map<char,int> need,window;
        for(char c : t) need[c]++;
        int left=0,right=0,cnt=0;
        // 记录最小覆盖子串的起始索引及长度
        int start=0,len=INT_MAX;
        while(right<s.size()){
         	// c 是将移入窗口的字符
            char c = s[right];
            // 右移窗口
            right++;
            // 进行窗口内数据的一系列更新
            if(need.count(c)){
                window[c]++;
                if(window[c]==need[c])
                    ++cnt;
            }
            // 判断左侧窗口是否要收缩
            while(cnt==need.size()){
            	// 在这里更新最小覆盖子串
                if(right-left<len){
                    len=right-left;
                    start=left;
                }
                // dd 是将移出窗口的字符
                char dd = s[left];
                // 左移窗口
                left++;
                // 进行窗口内数据的一系列更新
                if(need.count(dd)){
                    if(window[dd]==need[dd]) --cnt;
                    window[dd]--;
                }
            }
        }
        return len == INT_MAX? "" : s.substr(start,len);
    }
};

LeetCode 567. 字符串的排列 【滑动窗口】

题目描述

给定两个字符串 s1 和 s2，写一个函数来判断 s2 是否包含 s1 的排列。

换句话说，第一个字符串的排列之一是第二个字符串的子串。

示例1:

输入: s1 = “ab” s2 = “eidbaooo”
输出: True
解释: s2 包含 s1 的排列之一 (“ba”).

示例2:

输入: s1= “ab” s2 = “eidboaoo”
输出: False

注意：

• 输入的字符串只包含小写字母
• 两个字符串的长度都在 [1, 10,000] 之间

解题思路

这道题依旧是可以用滑动窗口算法来做，基本上与模板没什么太大差别。

需要修改的小地方：
1、本题移动 left 缩小窗口的时机是窗口大小 大于或等于 s1.size() 时。

2、当发现 cnt == need.size() 时，就说明窗口中就是一个合法的排列，所以立即返回 true。

AC

class Solution {
public:
    bool checkInclusion(string s1, string s2) {
        unordered_map<char,int> window,need;
        for(char c:s1) need[c]++;
        int left=0,right=0,cnt=0;
        int start=0,len=INT_MAX;
        while(right<s2.size()){
            char c = s2[right];
            right++;
            if(need.count(c)){
                window[c]++;
                if(window[c]==need[c]) ++cnt;
            }
            while(right-left>=s1.size()){
                if(cnt == need.size()){
                    return true;
                }
                char dd = s2[left];
                left++;
                if(need.count(dd)){
                    if(window[dd]==need[dd]) --cnt;
                    --window[dd];
                }
            }
        }
        return false;
    }
};

LeetCode 438. 找到字符串中所有字母异位词【滑动窗口】

题目描述

给定一个字符串 s 和一个非空字符串 p，找到 s 中所有是 p 的字母异位词的子串，返回这些子串的起始索引。

字符串只包含小写英文字母，并且字符串 s 和 p 的长度都不超过 20100。

说明：

字母异位词指字母相同，但排列不同的字符串。
不考虑答案输出的顺序。
示例 1:

输入:
s: “cbaebabacd” p: “abc”

输出:
[0, 6]

解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的字母异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的字母异位词。
示例 2:

输入:
s: “abab” p: “ab”

输出:
[0, 1, 2]

解释:
起始索引等于 0 的子串是 “ab”, 它是 “ab” 的字母异位词。
起始索引等于 1 的子串是 “ba”, 它是 “ab” 的字母异位词。
起始索引等于 2 的子串是 “ab”, 它是 “ab” 的字母异位词。

解题思路

输入一个串 S，一个串 T，找到 S 中所有 T 的排列，返回它们的起始索引。

这道题依旧是可以用滑动窗口算法来做，基本上与模板没什么太大差别。

需要修改的小地方：
1、本题移动 left 缩小窗口的时机是窗口大小 大于或等于 s1.size() 时。

2、当发现 cnt == need.size() 时，就说明窗口中就是一个合法的排列，添加对应索引值（即 left值）

AC

class Solution {
public:
    vector<int> findAnagrams(string s, string p) {
        unordered_map<char,int> window,need;
        for(char c:p) need[c]++;
        int left=0,right=0,cnt=0;
        int start=0,len=INT_MAX;
        vector<int> res;
        while(right<s.size()){
            char c = s[right];
            right++;
            if(need.count(c)){
                window[c]++;
                if(window[c]==need[c]) ++cnt;
            }
            while(right-left>=p.size()){
                if(cnt == need.size())
                    res.push_back(left);
                char dd = s[left];
                left++;
                if(need.count(dd)){
                    if(window[dd]==need[dd]) --cnt;
                    --window[dd];
                }
            }
        }
        return res;
    }
};

LeetCode 3. 无重复字符的最长子串【滑动窗口】

题目描述

给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。

示例 1:

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:

输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:

输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。

• 请注意，你的答案必须是 子串 的长度，”pwke” 是一个子序列，不是子串。

解题思路

当 window[c] 值大于 1 时，说明窗口中存在重复字符，不符合条件，就该移动 left 缩小窗口。当收缩窗口完成后，此时就不存在重复元素了，判断最长子串即可。

AC

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        unordered_map<char,int> window;
        int left=0,right=0;
        int ans=0;
        while(right<s.size()){
            char c = s[right];
            right++;
            window[c]++;
            while(window[c]>1){
                char dd = s[left];
                left++;
                window[dd]--;
            }
            ans=max(ans,right-left);
        }
        return ans;
    }
};

LeetCode 69. x 的平方根 【二分查找】

题目描述

实现 int sqrt(int x) 函数。

计算并返回 x 的平方根，其中 x 是非负整数。

由于返回类型是整数，结果只保留整数的部分，小数部分将被舍去。

示例 1:

输入: 4
输出: 2
示例 2:

输入: 8
输出: 2
说明: 8 的平方根是 2.82842…,

• 由于返回类型是整数，小数部分将被舍去。

解题思路

我们可以把这道题想象成，给定一个非负整数 a，求 f(x) = x^2^ −a = 0 的解。因为我们只考虑 x ≥ 0，所以 f(x)在定义域上是单调递增的。考虑到 f(0) = −a ≤ 0，f(a) = a^2^ −a ≥ 0，我们可以对[0,a]区间使用二分法找到 f(x) = 0的解。

注意，在以下的代码里，为了防止除以0，我们把 a = 0的情况单独考虑，然后对区间[1,a] 进行二分查找。

使用了左闭右闭的写法。

AC

class Solution {
public:
    int mySqrt(int x) {
        if(x==0) return 0;
        long left=1,right=x,ans;
        long mid;
        while(left<=right){
            mid = (left+right)/2;
            ans = x/mid;
            if(ans == mid) return ans;
            else if(ans < mid) right = mid-1;
            else left = mid+1;
        }
        return right;
    }
};

LeetCode 34. 在排序数组中查找元素的第一个和最后一个位置【二分查找】

题目描述

给定一个按照升序排列的整数数组 nums，和一个目标值 target。找出给定目标值在数组中的开始位置和结束位置。

你的算法时间复杂度必须是 O(log n) 级别。

如果数组中不存在目标值，返回 [-1, -1]。

示例 1:

输入: nums = [5,7,7,8,8,10], target = 8
输出: [3,4]
示例 2:

输入: nums = [5,7,7,8,8,10], target = 6
输出: [-1,-1]

解题思路

可以看作是自己实现 C++ 里的 lower_bound 和 upper_bound 函数。

AC

class Solution {
public:
    vector<int> searchRange(vector<int>& nums, int target) {
        if(nums.empty()) return vector<int>{-1,-1};
        int lower = lower_bound(nums,target);
        int upper = upper_bound(nums,target)-1;
        if(lower == nums.size() || nums[lower]!=target)
            return vector<int>{-1,-1};
        return vector<int>{lower,upper};
    }
    int lower_bound(vector<int> &nums, int target){
        int left=0,right=nums.size(),mid;
        while(left<right){
            mid = (left+right)/2;
            if(nums[mid] >= target) right=mid;
            else left=mid+1;
        }
        return left;
    }
    int upper_bound(vector<int> &nums, int target){
        int left=0,right=nums.size(),mid;
        while(left<right){
            mid = (left+right)/2;
            if(nums[mid] > target) right=mid;
            else left=mid+1;
        }
        return left;
    }
};

LeetCode 81. 搜索旋转排序数组 II【二分查找】

题目描述

假设按照升序排序的数组在预先未知的某个点上进行了旋转。

( 例如，数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。

编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true，否则返回 false。

示例 1:

输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true
示例 2:

输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false

解题思路

本题是需要使用二分查找，怎么分是关键，举个例子：

第一类
10111 和 11101 这种。此种情况下 nums[start] == nums[mid]，分不清到底是前面有序还是后面有序，此时 start++ 即可。相当于去掉一个重复的干扰项。
第二类
2 3 4 5 6 7 1 这种，也就是 nums[start] < nums[mid]。此例子中就是 2 < 5；
这种情况下，前半部分有序。因此如果 nums[start] <=target<nums[mid]，则在前半部分找，否则去后半部分找。
第三类
6 7 1 2 3 4 5 这种，也就是 nums[start] > nums[mid]。此例子中就是 6 > 2；
这种情况下，后半部分有序。因此如果 nums[mid] <target<=nums[end]。则在后半部分找，否则去前半部分找。

AC

class Solution {
public:
    bool search(vector<int>& nums, int target) {
        int left=0,right=nums.size()-1;
        while(left<=right){
            int mid = (left+right)/2;
            if(nums[mid] == target) return true;
            if(nums[left] == nums[mid]) left++;
            else if(nums[mid]<=nums[right]){
                if(target>nums[mid] && target<=nums[right]){
                    left=mid+1;
                }else{
                    right=mid-1;
                }
            }else{
                if(target>=nums[left] && target<nums[mid]){
                    right=mid-1;
                }else{
                    left=mid+1;
                }
            }
        }
        return false;
    }
};

LeetCode 215. 数组中的第K个最大元素 【小顶堆与快速选择】

题目描述

在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。

示例 1:

输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:

输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:

你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。

解题思路

• 小顶推方式

建一个只能存K个数字的小顶堆，超过K时候，每加进来一个，堆顶就要弹出一个。数组遍历完，最终堆顶的元素就是第K大的（堆里其他元素都比他还要大）。

• 快速选择方式

快速选择算法 的平均时间复杂度为 O(N)。就像快速排序那样，本算法也是 Tony Hoare 发明的，因此也被称为 Hoare选择算法。

本方法大致上与快速排序相同。简便起见，注意到第 k 个最大元素也就是第 N - k 个最小元素，因此可以用第 k 小算法来解决本问题。

首先，我们选择一个枢轴，并在线性时间内定义其在排序数组中的位置。这可以通过 划分算法 的帮助来完成。

为了实现划分，沿着数组移动，将每个元素与枢轴进行比较，并将小于枢轴的所有元素移动到枢轴的左侧。

这样，在输出的数组中，枢轴达到其合适位置。所有小于枢轴的元素都在其左侧，所有大于或等于的元素都在其右侧。

这样，数组就被分成了两部分。如果是快速排序算法，会在这里递归地对两部分进行快速排序，时间复杂度为 O(NlogN)。

而在这里，由于知道要找的第 N - k 小的元素在哪部分中，我们不需要对两部分都做处理，这样就将平均时间复杂度下降到 O(N)。

最终的算法十分直接了当 :

随机选择一个枢轴。

使用划分算法将枢轴放在数组中的合适位置 pos。将小于枢轴的元素移到左边，大于等于枢轴的元素移到右边。

比较 pos 和 N - k 以决定在哪边继续递归处理。

! 注意，本算法也适用于有重复的数组

AC

采用小顶推方式：

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        priority_queue<int,vector<int>,greater<int>> q;
        for(auto it:nums){
            q.push(it);
            if(q.size()>k) q.pop();
        }
        return q.top();
    }
};

采用快速选择方式：

class Solution {
public:
    int findKthLargest(vector<int>& nums, int k) {
        int start=0,end=nums.size()-1,target=nums.size()-k;
        while(start<end){
            int mid = quickSelect(nums,start,end);
            if(mid == target) return nums[mid];
            else if(target>mid) start=mid+1;
            else end=mid-1;
        }
        return nums[start];
    }
    int quickSelect(vector<int>& nums,int p,int q){
        int i=p+1,j=q;
        int x=nums[p];
        while(1){
            while(i<q && nums[i]<=x) ++i;
            while(j>p && nums[j]>=x) --j;
            if(i>=j) break;
            swap(nums[i],nums[j]);
        }
        swap(nums[p],nums[j]);
        return j;
    }
};

LeetCode 347. 前 K 个高频元素【桶排序】

题目描述

给定一个非空的整数数组，返回其中出现频率前 k 高的元素。

示例 1:

输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:

输入: nums = [1], k = 1
输出: [1]

提示：

• 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
• 你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
• 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
• 你可以按任意顺序返回答案。

解题思路

顾名思义，桶排序的意思是为每个值设立一个桶，桶内记录这个值出现的次数（或其它属 性），然后对桶进行排序。针对样例来说，我们先通过桶排序得到三个桶[1,2,3,4]，它们的值分别 为[4,2,1,1]，表示每个数字出现的次数。

紧接着，我们对桶的频次进行排序，前k 大个桶即是前k 个频繁的数。这里我们可以使用各种 排序算法，甚至可以再进行一次桶排序，把每个旧桶根据频次放在不同的新桶内。针对样例来说， 因为目前最大的频次是 4，我们建立 [1,2,3,4] 四个新桶，它们分别放入的旧桶为 [ [3,4],[2],[],[1] ]， 表示不同数字出现的频率。

最后，我们从后往前遍历，直到找到 k 个旧桶。

AC

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<long,long> mp;
        int max_count=0;
        for(auto x:nums){
            ++mp[x];
            if(max_count<=mp[x]) max_count=mp[x];
        }
        vector<vector<int>> v(max_count+1);
        for(auto it:mp)
            v[it.second].push_back(it.first);
        vector<int> ans;
        for(int i=max_count;i>=0;i--){
            for(auto x:v[i]){
                ans.push_back(x);
                if(ans.size()==k) break;
            }
            if(ans.size()==k) break;
        }
        return ans;
    }
};

LeetCode 695. 岛屿的最大面积【dfs】

题目描述

给定一个包含了一些 0 和 1 的非空二维数组 grid 。

一个 岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在水平或者竖直方向上相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

找到给定的二维数组中最大的岛屿面积。(如果没有岛屿，则返回面积为 0 。)

示例 1:

[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]

对于上面这个给定矩阵应返回 6。注意答案不应该是 11 ，因为岛屿只能包含水平或垂直的四个方向的 1 。

示例 2:

[[0,0,0,0,0,0,0,0]]

对于上面这个给定的矩阵, 返回 0。

注意: 给定的矩阵grid 的长度和宽度都不超过 50。

解题思路

十分标准的搜索题，用来练手深度优先搜索。

AC

class Solution {
public:
    vector<int> dir{-1,0,1,0,-1};
    int maxAreaOfIsland(vector<vector<int>>& grid) {
        if(grid.empty() || grid[0].empty()) return 0;
        int max_area=0;
        for(int i=0;i<grid.size();i++){
            for(int j=0;j<grid[0].size();j++){
                if(grid[i][j]==1){
                    max_area=max(max_area,dfs(grid,i,j));
                }
            }
        }
        return max_area;
    }
    int dfs(vector<vector<int>>& grid,int x,int y){
        if(grid[x][y]==0) return 0;
        grid[x][y]=0;
        int xx,yy,ans=1;
        for(int i=0;i<4;i++){
            xx=x+dir[i],yy=y+dir[i+1];
            if(xx>=0&&xx<grid.size() && yy>=0&&yy<grid[0].size()){
                ans+=dfs(grid,xx,yy);
            }
        }
        return ans;
    }
};

LeetCode 547. 朋友圈【dfs】

题目描述

班上有 N 名学生。其中有些人是朋友，有些则不是。他们的友谊具有是传递性。如果已知 A 是 B 的朋友，B 是 C 的朋友，那么我们可以认为 A 也是 C 的朋友。所谓的朋友圈，是指所有朋友的集合。

给定一个 N * N 的矩阵 M，表示班级中学生之间的朋友关系。如果M[i][j] = 1，表示已知第 i 个和 j 个学生互为朋友关系，否则为不知道。你必须输出所有学生中的已知的朋友圈总数。

示例 1:

输入:
[[1,1,0],
[1,1,0],
[0,0,1]]
输出: 2
说明：已知学生0和学生1互为朋友，他们在一个朋友圈。
第2个学生自己在一个朋友圈。所以返回2。

示例 2:

输入:
[[1,1,0],
[1,1,1],
[0,1,1]]
输出: 1
说明：已知学生0和学生1互为朋友，学生1和学生2互为朋友，所以学生0和学生2也是朋友，所以他们三个在一个朋友圈，返回1。

注意：

• N 在[1,200]的范围内。
• 对于所有学生，有M[i][i] = 1。
• 如果有M[i][j] = 1，则有M[j][i] = 1。

解题思路

dfs。朋友圈的个数等于连通块的个数，搜索一遍就累加一次即可。

AC

class Solution {
public:
    int findCircleNum(vector<vector<int>>& M) {
        int n=M.size(),cnt=0;
        vector<bool> vis(n,false);
        for(int i=0;i<n;i++){
            if(!vis[i]){
                dfs(M,vis,i);
                ++cnt;
            }
        }
        return cnt;
    }
    void dfs(vector<vector<int>>& M,vector<bool>& vis,int u){
        vis[u]=true;
        int m=M[u].size();
        for(int i=0;i<m;i++){
            if(M[u][i]==1 && !vis[i])
                dfs(M,vis,i);
        }
    }
};

LeetCode 417. 太平洋大西洋水流问题【dfs】

题目描述

给定一个 m x n 的非负整数矩阵来表示一片大陆上各个单元格的高度。“太平洋”处于大陆的左边界和上边界，而“大西洋”处于大陆的右边界和下边界。

规定水流只能按照上、下、左、右四个方向流动，且只能从高到低或者在同等高度上流动。

请找出那些水流既可以流动到“太平洋”，又能流动到“大西洋”的陆地单元的坐标。

提示：

输出坐标的顺序不重要
m 和 n 都小于150

示例：

给定下面的 5x5 矩阵:
太平洋 ~ ~ ~ ~ ~
~ 1 2 2 3 (5) *
~ 3 2 3 (4) (4) *
~ 2 4 (5) 3 1 *
~ (6) (7) 1 4 5 *
~ (5) 1 1 2 4 *
* * * * * 大西洋
返回:
[[0, 4], [1, 3], [1, 4], [2, 2], [3, 0], [3, 1], [4, 0]] (上图中带括号的单元).

解题思路

虽然题目要求的是满足向下流能到达两个大洋的位置，如果我们对所有的位置进行搜索，那么在不剪枝的情况下复杂度会很高。

因此我们可以反过来想，从两个大洋开始向上流，这样我们只需要对矩形四条边进行搜索。搜索完成后，只需遍历一遍矩阵，满足条件的位置即为两个大洋向上流都能到达的位置。

AC

class Solution {
public:
    vector<int> dir{-1,0,1,0,-1};
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& matrix) {
        if(matrix.empty() || matrix[0].empty()) return {};
        vector<vector<int>> ans;
        int n=matrix.size(),m=matrix[0].size();
        vector<vector<bool>> canReachT(n,vector<bool>(m,false));
        vector<vector<bool>> canReachD(n,vector<bool>(m,false));
        for(int i=0;i<n;i++){
            dfs(matrix,canReachT,i,0);
            dfs(matrix,canReachD,i,m-1);
        }
        for(int i=0;i<m;i++){
            dfs(matrix,canReachT,0,i);
            dfs(matrix,canReachD,n-1,i);
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<m;j++){
                if(canReachT[i][j] && canReachD[i][j]){
                    ans.push_back(vector<int>{i,j});
                }
            }
        }
        return ans;
    }
    void dfs(vector<vector<int>>& matrix,vector<vector<bool>>& canReach,int x,int y){
        if(canReach[x][y]) return;
        canReach[x][y]=true;
        int xx,yy;
        for(int i=0;i<4;i++){
            xx=x+dir[i],yy=y+dir[i+1];
            if(xx>=0&&xx<matrix.size() && yy>=0&&yy<matrix[0].size() && matrix[x][y]<=matrix[xx][yy])
            dfs(matrix,canReach,xx,yy);
        }
    }
};

LeetCode 46. 全排列【dfs】

题目描述

给定一个 没有重复 数字的序列，返回其所有可能的全排列。

示例:

输入: [1,2,3]
输出:
[
[1,2,3],
[1,3,2],
[2,1,3],
[2,3,1],
[3,1,2],
[3,2,1]
]

解题思路

怎样输出所有的排列方式呢？对于每一个当前位置 i，我们可以将其于之后的任意位置交换， 然后继续处理位置 i+1，直到处理到最后一位。

为了防止我们每此遍历时都要新建一个子数组储存位置i之前已经交换好的数字，我们可以利用回溯法，只对原数组进行修改，在递归完成后再修改回来。

我们以样例[1,2,3]为例，按照这种方法，我们输出的数组顺序为[[1,2,3],[1,3,2],[2,1,3],[2,3,1], [3,1,2],[3,2,1]]，可以看到所有的排列在这个算法中都被考虑到了。

AC

class Solution {
public:
    vector<vector<int>> permute(vector<int>& nums) {
        vector<vector<int>> ans;
        dfs(nums,0,ans);
        return ans;
    }
    void dfs(vector<int>& nums,int t,vector<vector<int>>& ans){
        if(t==nums.size()-1){
            ans.push_back(nums);
            return;
        }
        for(int i=t;i<nums.size();i++){
            swap(nums[i],nums[t]);
            dfs(nums,t+1,ans);
            swap(nums[i],nums[t]);
        }
    }
};