Posted on | In

Solution 1: accepted 10%

Time: O(n)
Still get very bad performance (10%), try to replace syntax.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public int maxSubArray(int[] nums) {
    int len = nums.length;
    if (len < 1) return 0;
    int sum = nums[0];
    int[] copy = new int[len];
    System.arraycopy(nums, 0, copy, 0, len);
    for(int i = 1; i < len; i++) {
        copy[i] = nums[i] > copy[i-1] + nums[i] ? nums[i] : copy[i-1] + nums[i];
        sum = sum > copy[i]? sum : copy[i];
        // Make it a little bit faster to 18ms (16%)
        // nums[i] = Math.max(nums[i], nums[i-1] + nums[i]); 
        // sum = Math.max(sum, nums[i]);
    }
    return sum;
}

Alternative: without copy (slower)

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

Solution 2: accepted 17ms 25%

I think the performance varies on server condition…

1
2
3
4
5
6
7
8
9
10
11
12
13
public int maxSubArray(int[] nums) {
    if (nums.length < 1) return 0;
    int sum = 0;
    int max = Integer.MIN_VALUE;
    for(int i = 0; i < nums.length; i++) {
        sum += nums[i];
        max = Math.max(max, sum); 
        if (sum < 0) 
            sum = 0; // restore negative number
    }
    return max;
}

Posted on | In

##Solution 2: accepted

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
37
38
39
40
41
42
43
44
45
46
47
public static List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> result = new ArrayList<>();
        int m = matrix.length;// rows
        if (m == 0) {
            return result;
        }
        int n = matrix[0].length;// columns
        int topOffset = 0;
        int rightOffset = 0;
        int bottomOffset = 0;
        int leftOffset = 0;
        while (true) {
            // top
            for (int i = leftOffset; i < n - rightOffset; i++) {
                result.add(matrix[topOffset][i]);
            }
            topOffset++;
            if (topOffset + bottomOffset == m) {
                break;
            }
            // right
            for (int i = topOffset; i < m - bottomOffset; i++) {
                result.add(matrix[i][n - 1 - rightOffset]);
            }
            rightOffset++;
            if (leftOffset + rightOffset == n) {
                break;
            }
            // bottom
            for (int i = n - 1 - rightOffset; i >= leftOffset; i--) {
                result.add(matrix[m - 1 - bottomOffset][i]);
            }
            bottomOffset++;
            if (topOffset + bottomOffset == m) {
                break;
            }
            // left
            for (int i = m - 1 - bottomOffset; i >= topOffset; i--) {
                result.add(matrix[i][leftOffset]);
            }
            leftOffset++;
            if (leftOffset + rightOffset == n) {
                break;
            }
        }
        return result;
    }

Posted on | In

Solution 2: accepted

Try to divide it into two parts.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Solution {
    public List<List<String>> groupAnagrams(String[] strs) {
        if (strs == null || strs.length == 0) return new ArrayList<List<String>>();
        Map<String, List<String>> map = new HashMap<String, List<String>>();
        for (String s : strs) {
            char[] ca = s.toCharArray();
            Arrays.sort(ca);
            String keyStr = String.valueOf(ca);
            if (!map.containsKey(keyStr)) map.put(keyStr, new ArrayList<String>());
            map.get(keyStr).add(s);
        }
        return new ArrayList<List<String>>(map.values());
    }
}

Posted on | In

Solution 1: TLE

Normal DP.
Time: O(nk) (k is the largest input[i])
Space: O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public boolean canJump(int[] nums) {
    int len = nums.length;
    if (len < 2) return true;
    boolean[] dp = new boolean[len];
    dp[len - 1] = true;
    for (int i = len - 2; i >= 0; i--) {
        for (int j = 0; j <= nums[i]; j++) {
            if (dp[Math.min(i + j, len - 1)]) {
                dp[i] = true;
            }
        }    
    }
    return dp[0];
}

Solution 2: accepted 10ms

DP.
Time: O(n)
Space: O(1) 

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

Solution 3: accepted 8ms

7ms

