Two Pointers Problems

Made by Mike_Zhang

数据结构与算法题主题：

Valid Palindrome II

LeetCode Problem #680

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 size = s.length();
        if (size == 1){
            return true;
        }
        int front = 0;
        int end = size-1;
        while (front < end) {
            if (s.charAt(front) != s.charAt(end)) {
                return isPalindrome(s,front, end-1) || isPalindrome(s,front+1,end);
            }
            front++;
            end--;
        }
        return true;
    
    }
    private boolean isPalindrome(String inStr, int i, int j) {
        while (i<j) {
            if (inStr.charAt(i) != inStr.charAt(j)) {
                return false;
            }
            i++;
            j--;
        }
        return true;
    }
}

Number of Segments in a String

LeetCode Problem #434

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
class Solution {
    public int countSegments(String s) {
        
        // M2: to check the beginning of a segment, 1) space + nonspace, or 2) i=0 + nonspace;
        int out = 0;
        int size = s.length();
        for (int i=0;i<size;i++) {
            if ((i==0 && s.charAt(i) != ' ') || s.charAt(i) != ' ' && s.charAt(i-1) == ' ') {
                out++;
            }
        }
        return out;
        
        
        // M1: two pointer to locate a segment
        // int size = s.length();
        // int slow = 0;
        // int out = 0;
        // for (int i=0;i<size;i++) {
        //     char fastChar = s.charAt(i);
        //     char slowChar = s.charAt(slow);
        //     if (fastChar == ' ') {
        //         slow = i+1;
        //     }
        //     if ((fastChar == ' ' && slowChar != ' ') || i == size-1 && slowChar != ' ') {
        //         out++;
        //     }
        // }
        // return out;
    }
}

Intersection of Two Arrays II

LeetCode Problem #350

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 int[] intersect(int[] nums1, int[] nums2) {
        
        // M1 HashMap
        HashMap<Integer,Integer> hs = new HashMap<>();
        for (int i: nums1) {
            if (hs.containsKey(i)) {
                int temp = hs.get(i);
                hs.put(i,temp+1);
            }
            else {
                hs.put(i,1);
            }
            
        }
        
        List<Integer> out = new ArrayList<>();
        
        for (int j: nums2) {
            if (hs.containsKey(j) && hs.get(j)>0) {
                out.add(j);
                int temp = hs.get(j);
                hs.put(j,temp-1);
            }
        }
        
        int size = out.size();
        int[] outArr = new int[size];
        int k = 0;
        for (Integer s:out) {
            outArr[k] = s;
            k+=1;
        }
        return outArr;
    }
}

2022-10-05

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
class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        // M2 Sort & Two Pointer
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        
        List<Integer> out = new ArrayList<>();
        
        int s1 = nums1.length;
        int s2 = nums2.length;
        
        int p1 = 0;
        int p2 = 0;
        
        while (p1<s1 && p2<s2) {
            if (nums1[p1]==nums2[p2]) {
                out.add(nums1[p1]);
                p1++;
                p2++;
            }
            else if (nums1[p1]<nums2[p2]) {p1++;}
            else {p2++;}
        }
        int size = out.size();
        int[] outArr = new int[size];
        int k = 0;
        for (Integer s:out) {
            outArr[k] = s;
            k+=1;
        }
        return outArr;
    }
}

2022-10-06

Assign Cookies

LeetCode Problem #455

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 findContentChildren(int[] g, int[] s) {
        Arrays.sort(g);
        Arrays.sort(s);
        int sizeG = g.length;
        int sizeS = s.length;
        int ptrG = 0;
        int ptrS = 0;
        int out = 0;
        while (ptrG < sizeG && ptrS < sizeS) {
            if (g[ptrG] <= s[ptrS]) {
                ptrG++;
                ptrS++;
                out++;
            }
            else {
                ptrS++;
            }
        }
        return out;
    }
}

2022-10-07

Count Binary Substrings

LeetCode Problem #696

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
class Solution {
    public int countBinarySubstrings(String s) {
        
        // 
        int curr = 1, prev = 0, ans = 0;
        for (int i = 1; i < s.length(); i++)
            if (s.charAt(i) == s.charAt(i-1)) curr++;
            else {
                ans += Math.min(curr, prev);
                prev = curr;
                curr = 1;
            }
        return ans + Math.min(curr, prev);
        
        // TL
//         int size = s.length();
//         int count = 0;
//         for (int i=0;i<size;i++) {
//             int nE = 1;
//             int nD = 0;
//             int fast = i+1;
//             while (fast<size && nE > nD && (size-fast)>=nE) {
//                 if (s.charAt(fast) == s.charAt(i)) {
//                     if (nD>0) {break;}
//                     nE++;
//                 }
//                 else {nD++;}
//                 fast++;
//             }
//             if ((nE>0 || nD>0) && nE == nD) {count++;}
            
//         }
//         return count;
    }
}

