LeetCode雙指針題小總結-(LeetCode344、LeetCode345、LeetCode125、LeetCode167、LeetCode11)(簡單題)

• LeetCode - 344. Reverse String(反轉字元串)
• LeetCode - 345. Reverse Vowels of a String(反轉字元串中的元音字母)
• LeetCode - 125. Valid Palindrome(驗證回文串)
• LeetCode - 167. Two Sum II - Input array is sorted(兩數之和 II - 輸入有序數組)
• LeetCode - 11. Container With Most Water(盛最多水的容器)

LeetCode - 344. Reverse String(反轉字元串)

題目連結

題目

解析

兩種做法:

• 可以使用下标的對應關系，調換

  i

  和

  (len - 1 - i)

  的位置；
• 也可以使用兩個指針

  l

  、

  r

  ，分别指向數組的開始和結尾，然後兩個指針不停的交換對應的字元，并逐漸向中間移動；

class Solution {
    public void reverseString(char[] s) {
        for(int l = 0, r = s.length-1; l < r; l++, r--){
            char tc = s[l];
            s[l] = s[r];
            s[r] = tc;
        }
    }
}
           

class Solution {
    public void reverseString(char[] s) {
        int n = s.length;
        for(int i = 0; i < n/2; i++){
            char tc = s[i];
            s[i] = s[n - i - 1];
            s[n - i - 1] = tc;
        }
    }
}
           

LeetCode - 345. Reverse Vowels of a String(反轉字元串中的元音字母)

題目連結

題目

解析

也是使用兩個指針掃描，從兩邊到中間掃:

• 隻要其中一個不是元音字母，那個指針就往中間移動，繼續下一次循環；
• 隻有兩個都是元音字母，才交換位置；

class Solution {

    public boolean isU(char c) {
        return c == 'a' || c == 'o' || c == 'e' || c == 'u' || c == 'i'
                || c == 'A' || c == 'O' || c == 'E' || c == 'U' || c == 'I';
    }

    public String reverseVowels(String s) {
        char[] str = s.toCharArray();
        for (int l = 0, r = str.length - 1; l < r; ) {
            if (!isU(str[l])) {
                l++;
                continue;
            }
            if (!isU(str[r])) {
                r--;
                continue;
            }
            if (isU(str[l]) && isU(str[r])) {
                char t = str[l];
                str[l] = str[r];
                str[r] = t;
                l++;
                r--;
            }
        }
        return String.valueOf(str);
    }
}
           

LeetCode - 125. Valid Palindrome(驗證回文串)

題目連結

題目

解析

也是使用雙指針，過程和上面的類似，不過要處理一下大小寫和數字的問題；

class Solution {
    
    public boolean isC(char c) {
        return Character.isLetter(c);
    }

    public boolean isD(char c) {
        return Character.isDigit(c);
    }

    public boolean ok(char lc, char rc) {
        return (isD(lc) && isD(rc) && lc == rc) ||
                (isC(lc) && isC(rc) && Character.toLowerCase(lc) == Character.toLowerCase(rc));
    }


    public boolean isPalindrome(String s) {

        boolean flag = true;
        char[] str = s.toCharArray();
        for (int l = 0, r = str.length - 1; l <= r; ) {
            if (!isC(str[l]) && !isD(str[l])) {
                l++;
                continue;

            }
            if (!isC(str[r]) && !isD(str[r])) {
                r--;
                continue;
            }
            if (ok(str[l], str[r])) {
                l++;
                r--;
            } else {
                flag = false;
                break;
            }
        }
        return flag;
    }
}
           

或者更加簡單的寫法:

class Solution {

    public boolean isLD(char c) {
        return Character.isLetterOrDigit(c);
    }

    public boolean isPalindrome(String s) {
        s = s.toLowerCase();

        char[] str = s.toCharArray();

        for (int l = 0, r = str.length - 1; l <= r; ) {
            if (!isLD(str[l]))
                l++;
            else if (!isLD(str[r]))
                r--;
            else if (str[l] != str[r])
                return false;
            else {
                l++;
                r--;
            }
        }
        return true;
    }
}
           

LeetCode - 167. Two Sum II - Input array is sorted(兩數之和 II - 輸入有序數組)

題目連結

題目

解析

兩種做法：

• 對于每一個

  arr[i]

  ，在後面的有序數組中二分查找有沒有可以比對的，時間複雜度

  n * logn

  ；
• 使用雙指針，因為是有序的，是以可以通過比較大小決定哪個指針的移動，時間複雜度

  n

  ；

class Solution {
    //n * logn
    public int[] twoSum(int[] numbers, int target) {
        for (int i = 0; i < numbers.length; i++) {
            // binary search
            int L = i + 1, R = numbers.length - 1;
            while (L <= R) {
                int mid = L + (R - L) / 2;
                if (numbers[mid] + numbers[i] == target)
                    return new int[]{i + 1, mid + 1};
                else if (numbers[mid] + numbers[i] < target)
                    L = mid + 1;
                else
                    R = mid - 1;
            }

        }
        return null;
    }
}
           

雙指針:

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        for (int l = 0, r = numbers.length - 1; l < r; ) {
            if (numbers[l] + numbers[r] == target)
                return new int[]{l + 1, r + 1};
            else if (numbers[l] + numbers[r] < target)
                l++;
            else
                r--;
        }
        return null;
    }
}
           

LeetCode - 11. Container With Most Water(盛最多水的容器)

題目連結

題目

解析

使用雙指針:

• 兩個指針從兩邊開始出發，周遊的過程中使用一個變量

  max

  記錄最大值；
• 因為

  x

  軸方向每兩個之間的寬度是相同的，是以向中間移動的時候，要選擇高度更小的那個向中間移動；

class Solution {
    public int maxArea(int[] height) {
        int max = 0;
        for (int l = 0, r = height.length - 1; l < r; ) {
            if (max < (r - l) * (Math.min(height[l], height[r]))) {
                max = (r - l) * (Math.min(height[l], height[r]));
            }
            if (height[l] > height[r])
                r--;
            else
                l++;
        }
        return max;
    }
}