字符串：实现

0006. Z 字形变换 (opens new window)

题目

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

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

P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

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

string convert(string s, int numRows);

示例 1：

输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

示例 2：

输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

示例 3：

输入：s = "A", numRows = 1
输出："A"

提示：

• 1 <= s.length <= 1000
• s 由英文字母（小写和大写）、',' 和 '.' 组成
• 1 <= numRows <= 1000

解析

使用一个数组存储每一行的字符串，在遍历过程中将每个字符拼接到数组对应行的字符串中。

代码

class Solution {
public:
    string convert(string s, int numRows) {
        if (numRows == 1) return s;
        vector<string> rows(numRows, "");
        bool down = false;
        for (int i = 0, row = 0; i < s.length(); i++) {
            rows[row] += s[i];
            if (row == 0 || row == numRows - 1) down = !down;
            row += down ? 1 : -1;
        }
        string ans = "";
        for (int i = 0; i < numRows; i++) ans += rows[i];
        return ans;
    }
};

func convert(s string, numRows int) (ans string) {
    if numRows == 1 {
        ans = s
        return
    }
    rows := make([]string, numRows)
    row, down := 0, false
    for _, c := range s {
        rows[row] += string(c)
        if row == 0 || row == numRows-1 {
            down = !down
        }
        if down {
            row++
        } else {
            row--
        }
    }
    for i := range rows {
        ans += rows[i]
    }
    return
}

class Solution:
    def convert(self, s: str, numRows: int) -> str:
        if numRows == 1:
            return s
        rows = [""] * numRows
        i, row, down = 0, 0, False
        for i in range(len(s)):
            rows[row] += s[i]
            if row == 0 or row == numRows - 1:
                down = not down
            row += 1 if down else -1
        ans = ""
        for row in rows:
            ans += row
        return ans

0012. 整数转罗马数字 (opens new window)

题目

罗马数字包含以下七种字符： I， V， X， L，C，D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

• I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
• X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
• C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给你一个整数，将其转为罗马数字。

示例 1:

输入: num = 3
输出: "III"

示例 2:

输入: num = 4
输出: "IV"

示例 3:

输入: num = 9
输出: "IX"

示例 4:

输入: num = 58
输出: "LVIII"
解释: L = 50, V = 5, III = 3.

示例 5:

输入: num = 1994
输出: "MCMXCIV"
解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示：

• 1 <= num <= 3999

解析

硬编码数字，每一位单独处理。

代码

class Solution {
public:
    string intToRoman(int num) {
        string thousands[] = {"", "M", "MM", "MMM"};
        string hundreds[] = {"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"};
        string tens[] = {"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"};
        string ones[] = {"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"};
        return thousands[num / 1000] + hundreds[num % 1000 / 100] + tens[num % 100 / 10] + ones[num % 10];
    }
};

