刷算法day2

砍一刀

来源：京东2024年秋招-京东-后端开发岗-第1批笔试有一个序列 a1,a2,...,ana1,a2,...,an ，牛牛将对这个序列切割一刀（划分分成两个不相交的非空序列，一个序列为 a1,…,apa1,…,ap，另一个序列为 ap+1,…,anap+1,…,an），牛牛切割的代价为两个序列元素和的乘积。牛牛想知道切割代价最小是多少。

解决：前缀和，一遍统计

代码：

public class Main {
    public static void main(String[] args) {
       	Scanner scanner = new Scanner(System.in);
		int n = scanner.nextInt();
		int [] arr = new int[n+1];
		int [] sum = new int[n+1];
		for(int  i=1;i<=n;i++) {
			arr[i] = scanner.nextInt();
			sum[i] =sum[i-1]+arr[i];
		}
		long minNumber = Long.MAX_VALUE;
		for(int i = 1 ;i<n;i++) {
			long startNumber = sum[i] - sum[0];
	
			long endNumber = sum[n] -sum[i];
			
			minNumber = Math.min(minNumber, endNumber * startNumber);
		}
		System.out.println(minNumber);
    }
}

字符串排序：

大致：给定 nn 个字符串，请你对这 nn 个字符串按照以下规则从小到大排序。对于任意两个字符串 ss 和 tt ，在排序后应当满足：

若 ss 是 tt 的一个前缀，则 ss 在排序后的下标小于等于 tt 的在排序后的下标。
若存在整数 ii ，使得 ss 的前 i−1i−1 个字符和 tt 的前 i−1i−1 个字符相同，且 ss 和 tt 的第 ii 个字符不同，则比较第 ii 个字符的大小关系（字符的大小关系顺序由输入数据给出）。若 ss 的第 ii 个字符小于等于 tt 的第 ii 个字符，则 ss 在排序后的下标小于等于 tt 的在排序后的下标。

大致就是给定一个26字母默认排序表，然后给你几个字符串，按照给定字典顺序来排序，前缀相同按长度短前面，内容不同按字典顺序来排序：代码如下：

解题思路：根据输入的26 通过数组来存储数字大小，然后通过sort 根据条件来遍历排序即可：

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String  str = scanner.nextLine();
        int [] arr = new int[26];
        for(int i = 0 ; i < 26 ; i++){
            arr[str.charAt(i) -'a'] = i;
        }
        int n = scanner.nextInt();
        scanner.nextLine();
        String[] strs = new String[n];
        for(int i = 0 ; i < n ; i++){
            strs[i] = scanner.nextLine();
        }
        Arrays.sort(strs, (o1, o2) -> {
            int minLength = Math.min(o1.length(), o2.length());
            for(int i =0 ; i< minLength ; i++){
                if(o1.charAt(i)!=o2.charAt(i)){
                    return Integer.compare(arr[o1.charAt(i) - 'a'], arr[o2.charAt(i) - 'a']);
                }
            }

            return Integer.compare(o1.length(), o2.length());
        });
        for(String s : strs){
            System.out.println(s);
        }
    }
}