java常见编程练习hw一(入门、简单题型)

骑猪看日落 2022-10-24 03:04 312阅读 0赞

### 文章目录 ###

*   *  1. 二进制中1的个数
     *   *  思路1： 输入的整数与1做位与运算
         *  \[推荐掌握\]思路2：n&(n-1)
     *  2. 最小公倍数
     *   *  思路1： 最小公倍数 = 两数相乘/最大公约数
     *  3. 字符逆序
     *   *  思路1： StringBuilder.reverse方法
     *  4. 等差数列
     *   *  思路：数学思路，转化为等差数列求和，直接用公式计算求解
     *  5. 求最大连续bit数
     *   *  思路: 位运算，利用>>运算符，循环判断是否有连续的1。
         *  \[简单、推荐\]思路：先转换成二进制字符串，然后以“0”对其进行分割成字符串数组
     *  6. 最长回文子串（TODO）
     *  7. 字符串反转
     *   *  思路：利用 StringBuffer 或 StringBuilder 的 reverse 成员方法
         *  思路2： 利用 String 的 toCharArray 方法先将字符串转化为 char 类型数组，然后将各个字符进行重新拼接
     *  8. 数字颠倒
     *   *  【简单直接】思路：转换成字符串、然后直接利用StringBuilder 的 reverse 成员方法
     *  9. 表达式求值（TODO）
     *  10. 统计大写字母个数
     *   *  【该方法简单、推荐】思路1: 利用charAt取出单个字符判断 a >= 'A' && a <= 'Z'r
     *  11. 根据输入的日期，计算是这一年的第几天
     *   *  思路1
     *  尼科彻斯定理(TODO)
     *  统计每个月兔子的总数
     *   *  思路1: 兔子分为3类：1个月的兔子，2个月的兔子，以及>=3个月的兔子

## 1. 二进制中1的个数 ##

二进制中1的个数  
参考URL: https://blog.51cto.com/12951882/2044547

### 思路1： 输入的整数与1做位与运算 ###

首先我们应该判断整数二进制表中最右边的一位是不是1，接着把输入的整数右移一位，此时原来处于右边倒数第二为被移到最右边了，再判断是不是1,。这样每次移动一位，直到整个整数变成0为止。

思路1：我们把输入的整数与1做位与运算，如果一个整数与1做与运算结果是1，表示该整数最右边一位是1，否则是0.

虽然把整数右移一位和把整数除以2在数学上是等价的，但是因为除法的运算效率比移位运算要低的多，在实际应用中尽可能低运用移位运算代替乘除法运算。

public static void main(String[] arg) { 
            Scanner sc = new Scanner(System.in);
            int num = sc.nextInt();
    
            int count = 0;
            while (num > 0) { 
                if ((num & 1) == 1) { 
                    ++count;
                }
                num >>= 1;
            }
            System.out.println(count);
        }

**应用这种方法有可能会导致死循环，如果输入一个负数，最高位为1，移位前是个负数，仍要保证移位后也是负数，因此移位后的最高为会设为1.如果一直做右移运算，最终会变为0xfffff而陷入死循环。**

如果输入的正整数可以，可以用这个方法。

### \[推荐掌握\]思路2：n&(n-1) ###

时间复杂度  O ( log ⁡ M ) O(\\log\_\{\}\{M\} ) O(logM) ，其中 M 表示 1 的个数。

思路： 一个数与该数减一的结果进行与运算n&(n-1)，会把该数右边（低位）第一个1变为0，而该位左边保持不变（高位）

> n&(n-1)作用：将n的二进制表示中的最低位为1的改为0.

例子：比如1100（对应十进制是12），减去1之后的结果是1011（也就是十进制的11），两个数进行与运算之后，我们发现最后的结果是1000（对应十进制的8，当然这个8与后面没有关系，可以略过）。这样我们每进行一次的与运算就消去一个1，这样消到最后肯定是0了，所以我们可以在代码中以这个为循环的终止条件。

public static void main(String[] args) { 
            Scanner scanner = new Scanner(System.in);
            int n = scanner.nextInt();
            int count = 0;
            while(n != 0) { 
                count ++;
                n = n & (n - 1);
            }
            System.out.println(count);
            scanner.close();
        }

## 2. 最小公倍数 ##

最小公倍数(Least Common Multiple(LCM))  
参考URL: https://www.cnblogs.com/echoing/p/7878954.html  
算法笔记\_042:求最小公倍数（Java）  
参考URL: https://www.cnblogs.com/liuzhen1995/p/6423600.html

