【程序员面试系列】算法题练习-汇总(含华为OD机试题目)

做个4月算法刷题集合，方便复习巩固，欢迎交流探讨。
题库源于牛客网，ACM模式，语言：Java，Python。
题库链接

HJ1 字符串最后一个单词的长度

描述 计算字符串最后一个单词的长度，单词以空格隔开，字符串长度小于5000。（注：字符串末尾不以空格为结尾）
输入描述：
输入一行，代表要计算的字符串，非空，长度小于5000。
输出描述：
输出一个整数，表示输入字符串最后一个单词的长度。
示例1
输入： hello nowcoder
输出： 8
说明： 最后一个单词为nowcoder，长度为8

Java版本

//w1
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();   //注意next() 与 nextLine()区别
        String[] s = str.split(" ");
        int length = s[s.length - 1].length();
        System.out.println(length);
    }
}

//w2 反过来打印
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();   //注意next() 与 nextLine()区别
        int length = str.length();
        int count = 0;
        for(int i = length -1; i>=0; i--) {
            if(str.charAt(i) == ' ') 
                break;
            count++;
        }
        System.out.println(count);
    }
}

HJ2 计算某字符出现次数

描述 写出一个程序，接受一个由字母、数字和空格组成的字符串，和一个字符，然后输出输入字符串中该字符的出现次数。（不区分大小写字母）
数据范围： 1 \le n \le 1000 \1≤n≤1000
输入描述：
第一行输入一个由字母、数字和空格组成的字符串，第二行输入一个字符（保证该字符不为空格）。
输出描述： 输出输入字符串中含有该字符的个数。（不区分大小写字母）
示例1
输入： ABCabc A
输出： 2

Java版本

import java.util.Scanner;

//减法
public class Main{
    public static void main(String[] args) {
        Scanner s = new Scanner(System.in);
        String str1 = s.nextLine();
        String str2 = s.nextLine();   //注意如何区分两次输入
        String str3 = str1.toUpperCase().replaceAll(str2.toUpperCase(),"");
        System.out.println(str1.length() - str3.length());
    }
}

HJ4 字符串分隔

描述 输入一个字符串，请按长度为8拆分每个输入字符串并进行输出；
•长度不是8整数倍的字符串请在后面补数字0，空字符串不处理。
输入描述： 连续输入字符串(每个字符串长度小于等于100)
输出描述： 依次输出所有分割后的长度为8的新字符串
示例1
输入： abc
输出： abc00000

Java版本

import java.util.Scanner;

//1.获取输入的字符串
//2.判断字符串长度，小于8,
//在后面补上0，达到8位，大于8，先以8位作为
//一段截取，再判断剩余字符串长度与8比较，如果小于8,
//照上述操作，大于8，先截取8位，再判断剩下的...
//如此循环操作。
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        //String s = in.nextLine();   注意第一次输入就使用了hasNextLine
        while (in.hasNextLine()) {
            String s = in.nextLine();
            split(s);
        }
    } // 主函数

    public static void split(String s) {
        while (s.length() >= 8) {
            System.out.println(s.substring(0, 8));
            s = s.substring(8);
        }
        if (s.length() < 8 && s.length() > 0) {
            s += "00000000";
            System.out.println(s.substring(0, 8));
        }
    }
}

HJ5 进制转换

描述 写出一个程序，接受一个十六进制的数，输出该数值的十进制表示。
数据范围：保证结果在 1 \le n \le 2^{31}-1 \1≤n≤2 31 −1
输入描述：
输入一个十六进制的数值字符串。
输出描述：
输出该数值的十进制字符串。不同组的测试用例用\n隔开。
示例1
输入： 0xAA
输出： 170

进制转换详解
Java版本

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        while (in.hasNextLine()) {
            String s = in.nextLine();  
            System.out.println(Integer.parseInt(s.substring(2), 16));
        }
    }
}

HJ6 质数因子

描述 功能:输入一个正整数，按照从小到大的顺序输出它的所有质因子（重复的也要列举）（如180的质因子为2 2 3 3 5 ）
数据范围： 1 \le n \le 2 \times 10^{9} + 14 \1≤n≤2×10 9 +14
输入描述： 输入一个整数
输出描述： 按照从小到大的顺序输出它的所有质数的因子，以空格隔开。
示例1
输入： 180
输出： 2 2 3 3 5

