Brooke

1.Trapping Rain Water
2. Find the Duplicate Number

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one.

Note:

You must not modify the array (assume the array is read only).
You must use only constant, O(1) extra space.
Your runtime complexity should be less than O(n2).
There is only one duplicate number in the array, but it could be repeated more than once.

鸽笼问题：nlogn

class Solution(object):
    def findDuplicate(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        low = 1
        high = len(nums)-1
        
        while low < high:
            mid = low+(high-low)/2
            count = 0
            for i in nums:
                if i <= mid:
                    count+=1
            if count <= mid:
                low = mid+1
            else:
                high = mid
        return low

cycle detection
pair of indices i != j such that f(i) = f(j).
To see this, note that it must contains a cycle
# because the array is finite and after visiting n elements, we necessarily
# must visit some element twice.  This is true no matter where we start off in
# the array.  Moreover, note that since the array elements range from 1 to
# n - 1 inclusive, there is no array index that contains 0 as a value.
# Consequently, when we leave index 0 after applying the function f one
# time, we can never get back there.  This means that 0 can't be part of a
# cycle, but if we follow indices starting there we must eventually hit some
# other node twice.  The concatenation of the chain starting at 0 with the
# cycle it hits must be rho-shaped.
#
http://keithschwarz.com/interesting/code/?dir=find-duplicate

public class Solution {
   public int findDuplicate(int[] nums) {
     int n = nums.length;
    int slow = 0;
    int fast = 0;
    do{
        slow = nums[slow];
        fast = nums[nums[fast]];
    }while(slow != fast);
    slow = 0;
    while(slow != fast){
        slow = nums[slow];
        fast = nums[fast];
    }
    return slow;
}
}

mutable

public class Solution {
   public int findDuplicate(int[] nums) {
     for(int i =0; i < nums.length - 1;i++){
         int j = i;
         while(nums[j]!=j+1){
             int k = nums[j] - 1;
             if(nums[k] == nums[j]) return nums[j];
             swap(nums,k,j);
         }
     }
     
     return nums.length==0? -1:nums[nums.length-1];
}
    public void swap(int[] nums,int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

3.Minimum Window Substring

public class Solution {
    public String minWindow(String s, String t) {
        int n = s.length(), min = s.length()+1; 
        String ret = "";
        int [] count = new int[256];
        for(int i = 0; i < t.length(); i++){
             int x = t.charAt(i);
              count[x]++;
        }
        int countDown = t.length();
        int begin =0, end = 0;
        while(end < n){
            int x = s.charAt(end++);
            if(count[x]-- > 0){
                countDown--;
            }
            while(countDown == 0){
                if(end - begin < min){
                    min = end - begin;
                    ret = s.substring(begin,end);
                }
                if(count[s.charAt(begin++)]++==0){
                    countDown++; 
                }
                
            }
        }
        return ret;
    }
}

4. Substring with Concatenation of All Words

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

For example, given:
s: "barfoothefoobarman"
words: ["foo", "bar"]

You should return the indices: [0,9].

public class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        //first we need a map to store words
        Map<String,Integer> map = new HashMap<>();
        List<Integer> ans =new ArrayList<>();
        int len = words[0].length();
        int n = s.length(); if(n == 0 || words.length == 0||n < len*words.length) return ans;
        for(String word: words) if(map.containsKey(word)) map.put(word,map.get(word)+1);else map.put(word,1);
        //two pointer method: window. outerloop len times, inner loop use two pointer 
        for(int i = 0; i < len; i++){
            int left = i;
            int count = 0;
            Map<String,Integer> copy = new HashMap<>();
            for(int j = i;j <= n-len; j+=len){
                String str = s.substring(j,j+len);
                if(!map.containsKey(str)){ 
                    left = j+len;
                    count=0;
                    copy = new HashMap<>();
                    continue;
                }
                if(!copy.containsKey(str) ||copy.get(str) < map.get(str)){
                   count++;
                }
                copy.put(str,copy.containsKey(str)? copy.get(str)+1 : 1);
                while(copy.get(str) > map.get(str)){              
                    String str1 = s.substring(left,left+len);
                    copy.put(str1,copy.get(str1)-1);
                    left+=len;
                    if(!str1.equals(str))
                        count--;
                }
                if(count == words.length) ans.add(left);

            }
        }
        return ans;
    }

}

5. Longest Substring with At Most Two Distinct Characters

Given a string, find the length of the longest substring T that contains at most 2 distinct characters.

For example, Given s = “eceba”,

T is "ece" which its length is 3.

public class Solution {
    public int lengthOfLongestSubstringTwoDistinct(String s) {
        int n = s.length();
        if(n == 0) return 0;
        char first = s.charAt(0),second = ' ';
        int count1 = 1, count2 = 0;
        int begin = 0, end = 0, max = 1;
        while(++end < n){
            if(s.charAt(end) == first){count1++;}
            else if(s.charAt(end) == second){count2++;}
            else if(second == ' '){second = s.charAt(end);count2++;}
            else{
                max = Math.max(max,end-begin);
                while( second != ' ' &&  first != ' '){
                    if(s.charAt(begin) == first) count1--;
                    else if(s.charAt(begin) == second) count2--;
                    if(count1 == 0) first = ' ';
                    if(count2 == 0) second = ' ';
                    begin++;
                }
                if(first == ' '){
                    first = second;
                    count1 = count2;
                    second = ' ';
                    count2 = 0;
                }
               second = s.charAt(end);count2++;
            }
        }
        max = Math.max(max,end-begin);
        return max;
    }
}

public class Solution {
    public int lengthOfLongestSubstring(String s) {
        int[] visited = new int[128];
        Arrays.fill(visited,-1);
        int max = 0,begin = 0;
        for(int i = 0; i <s.length(); i++){
            char c = s.charAt(i);
            if(visited[c]==-1||begin > visited[c]){
                visited[c] = i;
            }else{
                max = Math.max(max,i-begin);
                begin =  visited[c]+1;
                visited[c] = i;
            }
        }
        max = Math.max(max,s.length()-begin);
        return max;
    }
}

6. Longest Substring Without Repeating Characters

7. Sort Colors

public class Solution {
    public void sortColors(int[] nums) {
        int n = nums.length;
        if(n==0)return;
        int red = -1, blue = n;
        for(int i = 0; i < blue;){//!important
            if(nums[i] == 0){
                swap(nums,i,++red);
                i++;
            }else if(nums[i] == 2){
                swap(nums,i,--blue);
            }else
                i++;
        }
    }
    public void swap(int[] nums,int i,int j){
        if(i == j) return;//!important 
        nums[i] ^= nums[j];
        nums[j] ^= nums[i];
        nums[i] ^= nums[j];
    }
}

8. Sort Transformed Array

Given a sorted array of integers nums and integer values a, b and c. Apply a function of the form f(x) = ax2 + bx + c to each element x in the array.

The returned array must be in sorted order.

Expected time complexity: O(n)

Example:

nums = [-4, -2, 2, 4], a = 1, b = 3, c = 5,

Result: [3, 9, 15, 33]

nums = [-4, -2, 2, 4], a = -1, b = 3, c = 5

Result: [-23, -5, 1, 7]

public class Solution {
    public int[] sortTransformedArray(int[] nums, int a, int b, int c) {
        double vertex = a== 0 ? 0 : -(double)b/(2*a);
        int[] ans = new int[nums.length];
        int i = 0, j = nums.length-1;
        int k = a > 0 ? nums.length-1 : 0  ;
        int dir =a > 0? -1:1;
        if(a==0){
            k = b>=0?nums.length-1 : 0 ;
            dir =b >= 0? -1:1;                
        }
        while(i <= j){
            if(a==0 ||Math.abs(nums[j] - vertex) >= Math.abs(nums[i] - vertex)){
                ans[k] = a*nums[j]*nums[j] + b*nums[j--] + c;
            }else{
                ans[k] = a*nums[i]*nums[i] + b*nums[i++] + c;
            }
            k = k + dir;
        }
        return ans;
    }
}

9. Container With Most Water

Given n non-negative integers a1, a2, ..., an, where each represents a point at coordinate (i, ai).

n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0).

