入门题

HJ5 进制转换(输入处理)

描述

写出一个程序，接受一个十六进制的数，输出该数值的十进制表示。

数据范围：保证结果在 1≤n≤2^31−1

输入描述：

输入一个十六进制的数值字符串。

输出描述：

输出该数值的十进制字符串。不同组的测试用例用\n隔开。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.Scanner;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String s = in.nextLine();
            int count = 0;
            for(int i=2; i<s.length(); i++ ){
                int t = 0;
                char tc= s.charAt(i);
                if(tc >= '0' && tc <= '9'){
                    t = tc-'0';
                }else if(tc>='a' && tc <='f'){
                    t = tc-'a' + 10;
                }else if(tc>='A' && tc <='F'){
                    t = tc-'A' + 10;
                }
                count += t * Math.pow(16, s.length()-1-i);
            }
            System.out.println(count);
        }
    }
}

NC61 两数之和(排列组合)

描述

给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。

（注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）

数据范围：2≤len(numbers)≤105，−10≤numbersi≤109，0≤target≤109

要求：空间复杂度O*(n)，时间复杂度 O(nlogn)

题解

  • 方法一：直接遍历
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
import java.util.*;
public class Solution {
    /**
     * 
     * @param numbers int整型一维数组 
     * @param target int整型 
     * @return int整型一维数组
     */
    public int[] twoSum (int[] numbers, int target) {
        // write code here
        int n = numbers.length;
        int[] res = {-1, -1};
        //遍历数组
        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                //判断相加值是否为target
                if (numbers[i] + numbers[j] == target) {
                    res[0] = i+1;
                    res[1] = j+1;
                    //返回值
                    return res;
                }
            }
        }
        return res;
    }
}

  • 方法二: hash表

    使用Map来降低时间复杂度，遍历数组，如果没有 （target - 当前值） 就将当前数字存入哈希表，如果有，返回该数字下标即可。

    哈希表可以优化第二遍循环中对元素的检索速度，

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.*;
public class Solution {
    /**
     * 
     * @param numbers int整型一维数组 
     * @param target int整型 
     * @return int整型一维数组
     */
    public int[] twoSum (int[] numbers, int target) {
        int n = numbers.length;
        int[] res = {-1, -1};
        Map<Integer, Integer> map = new HashMap<>();
        //遍历数组
        for (int i = 0; i < n; ++i) {
            int temp = numbers[i];
			if(map.get(target - temp) == null){
                map.put(temp, i+1);
            }else{
                res[0] = map.get(target - temp);
                res[1] = i + 1;
                return res;
            }
        }
        return res;
    }
}

HJ3 明明的随机数(快速排序)

描述

明明生成了N个1到500之间的随机整数。请你删去其中重复的数字，即相同的数字只保留一个，把其余相同的数去掉，然后再把这些数从小到大排序，按照排好的顺序输出。

数据范围：1≤n≤1000 ，输入的数字大小满足 1≤val≤500

输入描述：

第一行先输入随机整数的个数 N 。 接下来的 N 行每行输入一个整数，代表明明生成的随机数。 具体格式可以参考下面的"示例"。

输出描述：

输出多行，表示输入数据处理后的结果

###　题解

方案一：去重，排序，使用TreeSet

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.*;

public class Test {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //获取个数
        int num = sc.nextInt();
        //创建TreeSet进行去重排序
        TreeSet set = new TreeSet();
        //输入
        for(int i =0 ; i < num ;i++){
            set.add(sc.nextInt());
        }

        //输出
        Iterator iterator = set.iterator();
        while (iterator.hasNext()){
            System.out.println(iterator.next());
        }
    }
}

方案二：利用数组每个下标都是独一无二的，且下标本身有序（空间换时间）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.*;

public class Test {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        //获取个数
        int num = sc.nextInt();
        int[] arr = new int[1000];
        //输入 对应下标内容设置为1
        for(int i =0 ; i < num ;i++){
            int temp = sc.nextInt();
            arr[temp-1] = 1;
        }

