对撞型 Palindrome

Trapping Rain Water

• 经典题，有一种很巧妙的2 pointers解法实现O(N) Time and O(1) Space

• how much can current position trap depends on the lower bar, min(leftmax, rightmax)

• 2 pointers left and right

• keep track of maxHeight from left and right, leftMax, rightMax

• every iteration when move left or right pointer, always update leftMax and rightMax

• then compare with leftMax and rightMax, the smaller one is the direction to move next

• 有单调栈的思想

public int trap(int[] height) {
        int n = height.length;
        int left = 0, right = n - 1;
        int water = 0;
        int leftMax = 0, rightMax = 0;
        while (left < right) {
            leftMax = Math.max(leftMax, height[left]);
            rightMax = Math.max(rightMax, height[right]);
            if (leftMax < rightMax) {
                water += leftMax - height[left];
                left++;
            } else {
                water += rightMax - height[right];
                right--;
            }
        }
        return water;
    }

Longest Palindromic Substring

• 这题可以用2 pointers实现O(N^2)的解法

• iterate each index of String, always check 2 substring

• isPalindrome(s, i - maxLen - 1, i) -> try len(maxLen + 2)

• isPalindrome(s, i - maxLen, i) -> try len(maxLen + 1)

public String longestPalindrome(String s) {
        if (s == null || s.length() < 2 ) return s;
        String res = "";
        for (int i = 0; i < s.length(); i++) {
            int len = res.length();
            if (isPalindrome(s, i - len - 1, i)) {
                res = s.substring(i - len - 1, i + 1);
            } else if (isPalindrome(s, i - len, i)) {
                res = s.substring( i - len, i + 1);
            }
        }
        return res;
    }
    private boolean isPalindrome(String s, int begin, int end) {
        if (begin < 0 || end >= s.length()) return false;
        while (begin < end) {
            if (s.charAt(begin) != s.charAt(end)) return false;
            begin++;
            end--;
        }
        return true;
    }

Reverse words in a String II

• 给一个char array, 每个单词被empty space隔开

• 要求 in place reverse words in a string

• reverse the whole char array first

• then reverse word one by one

public void reverseWords(char[] s) {
        if (s == null || s.length < 2) return;
        int n = s.length;
        reverse(s, 0, n - 1);
        int begin = 0, end = 0;
        while (end < n) {
            while (end + 1 < n && s[end + 1] != ' ') {
                end++;
            }
            reverse(s, begin, end);
            end += 2;
            begin = end;
        }
    }
    private void reverse(char[] s, int begin, int end) {
        while (begin < end) {
            char tmp = s[begin];
            s[begin] = s[end];
            s[end] = tmp;
            begin++;
            end--;
        }
    }

Next Permutation

• next permutation经典题，全文背诵，跟permutation关系不大

• 4步走，默背

• 51432, 从右往左找到第一个nums[i] < nums[i + 1] ->1

• 再从右往左找到比nums[i]大的最小的数 nums[j] > nums[i], 找从右往左第一个比nums[i]大的数 ->2

• swap nums[i] and nums[j] 52431

• everse subset from i+1 th to the end->52134

    public void nextPermutation(int[] nums) {
        //4步走，默背
        //51432, 从右往左找到第一个nums[i] < nums[i + 1]    ->1
        //再从右往左找到比nums[i]大的最小的数 nums[j] > nums[i], 也就是找从左往左第一个比nums[i]大的数    ->2
        //swap nums[i] and nums[j]  52431
        //reverse subset from i+1 th to the end->52134
        int n = nums.length;
        int i = n - 2;
        //find first element where nums[i] < nums[i+1]
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = n - 1;
            //find first/smallest element which is greater than nums[i], from right end
            while (j > i && nums[j] <= nums[i]) {
                j--;
            }
            swap(nums, i, j);
        }
        //reverse subset from i + 1
        reverse(nums, i + 1, n - 1);
    }
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    private void reverse(int[] nums, int begin, int end) {
        while (begin < end) {
            swap(nums, begin++, end--);
        }
    }

Next Greater Element III

• 给定一个int value N, 求比N大的最小的permutation, int value

• 解法跟next permutation很像

public int nextGreaterElement(int n) {
        char[] arr = String.valueOf(n).toCharArray();
        int len = arr.length;
        int i = len - 2;
        while (i >= 0 && arr[i] >= arr[i + 1]) {
            i--;
        }
        if (i < 0) return -1;
        int j = len - 1;
        while (j > i && arr[j] <= arr[i]) {
            j--;
        }
        swap(arr, i, j);
        reverse(arr, i + 1, len - 1);
        try {
            return Integer.parseInt(new String(arr));
        } catch(NumberFormatException e) {
            return -1;
        }
    }
    private void swap(char[] nums, int i, int j) {
        char tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
    private void reverse(char[] nums, int begin, int end) {
        while (begin < end) {
            swap(nums, begin++, end--);
        }
    }

Valid Palindrome II

• 最多允许删除一个char

• 也就是说当s.charAt(begin) != s.charAt(end)的时候

• either delete s.charAt(begin) or delete s.charAt(end)

• return isValid(s.substring(begin, end)) || isValid(s.substring(begin + 1, end + 1));

class Solution {
    public boolean validPalindrome(String s) {
        int begin = 0, end = s.length() - 1;
        while (begin < end) {
            if (s.charAt(begin) != s.charAt(end)) {
                return isValid(s.substring(begin, end)) || isValid(s.substring(begin + 1, end + 1));
            }
            begin++;
            end--;
        }
        return true;
    }
    private boolean isValid(String s) {
        if (s.length() < 2) {
            return true;
        }
        int begin = 0, end = s.length() - 1;
        while (begin < end) {
            if (s.charAt(begin) != s.charAt(end)) {
                return false;
            }
            begin++;
            end--;
        }
        return true;
    }
}