Tiger's leetcode solution

Friday, October 10, 2014

LC不能直接pass的题目，需要多写几遍的 !!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!

strstr()

Substring with of All Words

Permutations II ( 这个以前自己写了三种思路，刚刚竟然一种都没想起来，艹）

Wildcard Matching

N-Queens II

Largest Rectangle in Histogram

Permutation Sequence

Valid Number

sqrt()

Sunday, October 5, 2014

152. Maximum Product Subarray ~~~~~~~~~~~最终看了别人的代码

Given an integer array nums, find the contiguous subarray within an array (containing at least one number) which has the largest product.

Example 1:

Input: [2,3,-2,4]
Output: 6
Explanation: [2,3] has the largest product 6.

Example 2:

Input: [-2,0,-1]
Output: 0
Explanation: The result cannot be 2, because [-2,-1] is not a subarray.

A:
----------------------自己的代码-------略---------------
就是先用0 把所有的A[i]分开，然后，只算有正负的。这样，每次相乘的结果，绝对值都变大了。因此，可以直接maxPosProduct 和minNegProduct互相转换。
但其实，这样是没有必要的-----------------

------------------------参考了别人的geeksforgeeks的代码--------------------

public class Solution {
    public int maxProduct(int[] A) {
        assert(A!=null && A.length >0);
        if(A.length == 1)
            return A[0];
        int result = Integer.MIN_VALUE, maxEndHere = 1;// max positive product ending at the current position
        int minEndHere = 1;// min negative product ending at the current position
        for (int i = 0; i < A.length; i++) {
            if (A[i] > 0) {
                maxEndHere = maxEndHere * A[i];
                minEndHere = Math.min(minEndHere * A[i],1);
                result = Math.max(result,maxEndHere);
            } else if(A[i]==0) {
                maxEndHere = 1;
                minEndHere = 1;
                result = Math.max(result,0);// 0 can also be a product result
            }else{ // A[i]<0
                result = Math.max(minEndHere*A[i],result);
                int tmp = maxEndHere;
                maxEndHere = Math.max( minEndHere*A[i],1);
                minEndHere = tmp*A[i];
            }
        }
        return result;
    }
}

Mistakes:
1: 就是上面的这个思路了。每次用maxEndHere 等，每次初始值都设为1
2： when A[i]< 0 , we need calculate the result at the beginning, 因此，我们不能简单地把result = Math.max( ) 放到if 条件的外面。

3: 切记： A.length ==1的时候要单独列出来。

Learned: ----------

1: java中， given
int a =3;
int A = {1,2,3};
运行语句： A[a/2]是正确的
2：函数要求的返回值是double，我们可以return一个int类型。语法是正确的

3

Friday, August 22, 2014

几题排列组合看能不能把你绕晕

（来自买买提论坛。）

n个一样的球，放到m个一样的盒子里，有几种方法
n个一样的球，放到m个都不一样的盒子里，有几种方法
n个一样的球，放到m个除了颜色可能不一样其他都一样的盒子里，有几种方法
n个都不一样的球，放到m个一样的盒子里，有几种方法
n个都不一样的球，放到m个都不一样的盒子里，有几种方法
n个都不一样的球，放到m个除了颜色可能不一样其他都一样的盒子里，有几种方法
n个除了颜色可能不一样其他都一样的球，放到m个一样的盒子里，有几种方法
n个除了颜色可能不一样其他都一样的球，放到m个都不一样的盒子里，有几种方法
n个除了颜色可能不一样其他都一样的球，放到m个除了颜色可能不一样其他都一样的盒
子里，有几种方法

----------------------------------------Tiger's solution---------------------------请大家指正-------

n个一样的球，放到m个一样的盒子里，有几种方法

--------1------第一反应是DP方法。就是n分成最多m个子集，这样需要 m*n的时间和空间。
--------2------先把所有的求排成一串。把所有的盒子排成一串。然后每个球看放到哪个里面就是。就转换成了10块糖，每天至少吃一块儿的问题。但是，这里的糖是球。最多要吃m天

n个一样的球，放到m个都不一样的盒子里，有几种方法

-----------------------先把所有的求排成一串。只有1种方法。

n个一样的球，放到m个除了颜色可能不一样其他都一样的盒子里，有几种方法

n个都不一样的球，放到m个一样的盒子里，有几种方法

n个都不一样的球，放到m个都不一样的盒子里，有几种方法

n个都不一样的球，放到m个除了颜色可能不一样其他都一样的盒子里，有几种方法

n个除了颜色可能不一样其他都一样的球，放到m个一样的盒子里，有几种方法

n个除了颜色可能不一样其他都一样的球，放到m个都不一样的盒子里，有几种方法

n个除了颜色可能不一样其他都一样的球，放到m个除了颜色可能不一样其他都一样的盒子里，有几种方法

这里有个wiki的链接。貌似就是讲这样的问题。

Thursday, April 10, 2014

Construct a tree from Inorder and Level order traversals （待写）

原始链接：

Given inorder and level-order traversals of a Binary Tree, construct the Binary Tree. Following is an example to illustrate the problem.

Input: Two arrays that represent Inorder
       and level order traversals of a 
       Binary Tree
in[]    = {4, 8, 10, 12, 14, 20, 22};
level[] = {20, 8, 22, 4, 12, 10, 14};

Output: Construct the tree represented 
        by the two arrays.
        For the above two arrays, the 
        constructed tree is shown in 
        the diagram on right side

 思想就是每次在level order中，提取first node 作为当前的root。

然后，在in order中找到所有在其前面的值（作为左子树）。同时在level order的数组中抽取所有左子树的value。

same for the right subtree.

repeat above .

We strongly recommend to minimize the browser and try this yourself first.
The following post can be considered as a prerequisite for this.
Construct Tree from given Inorder and Preorder traversals
Let us consider the above example.
in[] = {4, 8, 10, 12, 14, 20, 22};
level[] = {20, 8, 22, 4, 12, 10, 14};
In a Levelorder sequence, the first element is the root of the tree. So we know ’20′ is root for given sequences. By searching ’20′ in Inorder sequence, we can find out all elements on left side of ‘20’ are in left subtree and elements on right are in right subtree. So we know below structure now.

             20
           /    \
          /      \ 
 {4,8,10,12,14}  {22}

Let us call {4,8,10,12,14} as left subarray in Inorder traversal and {22} as right subarray in Inorder traversal.
In level order traversal, keys of left and right subtrees are not consecutive. So we extract all nodes from level order traversal which are in left subarray of Inorder traversal. To construct the left subtree of root, we recur for the extracted elements from level order traversal and left subarray of inorder traversal. In the above example, we recur for following two arrays.

// Recur for following arrays to construct the left subtree
In[]    = {4, 8, 10, 12, 14}
level[] = {8, 4, 12, 10, 14}

Similarly, we recur for following two arrays and construct the right subtree.

// Recur for following arrays to construct the right subtree
In[]    = {22}
level[] = {22}

Following is C++ implementation of the above approach.

/* program to construct tree using inorder and levelorder traversals */

#include <iostream>

using namespace std;

/* A binary tree node */

struct Node

{

    int key;

    struct Node* left, *right;

};

/* Function to find index of value in arr[start...end] */

int search(int arr[], int strt, int end, int value)

{

    for (int i = strt; i <= end; i++)

        if (arr[i] == value)

            return i;

    return -1;

}

// n is size of level[], m is size of in[] and m < n. This

// function extracts keys from level[] which are present in

// in[].  The order of extracted keys must be maintained

int *extrackKeys(int in[], int level[], int m, int n)

{

    int *newlevel = new int[m], j = 0;

    for (int i = 0; i < n; i++)

        if (search(in, 0, m-1, level[i]) != -1)

            newlevel[j] = level[i], j++;

    return newlevel;

}

/* function that allocates a new node with the given key  */

Node* newNode(int key)

{

    Node *node = new Node;

    node->key = key;

    node->left = node->right = NULL;

    return (node);

}

/* Recursive function to construct binary tree of size n from

   Inorder traversal in[] and Level Order traversal level[].

   inSrt and inEnd are start and end indexes of array in[]

   Initial values of inStrt and inEnd should be 0 and n -1.

   The function doesn't do any error checking for cases

   where inorder and levelorder do not form a tree */

Node* buildTree(int in[], int level[], int inStrt, int inEnd, int n)

{

    // If start index is more than the end index

    if (inStrt > inEnd)

        return NULL;

    /* The first node in level order traversal is root */

    Node *root = newNode(level[0]);

    /* If this node has no children then return */

    if (inStrt == inEnd)

        return root;

    /* Else find the index of this node in Inorder traversal */

    int inIndex = search(in, inStrt, inEnd, root->key);

    // Extract left subtree keys from level order traversal

    int *llevel  = extrackKeys(in, level, inIndex, n);

    // Extract right subtree keys from level order traversal

    int *rlevel  = extrackKeys(in + inIndex + 1, level, n-inIndex-1, n);

    /* construct left and right subtress */

    root->left = buildTree(in, llevel, inStrt, inIndex-1, n);

    root->right = buildTree(in, rlevel, inIndex+1, inEnd, n);

    // Free memory to avoid memory leak

    delete [] llevel;

    delete [] rlevel;

    return root;

}

/* Uti;ity function to print inorder traversal of binary tree */

void printInorder(Node* node)

{

    if (node == NULL)

       return;

    printInorder(node->left);

    cout << node->key << " ";

    printInorder(node->right);

}

/* Driver program to test above functions */

int main()

{

    int in[]    = {4, 8, 10, 12, 14, 20, 22};

    int level[] = {20, 8, 22, 4, 12, 10, 14};

    int n = sizeof(in)/sizeof(in[0]);

    Node *root = buildTree(in, level, 0, n - 1, n);

    /* Let us test the built tree by printing Insorder traversal */

    cout << "Inorder traversal of the constructed tree is \n";

    printInorder(root);

    return 0;

}

Output:

Inorder traversal of the constructed tree is
4 8 10 12 14 20 22

An upper bound on time complexity of above method is O(n³). In the main recursive function, extractNodes() is called which takes O(n²) time.
The code can be optimized in many ways and there may be better solutions. Looking for improvements and other optimized approaches to solve this problem.

Suffix Array | Set 2 (nLogn Algorithm)

原始链接：

A suffix array is a sorted array of all suffixes of a given string. The definition is similar to Suffix Tree which is compressed trie of all suffixes of the given text.

Let the given string be "banana".

0 banana                          5 a
1 anana     Sort the Suffixes     3 ana
2 nana      ---------------->     1 anana  
3 ana        alphabetically       0 banana  
4 na                              4 na   
5 a                               2 nana

The suffix array for "banana" is {5, 3, 1, 0, 4, 2}

We have discussed Naive algorithm for construction of suffix array. The Naive algorithm is to consider all suffixes, sort them using a O(nLogn) sorting algorithm and while sorting, maintain original indexes. Time complexity of the Naive algorithm is O(n²Logn) where n is the number of characters in the input string.
In this post, a O(nLogn) algorithm for suffix array construction is discussed. Let us first discuss a O(n * Logn * Logn) algorithm for simplicity. The idea is to use the fact that strings that are to be sorted are suffixes of a single string.
We first sort all suffixes according to first character, then according to first 2 characters, then first 4 characters and so on while the number of characters to be considered is smaller than n. The important point is, if we have sorted suffixes according to first 2ⁱ characters, then we can sort suffixes according to first 2ⁱ⁺¹ characters in O(nLogn) time using a nLogn sorting algorithm like Merge Sort. This is possible as two suffixes can be compared in O(1) time (we need to compare only two values, see the below example and code).
The sort function is called O(Logn) times (Note that we increase number of characters to be considered in powers of 2). Therefore overall time complexity becomes O(nLognLogn). See http://www.stanford.edu/class/cs97si/suffix-array.pdf for more details.
Let us build suffix array the example string “banana” using above algorithm.
Sort according to first two characters Assign a rank to all suffixes using ASCII value of first character. A simple way to assign rank is to do “str[i] – ‘a’” for ith suffix of strp[]

Index     Suffix            Rank
 0        banana             1   
 1        anana              0 
 2        nana               13 
 3        ana                0
 4        na                 13
 5        a                  0

For every character, we also store rank of next adjacent character, i.e., the rank of character at str[i + 1] (This is needed to sort the suffixes according to first 2 characters). If a character is last character, we store next rank as -1

Index    Suffix            Rank          Next Rank 
 0       banana             1              0
 1       anana              0              13    
 2       nana               13             0
 3       ana                0              13
 4       na                 13             0 
 5       a                  0             -1

Sort all Suffixes according to rank and adjacent rank. Rank is considered as first digit or MSD, and adjacent rank is considered as second digit.

Index    Suffix            Rank          Next Rank 
 5        a                  0              -1
 1        anana              0               13    
 3        ana                0               13
 0        banana             1               0
 2        nana               13              0
 4        na                 13              0

Sort according to first four character
Assign new ranks to all suffixes. To assign new ranks, we consider the sorted suffixes one by one. Assign 0 as new rank to first suffix. For assigning ranks to remaining suffixes, we consider rank pair of suffix just before the current suffix. If previous rank pair of a suffix is same as previous rank of suffix just before it, then assign it same rank. Otherwise assign rank of previous suffix plus one.

Index       Suffix          Rank       
  5          a               0     [Assign 0 to first]        
  1          anana           1     (0, 13) is different from previous
  3          ana             1     (0, 13) is same as previous     
  0          banana          2     (1, 0) is different from previous      
  2          nana            3     (13, 0) is different from previous      
  4          na              3     (13, 0) is same as previous

For every suffix str[i], also store rank of next suffix at str[i + 2]. If there is no next suffix at i + 2, we store next rank as -1

Index       Suffix          Rank        Next Rank
  5          a               0             -1
  1          anana           1              1      
  3          ana             1              0 
  0          banana          2              3
  2          nana            3              3 
  4          na              3              -1

Sort all Suffixes according to rank and next rank.

Index       Suffix          Rank        Next Rank
  5          a               0             -1
  3          ana             1              0 
  1          anana           1              1      
  0          banana          2              3
  4          na              3             -1
  2          nana            3              3

We stop here as the next value is 8 which is greater than number of characters in “banana”.

// C++ program for building suffix array of a given text

#include <iostream>

#include <cstring>

#include <algorithm>

using namespace std;

// Structure to store information of a suffix

struct suffix

{

    int index; // To store original index

    int rank[2]; // To store ranks and next rank pair

};

// A comparison function used by sort() to compare two suffixes

// Compares two pairs, returns 1 if first pair is smaller

int cmp(struct suffix a, struct suffix b)

{

    return (a.rank[0] == b.rank[0])? (a.rank[1] < b.rank[1] ?1: 0):

               (a.rank[0] < b.rank[0] ?1: 0);

}

// This is the main function that takes a string 'txt' of size n as an

// argument, builds and return the suffix array for the given string

int *buildSuffixArray(char *txt, int n)

{

    // A structure to store suffixes and their indexes

    struct suffix suffixes[n];

    // Store suffixes and their indexes in an array of structures.

    // The structure is needed to sort the suffixes alphabatically

    // and maintain their old indexes while sorting

    for (int i = 0; i < n; i++)

    {

        suffixes[i].index = i;

        suffixes[i].rank[0] = txt[i] - 'a';

        suffixes[i].rank[1] = ((i+1) < n)? (txt[i + 1] - 'a'): -1;

    }

    // Sort the suffixes using the comparison function

    // defined above.

    sort(suffixes, suffixes+n, cmp);

    // At his point, all suffixes are sorted according to first

    // 2 characters.  Let us sort suffixes according to first 4

    // characters, then first 8 and so on

    int ind[n];  // This array is needed to get the index in suffixes[]

                 // from original index.  This mapping is needed to get

                 // next suffix.

    for (int k = 4; k < n; k = k*2)

    {

        // Assigning rank and index values to first suffix

        int rank = 0;

        suffixes[0].rank[0] = rank;

        ind[suffixes[0].index] = 0;

        int prev_rank = suffixes[0].rank[0];

        // Assigning rank to suffixes

        for (int i = 1; i < n; i++)

        {

            // If first rank and next ranks are same as that of previous

            // suffix in array, assign the same new rank to this suffix

            if (suffixes[i].rank[0] == prev_rank &&

                    suffixes[i].rank[1] == suffixes[i-1].rank[1])

            {

                prev_rank = suffixes[i].rank[0];

                suffixes[i].rank[0] = rank;

            }

            else // Otherwise increment rank and assign

            {

                prev_rank = suffixes[i].rank[0];

                suffixes[i].rank[0] = ++rank;

            }

            ind[suffixes[i].index] = i;

        }

        // Assign next rank to every suffix

        for (int i = 0; i < n; i++)

        {

            int nextindex = suffixes[i].index + k/2;

            suffixes[i].rank[1] = (nextindex < n)?

                                  suffixes[ind[nextindex]].rank[0]: -1;

        }

        // Sort the suffixes according to first k characters

        sort(suffixes, suffixes+n, cmp);

    }

    // Store indexes of all sorted suffixes in the suffix array

    int *suffixArr = new int[n];

    for (int i = 0; i < n; i++)

        suffixArr[i] = suffixes[i].index;

    // Return the suffix array

    return  suffixArr;

}

// A utility function to print an array of given size

void printArr(int arr[], int n)

{

    for (int i = 0; i < n; i++)

        cout << arr[i] << " ";

    cout << endl;

}

// Driver program to test above functions

int main()

{

    char txt[] = "banana";

    int n = strlen(txt);

    int *suffixArr = buildSuffixArray(txt,  n);

    cout << "Following is suffix array for " << txt << endl;

    printArr(suffixArr, n);

    return 0;

}

Output:

Following is suffix array for banana
5 3 1 0 4 2

Note that the above algorithm uses standard sort function and therefore time complexity is O(nLognLogn). We can use Radix Sort here to reduce the time complexity to O(nLogn).
Please note that suffx arrays can be constructed in O(n) time also. We will soon be discussing O(n) algorithms.
References:
http://www.stanford.edu/class/cs97si/suffix-array.pdf
http://www.cbcb.umd.edu/confcour/Fall2012/lec14b.pdf

Monday, April 7, 2014

Binary Tree Level-Order Traversal Using Depth First Search (DFS)

原始链接

Given a binary tree, print out the tree in level order (ie, from left to right, level by level). Output a newline after the end of each level. Breadth First Search (BFS) is not allowed.
     3
   /  \
  9   20    
     /  \
    15    7
For example, the level order output of the tree above is:
3 
9 20 
15 7

Hint:
Write a function call printLevel(BinaryTree *p, int level) which will print all nodes of a given level. Assume you know the height of the tree, then you can print the entire tree level by level utilizing printLevel.
Solution:
printLevel function can be solved using DFS. Decrement level by one as you advance to the next level. When level equals 1, you’ve reached the given level. To find the maximum height (or the max depth) of a tree, you can read my post: Maximum Height of a Binary Tree.

void printLevel(BinaryTree *p, int level) {
  if (!p) return;
  if (level == 1) {
    cout << p->data << " ";
  } else {
    printLevel(p->left, level-1);
    printLevel(p->right, level-1);
  }
}

void printLevelOrder(BinaryTree *root) {
  int height = maxHeight(root);
  for (int level = 1; level <= height; level++) {
    printLevel(root, level);
    cout << endl;
  }
}

void printLevel(BinaryTree *p, int level) {

if (!p) return;

if (level == 1) {

cout << p->data << " ";

} else {

printLevel(p->left, level-1);

printLevel(p->right, level-1);

}

void printLevelOrder(BinaryTree *root) {

int height = maxHeight(root);

for (int level = 1; level <= height; level++) {

printLevel(root, level);

cout << endl;

}

Further Thoughts:
If you look carefully, you will notice that the DFS solution traverses the same node multiple times. Since BFS traverses each node exactly one time, BFS is much more efficient than DFS.
Could you find the run time complexity for the DFS level-order traversal solution? Try to estimate as best as you can, and then find the correct answer by proving it using Math. Does your estimate fares well with the correct answer? Why?
Answer:
Although the DFS solution traverse the same node multiple times, it is not another order slower than the BFS solution. Here is the proof that the DFS solution above runs in O(N) time, where N is the number of nodes in the binary tree and we assume that the binary tree is balanced.
We first compute the complexity of printLevel for the kth level:

T(k) = 2T(k-1) + c
     = 2^k-1 T(1) + c
     = 2^k-1 + c

Assuming it’s a balanced binary tree, then it would have a total of lg N levels.
Therefore, the complexity of printing all levels is:

T(1) + T(2) + ... + T(lg N)
= 1 + 2 + 2² + ... + 2^{lg N-1} + c
= O(N)

Finding the maximum height of the tree also takes O(N) time, therefore the overall complexity is still O(N).

Tuesday, April 1, 2014

Sort 10GB dataset over 1GB memory

转自这里
This is a frequently encountered problem, the solution to which is based on the concept of External Sorting.
Here’s a summary of the process involved in doing this:

Of course, given that you only have 1 GB of main memory, that’s what you can read at once at any given time. So, read data in chunks of 1 GB at a time and sort using on of the conventional sorting algorithms, most likely Quicksort.
Write each sorted dataset to disk (of course, assuming that you have enough disk space :)).
You will end up having 10 chunks of 1 GB (10GB/1GB = 10 chunks), individually sorted, datasets which now needs to be merged into one single output file (on disk).
Now read the first 100 MB (= 1 GB /10 chunks) of each sorted chunk into an input buffer in main memory and allocate the remaining to an output buffer.
Perform a 10-way merge and store the results in the output buffer. If, at any given time, the output buffer is full, write it to the final sorted file, and empty it. If any of the 10 input buffers gets empty, fill it with the next 100 MB of its associated 1 GB sorted chunk until no more data from the chunk is available. This is the key step that makes external merge sort work externally — because the merge algorithm only makes one pass sequentially through each of the chunks, each chunk does not have to be loaded completely; rather, sequential parts of the chunk can be loaded as needed.

<Inspired from Wikipedia>