Weever's Road

Just another WordPress site

Author: weever (Page 2 of 4)

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

Wave Array

Given an array of integers, sort the array into a wave like array and return it,
In other words, arrange the elements into a sequence such that a1 >= a2 <= a3 >= a4 <= a5..... Example Given [1, 2, 3, 4] One possible answer : [2, 1, 4, 3] Another possible answer : [4, 1, 3, 2] Solution: 1.Sort the array 2.switch each two number along the array 3.boundary condition: a.size()-1 avoid Index out of boundary if array has odd elements.

1
2
3
4
5
6
7
8
9
10
11
    public ArrayList<Integer> wave(ArrayList<Integer> a) {
        if(a == null)
            return a;
       Collections.sort(a);
       for(int i=0; i < a.size()-1; i+=2){
           int temp = a.get(i);
           a.set(i,a.get(i+1));
           a.set(i+1,temp);
       }
       return a;
    }

Add One To Number (Easy)

Given a non-negative number represented as an array of digits,
add 1 to the number ( increment the number represented by the digits ).
The digits are stored such that the most significant digit is at the head of the list.

Example:
If the vector has [1, 2, 3]
the returned vector should be [1, 2, 4]
as 123 + 1 = 124.

Corner case: [0,6,6,0,9] need to remove the 0 at head of array/list

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 ArrayList<Integer> plusOne(ArrayList<Integer> a) {
        if(a==null){
            a = new ArrayList<>();
            a.add(1);
            return a;
        }
       
        int carry = 1;
        int sum =0;
        int index = a.size() - 1;
       
        while(carry == 1 && index >=0 ){
            sum = a.get(index) + carry;
            carry = sum/10;
            a.set(index,sum%10);
            index--;
        }
       
        if(carry ==1)
            a.add(0,1);
       
        while(a.get(0) == 0){
            a.remove(0);
        }
       
        return a;
    }

Min Steps in Infinite Grid

You are given a sequence of points and the order in which you need to cover the points. Give the minimum number of steps in which you can achieve it. You start from the first point.

Example :

Input : [(0, 0), (1, 1), (1, 2)]
Output : 2
It takes 1 step to move from (0, 0) to (1, 1). It takes one more step to move from (1, 1) to (1, 2).

This question is intentionally left slightly vague. Clarify the question by trying out a few cases in the “See Expected Output” section.

Solution:
The shortest way from point A to point B is go diagonal as possible as it can. the shortest way is max(x1-x2,y1-y2), sum all of steps between points.

1
2
3
4
5
6
7
    public int coverPoints(ArrayList<Integer> X, ArrayList<Integer> Y) {
        int step = 0;
        for(int i=0; i < X.size() - 1; i++){
            step += Math.abs(X.get(i+1)-X.get(i)) > Math.abs(Y.get(i+1)-Y.get(i)) ? Math.abs(X.get(i+1)-X.get(i)) : Math.abs(Y.get(i+1)-Y.get(i));
        }
        return step;
    }

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 2 of 4

Powered by WordPress & Theme by Anders Norén