Posted on | In

Test cases

1
" " // expect ""

Solution 1: accepted 20ms

Time: O(n)
Space: O(n) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public String reverseWords(String s) {
    StringBuilder sb = new StringBuilder();
    String temp = "";
    for (int i = s.length() - 1; i >= 0; i--) {
      char cur = s.charAt(i);
      if (cur == ' ' && temp.length() != 0) {
        sb.append(temp + " ");
        temp = "";
      } else if (cur == ' ') {
        continue;
      } else {
        temp = cur + temp;
      }
    }
    sb.append(temp);
    return sb.toString().trim();
}

Solution 2: accepted 12ms

Time: O(n)
Space: O(n) 

1
2
3
4
5
6
7
8
public String reverseWords(String s) {
    String[] words = s.trim().split("\\s+");
    StringBuilder sb = new StringBuilder();
    for (int i = words.length - 1; i >= 0; i--) {
      sb.append(words[i] + " ");
    }
    return sb.deleteCharAt(sb.length() - 1).toString();
}

Posted on | In

Solution 1: accepted 0ms

use nums[mid] > nums[hi] rather than nums[mid] > nums[lo] to avoid consideration of corner case, no rotation. If there’s no rotation and we say if (nums[mid] > nums[lo]) lo = mid, we abandon the left side, which has the answer. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int findMin(int[] nums) {
    if (nums.length == 0) return -1;
    int lo = 0;
    int hi = nums.length - 1;
    while (lo + 1 < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] > nums[hi])
            lo = mid;
        else
            hi = mid;
    }
    return nums[lo] < nums[hi] ? nums[lo] : nums[hi];
}

Posted on | In

Teat cases

1
2
3
4
5
6
[1]
[7,8,9,1,2,3,4,5,6]
[7,8,9,9,9,9,1,2,3,3,4,5,5,5,6,6,6,6]
[1,1,1,1,1,1,1,1]
[2,3,4,5,6,7,8,1]
[3,4,5,6,7,8,1,2]

Solution 1: accepted 1ms

Time: O(n) // worst case when all elements are the same 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int findMin(int[] nums) {
    if (nums.length == 0) return -1;
    int lo = 0;
    int hi = nums.length - 1;
    while (lo + 1 < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] > nums[hi])
            lo = mid;
        else if (nums[mid] < nums[hi])
            hi = mid;
        else
            hi--;
    }
    return nums[lo] <= nums[hi] ? nums[lo] : nums[hi];
}

Posted on | In

Solution 1��? time limit exceeded

Time: O(n^2), Space: O(1)

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
public class Solution {
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 2)
            return s;
            
        String output = "";
        
        for (int i = 0; i < s.length(); i++) {
           for (int j = 0; j < i + 1; j++) {
               int start = j;
               int end = i;
               while (s.charAt(start) == s.charAt(end)) {
                   if (end - start == 2 || end - start == 1) {
                        output = output.length() >= s.substring(j,i + 1).length()? output: s.substring(j,i + 1);
                        break;
                   }
                   if (end == 0 || start == i)
                       break;
                   start++;
                   end--;
               }
           }
        }
    return output;
    }
}

Mutation: Replacing string manipulation with int values, but it dones’t improve the performance.

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
public class Solution {
    public String longestPalindrome(String s) {
        
        int length = s.length();
        int startLocation = 0;
        int longestLength = 0;
        if (s == null || length < 2)
            return s;
        
        for (int i = 0; i < length; i++) {
           for (int j = 0; j < i + 1; j++) {
               int start = j;
               int end = i;
               while (s.charAt(start) == s.charAt(end)) {
                   if (end - start == 2 || end - start == 1) {
                        if (longestLength < i - j + 1) {
                            startLocation = j;
                            longestLength = i - j + 1;
                        }
                        break;
                   }
                   if (end == 0 || start == i)
                       break;
                   start++;
                   end--;
               }
           }
        }
    return s.substring(startLocation, startLocation + longestLength);
    }
}

Solution 2: accepted, 37%

中间��?��?

Time: O(2 n^2), Space: O(1)
avoid unnecessary check, but still O(n^2), failed the “aaaaaaaa…” test case.

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
public static String longestPalindrome(String s) {
	if (s == null || s.length() < 2) return s;
    	int len = s.length();
    	int start = 0;
    	int max = 0;
        for(int i = 0; i < len; i++) { 
        	// break if it's not possible to find longer output
        	if (len - i < max / 2)
        		break;
        	
        	// for "aba"
        	int left = i;
        	int right = i;
        	while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {
        		left--;
        		right++;
        	}
        	if (right - left - 2 >= max) {
        		max = right - left - 2;
        		start = left + 1;
        	}    	
        	
        	// for "abba"
        	left = i;
        	right = i + 1;
        	while (left >= 0 && right < len && s.charAt(left) == s.charAt(right)) {
        		left--;
        		right++;
        	}
        	if (right - left - 2 >= max) {
        		max = right - left - 2;
        		start = left + 1;
        	}    	
        }        
        return s.substring(start, start + max + 1);
}

