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

Generate Parentheses

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.
For example, given n = 3, a solution set is:
"((()))", "(()())", "(())()", "()(())", "()()()"


Idea: 
Keep track of the number of open and close brackets. If there are more open brackets than close ones and the number of open ones has not reached n, then for the next char we have two choices: add a open bracket / add a close bracket. The recursion ends when the number of close brackets reaches n.
 

public class Solution {
    ArrayList<String> result;
    public ArrayList<String> generateParenthesis(int n) {
        // Start typing your Java solution below
        // DO NOT write main() function
        result = new ArrayList<String>();
        if (n<1) return result;
        addBrackets(new String(""), n, 0, 0);
        return result;
    }
    
    private void addBrackets(String str, int target, int open, int close) {
        if (close == target) {
            result.add(str);
        }
        else {
            if (open > close) {
                addBrackets(str + ")", target, open, close + 1);
            }
            if (open < target) {
                addBrackets(str + "(", target, open + 1, close);                
            }
        }
    }
}

Find First Missing Positive

Given an unsorted integer array, find the first missing positive integer.

Problem:

For example,
Given [1,2,0] return 3,
and [3,4,-1,1] return 2.

Your algorithm should run in O(n) time and uses constant space.


Idea:

Say the array contains n numbers
Use the array index to indicate 1...n, the first missing positive must either be:
1. a number in [1...n]
2. n+1 (i.e. no missing positive in this array)

3 loops:

1. filter invalid numbers (<0 | >n), they won't help us get the answer so just set them to 0
2. for each number at A[i], set A[abs(A[i])] to negative
   abs(A[i]) - the index - is the indicator showing that positive number exists in the array
   Special case: if A[abs(A[i])] == 0, set it to an invalid number to avoid possible mis-counting during further iterations
   Here I set it to a negative number whose abs is > n so it won't be counted in further iterations
3. The first index i that A[i] >= 0 is the missing number (not affected by the previous iterations)

public class Solution {
    public int firstMissingPositive(int[] A) {
        // Start typing your Java solution below
        // DO NOT write main() function
        
        for (int i=0; i<A.length; i++) {
            if (A[i] < 0) A[i] = 0;
            else if (A[i] > A.length) A[i] = 0;
        }
        for (int i=0; i<A.length; i++) {
            int loc = Math.abs(A[i]) - 1;
            if (loc >= 0 && loc < A.length) {
                if (A[loc] > 0) {
                    A[loc] = - A[loc];
                }
                else if (A[loc] == 0) {
                    A[loc] = - A.length - 1;
                }
            }
        }
        for (int i=0; i<A.length; i++) {
            if (A[i] >= 0) return i + 1;
        }
        return A.length + 1;
    }
}

Read/Write Files Related in Java

Reading:

java.io.InputStream
  - java.io.FileInputStream
  - java.io.FilterInputStream
    - java.io.BufferedInputStream

When to use: Deal with charset problem (InputStream is byte-based, FileInputStream makes it char-based)

Example:

InputStreamReader isr = new InputStreamReader(
    new FileInputStream("test.txt"),"utf-8");   
BufferedReader br = new BufferedReader(isr);   
String str = br.readLine();  
br.close();

java.lang.Object
  - java.io.Reader
    - java.io.InputStreamReader
      - java.io.FileReader

When to use: Usually this could be easier as we can use Scanner after JDK 1.5 (Be careful to charset problem)

Example:

FileReader fr = new FileReader("file.txt");
BufferedReader br = new BufferedReader(fr);
Scanner sc = new Scanner(fr);
int i = sc.nextInt();
String str = br.readLine();
br.close();

Writing:

The class hierachy is symmetrical to reading.

Example:

FileWriter fw = new FileWriter("test.txt");
fw.write("Something");
fw.close();

(Or PrintWriter can be used but it doesn't throw IOException)

OutputStreamWriter osw = new OutputStreamWriter(
    new  FileOutputStream("file.txt"), "utf-8");
osw.write("Something");
osw.close();

Static Block in Java

A static block in Java looks like this:

class a {
    static {
    //...
    }
    public a() {
        //constructor
    }
}

take away essentials:

1. Static blocks are executed once the class is loaded (not necessarily to create a new instance).

2. Multiple static blocks are considered as one in code order.

3. Static blocks are executed before the constructor.

4. Omitting "static" will lead to that the code in these blocks are considered as "constructor block" and will be executed when the class is instantiated. The constructor block will be copied into each constructor of the class.

5. Better way:

class PrivateStaticMethodExample {
     public static varType myVar = initializeClassVariable();

    private static varType initializeClassVariable() {
        //initialization code goes here
    }
}