牛客编程题--必刷101之字符串(高效刷题，举一反三)

1、 字符串变形

题目描述：对于一个长度为 n 字符串，我们需要对它做一些变形。

首先这个字符串中包含着一些空格，就像"Hello World"一样，然后我们要做的是把这个字符串中由空格隔开的单词反序，同时反转每个字符的大小写。
比如"Hello World"变形后就变成了"wORLD hELLO"。

输入：“This is a sample”,16
返回值：“SAMPLE A IS tHIS”

双逆转

解题思路：将单词位置的反转，那肯定前后都是逆序，不如我们先将整个字符串反转，这样是不是单词的位置也就随之反转了。但是单词里面的成分也反转了啊，既然如此我们再将单词里面的部分反转过来就行。

具体步骤：
step 1：遍历字符串，遇到小写字母，转换成大写，遇到大写字母，转换成小写，遇到空格正常不变。
step 2：第一次反转整个字符串，这样基本的单词逆序就有了，但是每个单词的字符也是逆的。
step 3：再次遍历字符串，以每个空间为界，将每个单词反转回正常。

import java.util.*;

public class Solution {
    public String trans(String s, int n) {
        // 双逆转
        if(n==0)
            return s;
        StringBuffer res = new StringBuffer();
        for(int i=0; i<n; i++){
            // 大小写转换
            if(s.charAt(i)<='Z' && s.charAt(i)>='A')
                res.append((char)(s.charAt(i)-'A'+'a'));
            else if(s.charAt(i)>='a' && s.charAt(i)<='z')
                res.append((char)(s.charAt(i)-'a'+'A'));
            else
                // 空格
                res.append(s.charAt(i));
        }
        // 翻转整个字符串
        res = res.reverse();
        // 单词翻转
        for(int i = 0; i< n; i++){
            int j =i;
            // 以空格为界
            while(j<n && res.charAt(j) !=' ')
                j++;
            String temp = res.substring(i,j);
            StringBuffer buffer = new StringBuffer(temp);
            temp = buffer.reverse().toString();
            res.replace(i, j, temp);
            i = j;
        }
        return res.toString();
    }
}
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

2、最长公共前缀

题目描述：给你一个大小为 n 的字符串数组 strs ，其中包含n个字符串 , 编写一个函数来查找字符串数组中的最长公共前缀，返回这个公共前缀。

示例：
输入：[“abca”,“abc”,“abca”,“abc”,“abcc”]
返回值：“abc”

思路：既然是公共前缀，那我们可以用一个字符串与其他字符串进行比较，从第一个字符开始，逐位比较，找到最长公共子串。

具体步骤：
step 1：处理数组为空的特殊情况。
step 2：因为最长公共前缀的长度不会超过任何一个字符串的长度，因此我们逐位就以第一个字符串为标杆，遍历第一个字符串的所有位置，取出字符。
step 3：遍历数组中后续字符串，依次比较其他字符串中相应位置是否为刚刚取出的字符，如果是，循环继续，继续查找，如果不是或者长度不足，说明从第i位开始不同，前面的都是公共前缀。
step 4：如果遍历结束都相同，最长公共前缀最多为第一个字符串。

public String longestCommonPrefix (String[] strs) {
        // 处理数组为空的情况
        if(strs.length == 0 || strs == null)
            return "";
        int row = strs.length;
        int col = strs[0].length();
        // 开始扫描
        for(int i = 0;i<col;i++){
            char fchar = strs[0].charAt(i);
            for(int j = 1;j<row;j++){
                // 首先判断长度不够，直接返回，其次是字符不相等
                if(strs[j].length() == i || strs[j].charAt(i) != fchar){
                    return strs[0].substring(0,i);
                }
            }
        }
        return strs[0];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

3、验证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 开头，忽略大小写)。

示例1
输入：“172.16.254.1”
返回值：“IPv4”
说明：这是一个有效的 IPv4 地址, 所以返回 “IPv4”

示例2
输入：“2001:0db8:85a3:0:0:8A2E:0370:7334”
返回值：“IPv6”
说明：这是一个有效的 IPv6 地址, 所以返回 “IPv6”

主要内容：
IPv4只有十进制数和分割点，其中数字在0-255之间，共4组，且不能有零开头的非零数，不能缺省
IPv6由8组16进制数组成，会出现a-fA-F，通过冒号分割，不可缺省，可以零开头，或者为一个单独零，每组最多4位。

直接分割比较法

