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题解析
题目描述:
保证输入字符串中的括号'(',')','{','}','[',']'是否有效。也就是说,

  1. 左括号必须用相同类型的右括号闭合。
  2. 左括号必须以正确的顺序闭合。

题目解析:

  1. 栈先入后出特点恰好与本题括号排序特点一致,即若遇到左括号入栈,遇到右括号时将对应栈顶左括号出栈,则遍历完所有括号后 stack 仍然为空;
  2. 建立哈希表 dic 构建左右括号对应关系:key左括号,value右括号;这样查询 22 个括号是否对应只需 O(1) 时间复杂度;
  3. 建立栈 stack,遍历字符串 s 并按照算法流程一一判断。

算法流程:

  1. 先判断当前字符是括号么
  2. 如果 c 是左括号,则入栈 pushpush;
  3. 否则通过哈希表判断括号对应关系,若 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)
最大公约数用辗转相除法得到,

  1. a%b得余数c
  2. 若c=0,则b即为两数的最大公约数
  3. 若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:\”

解题思路:先用空格将字符串分割,在逐个便利每个,统计其中引号的数量:

  1. 如果有两个引号,就把引号去除直接加入答案容器中
  2. 如果有一个引号,则设置一个temp字符串,一致遍历到下一个引号为1的字符串,一起连起来
  3. 如果没有引号,直接加入答案容器中
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时,所有苹果都必须放在一个盘子里,所以返回1;

当没有苹果可放时,定义为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时,所有苹果都必须放在一个盘子里,所以返回1
    // 当apple=0(没有苹果可放)时,定义为1种放法
    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);
    }
}
全部评论

相关推荐

点赞 评论 收藏
分享
喜欢走神的孤勇者练习时长两年半:池是池,发是发,我曾池,我现黑
点赞 评论 收藏
分享
点赞 收藏 评论
分享
牛客网
牛客企业服务