Skip to main content

其他

删除三元组​

题目描述​

小红有一个长度为 n 的数组 a，她每次操作可以删掉一个三元组（x,y,z），要求 x < y < z，y 是 x 的倍数，z 是 y 的倍数。小红想知道最多可以执行多少次操作。

输入描述​

第一行一个整数 n（1 <= n <= 10^5），表示数组的长度。

第二行 n 个整数 a1，a2，...，an (1 <= ai <= 6)，表示数组的元素。

输出描述​

输出一个非负整数，表示最多可以执行多少次操作。

输入示例​
7
1 1 2 3 4 5 6
输出示例​
2
提示信息​

先删除(1, 2, 4)，再删除(1, 3, 6)

解答：

import java.util.Scanner;
 
public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int[] count = new int[7];
        int cnt = 0;
        for(int i = 0;i < n;i++){
            count[scanner.nextInt()]++;
        }
        for(int i = 2;i <= 3;i++){
            for(int j = 2 * i;j <= 6;j+=i){
                int minnum = Math.min(Math.min(count[1],count[i]),count[j]);
                    count[i]-=minnum;
                    count[j]-=minnum;
                    count[1]-=minnum;
                    cnt+=minnum;
                    if(count[1] ==0){
                        System.out.println(cnt);
                        return;
                    }
            }
        }
        System.out.println(cnt);
    }
}

非连续合法字符串​

题目描述​

小红有一个字符串 s，只包含小写字母。如果一个字符串中，不包含连续的三个相同的字母，并且不存在两个相同的字母紧挨着两个相同的字母，那么这个字符串就是合法的。例如，字符串“aaa”是不合法的，字符串"aabb"也是不合法的。字符串”aab”是合法的。

小红想知道，最少需要删除多少个字符，才能使得字符串变成合法的。

输入描述​

第一行一个字符串 s，长度不超过 10^5，只包含小写字母。

输出描述​

输出一个整数，表示最少需要删除的字符个数。

输入示例​
aabbaa
输出示例​
1
提示信息​

删除一个字符 b，得到 aabaa，是一个合法的字符串。

解答：

import java.util.*;
import java.io.*;
 
public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
 
        String str = in.readLine();
        int count = 0;
        int n = str.length();
        for(int i = 0; i < n; ++i){
            //aaa
            if((i + 2) < n && str.charAt(i) == str.charAt(i+1) && str.charAt(i+1) == str.charAt(i+2)){
                str = i == n - 3 ? str.substring(0, i+2) : str.substring(0, i+2) + str.substring(i+3, n);
                n--;
                i--;
                count++;
            }
            //aabb
            if(i < 0){
                continue;
            }
            if((i + 3) < n && str.charAt(i) == str.charAt(i+1) && str.charAt(i+2) == str.charAt(i+3) && str.charAt(i) != str.charAt(i+2) ){
                str =  i == n-4 ? str.substring(0, i+3) : str.substring(0, i+3) + str.substring(i+4, n);
                n--;
                i--;
                count++;
            }
        }
 
        System.out.println(count);
    }
}

约瑟夫环​

约瑟夫问题是个著名的问题：N个人围成一圈，第一个人从1开始报数，报M的将被杀掉，下一个人接着从1开始报。如此反复，最后剩下一个，求最后的胜利者。 例如只有三个人，把他们叫做A、B、C，他们围成一圈，从A开始报数，假设报2的人被杀掉。

公式法 约瑟夫环是一个经典的数学问题，我们不难发现这样的依次报数，似乎有规律可循。为了方便导出递推式，我们重新定义一下题目。 问题： N个人编号为1，2，……，N，依次报数，每报到M时，杀掉那个人，求最后胜利者的编号。

这边我们先把结论抛出了。之后带领大家一步一步的理解这个公式是什么来的。 递推公式：

f(N,M)=(f(N−1,M)+M)%Nf(N,M)=(f(N-1,M)+M)\%N

f(N,M)f(N,M)表示，N个人报数，每报到M时杀掉那个人，最终胜利者的编号 f(N−1,M)f(N-1,M)表示，N-1个人报数，每报到M时杀掉那个人，最终胜利者的编号

下图表示这一过程（先忽视绿色的一行）:

这里写图片描述

推导这个公式。

  • 问题1： 假设我们已经知道11个人时，胜利者的下标位置为6。那下一轮10个人时，胜利者的下标位置为多少？

    答： 其实吧，第一轮删掉编号为3的人后，之后的人都往前面移动了3位，胜利这也往前移动了3位，所以他的下标位置由6变成3。

  • 问题2： 假设我们已经知道10个人时，胜利者的下标位置为3。那下一轮11个人时，胜利者的下标位置为多少？

    答： 这可以看错是上一个问题的逆过程，大家都往后移动3位，不过有可能数组会越界，所以最后模上当前人数的个数

  • 问题3： 现在改为人数改为N，报到M时，把那个人杀掉，那么数组是怎么移动的？ 答： 每杀掉一个人，下一个人成为头，相当于把数组向前移动M位。若已知N-1个人时，胜利者的下标位置位f(N−1,M)f(N-1,M)，则N个人的时候，就是往后移动M为，(因为有可能数组越界，超过的部分会被接到头上，所以还要模N)，既f(N,M)=(f(N−1,M)+M)%Nf(N,M)=(f(N-1,M)+M)\%N

**注：**理解这个递推式的核心在于关注胜利者的下标位置是怎么变的。每杀掉一个人，其实就是把这个数组向前移动了M位。然后逆过来，就可以得到这个递推式。

因为求出的结果是数组中的下标，最终的编号还要加1

    // 约瑟夫环问题的解决方法，接收总人数 n 和报数 m 作为参数
    public static int josephus(int n, int m) {
        // 初始化结果为 0
        int result = 0;
        // 从 2 开始循环到 n，模拟约瑟夫环的报数过程
        for (int i = 2; i <= n; i++) {
            // 根据约瑟夫环的递推公式更新结果
            result = (result + m) % i;
        }
        // 返回最后剩下的人的编号，因为编号从 1 开始，所以加 1
        return result + 1;
    }