Showing posts with label Greedy. Show all posts
Showing posts with label Greedy. Show all posts

Wednesday, July 12, 2017

402. Remove K Digits

Given a non-negative integer num represented as a string, remove k digits from the number so that the new number is the smallest possible.
Note:
  • The length of num is less than 10002 and will be ≥ k.
  • The given num does not contain any leading zero.
Example 1:
Input: num = "1432219", k = 3
Output: "1219"
Explanation: Remove the three digits 4, 3, and 2 to form the new number 1219 which is the smallest.
Example 2:
Input: num = "10200", k = 1
Output: "200"
Explanation: Remove the leading 1 and the number is 200. Note that the output must not contain leading zeroes.
Example 3:
Input: num = "10", k = 2
Output: "0"
Explanation: Remove all the digits from the number and it is left with nothing which is 0.



Solution:

We use a stack to store every character of the number.

Go through all characters in the string.

If we find the current character is smaller than the last one in the stack, we replace the last character with the current one and decreased k.

Otherwise we simply push it into the stack.

After going through the above process, we still have two cases.

1. 1111 and k > 0

2. 1234 and k > 0

For both cases, we simply remove the last character k times.

Finally, we rebuild the string.



Code:


public class Solution {
    public String removeKdigits(String num, int k) {
        int n = num.length();
        if (k >= n) {
            return "0";
        }
        Stack<Character> stack = new Stack<>();
        int i = 0;
        while (i < n) {
            while (k > 0 && !stack.isEmpty() && num.charAt(i) < stack.peek()) {
                stack.pop();
                k--;
            }
            stack.push(num.charAt(i));
            i++;
        }
        while (k > 0) {
            stack.pop();
            k--;
        }
        StringBuilder sb = new StringBuilder();
        while (!stack.isEmpty()) {
            sb.append(stack.pop());
        }
        sb.reverse();
        while (sb.length() > 1 && sb.charAt(0) == '0') {
            sb.deleteCharAt(0);
        }
        return sb.toString();
    }
}

Monday, June 26, 2017

406. Queue Reconstruction by Height

Suppose you have a random list of people standing in a queue. Each person is described by a pair of integers (h, k), where h is the height of the person and k is the number of people in front of this person who have a height greater than or equal to h. Write an algorithm to reconstruct the queue.
Note:
The number of people is less than 1,100.
Example
Input:
[[7,0], [4,4], [7,1], [5,0], [6,1], [5,2]]

Output:
[[5,0], [7,0], [5,2], [6,1], [4,4], [7,1]]



Solution:

Use a comparator to sort the array with two conditions:

1. Height (h) in descending order.

2. People taller than this guy (k) in ascending order.

Then we insert every people to the list according to his k value.



Code:


public class Solution {
    public int[][] reconstructQueue(int[][] people) {
        Arrays.sort(people, new Comparator<int[]>() {
            public int compare(int[] p1, int[] p2) {
                if (p1[0] != p2[0]) {
                    return p2[0] - p1[0];
                }
                return p1[1] - p2[1];
            }
        });
        List<int[]> order = new ArrayList<>();
        for (int[] p : people) {
            order.add(p[1], p);
        }
        return order.toArray(new int[people.length][]);
    }
}

Sunday, May 28, 2017

44. Wildcard Matching

Implement wildcard pattern matching with support for '?' and '*'.
'?' Matches any single character.
'*' Matches any sequence of characters (including the empty sequence).

The matching should cover the entire input string (not partial).

The function prototype should be:
bool isMatch(const char *s, const char *p)

Some examples:
isMatch("aa","a") → false
isMatch("aa","aa") → true
isMatch("aaa","aa") → false
isMatch("aa", "*") → true
isMatch("aa", "a*") → true
isMatch("ab", "?*") → true
isMatch("aab", "c*a*b") → false



Solution:

Method 1: Two Pointers

We use two pointers.

One points to the string and one points to the pattern.

When we find a '?' in the pattern, we advance two pointers.

When we find a '*' in the pattern, we mark the current index of the string and the current index of the '*'. And start to do the match from mark and star + 1.

If we cannot find match, we go back to mark + 1 and star + 1 and try to match. (Every time we backtrack, we need to increase mark by 1.)

