Posted Updated LeetCode / Medium2 minutes read (About 235 words)

567. Permutation in String

问题
Given two strings s1 and s2, return true if s2 contains a permutation of s1, or false otherwise.

In other words, return true if one of s1’s permutations is the substring of s2.

将要查找的组合加入数组，数值为字符出现的次数。
滑动窗口，入窗口对应的元素数值-1，出窗口对应的元素数值+1。
每次移动窗口都检验一次数组的数值是否全部为0，如果是真，则返回真。
小技巧：直接用数组来记录字符出现的次数，用字符减去与’a’的差作为下标。

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 boolean checkInclusion(String s1, String s2) {
        if (s1.length() > s2.length()){
            return false;
        }
        
        int[] dic = new int[26];
        for (int i = 0; i < s1.length(); i++){
            dic[s1.charAt(i)-'a']++;
            dic[s2.charAt(i)-'a']--;
        }
 
        int i = 0;
        int j = s1.length();
        
        while( j < s2.length() ){
            if ( allZero(dic) ){
                return true;
            }
            dic[s2.charAt(i)-'a']++;
            dic[s2.charAt(j)-'a']--;
            i++;
            j++;
        }
        return allZero(dic);
    }
    
    private boolean allZero(int[] dic){
        for (int num : dic){
            if ( num != 0 ){
                return false;
            }
        }
        return true;
    }
}
3. Longest Substring Without Repeating Characters
Posted Updated LeetCode / Medium / 复习2 minutes read (About 355 words)

3. Longest Substring Without Repeating Characters

Question

Given a string s, find the length of the longest substring without repeating characters.

Solution 1

滑动窗口加数组统计。
用一个数组bin[]记录各个字符的访问情况。（数组尺寸由字符串的总数决定）

当指针j第一次遍历到一个字符时，如果该字符对应的位置为0，则将其设置为1。
否则对前面的i指针进行遍历，并将i经过的位置重新设置为0。如果i的字符与当前j字符相等，则将bin[index]设置为0，计算当前的长度j-i并更新最大值best。

Code

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
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int best = 0, i = 0, j = 0;
        char[] word = s.toCharArray();
        int[] bin = new int[128];
        while(j < s.length()){
            int index = word[j] - ' ';
            if(bin[index] == 0){
                bin[index] = 1;
                j++;
            }
            else{
                while(i < j){
                    int temp = word[i] - ' ';
                    if(temp == index && bin[index] == 1){
                        bin[index] = 0;
                        best = Math.max(best, j - i);
                        i++;
                        break;
                    }
                    bin[temp] = 0;
                    i++;
                }
            }
            best = Math.max(best, j - i);
        }
        return best;
    }
}

Solution 2

滑动窗口，哈希表记录访问过的字符的元素。
如果重复，则放弃前一个重复的字符，更新左指针。
注意：只有在新指针大于现有指针时才更新！

Code

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
class Solution {
    public int lengthOfLongestSubstring(String s) {
        int best = 0;
        int i = 0;
        int j = 0;
        
        HashMap<Character, Integer> map = new HashMap<Character, Integer>();
        
        while ( j < s.length() ){
            char curChar = s.charAt(j);
            if ( !map.containsKey(curChar) ){
                map.put( curChar, j );
            }
            else{
                if ( map.get(curChar) + 1 > i){
                    i = map.get(curChar) + 1;
                }

                map.put( curChar, j );
            }
            
            if ((j - i + 1) > best){
                best = (j - i + 1);
            }
            j++;
        }
        return best;
    }
}
Posted Updated LeetCode / Easya minute read (About 189 words)

1046. Last Stone Weight

问题
You are given an array of integers stones where stones[i] is the weight of the ith stone.

We are playing a game with the stones. On each turn, we choose the heaviest two stones and smash them together. Suppose the heaviest two stones have weights x and y with x <= y. The result of this smash is:

  • If x == y, both stones are destroyed, and
  • If x != y, the stone of weight x is destroyed, and the stone of weight y has new weight y - x.
    At the end of the game, there is at most one stone left.

Return the smallest possible weight of the left stone. If there are no stones left, return 0.

采用PriorityQueue队列，将所有元素放入。
每次取出两个，将两者的差值放回队列。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int lastStoneWeight(int[] stones) {
        PriorityQueue<Integer> pq = new PriorityQueue<Integer>(Collections.reverseOrder());
        for (int stone : stones){
            pq.add(stone);
        }
        
        while ( pq.size() > 1) {
            int largeStone = pq.poll();
            int smallStone = pq.poll();
            pq.add( largeStone - smallStone );
        }
        
        return pq.poll();
    }
}
Posted Updated LeetCode / Easy / 复习a minute read (About 144 words)

680. Valid Palindrome II

问题
Given a string s, return true if the s can be palindrome after deleting at most one character from it.

双指针，字符串两边对比。
如果两边字符不相等，则更新两边指针，并分别传入辅助方法再次对比。
两个结果有一个是true则返回true。

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
class Solution {
    public boolean validPalindrome(String s) {
        int left = 0;
        int right = s.length() - 1;
        
        while (left < right){
            if (s.charAt(left) == s.charAt(right) ){
                left++;
                right--;
            }
            else{
                return ( checkPalindrome(s, left+1, right) || checkPalindrome(s, left, right-1));
            }
        }
        return true;
    }
    private boolean checkPalindrome(String s, int left, int right){
        while (left < right){
            if (s.charAt(left)==s.charAt(right)){
                left++;
                right--;
            }
            else{
                return false;
            }
        }
        return true;
    }    
}
Posted Updated LeetCode / Mediuma minute read (About 166 words)

19. Remove Nth Node From End of List

问题
Given the head of a linked list, remove the nth node from the end of the list and return its head.


双指针，同时记录前n个节点和当前节点。
当前指针到链表尾部时，删除前面的指针，注意处理edge cases。

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode preNode = null;
        ListNode removedNode = head;
        ListNode fastNode = head;
        for ( int i = 0; i < n; i++ ){
            fastNode = fastNode.next;
        }
        
        while ( fastNode != null ){
            fastNode = fastNode.next;
            preNode = removedNode;
            removedNode = removedNode.next;
        }
        
        if ( removedNode == head ){
            head = head.next;
        }
        else if ( removedNode.next == null){
            preNode.next = null;
        }
        else{
            preNode.next = removedNode.next;
        }
        
        return head;
    }
}
Follow

Recents

Archives

Links

×