Weever's Road

Just another WordPress site

Category: Medium

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

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

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

Powered by WordPress & Theme by Anders Norén