leedcode

leedcode
算法
发布日期:   2021-09-14

leedcode 算法

链接

day 1

1. 二分查找

描述

给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。

分析

二分查找即可

学习算法要形成自己固定的模板。二分查找的模板如下：

  1. 统一标准：[low,high) 前闭后开
  2. mid=low+(high-low)/2;
  3. while(low < high)

所以模板如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
//定义low和high的初始值，high是可以取得的最后一个元素的下一个。前闭后开。
low=low;
high=high;
//循环
while(low<high)
{
    mid=low+(high-low)/2;
    if(mid比目标大)
        high=mid;//不一定是mid，只要high指向第一个肯定不是答案的元素即可
    else if(mid比目标小)
        low=mid+1;//low指向第一个可能是答案的元素即可 保证目标元素在 [low,high)即可
    else 
        查找成功，返回。
}
//查找失败
return -1;

有一点需要注意：若判断mid是否满足条件的时候，当mid满足条件则舍去mid时使用开区间，当mid满足条件而保留mid时使用闭区间。注意while中low和high的比较条件，当low和high满足什么条件时构成的区间仍然存在答案的可能性。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int search(int* nums, int numsSize, int target){
    int low=0;
    int high=numsSize;
    while(low<high)
    {
        int mid=low+(high-low)/2;
        if(*(nums+mid)>target)
            high=mid;
        else if(*(nums+mid)<target)
            low=mid+1;
        else 
            return mid;
    }
    return -1;
}

2. 第一个错误的版本

描述

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

分析

直接使用二分查找即可

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
// The API isBadVersion is defined for you.
// bool isBadVersion(int version);

int firstBadVersion(int n) 
{
    int low=1;
    int high=n;
    //mid满足条件仍然保留使用闭区间
    while(low<high)
    {
        int mid=low+(high-low)/2;
        if(isBadVersion(mid))
            high=mid;
        else 
            low=mid+1;
    }
    return low;
}

3. 搜索插入位置

描述

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

分析

判断mid是否相等，相等则返回，直到发现不存在位置。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
int searchInsert(int* nums, int numsSize, int target){
    int low=0;
    int high=numsSize-1;
    int mid;
    if(target<*nums)
        return 0;
    if(target>*(nums+numsSize-1))
        return numsSize;
    //找到第一个大于等于target的元素
    while(low<high)
    {
        mid=low+(high-low)/2;
        if(*(nums+mid)>=target)
            high=mid;
        else if(*(nums+mid)<target)
            low=mid+1;//low++则low至少每一次循环加一，故不可能死循环，所以等于的时候要退出
        else 
            return mid;
    }
    return low;
}

二分法总结

练习

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

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

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution
{
public:
    vector<int> searchRange(vector<int> &nums, int target)
    {
        vector<int> res;
        if (nums.size() == 0)
        {
            res.push_back(-1);
            res.push_back(-1);
            return res;
        }
        int low = 0;
        int high = nums.size() - 1;
        int mid;
        //min
        while (low < high)
        {
            //这里要是向下取整 尽量多走向low=mid+1;这个分支
            mid = low + (high - low) / 2;
            if (nums.at(mid) >= target)
                high = mid;
            else if (nums.at(mid) < target)
                low = mid + 1;
        }
        if (nums.at(low) == target)
            res.push_back(low);
        else
            res.push_back(-1);
        //max
        //low=0; //low不用变
        high = nums.size() - 1;
        while (low < high)
        {
            //这里要是向上取整 尽量多走向high=mid-1;这个分支,即尽可能取大的，即向上取整
            mid = low + (high - low) / 2 + (high - low) % 2;
            if (nums.at(mid) <= target)
                low = mid;
            else
                high = mid - 1;
        }
        if (nums.at(low) == target)
            res.push_back(low);
        else
            res.push_back(-1);
        return res;
    }
};
33. 搜索旋转排序数组

寻找所在分段然后在该分段内使用常规二分查找即可

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

