CTRL+A, CTRL+C, CTRL+V

Imagine you have a special keyboard with the following keys:

1. A
2. Ctrl+A
3. Ctrl+C
4. Ctrl+V

where CTRL+A, CTRL+C, CTRL+V each acts as one function key for “Select All”, “Copy”, and “Paste” operations respectively.
If you can only press the keyboard for N times (with the above four keys), please write a program to produce maximum numbers of A. If possible, please also print out the sequence of keys.
That is to say, the input parameter is N (No. of keys that you can press), the output is M (No. of As that you can produce).

I do believe there should be an O(n) solution, but sort of tricky. The O(n^2) solution is quite straightforward in DP problems.

public static int maxChar(int n) {
 int[] dp = new int[n];
 for (int i = 0; i < n; ++i) {
  dp[i] = i + 1;    // type A
 }
 for (int i = 0; i < n; ++i) {
  for (int j = i + 4; j < n; ++j) {
   dp[j] = Math.max(dp[j], dp[i] * (j - i - 3));    // using Ctrl + V
  }
 }
 return dp[n - 1];
}

Count and Say

Count and Say

The count-and-say sequence is the sequence of integers beginning as follows:
1, 11, 21, 1211, 111221, ...

1 is read off as "one 1" or 11.
11 is read off as "two 1s" or 21.
21 is read off as "one 2, then one 1" or 1211.

Given an integer n, generate the n^th sequence.

Note: The sequence of integers will be represented as a string.

Idea: use a hashmap to store the previous computed results

public class Solution {
    public String countAndSay(int n) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if (n == 0) return "";
        String str = "1";
        HashMap map = new HashMap();
        for (int i = 1; i < n; ++i) {
            int start = 0;
            StringBuffer newstr = new StringBuffer();
            for (int j = 0; j < str.length(); ++j) {
                if (j != str.length() - 1 && str.charAt(j) == str.charAt(j+1)) {
                    continue;
                }
                String stored = map.get(str.substring(start, j+1));
                if (stored == null) {
                    String strappend = String.valueOf(j - start + 1) + str.substring(start, start + 1);
                    map.put(str.substring(start, j+1), strappend);
                    newstr.append(strappend);
                }
                else {
                    newstr.append(stored);
                }
                start = j + 1;
            }
            str = newstr.toString();
        }
        return str;
    }
}

Flatten Binary Tree to Linked List

Flatten Binary Tree to Linked List

Given a binary tree, flatten it to a linked list in-place.

For example,
Given

         1
        / \
       2   5
      / \   \
     3   4   6

The flattened tree should look like:

   1
    \
     2
      \
       3
        \
         4
          \
           5
            \
             6

Pre-order Traversal

