[LeetCode] Container with most water

Given n non-negative integers a₁, a₂, ..., a_n, where each represents a point at coordinate (i, a_i). n vertical lines are drawn such that the two endpoints of line i is at (i, a_i) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
Note: You may not slant the container. 

解题思路：
                设2个指针，一个从开头，一个从尾部扫，用最小的高来算出当前的area大小，如果前面的指针的height，比较小，则往后移动到下一个比它大的位置。否则将尾部指针向前移到下一个比当前height大的位置
                     

public int maxArea(int[] height) {
        int start = 0, end = height.length-1;
        int maxArea = 0;
        int h = 0;
        
        while(start < end){
            h = Math.min(height[start], height[end]);
            int area = (end - start) * h;
            
            maxArea = Math.max(maxArea, area);
            
            if(height[start] == h){
              while(start < end && height[start] <= h) start++;
            }else{
              while(start < end && height[end] <= h) end--;
            }
        }
        
        return maxArea;
    }

[LeetCode] Generate Parenthese

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:
"((()))", "(()())", "(())()", "()(())", "()()()"

解题思路：
 i 位置为（ 或者 ) 取决于 目前左括号的数目和右括号的数目.
leftN < n 时，此位置可以为左括号
rightN < leftN && rightN < n时，此位置可以为右括号.


 

 public List generateParenthesis(int n) {
           List res = new ArrayList();
           
           getAllSolution(0,0,n,"",res);
           
           return res;
    }
    
    public void getAllSolution(int leftN, int rightN, int n,String s, List solution){
           if(leftN == n && rightN == n){
               solution.add(s);
               return;
           }
           
           if(leftN < n){
               getAllSolution(leftN+1, rightN, n, s + "(", solution);
           }
           
           if(rightN < n && rightN < leftN){
               getAllSolution(leftN, rightN + 1, n, s + ")", solution);
           }
    }

[LeetCode] CountAndSay

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. 

注意最后的一个count不能忘记

Java code:

 public String countAndSay(int n) {
        String s = "1";
        int i = 1;
        
        while(i < n){
            int j = 0;
            char a = s.charAt(0);
            int count = 0;
            String nexts = "";
            
            while(j < s.length()){
                if(s.charAt(j) == a){
                    count++;
                    j++;
                }else{
                   nexts += count + String.valueOf(a);
                   a = s.charAt(j);
                   count = 0;
                }
            }
            
            nexts += count + String.valueOf(a);//the last part
            
            s = nexts;
            i++;
        }
        
        
        return s;
    }

[LeetCode] Divide two integers

Divide two integers without using multiplication, division and mod operator.

解题思路：
   1. 类似二分法：每次左移divisor 一位。
   2.  用log（a-b）＝loga/logb
注意：overflow, underflow, 并且要考虑符号问题
 

public int divide(int dividend, int divisor) {
         if(dividend == 0 || divisor == 1) return dividend;
        
        int sign = 1;
        
        if(dividend < 0) sign *= -1;
        if(divisor < 0) sign *= -1;
        
        long dvd = Math.abs((long)dividend); //the overflow and underflow
        long dvs = Math.abs((long)divisor);
        int result = 0;
        int i = 0;
        
        while(dvd >= dvs){
            dvs <<=1;
            i++;
        }
       
        while(dvd < dvs && i > 0){
              i--;
              dvs >>= 1;
              
              if( dvd >= dvs ){
                  result += 1 << i;
                  dvd -= dvs;
              }
              
        }
                
        return sign*result;
        
    } 

以下为log的方法，由于在java里，double并不是准确的值，有一定的误差。所以最后的结果要有一个误差的调整。 

 public int divide(int dividend, int divisor) {
        if(dividend == 0 || divisor == 1) return dividend;
        
        int sign = 1;
        
        if(dividend < 0) sign *= -1;
        if(divisor < 0) sign *= -1;
        
         if(dividend==Integer.MAX_VALUE&&divisor==Integer.MIN_VALUE) return 0;
         else if(dividend==Integer.MIN_VALUE&&divisor==Integer.MAX_VALUE) return sign < 0? -1:1;
    
        dividend = Math.abs(dividend);
        divisor = Math.abs(divisor);
        
        double t = Math.log10(dividend) - Math.log10(divisor);
        double ret = Math.pow(10, t);
        int result = (int) Math.floor(ret+ 0.0000001);
        
        return sign*result;
    }

[LeetCode]Climbing stairs

You are climbing a stair case. It takes n steps to reach to the top.
Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top? 

Thoughts:
            1. 典型的 Fibonacci sequence
               F(n) = F(n -1) + F(n-2) n > 1;
               F(0) = F(1) = 1;

 
public int climbStairs(int n){
        if(n<2) return 1;
        
        return climbStairs(n-2) + climbStairs(n-1);
    }

