[LeetCode] Candy

There are N children standing in a line. Each child is assigned a rating value.
You are giving candies to these children subjected to the following requirements:

• Each child must have at least one candy.
• Children with a higher rating get more candies than their neighbors.

What is the minimum candies you must give?

解题思路：
        1. 对于ratings[i], ratings[i]的数目的大小，取决于ratings[i-1], ratings[i+1]和ratings[i]的大小对比。我们可以简化为，ratings[i-1] vs ratings[i] 或者ratings[i+1] vs ratings[i].
        从左到右扫描数组，candies[i] = candies[i-1] + 1 if ratisngs[i] > ratings[i-1]
          然后第二遍，从右到左，candies[i-1] = candies[i] + 1 if ratings[i-1] > ratisngs[i]
          第二遍，要注意在ratings[i-1] > ratings[i] and candies[i-1] > candies[i], 就不需要更改了candies了。

 
public int candy(int[] ratings) {
        int n = ratings.length;
        if(n == 0) return 0;
        
       int[] candies = new int[n];
       int total = 0;
       candies[0] = 1;
       
       
       for(int i = 1; i < ratings.length; i++){
           if(ratings[i] > ratings[i-1]){
               candies[i] = candies[i-1] + 1;
           }else{
               candies[i] = 1;
           }
       }
       
       total = candies[n - 1];
       
       for(int i = ratings.length - 1; i > 0 ; i--){
           if(ratings[i] < ratings[i-1] && candies[i] >= candies[i-1]){
               candies[i-1] = candies[i] + 1;
           }
               total += candies[i-1];
       }
       
       return total;
           
    }

[Leetcode]: Valid Number

Validate if a given string is numeric.

Some examples: "0" => true " 0.1 " => true "abc" => false "1 a" => false "2e10" => true
Note: It is intended for the problem statement to be ambiguous. You should gather all requirements up front before implementing one. 解题思路：
1. 整型 － [+-]?\\d+
2. 浮点数 - 小数点至少一旁为整型
3. 含e的表达式 － e的左边为浮点数，右边为整型

  
public class Solution {
    public boolean isNumber(String s) {
        String number_re = "\\s*[+-]?(\\d+\\.?\\d*|\\d*\\.\\d+)(e[+-]?\\d+)?\\s*";
        return s.matches(number_re);
    }
}

这题的关键就是要考虑到各个coners。

JAVA : Calculate Money With BigDecimal or Int, Long

When we calculate 1.00 - 0.90, the answer is not 0.1 but 0.09999999999999998.

The float and double types are primarily designed for scientific calculations.  If we want to get exact answer, we can use int, long or BigDecimal.

Like:
BigDecimal a = new BigDecimal("1.00");
BigDecimal b = new BigDecimal("0.90");

BigDecimal c = a.subtract(b);

It's less convenient than using a primitive arithmetic type. An alternative choice is to use int or long.


Reference:
<Effective Java> Chapert 7 

How to create JAX-RPC webservice Client with Netbeans

The JAX-RPC is  the old encoded style for webservice, netbeans doesn’t support this style anymore. The default webservice style is JAX-WS.  We need to install extra plugin if we want to call the RPC style webservice.

For the normal java application, we can find the solution here:

http://www.stormacq.com/netbeans-7-0-and-jax-rpc-web-service/

After the above steps, we can get two folders : ‘Generated Sources’ and ‘Web Service References’. Go to the class where you are going to call the method from the webservice, then right click, you can insert code. That is it.

For maven project, there are several ways to call RPC webservice: axis, ant and CFX.

I used axis to call the service for my project.

You can read related solution here: http://blog.dawouds.com/2008/10/maven-2-axis-wsdl-code-gen.html

http://www.ryandelaplante.com/2009/03/jax-rpc-client-with-maven2.html

Step 1:

Download the wsdl files, and put this file in the folder “src/main.resources/META-INF/wsdl”.

You can get this file by creating the webservice client in the normal java application project, then copy this folder to the maven project.

Step 2:

Define the pom file. Here is my POM file: 

