字节面试算法题

三角形最短路径和（动态规划）

三角形最短路径和（动态规划）

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Solution {
    
    public int minimumTotal(List<List<Integer>> triangle) {
    
        //对于一个数字的处理
        if (triangle.size() == 1) return triangle.get(0).get(0);
        int min = Integer.MAX_VALUE;
        int rec[][] = new int[triangle.size()][];
        for (int i = 0; i < triangle.size(); ++i){
    
            rec[i] = new int[i + 1];
        }
        rec[0][0] = triangle.get(0).get(0);
        for (int i = 0; i < triangle.size() - 1; ++i){
    
            List<Integer> curLine = triangle.get(i);
            List<Integer> nextLine = triangle.get(i + 1);
            for (int j = 0; j < triangle.get(i).size(); ++j){
    
                int first = nextLine.get(j);
                int second = nextLine.get(j + 1);
                int cur = rec[i][j];
                /*当为第一个的时候应该是直接相加即可其余的情况进行最小值的判断因为到达这个位置存在着两条路径需要对这两条路径进行比较*/
                if (j == 0){
    
                    //j == 0的情况
                    rec[i + 1][j] =  first + cur;
                    rec[i + 1][j + 1] =  second + cur;
                }else {
    
                    //j > 1的情况需要对之前得到的值进行比较
                    rec[i + 1][j] = Math.min(rec[i + 1][j], cur + first);
                    //对于第二个位置直接相加因为在下一次的时候这个位置会转为第一个位置会进行最小值的比较在纸上画一下图是很好理解的
                    rec[i + 1][j + 1] = second + cur;
                }
            }
        }
        for (int i = 0; i < triangle.size(); ++i){
    
            min = Math.min(min, rec[triangle.size() - 1][i]);
        }
        return min;
    }
}

二叉树遍历

汉字数字 转换int

import java.util.regex.Pattern;
 
public class MoneyTest {
    
 
    public static long parse(String money) {
    
        long result = 0;
        char c = 0;
 
        boolean flag = Pattern.matches("^.*亿.*万.*$", money);
 
        for (int i = 0; i < money.length(); i++) {
    
            switch (money.charAt(i)) {
    
            case '零':
                break;
            case '一':
                c = 1;
                break;
            case '二':
                c = 2;
                break;
            case '三':
                c = 3;
                break;
            case '四':
                c = 4;
                break;
            case '五':
                c = 5;
                break;
            case '六':
                c = 6;
                break;
            case '七':
                c = 7;
                break;
            case '八':
                c = 8;
                break;
            case '九':
                c = 9;
                break;
            case '十':
                result += (c == 0 ? 10 : c * 10);
                c = 0;
                break;
            case '百':
                result += c * 100;
                c = 0;
                break;
            case '千':
                result += c * 1000;
                c = 0;
                break;
            case '万':
                result = (result + c) * 10000;
                c = 0;
                break;
            case '亿':
                if (flag){
    
                    result = (result + c) * 10000;
                }else{
    
                    result = (result + c) * 100000000;
                }
                c = 0;
                break;
            default:
                c = 0;
            }
 
        }
        if (c != 0)
            result += c;
        return result;
 
    }
 
    public static void main(String args[]) {
    
        System.out.println(MoneyTest.parse("一百三十四亿一千零二十三万六千六百零九"));
    }
}