LeetCode - 灰太狼的狼堡

用于记录个人 LeetCode 刷题集合
目前已收录 8 题

题号题目难度算法

3无重复字符的最长子串Mid滑动窗口

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

思路： 考虑到需要的是无重复字符的子串，那么说明区间 [l, r] 内每个字符只能存在一次。于是可以用哈希表从头到尾记录区间 [l, r] 中每一个字符的出现次数。

如果当前字符（也就是下标 r 处）出现超过一次，那么说明前面肯定已经出现过，此时只需要不断减少下标 l 处字符的计数，同时把 l 往后移，直到下标 r 处字符的数量重新变为 1。这就是滑动窗口的思想。

代码实现：

1
func lengthOfLongestSubstring(s string) int {
2
    cnt := [128]int{}
3
    ans, left := 0, 0
4
    for right, c := range s {
5
        cnt[c]++
6
        for cnt[c] > 1 {
7
            cnt[s[left]]--
8
            left++
9
        }
10
        ans = max(ans, right - left + 1)
11
    }
12
    return ans
13
}

1
class Solution {
2
public:
3
    int lengthOfLongestSubstring(string s) {
4
        std::map<char, int> mp;
5
        int ans = 0, l = 0;
6
        for (int r = 0; r < s.size(); r++) {
7
            mp[s[r]]++;
8
            while (mp[s[r]] > 1) {
9
                mp[s[l]]--;
10
                l++;
11
            }
12
            ans = std::max(ans, r - l + 1);
13
        }
14
        return ans;
15
    }
16
};

11盛最多水的容器Mid双指针

题目链接：盛最多水的容器

给定一个长度为 n 的整数数组 height 。有 n 条垂线，第 i 条线的两个端点是 (i, 0) 和 (i, height[i]) 。

找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

返回容器可以储存的最大水量。

思路： 把问题转换一下，其实就是求 $(r - l) * min(height[l], height[r])$ 的最大值，那么我们只需要双指针跑一遍，每次移动小的指针，如果我们移动的是大的那个指针，min 会减小，而且长度也在减小，所以乘积也会减小，是不合理的。

代码实现：

1
func maxArea(height []int) int {
2
    ans, l, r := 0, 0, len(height) - 1
3
    for l < r {
4
        ans = max(ans, (r - l) * min(height[l], height[r]))
5
        if height[l] < height[r] {
6
            l++
7
        } else {
8
            r--
9
        }
10
    }
11
    return ans
12
}

1
class Solution {
2
public:
3
    int maxArea(vector<int>& height) {
4
        int ans = 0, l = 0, r = height.size() - 1;
5
        while (l < r) {
6
            ans = std::max(ans, (r - l) * std::min(height[l], height[r]));
7
            height[l] < height[r] ? l++ : r--;
8
        }
9
        return ans;
10
    }
11
};

20有效的括号Easy栈

题目链接：有效的括号