We should be able to cut the time to half by check “aba” and “abba” in the same loop:

Solution 3: accepted, 99%

Amaing boost in performace simply because I changed the duplicated code block in solution 2 to method. Is this the truth?

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
public class Solution {
    private int start, max;
    public String longestPalindrome(String s) {
        if (s == null || s.length() < 2) return s;
    	int len = s.length();
        for(int i = 0; i < len; i++) { 
        	// break if it's not possible to find longer output
        	if (len - i < max / 2)
        		break;
        	extendPalindrome(s, i, i);
        	extendPalindrome(s, i, i + 1);
        }        
        return s.substring(start, start + max);
    }
    private void extendPalindrome(String s, int left, int right) {
        while (left >= 0 && right < s.length() && s.charAt(left) == s.charAt(right)) {
    		left--;
    		right++;
    	}
    	if (max < right - left - 1) {
    		start = left + 1;
    		max = right - left - 1;
    	}
    }
}

Test case 1

Solution 1: ~100ms
Solution 2: ~6ms (without “len - i < output.length() / 2” it will be 10ms and will not be accepted)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
System.out.println(longestPalindrome("") + "/");
System.out.println(longestPalindrome("a") + "/a");
System.out.println(longestPalindrome("aa") + "/aa");
System.out.println(longestPalindrome("aaa") + "/aaa");
System.out.println(longestPalindrome("abc") + "/a");
System.out.println(longestPalindrome("aabaa") + "/aabaa");
System.out.println(longestPalindrome("ababababa") + "/ababababa");
System.out.println(longestPalindrome("kaba") + "/aba");
System.out.println(longestPalindrome("abak") + "/aba");
System.out.println(longestPalindrome("kabad") + "/aba");
System.out.println(longestPalindrome("kabba") + "/abba");
System.out.println(longestPalindrome("kabbad") + "/abba");
System.out.println(longestPalindrome("aaaakabbad") + "/aaaa");
System.out.println(longestPalindrome("kabbadaaaa") + "/abba");
System.out.println(longestPalindrome("aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa"));

Posted on | In

Solution 1: accepted

Binary search.

Since nums[-1] and num[n] are negative infinite, there must be a peak in the middle. Consider four conditions that mid may have, we can narrow the scope by half each time.

  1. mid - 1 < mid > mid + 1: mid is the peak.
  2. mid - 1 < mid < mid + 1: mid < mid + 1 [peak] len - 1 > -infinite, there must be a peak on right side.
  3. mid - 1 > mid > mid + 1: -infinite < 1 [peak] mid - 1 > mid, there must be a peak on left side.
  4. mid - 1 > mid < mid + 1: mid is a pit, either side has a peak. 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int findPeakElement(int[] nums) {
    int len = nums.length;
    if (len == 0) return -1;
    if (len == 1 || nums[0] > nums[1]) return 0;
    if (nums[len - 1] > nums[len - 2]) return len - 1;
    int lo = 0;
    int hi = nums.length - 1;
    while (lo + 1 < hi) {
        int mid = lo + (hi - lo) / 2;
        if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1])
            return mid;
        else if (nums[mid] < nums[mid - 1] && nums[mid] < nums[mid + 1])
            hi = mid;
        else if (nums[mid] < nums[mid - 1] && nums[mid] > nums[mid + 1])
            hi = mid;
        else if (nums[mid] > nums[mid - 1] && nums[mid] < nums[mid + 1])
            lo = mid;
    }
    return lo + 1;
}

Posted on | In

Solution 1: 1ms

Some binary thinking in the middle but not enough. We could make the time complexity closer to O(logn). 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int[] twoSum(int[] nums, int target) {
    if (nums.length < 2) return null;
    int lo = 0;
    int hi = nums.length - 1;
    while (true) {
        int sum = nums[lo] + nums[hi];
        if (sum == target) break;
        int mid = lo + (hi - lo) / 2;
        if (nums[lo] + nums[mid] > target) {
            hi = mid;
            continue;
        }
        if (nums[mid] + nums[hi] < target ) {
            lo = mid;
            continue;
        } 
        if (sum > target)hi--;
        else lo++;
    }
    return new int[] {++lo, ++hi};
}

Posted on | In

Solution 1: NC

Have problem with test cases:
4294967295 (11111111111111111111111111111111).
-2147483647 (1000 0000 0000 0000 0000 0000 0000 0000).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
    if (n == 0) 
        return 0;
    if (n < 0) 
        n = -n;
    int maxPow = 0;
    while (Math.pow(2, maxPow) <= n) {
        maxPow++;
    }       
    maxPow--;
    int result = 1;
    while (n > 1) {
        n -= Math.pow(2, maxPow);
        if (n == 0)
            return 1;
        maxPow--;
        result++;
    }
    return result;
}

Solution 2: accepted 2ms

  1. Unsigned: use >>> rather than >>
  2. Cannot use n >= 1, as some test cases will be recognized as negative number in java
