leetcode-整数拆分

给定一个正整数 n，将其拆分为至少两个正整数的和，并使这些整数的乘积最大化。 返回你可以获得的最大乘积。

例如，给定 n = 2，返回1（2 = 1 + 1）；给定 n = 10，返回36（10 = 3 + 3 + 4）。

注意：你可以假设 n 不小于2且不大于58。

思路

1
假设a[i]表示i对应最大乘积，已知a[0]~a[i],那么a[i+1]=（1+i；2+(i-1)...x+(i-x+1)..的最大的值）那么x+(i-x+1)的最大值如何求呢：取x*(i-x+1);a[x]*(i-x+1);x*a[i-x+1];a[x]*a[i-x+1]中的最大值；

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
class Solution {
    public int integerBreak(int n) {
      /*
      2:1+1   1
      3:1+2   2
      4:2+2   4
      5:2+3   6
      6:3+3   9
      7:3+4 . 12
      8:2+3+3 18
      9:3+6(3+3) 27
      10:3+7(3+4) 36
      11:1+10:2+9:3+8:4+7:5+6
       */ 
        if(n ==2){
            return 1;
        }
        if(n==3){
            return 2;
        }
        int [] arr = new int[n+1];
        arr[0]=0;
        arr[1]=1;
        arr[2]=1;
        arr[3]=2;
        for(int i =4;i<n+1;i++){
            int temp =0;
            for(int j =1;j<=i/2;j++){
                int temp1 = (i-j)*j;
                int temp2 = arr[i-j]*j;
                int temp3 = (i-j)*arr[j];
                int temp4 = arr[i-j]*arr[j];
                if(temp1>temp){
                    temp =temp1;
                }
                if(temp2>temp){
                    temp =temp2;
                }
                if(temp3>temp){
                    temp=temp3;
                }
                if(temp4>temp){
                    temp=temp4;
                }
            }
            arr[i]=temp;
        }
        return arr[n];
    }
}

Android-查找讯飞输入法的下载资源的路径01

查找讯飞输入法的下载资源的路径(间接证据)：

  1. 点击下载之后可以看到sd卡下“./iFlyIME/speech”文件夹下多了如下两个so,删除离线包之后so消失。

    • libAitalk5_v5_rnn.so

    • libAitalk5_res_cnsms_v5_rnn.so

  1. 调试smali文件可以看到：点击开启离线功能时，会先调用SpeechHelper的getAitalkChildType方法，在该方法中回去调用isV5RnnExist方法，之后会调用到getV5RnnSo跟getV5RnnRes方法，而这两个方法分别是获取这两个so的。（调试过程中截 取的数据中有这两个路径）。
SpeechHelper
  1. getAitalkChildType
1
2
3
4
5
6
7
8
public static int getAitalkChildType(Context paramContext)
  {
   	。。。
    if (isV5RnnExist()) {///////////////////////////////******1*******////////////////////
      return 0;
    }
    。。。
  }
  1. isV5RnnExist 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
private static boolean isV5RnnExist()
 {
   boolean bool2 = false;
   removeFilesToHiddenDir();
   File[] arrayOfFile1 = getV5RnnSo();//////////*******2******////////////////
   File[] arrayOfFile2 = getV5RnnRes();/////////*******3******////////////////
   boolean bool1 = bool2;
   if (arrayOfFile1 != null)
   {
     bool1 = bool2;
     if (arrayOfFile1.length > 0)
     {
       bool1 = bool2;
       if (arrayOfFile2 != null)
       {
         bool1 = bool2;
         if (arrayOfFile2.length > 0)
         {
           int i;
           String str;
           int j;
           if (arrayOfFile1.length > arrayOfFile2.length)
           {
             i = 0;
             if (i < arrayOfFile2.length)
             {
               str = arrayOfFile2[i].getName().substring(DIR_AITALK5_5_RNN_RES_PREFIX.length());
               j = 0;
               for (;;)
               {
                 if (j < arrayOfFile1.length)
                 {
                   if (arrayOfFile1[i].getName().endsWith(str)) {
                     mRnnVer = str;
                   }
                 }
                 else
                 {
                   i += 1;
                   break;
                 }
                 j += 1;
               }
             }
           }
           else
           {
             i = 0;
             if (i < arrayOfFile1.length)
             {
               str = arrayOfFile1[i].getName().substring(DIR_AITALK5_5_RNN_SO_PREFIX.length());
               j = 0;
               for (;;)
               {
                 if (j < arrayOfFile1.length)
                 {
                   if (arrayOfFile2[i].getName().endsWith(str)) {
                     mRnnVer = str;
                   }
                 }
                 else
                 {
                   i += 1;
                   break;
                 }
                 j += 1;
               }
             }
           }
           if (Logging.isDebugLogging()) {
             Logging.d(TAG, "rnn ver: " + mRnnVer);
           }
           bool1 = bool2;
           if (!TextUtils.isEmpty(mRnnVer)) {
             bool1 = true;
           }
         }
       }
     }
   }
   return bool1;
 }
  1. getV5RnnSo
