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, 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--;
}
}
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;
}
}