【LeetCode算法系列题解】第66~70题

LeetCode 66. 加一（简单）

【题目描述】

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位，数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。

【示例1】

输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。
1
2
3

【示例2】

输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。
1
2
3

【示例3】

输入：digits = [0]
输出：[1]
1
2

【提示】

$1\le digits.length\le 100$
$0\le digits[i]\le 9$

【分析】

---

简单的高精度模板题。

---

【代码】

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int t = 1;
        for (int i = digits.size() - 1; t && i >= 0; i--)
        {
            t += digits[i];
            digits[i] = t % 10;
            t /= 10;
        }
        if (t) digits.insert(digits.begin(), 1);
        return digits;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

LeetCode 67. 二进制求和（简单）

【题目描述】

给你两个二进制字符串 a 和 b，以二进制字符串的形式返回它们的和。

【示例1】

输入:a = "11", b = "1"
输出："100"
1
2

【示例2】

输入：a = "1010", b = "1011"
输出："10101"
1
2

【提示】

$1\le a.length,b.length\le 10^4$
a 和 b 仅由字符 '0' 或 '1' 组成
字符串如果不是 "0"，就不含前导零

【分析】

---

同样是高精度模板题，注意是二进制即可。

---

【代码】

class Solution {
public:
    string addBinary(string a, string b) {
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());
        string res;
        for (int i = 0, t = 0; i < a.size() || i < b.size() || t; i++)
        {
            if (i < a.size()) t += a[i] - '0';
            if (i < b.size()) t += b[i] - '0';
            res += to_string(t % 2);
            t /= 2;
        }
        reverse(res.begin(), res.end());
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

LeetCode 68. 文本左右对齐（困难）

【题目描述】

给定一个单词数组 words 和一个长度 maxWidth，重新排版单词，使其成为每行恰好有 maxWidth 个字符，且左右两端对齐的文本。
你应该使用贪心算法来放置给定的单词；也就是说，尽可能多地往每行中放置单词。必要时可用空格 ' ' 填充，使得每行恰好有 maxWidth 个字符。
要求尽可能均匀分配单词间的空格数量。如果某一行单词间的空格不能均匀分配，则左侧放置的空格数要多于右侧的空格数。
文本的最后一行应为左对齐，且单词之间不插入额外的空格。

注意：

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

【示例1】

输入: words = ["This", "is", "an", "example", "of", "text", "justification."], maxWidth = 16
输出:
[
   "This    is    an",
   "example  of text",
   "justification.  "
]
1
2
3
4
5
6
7

【示例2】

输入:words = ["What","must","be","acknowledgment","shall","be"], maxWidth = 16
输出:
[
  "What   must   be",
  "acknowledgment  ",
  "shall be        "
]
解释: 注意最后一行的格式应为 "shall be    " 而不是 "shall     be",
     因为最后一行应为左对齐，而不是左右两端对齐。       
     第二行同样为左对齐，这是因为这行只包含一个单词。
1
2
3
4
5
6
7
8
9
10

【示例3】

输入:words = ["Science","is","what","we","understand","well","enough","to","explain","to","a","computer.","Art","is","everything","else","we","do"]，maxWidth = 20
输出:
[
  "Science  is  what we",
  "understand      well",
  "enough to explain to",
  "a  computer.  Art is",
  "everything  else  we",
  "do                  "
]
1
2
3
4
5
6
7
8
9
10

【提示】

$1\le words.length\le 300$
$1\le words[i].length\le 20$
words[i] 由小写英文字母和符号组成
$1\le maxWidth\le 100$
$words[i].length\le maxWidth$

【分析】

---

假设我们有 $t$ 个空格需要添加，有 $c$ 个空位，由于需要尽可能平均地分配空格，因此每个空位至少需要有 $\lfloor \frac{t}{c}\rfloor$ 个空格，多出来的不能均匀分配的 $t\%c$ 个空格从左边开始依次加到每个空位中（每个空位加一个空格）。

还有需要注意当一行只有一个单词或者为最后一行时需要左对齐，在右边填充空格即可。

---

【代码】

class Solution {
public:
    vector<string> fullJustify(vector<string>& words, int maxWidth) {
        vector<string> res;
        for (int i = 0; i < words.size(); i++)
        {
            int len = words[i].size();  // 当前行的总长度，每个单词间有一个空格
            int j = i + 1;  // 一行能够放置最多单词的右边界
            while (j < words.size() && len + 1 + words[j].size() <= maxWidth)
                len += 1 + words[j].size(), j++;
            string line;
            if (j == i + 1 || j == words.size())  // 只有一个单词或者最后一行
            {
                line += words[i];
                for (int k = i + 1; k < j; k++) line += ' ' + words[k];
                while (line.size() < maxWidth) line += ' ';  // 长度不够在右边补空格
            }
            else  // 否则需要两端对齐
            {
                int c = j - i - 1, t = maxWidth - len + c;  // c表示空位数，t表示需要填充的空格数
                int k = 0;
                while (k < t % c) line += words[i + k] + string(t / c + 1, ' '), k++;
                while (k < c) line += words[i + k] + string(t / c, ' '), k++;
                line += words[i + k];  // 最后一个单词
            }
            res.push_back(line);
            i = j - 1;
        }
        return res;
    }
};
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

LeetCode 69. x 的平方根（简单）

【题目描述】

给你一个非负整数 x，计算并返回 x 的算术平方根。
由于返回类型是整数，结果只保留整数部分 ，小数部分将被舍去。
注意：不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5。

【示例1】

输入：x = 4
输出：2
1
2

【示例2】

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
1
2
3

【提示】

$0\le x\le 2^{31}-1$

【分析】

---

二分答案模板题，找出 $y^2\le x$ 的最大的 $y$ 即可，即我们每次在 $0\sim x$ 区间中二分出 $mid$，判断 $mid$ 是否大于等于 $x$。

---

【代码】

class Solution {
public:
    int mySqrt(int x) {
        int l = 0, r = x;
        while (l < r)
        {
            int mid = l + 1ll + r >> 1;  // 1ll防止l + r溢出
            // mid * mid <= x中可能会溢出，因此需要移一下位
            if (mid <= x / mid) l = mid;
            else r = mid -  1;
        }
        return r;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14

LeetCode 70. 爬楼梯（简单）

【题目描述】

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

【示例1】

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶
1
2
3
4
5

【示例2】

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶
1
2
3
4
5
6

【提示】

$1\le n\le 45$

【分析】

---

假设 f[i] 表示跳到第 $i$ 阶台阶的方法数，那么可以从第 $i-2$ 或 $i-1$ 阶台阶跳过来，即 f[i] = f[i - 2] + f[i - 1]，这个转移方程就是斐波那契数列，因此我们只需要用两个变量循环滚动即可。在起点的方法数为1，第一阶台阶只能从起点跳过来，因此方法数也为1，然后我们往后求解到第 $n-1$ 项即可。

---

【代码】

class Solution {
public:
    int climbStairs(int n) {
        int a = 1, b = 1;
        while (--n)  // --n只循环n-1次
        {
            int c = a + b;
            a = b, b = c;
        }
        return b;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12