第一部分

既有ACM，也有核心模式

第一题

给个数组，给个M，求数组中所有比M小的组合数

输入：

7 -1 -1

9

输出：3

因为7和第一个-1，7和第二个-1，第一个-1 和第二个-1

100%过

import java.util.Arrays;
import java.util.Scanner;

/**
 * @author keboom
 * @date 2021/8/21
 */
public class Solution1 {

    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] s = sc.nextLine().split(" ");
        int[] nums = new int[s.length];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = Integer.valueOf(s[i]);
        }
        int M = sc.nextInt();
//        System.out.println(Arrays.toString(nums));
//        System.out.println(M);

        int res = sumBiggerM(nums, M);
        System.out.println(res);
    }

    private static int sumBiggerM(int[] nums, int M) {
        int res = 0;
        for (int i = 0; i < nums.length-1; i++) {
            for (int j = i+1; j < nums.length; j++) {
                if (nums[i] + nums[j] <= M) {
                    res++;
                }
            }
        }
        return res;
    }
}

第二题

L1 = a L2 = b L3 = c ................. L26 = z

Si = Si-1 + Li + reverse(invert(Si-1))

reverse 为翻转字符串，invert为反转每个字符比如a反转为z，b反转为y，c反转为x

S1 = a S2 = a + b + z = abz

S3 = abz + c + reverse(zya) = abzcayz

.......................

输入n为Sn的意思，k为Sn字符串第k个字符

输入：2 1

输出：a S2的第一个字符为a

输入：3 6

输出：y S3的第6个字符为y

100%过

/**
 * @author keboom
 * @date 2021/8/21
 */
public class Solution2 {

    // si = si-1 + li + reverse(invert(si-1))
    public char findKthBit(int n, int k) {
        String[] dp = new String[n + 1];
        dp[1] = "a";
        for (int i = 2; i <= n; i++) {
            char Li = (char) ('a' + i - 1);
            dp[i] = dp[i - 1] + Li + reverse(invert(dp[i - 1]));
        }
        return dp[n].charAt(k-1);
    }

    public String reverse(String s) {
        return new StringBuilder(s).reverse().toString();
    }

    public String invert(String s) {
        StringBuilder sb = new StringBuilder();
        for (char c : s.toCharArray()) {
            char res = (char) ('z' - (c - 'a'));
            sb.append(res);
        }
        return sb.toString();
    }

    public static void main(String[] args) {
//        char res = 'z' - ('c' - 'a');
//        System.out.println(res);
        Solution2 s2 = new Solution2();
//        String abz = s2.invert("abz");
//        System.out.println(abz);
//        System.out.println(s2.reverse("abc"));
//        char Li = (char) ('a' + 2);
//        System.out.println(Li);
        char res = s2.findKthBit(4, 11);
        System.out.println(res);
    }
}

第三题

有一些小孩，他们有年龄，他们围成一圈，年龄高的小孩要比临近他的小孩多给纸张，求最少要给这些小孩多少纸张

输入：1 1 1

输出：3 三个小孩围一圈，年龄都相等，每人给一张

输入：1 2 3

输出：6 年龄为1的给1张，年龄为2的给两张，年龄为三的给三张

输入：5

输出：1 只有一个人就给一张

80%过，我的思路是不停的找年龄最小的，他的纸张应该是他临近的两个人中的纸张数大的+1，如果他跟他临近的两人年龄相等，那就不用+1

import java.util.*;

/**
 * @author keboom
 * @date 2021/8/21
 */
public class Solution3 {

    //80  围成一圈小孩发纸，岁数大的要邻近的多发，求最少要多少只
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String[] s = sc.nextLine().split(" ");
        int[] nums = new int[s.length];
        int[][] map = new int[nums.length][2];
        for (int i = 0; i < nums.length; i++) {
            nums[i] = Integer.valueOf(s[i]);
            map[i][0] = nums[i];
            map[i][1] = i;
        }
        Arrays.sort(map, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });
        if (nums.length == 1) {
            System.out.println(1);
            return;
        }
