年轻即出发...

简书：https://www.jianshu.com/u/7110a2ba6f9e

知乎：https://www.zhihu.com/people/zqtao23/posts

GitHub源码：https://github.com/zqtao2332

个人网站：http://www.zqtaotao.cn/ （停止维护更新内容）

QQ交流群：606939954

​ 咆哮怪兽一枚...嗷嗷嗷...趁你现在还有时间，尽你自己最大的努力。努力做成你最想做的那件事，成为你最想成为的那种人，过着你最想过的那种生活。也许我们始终都只是一个小人物，但这并不妨碍我们选择用什么样的方式活下去，这个世界永远比你想的要更精彩。

最后：喜欢编程，对生活充满激情

---

---

本节内容预告

2020秋招-快手笔试题

实例1：验证IP地址

实例2：电话号码的字母组合

实例3：数组|s1-s2|最小值

实例4：最长等差数列的长度

---

---

实例1：有效的IP地址

编写一个函数来验证输入的字符串是否是有效的 IPv4 或 IPv6 地址。

IPv4 地址由十进制数和点来表示，每个地址包含4个十进制数，其范围为 0 - 255， 用(".")分割。比如，172.16.254.1；

同时，IPv4 地址内的数不会以 0 开头。比如，地址 172.16.254.01 是不合法的。

IPv6 地址由8组16进制的数字来表示，每组表示 16 比特。这些组数字通过 (":")分割。比如, 2001:0db8:85a3:0000:0000:8a2e:0370:7334 是一个有效的地址。而且，我们可以加入一些以 0 开头的数字，字母可以使用大写，也可以是小写。所以， 2001:db8:85a3:0:0:8A2E:0370:7334 也是一个有效的 IPv6 address地址 (即，忽略 0 开头，忽略大小写)。

然而，我们不能因为某个组的值为 0，而使用一个空的组，以至于出现 (::) 的情况。 比如， 2001:0db8:85a3::8A2E:0370:7334 是无效的 IPv6 地址。

同时，在 IPv6 地址中，多余的 0 也是不被允许的。比如， 02001:0db8:85a3:0000:0000:8a2e:0370:7334 是无效的。

说明: 你可以认为给定的字符串里没有空格或者其他特殊字符。

示例 1:

输入: "172.16.254.1"

输出: "IPv4"

解释: 这是一个有效的 IPv4 地址, 所以返回 "IPv4"。

示例 2:

输入: "2001:0db8:85a3:0:0:8A2E:0370:7334"

输出: "IPv6"

解释: 这是一个有效的 IPv6 地址, 所以返回 "IPv6"。

示例 3:

输入: "256.256.256.256"

输出: "Neither"

解释: 这个地址既不是 IPv4 也不是 IPv6 地址。

/**
 * 有效IP地址
 */
public class Code_07_IsValidIP {
    public static String getIp(String ip) {
        if (ip == null || ip.length() == 0) return "Neither";

        if (ip.startsWith(":") || ip.startsWith(".")
                || ip.endsWith(":") || ip.endsWith(".")
        )
            return "Neither";

        String[] split = ip.split("\\.");
        if (split.length == 4) {
            int n = 1;
            for (int i = 0; i < 4; i++) {
                try {
                    n = Integer.parseInt(split[i]);
                    if (n < 0 || n > 255) return "Neither";
                    if (split[i].length() > 1 && (split[i].startsWith("0") || split[i].startsWith(".")))
                        return "Neither";
                } catch (Exception e) {
                    return "Neither";
                }
            }
            return "IPv4";
        } else {
            split = ip.split(":");
            if (split.length == 8) {
                long n = -1;
                for (int i = 0; i < 8; i++) {
                    try {
                        if (split[i].length() > 4 || split[i].startsWith(".")) return "Neither";
                        n = Long.parseLong(split[i], 16);
                        if (n < 0) return "Neither";
                    } catch (Exception e) {
                        return "Neither";
                    }
                }
                return "IPv6";
            } else {
                return "Neither";
            }

        }

    }