Find two lines, which together with x-axis forms a container,

such that the container contains the most water.

The O(n) solution with proof by contradiction doesn't look intuitive enough to me. Before moving on, read the algorithm first if you don't know it yet.

Here's another way to see what happens in a matrix representation:

Draw a matrix where the row is the first line, and the column is the second line. For example, say n=6.

In the figures below, x means we don't need to compute the volume for that case: (1) On the diagonal, the two lines are overlapped; (2) The lower left triangle area of the matrix is symmetric to the upper right area.

We start by computing the volume at (1,6), denoted by o. Now if the left line is shorter than the right line, then all the elements left to (1,6) on the first row have smaller volume, so we don't need to compute those cases (crossed by ---).

  1 2 3 4 5 6
1 x ------- o
2 x x
3 x x x 
4 x x x x
5 x x x x x
6 x x x x x x

Next we move the left line and compute (2,6). Now if the right line is shorter, all cases below (2,6) are eliminated.

  1 2 3 4 5 6
1 x ------- o
2 x x       o
3 x x x     |
4 x x x x   |
5 x x x x x |
6 x x x x x x

And no matter how this o path goes, we end up only need to find the max value on this path, which contains n-1 cases.

  1 2 3 4 5 6
1 x ------- o
2 x x - o o o
3 x x x o | |
4 x x x x | |
5 x x x x x |
6 x x x x x x

