【每日一题】day2(好多基础题)
文章目录
1.奇数位上都是奇数，偶数位上都是偶数
给定一个长度不小于2的数组arr。 写一个函数调整arr，使arr中要么所有的偶数位上都是偶数，要么所有的奇数位上都是奇数上。
要求：如果数组长度为N，时间复杂度请达到O(N)，额外空间复杂度请达到O(1),下标0,2,4,6…算作偶数位,下标1,3,5,7…算作奇数位，例如[1,2,3,4]调整为[2,1,4,3]即可
本题解读： 本题很简单，就是在一个数组中，要把奇数位上的元素为奇数，或者要把偶数位上的元素为偶数。
本题解析： 设置m为偶数位，在数组中的起始下标为0，设置n为奇数位，在数组中的起始下标为1.遍历这个数组，如果在遍历数组元素的过程中，在奇数位上遇到了奇数，那么就n += 2,如果遇到了偶数那么就停止遍历，等到偶数位上的元素为奇数的时候，两个下标上的元素进行交换。
主要代码：
public static int[] func(int []array) {int m = 0;//偶数位int n = 1;//奇数位//奇数位下标和偶数位下标不能超过数组长度while (m < array.length && n < array.length) {if (array[m] % 2 == 0) { //偶数位上都是偶数 ，直到偶数位上遍历到了奇数之后停止m += 2;continue;}if (array[n] % 2 != 0) { //奇数位上都是奇数，直到奇数位上遍历到偶数的时候停止n += 2;continue;}//奇数位上的偶数和偶数位上的奇数进行交换int temp = array[m];array[m] = array[n];array[n] = temp;}return array;}
2.猴子分桃
题目描述：
老猴子辛苦了一辈子，给那群小猴子们留下了一笔巨大的财富——一大堆桃子。老猴子决定把这些桃子分给小猴子。
第一个猴子来了，它把桃子分成五堆，五堆一样多，但还多出一个。它把剩下的一个留给老猴子，自己拿走其中的一堆。
第二个猴子来了，它把桃子分成五堆，五堆一样多，但又多出一个。它把多出的一个留给老猴子，自己拿走其中的一堆。
后来的小猴子都如此照办。最后剩下的桃子全部留给老猴子。
这里有n只小猴子，请你写个程序计算一下在开始时至少有多少个桃子，以及最后老猴子最少能得到几个桃子。
输入描述:
输入包括多组测试数据。
每组测试数据包括一个整数n(1≤n≤20)。
输入以0结束，该行不做处理。
输出描述:
每组测试数据对应一行输出。
包括两个整数a，b。
分别代表开始时最小需要的桃子数，和结束后老猴子最少能得到的桃子数。
示例：
输入
输出
3121 1025
1 1
题目解读： 本题要求解的是在一开始至少有几个桃子，和老猴子最终能够得到几个桃子。
本题解法： 本题因为在原有的桃子总数中，桃子的个数分成5份之后，有余数，所以现在假设我们借给老猴子4个桃子，让能够完整的分成5份。
主要代码：
public static void func2(){Scanner scanner = new Scanner(System.in);while(scanner.hasNext()){int n = scanner.nextInt();//表示猴子的数目//原来桃子的总个数 x + 4 = 5 ^n x = 5 ^ n - 4//老猴子得到的桃子总数：剩下的桃子 + n - 4 剩下的桃子 (x + 4) * (4/5)^n//老侯子得到的桃子总数为： (5 ^ n - 4 + 4) * (4/5)^n + n - 4//为什么要加n，因为在每次分桃的时候，老猴子都会得到一个桃子，一共分了n次桃子，所以说分给老猴子了n个桃子，并且在分给//小猴子桃子时，把借来的4个桃子不分给小猴子，分给老猴子，最终老猴子的桃子总数减去4//化简之后：4^n + n - 4long x = (long)Math.pow(5,n) - 4;long y = (long)Math.pow(4,n) + n - 4;System.out.println(x + " " + y);}}
3.剪花布条
一块花布条，里面有些图案，另有一块直接可用的小饰条，里面也有一些图案。对于给定的花布条和小饰条，计算一下能从花布条中尽可能剪出几块小饰条来呢？
输入描述:
输入包含多组数据。
每组数据包含两个字符串s,t，分别是成对出现的花布条和小饰条，其布条都是用可见ASCII字符表示的，可见的ASCII字符有多少个，布条的花纹也有多少种花样。花纹条和小饰条不会超过1000个字符长。
输出描述:
对应每组输入，输出能从花纹布中剪出的最多小饰条个数，如果一块都没有，那就输出0，每个结果占一行。
示例1
输入
abcde a3
aaaaaa aa
输出
0
3
问题解析： 简单的说，题目中给出了两个字符串，s和t，问题要求解的是t字符串在字符串s中出现了多少次，如果我们在遍历长字符串的时候，没有遇到短的字符串t,那么直接返回0，如果遇到了那么count就进行加一，并且在原来的长字符串的基础上，删去在长字符串中第一次找到短字符串的末尾下标，之前的字符串。
图文解释：
主要代码：
import java.util.*;
public class Main{public static int cut(String s,String t){if(s.indexOf(t) == -1){return 0;}return cut(s.substring(t.length() + s.indexOf(t)),t) + 1;}public static void main(String []args){Scanner scanner = new Scanner(System.in);while(scanner.hasNext()){String s = scanner.next();String t = scanner.next();int ans = cut(s,t);System.out.println(ans);}}
}
4.变态跳台阶
一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。
题解：
主要代码：
public class Solution {public int jumpFloorII(int target) {if(target == 1 || target == 2){ //当台阶数为1时，直接输出1，当台阶时2时直接输出两种跳法return target;}else{return jumpFloorII(target-1) * 2; //推演公式} }
}5.快到碗里来
小喵们很喜欢把自己装进容器里的（例如碗），但是要是碗的周长比喵的身长还短，它们就进不去了。
现在告诉你它们的身长，和碗的半径，请判断一下能否到碗里去。
输入描述:
输入有多组数据。每组数据包含两个整数n (1≤n≤2^128) 和r (1≤r≤2^128)，分别代表喵的身长和碗的半径。圆周率使用3.14。
输出描述:
对应每一组数据，如果喵能装进碗里就输出“Yes”；否则输出“No”。
示例1
输入
6 1
7 1
9876543210 1234567890
输出
Yes
No
No
本题解析：虽然看起来此题非常的简单，但是往往就在细节上会绊倒一些人，在问题描述中n的范围在(1 ~ 2 ^ 128)，这个范围显然大于了int和long的范围。所以我们不得不使用类(Java在java.math包中提供的API类，用来对超过16位有效位的数进行精确的运算)
主要代码：
import java.util.*;
import java.math.*;
public class Main{public static void main(String []args){Scanner scanner = new Scanner(System.in);while(scanner.hasNext()){//猫的身长BigDecimal length = scanner.nextBigDecimal();//碗的半径BigDecimal r = scanner.nextBigDecimal();//有的周长 2 * 3.14 * r//BigDecimal类中的乘法运算使用multiply()方法BigDecimal num = new BigDecimal("6.28").multiply(r);//猫的身长和碗的周长比较使用compareTo9()方法，A.compareTo(B) 如果A大于B就返回1，如果A 等于 B 就返回0//如果A小于B就返回-1System.out.println(length.compareTo(num) == 1 ? "No" : "Yes");}}
}
6.最难的问题
生活在充满危险和阴谋的年代。为了生存，他首次发明了密码，用于军队的消息传递。假设你是军团中的一名军官，需要把发送来的消息破译出来、并提
供给你的将军。
消息加密的办法是：对消息原文中的每个字母，分别用该字母之后的第5个字母替换（例如：消息原文中的每个字母A 都分别替换成字母F），其他字符不 变，并且消息原文的所有字母都是大写的。密码中的字母与原文中的字母对应关系如下。
密码字母：A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
原文字母：V W X Y Z A B C D E F G H I J K L M N O P Q R S T U
输入描述:
输入包括多组数据，每组数据一行，为收到的密文。
密文仅有空格和大写字母组成。
输出描述:
对应每一组数据，输出解密后的明文
输入：HELLO WORLD
SNHJ
输出： CZGGJ RJMGY
NICE
问题解析： 这里的密文转成明文，就是把密文中大于’E’的字符减去5，把密文中小于等于’E’的字符加21 ，就得到了明文
在这里 E + 21 = Z F - 5 = A
主要代码：
import java.util.*;
public class Main{public static void main(String []args){Scanner scanner = new Scanner(System.in);while(scanner.hasNext()){String str = scanner.nextLine();//字符串拼接StringBuilder sb = new StringBuilder();//遍历字符串中的每个字符，如果遍历到了字符串中的空格字符，那么直接在sb//sb中添加，如果遍历到了大于字符E的字符，直接把字符-5，得到到的是一个int类型的//元素，把它强制转换成char类型,如果遍历到的字符小于字符'E'，那么就把这个字符+21for(int i = 0;i<str.length();i++){char ch = str.charAt(i);if(ch == ' '){sb.append(' ');}else{//强制类型转换sb.append((char)(ch > 'E' ? ch - 5 : ch + 21));}}System.out.println(sb);}}
}
7.分解因数
所谓因子分解，就是把给定的正整数a，分解成若干个素数的乘积，即 a = a1 × a2 × a3 × … × an,并且 1 < a1 ≤ a2 ≤ a3 ≤ … ≤ an。其中a1、a2、…、an均为素数。 先给出一个整数a，请输出分解后的因子。
输入描述:
输入包含多组数据，每组数据包含一个正整数a（2≤a≤1000000）。
输出描述:
对应每组数据，以“a = a1 * a2 * a3...”的形式输出因式分解后的结果。
示例1
输入
10
18
输出
10 = 2 * 5
18 = 2 * 3 * 3
问题解析： 本题和第8题类似，
主要代码：
import java.util.*;
import java.math.*;
public class Main{public static List<String> func(int num){List<String> list = new ArrayList<>();for(int i = 2;i <= Math.sqrt(num);i++){ //素数范围while(num % i == 0){//如果num 能被 i除尽 那么i就是num的一个因子list.add(String.valueOf(i));num = num / i;}}if(num > 1){ //如果num最终不等于1,那么num此时是一个素数list.add(String.valueOf(num));}return list;}public static void main(String []args){Scanner scanner = new Scanner(System.in);while(scanner.hasNext()){int num = scanner.nextInt();List<String>list = func(num);//注意输出格式，" * "是list元素直接的连接符System.out.printf("%d = %s\n",num,String.join(" * ",list));}}
}
8.因子的个数
一个正整数可以分解成一个或多个数组的积。例如36=223*3，即包含2和3两个因子。最近在研究因子个数的分布规律，现在给出一系列正整数，他希望你开发一个程序输出每个正整数的因子个数。
输入描述:
输入包括多组数据。
每组数据仅有一个整数n (2≤n≤100000)。
输出描述:
对应每个整数，输出其因子个数，每个结果占一行。
输入
30
26
20
输出
3
2
2
问题解析: 其实本题描述的有些含糊，它没有告诉我们，要得到的是的因子要为素数。那么我们就要在这个输入的这个元素之前的素数中找到，那些素数的乘积之和等于输入进来的这个元素。因为要求因子，并且这个因子是素数，所以说因子的范围在2~math.sqrt(num).
主要代码：
import java.util.*;
public class Main{public static void main(String []args){Scanner scanner = new Scanner(System.in);while(scanner.hasNext()){int num = scanner.nextInt();int count = 0;for(int i = 2;i<=Math.sqrt(num);i++){ //素数/因子的范围if(num % i == 0){ //如果在这里能被i整除，那么这个i就是num的一个因子，因为素数的定义时：一个数，只有1和他本身能把自身除尽。while(num % i == 0){ //如果在遍历的过程中，发现了能被整除的元素，那么就进行相除，并且进行更更新。直到不能被2~math.sqrt(num)中的元素整除时，那么这个元素就是一个素数num/=i;}count++;}}if(num != 1){ //如果最终num不等于1，那么说明此时的num依然是一个素数。count++;}System.out.println(count);}}
}
9.树根
数根可以通过逇把一个数的各个位上的数字加起来得到。如果得到的数是一位数，那么这个数就是数根；如果结果是两位数或者包括更多位的数字，那么再把这些数字加起来。如此进行下去，直到得到是一位数为止。
比如，对于24 来说，把2 和4 相加得到6，由于6 是一位数，因此6 是24 的数根。再比如39，把3 和9 加起来得到12，由于12 不是一位数，因此还得把1 和2 加起来，最后得到3，这是一个一位数，因此3 是39 的数根。现在给你一个正整数，输出它的数根。
输入描述:输入包含多组数据。每组数据数据包含一个正整数n（1≤n≤10E1000）。输出描述:对应每一组数据，输出该正整数的数根。输入：24 39输出： 6 3
本题解析： 本题就是描述的是 输入一个数字，只要这个数字是一位数，那么直接输出，如果输入进来的元素不是一位数，那么这个数就不是树根，那么就把这个数的每个数位上的数字加起来，如果多个数位相加之和小于10，这个和就是树根，如果相加之后，依然不是一位数，那么进行循环。另外在题目中的输入描述中输入一个正整数n (1~)，输入进来的元素大于int,long的访问，这里使用
解释： 24 --> 2 + 4 --> 6 6为一位数，为树根 39 --> 3+9 --> 12 --> 1 + 2 --> 3 3为树根
主要代码：
//树根问题//输入进来的数在1-10^1000次方之间，所以不能使用int long 类型，此处要使用String 类型public static void main(String[] args) {Scanner scanner = new Scanner(System.in);//循环输入while(scanner.hasNext()) {String str = scanner.nextLine();while(str.length() > 1) {int sum = 0;for (int i = 0; i < str.length(); i++) { //str = "39" sum += str.charAt(i) - '0'; //sum = '3' - '0' = 3 3 + '9' - '0' = 12}str = String.valueOf(sum);//整形元素转换为字符串}System.out.println(str);}}
10.三角形
任意输入三个正整数，判断这三个正整数对应的边长是否能围城一个三角形，如果可以返回Yes,如果不能返回No
题目分析：本题和第5题相似，都是输入进来的正整数过大，需要使用类，关于三角形的定义，三角形的任意两条边之和要大于第三边
主要代码：
public static void main(String[] args) {Scanner scanner = new Scanner(System.in);while(scanner.hasNext()){BigDecimal a = scanner.nextBigDecimal();BigDecimal b = scanner.nextBigDecimal();BigDecimal c = scanner.nextBigDecimal();//BigDecimal类中的加法运算使用add()方法if(a.add(b).compareTo(c) > 0 && a.add(c).compareTo(b) > 0 && b.add(a).compareTo(c) > 0){System.out.println("Yes");}else{System.out.println("No");}}}
11.有假币
居然有假币！ 现在猪肉涨了，但是农民的工资却不见涨啊，没钱怎么买猪肉啊。这就去买猪肉，结果找来的零钱中有假币！！！可惜 一不小心把它混进了一堆真币里面去了。只知道假币的重量比真币的质量要轻，给你一个天平（天平两端能容纳无限个硬币），请用最快的时间把那个可恶的假币找出来。
输入描述:
1≤n≤2^30,输入0结束程序。
输出描述:
最多要称几次一定能把那个假币找出来？
示例1
输入
3
12
0
输出
1
3
问题解析： 本题就是让我们通过最多多少步可以找到假钱，通过题目中的测试用例我们可以知道，当假币和真币混到一起时，一共有三张，输出描述为1步完成。我们可以逆推，如果我们把钱分为2堆，一堆2张，另一对1张，如果在2张的一堆中都是真币，另一堆中是一张假币，我们此时是分辨不出来，那边是真币，那边是假币的。因为假币的中重量轻。倘若一边是一真一假，另一边是真的。经过推演这样的比较之后，我们一步还是得不到那边是假币。但是如果我们分为3堆，现在一堆一张纸币，倘若在天平上称的两个都是真币，那么重量相等，那么我们就得到了另一堆就是假币。所以分为3堆的情况下，找出假钱是最快的。
主要代码：
import java.util.*;
public class Main{public static void main(String []args){Scanner scanner = new Scanner(System.in);while(scanner.hasNext()){int n = scanner.nextInt();if(n == 0){break;}int count = 0;while(n >= 2){n = (int)Math.ceil((double)n/3);count++;}System.out.println(count);}}
}
12.客似云来
开了一家早餐店，这家店的客人都有个奇怪的癖好：他们只要来这家店吃过一次早餐，就会每天都过来；并且，所有人在这家店吃了两天早餐后，接下来每天都会带一位新朋友一起来品尝。
于是，这家店的客人从最初一个人发展成浩浩荡荡成百上千人：1、1、2、3、5……
现在，想请你帮忙统计一下，某一段时间范围那他总共卖出多少份早餐（假设每位客人只吃一份早餐）。
输入描述:
测试数据包括多组。
每组数据包含两个整数from和to(1≤from≤to≤80)，分别代表开店的第from天和第to天。
输出描述:
对应每一组输入，输出从from到to这些天里（包含from和to两天），需要做多少份早餐。
题目解析： 其实该题就想让我们求解一段斐波那契数列的和。题目中描述的就是串斐波那契数列 1 1 2 3 5……
主要代码：
import java.util.*;
public class Main{public static void main(String[]args){long []fib = new long[80];fib[0] = 1;fib[1] = 1;for(int i = 2;i<80;i++){fib[i] = fib[i-1] + fib[i-2]; //斐波那契数列求解}//得到fib数列中的每一个元素Scanner scanner = new Scanner(System.in);while(scanner.hasNext()){int from = scanner.nextInt();int to = scanner.nextInt();long sum = 0;for(int i = from - 1;i<= to - 1;i++){sum+= fib[i];}System.out.println(sum);}}
}