        //输出
        for(int i =0 ; i < arr.length ;i++){
            if(arr[i] == 1){
                System.out.println(arr[i]);
            }
        }
    }
}

方案三：数组存储，利用库函数排序，重复的不打印

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
import java.util.Scanner;
import java.util.Arrays;

public class Main{
    public static void main(String[] args){
        Scanner in = new Scanner(System.in);
        while(in.hasNext()){
            int count = in.nextInt();    //随机数总数
            int[] data = new int[count];
            for(int i=0; i < count; i++)    //读入生成的随机数
                data[i] = in.nextInt();
            
            Arrays.sort(data);    //使用库函数排序
            System.out.println(data[0]);    //打印排序后的第一个数（必不重复）
            for(int i=1; i < count; i++){    //打印其他数字，需与前面数字比较，不重复才能打印
                if(data[i] != data[i-1])
                    System.out.println(data[i]);
            }
        }
    }
}

HJ10 字符个数统计(哈希表)

描述

编写一个函数，计算字符串中含有的不同字符的个数。字符在 ASCII 码范围内( 0~127 ，包括 0 和 127 )，换行表示结束符，不算在字符里。不在范围内的不作统计。多个相同的字符只计算一次

例如，对于字符串 abaca 而言，有 a、b、c 三种不同的字符，因此输出 3 。

数据范围： 1≤n≤500

输入描述：

输入一行没有空格的字符串。

输出描述：

输出 输入字符串 中范围在(0~127，包括0和127)字符的种数。

题解

  • 方法一: HashSet
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        while (in.hasNextLine()) { // 注意 while 处理多个 case
            String str = in.nextLine();
            Set set = new HashSet();
            for(int i=0; i<str.length(); i++){
                char c = str.charAt(i);
                set.add(c);
            }
            System.out.println(set.size());
        }
    }
}
  • 方法二: 位图
1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        String line = in.nextLine();
        BitSet bitSet = new BitSet(128);
        for(char c : line.toCharArray()){
            if(!bitSet.get(c)){
                bitSet.set(c);
            }
        }
        System.out.println(bitSet.cardinality());
    }
}

*NC68 跳台阶(递归)

描述

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个 n 级的台阶总共有多少种跳法（先后次序不同算不同的结果）。

数据范围：1≤n≤40

要求：时间复杂度：O(n) ，空间复杂度： O*(1)

题解

  • 方法一: 递归(优点，代码简单好写，缺点：慢)
1
2
3
4
5
6
7
class Solution {
public:
    int jumpFloor(int number) {
        if (number<=1) return 1;
        return jumpFloor(number-1)+jumpFloor(number-2);
    }
};
  • 方法二: 记忆化搜索 记忆化搜索 拿求f[5] 举例

img

​ 通过图会发现，方法一中，存在很多重复计算，因为为了改进，就把计算过的保存下来。 那么用什么保存呢？一般会想到map， 但是此处不用牛刀，此处用数组就好了。

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int f[50]{0};
    int jumpFloor(int number) {
        if (number <= 1) return 1;
        if (f[number] > 0) return f[number];
        return f[number] = (jumpFloor(number-1)+jumpFloor(number-2));
    }
};
  • 方法三: 动态规划

​ 虽然方法二可以解决此题了，但是如果想让空间继续优化，那就用动态规划，优化掉递归栈空间。 方法二是从上往下递归的然后再从下往上回溯的，最后回溯的时候来合并子树从而求得答案。 那么动态规划不同的是，不用递归的过程，直接从子树求得答案。过程是从下往上。

1
2
3
4
5
6
7
8
9
class Solution {
public:
    int dp[50]{0};
    int jumpFloor(int number) {
        dp[0] = 1, dp[1] =1;
        for (int i = 2 ; i <= number ; i ++) dp[i] = dp[i-1]+dp[i-2];
        return dp[number];
    }
};

继续优化 发现计算f[5]的时候只用到了f[4]和f[3], 没有用到f[2]…f[0],所以保存f[2]…f[0]是浪费了空间。 只需要用3个变量即可。

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int jumpFloor(int number) {
        int a = 1 , b = 1 , c = 1;
        for (int i = 2 ; i <= number ; i ++) {
            c = a+b , a = b , b = c;
        }
        return c;
    }
};