1
2
3
4
5
6
7
8
9
public boolean canJump(int[] nums) {
    int last = nums.length - 1;
    for (int i = nums.length - 2; i >= 0; i--) {
        if (i + nums[i] >= last) {
            last = i;
        } 
    }
    return last == 0;
}

8ms

1
2
3
4
5
6
7
8
9
10
public boolean canJump(int[] nums) {
    int len = nums.length;
    int last = len - 1;
    for (int i = len - 2; i >= 0; i--) {
        if (i + nums[i] >= last) {
            last = i;
        } 
    }
    return last == 0;
}

Posted on | In

Solution 1: accepted 28ms 59%

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

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
class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals.size() < 2) 
            return intervals;
        List<Interval> result = new ArrayList<>();
        Collections.sort(intervals, new IntervalComparator());
        
        Interval temp = new Interval();
        for (int i = 0; i < intervals.size() - 1; i++) {
            if (intervals.get(i).end < intervals.get(i + 1).start) {
                result.add(intervals.get(i));
            } else if (intervals.get(i).start == intervals.get(i + 1).start) {
                intervals.get(i + 1).end = Math.max(intervals.get(i).end, intervals.get(i + 1).end);
            } else {
                intervals.get(i + 1).start = intervals.get(i).start;
                intervals.get(i + 1).end = Math.max(intervals.get(i).end, intervals.get(i + 1).end);
            }
        }
        result.add(intervals.get(intervals.size() - 1));
        return result;
    }
    
    private class IntervalComparator implements Comparator<Interval> {
        
        public int compare(Interval a, Interval b) {
            if (a.start < b.start)
                return -1;
            else if (a.start > b.start)
                return 1;
            else 
                return 0;
        }
    } 
}
Simplified
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
class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        if (intervals.size() < 2) 
            return intervals;
        List<Interval> result = new ArrayList<>();
        Collections.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval a, Interval b) {
                return a.start - b.start;
        }
        });
        
        Interval temp = new Interval();
        for (int i = 0; i < intervals.size() - 1; i++) {
            Interval current = intervals.get(i);
            Interval next = intervals.get(i + 1);
            if (current.end < next.start) {
                result.add(current);
            } else {
                next.start = current.start;
                next.end = Math.max(current.end, next.end);
            } 
        }
        result.add(intervals.get(intervals.size() - 1));
        return result;
    } 
}

Posted on | In

Solution 1: accepted 21ms

Add the new node to the list, and do the rest just like 056. 

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
public List<Interval> insert(List<Interval> intervals, Interval newInterval) {
    List<Interval> result = new ArrayList<>();
    intervals.add(newInterval);
    if (intervals.size() == 1)
        return intervals;
    Collections.sort(intervals, new Comparator<Interval>() {
       public int compare(Interval a, Interval b) {
           return a.start - b.start;
       } 
    });
    for (int i = 0; i < intervals.size() - 1; i++) {
        Interval current = intervals.get(i);
        Interval next = intervals.get(i + 1);
        if (current.end < next.start) {
            result.add(current);
        } else {
            next.start = current.start;
            next.end = Math.max(current.end, next.end);
        } 
    }
    result.add(intervals.get(intervals.size() - 1));
    return result;
}

Posted on | In

Test cases

1
2
3
4
5
6
""
"Hello World"
"OneWord"
"Space "
" Space"
"b   a    "

Solution 1: accepted 5ms

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

1
2
3
4
5
6
7
8
9
10
11
public int lengthOfLastWord(String s) {
    s = s.trim();
    int len = s.length();
    for(int i = len - 1; i >= 0; i--) {
        if (s.charAt(i) == ' ') {
            return len - i- 1;
            // return s.substring(i + 1, len).length();  // improved
        }
    }
    return len == 0? 0 : len;
}

Other solutions

1
2
3
public int lengthOfLastWord(String s) {
    return s.trim().length()-s.trim().lastIndexOf(" ")-1;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int lengthOfLastWord(String s) {
        String s1 = s.trim();
        int count = 0;
        for(int i = s1.length() - 1; i >=0; i--){
            if (s1.charAt(i) != ' '){
                count ++;
            }
            else{
                break;
            }
        }
        
       return count; 
    }
}