具体步骤：
step 1：写一个split函数（或者内置函数）。
step 2：遍历IP字符串，遇到.或者:将其分开储存在一个数组中。
step 3：遍历数组，对于IPv4，需要依次验证分组为4，分割不能缺省，没有前缀0或者其他字符，数字在0-255范围内。
step 4：对于IPv6，需要依次验证分组为8，分割不能缺省，每组不能超过4位，不能出现除数字小大写a-f以外的字符。

import java.util.*;
public class Solution {
    boolean isIPv4 (String IP) {
        if(IP.indexOf('.') == -1){
            return false;
        }
        String[] s = IP.split("\\.");  
        //IPv4必定为4组
        if(s.length != 4)  
            return false;
        for(int i = 0; i < s.length; i++){
            //不可缺省，有一个分割为零，说明两个点相连
            if(s[i].length() == 0)  
                return false;
            //比较数字位数及不为零时不能有前缀零
            if(s[i].length() < 0 || s[i].length() > 3 || (s[i].charAt(0)=='0' && s[i].length() != 1))  
                return false;
            int num = 0;
            //遍历每个分割字符串，必须为数字
            for(int j = 0; j < s[i].length(); j++){  
                char c = s[i].charAt(j);
                if (c < '0' || c > '9') 
                    return false;
                //转化为数字比较，0-255之间
                num = num * 10 + (int)(c - '0');  
            if(num < 0 || num > 255) 
                return false;
            }
        }    
        return true;
    }
    boolean isIPv6 (String IP) {
        if (IP.indexOf(':') == -1) {
            return false;
        }
        String[] s = IP.split(":",-1);
        //IPv6必定为8组
        if(s.length != 8){  
            return false;
        }
        for(int i = 0; i < s.length; i++){ 
            //每个分割不能缺省，不能超过4位
            if(s[i].length() == 0 || s[i].length() > 4){ 
                return false; 
            }
            for(int j = 0; j < s[i].length(); j++){
                //不能出现a-fA-F以外的大小写字符
                char c = s[i].charAt(j);
                boolean expr = (c >= '0' && c <= '9') || (c >= 'a' && c <= 'f') || (c >= 'A' && c <= 'F') ;
                if(!expr){
                    return false;
                }
            }
        }
        return true;
    }
    String solve(String IP) {
        if(isIPv4(IP))
            return "IPv4";
        else if(isIPv6(IP))
            return "IPv6";
        return "Neither";
    }
}

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
60
61
62
63
64
65

其实还有比较简单的方法，用正则表达式可以减少代码量

正则表达式

思路：IP地址是有规律可言的：IPv4用了4个0-255的数字，用点隔开，IPv6用了4位十六进制的数字，用冒号隔开，共8组，这都可以直接用正则表达式来表示。

具体步骤：
step 1：IPv4的正则表达式限制数字在0-255，且没有前缀0，用3个点隔开共4组。
step 2：IPv6的正则表达式限制出现8组，0-9a-fA-F的数，个数必须是1-4个，用冒号隔开。
step 3：调用函数依次比较给定字符串与模板串之间是否匹配，匹配哪一个就属于哪一种IP地址，否则都不是。