<groupId>com.medallion</groupId>

    <artifactId>ClientWS_Maven</artifactId>

    <version>1.0-SNAPSHOT</version>

    <packaging>jar</packaging>

    <name>ClientWS_Maven</name>

    <url>http://maven.apache.org</url>

    <properties>

       <project.build.sourceEncoding>UTF-8</project.build.sourceEncoding>

       <targetJdk>1.6</targetJdk>

    </properties>

   

    <dependencies>

       

    <dependency>

   <groupId>javax.activation</groupId>

   <artifactId>activation</artifactId>

   <version>1.1</version>

       

    </dependency>

       <dependency>

    <groupId>javax.mail</groupId>

    <artifactId>mail</artifactId>

    <version>1.4.3</version>

    </dependency>

   

       <dependency>

           <groupId>junit</groupId>

           <artifactId>junit</artifactId>

           <version>3.8.1</version>

           <scope>test</scope>

       </dependency>

       

       <dependency>

           <groupId>org.apache.axis</groupId>

           <artifactId>axis</artifactId>

           <version>1.4</version>

           <scope>compile</scope>

       </dependency>

       <dependency>

           <groupId>org.apache.axis</groupId>

           <artifactId>axis-jaxrpc</artifactId>

           <version>1.4</version>

           <scope>compile</scope>

       </dependency>

       <dependency>

           <groupId>commons-discovery</groupId>

           <artifactId>commons-discovery</artifactId>

           <version>0.4</version>

           <scope>compile</scope>

       </dependency>

       <dependency>

           <groupId>wsdl4j</groupId>

           <artifactId>wsdl4j</artifactId>

           <version>1.6.2</version>

           <scope>compile</scope>

       </dependency>

    </dependencies>

    <build>

       <sourceDirectory>src/main/java</sourceDirectory>

       <resources>

           <resource>

               <directory>src/main/resources</directory>

           </resource>

           <resource>

               <directory>src/main/autogen</directory>

           </resource>

       </resources>

         

       <plugins>      

           <plugin>

               <groupId>org.apache.maven.plugins</groupId>

               <artifactId>maven-compiler-plugin</artifactId>

               <version>2.3.2</version>

               <configuration>            

                   <source>1.6</source>

                   <target>1.6</target>

               </configuration>

           </plugin>

           <plugin>

               <groupId>org.codehaus.mojo</groupId>

               <artifactId>axistools-maven-plugin</artifactId>

               <version>1.4</version>

               <executions>

                   <execution>

                       <id>ax-ws-autogen</id>

                       <phase>generate-sources</phase>

                       <goals>

                           <goal>wsdl2java</goal>

                       </goals>

                   </execution>

               </executions>

               <configuration>

                   <useEmitter>true</useEmitter>

                   <packageSpace>com.medallion.clientws_maven</packageSpace>

                   <sourceDirectory>src/main/resources/META-INF/wsdl</sourceDirectory>

                   <wsdlFiles>

                       <wsdlFile>cminterface.asmx.wsdl</wsdlFile>                           

                   </wsdlFiles>

                   <outputDirectory>src/main/autogen</outputDirectory>

               </configuration>

           </plugin>

          

       </plugins>

    </build>   

</project>

step3:

Right click on the project node, test it.

Step4:

Go to the folder src/main/autogen/, you can find the generated code.

Step5:

We can call the webservice now.　We used wsdl2java to generate java file locally, then we can call it directly just like calling the local class.

public class App

{

    public static void main( String[] args ) throws ServiceException, RemoteException

    {

       

        com.medallion.clientws_maven.CMInterface cmInterface = new com.medallion.clientws_maven.CMInterfaceLocator();

        com.medallion.clientws_maven.CMInterfaceSoap_PortType stub = cmInterface.getCMInterfaceSoap();

        

        stub.login("User", "password");

        

    }

}

We can also call the webservice directly.. Please refer this log:

http://af8991.iteye.com/blog/1702741

Convert the relative path into absolute url

When we download the image in the website with java, the src in the img is relative, how could we download the image based on this relative?

We can try to convert the relative path into absolute url, then we save the img like writing one file.

 URL pageUrl = new URL(pageurl);
 URL imgurl1 = new URL(pageUrl, relativepath);

[LeetCode] Longest palindromic substring

Given a string S, find the longest palindromic substring in S. You may assume that the maximum length of S is 1000, and there exists one unique longest palindromic substring.

Another Linear time solution, please see This link

Java Code:
   
    

public String longestPalindrome(String s) {
         String palindrom = "";
        int maxLen = 0;
        
        int index1 = 0, index2 = 0;
        int i = 0;
        while(i < 2*s.length()){
            index1 = i/2;
            index2 = i/2 + i%2;
            
            while(index1 >= 0 && index2 < s.length() && s.charAt(index2) == s.charAt(index1)){     
                index1--;
                index2++;
            }
            
            if(index2 > index1 && maxLen < (index2 - index1 - 1)) {
                palindrom = s.substring(index1+1, index2);
                maxLen = index2 - index1 - 1; 
            }
            
            i++;
        }
        
        return palindrom;
    }

[Leetcode] Longest common prefix

Write a function to find the longest common prefix string amongst an array of strings. 