给定一个只包括 ’(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
每个右括号都有一个对应的相同类型的左括号。

思路： 维护一个栈，遇到左括号就放入，遇到右括号则看栈顶有没有对应类型的左括号。

代码实现：

1
func isValid(s string) bool {
2
    mp := map[rune]rune{')':'(', ']':'[', '}':'{'}
3
    stk := []rune{}
4
    for _, c := range s {
5
        if mp[c] == 0 {
6
            stk = append(stk, c)
7
        } else {
8
            if len(stk) == 0 || stk[len(stk) - 1] != mp[c] {
9
                return false
10
            }
11
            stk = stk[:len(stk) - 1]
12
        }
13
    }
14
    return len(stk) == 0
15
}

1
class Solution {
2
public:
3
    bool isValid(string s) {
4
        std::unordered_map<char, char> mp = {{')', '('}, {']', '['}, {'}', '{'}};
5
        std::stack<char> st;
6
        for (char c : s) {
7
            if (!mp.contains(c)) {
8
                st.push(c);
9
            } else {
10
                if (st.empty() || st.top() != mp[c]) {
11
                    return false;
12
                }
13
                st.pop();
14
            }
15
        }
16
        return st.empty();
17
    }
18
};

53最大子数组和Mid前缀和 / 贪心

题目链接：最大子数组和

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

代码实现：

1
func maxSubArray(nums []int) int {
2
    ans, sum, pre := math.MinInt, 0, 0;
3
    for _, v := range nums {
4
        sum += v
5
        ans = max(ans, sum - pre)
6
        pre = min(pre, sum)
7
    }
8
    return ans
9
}

1
class Solution {
2
public:
3
    int maxSubArray(vector<int>& nums) {
4
        int ans = INT_MIN, sum = 0, pre = 0;
5
        for (int i = 0; i < nums.size(); i++) {
6
            sum += nums[i];
7
            ans = std::max(sum - pre, ans);
8
            pre = std::min(pre, sum);
9
        }
10
        return ans;
11
    }
12
};

121买卖股票的最佳时机Easy枚举

题目链接：买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择某一天买入这只股票，并选择在未来的某一个不同的日子卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

思路： 根据题意，只能在前面买，后面卖，那么可以维护一个前缀最小值 pfmin，那么答案可能是当前位置的价格减去最小值的差值 prices[i] - pfmin，每次更新取最大值即可。

代码实现：

1
func maxProfit(prices []int) int {
2
    pfmin := prices[0]
3
    ans := 0
4
    for _, v := range prices {
5
        ans = max(ans, v - pfmin)
6
        pfmin = min(pfmin, v)
7
    }
8
    return ans
9
}

1
class Solution {
2
public:
3
    int maxProfit(vector<int>& prices) {
4
        int ans = 0;
5
        int pfmin = prices[0];
6
        for (int i = 0; i < prices.size(); i++) {
7
            ans = max(ans, prices[i] - pfmin);
8
            pfmin = min(pfmin, prices[i]);
9
        }
10
        return ans;
11
    }
12
};

128最长连续序列Mid哈希

题目链接：最长连续序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。

思路： 因为求的是最长连续的序列，序列不考虑顺序，那么我们可以考虑把数组里的数用哈希表存一下，然后我们去遍历整个哈希表，如果当前遍历的数是 x，那么看 x-1 在不在表里，如果在，就 continue，因为以 x-1 为起点一定比 x 优，如果 x-1 不在，设 y=x+1 一直往后看，直到不存在连续的，此时再更新一下答案，取 (ans, y - x) 的最大值，最后遍历完整个哈希表就得到了答案。

代码实现：

1
func longestConsecutive(nums []int) int {
2
    mp := make(map[int]bool)
3
    for _, v := range nums {
4
        mp[v] = true
5
    }
6
    ans := 0
7
    for k := range mp {
8
        if mp[k - 1] {
9
            continue
10
        }
11
        x := k + 1
12
        for mp[x] {
13
            x++
14
        }
15
        ans = max(ans, x - k)
16
    }
17
    return ans
18
}

1
class Solution {
2
public:
3
    int longestConsecutive(vector<int>& nums) {
4
        std::unordered_set<int> st(nums.begin(), nums.end());
5
        int ans = 0;
6
        for (auto &x : st) {
7
            if (st.contains(x - 1)) {
8
                continue;
9
            }
10
            int k = x + 1;
11
            while (st.contains(k)) {
12
                k++;
13
            }
14
            ans = std::max(ans, k - x);
15
        }
16
        return ans;
17
    }
18
};

206反转链表Easy链表

题目链接：反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

思路： 头插法。简单来说就是创建一个空列表，每次把当前节点插入到空列表的头部。

代码实现：

1
/**
2
 * Definition for singly-linked list.
3
 * type ListNode struct {
4
 *     Val int
5
 *     Next *ListNode
6
 * }
7
 */
8
func reverseList(head *ListNode) *ListNode {
9
    var pre, cur *ListNode = nil, head
10
    for cur != nil {
11
        next := cur.Next
12
        cur.Next = pre
13
        pre = cur
14
        cur = next
15
    }
16
    return pre
17
}

1
/**
2
 * Definition for singly-linked list.
3
 * struct ListNode {
4
 *     int val;
5
 *     ListNode *next;
6
 *     ListNode() : val(0), next(nullptr) {}
7
 *     ListNode(int x) : val(x), next(nullptr) {}
8
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
9
 * };
10
 */
11
class Solution {
12
public:
13
    ListNode* reverseList(ListNode* head) {
14
        ListNode* pre = nullptr;
15
        ListNode* cur = head;
16
        while (cur != nullptr) {
17
            ListNode* next = cur->next;
18
            cur->next = pre;
19
            pre = cur;
20
            cur = next;
21
        }
22
        return pre;
23
    }
24
};

283移动零Easy栈/双指针

题目链接：移动零

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

方法一：栈的思想

思路： 把nums数组当作一个栈，那么我们只需要遍历一次，每次遇到非 0 的数就加入到 nums 中，遍历完一次后，我们就已经把非 0 的数都移到了前面，剩下的就都是 0 的数，只需要覆盖一下就好了。

代码实现：

1
func moveZeroes(nums []int)  {
2
    idx := 0
3
    for _, v := range nums {
4
        if v != 0 {
5
            nums[idx] = v
6
            idx++
7
        }
8
    }
9
    clear(nums[idx:])
10
}

1
class Solution {
2
public:
3
    void moveZeroes(vector<int>& nums) {
4
        int idx = 0;
5
        for (auto &i : nums) {
6
            if (i) {
7
                nums[idx++] = i;
8
            }
9
        }
10
        fill(nums.begin() + idx, nums.end(), 0);
11
    }
12
};

方法二：双指针

思路： 方法一在最坏情况下（即 nums 全为 0）需要遍历两次，那么我们有没有一次的方法呢，有的兄弟有的，直接上双指针。

要保持相对顺序不变，那么我们可以维护一个下标为 l 的最左边的 0，r 为当前遍历到的位置，只要这个数不是 0，那么我们就需要交换，这样才能保持相对位置不改变，交换过后那么 l 的下标也会前进一位，此时就是维护了一个 [l, r] 全为 0 的一个区间，如果前面几位没有碰到 0 呢，那么 l 和 r 会一起前进，直到碰到 0 或者到末尾结束。

代码实现：

1
func moveZeroes(nums []int)  {
2
    l := 0
3
    for r, v := range nums {
4
        if v != 0 {
5
            nums[l], nums[r] = v, nums[l]
6
            l++
7
        }
8
    }
9
}

1
class Solution {
2
public:
3
    void moveZeroes(vector<int>& nums) {
4
        int l = 0;
5
        for (int &r : nums) {
6
            if (r != 0) {
7
                std::swap(nums[l], r);
8
                l++;
9
            }
10
        }
11
    }
12
};