func intToRoman(num int) string {
    thousands := []string{"", "M", "MM", "MMM"}
    hundreds := []string{"", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"}
    tens := []string{"", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"}
    ones := []string{"", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"}
    return thousands[num/1000] + hundreds[num%1000/100] + tens[num%100/10] + ones[num%10]
}

class Solution:
    def intToRoman(self, num: int) -> str:
        thousands = ["", "M", "MM", "MMM"]
        hundreds = ["", "C", "CC", "CCC", "CD", "D", "DC", "DCC", "DCCC", "CM"]
        tens = ["", "X", "XX", "XXX", "XL", "L", "LX", "LXX", "LXXX", "XC"]
        ones = ["", "I", "II", "III", "IV", "V", "VI", "VII", "VIII", "IX"]
        return thousands[num // 1000] + hundreds[num % 1000 // 100] + tens[num % 100 // 10] + ones[num % 10]

0013. 罗马数字转整数 (opens new window)

题目

罗马数字包含以下七种字符: I， V， X， L，C，D 和 M。

字符          数值
I             1
V             5
X             10
L             50
C             100
D             500
M             1000

例如， 罗马数字 2 写做 II ，即为两个并列的 1 。12 写做 XII ，即为 X + II 。 27 写做 XXVII, 即为 XX + V + II 。

通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 IIII，而是 IV。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 IX。这个特殊的规则只适用于以下六种情况：

• I 可以放在 V (5) 和 X (10) 的左边，来表示 4 和 9。
• X 可以放在 L (50) 和 C (100) 的左边，来表示 40 和 90。
• C 可以放在 D (500) 和 M (1000) 的左边，来表示 400 和 900。

给定一个罗马数字，将其转换成整数。

示例 1:

输入: s = "III"
输出: 3

示例 2:

输入: s = "IV"
输出: 4

示例 3:

输入: s = "IX"
输出: 9

示例 4:

输入: s = "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.

示例 5:

输入: s = "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.

提示：

• 1 <= s.length <= 15
• s 仅含字符 ('I', 'V', 'X', 'L', 'C', 'D', 'M')
• 题目数据保证 s 是一个有效的罗马数字，且表示整数在范围 [1, 3999] 内
• 题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
• IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。
• 关于罗马数字的详尽书写规则，可以参考 罗马数字 - Mathematics (opens new window) 。

解析

遍历罗马数字，逐个处理，若当前数字小于右侧数字，则减去对应数值；否则，累加对应数值。

代码

class Solution {
public:
    int romanToInt(string s) {
        unordered_map<char, int> value = {
            {'I', 1}, {'V', 5}, {'X', 10}, {'L', 50},
            {'C', 100}, {'D', 500}, {'M', 1000}
        };
        int ans = 0;
        for (int i = 0; i < s.length(); i++) {
            if (i + 1 < s.length() && value[s[i]] < value[s[i + 1]]) {
                ans -= value[s[i]];
            } else {
                ans += value[s[i]];
            }
        }
        return ans;
    }
};

func romanToInt(s string) (ans int) {
    value := map[byte]int{
        'I': 1, 'V': 5, 'X': 10, 'L': 50,
        'C': 100, 'D': 500, 'M': 1000,
    }
    for i := 0; i < len(s); i++ {
        if i+1 < len(s) && value[s[i]] < value[s[i+1]] {
            ans -= value[s[i]]
        } else {
            ans += value[s[i]]
        }
    }
    return
}

class Solution:
    def romanToInt(self, s: str) -> int:
        value = {
            'I': 1, 'V': 5, 'X': 10, 'L': 50,
            'C': 100, 'D': 500, 'M': 1000,
        }
        ans = 0
        for i in range(len(s)):
            if i + 1 < len(s) and value[s[i]] < value[s[i + 1]]:
                ans -= value[s[i]]
            else:
                ans += value[s[i]]
        return ans

0068. 文本左右对齐 (opens new window)

题目

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

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

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

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

说明:

• 单词是指由非空格字符组成的字符序列。
• 每个单词的长度大于 0，小于等于 maxWidth。
• 输入单词数组 words 至少包含一个单词。

解析

1. 根据单词长度确定每行选择的单词；
2. 对每行单词进行空格填充。

代码

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> ans, cur;
        for (int i = 0, curWidth = 0; i < words.size(); i++) {
            if (words[i].length() + curWidth + cur.size() <= maxWidth) {
                curWidth += words[i].length();
                cur.push_back(words[i]);
            } else {
                ans.push_back(fillSpace(cur, maxWidth, false));
                cur = vector<string>{words[i]};
                curWidth = words[i].length();
            }
        }
        ans.push_back(fillSpace(cur, maxWidth, true));
        return ans;
    }

    string fillSpace(vector<string>& words, int maxWidth, bool last) {
        int curWidth = 0;
        for (int i = 0; i < words.size(); i++) {
            if (i != words.size() - 1) words[i] += ' ';
            curWidth += words[i].length();
        }
        if (last || words.size() == 1) {
            words[words.size() - 1] += string(maxWidth - curWidth, ' ');
        } else {
            for (int i = 0; curWidth++ < maxWidth; i = (i + 1) % (words.size() - 1)) {
                words[i] += ' ';
            }
        }
        string ans;
        for (int i = 0; i < words.size(); i++) ans += words[i];
        return ans;
    }
};

0157. 用 Read4 读取 N 个字符 (opens new window)

题目

解析

代码

0158. 用 Read4 读取 N 个字符 II (opens new window)

题目

解析

代码

0179. 最大数 (opens new window)

题目

解析

代码

0243. 最短单词距离 (opens new window)

题目

解析

代码

0245. 最短单词距离 III (opens new window)

题目

解析

代码

0246. 中心对称数 (opens new window)

题目

解析

代码

0247. 中心对称数 II (opens new window)

题目

解析

代码

0248. 中心对称数 III (opens new window)

题目

解析

代码

0271. 字符串的编码与解码 (opens new window)

题目

解析

代码

0273. 整数转换英文表示 (opens new window)

题目

解析

代码

0293. 翻转游戏 (opens new window)

题目

解析

代码

0294. 翻转游戏 II (opens new window)

题目

解析

代码

0408. 有效单词缩写 (opens new window)

题目

解析

代码

0418. 屏幕可显示句子的数量 (opens new window)

题目

解析

代码

0420. 强密码检验器 (opens new window)

题目

解析

代码

0422. 有效的单词方块 (opens new window)

题目

解析

代码

0443. 压缩字符串 (opens new window)

题目

解析

代码

0459. 重复的子字符串 (opens new window)

题目

解析

代码

0468. 验证IP地址 (opens new window)

题目

解析

代码

0520. 检测大写字母 (opens new window)

题目

解析

代码

0522. 最长特殊序列 II (opens new window)

题目

解析

代码

0537. 复数乘法 (opens new window)

题目

解析

代码

0544. 输出比赛匹配对 (opens new window)

题目

解析

代码

0551. 学生出勤记录 I (opens new window)

题目

解析

代码

0553. 最优除法 (opens new window)

题目

解析

代码

0555. 分割连接字符串 (opens new window)

题目

解析

代码