非recursion

 
 public int climbStairs(int n) {
        if(n < 0) return 0;
        int f0 = 1, f1 = 1;
        int f2 = f0;
        
        for(int i = 2; i <= n; i++){
            f2 = f0+f1;
            f0 = f1;
            f1 = f2;
        }
        
        return f2;
    }

另外整理了别人用的code。觉得这里的int[] 用的比较巧妙

  public static int climbstairs(int n)
     {
      int[] s = {0,1,2};
    
      int number = 2;
      while (number++

[LeetCode] Gray Code

The gray code is a binary numeral system where two successive values differ in only one bit.

Given a non-negative integer n representing the total number of bits in the code, print the sequence of gray code. A gray code sequence must begin with 0.

For example, given n = 2, return [0,1,3,2]. Its gray code sequence is:

00 - 0 
01 - 1 
11 - 3
10 - 2

解题思路：
F（n） = F(n-1) + (F(n-1) in reverse order) + 1<<(n-1)

n个数的greycode等于 n-1的greycode再加上把greycode反序各自在第1位加个1

 public List grayCode(int n) {
          List res = new ArrayList();
         res.add(0);
         
         for(int i = 1; i <= n; i++){
             int j = res.size();
             int k = 1<<(i-1);
             
             while(j > 0){
                 res.add(res.get(j-1) + k);
                 j--;
             }
         }
         
       return res;
    }

［Leetcode］ Implement strStr

Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

Thoughts:
1. The most straight thought is to iterate through the haystack.
2. 另外一个为kmp算法，讲解可以参考 topcoder

Java Code:

public String strStr(String haystack, String needle) {
         if(needle.length() == 0) return haystack;
         
         int n = 0;
         
         for(int i = 0; i <= haystack.length() - needle.length(); i++){
             n = 0;
             
             while(n < needle.length() && haystack.charAt(i+n) == needle.charAt(n))
                  n++;
                  
             if(n == needle.length()) return haystack.substring(i);
         }
         
         return null;
    }

how to import one large data into mysql database

when we import data from file into database, there is usually restriction for the file size. For example, if we want to import file into mysql, which is larger than 128 M. Then we cann't import file by UI, we need import it through command line.

For windows, you need to type the flowing command line：
mysql -h localhost -r root password databasename<infile.sql;

XAMPP -- website development tool

The reason to choose XAMPP:
There are a lot of website development environments and tools. But why do we choose xampp? At first, it is open source. It's composed of PHP, Apache and Mysql, which are most used by small-middle company. All of them are free, open source. All of them are packed into one package. You just need to install XAMPP, then you can use it to build you own website and design your database. It's one ideal choice for new learner.


How to use it.
1, Download it and then install it by default.
2, Go to "localhost/xampp", you can see the xampp settings, then click the "phpMyAdmin", then you can see your mysql. You can create or delete your database here.
3, Then, you can see one "xampp control panel icon" on you desktop, then click it.
4, You can run "apache", 'mysql' .
5, Then write your first php program, then save it under folder "xampp/htdocs"
6, Input your website address to view the result: localhost/xampp/helloword.php

Tips:
1, The Apache uses the same port with skype, make sure you close the skype before running apache.
2, When you click the run "apache", or "mysql", don't too rush, it needs a little time to run them.

Good luck and enjoy your journey with developing website!

money denomination java program

Give you certain denomination and each kind of denomination have one fixed count. Then, you need to write one java program to output all of possible combinations to sum one target amount. For example: You have 100 Pennies, 20 Nickels, 10 Dimes and 4 Quarters to get $1. Then, how many ways do you have, and out put all of the possibilities.

The following is the java code:


/*
 * To change this template, choose Tools | Templates
 * and open the template in the editor.
 */
package currency;

public class currency1 {
  
    public static int[] baseCurrency = {25,10,5,1};
    
    public static void main(String[] args)
   {
     combCount(100);   
    }

    public static void combCount(int total)
    {
        int count = 0;
       
        System.out.println( "Quarter  Dime  Nickel  Penny");
       
        for(int i = 0; i <= (total/baseCurrency[0]); i++)
        {
          for (int j = 0; j <= (total - i*baseCurrency[0])/baseCurrency[1]; j++  )        
          {
              int left = total - i*baseCurrency[0] - j*baseCurrency[1];
              for(int k = 0; k <= left /baseCurrency[2]; k++ )
              {
               int m = ( left - k*baseCurrency[2] )/baseCurrency[3];
              
               System.out.println( "     "+ i + "      "+ j +"      " + k + "     " + m);
               count++;
              }
           }
       
        }
        System.out.println("Count:" + count);
   
    }   
}


The Output:

Quarter  Dime  Nickel  Penny
     0         0          0        100
     ...       ...         ...         ...

Count: ..