字符串操作

HJ17 坐标移动

描述

开发一个坐标计算工具， A表示向左移动，D表示向右移动，W表示向上移动，S表示向下移动。从（0,0）点开始移动，从输入字符串里面读取一些坐标，并将最终输入结果输出到输出文件里面。

输入：

合法坐标为A(或者D或者W或者S) + 数字（两位以内）

坐标之间以;分隔。

非法坐标点需要进行丢弃。如AA10; A1A; %; YAD; 等。

下面是一个简单的例子 如：

A10;S20;W10;D30;X;A1A;B10A11;;A10;

处理过程：

起点（0,0）

+ A10 = （-10,0）

+ S20 = (-10,-20)

+ W10 = (-10,-10)

+ D30 = (20,-10)

+ x = 无效

+ A1A = 无效

+ B10A11 = 无效

+ 一个空 不影响

+ A10 = (10,-10)

结果 （10， -10）

数据范围：每组输入的字符串长度满足 1≤n≤10000 ，坐标保证满足−2^31≤x, y≤2^31−1 ，且数字部分仅含正数

输入描述：

一行字符串

输出描述：

最终坐标，以逗号分隔

题解

关键在于正则过滤

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
import java.util.*;
import java.io.*;

public class Main{
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        String[] in = bf.readLine().split(";");
        int x = 0;
        int y = 0;
        for(String s : in){
            // 不满足题目给定坐标规则
            if(!s.matches("[WASD][0-9]{1,2}")){
                continue;
            }
            int val = Integer.valueOf(s.substring(1));
            switch(s.charAt(0)){
                case 'W':
                    y += val;
                    break;
                case 'S':
                    y -= val;
                    break;
                case 'A':
                    x -= val;
                    break;
                case 'D':
                    x += val;
                    break;
            }
        }
        System.out.println(x+","+y);
    }
}

HJ20 密码验证合格程序

描述

密码要求:

1.长度超过8位

2.包括大小写字母.数字.其它符号,以上四种至少三种

3.不能有长度大于2的包含公共元素的子串重复 （注：其他符号不含空格或换行）

数据范围：输入的字符串长度满足 1≤n≤100

输入描述：

一组字符串。

输出描述：

如果符合要求输出：OK，否则输出NG

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
import java.util.*;
import java.util.regex.*;
public class Main{
    public static void main(String[] arg){
        Scanner sc = new Scanner(System.in);
        while(sc.hasNext()){
            String str = sc.next();
            if(str.length() <= 8){
                System.out.println("NG");
                continue;
            }
            if(getMatch(str)){
                System.out.println("NG");
                continue;
            }
            if(getString(str, 0, 3)){
                System.out.println("NG");
                continue;
            }
            System.out.println("OK");
        }
    }
    // 校验是否有重复子串
    private static boolean getString(String str, int l, int r) {
        if (r >= str.length()) {
            return false;
        }
        if (str.substring(r).contains(str.substring(l, r))) {
            return true;
        } else {
            return getString(str,l+1,r+1);
        }
    }
    // 检查是否满足正则
    private static boolean getMatch(String str){
        int count = 0;
        Pattern p1 = Pattern.compile("[A-Z]");
        if(p1.matcher(str).find()){
            count++;
        }
        Pattern p2 = Pattern.compile("[a-z]");
        if(p2.matcher(str).find()){
            count++;
        }
        Pattern p3 = Pattern.compile("[0-9]");
        if(p3.matcher(str).find()){
            count++;
        }
        Pattern p4 = Pattern.compile("[^a-zA-Z0-9]");
        if(p4.matcher(str).find()){
            count++;
        }
        if(count >= 3){
            return false;
        }else{
            return true;
        }
    }
}

*HJ23删除字符串中出现次数最少的字符

描述

实现删除字符串中出现次数最少的字符，若出现次数最少的字符有多个，则把出现次数最少的字符都删除。输出删除这些单词后的字符串，字符串中其它字符保持原来的顺序。