/**
 * Definition for binary tree
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public void flatten(TreeNode root) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if (root == null) return;
        Stack stack = new Stack();
        stack.push(root);
        TreeNode lastNode = null;
        while (!stack.isEmpty()) {
            TreeNode node = stack.pop();
            if (lastNode != null) {
                lastNode.left = null;
                lastNode.right = node;
            }
            lastNode = node;
            TreeNode left = node.left;
            TreeNode right = node.right;
            if (right != null) {
                stack.push(right);
            }
            if (left != null) {
                stack.push(left);
            }
        }
    }
}

4 Sum

4Sum

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note:

• Elements in a quadruplet (a,b,c,d) must be in non-descending order. (ie, a ≤ b ≤ c ≤ d)
• The solution set must not contain duplicate quadruplets.

    For example, given array S = {1 0 -1 0 -2 2}, and target = 0.

    A solution set is:
    (-1,  0, 0, 1)
    (-2, -1, 1, 2)
    (-2,  0, 0, 2)

public class Solution {
    public ArrayList> fourSum(int[] num, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function
        Arrays.sort(num);
        ArrayList<Integer> list = new ArrayList<Integer>();
        
        for (int i = 0; i < num.length - 3; i++) {
            int a = num[i];
            for (int j = i + 1; j < num.length - 2; j++) {
                int b = num[j];
                int k = j + 1;
                int l = num.length - 1;
                while (k < l) {
                    int c = num[k];
                    int d = num[l];
                    if (a + b + c + d == target) {
                        ArrayList sublist = new ArrayList();
                        sublist.add(a);
                        sublist.add(b);
                        sublist.add(c);
                        sublist.add(d);
                        list.add(sublist);
                        k++;
                        while (num[k] == num[k - 1] && k - 1 != j && k < l) {
                            k++;
                        }
                        l--;
                        while (num[l] == num[l + 1] && k < l) {
                            l--;
                        } 
                    }
                    else if (a + b + c + d < target) {
                        k++;
                        while (num[k] == num[k - 1] && k - 1 != j && k < l) {
                            k++;
                        }
                    }
                    else {
                        l--;
                        while (num[l] == num[l + 1] && k < l) {
                            l--;
                        } 
                    }
                }
                
                while (j + 1 < num.length - 2 && num[j + 1] == num[j]) {
                    j++;
                }
            }
            
            while (i + 1 < num.length - 3 && num[i + 1] == num[i]) {
                i++;
            }
        }
        
        return list;
    }
}

3 Sum Closest

3Sum Closest

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution.

    For example, given array S = {-1 2 1 -4}, and target = 1.

    The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).

public class Solution {
    public int threeSumClosest(int[] num, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function
        Arrays.sort(num);
        ArrayList> list = new ArrayList>();
        
        Integer closest = null;
        
        for (int i = 0; i <= num.length - 3; i++) {
            int a = num[i];
            int j = i+1;
            int k = num.length - 1;
            if (closest == null) closest = a + num[j] + num[k];
            
            int best = closest.intValue();
            
            while (j < k) {
                int b = num[j];
                int c = num[k];
                if (a + b + c == target) {
                    return a + b + c;
                }
                else if (a + b + c < target) {
                    if (Math.abs(a + b + c - target)
                        < Math.abs(best - target)) {
                        best = a + b + c;
                    }
                    j++;
                }
                else {
                    if (Math.abs(a + b + c - target)
                        < Math.abs(best - target)) {
                        best = a + b + c;
                    }
                    k--;
                }
            }
            
            if (Math.abs(best - target) < Math.abs(closest.intValue() - target)) {
                closest = best;
            }
        }
        
        return closest.intValue();
    }
    
}

3 Sum

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

• Elements in a triplet (a,b,c) must be in non-descending order. (ie, a ≤ b ≤ c)
• The solution set must not contain duplicate triplets.

    For example, given array S = {-1 0 1 2 -1 -4},

    A solution set is:
    (-1, 0, 1)
    (-1, -1, 2)

public class Solution {
    public ArrayList> threeSum(int[] num) {
        // Start typing your Java solution below
        // DO NOT write main() function
        Arrays.sort(num);
        ArrayList<Integer> list = new ArrayList<Integer>();
        
        for (int i = 0; i <= num.length - 3; i++) {
            int a = num[i];
            int j = i+1;
            int k = num.length - 1;
            while (j < k) {
                int b = num[j];
                int c = num[k];
                if (a + b + c == 0) {
                    ArrayList sublist = new ArrayList();
                    sublist.add(a);
                    sublist.add(b);
                    sublist.add(c);
                    list.add(sublist);
                    j++;
                    while (num[j] == num[j - 1] && j - 1 != i && j < k) {
                        j++;
                    }
                    k--;
                    while (num[k] == num[k + 1] && j < k) {
                        k--;
                    } 
                }
                else if (a + b + c < 0) {
                    j++;
                    while (num[j] == num[j - 1] && j - 1 != i && j < k) {
                        j++;
                    }
                }
                else {
                    k--;
                    while (num[k] == num[k + 1] && j < k) {
                        k--;
                    } 
                }
            }
            
            while (i + 1 <= num.length - 3 && num[i + 1] == num[i]) {
                i++;
            }
        }
        
        return list;
    }
}

Best Time to Buy and Sell Stock

Best Time to Buy and Sell Stock

Say you have an array for which the i^th element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

DP Solution:

public class Solution {
    public int maxProfit(int[] prices) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if (prices.length <= 1) return 0;
        int min = prices[0];
        int maxProfit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] < min) min = prices[i];
            maxProfit = Math.max(prices[i] - min, maxProfit);
        }
        return maxProfit;
    }
}

Divide-n-Conquer:

public class Solution {
    private class MaxMin {
        public int max;
        public int min;
        public int profit;
        public MaxMin(int max, int min, int profit) {
            this.max = max;
            this.min = min;
            this.profit = profit;
        }
    }
    
    public int maxProfit(int[] prices) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if (prices.length <= 1) return 0;
        return _maxProfit(prices, 0, prices.length - 1).profit;
    }
    
    private MaxMin _maxProfit(int[] prices, int left, int right) {
        if (right - left <= 1) {
            MaxMin m = new MaxMin(
                Math.max(prices[right], prices[left]),
                Math.min(prices[right], prices[left]),
                Math.max(0, prices[right] - prices[left]));
            return m;
        }
        int mid = (right + left) / 2;
        MaxMin lm = _maxProfit(prices, left, mid);
        MaxMin rm = _maxProfit(prices, mid+1, right);
        int maxProfit = Math.max(Math.max(lm.profit, rm.profit), rm.max - lm.min);
        int min = Math.min(lm.min, rm.min);
        int max = Math.max(lm.max, rm.max);
        MaxMin m = lm;
        m.min = min;
        m.max = max;
        m.profit = maxProfit;
        return m;
    }
}

Merge Two Sorted Lists

Merge Two Sorted Lists

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

Time complexity: O(m+n)

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ListNode root = null;
        ListNode node = null;
        while (l1 != null && l2 != null) {
            if (l1.val < l2.val) {
                if (node == null) {
                    node = l1;
                    root = node;
                }
                else {
                    node.next = l1;
                    node = node.next;
                }
                l1 = l1.next;
            }
            else {
                if (node == null) {
                    node = l2;
                    root = node;
                }
                else {
                    node.next = l2;
                    node = node.next;
                }
                l2 = l2.next;
            }
        }
        
        while (l1 != null) {
            if (node == null) {
                node = l1;
                root = node;
            }
            else {
                node.next = l1;
                node = node.next;
            }
            l1 = l1.next;
        }
        
        
        while (l2 != null) {
            if (node == null) {
                node = l2;
                root = node;
            }
            else {
                node.next = l2;
                node = node.next;
            }
            l2 = l2.next;
        }
        return root;
    }
}

Merge Sorted Array

Merge Sorted Array

Given two sorted integer arrays A and B, merge B into A as one sorted array.

Note:
You may assume that A has enough space to hold additional elements from B. The number of elements initialized in A and B are m and n respectively.

Idea: Simply do it in reverse order

class Solution {
public:
    void merge(int A[], int m, int B[], int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int i = m - 1, j = n - 1, k = m + n - 1;
        while (i >= 0 && j >= 0) {
            if (A[i] < B[j]) {
                A[k] = B[j];
                --j;
            }
            else {
                A[k] = A[i];
                --i;
            }
            --k;
        }
        
        while (j >= 0) {
            // copy the rest of B into A
            A[k] = B[j];
            --k;
            --j;
        }
    }
};

Merge k Sorted Lists

Merge k Sorted Lists

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

Note: Merge sort was used.
Time complexity: O(nlgk).

/** 
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
public class Solution {
    public ListNode mergeKLists(ArrayList<listnode> lists) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if (lists.size() == 0) return null;
        ArrayList<listnode> klist = new ArrayList<listnode>();
        for (int i = 0; i &lt; lists.size(); i++) {
            ListNode node = lists.get(i);
            if (node != null) {
                klist.add(node);
            }
        }
        Collections.sort(klist, new Comparator<listnode>() {
            public int compare(ListNode n1, ListNode n2) {
                return n1.val - n2.val;
            }
        });
        ListNode root = null;
        ListNode node = null;
        
        while (!klist.isEmpty()) {
            
            if (root == null) {
                root = klist.get(0);
                node = root;
            }
            else {
                node.next = klist.get(0);
                node = node.next;
            }
            
            klist.set(0, klist.get(0).next);
            if (klist.get(0) == null) {
                klist.remove(0);
            }
            
            if (klist.isEmpty()) {
                break;
            }
            
            Collections.sort(klist, new Comparator<listnode>() {
                public int compare(ListNode n1, ListNode n2) {
                    return n1.val - n2.val;
                }
            });
            
            
        }
        return root;
    }
}

Search for a Range

Search for a Range

Given a sorted array of integers, find the starting and ending position of a given target value.

Your algorithm's runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

For example,
Given [5, 7, 7, 8, 8, 10] and target value 8,
return [3, 4].

Key: Binary search

public class Solution {
    public int[] searchRange(int[] A, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int left = getLeft(A, target);
        int right = getRight(A, target);
        return new int[]{left, right};
    }
    
    public int getLeft(int[] A, int target) {
        int start = 0;
        int end = A.length - 1;
        while (end >= start) {
            if (end == start) {
                if (A[start] == target) 
                    return start;
                else 
                    return -1;
            }
            
            int mid = (start + end) / 2;
            if (A[mid] > target) {
                end = mid - 1;
            }
            else if (A[mid] < target) {
                start = mid + 1;
            }
            else {
                end = mid;
            }
        }
        return -1;
    }
    
    public int getRight(int[] A, int target) {
        int start = 0;
        int end = A.length - 1;
        while (end >= start) {
            if (end == start) {
                if (A[start] == target) 
                    return start;
                else 
                    return -1;
            }
            
            int mid = (start + end) / 2;
            if (A[mid] > target) {
                end = mid - 1;
            }
            else if (A[mid] < target) {
                start = mid + 1;
            }
            else {
                if (end - start == 1) {
                    if (A[end] == target) {
                        return end;
                    }
                    else {
                        return start;
                    }
                }
                start = mid;
            }
        }
        return -1;
    }
}

Search a 2D Matrix

Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

• Integers in each row are sorted from left to right.
• The first integer of each row is greater than the last integer of the previous row.

For example,

Consider the following matrix:

[
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]

Given target = 3, return true.

Key: Binary search (There may be better code than mine in locating row number. The edge condition is when only two rows left. Incorrect treatment may lead to incorrect answer or infinite loop.)

public class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        // Start typing your Java solution below
        // DO NOT write main() function
        
        //locate row
        int rs = 0;
        int re = matrix.length - 1;
        while (re - rs > 1) {
            int rm = (rs + re) / 2;
            if (matrix[rm][0] > target) {
                re = rm;
            }
            else if (matrix[rm][0] < target) {
                rs = rm;
            }
            else {
                return true;
            }
        }
        
        int row = 0;
        
        if (matrix[rs][0] > target) {
            return false;
        }
        
        if (matrix[re][0] <= target) {
            row = re;
        }
        else {
            row = rs;
        }
        
        int start = 0;
        int end = matrix[row].length - 1;
        
        if (matrix[row][start] == target || matrix[row][end] == target) {
            return true;
        }
        else if (matrix[row][end] < target) {
            return false;
        }
        else {
            //might be in this row
            while (start < end) {
                if (matrix[row][start] == target || matrix[row][end] == target) {
                    return true;
                }
                int mid = (start + end) / 2;
                if (matrix[row][mid] > target) {
                    end = mid - 1;
                }
                else if (matrix[row][mid] < target) {
                    start = mid + 1;
                }
                else {
                    return true;
                }
            }
            return false;
        }
    }
}

Longest Valid Parentheses

Longest Valid Parentheses

Given a string containing just the characters '(' and ')', find the length of the longest valid (well-formed) parentheses substring.

For "(()", the longest valid parentheses substring is "()", which has length = 2.

Another example is ")()())", where the longest valid parentheses substring is "()()", which has length = 4.

public class Solution {
    public int longestValidParentheses(String s) {
        int n = s.countgth();
        int maxCount = 0;
        int lb = 0;
        int count = 0;
        for(int i = 0; i < n; i++){
            if(s.charAt(i) == '('){
                lb++;
                count++;
            }
            if(s.charAt(i) == ')') {
                lb--;
                count++;
            }
            if(lb == 0 && count > maxCount) {
                maxCount = count;
            }
            else if(lb < 0){
                //invalid
                lb = 0;
                count = 0;
            }
        }
        int rb = 0;
        count = 0;
        for(int i = n-1; i >= 0; i--) {
            if(s.charAt(i) == ')'){
                rb++;
                count++;
            }
            if(s.charAt(i) == '(') {
                rb--;
                count++;
            }
            if(lb == 0 && count > maxCount) {
                maxCount = count;
            }
            else if(lb < 0){
                //invalid
                rb = 0;
                count = 0;
            }
        }
        return maxCount;
    }
}

Jump Game II

Jump Game II

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.

Your goal is to reach the last index in the minimum number of jumps.

For example:
Given array A = [2,3,1,1,4]

The minimum number of jumps to reach the last index is 2. (Jump 1 step from index 0 to 1, then 3 steps to the last index.)

 
Strategy: Greedy (reversed order)

Complexity: O(n^2)

public class Solution {
    public int jump(int[] A) {
        // Start typing your Java solution below
        // DO NOT write main() function
        if (A.length == 1) return 0;
        int lastIndex = A.length - 1;
        int steps = 0;
        while (lastIndex > 0) {
            int preIndexMin = lastIndex;
            for (int i=lastIndex - 1; i>=0; i--) {
                if (A[i] >= lastIndex - i) {
                    if (preIndexMin > i) {
                        preIndexMin = i;
                    }
                }
            }
            if (lastIndex == preIndexMin) return -1;
            lastIndex = preIndexMin;
            steps++;
        }
        return steps;
    }
}

Jump Game

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.

Strategy: For each '0' in the array, find if it could be jumped over from its previous indexes, or if we can directly jump to the end.

Complexity: O(n^2)?

public class Solution {
    public boolean canJump(int[] A) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int end = A.length - 1;
        for (int i=0; i<A.length; i++) {
            if (A.length != 1 && A[i] == 0 && i != end) {
                int nextNonZeroIndex = i+1;
                while (nextNonZeroIndex < end) {
                    if (A[nextNonZeroIndex] > 0) {
                        break;
                    }
                    else {
                        nextNonZeroIndex++;
                    }
                }   //max: end
                int j = i - 1;
                boolean continueSearch = false;
                while (j>=0) {
                    if (A[j] >= end - j || A[j] >= nextNonZeroIndex - j) {
                        continueSearch = true;
                        break;
                    }
                    j--;
                }
                if (!continueSearch)
                    return false;
            }
            
        }
        return true;
    }
}

Spiral Matrix

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

For example,
Given the following matrix:

[
 [ 1, 2, 3 ],
 [ 4, 5, 6 ],
 [ 7, 8, 9 ]
]

You should return [1,2,3,6,9,8,7,4,5].

 public static ArrayList spiralOrder(int[][] matrix) {
        // Start typing your Java solution below
        // DO NOT write main() function
        ArrayList res = new ArrayList();
        if (matrix.length == 0) {
            return res;
        }
        
        int colStart = 0;
        int colEnd = matrix[0].length - 1;
        int rowStart = 0;
        int rowEnd = matrix.length - 1;
        
        while (colStart <= colEnd && rowStart <= rowEnd) {
            for (int i=colStart; i<=colEnd; i++) {
                res.add(matrix[rowStart][i]);
            }
            rowStart++;
            for (int i=rowStart; i<=rowEnd; i++) {
                res.add(matrix[i][colEnd]);
            }
            colEnd--;
            if (rowStart > rowEnd) break;
            for (int i=colEnd; i>=colStart; i--) {
                res.add(matrix[rowEnd][i]);
            }
            rowEnd--;
            if (colStart > colEnd) break;
            for (int i=rowEnd; i>=rowStart; i--) {
                res.add(matrix[i][colStart]);
            }
            colStart++;
        }
        return res;
    }

Given an integer n, generate a square matrix filled with elements from 1 to n² in spiral order.

For example,
Given n = 3,

You should return the following matrix:

[
 [ 1, 2, 3 ],
 [ 8, 9, 4 ],
 [ 7, 6, 5 ]
]

public class Solution {
    public int[][] generateMatrix(int n) {
        // Start typing your Java solution below
        // DO NOT write main() function
        int[][] matrix = new int[n][n];
        int colStart = 0;
        int colEnd = n - 1;
        int rowStart = 0;
        int rowEnd = n - 1;
        int val = 1;
        
        while (colStart <= colEnd && rowStart <= rowEnd) {
            for (int i = colStart; i <= colEnd; i++) {
                matrix[rowStart][i] = val;
                val++;
            }
            
            rowStart++;
            
            for (int i = rowStart; i <= rowEnd; i++) {
                matrix[i][colEnd] = val;
                val++;
            }
            
            colEnd--;
            
            for (int i = colEnd; i >= colStart; i--) {
                matrix[rowEnd][i] = val;
                val++;
            }
            
            rowEnd--;
            
            for (int i = rowEnd; i >= rowStart; i--) {
                matrix[i][colStart] = val;
                val++;
            }
            
            colStart++;
        }
        return matrix;
    }
}

Permutations

Permutations

Given a collection of numbers, return all possible permutations.

For example,
[1,2,3] have the following permutations:
[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], and [3,2,1].

public class Solution {

    public ArrayList<ArrayList<Integer>> permute(int[] num) {

        // Start typing your Java solution below

        // DO NOT write main() function

        ArrayList<ArrayList<Integer>> permutations =

               new ArrayList<ArrayList<Integer>>();

        permutations.add(new ArrayList<Integer>());

        for (int i=0; i<num.length; i++) {

            int currentSize = permutations.size();

            for (int j=0; j<currentSize; j++) {

                ArrayList<Integer> sub = permutations.get(0);

                permutations.remove(sub);

                for (int k=0; k<=sub.size(); k++) {

                    ArrayList<Integer> newSub = new ArrayList<Integer>(sub);

                    newSub.add(k,num[i]);

                    permutations.add(newSub);

                }

            }

        }

        return permutations;

    }

}

Thirty One

Problem Statement

Thirty One is a card game for 2 or more players. The game can be played with one or more decks of standard cards. The aim of the game is to try and make the value of your hand as close to 31 points as possible without going over 31 points. A hand consists of exactly 3 cards.

Each number card (2, 3, ... 9, 10) is worth the value written on the card; Jack (J), Queen (Q) and King (K) are all worth 10; while an Ace (A) is worth either 1 or 11 depending on which will give a greater total without going over 31 points. There is one exception however; if a hand consists of 3 identical cards then the value of that hand automatically becomes 30.5 points.

Each element in hands will contain exactly three cards, where cards are separated by exactly one space. For example "A 10 K" is a hand consisting of Ace, 10 and King. The value of this hand is 11 + 10 + 10 = 31. Note that we chose Ace to be 11 and not 1 since that gives us a greater total without exceeding 31.

Given a String[] of players' hands return the index of the winning player, where element i (0-indexed) in hands belongs to player i. If two or more players are tied for the lead then return the player with the lower index.

public class ThirtyOne {
 public static int findWinner(String[] hands) {
  int totalPlyrs = hands.length;
  float[] totalPoints = new float[totalPlyrs];
  int[] numOfAs = new int[totalPlyrs];
  float maxPoint = 0.0f;
  int maxLoc = totalPlyrs - 1;
  for (int i=0; i<totalPlyrs; i++) {
   totalPoints[i] = 0;
   numOfAs[i] = 0;
   String hand = hands[i];
   for (int j=0; j<hand.length(); j++) {
    if (hand.length() == 8 || (hand.length() == 5 && hand.charAt(0) == hand.charAt(2) && hand.charAt(2) == hand.charAt(4))) {
     totalPoints[i] = 30.5f;
     break;
    }
   
    if (hand.charAt(j) == 'J' || hand.charAt(j) == 'Q' || hand.charAt(j) == 'K') {
     totalPoints[i]+=10;
    }
    else if (hand.charAt(j) >= '2' && hand.charAt(j) <= '9') {
     totalPoints[i]+= (hand.charAt(j) - '0');
    }
    else if (hand.charAt(j) == '1') {
     if (i<hand.length()-1) {
      if (hand.charAt(j+1) == '0') {
       totalPoints[i]+=10;
       j++;
      }
      else {
       totalPoints[i]+=1;
      }
     }
     else {
      totalPoints[i]+=1;
     }
    }
    
    else if (hand.charAt(j) == 'A') {
     totalPoints[i]+=11;
     numOfAs[i]++;
    }
   }
   
   while (numOfAs[i] > 0) {
    if (totalPoints[i] > 31) {
     numOfAs[i]--;
     totalPoints[i]-=10;
    }
    else {
     break;
    }
   }
   
  }
  
  for (int i=totalPlyrs-1; i>0; i--) {
   if (totalPoints[i] >= maxPoint && totalPoints[i]<=31) {
    maxLoc = i;
    maxPoint = totalPoints[i];
   }
  }
  return maxLoc; 
 }
}

Insert Interval

Given a set of non-overlapping intervals, insert a new interval into the intervals (merge if necessary).

You may assume that the intervals were initially sorted according to their start times.

Example 1:
Given intervals [1,3],[6,9], insert and merge [2,5] in as [1,5],[6,9].

Example 2:
Given [1,2],[3,5],[6,7],[8,10],[12,16], insert and merge [4,9] in as [1,2],[3,10],[12,16].

This is because the new interval [4,9] overlaps with [3,5],[6,7],[8,10].

Idea: Easy question. Linear visiting.

/**
 * 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 ArrayList<Interval> insert(ArrayList<Interval> intervals, Interval newInterval) {
        // Start typing your Java solution below
        // DO NOT write main() function
        boolean merge = false;
        for (int i=0; i<intervals.size(); i++) {
            Interval inv = intervals.get(i);
            if (newInterval.start <= inv.start && newInterval.end >= inv.start) {
                merge = true;
                inv.start = newInterval.start;
            }
            
            else if (newInterval.start <= inv.end && newInterval.start >= inv.start) {
                merge = true;
            }
            
            
            if (merge) {
                //find end
                for (int j = i; j<intervals.size(); j++) {
                    inv = intervals.get(j);
                    if (inv.end >= newInterval.end) {
                        break;
                    }
                    else if (j+1 < intervals.size() && newInterval.end <= intervals.get(j+1).start) {
                        inv.end = newInterval.end;
                        break;
                    }
                    else if (j+1 >= intervals.size()) {
                        inv.end = newInterval.end;
                        break;
                    }
                    else {
                        if (j+1 < intervals.size()) {
                            inv.end = intervals.get(j+1).start;
                        }
                    }
                }
                break;
            }
            else {
                if (newInterval.start > inv.end && i+1 < intervals.size() &
                           & intervals.get(i+1).start > newInterval.end) {
                    intervals.add(i+1, newInterval);
                    return intervals;
                }
                else if (newInterval.start > inv.end && i+1 == intervals.size()) {
                    intervals.add(newInterval);
                    return intervals;
                }
                else if (newInterval.end < inv.start) {
                    intervals.add(i, newInterval);
                    return intervals;
                }
            }
        }
        
        ArrayList<Interval> result = new ArrayList<Interval>();
        if (merge) {
            for (int i=0; i<intervals.size(); i++) {
                Interval inv = intervals.get(i);
                result.add(inv);
                for (int j=i+1; j<intervals.size(); j++) {
                    if (inv.end == intervals.get(j).start) {
                        inv.end = intervals.get(j).end;
                        i = j;
                    }
                }
            }
        }
        else {
            if (intervals.size() == 0) {
                intervals.add(newInterval);
            }
            return intervals;
        }
        return result;
    }
}