35题：搜索插入位置

题目：

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

示例 1:
输入: nums = [1,3,5,6], target = 5
输出: 2

示例 2:
输入: nums = [1,3,5,6], target = 2
输出: 1

示例 3:
输入: nums = [1,3,5,6], target = 7
输出: 4

提示:

  • 1 <= nums.length <= 104
  • -104 <= nums[i] <= 104
  • nums 为 无重复元素 的 升序 排列数组
  • -104 <= target <= 104

分析：

题目要求使用时间复杂度为 O(log n) 的算法，那就是标准的二分查找

代码：

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
#include <iostream>
#include <vector>
using namespace std;

class Solution {
public:
    int searchInsert(vector<int>& nums, int target) {
        //如果数组为空，直接返回
        if (nums.empty()) {
            return 0;
        }
        //二分查找
        int right = nums.size() - 1;
        int left = 0;
        while (left <= right) {
            int mid = left + ((right - left) >> 1);
            if (target == nums[mid]) {
                return mid;
            }
            if (target > nums[mid]) {
                left = mid + 1;
            }
            else {
                right = mid - 1;
            }
        }
        return left;
    }
};

58题：最后一个单词的长度

题目：

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。
单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。

示例 1：
输入：s = "Hello World"
输出：5
解释：最后一个单词是“World”，长度为 5。