Posted on | In

Solution 1: accepted

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
public static int[][] generateMatrix(int n) {
	int[][] ret = new int[n][n];
	int left = 0,top = 0;
	int right = n -1,down = n - 1;
	int count = 1;
	while (left <= right) {
		for (int j = left; j <= right; j ++) {
			ret[top][j] = count++;
		}
		top ++;
		for (int i = top; i <= down; i ++) {
			ret[i][right] = count ++;
		}
		right --;
		for (int j = right; j >= left; j --) {
			ret[down][j] = count ++;
		}
		down --;
		for (int i = down; i >= top; i --) {
			ret[i][left] = count ++;
		}
		left ++;
	}
	return ret;
}

Posted on | In

Solution 1: accepted

The given number has to be an integer. So “if (reversed > 214748364 || reversed < -214748364)” would be fine.
Even if it is a fit, the is not a palindrome. 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class Solution {
    public boolean isPalindrome(int x) {
       if (x < 0 || x >= 2147483642) // making huge difference in performance, probably due to the speciality of the test cases 
		return false;
	int original = x;
	int reversed = 0;
	int digit = 0;
	while (x != 0) {
		if (digit == 9) {
			if (reversed > 214748364 || reversed < -214748364)
				return false;
		}
	
		reversed = reversed * 10 + x % 10;
		x = x / 10;
		digit++;
	}
	return original == reversed;
    }
}

Solution 2: accepted 261ms

Simplified. But do we need to check the entire number?

1
2
3
4
5
6
7
8
9
10
11
public boolean isPalindrome(int x) {
    if (x < 0 || x > 0 && x % 10 == 0)
        return false;
    int original = x;
    int reverse = 0;
    while (x != 0) {
        reverse = reverse * 10 + x % 10;
        x /= 10;
    }
    return reverse == original;
}
Improvement: accepted 221ms

We only need to check half of the number

1
2
3
4
5
6
7
8
9
10
public boolean isPalindrome(int x) {
    if (x < 0 || x > 0 && x % 10 == 0)
        return false;
    int reverse = 0;
    while (x > reverse) {
        reverse = reverse * 10 + x % 10;
        x /= 10;
    }
    return (x == reverse || x == reverse/10);  // for 123321 and 12321
}

Posted on | In

Solution 1: accepted

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
public class Solution {
    public int romanToInt(String s) {
	int num = 0;
	int length = s.length();
	char[] input = s.toCharArray();
	HashMap<Character, Integer> mymap = new HashMap<Character, Integer>();	
    mymap.put('I',1);
	mymap.put('V',5);
	mymap.put('X',10);
	mymap.put('L',50);
	mymap.put('C',100);
	mymap.put('D',500);
	mymap.put('M',1000);
    	
	for (int i = length - 1; i >= 0; i--) {
        char current = input[i];
		    
        if (i == length - 1) {
            num += mymap.get(current);
            continue;
        }
        
        char after = input[i + 1];
        
		if (mymap.get(current) < mymap.get(after)) 
		    num -= mymap.get(current);
		else 
		    num += mymap.get(current);
	}	
	return num;
    }
}

30 to 37~45.62 (15-16ms)
from char[] input = s.toCharArray()
to s.charAt(i)

25 to 30
from char current
to int current

18 to 25:
from after = input[i +1]
to after = current

Doesn’t make difference:
length
charAt / char[]

Solution 2: accepted

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
public class Solution {
    public int romanToInt(String s) {
	int num = 0;
	int after = 0;
	int length = s.length();
	
	HashMap<Character, Integer> mymap = new HashMap<Character, Integer>();	
    mymap.put('I',1);
	mymap.put('V',5);
	mymap.put('X',10);
	mymap.put('L',50);
	mymap.put('C',100);
	mymap.put('D',500);
	mymap.put('M',1000);
    	
	for (int i = length - 1; i >= 0; i--) {
        int current = mymap.get(s.charAt(i));
		    
        if (i == length - 1) {
            num += current;
            after = current;
            continue;
        }
        
		if (current < after) 
		    num -= current;
		else 
		    num += current;
		after = current;
	}	
	return num;
    }
}