leetcode热题100题

发表于 更新于 分类于 阅读次数： Changyan： 本文字数： 489 阅读时长 ≈ 2 分钟

该篇是关于LeetCode的热题100题

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

题——简单

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

示例 1:

1
2
3
输入: s = "abcabcbb"
输出: 3 
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。

示例 2:

1
2
3
4
输入: s = "pwwkew"
输出: 3
解释: 因为无重复字符的最长子串是 "wke"，所以其长度为 3。
     请注意，你的答案必须是 子串 的长度，"pwke" 是一个子序列，不是子串。

解题

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        record = set()
        l = 0
        res = 0
        for r in range(len(s)):
            while s[r] in record:
                record.remove(s[l])
                l += 1
            record.add(s[r])
            res = res if r - l + 1 < res else r - l + 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> record = new HashMap<>(); //记录已遍历的最长不重复连续子串
        // 定义滑动窗口
        int l = 0;
        int r;
        int res = 0;
        for (r = 0; r < s.length(); r++){ //遍历字符
            // 判断是否已记录，如果没有则添加，如果有，则在记录中删除并滑动left
            while(record.containsKey(s.charAt(r))){ // 有，删除并滑动窗口
                record.remove(s.charAt(l));
                l += 1;
            }
            record.put(s.charAt(r), r);
             // 已记录的和当前的滑动窗口长度选择较大的
             res = r - l + 1 < res ? res : r - l + 1;
        }
        return res;
    }
}

283. 移动零

题——简单

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

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

示例 2:

1
2
输入: nums = [0]
输出: [0]

解题

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def moveZeroes(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        # 情景想象：一列座位补座位
        front_zero_idx = 0 # 假设第一个元素（索引为0）的值为零的情况->>当假设失败那就跟自己交换
        for not_zero_idx in range(len(nums)): 
            if nums[not_zero_idx]!=0: # 找最前面的一个非零元素(定位)
                nums[not_zero_idx], nums[front_zero_idx] = nums[front_zero_idx], nums[not_zero_idx]# 跟最前面元素为零的进行交换
                front_zero_idx += 1 # 最前面的零元素索引改变（后移）


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 void moveZeroes(int[] nums) {
        // 找到最前面的一个非零，跟第一个零进行交换，交换后第一个零就要变化（使用假设最好）
        
        int frontZeroIdx = 0;// 假设第一个元素就是零

        // 找到最前面的一个非零
        int temp = 0;
        for (int NotZeroIdx=0; NotZeroIdx < nums.length; NotZeroIdx++ ){

            //定位到最前面一个的非零元素
            if (nums[NotZeroIdx]!=0){

                //跟第一个零进行交换 使用临时变量 int temp = 0;
                temp = nums[NotZeroIdx];
                nums[NotZeroIdx] = nums[frontZeroIdx]; //零放后
                nums[frontZeroIdx] = temp; //非零放前

                // 交换后第一个零就要变化，非零索引的状况，交换后零元素索引也应当后移
                frontZeroIdx++;
            }
        }
    }
}

438. 找到字符串中所有字母异位词

题——中等

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

示例 1:

1
2
3
4
5
输入: s = "cbaebabacd", p = "abc"
输出: [0,6]
解释:
起始索引等于 0 的子串是 "cba", 它是 "abc" 的异位词。
起始索引等于 6 的子串是 "bac", 它是 "abc" 的异位词。

示例 2:

1
2
3
4
5
6
输入: s = "abab", p = "ab"
输出: [0,1,2]
解释:
起始索引等于 0 的子串是 "ab", 它是 "ab" 的异位词。
起始索引等于 1 的子串是 "ba", 它是 "ab" 的异位词。
起始索引等于 2 的子串是 "ab", 它是 "ab" 的异位词。

解题

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def lengthOfLongestSubstring(self, s: str) -> int:
        record = set()
        l = 0
        res = 0
        for r in range(len(s)):
            while s[r] in record:
                record.remove(s[l])
                l += 1
            record.add(s[r])
            res = res if r - l + 1 < res else r - l + 1
        return res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int lengthOfLongestSubstring(String s) {
        Map<Character, Integer> record = new HashMap<>(); //记录已遍历的最长不重复连续子串
        // 定义滑动窗口
        int l = 0;
        int r;
        int res = 0;
        for (r = 0; r < s.length(); r++){ //遍历字符
            // 判断是否已记录，如果没有则添加，如果有，则在记录中删除并滑动left
            while(record.containsKey(s.charAt(r))){ // 有，删除并滑动窗口
                record.remove(s.charAt(l));
                l += 1;
            }
            record.put(s.charAt(r), r);
             // 已记录的和当前的滑动窗口长度选择较大的
             res = r - l + 1 < res ? res : r - l + 1;
        }
        return res;
    }
}

最大子数组和

题——中等

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

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

示例 1:

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

示例 2:

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

解题

方法1：直接暴力遍历枚举

时间复杂度为$O(n^2)$，空间复杂度为$O(1)$

方法2：新建数组用于记录遍历的当前元素对于的最大连续序列和

方法3：对方法2优化

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def maxSubArray(self, nums: List[int]) -> int:
        # 新建数组用于记录遍历的当前元素对于的最大连续序列和
        n = len(nums)
        temp = [0] * n  # 数组用于记录遍历的当前元素对于的最大连续序列和
        max_res = nums[0] # 最大和
        for i in range(n):
            if i > 0 and temp[i -1] >= 0:
                temp[i] = temp[i - 1] + nums[i]
            else:
                temp[i] = nums[i]
            max_res = max_res if max_res > temp[i] else temp[i]
        return max_res
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxSubArray(int[] nums) {
        int n = nums.length;
        int max_res = nums[0];
        int[] temp = new int[n];
        for (int i = 0; i < n; i++){
            if (i > 0 && temp[i - 1] >= 0){
                temp[i] = temp[i - 1] + nums[i];
            }else{
                temp[i] = nums[i];
            }
            max_res = max_res > temp[i] ? max_res : temp[i];
        }
        return max_res;
    }
}