    public static void main(String[] args) {
        System.out.println(getIp("256.256.256.256"));
        System.out.println(getIp("2001:0db8:85a3:0:0:8A2E:0370:7334"));
        System.out.println(getIp("172.16.254.1"));
    }
}

实例2：电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。

给出数字到字母的映射如下（与电话按键相同）。注意 1 不对应任何字母。

电话号码与字母映射.png

示例:

输入："23"
输出：["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"].

说明:
尽管上面的答案是按字典序排列的，但是你可以任意选择答案输出的顺序。

public static LinkedList<String> getRes(String str){
    if (str == null ||str.length() == 0) 
        return new LinkedList<>();
    String[] strings = {" ", " ", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};
    LinkedList<String> res = new LinkedList<>();
    res.add("");
    for (int i = 0; i < str.length(); i++) {
        int index = Character.getNumericValue(str.charAt(i));
        while (res.peek().length() == i) {
            String tmp = res.remove();
            for(char c : strings[index].toCharArray()){
                res.add(tmp + c);
            }
        }
    }
    return res;
}

实例3：数组|s1-s2|最小值

数组|s1-s2|最小值，其中s1 ,s2 分别为以i为数组左右两区域的子数组和，即0~i 累加和 s1, i+1~N-1 累加和 s2

这道题给我都做抑郁了，真心感到难受！快手给的测试用例应该是给错了，通过80%。

用例1
1,1,1,999
输出 996

用例2（我很难受的测试用例）
2,4,5,6,9
输出 0
请恕我不知道究竟如何分数组才能得到 0 这个答案，恕我学艺不精！！！

笔试完毕我在牛客上发现了别人发的100%通过，额，很意外，简直不想说话！！！这位牛友将这个测试用例提取出来了，单独处理，不得不说这个取巧通过让我无言以对呀！

牛油取巧.png

/**
 * 数组|s1-s2|最小值
 */
public class Code_09_ArrayTowPartMinSum{
    public static int method(int[] arr) {
        if (arr == null || arr.length < 1) return 0;
        if (arr.length == 2) {
            return Math.abs(arr[0] - arr[1]);
        }

        int[] sL = new int[arr.length];
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
            sL[i] = sum;
        }

        sum = 0;
        int[] sR = new int[arr.length];
        for (int i = arr.length - 1; i >= 0; i--) {
            sum += arr[i];
            sR[i] = sum;
        }

        int s1 = 0;
        int s2 = 0;
        int min = Integer.MAX_VALUE;
        for (int i = 1; i < arr.length - 1; i++) {
            s1 = sL[i];
            s2 = sR[i + 1];
            min = Math.min(min, Math.abs(s1 - s2));
        }
        return min;
    }

    public static void main(String[] args) {
        int[] arr = {1,1,1,999};
        System.out.println(method( arr));
        int[] arr2 = {2,4,5,6,9};
        System.out.println(method(arr2));
        int[] arr3 = {2,2,2,2};
        System.out.println(method(arr3));
    }
}

实例4：最长等差数列

题目：给定一个数组求出数组最长等差数列的长度。
举例：3,8,4,5,6,2
输出：5。

// dp[][]
public static int method(int[] arr) {
    if (arr == null || arr.length == 0) return 0;

    Arrays.sort(arr);
    int d = arr[arr.length - 1] - arr[0]; // 最大等差
    int[][] dp = new int[arr.length][d + 1];

    for (int i = 0; i < arr.length; i++) {
        for (int j = 0; j <= d; j++) {
            dp[i][j] = 1; // 任意一个元素单独成一个长度为1 的数列
        }
    }

    int max = 0;
    for (int i = 0; i < arr.length; i++) {
        for (int j = i - 1; j >= 0; j--) { // 考察 i-1~0 范围
            d = arr[i] - arr[j]; // 相同等差 d , a(n) = a(n-1) +d
            dp[i][d] = dp[j][d] + 1; // 所以相同等差，长度可以加一
            max = Math.max(max, dp[i][d]);
        }
    }
    return max;
}