Java日记2018-06-08

44. 数字序列中的某一位数字
    其实这题有点歧义，真实意思应该是有01234567891011121314...这样的一个整数，根据一个索引值，猜测这个索引值指向的数字是多少。这个整数是有规律的前10位是顺序的0 1 2 3...，然后是10,11,12,13..这样的东西，然后出个索引你就计算吧。

挺无趣的一个题，后面再说

45. 把数组排成最小的数

实现方法我觉得很赞，值得反复练习这种方法

public static String minNum(int[] arr)  {
        if(arr==null||arr.length==0) return null;
        String[] strArr = new String[arr.length];
        for(int i=0;i<arr.length;i++){
            strArr[i]=Integer.toString(arr[i]);
        }
        //这个地方蛮妙
        Arrays.sort(strArr, (s1,s2)->(s1+s2).compareTo(s2+s1));
        String ret = "";
        for(String str:strArr){
            ret += str;
        }
        return ret;
    }

46. 把数字翻译成字符串
    说明参考5月15日日记，具体算法就是f(n)=f(n+1)+g(n,n+1)*f(n+2)，g(n,n+1)代表索引n,n+1位置的数字是否大于25。也就是个另类的斐波那契切数列。

具体实现时候从最后一个开始算，但是我想从前算应该一样。
实现时候的错误见注释，另最好按从前往后的算法再实现一把，计划晚上或者明天吧

public static int trans(int num){
        if(num<0) return 0;
        if(num<10) return num;
        return transcore2(Integer.toString(num));
    }
    public static int transcore2(String str){
        if(str==null) return 0;
        int temp=0;
        int f1=0;
        int f2=1;
        int g=0;
        for(int i=str.length()-2;i>=0;i--){
            if(Integer.parseInt(str.charAt(i)+""+str.charAt(i+1))>25){
                g=0;
            } else{
                g=1;
            }
            temp=f2;
            //因为是反过来实现的，所以这个地方也反了
            f2=f2+g*f1;
            f1=temp;
        }
        return f2;
    }

47. 礼物的最大价值

分开来想，由于只能向上或向下移动一格。那么对于dp[i]代表每一列的最大礼物值。对于m行n列的礼物，每向右边一格代表的还是dp[i-1]+value(当前值)，或向下一格实际代表dp[i]+value(当前值)。因为向右dp实际列变大，向下实际还是那同一列的dp。（初始化dp[0]，因为i每向下走一格，对于初始列的最大礼物值就要加当前行0列的值）

 public static void getmost(int[][] arr) {
        if(arr==null) return;
        int m=arr.length;
        int n=arr[0].length;
        int[] dp = new int[n];
        for(int i=0;i<m;i++) {
            //初始化dp[0]，因为i每向下走一格，对于初始列的最大礼物值就要加当前行0列的值
            dp[0]+=arr[i][0];
            for(int j=1;j<n;j++) {
                dp[j]=Math.max(dp[j], dp[j-1])+arr[i][j];
            }
        }
        
        System.out.println("the result:"+dp[n-1]);
    }