2022-10-16

Reverse Only Letters

LeetCode Problem #917

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
class Solution {
    public String reverseOnlyLetters(String s) {
        char[] c = s.toCharArray();
        int size = s.length();
        int front = 0;
        int end = size-1;
        while (front<end) {
            if (((c[front]>='A' && c[front]<='Z') || (c[front]>='a' && c[front]<='z')) &&
                ((c[end]>='A' && c[end]<='Z') || (c[end]>='a' && c[end]<='z'))) {
                char temp = c[front];
                c[front] = c[end];
                c[end] = temp;
                front++;
                end--;
            }
            else if (c[front]<'A' || (c[front] > 'Z' && c[front]<'a') || c[front]>'z') {
                front++;
            }
            else if (c[end]<'A' || (c[end] > 'Z' && c[end]<'a') || c[end]>'z') {
                end--;
            }
        }
        return new String(c);
    }
}

2022-10-21

Long Pressed Name

LeetCode Problem #925

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
47
class Solution {
    public boolean isLongPressedName(String name, String typed) {
        if (name.charAt(0) != typed.charAt(0)) {
            return false;
        }
        
        // Using two pointer to check until one to the end
        int left = 1;
        int right = 1;
        while (left<name.length() && right<typed.length()) {
            if (name.charAt(left) == typed.charAt(right)) {
                left++;
                right++;
            }
            else if (typed.charAt(right) == typed.charAt(right-1)) {
                right++;
            }
            else {
                return false;
            }
        }
        
        // Both to the end: true
        if (left == name.length() && right == typed.length()) {
            return true;
        }
        
        // typed is to the end only: must false, for the rest of char in name have not been checked yet
        else if (left < name.length() && right == typed.length()) {
            return false;
        }
        
        // name is to the end. 
        // Now to check whether the rest of char in typed are the chars as same as the last one
        else if (left == name.length() && right < typed.length()) {
            while (right < typed.length()) {
                if (typed.charAt(right) == typed.charAt(right-1)) {
                    right++;
                }
                else {
                    return false;
                }
            }
        }
        return true;
    }
}

2022-10-22

Max Consecutive Ones II

LeetCode Problem #487

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
class Solution {
    public int findMaxConsecutiveOnes(int[] nums) {
        // M1: Two pointer
        int size = nums.length;
        int slow = 0;
        int fast = 0;
        int nextFast = 0;
        boolean fliped = false;
        int out = 0;
        while (fast<size) {
            if (nums[fast] == 0 && !fliped) {
                fliped = true;
                nextFast = fast;
            }
            else if (nums[fast] == 0 && fliped) {
                int temp = fast-slow;
                out = Math.max(temp,out);
                slow = nextFast+1;
                fliped = false;
                fast = nextFast+1;
                continue;
            }
            fast++;
        }
        return Math.max(fast-slow,out);
    }
}
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 findMaxConsecutiveOnes(int[] nums) {
        // M2: DP
        int max = 0;
        int curr = 0; // #of ones after prev 0
        int prev = 0; // #of ones before prev 0
        int seenZero = 0; // whether see a zero

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] == 0) { // if see a zero
                seenZero = 1; // see
                prev = curr; // now become the past
                curr = 0; // new start
            } else {
                curr++; // else keep life going on
            }

            max = Math.max(max, curr + prev + seenZero); // now + past +(allow one miss)
        }
        return max;
    }
}

2022-11-10

Longest Substring Without Repeating Characters

LeetCode Problem #3

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
class Solution {
    public int lengthOfLongestSubstring(String s) {
        
        // M1
        int size = s.length();
        int fast = 0;
        int slow = 0;
        int max = 0;
        Set<Character> hs = new HashSet<>();
        while (fast<size) {
            char c = s.charAt(fast);
            if (hs.contains(c)) {
                hs.clear();
                slow++;
                fast=slow;
            }
            else {
                hs.add(c);
                max = Math.max(max,hs.size());
                fast++;
            }
        }
        return max;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int lengthOfLongestSubstring(String s) {

        // M2
        final int n = s.length();
        int len = 0;
        int [] repeat = new int[128];
        for (int c = 0, j = 0, i = 0; j < n; j++) {
            c = s.charAt(j);
            i = Math.max(repeat[c], i);
            len = Math.max(len, j - i +1);
            repeat[c] = j+1;
        }
        return len;
    }
}

2022-11-25

Last updated on 2022-11-25

References

Two Pointers - LeetCode

写在最后

Two Pointers相关的知识会继续学习，继续更新.
最后，希望大家一起交流，分享，指出问题，谢谢！

原创文章，转载请标明出处
Made by Mike_Zhang




感谢你的支持
Data Structure and Algorithm > Problem Set
#Java #Two Pointers
Two Pointers Problems
https://ultrafish.io/post/two-pointers-problems/
Author
Mike_Zhang
Posted on
November 25, 2022
Licensed under