LeetCode Hot 100 (5) 普通数组

小帅 1/6/2024 LeetCode

# 53. 最大子数组和 (opens new window)

题目：

给你一个整数数组 nums ，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例 1：

输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

1
2
3

示例 2：

输入：nums = [1]
输出：1

1
2

示例 3：

输入：nums = [5,4,-1,7,8]
输出：23

1
2

提示：

1 <= nums.length <= 105
-10^4 <= nums[i] <= 10^4

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。

思路：

dp类型问题 dp[i]表示以nums[i]结尾的连续数组的最大和 dp[i] = max(dp[i-1]+nums[i], nums[i])

代码：

C++代码

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n = nums.size();
        vector<int> dp(n);
        dp[0] = nums[0];
        int res = dp[0];
        for(int i=1;i<n;i++) {
            dp[i] = max(dp[i-1]+nums[i],nums[i]);
            res = max(res, dp[i]);
        }
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14

Go代码

func maxSubArray(nums []int) int {
    n := len(nums)
    dp := make([]int,n)
    dp[0] = nums[0]
    res := dp[0]
    for i:=1;i<n;i++ {
        dp[i] = max(dp[i-1]+nums[i],nums[i])
        res = max(res,dp[i])
    }
    return res
}

1
2
3
4
5
6
7
8
9
10
11

# 56. 合并区间 (opens new window)

题目：

以数组 intervals 表示若干个区间的集合，其中单个区间为 intervals[i] = [starti, endi] 。请你合并所有重叠的区间，并返回一个不重叠的区间数组，该数组需恰好覆盖输入中的所有区间。

示例 1：

输入：intervals = [[1,3],[2,6],[8,10],[15,18]]
输出：[[1,6],[8,10],[15,18]]
解释：区间 [1,3] 和 [2,6] 重叠, 将它们合并为 [1,6].

1
2
3

示例 2：

输入：intervals = [[1,4],[4,5]]
输出：[[1,5]]
解释：区间 [1,4] 和 [4,5] 可被视为重叠区间。

1
2
3

提示：

1 <= intervals.length <= 10^4
intervals[i].length == 2
0 <= starti <= endi <= 10^4

思路：

现根据起始位置对数组排序然后分三种情况讨论

代码：

C++代码

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

Go代码

func merge(intervals [][]int) [][]int {
    n := len(intervals)
    res := make([][]int,0);
    st, ed := -1, -1
    sort.Slice(intervals,func(i int, j int) bool {
        return intervals[i][0]<intervals[j][0]
    })
    for i:=0;i<n;i++ {
        if intervals[i][0]>ed {
            if ed!=-1 {
                res = append(res,[]int{st,ed})
            }
            st = intervals[i][0]
            ed = intervals[i][1]
        } else {
            ed = max(ed,intervals[i][1])
        }
    }
    if ed!=-1 {
        res = append(res,[]int{st,ed})
    }
    return res
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

# 189. 轮转数组 (opens new window)

题目：

给定一个整数数组 nums，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

1
2
3
4
5
6

示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

1
2
3
4
5

提示：

1 <= nums.length <= 105
-2^31 <= nums[i] <= 2^31 - 1
0 <= k <= 10^5

进阶：

尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的原地算法解决这个问题吗？

思路：

先反转整个数组，再反转前半部分，再反转后半部分

代码：

C++代码

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n = nums.size();
        int t = k % n;
        reverse(nums.begin(),nums.end());
        reverse(nums.begin(),nums.begin()+t);
        reverse(nums.begin()+t,nums.end());
    }
};

1
2
3
4
5
6
7
8
9
10

Go代码

func rotate(nums []int, k int)  {
    n := len(nums) 
    t := k % n
    reverse(nums)
    reverse(nums[:t])
    reverse(nums[t:])
}

func reverse(nums []int) {
    l, r := 0, len(nums)-1
    for l<r {
        nums[l], nums[r] = nums[r], nums[l]
        l++
        r--
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

# 238. 除自身以外数组的乘积 (opens new window)

题目：

给你一个整数数组 nums，返回数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内。

请不要使用除法，且在 O(n) 时间复杂度内完成此题。

示例 1:

输入: nums = [1,2,3,4]
输出: [24,12,8,6]

1
2

示例 2:

输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

1
2

提示：

2 <= nums.length <= 10^5
-30 <= nums[i] <= 30
保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位整数范围内

进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（出于对空间复杂度分析的目的，输出数组不被视为额外空间。）

思路：

前后缀积先预处理出res[i]表示索引i左侧的数的乘积，然后从后往前遍历的过程中求出来最终结果。

代码：

C++代码

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        int n = nums.size();
        vector<int> res(n);
        //res[i]表示索引为i左侧的所有数的乘积
        res[0] = 1;
        for(int i=1;i<n;i++) {
            res[i] = nums[i-1]*res[i-1];
        }
        int t = 1;
        for(int i=n-1;i>=0;i--) {
            res[i] = res[i]*t;
            t *= nums[i];
        }
        return res;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

Go代码

func productExceptSelf(nums []int) []int {
    n := len(nums)
    res := make([]int,n)
    res[0] = 1
    for i:=1;i<n;i++ {
        res[i] = res[i-1]*nums[i-1]
    }
    t := 1
    for i:=n-1;i>=0;i-- {
        res[i] = res[i] * t
        t *= nums[i]
    }
    return res
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 41. 缺失的第一个正数 (opens new window)

题目：

给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。

请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。

示例 1：

输入：nums = [1,2,0]
输出：3

1
2

示例 2：

输入：nums = [3,4,-1,1]
输出：2

1
2

示例 3：

输入：nums = [7,8,9,11,12]
输出：1

1
2

提示：

1 <= nums.length <= 5 * 10^5
-2^31 <= nums[i] <= 2^31 - 1

思路：

第0个位置应该放1，第1个位置应该放2..... 所以当nums[i]>=1并且小于等于n时，它的位置应该是nums[i]-1

代码：

C++代码

class Solution {
public:
    int firstMissingPositive(vector<int>& nums) {
        int n = nums.size();
        for(int i=0;i<n;i++) {
            while(nums[i]>=1&&nums[i]<=n&&nums[i]!=nums[nums[i]-1]) {
                swap(nums[i],nums[nums[i]-1]);
            } 
        }
        for(int i=0;i<n;i++) {
            if(nums[i]!=i+1) {
                return i+1;
            }
        }
        return n+1;
    }
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

Go代码

func firstMissingPositive(nums []int) int {
    n := len(nums) 
    for i:=0;i<n;i++ {
        for nums[i]>=1&&nums[i]<=n&&nums[i]!=nums[nums[i]-1] {
            nums[i],nums[nums[i]-1] = nums[nums[i]-1], nums[i]
        }
    }
    for i:=0;i<n;i++ {
        if nums[i]!=i+1 {
            return i+1
        }
    }
    return n+1
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14

小帅的博客

Choose mode