Posted Updated LeetCode / Medium / 复习2 minutes read (About 307 words)

438. Find All Anagrams in a String

Given two strings s and p, return an array of all the start indices of p’s anagrams in s. You may return the answer in any order.

An Anagram is a word or phrase formed by rearranging the letters of a different word or phrase, typically using all the original letters exactly once.

滑动窗口。采用两个数组分别计算两个字符串中字符出现的数量。

滑动窗口时，维护数组中字符串中字符出现的次数。
循环，判断两个字符串是否相等，如果相等，则将当前的左指针添加进答案。
移动窗口的左右指针，在数组中减少前一项出现的次数，增加后一项出现的次数。

通过维护一个表示两个字符串中字符差值的数组，可以将算法优化算法，而不必进行两个数组的比较。

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
class Solution {
    public List<Integer> findAnagrams(String s, String p) {        
        List<Integer> ans = new ArrayList();
        if(p.length()>s.length()){
            return ans;
        }
        
        int[] alphabet = new int[26];
        int[] window = new int[26];
        
        for(int i = 0; i < p.length(); i++){
            alphabet[p.charAt(i) - 'a']++;
            window[s.charAt(i) - 'a']++;
        }
        
        int i = 0;
        int j = p.length();
        
        while(j < s.length()){
            if(Arrays.equals(alphabet, window)){
                ans.add(i);
            }
            window[s.charAt(i) - 'a']--;
            window[s.charAt(j) - 'a']++;
            i++;
            j++;
        }
        
        if(Arrays.equals(alphabet, window)){
            ans.add(i);
        }
        
        return ans;
        
    }
}
Posted Updated LeetCode / Medium / 复习3 minutes read (About 511 words)

334. Increasing Triplet Subsequence

Given an integer array nums, return true if there exists a triple of indices (i, j, k) such that i < j < k and nums[i] < nums[j] < nums[k]. If no such indices exists, return false.

贪心算法。
将first与second初始化为最大值。
first保存遍历过的最小值。
second保存遍历过的大于之前最小值的最小值。

遍历数组。
条件一：如果数字小于现在第一个值，则更新第一个值。
（此时一定不满足条件二，因此可以安全地更新更小的数字。）
条件二：如果数字大于第一个值，且小于第二个值，则更新第二个值。
（此时第一个值已经被更新过了，满足第一个值小于第二个值。）
条件三：如果数字大于第二个值，则返回true。
（此时两个值一定都被更新过了，满足第一个值小于第二个值小于第三个值。）

注意：
更新first后，second不会更新，但是second的存在可以确保曾经存在first小于second。
如果此时数字大于second，则数组中存在Triplet Subsequence。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean increasingTriplet(int[] nums) {
        int first = Integer.MAX_VALUE;
        int second = Integer.MAX_VALUE;
        
        for(int num : nums){
            if(num < first){
                first = num;
            }
            else if(num > first && num < second){
                second = num;
            }
            else if(num > second){
                return true;
            }   
        }
        return false;
    }
}

双向遍历，逐渐收紧搜索窗口。设置i，k两个指针分别在头尾。
当nums[j] <= nums[i]，则更新i指针为j。
当nums[j] >= nums[k]，则更新k指针为j。
如果找到符合条件的nums[i] < nums[j] < nums[k]则返回。

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
class Solution {
    public boolean increasingTriplet(int[] nums) {
        boolean flag = true;
        int i = 0;
        int k = nums.length -1 ;
        int j;
        int count = 1;
        
        while(i < k && i + count < k){
            if(flag){
                j = i + count;
                if(nums[i] >= nums[j]){
                    i = j;
                    count = 1;
                    flag = true;
                    continue;
                }
                else if(nums[j] < nums[k]){
                    return true;
                }
                flag = !flag;
            }
            else{
                j = k - count;
                if(nums[k] <= nums[j]){
                    k = j;
                    count = 1;
                    flag = true;
                    continue;
                }
                else if(nums[j] > nums[i]){
                    return true;
                }
                else{
                    count++;
                }
                flag = !flag;
            }
        }
        return false;
    }
}
Posted Updated LeetCode / Medium / 复习4 minutes read (About 534 words)

173. Binary Search Tree Iterator

Implement the BSTIterator class that represents an iterator over the in-order traversal of a binary search tree (BST):

BSTIterator(TreeNode root) Initializes an object of the BSTIterator class. The root of the BST is given as part of the constructor. The pointer should be initialized to a non-existent number smaller than any element in the BST.
boolean hasNext() Returns true if there exists a number in the traversal to the right of the pointer, otherwise returns false.
int next() Moves the pointer to the right, then returns the number at the pointer.
Notice that by initializing the pointer to a non-existent smallest number, the first call to next() will return the smallest element in the BST.

You may assume that next() calls will always be valid. That is, there will be at least a next number in the in-order traversal when next() is called.

