[数据结构与算法]【数据结构】LeetCode必刷题之字符串

二、字符串

1、006——Z 字形变换

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 “PAYPALISHIRING” 行数为 3 时，排列如下：

P A H N
A P L S I I G
Y I R
之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如：“PAHNAPLSIIGYIR”。

请你实现这个将字符串进行指定行数变换的函数：

/**
 * 要求：按Z字从上到下，从左到右排列，要求从左到右按行输出
 * 思路：把每行的字符逐个加进来，通过一个flag表示向上或者向下，
 * 每次到临界值是flag = -flag,用于改变方向
 */
public static String convert(String s, int numRows) {
    if (null == s || numRows < 2) {
        return s;
    }
    List<StringBuilder> rows = new ArrayList<>();
    for (int i = 0; i < numRows; i++) {
        rows.add(new StringBuilder());
    }
    int i = 0;
    int flag = -1;
    for (char c : s.toCharArray()) {
        rows.get(i).append(c);
        if (i == 0 || i == numRows - 1) {
            flag = -flag;
        }
        i += flag;
    }
    StringBuilder res = new StringBuilder();
    for (StringBuilder row : rows) {
        res.append(row);
    }
    return res.toString();
}

2、008——字符串转换整数 (atoi)

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

1、读入字符串并丢弃无用的前导空格
2、检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
3、读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
4、将前面步骤读入的这些数字转换为整数（即，“123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
5、如果整数数超过 32 位有符号整数范围 [?231, 231 ? 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 ?231 的整数应该被固定为 ?231 ，大于 231 ? 1 的整数应该被固定为 231 ? 1 。
返回整数作为最终结果。

public int myAtoi(String s) {
    int len = s.length();
    char[] chars = s.toCharArray();
    // 1、去除前置空格
    int index = 0;
    while (index < len && chars[index] == ' ') {
        index++;
    }
    // 2、如果已经遍历完成（针对极端用例 "      "）
    if (index == len) {
        return 0;
    }
    // 3、如果出现符号 仅第一个有效
    int sign = 1;
    char firstChar = chars[index];
    if (firstChar == '+') {
        index++;
    } else if (firstChar == '-') {
        index++;
        sign = -1;
    }
    // 4、将后续出现的数字字符进行转换
    // 不能使用 long 类型，这是题目说的
    int res = 0;
    while (index < len) {
        char curr = chars[index];
        // 5、遇到非数字结束返回
        if (curr > '9' || curr < '0') {
            break;
        }
        // 6、如果比最大值大，返回最大值
        if (res > Integer.MAX_VALUE / 10 || (res == Integer.MAX_VALUE / 10 && (curr - '0' > Integer.MAX_VALUE % 10))) {
            return Integer.MAX_VALUE;
        }
        // 7、如果比最小值小,返回最小值
        if (res < Integer.MIN_VALUE / 10 || (res == Integer.MIN_VALUE / 10 && (curr - '0' > -(Integer.MIN_VALUE % 10)))) {
            return Integer.MIN_VALUE;
        }

        // 8、没有超出范围，加上去
        res = res * 10 + sign * (curr - '0');
        index++;
    }
    return res;
}

3、014——最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

/**
 * 思路: 把数组第一个字符串作为比较对象,逐个遍历，并更新最大公共前缀
 */
public String longestCommonPrefix(String[] strs) {
    if (strs.length == 0) {
        return "";
    }
    String ans = strs[0];
    for (int i = 1; i < strs.length; i++) {
        int j = 0;
        for (; j < ans.length() && j < strs[i].length(); j++) {
            if (ans.charAt(j) != strs[i].charAt(j)) {
                break;
            }
        }
        ans = ans.substring(0, j);
        if (ans.equals("")) {
            return ans;
        }
    }
    return ans;
}

4、017——电话号码的字母组合

给定一个仅包含数字 2-9 的字符串，返回所有它能表示的字母组合。答案可以按 任意顺序 返回。

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

class Solution {
    String[] strMap = {" ", "*", "abc", "def", "ghi", "jkl", "mno", "pqrs", "tuv", "wxyz"};

    //最终输出结果的list
    List<String> res = new ArrayList<>();

    public List<String> letterCombinations(String digits) {
        if(digits==null || digits.length()==0) {
            return new ArrayList<>();
        }
        iterStr(digits, new StringBuilder(), 0);
        return res;
    }

    void iterStr(String str, StringBuilder letter, int index) {
        //递归的终止条件，注意这里的终止条件看上去跟动态演示图有些不同，主要是做了点优化
        //动态图中是每次截取字符串的一部分，"234"，变成"23"，再变成"3"，最后变成""，这样性能不佳
        //而用index记录每次遍历到字符串的位置，这样性能更好
        if (index == str.length()) {
            res.add(letter.toString());
            return;
        }

        //获取index位置的字符，假设输入的字符是"234"
        //第一次递归时index为0所以c=2，第二次index为1所以c=3，第三次c=4
        //subString每次都会生成新的字符串，而index则是取当前的一个字符，所以效率更高一点
        char c = str.charAt(index);

        int pos = c - '0';
        String mapping = strMap[pos];

        for (int i = 0; i < mapping.length(); i++) {
            // 添加第一个
            letter.append(mapping.charAt(i));
            // 递归下一层
            iterStr(str, letter, index + 1);
            letter.deleteCharAt(letter.length() - 1);
        }

    }
}

5、028——实现 strStr()

实现 strStr() 函数。

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串出现的第一个位置（下标从 0 开始）。如果不存在，则返回 -1 。

//1、暴力遍历
public static int strStr(String haystack, String needle) {
    if (haystack.length() == 0 || haystack.length() < needle.length()) {
        return -1;
    }
    if (needle.length() == 0) {
        return 0;
    }
    int index = 0;
    int cur = 0;
    boolean flag = false;
    while ((index + cur) < haystack.length() && cur < needle.length()) {
        if (haystack.charAt(index + cur) == needle.charAt(cur)) {
            cur++;
            flag = true;
        } else {
            index++;
            cur = 0;
            flag = false;
        }
    }
    if (flag && cur == needle.length()) {
        return index;
    } else {
        return -1;
    }
}


//2、KMP,找到目标串的最大公共前后缀，然后每次不匹配回溯到公共部分后面开始比较，减少比较次数
public static int strStr(String haystack, String needle) {
    if (needle.length() == 0) {
        return 0;
    }

    int[] nextArray = getNextArray(needle);
    int i = 0, j = 0;
    while (i < haystack.length() && j < needle.length()) {
        if (j == -1 || haystack.charAt(i) == needle.charAt(j)) {
            i++;
            j++;
        } else {
            j = nextArray[j];
        }
    }
    if (j == needle.length()) {
        return i - j;
    } else {
        return -1;
    }
}


private static int[] getNextArray(String str) {
    char[] chars = str.toCharArray();
    int[] next = new int[chars.length];
    next[0] = -1;
    if (chars.length < 2) {
        return next;
    }
    next[1] = 0;
    for (int i = 2; i < chars.length; i++) {
        int k = next[i - 1];
        while (k != -1) {
            if (chars[i - 1] == chars[k]) {
                next[i] = k + 1;
                break;
            } else {
                k = next[k];
            }
            next[i] = 0;
        }
    }
    return next;
}

6、038—— 外观数列

给定一个正整数 n ，输出外观数列的第 n 项。

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。

你可以将其视作是由递归公式定义的数字字符串序列：

countAndSay(1) = “1”
countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。

1. 1
   

2. 11
   

3. 21
   

4. 1211
   

5. 111221
   第一项是数字 1 
   描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 "11"
   描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 "21"
   描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 "1211"
   描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 "111221"
   

要 描述 一个数字字符串，首先要将字符串分割为 最小 数量的组，每个组都由连续的最多 相同字符 组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。

/**
 * 思路：设置递归的终止条件，当n=1,return "1"; 然后每次进来获取上一次的结果
 * 使用temp记录第一个值，用index记录遍历字符串的下标，count记录有多少个值和temp相等
 * 如果相等，index++,count++;如果不相等，把记录记下来。append(count).append(temp);
 * 然后更新temp的值为当前的index下标的值，count重置为1,index++;
 * 等最后跳出循环，把最后一次的结果加上
 */
public static String countAndSay(int n) {
    if (n == 1) {
        return "1";
    }
    String str = countAndSay(n - 1);
    StringBuilder sb = new StringBuilder();
    char[] chars = str.toCharArray();
    int temp = chars[0] - '0';
    int index = 1;
    int count = 1;
    while (index < str.length()) {
        if (chars[index] - '0' == temp) {
            index++;
            count++;
        } else {
            sb.append(count).append(temp);
            temp = chars[index++] - '0';
            count = 1;
        }
    }
    sb.append(count).append(temp);
    return sb.toString();
}

7、058——最后一个单词的长度

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中最后一个单词的长度。

单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

/**
 * 思路：到序遍历，使用一个标志位flag标记开始还是结束
 * 遇到' '且标志位flag为false,直接跳过，如果遇到非空串，falg设置为ture,表示可以
 * 计数，如果遇到' '，且flag为true,表示这个单词已经完毕，返回count
 */
public static int lengthOfLastWord(String s) {
    int count = 0;
    boolean flag = false;
    for (int i = s.length() - 1; i >= 0; i--) {
        if (s.charAt(i) == ' ') {
            if (flag) {
                break;
            }
        } else {
            flag = true;
            count++;
        }
    }
    return count;
}

8、067——二进制求和

给你两个二进制字符串，返回它们的和（用二进制表示）。

输入为 非空字符串且只包含数字 1 和 0。

/**
 * 思路：从后往前遍历，对应位置求和，使用temp记录是否要进1,
 * 如果其中一个字符串遍历完毕，则遍历另一个，把结果反转
 */
public static String addBinary(String a, String b) {
    int aRight = a.length() - 1;
    int bRight = b.length() - 1;
    int temp = 0;
    int sum = 0;
    StringBuilder sb = new StringBuilder();
    while (aRight >= 0 && bRight >= 0) {
        sum = a.charAt(aRight--) - '0' + b.charAt(bRight--) - '0' + temp;
        temp = sum / 2;
        sum = sum % 2;
        sb.append(sum);
    }
    while (aRight < 0 && bRight >= 0) {
        sum = b.charAt(bRight--) - '0' + temp;
        temp = sum / 2;
        sum = sum % 2;
        sb.append(sum);
    }
    while (bRight < 0 && aRight >= 0) {
        sum = a.charAt(aRight--) - '0' + temp;
        temp = sum / 2;
        sum = sum % 2;
        sb.append(sum);
    }
    if (temp != 0) {
        sb.append(temp);
    }
    return sb.reverse().toString();
}

9、068——文本左右对齐

给定一个单词数组 words 和一个长度 maxWidth ，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。

你应该使用 “贪心算法” 来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ’ ’ 填充，使得每行恰好有 maxWidth 个字符。

要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。

文本的最后一行应为左对齐，且单词之间不插入额外的空格。

public static List<String> fullJustify(String[] words, int maxWidth) {

    int length = 0;
    int index = 0;
    int begin = 0;
    List<String> res = new ArrayList<>();
    while (index < words.length) {
        length += words[index].length() + 1;
        // 如果是最后一个词，或者长度超长即可放在一行
        if (index + 1 == words.length || length + words[index + 1].length() > maxWidth) {
            // 对每个单词进行空格平均划分
            res.add(fillWords(words, begin, index, maxWidth, index + 1 == words.length));
            begin = index + 1;
            length = 0;
        }
        index++;
    }
    return res;
}


/**
     * 对每行单词进行空格平均划分
     */
public static String fillWords(String[] words, int bg, int ed, int maxWidth, boolean lastLne) {
    int wordCount = ed - bg + 1;
    // 除去每个单词的尾部空格(+1是因为每行最后一个不需要原本的空格，额外处理掉)
    int spaceCount = maxWidth + 1 - wordCount;

    for (int i = bg; i <= ed; i++) {
        spaceCount -= words[i].length();
    }
    // 词尾空格
    int spaceSuffix = 1;
    // 额外的空格平均数 = 总空格数 / 间隙数
    int spaceAvg = (wordCount == 1) ? 1 : spaceCount / (wordCount - 1);
    // 额外空格的余数
    int spaceExtra = (wordCount == 1) ? 0 : spaceCount % (wordCount - 1);
    // 填入单词
    StringBuilder sb = new StringBuilder();
    for (int i = bg; i < ed; i++) {
        sb.append(words[i]);
        if (lastLne) {
            sb.append(" ");
            continue;
        }
        int n = spaceSuffix + spaceAvg + (((i - bg) < spaceExtra ? 1 : 0));
        while (n-- > 0) {
            sb.append(" ");
        }
    }
    // 补上最后一个单词
    sb.append(words[ed]);
    // 补上这一行最后的空格
    int lastSpaceCnt = maxWidth - sb.length();
    while (lastSpaceCnt-- > 0) {
        sb.append(" ");
    }
    return sb.toString();
}

10、151——翻转字符串里的单词

给你一个字符串 s ，逐个翻转字符串中的所有 单词 。

单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。

请你返回一个翻转 s 中单词顺序并用单个空格相连的字符串。

/**
 * 思路：从后往前遍历，如果遇到的不为空格，记录下标，然后直到遇到空格（改单词遍历完毕）
 * 这里有个判断，一开始记录单词的StringBuilder为空，说明是第一个单词前面不需要加" "空格，
 * 然后将该单词加入StringBuilder，然后遇到空格直接跳过
 */
public String reverseWords1(String s) {
    int n = s.length();
    int i = n;
    StringBuffer sb = new StringBuffer();
    while (i > 0) {
        int j = i;
        while (i > 0 && s.charAt(i - 1) != ' ') {
            //i停在i=0或i-1=' ',i=字母
            i--;
        }
        if (sb.length() > 0) {
            sb.append(' ');
        }
        sb.append(s.substring(i, j));
        //因为可能是有连续的空格，所以用while一直移动，直到i=' ',i-1=字母
        while (i > 0 && s.charAt(i - 1) == ' ') {
            i--;
        }
    }
    return sb.toString();
}

11、165——比较版本号

给你两个版本号 version1 和 version2 ，请你比较它们。

版本号由一个或多个修订号组成，各修订号由一个 ‘.’ 连接。每个修订号由 多位数字 组成，可能包含 前导零 。每个版本号至少包含一个字符。修订号从左到右编号，下标从 0 开始，最左边的修订号下标为 0 ，下一个修订号下标为 1 ，以此类推。例如，2.5.33 和 0.1 都是有效的版本号。

比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较 忽略任何前导零后的整数值 。也就是说，修订号 1 和修订号 001 相等 。如果版本号没有指定某个下标处的修订号，则该修订号视为 0 。例如，版本 1.0 小于版本 1.1 ，因为它们下标为 0 的修订号相同，而下标为 1 的修订号分别为 0 和 1 ，0 < 1 。

返回规则如下：

• 如果 *version1* > *version2* 返回 1，
• 如果 *version1* < *version2* 返回 -1，
• 除此之外返回 0。

/**
 * 思路：根据'.'从左到右，区分不同级别的版本，然后进行比较
 */
public int compareVersion1(String v1, String v2) {
    int i = 0, j = 0;
    int n = v1.length(), m = v2.length();
    while(i < n || j < m)
    {
        int num1 = 0, num2 = 0;
        while(i < n && v1.charAt(i) != '.') {
            num1 = num1 * 10 + v1.charAt(i++) - '0';
        }
        while(j < m && v2.charAt(j) != '.') {
            num2 = num2 * 10 + v2.charAt(j++) - '0';
        }
        if(num1 > num2) {
            return 1;
        }
        else if( num1 < num2) {
            return -1;
        }
        i++;
        j++;
    }
    return 0;
}

12、344——反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题

/**
 * 思路：双指针，一个从左到右，一个从右到左
 */
public void reverseString(char[] s) {
    int left = 0;
    int right = s.length - 1;
    while (left < right) {
        char temp = s[left];
        s[left++] = s[right];
        s[right--] = temp;
    }
}