3.11PCG后台一面算法题总结

一直在emo没有整上周一的面经，今天先把问的算法题整理下

面的是PCG的「PCG技术线、应用架构方向」的后台开发

明天又要面了，唉，越面越感受到一种无力感，查漏补缺的网越织越大，发现还有一大堆地方不会的，来日方长，慢慢一点一点进步把。心态真的很难蚌TAT

题目：

写一个函数将ipv4 地址字符串(仅包含数字，点，空格)转化成 32 位整数。数值两边的空格是合法的，其他情况均视为非法地址。要求输出合法地址的 32 位整型结果非法地址输出-1。注意此函数需要处理所有可能的错误。

输入:

0.0.0.1

0.0.1.0

0.0.1.1

1.1.1.1

1 . 1.1.1

1 1.1.1.1

输出：

1

256

257

16843009

16843009

-1

解析：1. 字符串相关操作是否熟练； 2. 正则表达式； 3. ipv4转整数位运算

字符串String相关操作

split(String regex)

用法： 以某种字符模式分隔字符串

返回值： 一个String数组（String[]）

例子： "1.1.1.1"

String str = "1.1.1.1";
System.out.println(str.split("\\.")); //这里的返回值是一个装了4个 1 的字符串数组

trim()

用法： 去除字符串头部和尾部的空格，中间的空格保留

返回值： 一个String

例子： " shut up! "

String str = " shut up ~! ";
System.out.println(str.trim); //这里的返回值是"shut up~!"

matches(String regex)

用法： 判断一个字符串是否满足某种字符模式

返回值： 一个boolean值，满足返回true，不满足返回false

例子： "123"

String str = "123456";
System.out.println(str.matches("[0-9]+")); //这里的返回值是true，因为满足了任意数字组合这个表达式

Integer.ParseInt(String str)

用法： 将字符串转换成整型数字

返回值： 一个int数字

OS: 呜呜呜那个时候被面麻了，根本就是忘了这个了，所以mark一下

正则表达式

+, *, ?

• +：表示+前面的字符必须至少出现一次

  E.G. sk+y sky，skky，skkky，...

• *：表示*前面的字符可以出现0次，1次或多次

  E.G. sk+y sy，skky，...

• ?：表示?前的字符最多可以出现1次

  E.G. sk?y sy，sky

普通字符

[ABC]

匹配[...]中的所有字符，他匹配zzzzzzA中的A；DWDWDAB中的AB

[^ABC]

匹配除了[...]中字符以外的所有字符

[A-Z]

匹配A-Z这个区间内的所有字母（匹配所有大写字母）

.

匹配除了换行符\n和\r以外的所有字符

IPV4转数字的逻辑

• 1.1.1.1，IPV4的每一个部分都是一个八位二进制数，我们计算完一部分IPV4就将结果左移8位来给下一个部分计算腾出空间，并与当前部分相加，如此往复

• 例子：

  192.168.1.1 将每一个部分转换成八位二进制就是11000000 10101000 00000001 00000001

  根据这个逻辑逐步来看

  • 首先处理192，

  • 然后是168，，我们可以看到每次处理的时候都会把上一个部分的值左移8位，这样反复循环四次就得到了IPV4所代表的整数值了

题解

package org.example.String;
import java.util.Scanner;

public class IPV4 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while (sc.hasNextLine()) {
            String s = sc.nextLine();
            if ("end".equalsIgnoreCase(s)) {
                break;
            }
            System.out.println(new IPV4Solution().IPV4parser(s));
        }
    }
}

class IPV4Solution{
    public int IPV4parser(String ipv4) {
        //trim方法会去除掉字符串收尾的空白字符
        ipv4 = ipv4.trim();
        //因为.在正则表达式中其他含义，需要转义（.表示除了换行符\n \r以外的所有字符）
        String[] strs = ipv4.split("\\.");
        int ans = 0;
        for(String str : strs) {
            //去除掉str里的空格
            str = str.trim();
            //检查字符是否合法
            if (!str.matches("[0-9]+") || str.isEmpty()) {
                return -1;
            }
            int num = Integer.parseInt(str);
            //检查数字是否在0..255之间
            if (num < 0 || num > 255) {
                return -1;
            }

            //将该部分加入到答案中
            //每处理完ipv4的一个部分就把已经处理完的部分左移8位并处理下一个部分（num）
            ans = (ans << 8) + num;
        }
        return ans;
    }
}