数据范围：输入的字符串长度满足 1≤n≤20 ，保证输入的字符串中仅出现小写字母

输入描述：

字符串只包含小写英文字母, 不考虑非法输入，输入的字符串长度小于等于20个字节。

输出描述：

删除字符串中出现次数最少的字符后的字符串。

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
import java.util.*;

// 注意类名必须为 Main, 不要有任何 package xxx 信息
public class Main {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 注意 hasNext 和 hasNextLine 的区别
        String str = in.nextLine();
        Map<Character, Integer> map = new HashMap<>();
        char[] charArr = str.toCharArray();
        for(char c: charArr){
            map.put(c, map.getOrDefault(c, 0) + 1);
        }
        int min = Integer.MAX_VALUE;
        for(char c: charArr){
            min=Math.min(min, map.get(c));
        }
        StringBuilder sb = new StringBuilder();
        for(char c: charArr){
            if(map.get(c) != min){
                sb.append(c);
            }
        }
        System.out.println(sb.toString());
    }
}

*HJ33 整数和IP地址间的转换

描述

原理：ip地址的每段可以看成是一个0-255的整数，把每段拆分成一个二进制形式组合起来，然后把这个二进制数转变成
一个长整数。
举例：一个ip地址为10.0.3.193
每段数字 相对应的二进制数
10 00001010
0 00000000
3 00000011
193 11000001

组合起来即为：00001010 00000000 00000011 11000001,转换为10进制数就是：167773121，即该IP地址转换后的数字就是它了。

数据范围：保证输入的是合法的 IP 序列

输入描述：

输入
1 输入IP地址
2 输入10进制型的IP地址

输出描述：

输出
1 输出转换成10进制的IP地址
2 输出转换后的IP地址

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
import java.util.*;

public class Main {

    private final int N = 4;
    public Main() {
    }

    public String convert(String str) {
        // ipv4 -> int
        if (str.contains(".")) {
            String[] fields = str.split("\\.");
            long result = 0;
            for (int i = 0; i < N; i++) {
                result = result * 256 + Integer.parseInt(fields[i]);
            }
            return "" + result;
        }
        // int -> ipv4
        else {
            long ipv4 = Long.parseLong(str);
            String result = "";
            for (int i = 0; i < N; i++) {
                result = ipv4 % 256 + "." + result;
                ipv4 /= 256;
            }
            return result.substring(0, result.length() - 1);
        }
    }

    public static void main(String[] args) {
        Main solution = new Main();
        Scanner in = new Scanner(System.in);
        while (in.hasNext()) {
            String str = in.next();
            String res = solution.convert(str);
            System.out.println(res);
        }
    } 
}

HJ101 输入整型数组和排序标识，对其元素按照升序或降序进行排序

描述

输入整型数组和排序标识，对其元素按照升序或降序进行排序

数据范围： 1≤n≤1000 ，元素大小满足 0≤val≤100000

输入描述：

第一行输入数组元素个数
第二行输入待排序的数组，每个数用空格隔开
第三行输入一个整数0或1。0代表升序排序，1代表降序排序

输出描述：

输出排好序的数字

题解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
import java.util.*;
public class Main{
	public static void main(String[] args){
		Scanner sc = new Scanner(System.in);
		while(sc.hasNext()){
			int n = sc.nextInt();//接收数组长度
			int[] arr = new int[n];//创建数组

			for (int i = 0; i < n; i++) {//数组填入
				arr[i] = sc.nextInt();
			}
			
			int flag = sc.nextInt();//接收排序标识
			Arrays.sort(arr);//数组排序

			if (flag == 0) {//正序输出
				for(int i =0; i < arr.length; i++){
					System.out.print(arr[i] + " ");
				} 
			}
			else {//逆序输出
					for(int i = arr.length - 1; i >= 0; i--){
						System.out.print(arr[i] + " ");
					}
			}
		}
	}
}

排序

#　栈

排列组合

双指针

深搜

二叉树

其他