1
2
3
4
5
6
7
8
9
10
//DIR_AITALK5_5_RNN_SO_PREFIX = "libAitalk5_v5_rnn"
private static File[] getV5RnnSo()
  {
    removeFilesToHiddenDir();
    File localFile = new File(DIR_AITALK5_5_RNN_ROOT);
    if ((localFile.exists()) && (localFile.isDirectory())) {
      return localFile.listFiles(new ccf(Pattern.compile(DIR_AITALK5_5_RNN_SO_PREFIX + "(_v)?[0-9]*.so")));
    }
    return null;
  }
  1. getV5RnnRes
1
2
3
4
5
6
7
8
9
10
//DIR_AITALK5_5_RNN_RES_PREFIX = "libAitalk5_res_cnsms_v5_rnn"
private static File[] getV5RnnRes()
  {
    removeFilesToHiddenDir();
    File localFile = new File(DIR_AITALK5_5_RNN_ROOT);
    if ((localFile.exists()) && (localFile.isDirectory())) {
      return localFile.listFiles(new ccg(Pattern.compile(DIR_AITALK5_5_RNN_RES_PREFIX + "(_v)?[0-9]*.so")));
    }
    return null;
  }
  1. 调试过程截取的常量
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
CPU_ARM_V6 = "(v6"
CURRENT_DIR_SPEECH = "/storage/emulated/0/.iFlyIME/speech/"
DIR_AITALK5_2_RES = "/storage/emulated/0/.iFlyIME/speech/libAitalk5_res_cnsms_v2.so"
DIR_AITALK5_2_RES_HIDDEN = "/storage/emulated/0/.iFlyIME/speech/libAitalk5_res_cnsms_v2.so"
DIR_AITALK5_2_SO = "/storage/emulated/0/.iFlyIME/speech/libAitalk5_v2.so"
DIR_AITALK5_2_SO_HIDDEN = "/storage/emulated/0/.iFlyIME/speech/libAitalk5_v2.so"
DIR_AITALK5_3_RES = "/storage/emulated/0/.iFlyIME/speech/libAitalk5_res_cnsms_v3.so"
DIR_AITALK5_3_RES_HIDDEN = "/storage/emulated/0/.iFlyIME/speech/libAitalk5_res_cnsms_v3.so"
DIR_AITALK5_3_SO = "/storage/emulated/0/.iFlyIME/speech/libAitalk5_v3.so"
DIR_AITALK5_3_SO_HIDDEN = "/storage/emulated/0/.iFlyIME/speech/libAitalk5_v3.so"
DIR_AITALK5_4_RES = "/storage/emulated/0/.iFlyIME/speech/libAitalk5_res_cnsms_v4.so"
DIR_AITALK5_4_RES_HIDDEN = "/storage/emulated/0/.iFlyIME/speech/libAitalk5_res_cnsms_v4.so"
DIR_AITALK5_4_SO = "/storage/emulated/0/.iFlyIME/speech/libAitalk5_v4.so"
DIR_AITALK5_4_SO_HIDDEN = "/storage/emulated/0/.iFlyIME/speech/libAitalk5_v4.so"
DIR_AITALK5_5_RNN_PATTERN = "(_v)?[0-9]*.so"
DIR_AITALK5_5_RNN_RES = "/storage/emulated/0/.iFlyIME/speech/libAitalk5_res_cnsms_v5_rnn.so"
DIR_AITALK5_5_RNN_RES_HIDDEN = "/storage/emulated/0/.iFlyIME/speech/libAitalk5_res_cnsms_v5_rnn.so"
DIR_AITALK5_5_RNN_RES_PREFIX = "libAitalk5_res_cnsms_v5_rnn"
DIR_AITALK5_5_RNN_ROOT = "/storage/emulated/0/.iFlyIME/speech/"
DIR_AITALK5_5_RNN_ROOT_HIDDEN = "/storage/emulated/0/.iFlyIME/speech/"
DIR_AITALK5_5_RNN_SO = "/storage/emulated/0/.iFlyIME/speech/libAitalk5_v5_rnn.so"
DIR_AITALK5_5_RNN_SO_HIDDEN = "/storage/emulated/0/.iFlyIME/speech/libAitalk5_v5_rnn.so"
DIR_AITALK5_5_RNN_SO_PREFIX = "libAitalk5_v5_rnn"
DIR_AITALK6_RES = "/storage/emulated/0/.iFlyIME/speech/libAitalk6_res_cnsms.so"
DIR_AITALK6_RES_HIDDEN = "/storage/emulated/0/.iFlyIME/speech/libAitalk6_res_cnsms.so"
DIR_AITALK6_SO = "/storage/emulated/0/.iFlyIME/speech/libAitalk6.so"
DIR_AITALK6_SO_HIDDEN = "/storage/emulated/0/.iFlyIME/speech/libAitalk6.so"
DIR_AITALK_RES = "/storage/emulated/0/.iFlyIME/speech/libAitalk5_res_cnsms.so"
DIR_AITALK_RES_HIDDEN = "/storage/emulated/0/.iFlyIME/speech/libAitalk5_res_cnsms.so"
DIR_AITALK_SO = "/storage/emulated/0/.iFlyIME/speech/libAitalk5.so"
DIR_AITALK_SO_HIDDEN = "/storage/emulated/0/.iFlyIME/speech/libAitalk5.so"
DIR_LIBS_AITALK5_2_SO = "/libs/libAitalk5_v2.so"
DIR_LIBS_AITALK5_3_SO = "/libs/libAitalk5_v3.so"
DIR_LIBS_AITALK5_4_SO = "/libs/libAitalk5_v4.so"
DIR_LIBS_AITALK5_5_RNN_ROOT = "/libs/"
DIR_LIBS_AITALK5_5_RNN_SO = "/libs/libAitalk5_v5_rnn.so"
DIR_LIBS_AITALK6_SO = "/libs/libAitalk6.so"
DIR_LIBS_AITALK_SO = "/libs/libAitalk5.so"
DIR_SPEECH = "/storage/emulated/0/iFlyIME/speech/"
DIR_SPEECH_HIDDEN = "/storage/emulated/0/.iFlyIME/speech/"
FILE_PATH = "FILE_PATH"
MAX_SYNC_CALL_WAIT_TIME = 20000
MIN_RAM_REQUIRE = 50
RAM_REQUIRE_1G = 1000
RAM_REQUIRE_2G = 1700
TAG = "SpeechHelper"
URL_PATH = "URL_PATH"
VER_AITALK_5 = 1003
VER_AITALK_5_2 = 1015
VER_AITALK_5_3 = 1022
VER_AITALK_6 = 1100
mRnnVer = ".so"
  1. 。。。。