class Solution
{
public:
    int search(vector<int> &nums, int target)
    {
        //输入：nums = [4,5,6,7,0,1,2], target = 0
        //输出：4
        //先找到分界处再分段处理
        int low = 0;
        int high = nums.size() - 1;
        int mid;
        //如果旋转度不为零则寻找目标分段
        if (nums.at(low) > nums.at(high))
        {
            //找到分界处
            while (low < high - 1)
            {
                //向下取整
                mid = low + (high - low) / 2;
                if (nums.at(mid) > nums.at(low))
                    low = mid;
                else if (nums.at(mid) < nums.at(high))
                    high = mid;
            }
            //已经找到了分界处，划分
            //在第一段
            if (target >= nums.at(0) && target <= nums.at(low))
            {
                high = low;
                low = 0;
            }
            //在第二段
            else if (target >= nums.at(high) && target <= nums.at(nums.size() - 1))
            {
                low = high;
                high = nums.size() - 1;
            }
            //都不在
            else
                return -1;
        }
        //现在target就在low-high中
        while (low <= high)
        {
            //向下取整
            mid = low + (high - low) / 2;
            if (nums.at(mid) < target)
                low = mid + 1;
            else if (nums.at(mid) > target)
                high = mid - 1;
            else
                return mid;
        }
        return -1;
    }
};
81. 搜索旋转排序数组 II

跟上一道题比起来，这道题的难点在于如何处理重复的元素。
//去除重复的影响
while ((low<high)&&(nums.at(++low) == nums.at(high)));

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
class Solution
{
public:
    bool search(vector<int> &nums, int target)
    {
        //输入：nums = [1,0,1,1,1] target = 0
        //输出：4
        if (nums.size() == 1)
            return nums.at(0) == target;
        //先找到分界处再分段处理
        int low = -1;
        int high = nums.size() - 1;
        int mid;
        //如果旋转度不为零则寻找目标分段
        //去除重复的影响
        while ((low<high)&&(nums.at(++low) == nums.at(high)));
        if (nums.at(low) > nums.at(high))
        {
            //找到分界处
            while (low < high - 1)
            {
                //向下取整
                mid = low + (high - low) / 2;
                if (nums.at(mid) == target)
                    return true;
                if (nums.at(mid) >= nums.at(low))
                    low = mid;
                else if (nums.at(mid) <= nums.at(high))
                    high = mid;
            }
            //已经找到了分界处，划分
            //在第一段
            if (target >= nums.at(0) && target <= nums.at(low))
            {
                high = low;
                low = 0;
            }
            //在第二段
            else if (target >= nums.at(high) && target <= nums.at(nums.size() - 1))
            {
                low = high;
                high = nums.size() - 1;
            }
            //都不在
            else
                return false;
        }
        //现在target就在low-high中
        while (low <= high)
        {
            //向下取整
            mid = low + (high - low) / 2;
            if (nums.at(mid) < target)
                low = mid + 1;
            else if (nums.at(mid) > target)
                high = mid - 1;
            else
                return true;
        }
        return false;
    }
};
153. 寻找旋转排序数组中的最小值

没什么难度，就是判断是否分界以及分界点

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution
{
public:
    int findMin(vector<int> &nums)
    {
        //输入：nums = [1,0,1,1,1] target = 0
        //输出：4
        if (nums.size() == 1)
            return nums.at(0);
        //先找到分界处再分段处理
        int low = 0;
        int high = nums.size() - 1;
        int mid;
        //如果旋转度不为零则寻找目标分段
        if (nums.at(low) > nums.at(high))
        {
            //找到分界处
            while (low < high - 1)
            {
                //向下取整
                mid = low + (high - low) / 2;
                if (nums.at(mid) > nums.at(low))
                    low = mid;
                else if (nums.at(mid) < nums.at(high))
                    high = mid;
            }
            //已经找到了分界处，划分
            return nums.at(high);
        }
        return nums.at(low);
    }
};
154. 寻找旋转排序数组中的最小值 II

