Weever's Road

Just another WordPress site

Category: Leetcode (Page 1 of 3)

151. Reverse Words in a String

Given an input string, reverse the string word by word.

Example:
Given s = “the sky is blue”,
return “blue is sky the”.

Trick: trim before split.

1
2
3
4
5
6
7
8
9
    public String reverseWords(String s) {
        if( s == null || s=="" || s.length() == 0)
            return s;
        String[] strs = s.trim().split("\\s+");
        List<String> list = Arrays.asList(strs);
        Collections.reverse(list);
        strs = (String[]) list.toArray();
        return String.join(" ",strs);
    }

287. Find the Duplicate Number (Hard??)

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.

Solution:

1
2
3
4
5
6
7
8
9
10
11
12
 public int findDuplicate(int[] nums) {
        if(nums == null)
            return -1;
        boolean[] check = new boolean[nums.length];
        for(int i=0 ; i< nums.length; i++){
            if(check[nums[i]])
                return nums[i];
            else
                check[nums[i]] = true;
        }
        return -1;
    }

179. Largest Number (Meduim)

Given a list of non negative integers, arrange them such that they form the largest number.
For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.
Note: The result may be very large, so you need to return a string instead of an integer.

Solution:
1: sort the number, compare the digits of number from left to right, the largest should be first.
like: compare {89,9}, the first digit 9 is largest, sort as {9,89} so the combined 989 is largest.
2. if the digits are same like {2332,23}, we have to compare left digits with shortest number again to determine which is first, 32 > 23, so sorted as {2332,23}
3. We can find trick, for each two number, we can find the law: combine numbers in both way as strings, {89,9} = {899,989}, then compare the strings so we can sort the numbers

For list, override Collections.sort()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public String largestNumber(final List<Integer> a) {
        if(a == null)
            return "0";
        Collections.sort(a, new Comparator<Integer>(){
            @Override
            public int compare(Integer n1, Integer n2){
                String s1 = String.valueOf(n1);
                String s2 = String.valueOf(n2);
                return (s2+s1).compareTo(s1+s2);
            }
        });
        if(a.get(0) == 0)
            return "0";
       StringBuffer sb = new StringBuffer();
       for(Integer i : a){
           sb.append(i);
       }
       return sb.toString();
    }

For Arrays, write Comparator function.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
 public String largestNumber(int[] nums) {
        Integer[] ints = new Integer[nums.length];
        int index = 0;
        for(int i : nums){
            ints[index++] = i;
        }
        Arrays.sort(ints,new Comparator<Integer>(){
            public int compare(Integer n1, Integer n2){
                String s1=String.valueOf(n1);
                String s2=String.valueOf(n2);
                return (s2+s1).compareTo(s1+s2);
            }
        });
       
        if(ints[0] == 0)
            return "0";
        StringBuilder sb = new StringBuilder();
        for(Integer i : ints){
            sb.append(i);
        }
       
        return sb.toString();
    }

416. Partition Equal Subset Sum (Medium)

Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:
Each of the array element will not exceed 100.
The array size will not exceed 200.

Solution:
1. If array can be divided two sum of subset equally, the total sum of array should be even.
2. Find subset, target = sum/2
2. Use boolean array dp[i], i = sum of subset, dp[i] = true if the sum exits.
3. Only need to check the sum of subset between [1, target]
4. loop nums array, for each loop, check i in dp[] between [0, min(currSum, target)]
if the previous sums in dp[] are true, plus current num, each i which is true in dp[], each i + num if also true.
5. when there is a one in loop we can find previous i + current num = target, return true; otherwise after loop, dp[target] = false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public boolean canPartition(int[] nums) {
        if(nums == null && nums.length < 2)
            return false;
        int sum = Arrays.stream(nums).sum();
        if(sum%2 == 1)
            return false;
        int target = sum/2;
       
        boolean[] dp = new boolean[target+1];
        dp[0] = true;
       
        int currSum = 0;
        for(int i=0; i < nums.length; i++){
            int max = Math.min(currSum+nums[i],target);
            for(int j = max ; j >= nums[i] ; j-- ){
                dp[j] = dp[j] || dp[j-nums[i]] ;
            }
            if (dp[target]==true)
                return true;
            currSum += nums[i];
        }
        return dp[target];
    }

56. Merge Intervals (hard)

Given a collection of intervals, merge all overlapping intervals.

For example,
Given [1,3],[2,6],[8,10],[15,18],
return [1,6],[8,10],[15,18].

Solution:
1. If the given list is sort by start.
2. Check the current intervals is overlap or inside the previous one.
if true: combine the overlap intervals, go next interval
if false: no overlap, save the previous one, set current, go next interval

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
/**
 * Definition for an interval.
 * public class Interval {
 *     int start;
 *     int end;
 *     Interval() { start = 0; end = 0; }
 *     Interval(int s, int e) { start = s; end = e; }
 * }
 */

