第一题:删除数位求是否能整除
题目大意:有a和b两个整数,每次操作都可以对a和b删除一位,比如a=‘1234’一次操作可以变为‘123’,‘124’,‘134’,‘123’,操作N次后,a可以被b整除或者b可以被a整除,求最少操作次数
示例:a=1234 b=99,输出:2
理由:a变为234,b变为9,操作2次
思路:看了别人的代码才知道,要先把新的数用Set存起来,然后遍历判断(因为要判断最少操作数,所以要用Set存储)重点在于别人dfs,使用双重递归,要学会用。
代码:
- import java.util.HashSet;
- import java.util.Scanner;
- import java.util.Set;
-
- public class Main_1 {
- public static void main(String[] args) {
- Scanner sc = new Scanner(System.in);
- int a = sc.nextInt(), b = sc.nextInt();
- Set
set1 = new HashSet<>(), set2 = new HashSet<>(); - backtrack(set1, a + "", "", 0);
- backtrack(set2, b + "", "", 0);
- int alen = (a + "").length(), blen = (b + "").length();
- int res = Integer.MAX_VALUE;
- for (Integer si : set1) {
- for (Integer sj : set2) {
- System.out.println(si + " " + sj);
- if (si % sj == 0 || sj % si == 0) {
- res = Math.min(alen - (si + "").length() + blen - (sj + "").length(), res);
- }
- }
- }
- System.out.println(res == Integer.MAX_VALUE ? -1 : res);
- }
- static void backtrack (Set
set, String s, String c, int i) { - if (i == s.length()) {
- if (c.length() > 0){
- int val = Integer.parseInt(c);
- set.add(val);
- }
- return;
- }
- //好好体会一下这个递归的执行过程
- backtrack(set, s, c + s.charAt(i), i + 1);
- backtrack(set, s, c, i + 1);
- }
- }
第二题:长城数组
题目大意:数组可构成长城数组,比如[4,5,4,5,4,5]这样的是长城数组,每次操作可对原数组某一位元素进行+1操作,求最少操作次数
示例:输入[1,1,4,5,1,4],输出:11
思路:得到数组中奇数项的最大值,偶数项的最大值,遍历
注意:都要使用 long类型存储数据
代码:
- import java.util.Scanner;
-
- public class Main_2 {
- public static void main(String[] args) {
- Scanner sc = new Scanner(System.in);
- int n = sc.nextInt();
- long[] arr = new long[n];
- for (int i = 0; i < n; i++) {
- arr[i] = sc.nextInt();
- }
- long res = 0;
- long max1 = 0;
- long sum = 0;
- long cnt = 0;
- //偶数项的最大值
- for (int i = 0; i < n; i += 2) {
- max1 = Math.max(arr[i], max1);
- sum += arr[i];
- cnt++;
- }
- res += max1 * cnt - sum;
- long max2 = 0;
- sum = 0;
- cnt = 0;
- //奇数项的最大值
- for (int i = 1; i < n; i += 2) {
- max2 = Math.max(arr[i], max2);
- sum += arr[i];
- cnt++;
- }
- res += max2 * cnt - sum;
- if (max1 == max2) res += n / 2;
- System.out.println(res);
- }
- }
第三题:好e
题目大意: 一个字符串由r d e三种字符组成,好e的定义是e的两边分别是r和d,输入字符串,三种字符都可以修改求尽可能多地把e变好e,求最少操作次数
示例:输入derrd,输出1,即把字符串变为dered
思路:不会写,别人的代码(还不太懂)
- public class Main {
- public static void main(String[] args) {
- Scanner sc = new Scanner(System.in);
- String s = sc.next();
- if (s.length() < 3) {
- System.out.println(0);
- return;
- }
- String[] strs = new String[]{"red","der"};
- StringBuilder sb = new StringBuilder();
- int idx = 0;
- while(sb.length() < s.length() - 3) {
- sb.append(strs[idx % 2]);
- idx++;
- }
- int res = Integer.MAX_VALUE;
- int sum = 0;
- String str = sb.toString();
- for (int i = 0; i < str.length() - 3; i++) {
- if (str.charAt(i) != s.charAt(i)) sum++;
- }
- res = Math.min(sum, res);
- sb = new StringBuilder();
- idx = 1;
- while(sb.length() < str.length() - 3) {
- sb.append(strs[idx % 2]);
- idx++;
- }
- sum = 0;
- str = sb.toString();
- for (int i = 0; i < s.length() - 3; i++) {
- if (str.charAt(i) != s.charAt(i)) sum++;
- }
- res = Math.min(sum, res);
- System.out.println(res);
- String endStr = s.substring(s.length() - 3);
- if (endStr.charAt(0) == 'e' && endStr.charAt(1) != 'e' || endStr.equals("red") || endStr.equals("der")) {
- System.out.println(res);
- return;
- } else {
- System.out.println(res + 1);
- }
- }
- }
第四题:V三元组
题目大意:V三元组的定义为,有个三元组,第一个元素等于第三个元素,且第一个元素大于第二个元素,三个元素形成V结构,数学描述为[ax,ay,az],其中 ax = az且 ax > ay
示例: 输入[3,1,3,4,3,4],输出3
理由: 可构成三元组为[3,1,3] [3,1,3] [4,3,4], 题目为了更加清晰描述,给我们的是索引(从1开始),即为(1,2,3) (1,2,5) (4,5,6)
自己写的代码超时了,有重复遍历的情况
- import java.util.Scanner;
-
- public class Test4 {
-
- public static void main(String[] args) {
- Scanner sc = new Scanner(System.in);
- int n = sc.nextInt();
- sc.nextLine();
- String[] input = sc.nextLine().split(" ");
- int[] A = new int[n];
- for(int i=0;i
- A[i] = Integer.parseInt(input[i]);
- }
- int res = 0;
- for(int i=0;i
2;i++){ - int a_i = A[i];
- int k = i+2;
- for(k=i+2;k
- if(A[k] == a_i){
- for(int j=i+1;j
- if(A[j] < a_i){
- res++;
- }
- }
- }
- }
- }
- System.out.println(res);
- }
- }
借鉴别人的代码,使用前缀和来减少遍历次数
- public static void main(String[] args) {
- Scanner sc = new Scanner(System.in);
- int n = sc.nextInt();
- int[] a = new int[n];
- for (int i = 0; i < n; i++) {
- a[i] = sc.nextInt();
- }
- long res = 0;
- for (int i = 0; i < n - 2; i++) {
- int sum = 0;
- for (int j = i + 1; j < n; j++) {
- if (a[j] < a[i]) sum++;
- else if(a[j] == a[i]) res += sum;
- }
- }
- System.out.println(res);
- }
-
相关阅读:
国产化系统加密/国产化系统防泄密
白话模电:3.三极管(考研面试与笔试常考问题)
LCR 122.路径加密
46.集群节点维护—添加节点
力扣226:反转二叉树
低代码助力教培机构管理,数字化+智能化
Maven 构建&项目测试
1.3.3系统调用
面试中的技术趋势:如何展示你跟进最新技术的能力
牛客网AI面试第二弹
-
原文地址:https://blog.csdn.net/qq_38235017/article/details/126445363