字符串（牛客）

2023-06-24 | 阅读：次

字符串（牛客）

题目来自牛客题目库算法篇面试必刷TOP101。

BM83 字符串变形(简单)

题目

题目链接

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

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

比如”Hello World”变形后就变成了”wORLD hELLO”。

数据范围: 1≤n≤10^6^ , 字符串中包括大写英文字母、小写英文字母、空格。

进阶：空间复杂度 O(n)，时间复杂度 O(n)

输入描述：

给定一个字符串s以及它的长度n(1 ≤ n ≤ 10^6)

返回值描述：

请返回变形后的字符串。题目保证给定的字符串均由大小写字母和空格构成。

示例：

示例1：
输入："This is a sample",16
返回值："SAMPLE A IS tHIS"
示例2：
输入："nowcoder",8
返回值："NOWCODER"
示例3：
输入："iOS",3
返回值："Ios"

解法双逆转

先将整个字符串反转，再反转每个单词。

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')); // 类型必须转化为char
            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();
    }
}

BM84 最长公共前缀(简单)

题目

题目链接

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

数据范围： 0≤n≤5000， 0≤len(strs~i~)≤5000

进阶：空间复杂度 O(1)，时间复杂度 O(n*len)

示例：

示例1：
输入：["abca","abc","abca","abc","abcc"]
返回值："abc"
示例2：
输入：["abc"]
返回值："abc"

解法纵向扫描

import java.util.*;

public class Solution {

    public String longestCommonPrefix (String[] strs) {
        if(strs.length==0 || strs==null){
            return "";
        }

        int rows = strs.length;
        int cols = strs[0].length();
        //开始扫描
        for(int i = 0; i < cols; i++){
            char firstChar = strs[0].charAt(i);
            for(int j = 1; j < rows; j++){
                // 最短的字符串已经扫描结束，或者存在字符串扫描的当前字符不相同
                if(strs[j].length() == i || strs[j].charAt(i) != firstChar){
                    return strs[0].substring(0,i);
                }
            }
        }
        // 第一个字符串扫描介绍，则返回第一个字符串
        return strs[0];
    }
}

BM85 验证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 是无效的。

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

数据范围：字符串长度满足 5≤ n ≤50

进阶：空间复杂度 O(n)，时间复杂度 O(n)

示例：

示例1：
输入："172.16.254.1"
返回值："IPv4"
示例2：
输入："2001:0db8:85a3:0:0:8A2E:0370:7334"
返回值："IPv6"
示例3：
输入："256.256.256.256"
返回值："Neither"

解法

import java.util.*;

public class Solution {

    public boolean isIPv4(String IP) {
        // 需以'.'为分隔符
        if (IP.indexOf('.') == -1)
            return false;
        String[] strs = IP.split("\\.");
        // 需分成4个字符串
        if (strs.length != 4)
            return false;
        for (int i = 0; i < strs.length; i++) {
            // 长度需在0~3之间
            if (strs[i].length() == 0 || strs[i].length() > 3)
                return false;
            // 不能存在开头的'0'
            if (strs[i].length() > 1 && strs[i].charAt(0) == '0')
                return false;
            int num = 0;
            for (int j = 0; j < strs[i].length(); j++) {
                // 需为0~9的数字
                if (strs[i].charAt(j) < '0' || strs[i].charAt(j) > '9')
                    return false;
                num = num * 10 + (int)(strs[i].charAt(j) - '0');
                if (num > 255)
                    return false;
            }
        }
        return true;
    }

    public boolean isIPv6(String IP) {
        // 需以':'分隔
        if (IP.indexOf(':') == -1)
            return false;
        String[] strs = IP.split(":", -1); // 不能用IP.split(":")，否则无法通过字符串结尾为":"的用例
        // 需为8组
        if (strs.length != 8)
            return false;
        for (int i = 0; i < strs.length; i++) {
            // 长度需在1~4之间
            if (strs[i].length() == 0 || strs[i].length() > 4)
                return false;
            // 组成字符需为数字和a到f的大小写英文字符
            for (int j = 0; j < strs[i].length(); j++) {
                Boolean b = strs[i].charAt(j) >= '0' && strs[i].charAt(j) <= '9' ||
                            strs[i].charAt(j) >= 'a' && strs[i].charAt(j) <= 'f' ||
                            strs[i].charAt(j) >= 'A' && strs[i].charAt(j) <= 'F';
                if (!b)
                    return false;
            }
        }
        return true;
    }

    public String solve (String IP) {
        if (isIPv4(IP))
            return "IPv4";
        else if (isIPv6(IP))
            return "IPv6";
        else
            return "Neither";
    }
}

BM86 大数加法(中等)

题目

题目链接

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

数据范围：s.length, t.length≤100000，字符串仅由’0’~‘9’构成

要求：时间复杂度 O(n)

示例：

示例1：
输入："1","99"
返回值："100"
说明：1+99=100 
示例2：
输入："114514",""
返回值："114514"

解法

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'); 
        }
        // 将char[]类型的res转化为String类的变量
        String output = String.valueOf(res);
        //最后的进位
        if(carry == 1) 
            output = '1' + output;
        return output;
    }
}

总结

字符串操作的主要方法：

StringBuffer类：
- char append(char a)：添加字符a
- void reverse()：反转字符串
- void toString()：转化为String类对象

String类：

int indexOf(char a) / indexOf(str s) / indexOf(char a, int i) / indexOf(str s, int i)：在字符串中（从下标 i 开始）寻找字符a（或字符串s）所在的下标，如果没有则返回-1

String[] split(String regex) / String[] split(String regex, int limit)：将字符串按分隔符regex分割，分成limit份（. 、 $、 **

** 和 *** 等转义字符，必须得加 **\\）

String[] split(String regex, -1)：如果最后若干位是分隔符， String[] split(String regex, -1) 仍然切割，而 String[] split(String regex) 不再切割
static valueOf()：静态方法，将括号里的各种类型的变量转化为String类的变量

String和StringBuffer类：
- replace(int i, int j, String s)：将字符串从 i 到 j（包括i，不包括j）替换为字符串s
- substring(int i, int j)：返回字符串从 i 到 j（包括i，不包括j）的字串

York Sun

York Sun

字符串（牛客）

目录

字符串（牛客）

BM83 字符串变形(简单)

题目

解法双逆转

BM84 最长公共前缀(简单)

题目

解法纵向扫描

BM85 验证IP地址(中等)

题目

解法

BM86 大数加法(中等)

题目

解法

总结

目录

字符串（牛客）

BM83 字符串变形(简单)

题目

解法 双逆转

BM84 最长公共前缀(简单)

题目

解法 纵向扫描

BM85 验证IP地址(中等)

题目

解法

BM86 大数加法(中等)

题目

解法

总结

解法双逆转

解法纵向扫描