Worst case time complexity is O(mn).

The space complexity is O(1).



Code:


public class Solution {
    public boolean isMatch(String s, String p) {
        int i = 0;
        int j = 0;
        int mark = 0;
        int star = -1;
        while (i < s.length()) {
            if (j < p.length() && (s.charAt(i) == p.charAt(j) || p.charAt(j) == '?')) {
                i++;
                j++;
            }
            else if (j < p.length() && p.charAt(j) == '*') {
                mark = i;
                star = j;
                j++;
            }
            else if (star != -1) {
                mark++;
                i = mark;
                j = star + 1;
            }
            else {
                return false;
            }
        }
        while (j < p.length() && p.charAt(j) == '*') {
            j++;
        }
        return j == p.length();
    }
}



Method 2: Dynamic Programming


Code:


Saturday, May 13, 2017

134. Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.
Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.
Note:
The solution is guaranteed to be unique.



Solution:

1. If from start we cannot get to station i, we know from start, no one can get to station i. Therefore station 0 to i can be safely removed from candidates.

2. If from to end, the total gas - total cost < 0, we know it is impossible from any station to drive a loop. So there is no solution.



Code:


public class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int totalGas = 0;
        int leftOver = 0;
        int res = 0;
        for (int i = 0; i < gas.length; i++) {
            totalGas += gas[i] - cost[i];
            leftOver += gas[i] - cost[i];
            if (leftOver < 0) {
                leftOver = 0;
                res = i + 1;
            }
        }
        return totalGas >= 0 ? res : -1;
    }
}

Thursday, May 11, 2017

253. Meeting Rooms II

Given an array of meeting time intervals consisting of start and end times [[s1,e1],[s2,e2],...] (si < ei), find the minimum number of conference rooms required.
For example,
Given [[0, 30],[5, 10],[15, 20]],
return 2.



Solution:

We split the input array to two arrays: one with all the start points and the other with all the end points.

Sort these two arrays.

Use two pointers point to two arrays and compare each element.

If we find start time is less than end time, we know we need one more room.

If we find start time is larger than end time, we know we can release a room

We keep a max value of the rooms we need.

The time complexity is O(nlogn) since we use sort.



Code:


/**
 * 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 int minMeetingRooms(Interval[] intervals) {
        int[] starts = new int[intervals.length];
        int[] ends = new int[intervals.length];
        for (int i = 0; i < intervals.length; i++) {
            starts[i] = intervals[i].start;
            ends[i] = intervals[i].end;
        }
        Arrays.sort(starts);
        Arrays.sort(ends);
        int maxRoom = 0;
        int room = 0;
        int i = 0;
        int j = 0;
        while (i < starts.length) {
            if (starts[i] < ends[j]) {
                room++;
                maxRoom = Math.max(maxRoom, room);
                i++;
            }
            else if (starts[i] > ends[j]) {
                room--;
                j++;
            }
            else {
                i++;
                j++;
            }
        }
        return maxRoom;
    }
}

Sunday, May 7, 2017

55. Jump Game

Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position. 
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.



Solution:

We maintains the max distance that we can jump (a greedy algorithm).

If at any position, we find we can jump to here, we set the max distance to be the max of previous max distance and the distance we can jump from the current position.

If we find we can jump to the end, return true.

After trying all positions, we know we have not reach the end, so we return false;

The time complexity is O(n).



Code:


public class Solution {
    public boolean canJump(int[] nums) {
        int maxReach = 0;
        for (int i = 0; i < nums.length; i++) {
            if (i <= maxReach) {
                maxReach = Math.max(maxReach, i + nums[i]);
            }
            if (maxReach >= nums.length - 1) {
                return true;
            }
        }
        return false;
    }
}

Saturday, April 29, 2017

122. Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).



Solution:

Whenever we find the stock price is higher than last day, we buy at last day and sell at current day.

For example, if the input prices are [1, 2, 3, 4, 5]

We do max = (2 - 1) + (3 - 2) + (4 - 3) + (5 - 4)

It is equivalent to max = 5 - 1.



Code:


public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int max = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1]) {
                max += prices[i] - prices[i - 1];
            }
        }
        return max;
    }
}