比上一道题多一个消除即可
//去除重复的影响
while ((low<high)&&(nums.at(++low) == nums.at(high)));

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution
{
public:
    int findMin(vector<int> &nums)
    {
        //输入：nums = [1,0,1,1,1] target = 0
        //输出：4
        if (nums.size() == 1)
            return nums.at(0);
        //先找到分界处再分段处理
        int low = -1;
        int high = nums.size() - 1;
        int mid;
        //如果旋转度不为零则寻找目标分段
        //去除重复的影响
        while ((low<high)&&(nums.at(++low) == nums.at(high)));
        if (nums.at(low) > nums.at(high))
        {
            //找到分界处
            while (low < high - 1)
            {
                //向下取整
                mid = low + (high - low) / 2;
                if (nums.at(mid) >= nums.at(low))
                    low = mid;
                else if (nums.at(mid) <= nums.at(high))
                    high = mid;
            }
            //已经找到了分界处，划分
            return nums.at(high);
        }
        return nums.at(low);
    }
};
300. 最长递增子序列

首先想到使用动态规划将问题缩小到更小规模。考虑到以每一个元素为结尾的最长递增子序列与在其前面的所有元素的关系为 两个元素满足递增关系则当前元素的最长值的前面的元素的最长值加一,然后遍历当前元素的所有前元素即可找打最大值。

但是这种方法的时间复杂度为O(N^2)不好。

方法二：

贪心加二分，首先维护一个最长递增子序列的长度len，一个记录每一个长度的递增子序列的最后一个元素的最小值的数组dp[n]，显然这个数组递增。然后遍历nums,若nums[i]大于dp[len]则说明当前最长的递增子序列还可以在其后面加上一个nums[i]来使得长度加一。否则的话在dp中寻找一个位置使得dp[j]为第一个大于nums[i]的。这可以使用二分来寻找。

代码 方法一 动态规划
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        //最长子序列长度
        //dp[i]=max{dp[i]&&nums[i]>nums[j],|j = 0 - i-1}
        vector<int> dp;
        dp.push_back(1);
        int MAX=1;
        for(int i=1;i<=nums.size()-1;i++)
        {
            int max=1;
            for(int j=i-1;j>=0;j--)
                if(nums.at(i)>nums.at(j))
                    if(dp.at(j)+1>max)
                        max=dp.at(j)+1;
            dp.push_back(max);
            MAX=max>MAX?max:MAX;
        }
        return MAX;
    }
};
代码 方法二 贪心加二分
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
class Solution
{
public:
    int lengthOfLIS(vector<int> &nums)
    {
        vector<int> dp = {0};
        int len = 1;
        dp.push_back(nums.at(0));
        int low;
        int high;
        int mid;
        int cur;
        for (int i = 1; i <= nums.size() - 1; i++)
        {
            cur = nums.at(i);
            if (cur > dp.at(len))
            {
                dp.push_back(cur);
                len++;
                continue;
            }
            //二分寻找合适的位置
            low = 1;
            high = len;
            mid;
            //找到第一个大于cur
            while (low < high)
            {
                mid = low + (high - low) / 2;
                if (cur < dp.at(mid))
                    high = mid;
                else if (cur > dp.at(mid))
                    low = mid + 1;
                else
                    low = high = mid;
            }
            dp.at(high) = cur;
        }
        return len;
    }
};
852. 山脉数组的峰顶索引

没什么好说的，注意边界即可

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution
{
public:
    int peakIndexInMountainArray(vector<int> &arr)
    {
        //山脉数组 单调
        //即找出最大值
        int low = 0;
        int high = arr.size() - 1;
        int mid;
        int left_value;
        int mid_value;
        int right_valule;
        while (low < high)
        {
            mid = low + (high - low) / 2;
            if (mid == 0)
                return 1;
            left_value = arr.at(mid - 1);
            mid_value = arr.at(mid);
            right_valule = arr.at(mid + 1);
            //左峰
            if (left_value < mid_value && mid_value < right_valule)
                low = mid + 1;
            else if (left_value > mid_value && mid_value > right_valule)
                high = mid - 1;
            else
                return mid;
        }
        return low;
    }
};
1095. 山脉数组中查找目标值

这个也好，首先利用上一题找到山峰的位置，然后分段二分查找即可，先左后右

代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76


