阅读须知

本篇博客是根据 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]);
}
}
};