leetcode-Bit位计数

给定一个非负整数 num。 对于范围 0 ≤ i ≤ num 中的每个数字 i ，计算其二进制数中的1的数目并将它们作为数组返回。

示例：
比如给定 num = 5 ，应该返回 [0,1,1,2,1,2].

进阶：

  • 给出时间复杂度为O(n * sizeof(integer)) 的解答非常容易。 但是你可以在线性时间O(n)内用一次遍历做到吗？
  • 要求算法的空间复杂度为O(n)。
  • 你能进一步完善解法吗？ 在c ++或任何其他语言中不使用任何内置函数（如c++里的 __builtin_popcount）来执行此操作。

思路

1
2
3
4
5
6
考虑5 （111） 除以2就相当于把后面的1砍掉剩下11（2）余 1 
 这样a[5]=a[2]+1;

考虑4 100除以2 就相当于把0砍掉=2 余 0 
  这样a[4]=a[2];
...

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int[] countBits(int num) {        
        int [] arr= new int[num+1];
        if(num==0){
            arr[0]=0;
            return arr;
        }
        if(num==1){
            arr[0]=0;
            arr[1]=1;
            return arr;
        }
        arr[0]=0;
        arr[1]=1;
        for(int i =2;i<=num;i++){
            int temp1=i/2;
            int temp2=i%2;
            if(temp2==1){
                arr[i]=1+arr[temp1];
            }else {
                arr[i]=arr[temp1];
            }
        }
        return arr;
    }
}

Android-反编译调试smali文件

工具

  1. apktool

  2. smalidea插件（需要安装到as）