public class Solution {
    public List<Interval> merge(List<Interval> intervals) {
        if(intervals == null || intervals.size() == 0)
            return intervals;
         Collections.sort(intervals, new Comparator<Interval>() {
            public int compare(Interval o1, Interval o2) {
                return o1.start - o2.start;
            }
        });
        List<Interval> result = new ArrayList<>();
        Interval current = intervals.get(0);
        for(int i = 1; i < intervals.size(); i++){
            if(intervals.get(i).end <= current.end){
                 current = intervals.get(i);
            }
            else if( intervals.get(i).start <= current.end){
                current = new Interval(current.start,intervals.get(i).end);
            } else {
                result.add(current);
                current = intervals.get(i);
            }
        }
        result.add(current);
        return result;
    }
}

InterviewBit solution:
1. assume the List is sorted, insert the new element in the list
2. Do the logic above

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
 public ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
        if (newInterval.end  < newInterval.start)
            newInterval = new Interval(newInterval.end, newInterval.start);
        ArrayList<Interval> result = new ArrayList();
        if(intervals == null || intervals.size() == 0){
            result.add(newInterval);
            return result;
        }
        int i = 0;
        while(i < intervals.size() && newInterval.start > intervals.get(i).start)
            i++;
        if(i == intervals.size())
            intervals.add(newInterval);
        else
            intervals.add(i,newInterval);
       
        Interval current = intervals.get(0);
        for(int j=1;j<intervals.size();j++){
            if(intervals.get(j).start <= current.end)
                current = new Interval(current.start, Math.max(current.end,intervals.get(j).end));
            else{
                result.add(current);
                current = intervals.get(j);
            }
        }
        result.add(current);
        return result;
    }

54. Spiral Matrix (Medium)

Given a matrix of m * n elements (m rows, n columns), return all elements of the matrix in spiral order.

1. Math.min() return int, cast to double then divided by 2, ceil() to find the minimum for loop times
2. check if vertical or horizontal line has only one left, then return the line to finish.

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
public ArrayList<Integer> spiralOrder(final List<ArrayList<Integer>> a) {
        ArrayList<Integer> result = new ArrayList<Integer>();
        // Populate result;
        if(a == null || a.size() == 0)
            return result;
        int rs = 0 , cs = 0;
        int re = a.size() - 1, ce = a.get(0).size() -1;
       
        for(int i = 0; i < Math.ceil(((double) Math.min(a.size(),a.get(0).size()))/2); i++){

            if (re - rs == 0) {
                for (int index = cs; index <= ce; index++)
                    result.add(a.get(rs).get(index));
                return result;
            }

            if (ce - cs == 0) {
                for (int index = rs; index <= re; index++)
                    result.add(a.get(index).get(cs));
                return result;
            }
           
            //top
            for(int index = cs ; index <= ce; index++)
                result.add(a.get(rs).get(index));
           
            //right
            for(int index = rs + 1; index <= re ; index ++)
                result.add(a.get(index).get(ce));
           
            //bottom
            for(int index = ce - 1; index >= cs; index --)
                result.add(a.get(re).get(index));
           
            //left
            for(int index = re - 1; index >= rs + 1; index --)
                result.add(a.get(index).get(cs));
           
            rs++;cs++;re--;ce--;
        }
        return result;
    }

242. Valid Anagram

242. Valid Anagram

Solution: if two String are anagram, they has some number of each letter. sort each String char, compare two String after sort.

1.sort

1
2
3
4
5
6
7
    public boolean isAnagram(String s, String t) {
        if(s == null && t == null) return true;
        if(s == null || t == null || s.length() != t.length()) return false;
        char[] ss = s.toCharArray(); Arrays.sort(ss);
        char[] tt = t.toCharArray(); Arrays.sort(tt);
        return String.valueOf(ss).equals(String.valueOf(tt));
    }

2.count:

100.Same Tree (Easy)

100. Same Tree

Solution: Recursive,
1.if both trees are null, then they are same
2.if one of them is null, they are not same
3.if they are not null and val is different, they are not same
Recursively check until last leafs on both left and(&&) right node

1
2
3
4
5
6
7
public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null)
            return true;
        if(p == null || q == null || p.val != q.val)
            return false;
        return isSameTree(p.left,q.left) && isSameTree(p.right, q.right);
    }

283. Move Zeroes (Easy)

238.Move Zeros

Solution: Compression with two pointers.

1
2
3
4
5
6
7
8
9
10
11
12
13
    public void moveZeroes(int[] nums) {
        if(nums == null || nums.length == 0)
            return;
        int current = 0, scan = 0;
        while(scan < nums.length){
            if(nums[scan] != 0)
                nums[current++] = nums[scan++];
            else
                scan++;
        }
        for(;current<nums.length;)
            nums[current++] = 0;
    }

226. Invert Binary Tree

226. Invert Binary Tree

Typical recursive.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
   public TreeNode invertTree(TreeNode root) {
        swap(root);
        return root;
   }
   
    private void swap(TreeNode root){
        if(root == null)
            return;
        swap(root.left);
        swap(root.right);
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
    }

Page 1 of 3

Powered by WordPress & Theme by Anders Norén