class Solution
{
public:
    int findInMountainArray(int target, MountainArray &mountainArr)
    {
        //山脉数组 单调
        //即找出最大值
        int low = 0;
        int high = mountainArr.length() - 1;
        int mid;
        int left_value;
        int mid_value;
        int right_valule;
        int peak;
        int res = -1;
        while (low < high)
        {

            mid = low + (high - low) / 2;
            if (mid == 0)
            {
                low=1;
                break;
            }
            left_value = mountainArr.get(mid - 1);
            mid_value = mountainArr.get(mid);
            right_valule = mountainArr.get(mid + 1);
            //左峰
            if (left_value < mid_value && mid_value < right_valule)
                low = mid + 1;
            else if (left_value > mid_value && mid_value > right_valule)
                high = mid - 1;
            else
            {
                low = mid;
                break;
            }
        }
        peak=low;
        //在山峰左侧寻找
        low = 0;
        high = peak;
        while (low < high)
        {
            mid = low + (high - low) / 2;
            mid_value = mountainArr.get(mid);
            if (target < mid_value)
                high = mid - 1;
            else if (target > mid_value)
                low = mid + 1;
            else
                return mid;
        }
        if(mountainArr.get(low)==target)
            return low;
        //左侧没有找到，寻找右侧
        low = peak + 1;
        high = mountainArr.length() - 1;
        while (low < high)
        {
            mid = low + (high - low) / 2;
            mid_value = mountainArr.get(mid);
            if (target > mid_value)
                high = mid - 1;
            else if (target < mid_value)
                low = mid + 1;
            else
                return mid;
        }
        if(mountainArr.get(low)==target)
            return low;
        return -1;
    }
};
4. 寻找两个正序数组的中位数
代码 未定
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
class Solution
{
public:
    double findMedianSortedArrays(vector<int> &nums1, vector<int> &nums2)
    {
        //寻找中位数
        //方法一 合并 O(m+n)
        //方法二 使用二分直接锁定

        //若有一个为空，则直接返回另一个的结果。
        if (nums1.size() == 0)
        {
            int index = nums2.size() - 1;
            if (index % 2 == 0)
            {
                return (double)nums2.at(index / 2);
            }
            else
            {
                return (double)(nums2.at(index / 2) + nums2.at(index / 2 + 1));
            }
        }
        else if (nums2.size() == 0)
        {
            int index = nums1.size() - 1;
            if (index % 2 == 0)
            {
                return (double)nums1.at(index / 2);
            }
            else
            {
                return (double)(nums1.at(index / 2) + nums1.at(index / 2 + 1));
            }
        }
        //无空
        int low1 = 0;
        int high1 = nums1.size() - 1;
        int low2 = 0;
        int high2 = nums2.size() - 1;
        bool isodd=(high1+high2)%2;
        double res;
        int mid1;
        int mid2;
        int mid1_value;
        int mid2_value;
        while (low1 < high1 || low2 < high2)
        {
            mid1 = low1 + (high1 - low1) / 2;
            mid1_value = nums1.at(mid1);
            mid2 = low2 + (high2 - low2) / 2;
            mid2_value = nums2.at(mid2);
            //左侧的mid小
            if (mid1_value <= mid2_value)
            {
                //左
                low1 = mid1;
                //high1 等于 nums1中最后一个小于mid2的
                int low = low1;
                int high = high1;
                int mid;
                int mid_value;
                while (low < high)
                {
                    mid = low + (high - low) / 2+(high-low)%2;
                    mid_value = nums1.at(mid);
                    if (mid2_value > mid_value)
                        low = mid;
                    else if (mid2_value <= mid_value)
                        high = mid - 1;
                }
                high1 = high;
                //右
                high2 = mid2;
                //low2 等于nums2中第一个大于mid1的
                low = low2;
                high = high2;
                while (low < high)
                {
                    mid = low + (high - low) / 2;
                    mid_value = nums2.at(mid);
                    if (mid1_value >= mid_value)
                        low = mid + 1;
                    else if (mid1_value < mid_value)
                        high = mid;
                }
                low2 = low;
            }
            //右侧的mid小
            else
            {
                //右
                low2 = mid2;
                //high1 等于 nums1中最后一个小于mid2的
                int low = low2;
                int high = high2;
                int mid;
                int mid_value;
                while (low < high)
                {
                    mid = low + (high - low) / 2+(high-low)%2;
                    mid_value = nums2.at(mid);
                    if (mid1_value > mid_value)
                        low = mid;
                    else if (mid1_value <= mid_value)
                        high = mid - 1;
                }
                high2 = high;

                //左
                high1 = mid1;
                //low2 等于nums2中第一个大于mid1的
                low = low1;
                high = high1;
                while (low < high)
                {
                    mid = low + (high - low) / 2;
                    mid_value = nums1.at(mid);
                    if (mid2_value >= mid_value)
                        low = mid + 1;
                    else if (mid2_value < mid_value)
                        high = mid;
                }
                low1 = low;
            }
        }
        //得到两个中值
        mid1_value=nums1.at(low1);
        mid2_value=nums2.at(low2);
        if(isodd)
            return (double)mid1_value>mid2_value?mid1_value:mid2_value;
        else
            return (double)(mid1_value+mid2_value);
        return -1;
    }
};