1
2
3
4
5
6
7
8
public int hammingWeight(int n) {        
    int count = 0;
    while (n != 0) { // can't use n >= 1, as negative number do exist
      count += n & 1;
      n = n >>> 1; // unsigned, use >>> rather than >>
    }
    return count;
}

Posted on | In

Test cases

1
2
3
4
5
6
7
8
9
[]
[1,2]
[2,1]
[1,3,2]
[1,2,3]
[1,2,3,4,5,6,7]
[7,6,5,4,3,2,1]
[1,0,3,5,6,4,1,4,2,9,5,8]
[1,0,3,5,6,4,1,4,2,9,5,8,6]

Solution 1: accepted 0ms

DP: To calculate the total gain after robbing house number N, we need to consider the accumulated stash of house N-2 or N-3. N-1 is not available as it will trigger the alarm.
Time: O(n)

1
2
3
4
5
6
7
8
9
10
11
public int rob(int[] nums) {
        int len = nums.length;
        if (len == 0) return 0;
        if (len == 1) return nums[0];
        if (len > 2)
            nums[2] = Math.max(nums[0] + nums[2], nums[1]);
        for(int i = 3; i < len; i++) {
            nums[i] = Math.max(nums[i] + nums[i-2], nums[i] + nums[i-3]);
        }
        return Math.max(nums[len-1], nums[len-2]);
    }

Or convert to Space O(1) by storing two previous stashes in two int variables.

Solution 2: accepted 0ms

More elegant code.

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    public int rob(int[] nums) {
        int doit = 0; // total stash if we do rob the current house
        int dont = 0; // total stash if don't rob the current house
        for(int i = 0; i < nums.length; i++) {
            int current = dont + nums[i];
            dont = Math.max(doit, dont);
            doit = current;
        }
        return Math.max(dont, doit);
    }
}

Posted on | In

Test cases

1
2
3
4
5
6
7
8
10000
123321
-2147483412
2147483412
-2147483648
2147483647
1534236469
-1534236469

Solution 1: accepted

Basicly hard code, not wise at all. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public class Solution {
    public int reverse(int x) {
        int reversed = 0;
    	int digit = 0;
    	while (x != 0) {
		if (digit == 9) {//2147483648
			if (reversed > 214748364 || reversed < -214748364)
				return 0;
			else if (reversed == 214748364 && x % 10 >7)
				return 0;
			else if (reversed == -214748364 && x % 10 >8)
				return 0; // not happening as input is int
		}
    		reversed = reversed * 10 + x % 10;
    		x = x / 10;
		digit++;
        }
	return reversed;
    }
}

Solution 2: accepted 41ms, 54%

Concise and fast. A smart way to detect overflow. 

1
2
3
4
5
6
7
8
9
10
11
12
public int reverse(int x) {
  int reversed = 0;
  while (x != 0) { // x could be negative
    int before = reversed;
    int tail = x % 10; // this improves speed
    reversed = reversed * 10 + tail;
    if ((reversed - tail) / 10 != before)  // check overflow
	return 0;
    x /= 10;
  }
  return reversed;
}

Solution 3: accepted 36ms 92%

Even more concise and faster! Jump out of the “box”! 

1
2
3
4
5
6
7
8
9
10
public int reverse(int x) {
  long reversed = 0;
  while (x != 0) {
    reversed = reversed * 10 + x % 10;
    if (reversed > Integer.MAX_VALUE || reversed < Integer.MIN_VALUE )
	return 0;
    x /= 10;
  }
  return (int)reversed;
}

Posted on | In

Solution 1:

In this question we need to rearrange a string according to certain order. We need to find out the order of rearrangement.

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
public static String convert(String s, int numRows) {
		if (numRows < 2 || s == null || s.length() < numRows)
			return s;
		StringBuilder sb = new StringBuilder();
		int circleLength = 0;
		if (numRows < 3)
			circleLength = numRows;
		else
			circleLength = numRows * 2 - 2;
		for (int i = 1; i <= numRows; i++) {
			for (int j = 1; j <= s.length(); j++) {
				if (j % circleLength == i) {
					sb.append(s.charAt(j - 1));
				}
				
				if (i == 2 && j % circleLength == 0) {
					sb.append(s.charAt(j - 1));
				}
				
				if (i > 2 && i != numRows && j % circleLength == circleLength - i + 2) {
					sb.append(s.charAt(j - 1));
				}
			}
		}
		
		return sb.toString();
	}

Solution 2:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public String convert(String s, int nRows) {  
	int len = s.length();  
	if (len == 0 || nRows < 2) return s;  
	String ret = "";  
	int lag = 2*nRows - 2; //循环周期  
	for (int i = 0; i < nRows; i++) {  
	    for (int j = i; j < len; j += lag) {  
		ret += s.charAt(j);  
		//非首行和末行时还要加��?��?  
		if (i > 0 && i < nRows-1) {  
		    int t = j + lag - 2*i;  
		    if (t < len) {  
			ret += s.charAt(t);  
		    }  
		}  
	    }  
	}  
	return ret;  
}