Java版本

import java.util.Scanner;
//import java.math.*;
//一个正整数最多有一个质因子大于其平方根，且只会是其本身
//质因数指既是因子，又是质数
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        long num = in.nextLong();
        long k = (long) Math.sqrt(num);
        for (int i = 2; i <= k; i++) {
            while (num % i == 0) {
                System.out.print(i + " ");
                num = num / i;
            }
        }
        System.out.println(num == 1 ? "" : num + ""); //注意是最后一步
    }
}

HJ8 合并表记录

描述
数据表记录包含表索引index和数值value（int范围的正整数），请对表索引相同的记录进行合并，即将相同索引的数值进行求和运算，输出按照index值升序进行输出。

提示: 0 <= index <= 11111111 1 <= value <= 100000

输入描述： 先输入键值对的个数n（1 <= n <= 500） 接下来n行每行输入成对的index和value值，以空格隔开
输出描述： 输出合并后的键值对（多行）
示例1 输入： 4
0 1
0 2
1 2
3 4

输出：
0 3
1 2
3 4

Java版本

import java.util.*;

// 注意：最后循环的map.keySet() 注意大小写
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        int num = in.nextInt();
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for (int i = 1; i <= num; i++) {
            int key = in.nextInt();
            int value = in.nextInt();
            map.put(key, map.getOrDefault(key, 0) + value);
        }
        for (Integer key : map.keySet()) {
            System.out.println(key + " " + map.get(key));
        }
    }
}

HJ10 字符个数统计

编写一个函数，计算字符串中含有的不同字符的个数。字符在 ASCII 码范围内( 0~127 ，包括 0 和 127> )，换行表示结束符，不算在字符里。不在范围内的不作统计。多个相同的字符只计算一次 例如，对于字符串 abaca 而言，有 a、b、c
三种不同的字符，因此输出 3 。
数据范围： 1 ≤ � ≤ 500 1≤n≤500 输入描述： 输入一行没有空格的字符串。
输出描述： 输出 输入字符串 中范围在(0~127，包括0和127)字符的种数。
示例1 输入： abc 输出： 3
示例2 输入： aaa 输出： 1

import java.util.Scanner;
import java.util.BitSet;

public class Main {
//Java BitSet解决海量数据去重
//https://blog.csdn.net/weixin_30500473/article/details/99400100
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        String line = scanner.next();
        //总共有128个字符。字需要用128位
        BitSet bitSet = new BitSet(128);
        for (char c : line.toCharArray()) {
            //判断字符c是否已出现
            if (!bitSet.get(c)) {
                //未出现就设置为已出现
                bitSet.set(c);
            }
        }
        //统计有多少字符已出现过
        System.out.println(bitSet.cardinality());
    }
}

HJ11 数字颠倒

输入描述： 输入一个int整数
输出描述： 将这个整数以字符串的形式逆序输出
示例1
输入： 1516000
输出： 0006151
示例2
输入： 0
输出： 0

import java.util.Scanner;
/*
老套路，写出主体框架→实例化字符串对象str并接收命令行传入的变量→直接使用传入的字符串对象来构造可变数组的实例对象strb，
可变字符串类有reverse方法可以直接反转数组，不需要自己写方法。输出的时候记得再转换成字符串类型。和另一个题（字符串反转）完全一致。。。
*/
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        StringBuffer strb = new StringBuffer(str);
        strb.reverse();
        System.out.println(strb);
    }
}

HJ13 句子逆序

描述 将一个英文语句以单词为单位逆序排放。例如“I am a boy”，逆序排放后为“boy a am I”
所有单词之间用一个空格隔开，语句中除了英文字母外，不再包含其他字符
数据范围：输入的字符串长度满足 1 ≤ � ≤ 1000 1≤n≤1000
注意本题有多组输入 输入描述： 输入一个英文语句，每个单词用空格隔开。保证输入只包含空格和字母。
输出描述： 得到逆序的句子
示例1
输入： I am a boy
输出： boy a am I
示例2
输入：nowcoder
输出：nowcoder

import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        String str = in.nextLine();
        String s[] = str.split(" ");        //这一步挺关键
        for(int i=s.length- 1; i>=0; i--) {  //注意循环的判断条件问题
            if(i!=0)
                System.out.print(s[i]+" ");
            else
                System.out.print(s[i]);
        }
    }
}