正整数A和正整数B 的最小公倍数是指 能被A和B整除的最小的正整数值，设计一个算法，求输入A和B的最小 公倍数。

两个或多个整数公有的倍数叫做它们的公倍数，其中除0以外最小的一个公倍数就叫做这几个整数的最小公倍数。整数a，b的最小公倍数记为\[a，b\]，同样的，a，b，c的最小公倍数记为\[a，b，c\]，多个整数的最小公倍数也有同样的记号。

与最小公倍数相对应的概念是最大公约数，a，b的最大公约数记为（a，b）。关于最小公倍数与最大公约数，我们有这样的定理：(a,b)\[a,b\]=ab(a,b均为整数)

### 思路1： 最小公倍数 = 两数相乘/最大公约数 ###

求最大公约数有两种方法 更相减损法和辗转相处法 最小公倍数在求出最大公约数后 两个数相乘除以最大公约数就是最小公倍数

更相减损法:

> 更相减损法是拿两个数中的较大值减去较小值，然后在减数、被减数、差之间选取两个较小值继续相减，直到减数和被减数相等，得出的数就是最大公约数。

例：//更相减损术：  
//8 10  
//10 - 8=2  
//8 - 2= 6  
//6-2=4  
//4-2=2  
//2==2于是最大公约数就是2

public static void main(String[] args){ 
            Scanner scanner = new Scanner(System.in);
            
            int int1 = scanner.nextInt();
            int int2 = scanner.nextInt();
            
            System.out.println( int1*int2/methods(int1,int2));
            
        }
        
        public static int methods(int int1, int int2){ 
            if(int1 == int2){ 
                return int1;
            } 
            
            if(int1 > int2){ 
                int differ = int1 - int2;
                return methods(int2,differ);
            }else{ 
                int differ = int2- int1;
                return methods(int1,differ);
            }
            
            
        }

## 3. 字符逆序 ##

将一个字符串str的内容颠倒过来，并输出。str的长度不超过100个字符。

输入描述:  
输入一个字符串，可以有空格

输出描述:  
输出逆序的字符串

### 思路1： StringBuilder.reverse方法 ###

import java.util.*;
     
    public class Main { 
     
        public static String reverse(String str) { 
            StringBuilder res = new StringBuilder(str);
            return res.reverse().toString();
        }
    
        public static void main(String[] args){ 
            
            Scanner in = new Scanner(System.in);
            while (in.hasNextLine()) { 
                String str = in.nextLine();
                String res = reverse(str);
                System.out.println(res);
            }
        }
    }

## 4. 等差数列 ##

题目描述  
功能:等差数列 2，5，8，11，14。。。。

输入:正整数N >0

输出:求等差数列前N项和

本题为多组输入，请使用while(cin>>)等形式读取数据

输入描述:  
输入一个正整数。

输出描述:  
输出一个相加后的整数。

示例1  
输入 2  
输出 7

### 思路：数学思路，转化为等差数列求和，直接用公式计算求解 ###

等差数列基础：  
等差数列是常见数列的一种，可以用AP表示，如果一个数列从第二项起，每一项与它的前一项的差等于同一个常数，这个数列就叫做等差数列，而这个常数叫做等差数列的公差，公差常用字母d表示 \[1\] 。例如：1,3,5,7,9……（2n-1)。

等差数列\{an\}的通项公式为：an=a1+(n-1)d。  
前n项和公式为：Sn=n\*a1+n(n-1)d/2或Sn=n(a1+an)/2 。注意： 以上整数。

思路：等差数列求和公式  
前n项和:Sn = （a1 + an）\*n/2  
第n项： an = a1 + (n - 1) \* 3(公差);

根据题目中的 具体的 a1 和 n  
把 a1 和 n 代进去，计算出来格式题目中 Sn = (1 + 3 \* n) \* n / 2

import java.util.Scanner;
     
    public class Main{ 
     
        public static void main(String[] args){ 
            Scanner sc = new Scanner(System.in);
            while(sc.hasNext()){ 
                int n = sc.nextInt();
                System.out.println((1 + 3 * n) * n / 2);
            }
        }
    }

## 5. 求最大连续bit数 ##

题目描述  
求一个byte数字对应的二进制数字中1的最大连续数，例如3的二进制为00000011，最大连续2个1

本题含有多组样例输入。

输入描述:  
输入一个byte数字

输出描述:  
输出转成二进制之后连续1的个数

示例1  
输入 3  
输出 5

### 思路: 位运算，利用>>运算符，循环判断是否有连续的1。 ###

求一个byte数字对应的二进制数字中1的最大连续数  
参考URL: https://www.it610.com/article/1297183224455307264.htm

