HW机试题目练习
1. 入门
1. 求int型正整数在内存中存储时1的个数
题目描述:
输入一个int型的正整数，计算出该int型数据在内存中存储时1的个数。
输入: 输入一个整数（int类型）
输出: 这个数转换成2进制后，输出1的个数
示例： 5 得到 2
解法一：
正整数转换成二进制，每次整除2，直到商为0，每次得到的余数(0或者1)组合起来就是它的二进制
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int count = 0;
while(sc.hasNextInt()){
int input = sc.nextInt();
while(input!=0){
// input%2是余数
count = count + input%2;
// input/2是商
input = input >> 1;
// input = input/2;
// 用移位操作代替除法
}
// Ouput
System.out.println(count);
}
}
} 解法二:
在位操作中，数字自动是按照二进制运算的。
例如7表示为0111
n&(n-1) 即（0111）&（0110）== 0110 就是 n去除了最后一个1 ；
几个1 就可以在几次内 去除几个1；
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
int count = 0;
while(sc.hasNextInt()){
int input = sc.nextInt();
while(input!=0){
input = input & (input-1);
count++;
}
}
// Ouput
System.out.println(count);
}
} 2. 近似值
题目描述:
写出一个程序，接受一个正浮点数值，输出该数值的近似整数值。如果小数点后数值大于等于5,向上取整；小于5，则向下取整。
输入：输入一个正浮点数值
输出：输出该数值的近似整数值
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNextDouble()){
double input = sc.nextDouble();
// java 的数据强制转换，是同意向下取整
System.out.println( (int)(input+0.5) );
}
}
} 2. 简单
1. 棋盘路径
题目描述:
请编写一个函数（允许增加子函数），计算n x m的棋盘格子（n为横向的格子数，m为竖向的格子数）沿着各自边缘线从左上角走到右下角，总共有多少种走法，要求不能走回头路，即：只能往右和往下走，不能往左和往上走。
输入描述: 输入两个正整数
输出描述: 返回结果
解法: 考虑棋盘的走法，从起点出发到达终点，无论走何种路线都要走(m+n)步且经过(m+n)个交叉路口决定走的方向，其中m步向下，n步向右。
数学中的组合可以解决这个问题，一共(m+n)次决定，其中任意选择m次向下走，其余的n次必然向右走，一共有 种走法, 公式计算为
import java.util.Scanner;
public class Main{
public static int factorial(int num){
if(num==0 || num==1){
return num;
}
int res = 1;
while(num!=0){
res = res * num;
num--;
}
return res;
}
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
while(sc.hasNextInt()){
int n = sc.nextInt();
int m = sc.nextInt();
int res = factorial(n+m)/(factorial(m)*factorial(n));
System.out.println(res);
}
}
} 2. 字符串逆序
题目描述:
将一个字符串str的内容颠倒过来，并输出。str的长度不超过100个字符。 如：输入“I am a student”，输出“tneduts a ma I”。
解法: 题目本身很简单，但是我这个菜鸡在学习别人的解法时发现了很多java的语法知识点，特此记录，string与stringBuilder的区别
解法一: String 转成 char array 再逆序, 缺点: 数组越界，菜
import java.util.Scanner;
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
char[] str = sc.nextLine().toCharArray();
char[] rev = new char[str.length];
for(int i=0; i<str.length; i++){
rev[i] = str[str.length-i-1];
}
for(int i=0; i<str.length; i++){
System.out.print(rev[i]);
}
}
} 解法二: 直接用StringBuilder的reverse()方法
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();//next()是遇到空格；nextLine()是遇到回车
StringBuilder sb = new StringBuilder(str);
System.out.println(sb.reverse());
} 解法三: 改进解法一
public class Main{
public static void main(String[] args){
Scanner sc = new Scanner(System.in);
String str = sc.nextLine();//next()是遇到空格；nextLine()是遇到回车
StringBuilder sb = new StringBuilder();
for(int i=0; i<str.length(); i++){
sb.append(str.charAt(str.length()-i-1));
}
System.out.println(sb);
}
} 解法四: 用栈的逆序性质；
解法五: toCharArray，再逆序输出
3. 输入字符串的四则运算
快速解法:
//😄 😄 print(eval(input()))
// 用javascript里面内置的eval函数做
import javax.script.ScriptEngine;
import javax.script.ScriptEngineManager;
import javax.script.ScriptException;
import java.util.Scanner;
public class Main
{
public static void main(String args[]) {
String enter;
Scanner in = new Scanner(System.in);
while (in.hasNextLine()){
enter = in.nextLine();
ScriptEngineManager manager = new ScriptEngineManager();
ScriptEngine engine = manager.getEngineByName("js");
try {
Object result = engine.eval(enter);
System.out.println(result);
} catch (ScriptException e) {
e.printStackTrace();
}
}
}
} a) 括号匹配
参考力扣第20题解析
题目描述:
保证输入字符串中的括号'('，')'，'{'，'}'，'['，']'是否有效。也就是说,
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
题目解析:
- 栈先入后出特点恰好与本题括号排序特点一致，即若遇到左括号入栈，遇到右括号时将对应栈顶左括号出栈，则遍历完所有括号后 stack 仍然为空；
- 建立哈希表 dic 构建左右括号对应关系：key左括号，value右括号；这样查询 22 个括号是否对应只需 O(1) 时间复杂度；
- 建立栈 stack，遍历字符串 s 并按照算法流程一一判断。
算法流程:
- 先判断当前字符是括号么
- 如果 c 是左括号，则入栈 pushpush；
- 否则通过哈希表判断括号对应关系，若 stack 栈顶出栈括号
stack.pop()与当前遍历括号c不对应，则提前返回false。
public static boolean isValid(String s) {
// 建立哈希表
HashMap<Character, Character> myMap = new HashMap<Character, Character>();
myMap.put('(', ')');
myMap.put('{', '}');
myMap.put('[', ']');
HashSet<Character> charSet = new HashSet<>();
charSet.add('(');
charSet.add(')');
charSet.add('[');
charSet.add(']');
charSet.add('{');
charSet.add('}');
// 利用辅助栈
LinkedList<Character> myStack = new LinkedList<>();
// 遍历字符串
for(int i=0; i<s.length(); i++){
// 当前字符
char c = s.charAt(i);
// 判断是否是括号集合里面的元素
// 非括号元素
if (charSet.contains(c)){
// 判断当前字符是否是开括号，如果是则入栈
// 如果闭括号，则判断此时栈是否为空，若为空则返回false
// 若不为空，则判断弹出字符是否是开括号所对应的闭括号
if(myMap.containsKey(c)){
myStack.addLast(c);
}else{
if(myStack.isEmpty() || myMap.get(myStack.removeLast())!=c){
return false;
}
}
}else continue;
}
return myStack.isEmpty();
} b) 逆波兰表达式
平时我们习惯将表达式写成 (1 + 2) * (3 + 4)，加减乘除等运算符写在中间，因此称呼为中缀表达式。
而波兰表达式的写法为 (* (+ 1 2) (+ 3 4))，将运算符写在前面，因而也称为前缀表达式。
逆波兰表达式的写法为 ((1 2 +) (3 4 +) *)，将运算符写在后面，因而也称为后缀表达式。
波兰表达式和逆波兰表达式有个好处，就算将圆括号去掉也没有歧义。逆波兰表达式去掉圆括号，变成 1 2 + 3 4 + * 也是无歧义并可以计算的。
如何把中缀表达式转换成后缀表达式，以后有时间再写,参考资料1 和 资料2，先重要的是解决如何把后缀表达式变成数学表达式输出结果:
输入表达式: "3", "4", "+", "5", "*","6","-", 得到(3+4)*5-6=29
思路:
遍历每一个字符，如果是数字就入栈，如果是运算符，就出栈两个数***算，结果再入栈
/*
* 定义一个后缀表达式计算器
* @ parameter:
* List<String> notation -> 包含操作数和运算符的list
* @ return
* int result -> 后缀表达式，逆波兰表达式所得到的结果
*/
public static int suffixCalculator(String[] notation) {
// 计算思路:
// 1. 定义一个栈，用来存储操作数
if (notation == null){
return -1;
}
LinkedList<String> stack = new LinkedList<>();
// 2. 从左向右遍历每个字符
for (String elem : notation){
// 3. 判断当前字符是操作数还是运算符
if (elem.matches("\\d+")){ // 匹配多位数，其中第一个/是转义字符,/d是0-9数字，/d+是多位数
// 4. 操作数，则压入栈中
stack.addLast(elem);
//System.out.println("压入数字: " + elem);
}else {
// 5. 运算符, 则从栈中弹出两个操作数，运算完后再放入栈
int num2 = Integer.parseInt(stack.removeLast());
int num1 = Integer.parseInt(stack.removeLast());
int result = 0;
if(elem.equals("+")){
result = num1 + num2;
} else if (elem.equals("-")){
result = num1 - num2;
} else if (elem.equals("*")){
result = num1 * num2;
} else if (elem.equals("/")){
result = num1 / num2;
} else {
throw new RuntimeException("非法输入操作符");
}
stack.addLast(valueOf(result));
}
// 6. 得到栈中最后一个元素，就是最后的结果
}
return Integer.parseInt(stack.removeLast());
} 4. 杨辉三角变形
题目描述:
1
1 1 1
1 2 3 2 1
1 3 6 7 6 3 1
1 4 10 16 19 16 10 4 1
以上三角形的数阵，第一行只有一个数1，以下每行的每个数，是恰好是它上面的数，左上角数到右上角的数，3个数之和（如果不存在某个数，认为该数就是0）。
求第n行第一个偶数出现的位置。如果没有偶数，则输出-1。例如输入3,则输出2，输入4则输出3。
解法一: 观察法
/* 本题观察数据有规律可循
1
1 1 1
1 2 3 2 1
1 3 6 7 6 3 1
1 4 10 16 19 16 10 4 1
1 5 15 30 45 51 45 30 15 5 1
1 6 21 50 90 126 141 126 90 50 21 6 1
1 7 28 77 161 266 357 393
1 8 36 112
1 9 45 156
*/
public static int ruler(int row) {
//当n<3时，没有偶数，输出-1
//当n为偶数且能被4整除时，第一个偶数位置在第三，输出3
//当n为偶数但不能被4整除时，偶数位置在第四，输出4
//当n为奇数时，第一个偶数位置在第二，输出2
if(row < 3){
return -1;
}else if (row % 2 == 1) {
return 2;
} else if (row % 4 == 0) {
return 3;
} else {
return 4;
}
} 解法二: 构造三角矩阵
利用当前数字等于上三个数字的和，可以迭代算出答案;
注意边界条件，导致遍历从1开始到i-2结束
public static int constructionTriangle(int row){
// 用一个矩阵来表示杨辉三角，n行会有 2*n-1列
int col = 2*row-1;
int[][] matrix = new int[row][col];
// 每一行代表一个杨辉三角行，第一行在最中间有一个1，其他都是0，1的位置在[0][row-1]
matrix[0][row-1] = 1;
// 构造每一行的值，注意为了边界问题，遍历每一行时
// 下标从1开始遍历到倒数第二结束，最后一行的开头和结尾补1
for(int i=1; i<row; i++){
for (int j=1; j<col-1; j++){
matrix[i][j] = matrix[i-1][j-1] + matrix[i-1][j] + matrix[i-1][j+1];
}
}
// 补1, 最后一行没有计算
matrix[row-1][0] = matrix[row-1][col-1] = 1;
// 找到最后一行的第一个偶数位
int evenIndex = -1;
for(int i=0; i<col; i++){
if (matrix[row-1][i] % 2 == 0 && matrix[row-1][i]!=0){
evenIndex = i+1;
break;
}
}
// 若没有找到，自动返回-1
return evenIndex;
} 5. 最小公倍数
解法:
最小公倍数 = a*b / 最大公约数(a,b)
最大公约数用辗转相除法得到，
- a%b得余数c
- 若c=0，则b即为两数的最大公约数
- 若c≠0，则a=b，b=c，再回去执行(1)
public static int getGCD (int a, int b){
// 自动交换 a， b
int mod = 1;
while (mod != 0){
mod = a % b;
if (mod == 0){
break;
}
a = b;
b = mod;
}
return b;
// 递归版本;
//return a%b==0 ? b:getGCD(b, a%b);
}
// 最小公倍数 = x * y / 最大公约数(x,y)
public static int getLCM (int a, int b){
return a*b/getGCD(a,b);
} 3.字符串问题集合
计算整数二进制中1的个数
解法：输入整数变成二进制字符串，再遍历统计'1'的个数
int num = sc.nextInt();
String binaryStr = Integer.toBinaryString(num);
char[] charArr = binaryStr.toCharArray();
int count = 0;
for(char cur : charArr){
if (cur == '1'){
count++;
}
} 大写字符(即'A'-'Z')的个数
解法: 遍历字符检查
public static int getCaptialNumber (String str){
int count = 0;
char[] charArr = str.toCharArray();
for(char cur : charArr){
if(cur>='A' && cur<='Z'){
count++;
}
}
return count;
} 参数解析
NR. HJ 74
请编写一个参数解析程序，实现将命令行各个参数解析出来。
解析规则：
1.参数分隔符为空格
2.对于用“”包含起来的参数，如果中间有空格，不能解析为多个参数。比如在命令行输入xcopy /s “C:\program files” “d:\”时，参数仍然是4个，第3个参数应该是字符串C:\program files，而不是C:\program，注意输出参数时，需要将“”去掉，引号不存在嵌套情况。
3.参数不定长
4.输入由用例保证，不会出现不符合要求的输入
题意理解就是，输入的参数可以按照空格将字符串分割，但是带引号的字符串不是以空格为分隔符而是成对的引号，比如说:
输入字符串是 xcopy /s “C:\program files” “d:\”
按照空格分割就是:
xcopy
/s
“C:\program
files”
“d:\”
但实际题目想要的是:
xcopy
/s
“C:\program files”
“d:\”
解题思路：先用空格将字符串分割，在逐个便利每个，统计其中引号的数量:
- 如果有两个引号，就把引号去除直接加入答案容器中
- 如果有一个引号，则设置一个temp字符串，一致遍历到下一个引号为1的字符串，一起连起来
- 如果没有引号，直接加入答案容器中
public static LinkedList<String> inputParsing(String input){
// 先把字符串按照空格分割
String[] strings = input.split(" ");
// 答案容器
LinkedList<String> res = new LinkedList<>();
// 遍历每个字符串，按照引号的数量处理
int index = 0;
while (index < strings.length){
// 分割的字符包含完整的引号，则直接加入list中
if (stringCount(strings[index]) == 2){
res.add(strings[index].replace("\"", ""));
index += 1;
}else if (stringCount(strings[index]) == 1){
// 只包含一个引号，需要遍历寻找，直到下一个引号也为一个
StringBuilder temp = new StringBuilder(strings[index]);
for (int j = index + 1; j < strings.length; j++){
if (stringCount(strings[j]) == 1){
temp.append(" ");
temp.append(strings[j]);
// 注意这里是j+1，如果是j则就是死循环
index = j+1;
break;
}else {
temp.append(" ");
temp.append(strings[j]);
}
}
res.add(temp.toString().replace("\"", ""));
}else { // 包含零个引号，直接加入
res.add(strings[index]);
index += 1;
}
}
return res;
}
// 统计字符串中引号的个数，并返回数量
public static int stringCount(String str){
int num = 0;
for (char character : str.toCharArray()){
if (character == '\"'){
num += 1;
}
}
return num;
} 日期到天数转换
Nr. HJ 73
详细描述：
输入某年某月某日，判断这一天是这一年的第几天？
示例1
输入
2012 12 31
输出
366
解题思路:
首先要判断输入的年份是否合法，考虑年月日的合法性，和2月在闰年和非闰年是否合法。接下来就是计算天数，公式就是month*当月天数累加再加上最后一个月的day。
判断闰年的方法参考热心网友admin-root
闰年是公历中的名词。闰年分为普通闰年和世纪闰年。
普通闰年: 公历年份是4的倍数的，且不是100的倍数，为普通闰年。（如2004年就是闰年）；
世纪闰年: 公历年份是整百数的，必须是400的倍数才是世纪闰年。(如1900年不是世纪闰年，2000年是世纪闰年)
// days[0] 是非闰年，days[1] 是闰年
// 1 2 3 4 5 6 7 8 9 10 11 12
private static final int[][] days = {{0, 31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31},
{0, 31, 29, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31}};
public static boolean isLeapYear(int year){
// 闰年分世纪闰年和普通闰年
// 世纪闰年：能被400整除的年份
// 普通闰年：能被4整除但不能被400整除
if (year % 400 == 0){
return true;
}else if ((year%100 != 0 && year%4 == 0)){
return true;
}else {
return false;
}
}
public static boolean isValidDate(int year, int month, int day){
// 不符合规定就是：
if (year<0 || month<0 || month>12 || day<0 || day>31){
return false;
}
// 检查特定月份的天数是否符合规定
if (isLeapYear(year)){ // 闰年
if (day > days[1][month]){
return false;
}
}else{ // 非闰年
if (day > days[0][month]){
return false;
}
}
return true;
}
public static int getDays(String str){
// 清洗数据
String[] inputs = str.trim().split(" ");
if (inputs.length != 3){
return -1;
}
int year = Integer.parseInt(inputs[0]);
int month = Integer.parseInt(inputs[1]);
int day = Integer.parseInt(inputs[2]);
// 判断数据是否合法
if (!isValidDate(year, month, day)){
return -1;
}
// 判断是否是闰年
if (isLeapYear(year)){
int dayOfMonth = 0;
for (int i = 1; i < month; i++){
dayOfMonth += days[1][i];
}
return day + dayOfMonth;
}else{
int dayOfMonth = 0;
for (int i = 1; i < month; i++){
dayOfMonth += days[0][i];
}
return day + dayOfMonth;
}
} 4.动态规划
放苹果
解法参考牛客网友，没看懂--
设f(m,n) 为m个苹果，n个盘子的放法数目，则先对n作讨论，
当n>m：必定有n-m个盘子永远空着，去掉它们对摆放苹果方法数目不产生影响。即if(n>m) f(m,n) = f(m,m)
当n<=m：不同的放法可以分成两类：
1、有至少一个盘子空着，即相当于f(m,n) = f(m,n-1);
2、所有盘子都有苹果，相当于可以从每个盘子中拿掉一个苹果，不影响不同放法的数目，即f(m,n) = f(m-n,n).
而总的放苹果的放法数目等于两者的和，即 f(m,n) =f(m,n-1)+f(m-n,n)
递归出口条件说明：
当n=1时，所有苹果都必须放在一个盘子里，所以返回１；
当没有苹果可放时，定义为１种放法；
递归的两条路，第一条n会逐渐减少，终会到达出口n==1;
第二条m会逐渐减少，因为n>m时，我们会return f(m,m) 所以终会到达出口m==0．
public static int count(int num_apple, int num_dish) {
// 递归出口
// 当dish=1时，所有苹果都必须放在一个盘子里，所以返回１
// 当apple=0(没有苹果可放)时，定义为１种放法
if(num_apple==0 || num_dish==1){
return 1;
}
//因为我们总是让m>=n来求解的，所以m-n>=0,所以让m=0时候结束，如果改为m=1
//则可能出现m-n=0的情况从而不能得到正确解
if(num_dish > num_apple){
return count(num_apple, num_apple);
}else {
return count(num_apple, num_dish-1) + count(num_apple-num_dish, num_dish);
}
} 
虾皮信息成长空间 250人发布
