Byte interview algorithm question

Triangle shortest path and （ Dynamic programming ）

Triangle shortest path and （ Dynamic programming ）

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;
public class Solution {
    
    public int minimumTotal(List<List<Integer>> triangle) {
    
        // Processing of a number 
        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];
                /* When it is the first one, it should be added directly, and the minimum value can be judged in the rest cases, because there are two paths to reach this position, and these two paths need to be compared */
                if (j == 0){
    
                    //j == 0 The situation of 
                    rec[i + 1][j] =  first + cur;
                    rec[i + 1][j + 1] =  second + cur;
                }else {
    
                    //j > 1 The previous values need to be compared 
                    rec[i + 1][j] = Math.min(rec[i + 1][j], cur + first);
                    // For the second position, add it directly, because next time, this position will turn into the first position, and the minimum value will be compared. It is easy to understand to draw a figure on the paper 
                    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;
    }
}

Binary tree traversal

Chinese characters and numbers transformation 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("^.* Billion .* ten thousand .*$", money);
 
        for (int i = 0; i < money.length(); i++) {
    
            switch (money.charAt(i)) {
    
            case ' zero ':
                break;
            case ' One ':
                c = 1;
                break;
            case ' Two ':
                c = 2;
                break;
            case ' 3、 ... and ':
                c = 3;
                break;
            case ' Four ':
                c = 4;
                break;
            case ' 5、 ... and ':
                c = 5;
                break;
            case ' 6、 ... and ':
                c = 6;
                break;
            case ' 7、 ... and ':
                c = 7;
                break;
            case ' 8、 ... and ':
                c = 8;
                break;
            case ' Nine ':
                c = 9;
                break;
            case ' Ten ':
                result += (c == 0 ? 10 : c * 10);
                c = 0;
                break;
            case ' hundred ':
                result += c * 100;
                c = 0;
                break;
            case ' thousand ':
                result += c * 1000;
                c = 0;
                break;
            case ' ten thousand ':
                result = (result + c) * 10000;
                c = 0;
                break;
            case ' Billion ':
                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(" 13.4 billion, 10.2 million, 26.69 million "));
    }
}