步骤

  1. 使用apktool反编译apk，修改manifest（在application下添加android:debuggable=true）

  2. 使用apktool回编生成新的apk

  3. 给新的apk签名

  4. 安装新的apk

  5. 将smali文件导入as中，将smali文件夹设置为source root

  6. 在as中创建remote调试（注意设置填写端口号为8800：将as的remote调试跟本机的8800端口“打通”）run->edit xxx

  7. 设置project的jdk

  8. 在as终端输入

    1
    adb shell am start -D -n com.xxx.xxx/com.xxx.xxx.xxx

    以调试模式开启安装的apk

  9. 1
    2
    adb shell ps | grep com.xxx.xxx     
    //查看手机中该apk程序的pid
  10. 1
    2
    3
    adb forward tcp:8800 jdwp:查找到的pid
    //将本机的8800端口跟该apk进程“打通”
    //记得设置remote调试的时候将本机的8800端口跟as的remote调试“打通”了，那么remote调试就跟手机的apk进程“打通”了；
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12

    10. 在smali文件中打好断点

    11. as-》run-〉debug





    参考https://www.cnblogs.com/gordon0918/p/5570811.html

    http://www.cnblogs.com/goodhacker/p/5592313.html

leetcode-单词拆分

给定一个非空字符串 s 和一个包含非空单词列表的字典 wordDict，判定 s 是否可以被空格拆分为一个或多个在字典中出现的单词。

说明：

  • 拆分时可以重复使用字典中的单词。
  • 你可以假设字典中没有重复的单词。

示例 1：

1
2
3
输入: s = "leetcode", wordDict = ["leet", "code"]
输出: true
解释: 返回 true 因为 "leetcode" 可以被拆分成 "leet code"。

示例 2：

1
2
3
4
输入: s = "applepenapple", wordDict = ["apple", "pen"]
输出: true
解释: 返回 true 因为 "applepenapple" 可以被拆分成 "apple pen apple"。
     注意你可以重复使用字典中的单词。

示例 3：

1
2
输入: s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
输出: false

思路

1
2
3
这道题仍然是动态规划的题目，我们总结一下动态规划题目的基本思路。首先我们要决定要存储什么历史信息以及用什么数据结构来存储信息。然后是最重要的递推式，就是如从存储的历史信息中得到当前步的结果。最后我们需要考虑的就是起始条件的值。

首先我们要存储的历史信息res[i]是表示到字符串s的第i个元素为止能不能用字典中的词来表示，我们需要一个长度为n的布尔数组来存储信息。然后假设我们现在拥有res[0,...,i-1]的结果，我们来获得res[i]的表达式。思路是对于每个以i为结尾的子串，看看他是不是在字典里面以及他之前的元素对应的res[j]是不是true，如果都成立，那么res[i]为true;

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean [] arr=new boolean[s.length()];
        String temp =s.substring(0,1);
        for(int i =0 ;i<wordDict.size();i++){
            if(temp.equals(wordDict.get(i))){
                arr[0]=true;
                break;
            }
        }
        for(int i =1;i<arr.length;i++){
            temp=s.substring(0,i+1);
            for(int j =0;j<wordDict.size();j++){
                String str=wordDict.get(j);
                if(temp.endsWith(str)){
                    if(str.length()==(i+1)){
                        arr[i]=true;
                        break;
                    }else if(str.length()<(i+1)){
                        int k =i-str.length();
                        if(arr[k]==true){                       
                            arr[i]=true;
                            break;
                        }else {
                            continue;
                        }
                    }
                }else{
                    
                    continue;
                }
            }
        }
        return arr[s.length()-1];
    }
}

leetcode-三角形最小路径

给定一个三角形，找出自顶向下的最小路径和。每一步只能移动到下一行中相邻的结点上。

例如，给定三角形：

1
2
3
4
5
6
[
     [2],
    [3,4],
   [6,5,7],
  [4,1,8,3]
]

自顶向下的最小路径和为 11（即，2 + 3 + 5 + 1 = 11）。

说明：

如果你可以只使用 O(n) 的额外空间（n 为三角形的总行数）来解决这个问题，那么你的算法会很加分。

思路

