Jane Xie: July 2015

Friday, July 24, 2015

Merge K Sorted Lists -- Leetcode

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

Answer:
Using Heap.
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
private:
struct cmp{
bool operator()(ListNode* lhs, ListNode *rhs){
if(lhs->val < rhs->val) return false;
else return true;
}
};
public:
ListNode *mergeKLists(vector<ListNode *> &lists) {
int K = lists.size();
if (K == 0) return NULL;
else if (K == 1) return lists[0];

ListNode *listHead(NULL), *listRear(NULL);
ListNode *node(NULL);
priority_queue<ListNode*, vector<ListNode*>, cmp> h;

// push K list heads into heap
for(int i=0; i<K; ++i)
if(lists[i] != NULL){
h.push(lists[i]);
lists[i] = lists[i]->next;
}

while(!h.empty()){
//pop the min of k nodes
node = h.top(); h.pop();
if(node->next)
h.push(node->next);

//insert node into new list
if(listRear){
listRear->next = node;
listRear = listRear->next;
}
else{
listHead = listRear = node;
}
}

return listHead;
}
};

Merge Sorted Array -- Leetcode

Question:

Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.

Note:
You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1and nums2 are m and n respectively.

Answer:

class Solution {

public:

void merge(int A[], int m, int B[], int n) {

int pos = m + n -1;

while( m>0 && n>0)

{

if( A[m-1] < B[n-1])

{

A[pos] = B[n-1];

pos--;

n--;

}

else

{

A[pos] = A[m-1];

pos--;

m--;

}

while( n >0)

{

A[pos] = B[n-1];

pos--;

n--;

}

};

Buffered Reader demo -- Java

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.InputStream;
import java.io.InputStreamReader;

public class BufferedReaderDemo {
   public static void main(String[] args) throws Exception {
      
      InputStream is = null; 
      InputStreamReader isr = null;
      BufferedReader br = null;

      try{
         // open input stream test.txt for reading purpose.
         is = new FileInputStream("c:/test.txt");
         
         // create new input stream reader
         isr = new InputStreamReader(is);
         
         // create new buffered reader
         br = new BufferedReader(isr);
      
         // creates buffer
         char[] cbuf = new char[is.available()];
         
         // reads characters to buffer, offset 2, len 10
         br.read(cbuf, 2, 10);
         
         // for each character in the buffer
         for (char c:cbuf)
         {
            // if char is empty
            if(c == (char)0)
            {
               c='*';
            }
            // prints characters
            System.out.print(c);
         }
                  
      }catch(Exception e){
         e.printStackTrace();
      }finally{
         
         // releases resources associated with the streams
         if(is!=null)
            is.close();
         if(isr!=null)
            isr.close();
         if(br!=null)
            br.close();
      }
   }
}

Assuming we have a text file c:/test.txt, which has the following content. This file will be used as an input for our example program:

ABCDEFGHIJKLMNOPQRSTUVWXYZ

Let us compile and run the above program, this will produce the following result:

**ABCDEFGHIJ**************

Thursday, July 23, 2015

permutations -- Leetcode

Question:

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].

Answer:

public class Solution {

public List<List<Integer>> permute(int[] nums) {

List<List<Integer>> res = new ArrayList<List<Integer>>();

ArrayList<Integer> subres = new ArrayList<Integer>();

ArrayList<Integer> num = new ArrayList<Integer>();

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

num.add(nums[i]);

}

permuteRec(num,res,subres);

return res;

}

public void permuteRec(ArrayList<Integer> nums, List<List<Integer>> res, List<Integer> subres){

int len = nums.size();

if(len ==0){

//clone a new copy, then add!!!

ArrayList<Integer> newcopy = new ArrayList<Integer>(subres);

res.add(newcopy);

return;

}

for(int i=0;i<len;++i){

int n=nums.get(i);

subres.add(n);

nums.remove(i);

permuteRec(nums,res,subres);

//backtrack!!!

nums.add(i,n); //note: specific pos:i!!!

subres.remove(subres.size()-1);

}

return;

}

valid Sudoku -- Leetcode

Question:

Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.

The Sudoku board could be partially filled, where empty cells are filled with the character '.'.

A partially filled sudoku which is valid.

Note:
A valid Sudoku board (partially filled) is not necessarily solvable. Only the filled cells need to be validated.

Answer:

class Solution {
public:
bool isValidSudoku(vector<vector<char>>& board) {
if(board.size() == 0) return false;
int row[9], col[9];

for(int i =0; i<9; i++){
memset(row, 0, 9*sizeof(int));
memset(col, 0, 9*sizeof(int));

for(int j =0; j<9; j++){
//check whole row.
if(board[i][j] != '.'){
if(row[board[i][j]-49] ==1){
return false;
}
row[board[i][j]-49]=1;
}
//check whole column, using board[j][i],tricky!
if(board[j][i] != '.'){
if(col[board[j][i]-49] ==1){
return false;
}
col[board[j][i]-49]=1;
}
}
}

//check whole cube.
for(int i=0;i<3;++i){
for(int j=0;j<3;++j){
memset(row,0,9*sizeof(int));

for(int m=i*3;m<(i*3+3);++m){
for(int n=j*3;n<(j*3+3);++n){
if(board[m][n]!='.'){
if(row[board[m][n]-49]==1){
return false;
}
row[board[m][n]-49]=1;
}
}
}
}
}
return true;
}
};

Sudoku solver -- Leetcode

Question:

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

A sudoku puzzle...

...and its solution numbers marked in red.

Answer:

public class Solution {
public void solveSudoku(char[][] board) {
int len = board.length;
if(len==0) return;
DFS(board);
}
public boolean DFS(char[][] board){
int len = board.length;
for(int i=0;i<len;++i){
for(int j=0;j<len;++j){
if(board[i][j] == '.'){
for(int k=1;k<=9;++k){
if(validStep(board,k,i,j)==true){
board[i][j] = (char)(k+'0');
if(DFS(board)==true){
return true;
}
}
}
board[i][j] = '.'; //backtrack!!!
return false;
}
}
}
return true;
}

public boolean validStep(char[][]board, int k, int i, int j){
for(int m=0;m<9;++m){
if(board[i][m]!='.' && m!=j && ((board[i][m]-'0') ==k)){
return false;
}
if(board[m][j]!='.' && m!=i && ((board[m][j]-'0') ==k)){
return false;
}
}
for(int n=i/3*3;n<(i/3*3+3);++n){
for(int q=j/3*3;q<(j/3*3+3);++q){
if(board[n][q]!='.' && (n!=i || q!=j) && ((board[n][q]-'0') ==k)){
return false;
}
}
}
return true;
}
}

Pissa design -- OOD

import java.util.ArrayList;

public class PissaApp {

enum PissaSize{

big,medium,small

}

abstract class Topping {

String name = null;

int price = 0;

private int num = 0;

public void setNum(int number){

this.num = number;

}

public int getNum(){

return this.num;

}

public int getPrice(){

return this.price;

}

class DoubleCheese extends Topping{

DoubleCheese(){

this.name = "DoubleCheese";

this.price = 2;

this.num = 1;

}

class Cheese extends Topping{

Cheese(){

this.name = name;

this.price = 1;

}

class Tomato extends Topping{

Tomato(){

this.name = name;

this.price = 1;

}

class Sausage extends Topping{

Sausage(){

this.name = name;

this.price = 2;

}

class Mushroom extends Topping{

Mushroom(String name, int price){

this.name = name;

this.price = 2;

}

class Pissa{

private String custorName;

private PissaSize pissaSize;

private int toppingNum;

private ArrayList<Topping> allToppings;

private int price;

public Pissa(String customer,PissaSize size){

this.custorName = customer;

this.pissaSize = size;

this.toppingNum = 0;

this.allToppings = new ArrayList<Topping>();

switch(size){

case PissaSize.small:

price = 5;

case PissaSize.medium:

price = 10;

case PissaSize.big:

price = 15;

defult:

break;

}

public int calculatePrice(){

for(Topping top: this.allToppings){

price += top.price * top.num;

}

return price;

}

public void addToppings(Topping topping, int num){

topping.setNum(num);

this.toppingNum++;

this.allToppings.add(topping);

}

Card Game -- OOD

import java.util.Random;

enum Suit { SPADES, CLUBS, HEARTS, DIAMONDS };

enum Face { ACE, TWO, THREE, FOUR, FIVE, SIX, SEVEN, EIGHT, NINE, TEN, JACK, QUEEN, KING };

class Card {

Suit suit;

Face face;

public Card(Suit suit, Face face){

this.suit = suit;

this.face = face;

}

public Suit getSuit(){

return suit;

}

public Face getFace(){

return face;

}

public class DeckCardGame {

private static final int suits_per_deck = Suit.values().length;

private static final int cards_per_suit = Face.values().length;

private Card [] cards = null;

public DeckCardGame() {

cards = new Card[suits_per_deck * cards_per_suit];

for (Suit s : Suit.values()) {

for (Face f : Face.values()) {

int index = s.ordinal() * cards_per_suit + f.ordinal();

cards[index] = new Card(s, f);

}

public void shuffle() {

int total = suits_per_deck * cards_per_suit;

int j = total;

int index;

Random rand = new Random();

while (j > 0) {

index = rand.nextInt(total);

try{

Card tmp = cards[index];

cards[index] = cards[j];

cards[j] = tmp;

}catch(Exception e){

}

j--;

}

public void printCards() {

for(Card c : cards) {

System.out.println("["+c.getSuit().toString() + " " + c.getFace().toString() + "], ");

}

System.out.println("");

}

public static void main(String [] args) {

DeckCardGame dcg = new DeckCardGame();

dcg.printCards();

dcg.shuffle();

dcg.printCards();

}

};

Wednesday, July 22, 2015

Minimum Size Subarray Sum -- Leetcode

Question:

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

Answer:
traverse the array one time, Optimal method, using O(n)!

public class Solution {
public int minSubArrayLen(int s, int[] nums) {
int start=0,end=0;
int n=nums.length;
if(n==0){
return 0;
}
int currsum=nums[0];
int minLen=n+1;
boolean flag = false;

while(start<=end && end<n){
//if not satisfy the constraint, keep end index ++ and adding shift elements until satisfy.
while(currsum < s){
if(end<n-1){
currsum += nums[++end];
}else{// end index arrived to n-1.
if(flag == true){ //have found one.
return minLen;
}else{
return 0;
}
}
}
//if satisfy the constraint, keep start index ++ and substracting shift elements until not satisfy again.
while(currsum >= s){
int len = end-start+1;

if(len < minLen){
minLen = len;
flag = true;
}
if(start<=end){
currsum -= nums[start++];
}
}
}
return minLen;
}
}

Happy number -- Leetcode

Question:

Write an algorithm to determine if a number is "happy".

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 19 is a happy number

12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

Answer:
Note using HashSet to avoid endless loop!
public class Solution {
public boolean isHappy(int n) {
HashSet<Integer> set = new HashSet<Integer>();

int res = Util(n);
while(res!=1){
if(set.contains(res)==false){
set.add(res);
}else{
break;
}
res = Util(res);
}
if(res == 1){
return true;
}
return false;
}

int Util(int n){
ArrayList<Integer> numbers = new ArrayList<Integer>();
int p= n/10;
int q= n%10;
numbers.add(q);
while(p>0){
q= p%10;
p= p/10;
numbers.add(q);
}
int res = computeRes(numbers);
return res;
}
int computeRes(ArrayList<Integer> numbers){
int res=0;
for(int i=0; i<numbers.size(); ++i){
res += numbers.get(i) * numbers.get(i);
}
return res;
}
}

Count Primes -- Leetcode

Question:
Count the number of prime numbers less than a non-negative number, n.
Answer:
Method 1. Judge using isPrime for every 4 -- (n-1), O(n2).
public class Solution {
public int countPrimes(int n) {
n--;
ArrayList<Integer> primes = new ArrayList<Integer>();
primes.add(2);
primes.add(3);

for(int i=5;i<=n;i=i+2){
Boolean isPrime = true;
for(Integer prime : primes){
int max = (int)Math.sqrt(n);
if(prime <= max){
if(n % prime == 0){
isPrime = false;
}
}
}
if(isPrime == true){
primes.add(i);
}
}
return primes.size();
}
}

Time Limit Exceeded : 1500000

Method 2. "Sieze of Eratosthenes" https://en.wikipedia.org/wiki/Sieve_of_Eratosthenes

public int countPrimes(int n) {

if (n <= 2)

return 0;

// init an array to track prime numbers

boolean[] primes = new boolean[n];

for (int i = 2; i < n; i++){

primes[i] = true;

}

for (int i = 2; i <= Math.sqrt(n - 1); i++) {

if (primes[i]) {

for (int j = i + i; j < n; j += i){

primes[j] = false;

}

int count = 0;

for (int i = 2; i < n; i++) {

if (primes[i])

count++;

}

return count;

}

longest palindromic string -- Leetcode

Question:

Write a function that finds the longest palindromic substring in a string.
ex: findLongstPal('affaptbbcracecarf') returns 'racecar'

Answer:

string findLongstHelp(string str, int& maxi, int& maxj){
int len = str.length();
bool flag[] = new int[len+1];
int max=0;

for (int i = 0;i<len+1;++i){
flag[i] = i;
}

for(int i=len;i>=0;--i){
for(int j=i;j>=0;--j){
if(isPalindrome(str, j, i)){
int diff = i-j+1;
if(diff >= i-flag[i]){
flag[i] = j;
}
}
}

if(i-flag[i] > max){
maxi = i;
maxj = flag[i];
}

}
return str.substring(maxj,maxi-maxj+1);

}

bool isPalindrome(string str, int m, int n){
while(m<n){
if(str[m] != str[n]) break;
m++;
n--;
}
if(m<n) return false;
return true;
}

Lowest Common Ancestor of a Binary Tree -- Leetcode

Question:

Given a binary tree, find the lowest common ancestor (LCA) of two given nodes in the tree.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

        _______3______
       /              \
    ___5__          ___1__
   /      \        /      \
   6      _2       0       8
         /  \
         7   4

For example, the lowest common ancestor (LCA) of nodes 5 and 1 is 3. Another example is LCA of nodes 5 and 4 is 5, since a node can be a descendant of itself according to the LCA definition.

Answer:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null){
return null;
}
if(root==p || root==q){
return root;
}
TreeNode left = lowestCommonAncestor(root.left, p, q);
TreeNode right = lowestCommonAncestor(root.right, p, q);
if(left!=null && right!=null){
return root;
}
return left!=null ? left : right;
}
}

Lowest Common Ancestor of a Binary Search Tree -- Leetcode

Question:

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

        _______6______
       /              \
    ___2__          ___8__
   /      \        /      \
   0      _4       7       9
         /  \
         3   5

For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

Answer:
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null){
return null;
}

if(p.val>q.val){
TreeNode tmp=q;
q=p;
p=tmp;
}
//p.val<=q.val
while(true){
if(root.val<p.val && root.val<q.val){
root=root.right;
}
else if(root.val>p.val && root.val>q.val){
root=root.left;
}
else{
break;
}
}
return root;
}
}

Tuesday, July 21, 2015

Reverse LinkedList -- Leetcode

Question:

Reverse a singly linked list.

Hint:

A linked list can be reversed either iteratively or recursively. Could you implement both?

Answer:
1. Iteratively: (C++)
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
ListNode *prev = NULL, *cur = head, *next = NULL;
while(cur){
next = cur->next;
cur->next = prev;
prev = cur;
cur = next;
}
return prev;
}
};

2. Recursively: (Java)
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
public class Solution {
public ListNode reverseList(ListNode head) {
return recursive(head);
}
ListNode recursive(ListNode head) {
if (head == null)
return null;

ListNode rest = head.next; //next node of head
if(rest == null){
return head; //where newHead returns in fact!
}

ListNode newHead = recursive(head.next);
head.next.next = head;
head.next = null;

return newHead;
}

}

Intersection of Two LinkedList -- Leetcode

Question:

Write a program to find the node at which the intersection of two singly linked lists begins.

For example, the following two linked lists:

A:          a1 → a2
                   ↘
                     c1 → c2 → c3
                   ↗            
B:     b1 → b2 → b3

begin to intersect at node c1.

Notes:

If the two linked lists have no intersection at all, return null.
The linked lists must retain their original structure after the function returns.
You may assume there are no cycles anywhere in the entire linked structure.
Your code should preferably run in O(n) time and use only O(1) memory.

Answer:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
if(!headA || !headB)return NULL;

ListNode *pA = headA, *pB = headB;
int num1=0, num2=0;
while(pA){
pA = pA->next;
num1++;
}
while(pB){
pB = pB->next;
num2++;
}

pA = headA;
pB = headB;
if(num1 >= num2){
int extra = num1-num2;
while(extra-- > 0){
pA = pA->next;
}
}else if(num1 < num2){
int extra = num2-num1;
while(extra-- > 0){
pB = pB->next;
}
}

while(pA && pB && pA!=pB){
pA = pA->next;
pB = pB->next;
}
if(pA && pB){
return pA;
}else{
return NULL;
}
}
};

Wednesday, July 15, 2015

Word Search II (Boggle Game) -- Leetcode

Question:

Given a 2D board and a list of words from the dictionary, find all words in the board.

Each word must be constructed from letters of sequentially adjacent cell, where "adjacent" cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once in a word.

For example,
Given words = ["oath","pea","eat","rain"] and board =

[
  ['o','a','a','n'],
  ['e','t','a','e'],
  ['i','h','k','r'],
  ['i','f','l','v']
]

Return ["eat","oath"].

Note:
You may assume that all inputs are consist of lowercase letters a-z.

click to show hint.

You would need to optimize your backtracking to pass the larger test. Could you stop backtracking earlier?

If the current candidate does not exist in all words' prefix, you could stop backtracking immediately. What kind of data structure could answer such query efficiently? Does a hash table work? Why or why not? How about a Trie? If you would like to learn how to implement a basic trie, please work on this problem: Implement Trie (Prefix Tree) first.

Answer:

public class Solution {

public List<String> findWords(char[][] board, String[] words) {

List<String> res = new ArrayList<String>();

//to avoid duplicate

Set<String> sset = new HashSet<String>();

String tmp = new String("");

int m = board.length;

int n = board[0].length;

Trie trie = new Trie();

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

trie.insert(words[i]);

}

boolean[][] visited = new boolean[m][n];

for(int i=0;i<m;++i){

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

visited[i][j] = false;

}

for(int i=0; i<m; ++i){

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

DFS(board, i, j, visited, tmp, trie, sset);

}

for(String s : sset){

res.add(s);

}

return res;

}

public void DFS(char[][] board, int i, int j, boolean[][] visited, String str, Trie trie, Set<String> sset){

str = str += board[i][j];

if(!trie.startsWith(str)){

str = str.substring(0,str.length()-1);

return;

}

if(trie.search(str)){

sset.add(str);

}

visited[i][j] = true;

int m = board.length;

int n = board[0].length;

if(j-1 >= 0 && !visited[i][j-1]){

DFS(board, i, j-1, visited, str, trie, sset);

}

if(j+1 < n && !visited[i][j+1]){

DFS(board, i, j+1, visited, str, trie, sset);

}

if(i-1 >= 0 && !visited[i-1][j]){

DFS(board, i-1, j, visited, str, trie, sset);

}

if(i+1 < m && !visited[i+1][j]){

DFS(board, i+1, j, visited, str, trie, sset);

}

//backtrack, important!

visited[i][j] = false;

str = str.substring(0,str.length()-1);

return;

}

//Trie tree

class TrieNode {

// Initialize your data structure here.

public char c;

// important!

public boolean isEnd;

public int count;

public ArrayList<TrieNode> children;

public TrieNode(char cha) {

this.c = cha;

isEnd = false;

count = 1;

children = new ArrayList<TrieNode>();

}

//return the node in the chilren == cha

public TrieNode rtnchildNode(char cha){

for(TrieNode child : this.children){

if(child.c == cha){

return child;

}

return null;

}

class Trie {

private TrieNode root;

public Trie() {

root = new TrieNode(' ');

}

// Inserts a word into the trie.

public void insert(String word) {

TrieNode cur = root;

TrieNode next = null;

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

next = cur.rtnchildNode(word.charAt(i));

if(next!=null){

next.count++;

cur=next;

}else{

TrieNode insertNewNode = new TrieNode(word.charAt(i));

cur.children.add(insertNewNode);

cur=insertNewNode;

}

if(i== word.length()-1){

cur.isEnd = true;

}

// Returns if the word is in the trie.

public boolean search(String word) {

TrieNode cur = root;

TrieNode next = null;

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

next = cur.rtnchildNode(word.charAt(i));

if(next != null){

cur = next;

}else{

return false;

}

//important!Judge the tail char whether 'isEnd'

if(i == word.length()-1){

if(cur.isEnd == true){

return true;

}

return false;

}

// Returns if there is any word in the trie

// that starts with the given prefix.

public boolean startsWith(String prefix) {

TrieNode cur = root;

TrieNode next = null;

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

next = cur.rtnchildNode(prefix.charAt(i));

if(next != null){

cur = next;

}else{

return false;

}

return true;

}