解题思路：
1. 遍历数组，找出当前commonprefix下一个str的commonprefix。
2. 查看数组里所有的变量的第i位置上的字符相等否

   public String longestCommonPrefix(String[] strs) {
        String prefix = "";
        
        if(strs.length == 0) return prefix;
        
        prefix = strs[0];
        
        for(int i = 1; i < strs.length && prefix.length() > 0; i++){
            
            int j = 0;
            
            while(j < prefix.length() && j < strs[i].length() && prefix.charAt(j) == strs[i].charAt(j)) j++;
            
            prefix = prefix.substring(0, j);
        }
        
        return prefix;
    }

public String longestCommonPrefix(String[] strs) {
         String res = "";
        if(strs.length == 0) return res;
        res = strs[0];
        
        for(int i = 0; i < res.length(); i++){         
            for(int j = 1; j < strs.length; j++){
                if(i >= strs[j].length() || strs[j].charAt(i) != res.charAt(i)){
                    return res.substring(0, i);
                }
            }
        }
        
        return res;
    }

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

解题思路： insertion sort 的演变

Java Code:

public List insert(List intervals, Interval newInterval) {
           List res = new ArrayList(intervals);
        
        int s = 0;
        
        // at index s, the start is correct. we need to merge the end.
        while(s < intervals.size() && newInterval.start >= intervals.get(s).start){
            s++;
        }
        
        if(s > 0 && newInterval.start <= intervals.get(s-1).end){
            s--;
        }else{
            res.add(s, newInterval);
        }
        
        res.get(s).end = Math.max(newInterval.end, res.get(s).end);
        s++;
              
       while( s < res.size() && newInterval.end >= res.get(s).start){
           newInterval.end = Math.max(newInterval.end, res.get(s).end);
           res.remove(s);
       }
        
        return res;
    }

[LeetCode] Combination Sum

Given a set of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T. 

解题思路：recursion

Java Code:

public List<List<Integer>> combinationSum(int[] candidates, int target) {
        Arrays.sort(candidates);
        List> res = new ArrayList>();
        List solution = new ArrayList();
        
        combination(candidates, 0, target, res, solution);
        
        return res;
    }
    
    public void combination(int[] candidates, int startIndex, int target, List> res, List solution){
        if(target == 0){
            List tmp = new ArrayList(solution);
            res.add(tmp);
            return;
        }
        
        for(int i = startIndex; i < candidates.length; i++){
            if(candidates[i] <= target){
                solution.add(candidates[i]);
                combination(candidates, i, target - candidates[i], res, solution);
                solution.remove(solution.size() - 1);
            }else break;
        }
    }

[LeetCode] Construct binary tree from Inorder and Preorder

Given preorder and inorder traversal of a tree, construct the binary tree.

Java Code:

 

public TreeNode buildTree(int[] preorder, int[] inorder) {
         if(inorder.length != preorder.length || preorder.length == 0) return null; 
           
          return buildSubTree(inorder, 0, inorder.length-1, preorder, 0, inorder.length-1);
        
    }
    
     public TreeNode buildSubTree(int[] inorder, int begin, int end, int[] preorder, int s, int t) {
        
           TreeNode root = new TreeNode(preorder[s]);
           int pos = begin;
           
           for(int i = begin; i <= end; i++){
               if(inorder[i] == preorder[s]){
                   pos = i;
                   break;
               }
           }
              
           if(begin <= pos - 1) root.left = buildSubTree(inorder, begin, pos-1, preorder, s+1, s+pos-begin);
           
           if(pos+1 <= end) root.right = buildSubTree(inorder, pos+1, end, preorder, s + pos-begin+1, t);
           
           return root;
    }

[LeetCode]Construct binary tree from inorder and postorder traversal

Given inorder and postorder traversal of a tree, construct the binary tree.

解题思路：
1. 从postorder里找到root node, 然后在inorder里找到此root node, 分别recursion

Java Code:

 public TreeNode buildTree(int[] inorder, int[] postorder) {
        if(inorder.length != postorder.length || postorder.length == 0) return null; 
           
          return buildSubTree(inorder, 0, inorder.length-1, postorder, 0, inorder.length-1);
        
    }
     
      public TreeNode buildSubTree(int[] inorder, int begin, int end, int[] postorder, int s, int t) {
        
           TreeNode root = new TreeNode(postorder[t]);
           int pos = begin;
           
           for(int i = begin; i <= end; i++){
               if(inorder[i] == postorder[t]){
                   pos = i;
                   break;
               }
           }
              
           if(begin <= pos - 1) root.left = buildSubTree1(inorder, begin, pos-1, postorder, s, s+pos-begin-1);
           
           if(pos+1 <= end) root.right = buildSubTree1(inorder, pos+1, end, postorder, s + pos-begin, t-1);
           
           return root;
    }

［LeetCode］Combinations

Given two integers n and k, return all possible combinations of k numbers out of 1 ... n.

For example,

If n = 4 and k = 2, a solution is:

[ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]