根据位运算，获取每一位的二进制值。获取第i位的值： (n >> i) & 1。如果1连续，则计数累加， 如果不连续，则从0开始计数。

总结： 一边右移一边统计，不断更新count和max。

### \[简单、推荐\]思路：先转换成二进制字符串，然后以“0”对其进行分割成字符串数组 ###

思路是先转换成二进制字符串，然后以“0”对其进行分割成字符串数组，  
求数组中每项长度的最大值即为最大连续1的个数。

public static void main(String[] args) { 
            Scanner sc = new Scanner(System.in);
            while (sc.hasNext()) { 
                int in1 = sc.nextInt();
                int max = 0;
                String str = Integer.toBinaryString(in1);
                String[] stra = str.split("0");
                for (int i = 0; i < stra.length; i++) { 
                    max = max < stra[i].length() ? stra[i].length() : max;
                }
    
                System.out.println(max);
            }
    
        }

## 6. 最长回文子串（TODO） ##

最简便的找字符串中最长回文子串的方法是什么？  
参考URL: https://www.zhihu.com/question/40965749  
最长回文子串（Java版本）  
参考URL: https://blog.csdn.net/tiankong\_12345/article/details/102018257  
Java算法练习——最长回文子串  
参考URL: https://www.cnblogs.com/mxwbq/p/10938952.html

给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。

## 7. 字符串反转 ##

接受一个只包含小写字母的字符串，然后输出该字符串反转后的字符串。（字符串长度不超过1000）

输入描述:  
输入一行，为一个只包含小写字母的字符串。

输出描述:  
输出该字符串反转后的字符串。

示例1  
输入 abcd  
输出 dcba

### 思路：利用 StringBuffer 或 StringBuilder 的 reverse 成员方法 ###

Java实现字符串反转  
参考URL: https://www.cnblogs.com/binye-typing/p/9260994.html

import java.util.*;
    public class Main{ 
        public static void main(String[] args){ 
            Scanner sc=new Scanner(System.in);
            while(sc.hasNext()){ 
                String s=sc.next();
                StringBuffer sb = new StringBuffer(s);
                System.out.println(sb.reverse().toString()); 
                
            }
        }
    }

### 思路2： 利用 String 的 toCharArray 方法先将字符串转化为 char 类型数组，然后将各个字符进行重新拼接 ###

Java实现字符串反转  
参考URL: https://www.cnblogs.com/binye-typing/p/9260994.html

import java.util.*;
    public class Main{ 
        public static void main(String[] args){ 
            Scanner sc=new Scanner(System.in);
            while(sc.hasNext()){ 
                String s=sc.next();
                char[] chars = s.toCharArray();
                String reverse = "";
                for(int i = chars.length - 1; i >= 0; i--){ 
                    reverse += chars[i];
                }
                
                System.out.println(reverse); 
                
            }
        }
    }

## 8. 数字颠倒 ##

题目描述  
输入一个整数，将这个整数以字符串的形式逆序输出  
程序不考虑负数的情况，若数字含有0，则逆序形式也含有0，如输入为100，则输出为001

### 【简单直接】思路：转换成字符串、然后直接利用StringBuilder 的 reverse 成员方法 ###

import java.util.Scanner;
     
    public class Main { 
        public static void main(String[] args) { 
            Scanner in = new Scanner(System.in);
            
            while (in.hasNextInt()) { 
                int a = in.nextInt();
                String b = String.valueOf(a);
                StringBuffer sb = new StringBuffer(b);
                
                System.out.println(sb.reverse().toString());
            }
        }
    }

## 9. 表达式求值（TODO） ##

牛客网：表达式求值(Java实现)  
参考URL: https://blog.csdn.net/u013053615/article/details/94380525

题目描述  
给定一个字符串描述的算术表达式，计算出结果值。

输入字符串长度不超过100，合法的字符包括”+, -, \*, /, (, )”，”0-9”，字符串内容的合法性及表达式语法的合法性由做题者检查。本题目只涉及整型计算。

输入  
400+5

输出  
405

## 10. 统计大写字母个数 ##

题目描述  
找出给定字符串中大写字符(即’A’-‘Z’)的个数。

### 【该方法简单、推荐】思路1: 利用charAt取出单个字符判断 a >= ‘A’ && a <= 'Z’r ###

public static void main(String[] args) { 
            Scanner in = new Scanner(System.in);
            while (in.hasNext()) { 
               
                String str = in.nextLine();
                int count = 0;
                for(int i=0; i<str.length();i++){ 
                    char a = str.charAt(i);
                    if(a >= 'A' && a <= 'Z'){ 
                        ++count;
                    }
                }
                System.out.println(count);
            }
    
        }