1
如上图中的三角形，考虑到4的最小路径为到6的最小路径+4；到1的最小路径为min(到6的最小路径，到5的最小路径)+1；。。。。。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public int minimumTotal(List<List<Integer>> t) {
        int[] preArr=new int[t.size()];
        for(int i =0;i<t.size();i++){
            if(i==0){
                preArr[i]=t.get(0).get(0);
            }else{
                preArr[i]=Integer.MAX_VALUE;
            }
        }
        for(int i=1;i<t.size();i++){
            List<Integer>arr = t.get(i);
            int temp =preArr[0];
            for(int j =0;j<arr.size();j++){
                if(j==0){
                    preArr[j]=preArr[j]+arr.get(j);
                }else{
                    int temp1=preArr[j];
                    preArr[j]=arr.get(j)+(temp>temp1?temp1:temp);
                    temp=temp1;
                }
            }
        }
        int re=preArr[0];
        for(int i =1;i<preArr.length;i++){
            re=(re>preArr[i]?preArr[i]:re);
        }
        return re;
        
    }
}

leetcode-股票最大收益

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。

注意你不能在买入股票前卖出股票。

示例 1:

1
2
3
4
输入: [7,1,5,3,6,4]
输出: 5
解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。

示例 2:

1
2
3
输入: [7,6,4,3,1]
输出: 0
解释: 在这种情况下, 没有交易完成, 所以最大利润为 0。

思路

1
2
3
4
假设一共有n天，那么最好的情况一定是在（第一天卖出，第二天卖出。。。第n天卖出）这n中case中的最大值。（废话哈。。。）

循环数组： 记录i天之前的最小price：minPrice
		 记录i天之前的最大收益：maxPro

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int maxProfit(int[] prices) {
        if(prices.length<=1){
            return 0;
        }
        //minPrice
        //maxPro
        int maxPro=0;
        int minPrice = prices[0];
        for(int i =1;i<prices.length;i++){
            minPrice =(minPrice>prices[i]?prices[i]:minPrice);
            maxPro=(maxPro>(prices[i]-minPrice)?maxPro:(prices[i]-minPrice));
        }
        return maxPro;    
    }
}

MSC-Android开发文档

MscSdk引擎

####在线

  • 需要网络；

  • 速度慢（通过会话模式（边录边传）跟音频压缩的优化，在讯飞输入法的实际速度并不比离线的慢）；

####离线：

  • 不需要网络；
  • 识别速度快；
  • 需要付费；
  • 需要下载离线包；

语音识别相关

####语音听写

  • 语音转文本；
  • 可以提取语音中的文字信息，可以识别个性化数据；
  • 不需要构建语法；
  • 可以通过上传词典的方式提高匹配率；
  • 离线的只支持普通话转文本，且暂未开放购买；
  • 在线的可以支持多种语言；

####语法识别

  • 语音转文本；

  • 识别的匹配率高（因为上传了语法规则）；

  • 识别结果有置信度，可以根据这个值判断该识别结果是否有效；

  • 使用场景多是需要准确结果并且结果有限的语音控制（比如语音控制空调）；

  • 需要构建语法；

  • 在线语法识别已经下线，新用户无法使用；

####构建语法

  • abnf（在线语法规则）：需要指定引擎类型为在线引擎；需要指定语法格式为abnf;构建成功之后会在回调里返回一个id，在识别时会用到；
  • bnf（离线语法规则）:需要指定引擎为本地引擎；需要指定语法格式为bnf；需要指定本地语法构建结果文件的路径；需要下载对应的离线sdk；

####更新词典

实质是个性化热词上传。

有以下两种方式指定词典：

  • 在线听写词典：考虑这种情况：发音是‘zhangsan’,习惯上出现概率最高的应该是”张三”，但实际我们想要的是”张散”（假如有个手机联系人是张散），此时我们可以通过上传个性化热词的方式告诉语音云服务器优先匹配”张散”。
  • 离线语法词典：用于更新已经构建的语法文件中某个规则的内容。

####识别对话框

这个是讯飞提供的语音输入ui。

  • 在显示对话框后，录音自动开始；
  • 点击对话框内任意地方，可结束录音，点击对话框外，则取消会话；
  • 出现错误后，再点击对话框内，可启动下一次会话。

####翻译

将语音翻译成目标语种文本，涉及到如下参数：

  • SpeechConstant.ASR_SCH 启用翻译
  • SpeechConstant.ADD_CAP 翻译通道
  • SpeechConstant.ORI_LANG 原始语种
  • SpeechConstant.TRANS_LANG 目标语种
  • SpeechConstant.TRS_SRC 结果格式

语音合成相关

文字转为语言：可以设置转换结果的语言，方言，发音人的特征语速等；

###语义理解相关

  • 将语言内容转换为一定结构的文本数据，之后抓取重点信息，理解用户意图，进行下一步处里。
  • 分为两种：文本语义跟语音语义（先转为文本之后再进行文本语义理解）；
  • 仅有在线模式；
  • 默认不开通，需要再aiui开放平台开通；
  • aiui:主要用于人机交互

