8.18刷题

发表于 | 分类于 | 0 comments

第一题 125. Valid Palindrome

题目描述

判断一个字符串是不是回文，忽略所有不是字母和数字的字符。

算法

从后往前即可，注意一下这题的姊妹题，先将指针前后赛跑，然后再进行原地反转，再进行对比，是一道非常好的题目。

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 boolean isPalindrome(String s) {
        if (s.length() == 0)
            return true;
        s = s.toLowerCase();
        int left = 0, right = s.length() - 1;
        while (left < right) {
            while (left < right && (s.charAt(left) < 'a' || s.charAt(left) > 'z') && (s.charAt(left) < '0' || s.charAt(left) > '9'))
                left++;
            while (left < right && (s.charAt(right) < 'a' || s.charAt(right) > 'z') && (s.charAt(right) < '0' || s.charAt(right) > '9'))
                right--;
            if (left >= right)
                return true;
            if (s.charAt(left) == s.charAt(right)) {
                left++;
                right--;
            } else {
                return false;
            }
        }
        return true;        
    }
}

第二题 155. Min Stack

题目描述

设计一个栈，支持在常数时间内push，pop，top，和取最小值。

  • push(x) – 元素x压入栈
  • pop() – 弹出栈顶元素
  • top() – 获取栈顶元素
  • getMin() – 获取栈中的最小值
One Stack
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
public class MinStack {
    int min = Integer.MAX_VALUE;
    Stack<Integer> stack;
    /** initialize your data structure here. */
    public MinStack() {
        stack = new Stack<>();
    }
    public void push(int x) {
        if (x < min) {
            stack.push(min);
            min = x;
        }
        stack.push(x);
    }
    public void pop() {
        int cur = stack.pop();
        if (cur == min)
            min = stack.pop();
    }
    public int top() {
        return stack.peek();
    }
    public int getMin() {
        return min;
    }
}
ListNode
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
class MinStack {
    Node cur;
    public MinStack() {
    }
    public void push(int x) {
        if (cur == null) {
            cur = new Node(x, x);
        } else {
            cur = new Node(x, Math.min(cur.min, x), cur);
        }
    }
    public void pop() {
        cur = cur.next;
    }
    public int top() {
        return cur.val;
    }
    public int getMin() {
        return cur.min;
    }
    private class Node {
        int val;
        int min;
        Node next;
        public Node(int val, int min) {
            this(val, min, null);
        }
        public Node(int val, int min, Node next) {
            this.val = val;
            this.min = min;
            this.next = next;
        }
    }
}

第三题 239. Sliding Window Maximum

题目描述

给定一个数组，一个大小为k的滑动窗口从数组的最左端向最右端移动。你只可以看到窗口中的k个数字。每一次窗口向右边移动一步。

例如，给定数组nums = [1,3,-1,-3,5,3,6,7], k = 3

算法

双端队列

遍历数组nums，使用双端队列deque维护滑动窗口内有可能成为最大值元素的数组下标

由于数组中的每一个元素至多只会入队、出队一次，因此均摊时间复杂度为O(n)

记当前下标为i，则滑动窗口的有效下标范围为[i - (k - 1), i]

若deque中的元素下标＜ i - (k - 1)，则将其从队头弹出，deque中的元素按照下标递增顺序从队尾入队。

这样就确保deque中的数组下标范围为[i - (k - 1), i]，满足滑动窗口的要求。

当下标i从队尾入队时，顺次弹出队列尾部不大于nums[i]的数组下标（这些被弹出的元素由于新元素的加入而变得没有意义）

deque的队头元素即为当前滑动窗口的最大值

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
public class maxSlidingWindow239 {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (k <= 0 || nums.length <= 0)
            return new int[0];
        int[] res = new int[nums.length - k + 1];
        int cur = 0;
        Deque<Integer> dq = new ArrayDeque<>();
        int i = 0;
        while (i < nums.length) {
            while (!dq.isEmpty() && dq.peek() < i - k + 1)
                dq.pollFirst();
            while(!dq.isEmpty() && nums[dq.peekLast()] < nums[i])
                dq.pollLast();
            dq.offerLast(i);
            if (i >= k - 1) {
                res[cur++] = nums[dq.peek()];
            }
            i++;
        }
        return res;
    }
}
Heap
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (k <= 0 || nums.length == 0)
            return new int[0];
        
        int[] res = new int[nums.length - k + 1];
        PriorityQueue<Integer> pq = new PriorityQueue<>((x, y) -> y - x);
        
        for (int i = 0; i < k - 1; i++)
            pq.offer(nums[i]);
        
        int cur = 0;
        for (int i = k - 1; cur < nums.length - k + 1; i++) {
            pq.add(nums[i]);
            res[cur++] = pq.peek();
            pq.remove(nums[i - k + 1]);
        }
        return res;
    }
}

相关问题

Sliding Window的问题：

统一的思路一般有两种:

  • 一种是利用int[256]大小的数组，记录和统计每个字符出现的次数。
  • 另外一种办法是利用hashmap,记录下对应Map<对应数字，出现的位置>来进行窗口的更新
76. Minimum Window Substring hard

在String S中寻找包含最短的包含String T，的子String（不必有顺序）

关键思路，利用char[256]来表示所有String，如果出现过，则加1。通过对String t长度的计数，查看是否已经完全包含，并利用leftPoint和rightPoint对左右节点进行记录

159. Longest Substring with At Most Two Distinct Characters hard

找出至多有两个不同字母的子字符串的长度。

关键思路，利用map记录下出现的字符和其位置，然后出现重复时候进行更新，并实时计算最长的位置

340. Longest Substring with At Most K Distinct Characters hard

找出至多有k个不同字符的子字符串的长度

同上

30. Substring with Concatenation of All Words hard

给定一组words 和一个长String, 找出String中包含所有words的连续String

利用map对每个单词进行计数，然后对每一段查看是否包含全部的单词

[438. Find All Anagrams in a String

](https://leetcode.com/problems/find-all-anagrams-in-a-string/description/) easy

给定一个长String s 和一个短String p, 查看所有包含p的在s中的片段。只需要包含所有字符即可，不要求顺序。

用int[256]进行计数，然后通过计数查看最终结果。