import java.util.regex.Pattern;
public class Solution {
    String solve(String IP) {
        //正则表达式限制0-255 且没有前缀0 四组齐全
        String ipv4 = "(([0-9]|[1-9][0-9]|[1-9][0-9][0-9]|2[0-4][0-9]|25[0-5])\\.){3}([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])";
        Pattern ipv4_pattern = Pattern.compile(ipv4);
        //正则表达式限制出现8组，0-9a-fA-F的数，个数必须是1-4个
        String ipv6="([0-9a-fA-F]{1,4}\\:){7}[0-9a-fA-F]{1,4}";
        Pattern ipv6_pattern = Pattern.compile(ipv6);
        //调用正则匹配函数
        if(ipv4_pattern.matcher(IP).matches())
            return "IPv4";
        else if (ipv6_pattern.matcher(IP).matches())
            return "IPv6";
        else return "Neither";
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

4、大数加法

题目描述：以字符串的形式读入两个数字，编写一个函数计算它们的和，以字符串形式返回。

示例1：
输入：“1”,“99”
返回值：“100”
说明：1+99=100

示例2：
输入：“114514”,“”
返回值：“114514”

模拟法

思路：大整数相加，就可以按照整数相加的方式，从个位开始，逐渐往上累加，换到字符串中就是从两个字符串的末尾开始相加。

具体步骤：
step 1：若是其中一个字符串为空，直接返回另一个，不用加了。
step 2：交换两个字符串的位置，我们是s为较长的字符串，t为较短的字符串，结果也记录在较长的字符串中。
step 3：从后往前遍历字符串s，每次取出字符转数字，加上进位制，将下标转换为字符串t中从后往前相应的下标，如果下标为非负数则还需要加上字符串t中相应字符转化的数字。
step 4：整型除法取进位，取模算法去掉十位，将计算后的结果放入较长数组对应位置。
step 5：如果遍历结束，进位值还有，则需要直接在字符串s前增加一个字符‘1’。

import java.util.*;
public class Solution {
    public String solve (String s, String t) {
         //若是其中一个为空，返回另一个
        if(s.length()<=0)
            return t;
        if(t.length()<=0)
            return s;
        //让s为较长的，t为较短的
        if(s.length() < t.length()){
            String temp = s;
            s = t;
            t = temp;
        }
        int carry = 0; //进位标志
        char[] res = new char[s.length()];
        //从后往前遍历较长的字符串
        for(int i = s.length() - 1; i >= 0; i--){
            //转数字加上进位
            int temp = s.charAt(i) - '0' + carry;
            //转较短的字符串相应的从后往前的下标
            int j = i - s.length() + t.length();
            //如果较短字符串还有
            if(j >= 0)
                //转数组相加
                temp += t.charAt(j) - '0';
            //取进位
            carry = temp / 10;
            //去十位
            temp = temp % 10;
            //修改结果
            res[i] = (char)(temp + '0');
        }
        String output = String.valueOf(res);
        //最后的进位
        if(carry == 1)
            output = '1' + output;
        return output;
    }
}
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

尾部插入

实际上这道题求的是两个字符串相加，我们就用两个很短的字符串"12367"+"89"为例画个图来看下是怎么计算的

它相当于两个字符串从最右边开始相加，比如我们要计算s字符串的最右边的那个数字和t字符串最右边的那个字符相加：

int i = s.length() - 1, j = t.length() - 1;
int x = s.charAt(i) - '0';
int y = t.charAt(j) - '0';
int sum = x + y;
1
2
3
4

把计算的结果放到一个新的字符串后面，但字符串每一位只能保存一位数字，而我们相加的结果sum可能是个两位数，所以这里我们只取他的个位数，十位数要往前进一位。比如我们要计算s和t的倒数第二位：

int x = s.charAt(i - 1) - '0';
int y = t.charAt(j - 1) - '0';
int sum = x + y + carry;
1
2
3

carry就是上一步相加结果的进位，上一步如果进位了就是1，如果没进位就是0。搞懂了上面的相加过程，剩下的就是一些边界条件的判断。最后不要忘了对字符串进行反转，因为我们相加的时候是从s和t的尾部开始加的，下面我们来看下完整代码：

public String solve (String s, String t) {
        // write code here
        StringBuilder stringBulider = new StringBuilder();
        int i = s.length()-1, j = t.length()-1,carry = 0;
        while(i>=0|| j>=0 || carry !=0){
            int x = i<0 ? 0:s.charAt(i--) - '0';
            int y = j<0 ? 0:t.charAt(j--) - '0';
            int sum = x + y + carry;
            stringBulider.append(sum % 10);//添加到字符串尾部
            carry = sum /10 ;
        }
        return stringBulider.reverse().toString();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

为了避免进行反转字符串，可以直接用头部插入法

头部插入法

我们在计算的时候还可以先插入到字符串的头部，最后直接返回即可，不需要再反转了，代码和上面差不多:

public String solve (String s, String t) {
        // write code here
        StringBuilder stringBulider = new StringBuilder();
        int i = s.length()-1, j = t.length()-1,carry = 0;
        while(i>=0|| j>=0 || carry !=0){
            int x = i<0 ? 0:s.charAt(i--) - '0';
            int y = j<0 ? 0:t.charAt(j--) - '0';
            int sum = x + y + carry;
            stringBulider.insert(0,sum % 10);//插入到s字符串的第一个位置
            carry = sum /10 ;
        }
        return stringBulider.toString();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13

栈

思路跟之前链表中链表相加，解法思路一致，使用栈来解决，先把相加的结果放到一个栈中，最后再一个个出栈。

public String solve (String s, String t) {
        // write code here
        Stack<Integer> stack = new Stack<>();
        StringBuilder stringBulider = new StringBuilder();
        int i = s.length()-1, j = t.length()-1,carry = 0;
        while(i>=0|| j>=0 || carry !=0){
             carry += i<0 ? 0:s.charAt(i--) - '0';
             carry += j<0 ? 0:t.charAt(j--) - '0';
            //添加到字符串尾部
            stack.push(carry %10);
            carry = carry /10 ;
        }
        while(!stack.isEmpty())
            stringBulider.append(stack.pop());
        return stringBulider.toString();
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16