解题思路：
                1. 求n个数中的k个数的组合，如果此组合含有n,则就是求n-1的k-1个组合，不含有n，就是n-1的k。即 combine(n, k) = combine(n-1, k -1) + combine(n-1, k);
                2. 要注意的就是n-1,k-1可能返回nil, 那么这时就要初始化n。
       

public List> combine(int n, int k) {
         List> res = new ArrayList>();
         
         if( n < k || k == 0) return res;
         
         res = combine(n-1, k-1);
         
         for(int i = 0; i < res.size(); i++){
             List tmp = res.get(i);
             tmp.add(n);
         }
         
         if(res.size() == 0){
             List tmp = new ArrayList();
             tmp.add(n);
             res.add(tmp);
         }
         
         res.addAll(combine(n-1, k));
         
         return res;
    }

[LeetCode] Binary Tree PostOrder

Given a binary tree, return the postorder traversal of its nodes' values.
For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [3,2,1].
Note: Recursive solution is trivial, could you do it iteratively?

解题思路：
1. recursion 最直接的做法
2. non-recursion, 借助stack.
   2.1 find the leftmost node, for every step, push node.right, node into stack
  2.2  pop up one node if current node is null, if the popped one node has its right node at the top of the stack, then pop up its right child node, push itself into the stack. repeat the 2.1

和inorder类似，区别为在push node, node.right的顺序不一样。要确保node的right child 不会重复visit,就先push node.right, 再存入node. 这样每次就可以对比当前的node的right child是不是为stack top。

Java Code:

recursion solution:

 public List postorderTraversal(TreeNode root) {
         List res = new ArrayList();
        
         postorderT(res, root);
         return res;
    }
     public void postorderT(List res, TreeNode root) {
            if(root == null) return;
            if(root.left != null) postorderT(res, root.left);
            if(root.right != null) postorderT(res, root.right);
            res.add(root.val);
    }

non-recursion solution:

public List postorderTraversal(TreeNode root) {
         List res = new ArrayList();
         Stack tmp = new Stack();
         TreeNode p = root;
         
         while(!tmp.isEmpty() || p != null ){
             while(p != null){
                 if(p.right != null) tmp.add(p.right);
                  tmp.add(p);
                
                 p = p.left;
             }
             
            p = tmp.pop();
            
            if(p.right != null && !tmp.isEmpty() &&p.right == tmp.peek()){
               TreeNode tmp0 = tmp.pop();
               tmp.add(p);
               p = p.right;
            }else{
                res.add(p.val);
                p = null;
            }
         }
         
         return res;
    }

[LeetCode] Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [−2,1,−3,4,−1,2,1,−5,4],
the contiguous subarray [4,−1,2,1] has the largest sum = 6.

 解体思路：
       1. 数组A[0..j]的最大和来自于子数组A[0..j-1]或者来自于A[i..j]
       2. 对于A[i..j]的最大数，是 A[i..j-1]+A[j] or A[j]
       3. 使用divide-conquer 解法：A[0..n]的最大值来自于3个地方：左边子数组A[0..j]， 右边子数组 A[j+1..n]的最大值，或者跨越这两个数组之间的最大值，也就是一定包含A[j],A[j+1]的最大值。
     
     

public int maxSubArray(int[] A) {
        if(A.length == 0) return 0;
        int maxSum = A[0];
        int sum = A[0];
        
        for(int i = 1; i < A.length; i++){
           sum = A[i] > sum + A[i] ? A[i] : sum + A[i];
           maxSum = Math.max(maxSum, sum);
        }
     
        return maxSum;
    }

divide-conquer的解法

public int maxSubArray(int[] A) {
        if (A.length == 0) return 0;
        
        return maxSubarray(A, 0, A.length - 1);
    }

    public int maxSubarray(int[] A, int start, int end) {
        int mid = (start + end) / 2;
        int leftMax = Integer.MIN_VALUE;
        int rightMax = Integer.MIN_VALUE;
        int crossMax = Integer.MIN_VALUE;
        int maxSum = 0;
        
        if(start == end) return A[start];
        
        if (mid >= start) {
            leftMax = maxSubarray(A, start, mid);
        }

        if (mid < end) {
            rightMax = maxSubarray(A, mid + 1, end);
        }


        if (mid >= start && mid < end) {
            int sum = A[mid];
            crossMax = A[mid];
            
            for (int j = mid - 1; j >= start; j--) {
                sum += A[j];
                crossMax = Math.max(sum, crossMax);
            }

            crossMax+= A[mid+1];
            sum = crossMax;
            
            for (int i = mid + 2; i <= end; i++) {
                sum += A[i];
                crossMax = Math.max(sum, crossMax);
            }
        }
        
        maxSum = Math.max(leftMax,rightMax);
        maxSum = Math.max(maxSum, crossMax);
        
        return maxSum;
    }

[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++