day 2

977. 有序数组的平方

这个也没有难度，首先使用二分找到绝对值最小的数，然后使用双指针双向前进即可。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution
{
public:
    vector<int> sortedSquares(vector<int> &nums)
    {
        //非递减顺序
        //判断是否不存在负数 或者 不存在正数
        //二叉搜索绝对值最小的值 即找到一个正数，且其左边的数为负数，然后两个指针分别指向这两个数
        int low = 0;
        int high = nums.size() - 1;
        int mid;
        vector<int> res;
        //1. 非负
        if (nums.at(0) >= 0)
        {
            for (int i = 0; i <= nums.size() - 1; i++)
                res.push_back(nums.at(i) * nums.at(i));
            return res;
        }
        //2.非正
        if (nums.at(nums.size() - 1) <= 0)
        {
            for (int i = nums.size() - 1; i >= 0; i--)
                res.push_back(nums.at(i) * nums.at(i));
            return res;
        }
        //既有正也有负
        int positive=nums.size()-1;//非负
        int negative=0;//负
        while(positive-negative>1)
        {
            mid=negative+(positive-negative)/2;
            if(nums.at(mid)<0)
                negative=mid;
            else    
                positive=mid;
        }
        while(positive<=nums.size()-1&&negative>=0)
        {
            if(nums.at(positive)+nums.at(negative)>=0)
                res.push_back(nums.at(negative)*nums.at(negative--));
            else
                res.push_back(nums.at(positive)*nums.at(positive++));
        }
        while(positive<=nums.size()-1)
            res.push_back(nums.at(positive)*nums.at(positive++));
        while(negative>=0)
            res.push_back(nums.at(negative)*nums.at(negative--));

        return res;
        
    }
};

189. 旋转数组

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution
{
public:
    void rotate(vector<int> &nums, int k)
    {
        //1. 旋转整体
        //2. 旋转 0 - k-1
        //3. 旋转 k - n-1
        int low = 0;
        int high = nums.size() - 1;
        int temp;
        k = k % nums.size();
        rotate1(nums, low, high);
        rotate1(nums, 0, k - 1);
        rotate1(nums, k, nums.size() - 1);
    }
    void rotate1(vector<int> &nums, int low, int high)
    {
        int temp;
        while (low < high)
        {
            temp = nums.at(low);
            nums.at(low) = nums.at(high);
            nums.at(high) = temp;
            low++;
            high--;
        }
    }
};

day 3

283. 移动零

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution
{
public:
    void moveZeroes(vector<int> &nums)
    {
        int size = nums.size();
        int t1 = 0;
        int t2 = 0;
        while (t2 < size)
        {
            if(nums.at(t2)!=0)
            {
                if(t1!=t2)
                    swap(nums.at(t1),nums.at(t2));
                t1++;
            }
            t2++;
        }
    }
};

167. 两数之和 II - 输入有序数组

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int low=0;
        int high=numbers.size()-1;
        vector<int> res;
        while(1)
        {
            int sum=numbers.at(low)+numbers.at(high);
            if(sum>target)
                high--;
            else if(sum<target)
                low++;
            else
                {
                    res.push_back(low+1);
                    res.push_back(high+1);
                    return res;
                }
        }
        return res;
    }
};