目前支持的离线在线服务：

  • 离线服务（离线命令词、离线合成、唤醒），体验期均为35天，装机量3台，体验期结束后，点击控制台-》我的应用-》立即购买按钮
  • 在线服务（听写、合成）：免费500次/天-》免费提额通过后2w次/天-》超过2w/天-》联系商务msp_business@iflytek.com
  • 在线服务（人脸、声纹）：免费500次/天-》超过500次/天-》联系商务msp_business@iflytek.com

ps:具体接入及使用代码示例参见https://doc.xfyun.cn/msc_android

参考文档：https://doc.xfyun.cn/msc_android

leetcode-不同的二叉搜索树

给定一个整数 n，求以 1 … n 为节点组成的二叉搜索树有多少种？

示例:

1
2
3
4
5
6
7
8
9
10
输入: 3
输出: 5
解释:
给定 n = 3, 一共有 5 种不同结构的二叉搜索树:

   1         3     3      2      1
    \       /     /      / \      \
     3     2     1      1   3      2
    /     /       \                 \
   2     1         2                 3

思路:

1
2
3
4
5
6
7
8
9
10
11
12
f(n)=
    1:f(0)*f(n-1)       1为根结点
    2:f(1)*f(n-2)		 2为根结点
    3:f(2)*f(n-3)		 3为根结点
    4:f(3)*f(n-4)		 4为根结点
    ...		
    n:f(n-1)*f(0)		 n为根结点

          
    f(0)=1;f(1)=1;f(2)=2;   //初始条件
               
    f(3)=f(0)*f(2)+f(1)*f(1)+f(2)*f(0)=2+1+2=5;

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int numTrees(int n) {
           
        if(n==0){
            return 0;
        }
        if(n==1){
            return 1;
        }
        if(n==2){
            return 2;
        }
        int [] arr= new int[n+1];
        arr[0]=1;
        arr[1]=1;
        arr[2]=2;
        for(int i =3;i<=n;i++){
            int temp = 0;
            while(temp <=i-1){
                arr[i]+=arr[temp]*arr[i-temp-1];
                temp++;
            }
        }    
        return arr[n];
    }
}

leetcode-解码方法

一条包含字母 A-Z 的消息通过以下方式进行了编码：

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

给定一个只包含数字的非空字符串，请计算解码方法的总数。

示例 1:

1
2
3
输入: "12"
输出: 2
解释: 它可以解码为 "AB"（1 2）或者 "L"（12）。

示例 2:

1
2
3
输入: "226"
输出: 3
解释: 它可以解码为 "BZ" (2 26), "VF" (22 6), 或者 "BBF" (2 2 6) 。

思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
考虑String字符串新加入一个char时的case；
两个维度：1:新加入的char是否为0；2:新加入的跟前一个字符表示的数字是否合法（1-26）
if(2){
	a[n]+=a[n-2];
	if(!1){
		a[n]+=a[n-1];
	}
}else{
	if(!1){
		a[n]+=a[n-1];
    }else{
    	return 0;//无法解码    
    }	
}
该题是爬楼梯问题的升级版，实质是相通的，都属于"斐波纳切"型，由前往后推。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
class Solution {
    public int numDecodings(String s) {
        //1:数字要大于等于1，小于等于26
        //2:新加入的数字是否为0
        if(s==null||"".equals(s)||"0".equals(s)||s.charAt(0)=='0'){
            return 0;
        }
        char[] ch=s.toCharArray();
        int[] in= new int[ch.length];
        in[0]=1;
        if(ch.length>=2){
            //计算dp初始值
            int empty=(ch[0]-'0')*10+(ch[1]-'0');
            if(empty>9&&empty<27){
                if(ch[1]=='0'){
                    in[1]=1;
                }else{
                    in[1]=2;
                }
            }else{
                if(ch[1]=='0'){
                    return 0;
                }else{
                    in[1]=1;
                }
            }
            //dp计算出最终值
            for(int i =2;i<in.length;i++){
                int temp = (ch[i-1]-'0')*10+(ch[i]-'0');
                if(temp>9&&temp<27){
                    in[i]+=in[i-2];
                    if(ch[i]!='0'){
                        in[i]+=in[i-1];
                    }
                }else{
                    if(ch[i]!='0'){
                        in[i]+=in[i-1];
                    }else{
                        return 0;//无法解码       
                    }
                }
            }
        }
        return in[in.length-1];
    }
}