这是参加百度松果菁英班的3月日常练习题-1，题目价值量挺高，网上只有类似的题型，题解只有对其思路的讲解，而且是C++的代码风格，下方是我自己做的，不会就去参考题解，编写的Java题解，凭借自己的理解写了点核心代码的注释。在学习算法和数据结构时，简单学习过C++，可以应付大部分编程题，而Java是来开发项目，现在尝试用Java解题。对于打*的题目是用java做不出的或运行没法通过的，打.的题目是用java做出部分通过的，欢迎大家进行点评指正，共同进步。
一、找1
题目：最近小码哥爱上二进制，他特别喜欢全是1的二进制串，但通常会有0。于是他给你一个二进制字符串，问你字符都为1的子串的个数（结果对10°＋7取模)。
/** 输入格式:一个二进制字符串 输出格式:所有字符都为1的子串个数 样例1 样例2 样例2 输入：0110111 输入：101 输入：111111 输出：9 输出：2 输出：21 备注 s[i] == '0' 或 s[i] == '1' 1 <= s.length <= 10^5 */ import java.util.Scanner; import java.util.*; class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); String str = input.next(); // code here int mod = 1000000007; int result = 0; int num = 0; for(int i = 0; i < str.length(); i++){ if(str.charAt(i) == '1'){ num++; }else{ //规律：11 -> 1 + 2 = 3 1111 -> 1 + 2 + 3 + 4 = 10 //也就是单纯的排列问题 1 + 2 + …… + n = (1 + n)*n / 2 result = (result + num*(num + 1) / 2) % mod; num = 0; } } //考虑收尾，如果最后一次都为1，需要加上 result = (result + num*(num + 1) / 2) % mod; System.out.println(result); input.close(); } }
二、挑兵挑将
题目：马上要进行阅兵仪式了，将军要在手下n个人中挑人参加，他用以下方法选人：n个人站成一圈，逆时针编号为1一n ，现在A、B两人选人。A逆时针数k个停下来，B顺时针数m个停下来，被选中的1或2个人输出，直至所有人输出。首次从A从1开始，B从N开始，之后AB分别从上次各自的位置的各自方向的下一位接着数。
/** 输入格式:可能有多组数据，每组一行输入三个整数n、k、m，输入000停止。 输出格式:输出每轮选出的人，用,隔开，每个编号占3个格子(右对齐)。 样例1 输入：10 4 3 0 0 0 输出：4 8, 9 5, 3 1, 2 6, 10, 7 备注 0<n<=20；k,m在int范围内，且为正数；组数少于20 */ import java.util.Scanner; import java.util.*; class Main { public static int solve(int p, int d, int t, int n, int[] a){ while(t > 0){ do{ //转圈一个个找物核心公式：(p - c + d + n) % n + c //p -> 当前位置 c -> 当前位置 d -> 顺时针或逆时针循环 n -> 总人数，一个周期 p = (p - 1 + d + n) % n + 1; }while(a[p] == 0); t--; } return p; } public static void main(String[] args) { Scanner input = new Scanner(System.in); // code here int[] a = new int[25]; while(true){ int n = input.nextInt(); int k = input.nextInt(); int m = input.nextInt(); if(n==0 && k==0 && m==0){ break; }else{ for(int i = 1; i <= n; i++){ a[i] = 1; } int person = n; int A = n; int B = 1; while(person > 0){ A = solve(A, 1, k, n, a); B = solve(B, -1, m, n, a); if( A == B){ System.out.printf("%3d", A); person--; }else{ System.out.printf("%3d%3d", A, B); person -= 2; } a[A] = a[B] = 0; if(person > 0){ System.out.printf(","); } } System.out.print("\n"); } } input.close(); } }
三、水位线
题目：饮水机中本来有k升水,小码哥希望在t天内饮水机的水量保持在[1,r]之间,小码哥知道每天会用掉x升水,而小码哥可以在一天的开始选择加y升(一天只能加一次)或不加。给出 k,l, r ,t, x,y ,求能否在t天内把水量控制在 [l,r]，能输出Yes,否则输出No。
/** 输入格式:仅一行为 k,l, r ,t, x,y 输出格式:输出Yes或输出No 样例1 输入：8 1 10 2 6 4 输出：No 备注 其中: 1<l≤k≤r ≤1e9,1 ≤t ≤1e9,1 ≤x ≤1e6,1≤y ≤1e9。 */ import java.util.Scanner; import java.util.*; class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); // code here int[] a = new int[10]; for(int i = 0; i <= 5; i++){ a[i] = input.nextInt(); } while(a[3] > 0){ // 判断饮水机的水量的临界值即可，符合则加水 if(a[0] + a[5] <= a[2]){ a[0] += a[5]; } // 判断饮水机的水量的临界值即可，符合则用掉水 if(a[0] - a[4] > a[1]){ a[0] -= a[4]; }else{ System.out.printf("No"); return; } a[3]--; } System.out.printf("Yes"); input.close(); } }
四、小码哥的跳棋游戏
题目：小码哥喜爱跳棋。跳棋游戏在一条直线上，一共n个位置( 1 ~n )，每个位置有2个状态: 0表示没有棋子，1表示有棋子。小码哥的棋子自然是能通过没有棋子的位置。当面前有1个棋子时，小码哥可以直接跳过。当有两个及以上棋子连在一起时，小码哥的棋子是跳不过去的。这时候，就要花费能量，破坏掉一些棋子，才能跳过。已知破坏一枚棋子需要花费一点能量。小码哥的棋子从第0个位置出发，现在要求小码哥到达终点(第n个位置)至少需要花费多少能量?
/** 输入格式:第1行包含一个正整数n ;第2行n个整数ai，表示棋盘的状态。 输出格式:一个整数，输出最小耗费的能量数。 样例1 输入：5 0 1 1 0 0 输出：1 备注 其中: 1<=n<=10^5 */ import java.util.Scanner; import java.util.*; class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); // code here int n = input.nextInt(); int[] a = new int[100005]; for(int i = 1; i <= n; i++){ a[i] = input.nextInt(); } int num = 0; //核心：a[i] == 1 && a[i + 1] == 1 -> 连续两个1只需摧毁后一个 for(int i = 1; i <= n; i++){ if(a[i] == 1 && a[i + 1] == 1){ a[i + 1] = 0; num++; } } //若最后一位为0的话加起来不影响，若为1的话需要消耗能量破坏掉占据位置 //结尾为1的例子：011111 -> 010111 --> 01010 1 -> 最后一位不能跳过需要销毁 //结尾为0的例子：011110 -> 010110 --> 01010 0 -> 最后一位为空，加0不影响 num += a[n]; System.out.printf("%d", num); input.close(); } }
五、小码哥与机器人
题目：小码哥新买了一个机器人，但是这个机器人因为很便宜只能做三个动作.三个动作:前进FD，倒退BK和重复REPEAT。FD后加数字表示前进多少步;BK后加数字表示后退多少步;REPEAT后加数字再加方括号，表示重复方括号里的命令。三个动作加的数字均为正整数。(*)
命令的格式:1.FD与BK命令组合;2.REPEAT命令内加REPEAT命令与FD、BK组合，且REPEAT排在最后。
/** 输入格式:一行字符串（长度不超过200) 。 输出格式:表示最后得到的步数，表示离起点的距离（非负整数)。 样例1 输入：REPEAT 5[ FD 50 REPEAT 10[FD 100]] 输出：5250 */ // java为实现，下方是我编写的各种可能的代码，都是报`Nosuchelementexception异常`--`无元素异常`，百度也没找到相关的解决办法，热烈欢迎各位的指正，共同进步~ import java.util.Scanner; import java.util.*; class Main { public static long order(){ Scanner input = new Scanner(System.in); long result = 0; // String str = input.next(); char firstNum = input.next().charAt(0); while(firstNum != '\0'){ if(firstNum == ']'){ break; } // String afterNum = str.substring(1); long num = input.nextInt(); // String str1 = input.next(); // long num = str1.charAt(0) - '0'; if(firstNum == 'R'){ // char k = str1.charAt(1); char k = input.next().charAt(0); // char k = (char)new BufferedReader(new InputStreamReader(System.in)).read(); result += firstNum * order(); } if(firstNum == 'F'){ result += num; } if(firstNum == 'B'){ result -= num; } } input.close(); return result; } public static void main(String[] args) { // code here long result = Math.abs(order()); System.out.printf("%ld", result); } } // c++题解 #include<bits/stdc++.h> using namespace std; long long order(){ string str; char firstNum, k; long long num, result = 0; while( cin >> firstNum ){ if(firstNum == ']'){ break; } cin >> str >> num; if(firstNum == 'R'){ cin >> k;//也就是输入[ result += num * order(); } //原本打算用三目运算法的，发现这里不适合使用，firstName的值需要准确，测试输出发现FFRR，根据递归而减去了55 // result = firstNum == 'F' ? result += num : result -= num; if(firstNum == 'F'){ result += num; } if(firstNum == 'B'){ result -= num; } } return result; } int main( ) { cout << abs(order()); return 0; }
六、银行账户
题目：据说对银行账户进行盗窃时，如果只盗取小数点下的数值，就不容易引起注意，所以你决定进行尝试。银行总共有n个账户, m次转账，对每次转账，你可以盗取（转账金额-转账金额下取整）的资金，并使转入账户的警戒值增加相同数值，当任意账户的警戒值>1，或者无法实现转账（转出账户余额不足)，或者m次转账全部完成，你停止盗取，请计算总盗取金额。（*）
/** 输入格式:第一行n，m，表示有n个账户，m条转账记录;第二行n个实数，表示每个账户的资金;接下来m行，每行有三个参数;整数α，整数y，实数z，分别表示转出账户，转入账户，和转账金额。输出盗取金额,保留两位小数。 输出格式:表示最后得到的步数，表示离起点的距离（非负整数)。 样例1 输入：5 5 2 2 2 2 2 1 2 1.5 2 1 1.5 1 2 1.5 2 1 1.5 1 2 1.5 输出：2.00 备注: 1 <= n <= 1000, 1<= m <= 10000; 0< 每个账户初始资金 < 10; 1<= x, y <= n, x!= y; 0 < z < 100; */ //测试用例可以通过，运行时出现运行错误，调试了很久，没看出来是哪里出错，欢迎帮忙大家指正 import java.util.Scanner; import java.util.*; class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); // code here int n = input.nextInt(); int m = input.nextInt(); // ps：这里是double数组，不然double赋值给int会导致精度损失 double count[] = new double[1005]; double warn[] = new double[1005]; for(int i = 1; i <= n; i++){ count[i] = input.nextInt(); // System.out.println( count[i]); warn[i] = 0; // System.out.println( warn[i]); } int x, y; double z; double sum = 0.0d; for(int i = 1; i <= m; i++){ x = input.nextInt(); y = input.nextInt(); z = input.nextDouble(); if(count[x] < z){ break; } // 根据输入 第一次x = 1 ; 第二次x = 2 count[x] -= z; // System.out.println( count[x]); sum += z - Math.floor(z); count[y] += Math.floor(z); warn[y] += z - Math.floor(z); // System.out.println( z); // System.out.println(Math.floor(z)); // System.out.println( count[y]); // System.out.println( warn[y]); // System.out.println(sum); if(warn[y] > 1.0){ break; } } System.out.println(String.format("%.2f", sum)); input.close(); } }
七、数字问题
题目：输入n，输出1一n的自然数中各数位只包含0或1的数的个数。
/** 输入格式:输入一个整型数字n(1 ≤n ≤1e9) 输出格式:输出一行一个整数表示答案 样例1 输入：19 输出：3 */ import java.util.Scanner; import java.util.*; class Main { static int sum = 0; public static void num(int m, int n){ if(m > n){ return; }else{ sum++; } num(m * 10, n);//递归 n -> 1 , 10 num(m * 10 + 1, n);// n = 0 , n -> 1 , 11 } public static void main(String[] args) { Scanner input = new Scanner(System.in); // code here int n = input.nextInt(); num(1 ,n); System.out.printf("%d",sum); input.close(); } }
八、字符串的解码
题目：给你一个字符串，由[，]，数字和大写字母组成，现要求对其解码。字符串中形如[Dx]，表示D个连续的X，例如[4CB]或[2[2CB]]都可以表示，一旦出现括号就会有数字，且为正整数，会有两组方括号相邻的情况，如[4A][5B]。（.）
/** 输入格式:AC[3FUN] 输出格式:ACFUNFUNFUN 样例1 输入：19 输出：3 */ import java.util.Scanner; import java.util.*; class Main { static int len; static String str; public static void s(int num){ // C++类似逻辑的代码可以通过 // java部分通过，也就是正规的输入可以有相应的输出 if(num == len || str.charAt(num) == ']'){ return; } // 若是这种 ]]][4A][5B] 就无法正确输出 // 下面是我尝试修改的代码，发现输出为ABBBBBABBBBBABBBBBABBBBBBBBBB // 感觉把s(num)和return去掉，问题不大，可是就报数组越界异常，希望哪位大佬帮忙解决 // if(num == len){ // return; // } // if(str.charAt(num) == ']'){ // num++; // s(num); // return; // } if(str.charAt(num) == '['){ num++; int sum = 0; while(str.charAt(num) >= '0' && str.charAt(num) <= '9'){ sum = sum * 10 + str.charAt(num) - '0';//若是数字大于等于10时 num++; } while(sum > 0){ sum--; s(num); } int tmp = 1;//当]比[多一个时跳出循环 while(tmp > 0){//循环字符串，跳过索引字母 if(str.charAt(num) == '['){ tmp++; }else if(str.charAt(num) == ']'){ tmp--; } num++; } s(num); }else{ while(str.charAt(num) >= 'A' && str.charAt(num) <= 'Z'){ System.out.printf("%s", str.charAt(num)); num++; } s(num); } } public static void main(String[] args) { Scanner input = new Scanner(System.in); // code here str = input.nextLine(); len = str.length(); s(0); input.close(); } }
九、斐波那契，但是是字符串
题目：现在有字符串组:第0项a0=“IAKIOI";第1项a1=“WHENWILLSCORLLOFTAIWUCOMEOUT!!!”;之后的第k项由第k-2项+第k-1项构成。问第n项字符串的第c个字符是什么。（.）
/** 输入格式:两个整数n,c意义如题 输出格式:一个字符表示答案 样例1 输入：5 6 输出：I 备注：数据范围:0≤n ≤80,1≤c≤第n项字符串的长度 */ import java.util.Scanner; import java.util.*; class Main { static String a0 = "IAKIOI"; static String a1 = "WHENWILLSCORLLOFTAIWUCOMEOUT!!!"; static int len[] = new int[85]; static int n, c; // 运行部分通过，由于charAt(int)类型，传long无法取值 public static void ch(int n, int c){ if(n == 0){//百度没有找到怎么取长整形的字符串的字符，知道的朋友，望告知 System.out.printf("%c", a0.charAt(c - 1)); return; } if(n == 1){ System.out.printf("%c", a1.charAt(c - 1)); return; } //若取的字符c小于等于字符的前半截 if(c <= len[n - 2]){ ch(n-2, c); }else{//若取的字符c大于字符的前半截，c需要从后截0开始比较 ch(n-1, c - len[n - 2]); } } public static void main(String[] args) { Scanner input = new Scanner(System.in); // code here n = input.nextInt(); c = input.nextInt(); len[0] = a0.length(); len[1] = a1.length(); for(int i = 2; i <= n; i++){ len[i] = len[i - 2] + len[i - 1]; } ch(n, c); input.close(); } }
十、最大的平均值
题目：给一个数组，长度为n，找一个长度大于等于m的子区间，使这个区间的元素的平均值最大。（.）
/** 输入格式:第一行输入整数n和m，数据间用空格隔开;接下来n行，每行输入一个整数ai。 输出格式:输出一个整数，表示平均值的最大值乘以1000再向下取整之后得到的结果。 样例1 输入：10 6 6 4 2 10 3 8 5 9 4 1 输出：6500 备注：1<n≤100000,1 < m≤n,0≤ai≤1e7 */ // 只通过一个用例，调试没看不出来错哪了 import java.util.Scanner; import java.util.*; class Main { static int n, m; static double mid; static double a[] = new double[100000]; static double sum[] = new double[100000]; public static int check(double mid){ double minn = 0; for(int i = 1; i <= n; i++){ sum[i] = sum[i - 1] + a[i] - mid; } for(int i = m; i <= n; i++){ minn = minn > sum[i] ? sum[i] : minn; if(sum[i] >= minn){ return 1; } } return 0; } public static void main(String[] args) { Scanner input = new Scanner(System.in); // code here n = input.nextInt(); m = input.nextInt(); double l = 0, r = 0; for(int i = 1; i <= n; i++){ a[i] = input.nextInt(); r = r < a[i] ? a[i] : r; } while(r - l >= 0.001){ mid = (l + r) / 2; if(check(mid) >= 0){ l = mid; }else{ r = mid; } } System.out.printf("%d", (int)Math.floor(r * 1000)); input.close(); } }
十一、数列分隔
题目：小码哥给你一个长度为n的数列，求将该数列分割成两个左右两个部分且两个部分内数字的和相等的方案数。
/** 输入格式:给定一整数n ;接下来有n个数a[i]。其中: 1≤n≤105,a[i]的绝对值不大于10000。 输出格式:输出一行表示答案。 样例1 输入：9 1 5 -6 7 9 -16 0 -2 2 输出：3 */ import java.util.Scanner; import java.util.*; class Main { public static void main(String[] args) { Scanner input = new Scanner(System.in); // code here int n = input.nextInt(); int a[] = new int[100000]; int sum[] = new int[100000]; int num = 0; for(int i = 1; i <= n; i++){ a[i] = input.nextInt(); sum[i] = sum[i - 1] + a[i]; } for(int i = 2; i <= n; i++){//前缀和 if(sum[n] - sum[i - 1] == sum[i - 1]){ num++; } } System.out.printf("%d", num); input.close(); } }
记录每一个学习瞬间