Hope this helps. I feel more comfortable seeing things this way.

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

10. Partition List

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

public class Solution {
    public ListNode partition(ListNode head, int x) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode p1 = null;
        ListNode pre = dummy;        
        ListNode cur = head;
        while(cur!=null){
            ListNode next = cur.next;
            if(cur.val >= x || (p1 == null)){
                if(cur.val >= x && p1 == null) p1 = pre;
                pre = cur;
            }else{
                pre.next = next;
                ListNode tmp = p1.next;
                p1.next = cur;
                cur.next = tmp;
                p1 = cur;
            }
            cur = next;
        }
        return dummy.next;
    }
}

11. Rotate List

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

public class Solution {
    public int len(ListNode head){int n = 0;while(head!=null) {n++;head = head.next;}return n;}
    public ListNode rotateRight(ListNode head, int k) {
        if(head == null) return null;
        int len = len(head);
        k = k%len;
        if(k == 0) return head;
        
        ListNode cur = head;

        // using k to represent faster pointer,when faster pointer is at tail, slow is at then end of first part

        while(k++<len-1){
            cur = cur.next;
        }

        ListNode newHead = cur.next;
        ListNode tail = newHead;
        cur.next = null;
        while(tail.next!=null) tail = tail.next;
        tail.next = head;
        return newHead;
    }
}

12. Linked List Cycle II

public class Solution {
    public ListNode detectCycle(ListNode head) {
        ListNode slow = head, fast = head;
        if(head==null) return null;
        while(fast!=null && fast.next!=null){
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow){
                fast = head;
                while(fast!=slow){
                    fast = fast.next;
                    slow = slow.next;
                }
                return slow;
            }
        }
        return null;
        
    }
}

13. Remove Duplicates from Sorted Array II

Follow up for "Remove Duplicates":
What if duplicates are allowed at most twice?

For example,
Given sorted array nums = [1,1,1,2,2,3],

Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length.

public class Solution {
    public int removeDuplicates(int[] nums) {
        int j = 2, i = 2;
        while(i < nums.length){
            if(nums[i]!=nums[j-2]){
                //not twice duplicates
                nums[j++] = nums[i++];
            }else{
                i++;
            }
        }
        return j;
    }
}

14. Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

public class Solution {
    int INT_MAX =Integer.MAX_VALUE;
    public int minSubArrayLen(int s, int[] nums) {
         int n = nums.length, minlen = INT_MAX;
        int[] sums = new int[n+1];
        for (int i = 1; i <= n; i++) {
            sums[i]=sums[i-1] + nums[i-1];                                     
            if (sums[i] >= s) {
                //find sum[i] - sum[j]  >= s && sum[i] - sum[j+1] < s
                //find sum[i] - s >= sum[j]  && sum[i] - s  < sum[j+1]
                int p = ceiling(sums, 0, i-1, sums[i] - s);
                if (p != -1) minlen = Math.min(minlen, i - p);
            }
        }
        return minlen == INT_MAX ? 0 : minlen;
    }
    int ceiling(int[] sums, int l, int r, int target) {
        //找到最右边小于等于target的位置
        while (l + 1 < r) {
            int m = l + ((r - l) >> 1);
            if (sums[m] <= target) l = m;
            else r = m - 1;
        }
        if(sums[r] <= target) return r;
        if(sums[l] <= target) return l;
        return -1;
    }
}

15. 3Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note: The solution set must not contain duplicate triplets.

For example, given array S = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
  [-1, 0, 1],
  [-1, -1, 2]
]

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> ans = new ArrayList<>();
        for(int i = 0; i < nums.length; i++){
            if(nums[i] > 0) break;
            if(i>0&&nums[i]==nums[i-1]) continue;
            int  lo=i+1,hi = nums.length-1;
            while(lo < hi){
                if(nums[lo]+nums[hi] > -nums[i]){
                    hi--;
                }else if(nums[lo]+nums[hi] <  -nums[i]){
                    lo++;
                }else{
                    int mid = nums[lo], max = nums[hi];
                    ans.add(Arrays.asList(nums[i], nums[lo], nums[hi]));
                    while(lo < hi && nums[++lo] == mid);
                    while(lo < hi && nums[--hi] == max);
                }
            }
        }
        return ans;
    }
}

16. 3Sum Smaller

Given an array of n integers nums and a target, find the number of index triplets i, j, k with 0 <= i < j < k < n that satisfy the condition nums[i] + nums[j] + nums[k] < target.

For example, given nums = [-2, 0, 1, 3], and target = 2.

Return 2. Because there are two triplets which sums are less than 2:

[-2, 0, 1]
[-2, 0, 3]

Follow up:
Could you solve it in O(n2) runtime?

public class Solution {
    public int threeSumSmaller(int[] nums, int target) {
        Arrays.sort(nums);
        int cnt=0;
        for(int i = 0; i < nums.length; i++){
            int  lo=i+1,hi = nums.length-1;
            //2sum smaller? than target
            //in the mean time, we could not use ith number
            while(lo < hi){
                if(nums[lo]+nums[hi] <target -nums[i]){
                    cnt+= hi-lo;
                    lo++;
                }else{
                    hi--;
                }
            }
        }
        return cnt;
    }
}

17. 3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

public class Solution {
    public int threeSumClosest(int[] nums, int target) {
        int diff = Integer.MAX_VALUE;
        int sum = 0;
        Arrays.sort(nums);
        for(int i = 0; i < nums.length; i++){
            if(i>0&&nums[i]==nums[i-1]) continue;
            int  lo=i+1,hi = nums.length-1;
            while(lo < hi){
                int tmp = Math.abs(nums[lo]+nums[hi]+nums[i]-target);
                if(tmp < diff){
                    diff = tmp;
                    sum = nums[lo]+nums[hi]+nums[i];
                }
                if(nums[lo]+nums[hi] > target-nums[i]){
                    hi--;
                }else if(nums[lo]+nums[hi] < target -nums[i]){
                    lo++;
                }else{
                   return target;
                }
            }
        }
        return sum;
    }
}