day 4

344. 反转字符串

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    void reverseString(vector<char>& s) {
        int low=0;
        int high=s.size()-1;
        
        while(low<high)
        {
            swap(s.at(low),s.at(high));
            low++;
            high--;
        }
    }
};

557. 反转字符串中的单词 III

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution
{
public:
    string reverseWords(string s)
    {
        int low = 0;
        int high = 0;
        int size = s.length();
        while (high < size)
        {
            low = high;
            while (high < size && s.at(high) != ' ')
                high++;
            //指向空格或者末尾
            //low - high-1
            int i = low;
            int j = high - 1;
            while (i < j)
                swap(s.at(i++), s.at(j--));
            high++;
        }
        return s;
    }
};

day 5

876. 链表的中间结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* middleNode(ListNode* head) {
        //使用两个指针，high每一次前进两步，low每一次前进一步
        ListNode*high=head;
        ListNode*low=head;
        while(high->next!=NULL)
        {
            high=high->next;
            low=low->next;
            high=high->next;
            if(high==NULL)
                return low;
        }
        return low;
    }
};

19. 删除链表的倒数第 N 个结点

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        //遍历一次链表并将指针放入数组中，删除即可
        vector<ListNode*> v;
        ListNode * it=head;
        while(it)
        {
            v.push_back(it);
            it=it->next;
        }
        int count=v.size();
        int index=count-n;
        printf("%d %d \n",count,index);
        if(index==0)
        {
            return head->next;
        }
        if(index==count-1)
        {
            v.at(count-2)->next=NULL;
            return head;
        }
        v.at(index-1)->next=v.at(index+1);
        return head;
    }
};

这种方法太傻了，使用双指针即可

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode*prehead=new ListNode(-1,head);
        ListNode*high=prehead;
        ListNode*low=prehead;
        //head向前前进n步之后再同步前进
        for(int i=1;i<=n+1;i++)
            high=high->next;
        //同步前进到high指向null时，low指向要删除的节点
        //为了让low指向要删除节点的前一个结点，high需要再向前走一个步 n+1
        while(high!=NULL)
        {
            high=high->next;
            low=low->next;
        }
        low->next=low->next->next;
        return prehead->next;
    }
};

但事实上由于双指针法需要大量的访问内存，这导致其访问内存的次数是方法一的一倍多，故其速度并不快。内存真的好慢。

day 6

3. 无重复字符的最长子串

code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        //最长不重复子串
        // dp[n] 代表以 第n个字符结尾的最长不重复 dp[i]= 向前数 ， 前进量 w=dp[i-1] 向前遍历 若某个字符等于cur则break,否则前尽量每一步减一并和当前遍历到的字符的前向数比较去最小值，知道w==0
        // 或者到达最前面的字符

        int len=s.length();
        if(len==0)
            return 0;
        vector<int> dp;
        dp.push_back(1);
        int max=1;
        for(int i=1;i<=len-1;i++)
        {
            //i指向当前计算的字符
            char cur=s.at(i);
            int it=i-1;
            int w=dp.at(i-1);//前进量，代表可以向前走几步
            int length;
            while(w>0&&it>=0)
            {
                w=w<dp.at(it)?w:dp.at(it);
                if(s.at(it)==cur)
                {
                    //相等则说明到达了可以达到的最前端，退出。 it指向第一个不可以归属于以i结尾的最长不重复字串，求长度即可
                    //length=i-it;
                    break;
                }
                w--;
                it--;
            }
            //it指向第一个不可以归属于以i结尾的最长不重复字串，求长度即可
            length=i-it;
            dp.push_back(length);
            max=length>max?length:max;
        }
        return max;
    }   
};

567. 字符串的排列

文章作者: 崔文耀
文章链接: http://myblog.cuimouren.cn
版权声明: 本博客所有文章除特別声明外，均采用 CC BY 4.0 许可协议。转载请注明来源 崔文耀 !
leedcode
  目录