注意：使用nextLine() 输入用例里面有 空格的字符串。

## 11. 根据输入的日期，计算是这一年的第几天 ##

思路比较简单, 从这一年的开始一直加到这一天, 注意闰年二月是29天

注意: 闰年的二月份的天数为29天，如果日期是闰年且月份大于二月时，需要考虑加一天。

### 思路1 ###

Java篇—根据输入的日期（年月日），输出这一年的第几天  
参考URL: https://blog.csdn.net/weixin\_43761659/article/details/96889620

step 1：判断输入日期的合法性，如果输入不合法返回-1；

step 2：根据输入的月份，计算从1月到（month - 1）月的天数，如果是二月的话，就要判断该年是否为闰年（闰年，day加29天，反之，day加28天）；

step 3：根据步骤二计算出来的数值，最后加上输入的date，输出即可。

题目总结：题目的关键点在于二月的天数累加，即闰年判断。  
易错点分析：在for循环结束之后，还要加上之前输入的date。

public static void main(String [] args){ 
            Scanner sc = new Scanner(System.in);
            while (sc.hasNext()) { 
                int year = sc.nextInt();
                int month = sc.nextInt();
                int date = sc.nextInt();
                int day = 0;
                if (year <=0 || month <= 0 || month > 12 || date <= 0 || date > 31){ 
                    System.out.println(-1);
                    break;
                }
                for(int i=1; i<month; i++) { 
                    if(i==1 || i==3 || i==5 || i==7 || i==8 || i==10 || i==12) { 
                        day += 31;
                    } else if(i==4 || i==6 || i==9 || i==11) { 
                        day += 30;
                    } else if(i==2 && (year%400==0 || (year%4==0 && year%100!=0))) { 
                        day += 29;
                    } else { 
                        day += 28;
                    }
                }
                day += date;
                System.out.println(day);
            }
            sc.close();
        }

## 尼科彻斯定理(TODO) ##

题目描述  
验证尼科彻斯定理，即：任何一个整数m的立方都可以写成m个连续奇数之和。

例如：

1^3=1

2^3=3+5

3^3=7+9+11

4^3=13+15+17+19

输入一个正整数m（m≤100），将m的立方写成m个连续奇数之和的形式输出。

输入描述:  
输入一个int整数

输出描述:  
输出分解后的string

## 统计每个月兔子的总数 ##

有一只兔子，从出生后**第3个月起**每个月都生一只兔子，小兔子长到第三个月后每个月又生一只兔子，假如兔子都不死，问每个月的兔子总数为多少？

①兔子的初始数：一只刚出生的兔子  
②兔子到第三个月的时候，就开始生兔宝宝，**不是要等完全满**3个月才生。

### 思路1: 兔子分为3类：1个月的兔子，2个月的兔子，以及>=3个月的兔子 ###

所以只需要求出每个月这三类兔子的数目即可  
根据题意可知兔子分为3类：1个月的兔子，2个月的兔子，以及>=3个月的兔子  
所以只需要求出每个月这三类兔子的数目即可！  
一个月大的兔子书数量 = 能生的兔子生的兔子数量

*  能生的兔子数量=前一个月能生的数量+前一个月是两个月大的兔子数量
 *  两个月大的兔子数量 = 前一个月一个月大兔子数量
 *  一个月大的兔子书数量 = 能生的兔子生的兔子数量

import java.util.Scanner;
    
    public class Main { 
        public static void main(String[] args) { 
            Scanner in =new Scanner(System.in);
            while(in.hasNext()){ 
                int month=in.nextInt();
                
                int nengsheng = 0;// 能生的兔子数量（三个月大）
    			int yigeyueda = 1;// 一个月大的兔子数量
    			int lianggeyueda = 0;// 两个月大的兔子数量
    			int sum = 0;// 每个月的兔子数量总和
     
    			for (int i = 1; i < month; i++) { 
     
    				nengsheng += lianggeyueda;// 能生的兔子数量=前一个月能生的数量+前一个月是两个月大的兔子数量
    				lianggeyueda = yigeyueda;// 两个月大的兔子数量 = 前一个月一个月大兔子数量
    				yigeyueda = nengsheng;// 一个月大的兔子书数量 = 能生的兔子生的兔子数量
    				sum = nengsheng + yigeyueda + lianggeyueda;// 总数量
     
    			}
                System.out.println(sum);
            }
            in.close();
        }
    
    }