示例 2：
输入：s = " fly me to the moon " **输出**：4 **解释**：最后一个单词是“moon”`，长度为 4。

示例 3：
输入：s = "luffy is still joyboy"
输出：6
解释：最后一个单词是长度为 6 的“joyboy”

提示：

  • 1 <= s.length <= 104
  • s 仅有英文字母和空格 ' ' 组成
  • s 中至少存在一个单词

分析：

这个很简单，我竟然一下就写出来了。
直接从最后开始遍历即可，首先排除空的情况，然后遍历，找到非空的时候开始计数，直到找到下一个空格结束。

代码：

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
#include <iostream>
#include <string>
using namespace std;
class Solution {
public:
    int lengthOfLastWord(string s) {
        //从最后开始遍历
        int length = s.size();
        int i = 0;
        int count = 0;
        bool word = false;
        if (s.empty()) {
            return 0;
        }
        for (i = length - 1; i >= 0; i--) {
            if (s[i] != ' ') {
                count++;
                word = true;
            }
            else {
                if (word == true) {
                    return count;
                }
            }
        }
        return count;
    }
};

21题：合并两个有序链表

题目：

将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。 

示例 1：

输入：l1 = [1,2,4], l2 = [1,3,4]
输出：[1,1,2,3,4,4]

示例 2：
输入：l1 = [], l2 = []
输出：[]

示例 3：
输入：l1 = [], l2 = [0]
输出：[0]

提示：

  • 两个链表的节点数目范围是 [0, 50]
  • -100 <= Node.val <= 100
  • l1 和 l2 均按 非递减顺序 排列

分析：

该题套路也相对固定。
方法是：先建立一个空的节点，作为头节点，可以赋值为-1，然后用一个指针指向它；l1和l2分别指向两个要合并的链表的头，然后使用while循环，退出条件是其中一个链表被连接完，剩下的链表直接连接即可，然后返回开始设置头节点的next

代码：

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
#include <iostream>
using namespace std;
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
 
 class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        //创建一个辅助头节点
        ListNode* preHead = new ListNode(-1);
        ListNode* prev = preHead;

        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val < l2->val) {
                prev->next = l1;
                l1 = l1->next;
            }
            else {
                prev->next = l2;
                l2 = l2->next;
            }
            prev = prev->next;
        }

        prev->next = l1 == nullptr ? l2 : l1;
        return preHead->next;
    }
};

66题：加一

题目：

给定一个表示 大整数 的整数数组 digits，其中 digits[i] 是整数的第 i 位数字。这些数字按从左到右，从最高位到最低位排列。这个大整数不包含任何前导 0。

将大整数加 1，并返回结果的数字数组。

示例 1：
输入：digits = [1,2,3]
输出：[1,2,4]
解释：输入数组表示数字 123。
加 1 后得到 123 + 1 = 124。
因此，结果应该是 [1,2,4]。

示例 2：
输入：digits = [4,3,2,1]
输出：[4,3,2,2]
解释：输入数组表示数字 4321。
加 1 后得到 4321 + 1 = 4322。
因此，结果应该是 [4,3,2,2]。

示例 3：
输入：digits = [9]
输出：[1,0]
解释：输入数组表示数字 9。
加 1 得到了 9 + 1 = 10。
因此，结果应该是 [1,0]。

提示：

  • 1 <= digits.length <= 100
  • 0 <= digits[i] <= 9
  • digits 不包含任何前导 0

分析：

这个题目也比较简单。
题目只要求加1，那直接从最后一位开始判断即可，如果这个数是9，那么就这个数变为0，并往前移，再加1，一旦遇到某个数不用进位，就返回值。
如果一个数全是9，比如9999，那么前面的判断不会返回值，而是4个数全部变为0，这时候就需要在前面加1，使用vector的insert函数即可。

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int length = digits.size();
        int i = 0;
        for (i = length - 1; i >= 0; i--) {
            if (digits[i] < 9) {
                digits[i]++;
                return digits;
            }
            else {
                digits[i] = 0;
            }
        }
        //如果没有返回，说明所有数都是9，需要在开头插入1
        digits.insert(digits.begin(), 1);
        return digits;
    }
};

67题：二进制求和

题目：

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

示例 1：
输入:a = “11”, b = “1”
输出：”100”

示例 2：
输入：a = “1010”, b = “1011”
输出：”10101”

提示：

  • 1 <= a.length, b.length <= 104
  • a 和 b 仅由字符 '0' 或 '1' 组成
  • 字符串如果不是 "0" ，就不含前导零

分析：

题目本身不是很难，但是我写的很复杂，把自己绕晕了。
思路就是模拟人计算二进制的方法，要考虑到进位的问题。
整个的过程是这样，使用i,j指向两个字符的末尾，每成功计算一次，就进行i--,j--的操作，还要考虑到只有i>=0,j>=0，才能进行计算，也才能减，如果某一个或者两个同时不满足这个条件，两个值都要设置为0，如果此时还有进位，那么需要继续计算，如果没有进位，就停止。
如果有进位，就令carry=1，否则，令carry=0。
所以进入一个while循环，需要满足i>=0 || j>=0 || carry!=0中的任意一个条件，才能执行，最后就得到结果，由于是模拟人的方法，所以先得到的结果应该排在后面，所以最后需要进行一个逆置，使用string的inverse函数即可。

坑的点是，string中是字符，'0','1'是ASCII值，分别为48和49，需要注意，不能直接使用(int)强制转换类型。

代码：

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
#include <iostream>
#include <string>
#include <algorithm>//包含reverse函数
using namespace std;
//67题：二进制求和
class Solution {
public:
    string addBinary(string a, string b) {
        string result = "";//用于返回结果
        int i = a.size() - 1;
        int j = b.size() - 1;
        int carry = 0;

        while (i >= 0 || j >= 0 || carry != 0) {
            int bita = i >= 0 ? a[i] - '0' : 0;
            int bitb = j >= 0 ? b[j] - '0' : 0;
            int sum = bita + bitb + carry;//可能的结果有0，1，2，3

            //计算当前位的结果，添加到result中
            result += sum % 2 + '0'; //若sum为0或2，该位的计算结果就是0，给result返回0即可，恰好对应sum%2的值

            //计算进位的结果
            carry = sum / 2; //若sum为2或3，就有进位，给carry返回1，正好对应sum/2的结果

            //如果i，j没有到头，就可以进行--，当i或j为负值的时候，前面对应的bit就恒为0，符合需要
            if (i >= 0)i--;
            if (j >= 0)j--;
        }
        //循环结束，需要逆置得到结果
        reverse(result.begin(), result.end());

        return result;
    }
};