//        System.out.println(map.toString());
        int[] papers = new int[nums.length];
//        System.out.println(Arrays.deepToString(map));
        for (int[] ints : map) {
            int index = ints[1];
            int max = 0;
            boolean isequals = false;
            if (index == 0) {
                max = Math.max(papers[papers.length - 1], papers[1]);
                if (nums[index] == nums[papers.length - 1] || nums[index] == nums[1]) {
                    isequals = true;
                }
            } else if (index == papers.length - 1) {
                max = Math.max(papers[index - 1], papers[0]);
                if (nums[index] == nums[index - 1] || nums[index] == nums[0]) {
                    isequals = true;
                }
            } else {
                max = Math.max(papers[index - 1], papers[index + 1]);
                if (nums[index] == nums[index - 1] || nums[index] == nums[index + 1]) {
                    isequals = true;
                }
            }
            papers[index] = isequals ? max : max + 1;
            if (papers[index] == 0) {
                papers[index] = 1;
            }
        }
        int sum = 0;
        for (int i : papers) {
            sum += i;
        }
        System.out.println(sum);

    }
}

第四题

给你一个二维矩阵，0表示水，1表示陆地，2表示障碍物

走水路要花2钱，走陆地要花1钱，障碍物没法走

求从左上角，到右下角要花的最少的钱，如果走不过去，那么就返回-1

左上角起始位置（0，0）不花钱，右下角终点是花钱的

输入：[[1,1,1,1,0],[0,1,0,1,0],[1,1,2,1,1],[0,2,0,0,1]]

输出：7 路径为 0,1--0,2--0,3--1,3--2,3--2,4--3,4

只过了50%，他报错说数组越界，不知道为啥？

import java.util.Arrays;

/**
 * @author keboom
 * @date 2021/8/21
 */
public class Solution4 {

    public int minSailCost (int[][] input) {
        int row = input.length;
        int col = input[0].length;
        int[][] dp = new int[row][col];
        for (int i = 0; i < dp.length; i++) {
            Arrays.fill(dp[i],-1);
        }
        dp[0][0] = 0;
        for (int i = 1; i < row; i++) {
            if (dp[i - 1][0] == -1 || input[i][0] == 2) {
                dp[i][0] = -1;
            } else {
                int val = input[i][0] == 0 ? 2 : 1;
                dp[i][0] = dp[i-1][0] + val;
            }
        }
        for (int i = 1; i < col; i++) {
            if (dp[0][i-1] == -1 || input[0][i] == 2) {
                dp[i][0] = -1;
            } else {
                int val = input[0][i] == 0 ? 2 : 1;
                dp[0][i] = dp[0][i-1] + val;
            }
        }
        for (int i = 1; i < row; i++) {
            for (int j = 1; j < col; j++) {
                if (input[i][j] == 2 || (dp[i - 1][j] == -1 && dp[i][j - 1] == -1)) {
                    dp[i][j] = -1;
                } else {
                    int val = input[i][j] == 0 ? 2 : 1;
                    if (dp[i - 1][j] == -1) {
                        dp[i][j] = dp[i][j-1] + val;
                    } else if (dp[i][j - 1] == -1) {
                        dp[i][j] = dp[i - 1][j] + val;
                    } else {
                        dp[i][j] = Math.min(dp[i - 1][j], dp[i][j - 1]) + val;
                    }
                }
            }
        }
        return dp[row-1][col-1];
    }

    // [[1,1,1,1,0],[0,1,0,1,0],[1,1,2,1,1],[0,2,0,0,1]]
    public static void main(String[] args) {
        int[][] input = {{1,1,1,1,0},{0,1,0,1,0},{1,1,2,1,1},{0,2,0,0,1}};

        int res = new Solution4().minSailCost(input);
        System.out.println(res);

    }
}

第二部分

两种常见的软件开发模型并说出特点

如果有更好的答案，求分享哦~

在评论区打出来~