18. 4Sum

算法1：我们可以仿照3sum的解决方法。这里枚举第一个和第二个数，然后对余下数的求2sum，算法复杂度为O（n^3）,去重方法和上一题类似

class Solution {
public:
    vector<vector<int> > fourSum(vector<int> &num, int target) {
        int n = num.size();
        vector<vector<int> > res;
        sort(num.begin(), num.end());
        for(int i = 0; i < n-3; i++)
        {
            if(i > 0 && num[i] == num[i-1])continue;//防止第一个元素重复
            for(int j = i+1; j < n-2; j++)
            {
                if(j > i+1 && num[j] == num[j-1])continue;//防止第二个元素重复
                int target2 = target - num[i] - num[j];
                int head = j+1, tail = n-1;
                while(head < tail)
                {
                    int tmp = num[head] + num[tail];
                    if(tmp > target2)
                        tail--;
                    else if(tmp < target2)
                        head++;
                    else
                    {
                        res.push_back(vector<int>{num[i], num[j], num[head], num[tail]});
                        //为了防止出现重复的二元组，使结果等于target2
                        int k = head+1;
                        while(k < tail && num[k] == num[head])k++;
                        head = k;
                        
                        k = tail-1;
                        while(k > head && num[k] == num[tail])k--;
                        tail = k;
                    }
                }
            }
        }
        return res;
    }
};

http://westpavilion.blogspot.com/2014/02/k-sum-problem.html

19. Remove Nth Node From End of List

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

For example,

   Given linked list: 1->2->3->4->5, and n = 2.

   After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:
Given n will always be valid.

linked list题目大多不是特别难，但是写对又往往不容易。一些容易犯的错误是：

1. 越界：容易造成内存访问错误，比如调用了NULL->next。尤其对于空链表的特殊情况。

2. 更新head的特殊处理

3. 删除节点时没有保留下一个移动位置的指针（多用于reverse linked list）。

4. 移动位置存在+-1的偏差。

常用技巧：
1. Dummy head：简化改变、删除头指针的处理。
2. 前后双指针：多用于链表反转。

所以做这类题目时，一定要在纸上画图。写完代码后必须要跑test case来确认正确。

public class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode first = dummy, second = dummy;
        while(n-->0){
            first = first.next;
        }
        while(first.next!=null){
            first = first.next;
            second = second.next;
        }
        second.next = second.next.next;
        return dummy.next;
    }
}

20. Remove Duplicates from Sorted Array

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example,
Given input array nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn't matter what you leave beyond the new length.

public class Solution {
      public int removeElement(int[] nums,int val) {
        int p = 0;
        for(int i =0; i< nums.length; i++){
            if(nums[i]==val) continue;
            if(i!=p) swap(nums,p,i);
            p++;
        }
        return p;
    }
    public void swap(int[] nums, int i, int j){
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

21. Intersection of Two Arrays

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].

Note:

Each element in the result must be unique.
The result can be in any order.

public class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        Set<Integer> ans = new HashSet<>();
        Arrays.sort(nums2);
        for (Integer num : nums1) {
            if (binarySearch(nums2, num)) {
                ans.add(num);
            }
        }
        int i = 0;
        int[] result = new int[ans.size()];
        for (Integer num : ans) {
            result[i++] = num;
        }
        return result;
    }
    public boolean binarySearch(int[] nums, int target) {
        int hi = nums.length-1;
        int lo = 0;
        while(lo <= hi){
            int mid = lo + (hi - lo)/2;
            if (nums[mid] == target) {
                return true;
            }
            if (nums[mid] > target) {
                hi = mid - 1;
            } else {
                lo = mid + 1;
            }
        }
        return false;
    }

}

22. Intersection of Two Arrays II

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2, 2].

Note:

Each element in the result should appear as many times as it shows in both arrays.
The result can be in any order.

Follow up:

What if the given array is already sorted? How would you optimize your algorithm?
What if nums1's size is small compared to nums2's size? Which algorithm is better?
What if elements of nums2 are stored on disk, and the memory is limited such that you cannot load all elements into the memory at once?

What if elements of nums2 are stored on disk, and the memory is
limited such that you cannot load all elements into the memory at
once?

public class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        Arrays.sort(nums1);
        Arrays.sort(nums2);
        List<Integer> ans= new ArrayList<>();
        int i = 0, j = 0;
        while(i < m && j < n){
           if(nums1[i] < nums2[j]) i++;
           else if(nums1[i] > nums2[j]) j++;
           else{
               ans.add(nums1[i]);
               i++;
               j++;
           }
        }
        int[] ret = new int[ans.size()];
        int k = 0;
        for(int num : ans){
            ret[k++] = num;
        }
        return ret;
    }
}

If only nums2 cannot fit in memory, put all elements of nums1 into a HashMap, read chunks of array that fit into the memory, and record the intersections.
If both nums1 and nums2 are so huge that neither fit into the memory, sort them individually (external sort), then read 2 elements from each array at a time in memory, record intersections.

23. Palindrome Linked List

public class Solution {
    //ab
    //abc
    //abcd
    public boolean isPalindrome(ListNode head) {
        if(head == null) return true;
        ListNode slow = head, fast = head;
        while(fast.next!=null && fast.next.next != null){
            slow = slow.next;
            fast = fast.next.next;
        }        
        slow = reverse(slow.next);
        while(slow!=null){
            if(slow.val != head.val) return false;
            slow = slow.next;
            head = head.next;
        }
        return true;
    }
    public ListNode reverse(ListNode head){
        ListNode pre = null;
        while(head!= null){
            ListNode next = head.next;
            head.next = pre;
            pre = head;
            head = next;
        }
        return pre;
    }
}

24. Valid Palindrome

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

For example,
"A man, a plan, a canal: Panama" is a palindrome.
"race a car" is not a palindrome.

public class Solution {
    public boolean isPalindrome(String s) {
        int i = 0, j = s.length()-1;
        while(i < j){
            while(i < j && !(Character.isDigit(s.charAt(i)) || Character.isLetter(s.charAt(i)))) i++;
            while(i < j && !(Character.isDigit(s.charAt(j)) ||Character.isLetter(s.charAt(j)))) j--;
            if(s.charAt(i)!=s.charAt(j) && !( Character.isLetter(s.charAt(i)) && Character.isLetter(s.charAt(j)) && Math.abs(s.charAt(i)-s.charAt(j))=='a'-'A') )
                    return false;
            
            i++;
            j--;
        }
        return true;
    }
}

25. Reverse Vowels of a String

Write a function that takes a string as input and reverse only the vowels of a string.

Example 1:
Given s = "hello", return "holle".

Example 2:
Given s = "leetcode", return "leotcede".

public class Solution {
    public String reverseVowels(String s) {
        //a e i o u
        Set<Character> set = new HashSet<>();
        set.add('a');set.add('e');set.add('i');set.add('o');set.add('u');
        set.add('A');set.add('E');set.add('I');set.add('O');set.add('U');
        int lo = 0, hi = s.length()-1;
        char[] chars = s.toCharArray();
        while(lo < hi){
            while(lo < hi && !set.contains(s.charAt(lo))) lo++;
            while(lo < hi && !set.contains(s.charAt(hi))) hi--;
            if(lo >= hi) break;
            swap(chars,lo++,hi--);
        }
        return String.valueOf(chars);
    }
    public void swap(char[] cs, int i, int j){
        char tmp = cs[i];
        cs[i] = cs[j];
        cs[j] = tmp;
    }
}

Brooke

2018年7月24日星期二

英文学习

2018年7月16日星期一

Subsets

2018年7月15日星期日

43. Multiply Strings

2016年11月27日星期日

Two Pointers

博客归档