此方法不用将所有节点一次性入栈，而是在获得next时更新栈内的节点，因此更省时间。
将根节点的所有左子节点入栈，此时栈顶为最小值。
next方法：返回当前的栈顶节点。如果栈顶节点存在右子节点，则将其所有的左子节点入栈。
hasNext方法：返回栈是否为空的非值。

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class BSTIterator {
    Stack<TreeNode> stack;
    public BSTIterator(TreeNode root) {
        stack = new Stack();
        updateStack(root);
    }
    
    public int next() {
        TreeNode node = stack.pop();
        updateStack(node.right);
        return node.val;
    }
    
    public boolean hasNext() {
        return !stack.isEmpty();
    }
    
    private void updateStack(TreeNode root){
        while(root != null){
            stack.push(root);
            root = root.left;
        }
    }
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator obj = new BSTIterator(root);
 * int param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */

DFS搜索，中序搜索，从右子节点至左子节点，先将所有元素入栈。
next方法：挤出栈顶并返回。
hasNext方法： 返回栈是否为空的非值。

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class BSTIterator {
    Stack<TreeNode> stack;
    public BSTIterator(TreeNode root) {
        stack = new Stack();
        initiateStack(root);
    }
    
    public int next() {
        return stack.pop().val;
    }
    
    public boolean hasNext() {
        return !stack.isEmpty();
    }
    
    private void initiateStack(TreeNode root){
        if(root == null){
            return;
        }
        initiateStack(root.right);
        stack.push(root);
        initiateStack(root.left);
    }
}

/**
 * Your BSTIterator object will be instantiated and called as such:
 * BSTIterator obj = new BSTIterator(root);
 * int param_1 = obj.next();
 * boolean param_2 = obj.hasNext();
 */
Posted Updated LeetCode / Medium2 minutes read (About 353 words)

986. Interval List Intersections

You are given two lists of closed intervals, firstList and secondList, where firstList[i] = [starti, endi] and secondList[j] = [startj, endj]. Each list of intervals is pairwise disjoint and in sorted order.

Return the intersection of these two interval lists.

A closed interval [a, b] (with a <= b) denotes the set of real numbers x with a <= x <= b.

The intersection of two closed intervals is a set of real numbers that are either empty or represented as a closed interval. For example, the intersection of [1, 3] and [2, 4] is [2, 3].

设置两个指针，分别指向两个intervals的头部。
循环，相交的left等于两者左端的较大值。right等于两者右端的较小值。
只有在left小于right时，两个interval才相交，填入列表。
然后更新两个interval中右端较小的指针。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        List<int[]> ans = new ArrayList(); 
        int i = 0;
        int j = 0;
        
        while(i < firstList.length && j < secondList.length){
            int left = Math.max( firstList[i][0], secondList[j][0] );
            int right = Math.min( firstList[i][1], secondList[j][1] );
            if(left <= right){
                ans.add(new int[]{left, right});
            }
            if(firstList[i][1] < secondList[j][1]) i++;
            else j++;

        }
        
        int[][] ret = new int[ans.size()][2];
        ans.toArray(ret);
        return ret;
    }
}
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
class Solution {
    public int[][] intervalIntersection(int[][] firstList, int[][] secondList) {
        int i = 0;
        int j = 0;
        ArrayList<int[]> ans = new ArrayList(); 
        int[] holdA;
        int[] holdB;

        while(i < firstList.length && j < secondList.length){
            holdA = firstList[i];
            holdB = secondList[j];
            
            int[] arr = new int[2];
            
            if(holdA[0] <= holdB[0] && holdA[1] >= holdB[1]){
                ans.add(holdB);
                j++;
            }
            else if(holdA[0] >= holdB[0] && holdA[1] <= holdB[1]){
                ans.add(holdA);
                i++;
            }
            else if(holdA[0] <= holdB[0] && holdA[1] >= holdB[0]){
                arr[0] = holdB[0];
                arr[1] = holdA[1];
                ans.add(arr);
                i++;
            }
            else if(holdA[0] >= holdB[0] && holdB[1] >= holdA[0]){
                arr[0] = holdA[0];
                arr[1] = holdB[1];
                ans.add(arr);
                j++;
            }
            else if(holdA[1] <= holdB[1]){
                i++;
            }
            else{
                j++;
            }
        }
        int[][] ret = new int[ans.size()][2];
        ans.toArray(ret);
        return ret;
    }
}
Posted Updated LeetCode / Medium / 复习2 minutes read (About 334 words)

844. Backspace String Compare

Given two strings s and t, return true if they are equal when both are typed into empty text editors. '#' means a backspace character.

Note that after backspacing an empty text, the text will continue empty.

辅助方法getNextValid，返回下一个有效值。
将两个指针分别设置在两个字符串的尾部。
当两指针有一个大于0时，进行循环。
每次都搜索两个指针的下一个有效值。
如果两个指针上的字符不同则返回false。

最后返回两个指针的停留位置是否相同。

注意：
如果有一个字符串指针先更新到0以下，另一个指针仍有可能更新到一个“#”字符位置。
此时最后的结应该是两个空字符串。
因此需要继续循环一次，得出其是否会归到零以下。如果此时归零则两者的指针位置仍然相等。

因此即使getNextValid返回的下一个值为负数也应该保留其数值。

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 boolean backspaceCompare(String s, String t) {
        int i = s.length()-1;
        int j = t.length()-1;

        while(i >= 0 || j >= 0){
            i = getNextValid(s, i);
            j = getNextValid(t, j);
            if( i >= 0 && j >= 0 && s.charAt(i) != t.charAt(j)){    
                return false;
            }
            i--;
            j--;
        }
        return (i == j);
    }
    
    private int getNextValid(String s, int start){
        int i = start;
        int count = 0;
        while(i >= 0 && (s.charAt(i) == '#' || count != 0)){
            if(s.charAt(i) == '#'){
                count++;
            }
            else{
                count--;
            }
            i--;
        }
        return i;
    }
}
Follow

Recents

Archives

Links

×