[LeetCode] Decode Ways

A message containing letters from A-Z is being encoded to numbers using the following mapping:

'A' -> 1
'B' -> 2
...
'Z' -> 26

Given an encoded message containing digits, determine the total number of ways to decode it.
For example,
Given encoded message "12", it could be decoded as "AB" (1 2) or "L" (12).
The number of ways decoding "12" is 2.


解题思路：
            1. 与climbstairs非常相似，只是这里多加了一些限制条件
            f(n) = f(n-2) 当n为0时。
            f(n) = f(n-1) 当大于26
 容易出错点： 当遇到0的时候，需要判断。

 public int numDecodings(String s) {
        int n = s.length();

        if (n == 0 || s.charAt(0) == '0') {
            return 0;
        }

        int num0 = 1, num1 = 1, num = 1;

        for (int i = 1; i < n; i++) {
                if(s.charAt(i) != '0'){
                    num = num1;
                }else{
                    num = 0;
                }
                
                if(s.charAt(i-1) != '0' && Integer.valueOf(s.substring(i-1, i+1)) <= 26){
                    num += num0;
                }
                
                if(num == 0) return 0;
            
                num0 = num1;
                num1 = num;
            
        }

        return num;
    }

[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] Combination Sum2

Given a collection of candidate numbers (C) and a target number (T), find all unique combinations in C where the candidate numbers sums to T.
Each number in C may only be used once in the combination.
Note:

• All numbers (including target) will be positive integers.
• Elements in a combination (a₁, a₂, … , a_k) must be in non-descending order. (ie, a₁ ≤ a₂ ≤ … ≤ a_k).
• The solution set must not contain duplicate combinations.

For example, given candidate set 10,1,2,7,6,1,5 and target 8,
A solution set is:
[1, 7]
[1, 2, 5]
[2, 6]
[1, 1, 6]

解题思路：
      1. 与combination sum基本一致，区别为每次都要移动到下一个不相同的数。

 public List> combinationSum2(int[] candidates, int target) {
        Arrays.sort(candidates);
        List> res = new ArrayList>();
        List solution = new ArrayList();
        
        combination2(candidates, 0, target, res, solution);
        
        return res;
    }
    
    public void combination2(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]);
                combination2(candidates, i+1, target - candidates[i], res, solution);
                solution.remove(solution.size() - 1);
                
                while(i < candidates.length - 1 && candidates[i] == candidates[i+1]) i++; //move to next diff candidate
            }else break;
        }
    }

小城悠悠 - 美丽的安娜波利斯

在给父母的美国之旅划上一个圆满的句号，我们选择了安娜波利斯作为旅途的最后一站。安娜波利斯是马里兰的首府，地处东海岸，面向大海。作为一个港口城市，少不了海鲜，码头，还有游艇。

它给人最大印象是小而美丽。像花丛笼罩之下的一个隔离小岛。安娜波利斯最繁华的地段当属main street.　这条街不长，从city hall一直延续到港口，大约也只有100-200米左右。上面都是一些特色小店和各国特色的餐馆。作为市中心，没有林立的高楼大厦，没有现代化的购物中心。全部都是家庭作坊式的店铺。这也让人倍感亲切。第二有特色的当属立在各个餐厅前面的小黑板式的菜单和招牌。他们有的是可爱的航海插图，有的是俏皮的动漫眼睛。漫步于此，哪怕只是在外面观看这些艺术式的广告牌都让人里暖暖。而除了这条中心街以外，其它都是民用的住宅区了。从这点可以看出，这个城市真的是一个休闲的地方，没有霓虹灯的渲染，没有人来人往的吵闹喧嚣，来此的人们都学会了沉浸，让自己慢慢融化在这个小而安静的城市里。

安娜波利斯在历史上有着很重要的地位，是美国最早的临时政府，也是最早的殖民地之一。它里面的很多建筑已经有了好几百年的历史。这里也有一所很出名的大学，就是安娜波利斯海军学校，这个学校也属于美国最难念的前十之一。它是开放给大众的，游客可以通过安检后参观学校，还可以看到学生的训练。

我们花了３-４个小时用脚完成了主要城市部分的参观，并且还吃了美味的海鲜。回来以后的这么长时间，我也在不断的回味那个悠悠小城。让人可惜的是我的相机记忆卡在回去的路上丢了。。只能用手机里仅有的相片来纪念一下我们的安娜波利斯之旅。


                                 

　　　　　　　　　　　　　　　　　　海军学校

 

[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