本文为记录自己学习算法的过程

[28]实现 strStr()

实现strStr()函数。

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

说明：

当needle是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。

对于本题而言，当needle是空字符串时我们应当返回0。这与 C 语言的strstr()以及Java的indexOf()定义相符。

示例 1：

1
2
输入：haystack = "hello", needle = "ll"
输出：2

示例 2：

1
2
输入：haystack = "aaaaa", needle = "bba"
输出：-1

示例 3：

1
2
输入：haystack = "", needle = ""
输出：0

提示：

  • $1 <= haystack.length, needle.length <= 10^4$
  • haystack和needle仅由小写英文字符组成

题解：

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
class Solution {
public:
    int strStr(string haystack, string needle) {
        if (needle.length() == 0) {//needle长度等于0直接返回0
            return 0;
        }
        int index = -1;//定义需要返回的下标
        //遍历haystack字符串
        for (int i = 0; i < haystack.length(); ++i) {
            //找到needle字符中的第一个字符在haystack字符串中出现的第一个位置
            if (haystack[i] == needle[0]) {
                int j = 0;
                //遍历needle字符串判断从haystack字符串第i个字符开始后面是否都匹配
                for (j = 0; j < needle.length(); ++j) {
                    //有一个不匹配就break
                    if (haystack[i + j] != needle[j]) {
                        break;
                    }
                }
                //如果都匹配了说明下标j遍历到了needle字符串的最后一个位置
                if (j == needle.length()) {
                    index = i;//index记录改变为i
                    break;//此时找到了不需要进行遍历了
                }
            }
        }
        return index;//返回index
    }
};

思路：

这题主要考察的就是字符串的匹配，其实在数据结构这门课程里面学习过KMP算法，但是学习不精看到可以想到要使用这个算法，但是不知道怎么写，所以使用的是另一种自己单纯想到的算法，下面就来描述下自己的想法。

首先根据题意判断如果needle字符串为空串就返回0。定义一个index记录匹配haystack字符串开始的位置，初始值设置成-1，因为找不到也是返回-1，并且字符串下标是从0开始的，所以不会冲突。直接遍历haystack字符串，找到出现了某个字符与needle字符串第一个字符匹配的情况，此时就开始同时遍历needle和haystack，判断每个字符是否都相等，如果都相等就将index记录成当前在haystack字符串匹配的第i个位置并且跳出循环表示已经找到，否则继续找。

LeetCode题解

方法一：暴力匹配

思路及算法

我们可以让字符串needle与字符串haystack的所有长度为m的子串均匹配一次。

为了减少不必要的匹配，我们每次匹配失败即立刻停止当前子串的匹配，对下一个子串继续匹配。如果当前子串匹配成功，我们返回当前子串的开始位置即可。如果所有子串都匹配失败，则返回−1。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        for (int i = 0; i + m <= n; i++) {
            bool flag = true;
            for (int j = 0; j < m; j++) {
                if (haystack[i + j] != needle[j]) {
                    flag = false;
                    break;
                }
            }
            if (flag) {
                return i;
            }
        }
        return -1;
    }
};
作者：LeetCode-Solution

方法二：Knuth-Morris-Pratt（KMP） 算法*

思路及算法

KMP算法见我的理解之KMP算法

如何解决本题

记字符串haystack的长度为n，字符串needle的长度为m。

我们记字符串str=needle+#+haystack，即将字符串needle和haystack进行拼接，并用不存在于两串中的特殊字符#将两串隔开，然后我们对字符串str求前缀函数。

因为特殊字符#的存在，字符串str中haystack部分的前缀函数所对应的真前缀必定落在字符串needle部分，真后缀必定落在字符串haystack部分。当haystack部分的前缀函数值为m时，我们就找到了一次字符串needle在字符串haystack中的出现（因为此时真前缀恰为字符串needle）。

实现时，我们可以进行一定的优化，包括：

  1. 我们无需显式地创建字符串str。

    • 为了节约空间，我们只需要顺次遍历字符串needle、特殊字符#和字符串haystack即可。

  2. 也无需显式地保存所有前缀函数的结果，而只需要保存字符串needle部分的前缀函数即可。

    • 特殊字符#的前缀函数必定为0，且易知π(i)≤m（真前缀不可能包含特殊字符#）。
    • 这样我们计算π(i)时，j=π(π(π(…)−1)−1)的所有的取值中仅有π(i−1)的下标可能大于等于m。我们只需要保存前一个位置的前缀函数，其它的j的取值将全部为字符串needle部分的前缀函数。

  3. 我们也无需特别处理特殊字符#，只需要注意处理字符串haystack的第一个位置对应的前缀函数时，直接设定j的初值为0即可。

这样我们可以将代码实现分为两部分：

  1. 第一部分是求needle部分的前缀函数，我们需要保留这部分的前缀函数值。
  2. 第二部分是求haystack部分的前缀函数，我们无需保留这部分的前缀函数值，只需要用一个变量记录上一个位置的前缀函数值即可。当某个位置的前缀函数值等于m时，说明我们就找到了一次字符串needle在字符串haystack中的出现（因为此时真前缀恰为字符串needle，真后缀为以当前位置为结束位置的字符串haystack的子串），我们计算出起始位置，将其返回即可。
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
class Solution {
public:
    int strStr(string haystack, string needle) {
        int n = haystack.size(), m = needle.size();
        if (m == 0) {
            return 0;
        }
        vector<int> pi(m);
        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && needle[i] != needle[j]) {
                j = pi[j - 1];
            }
            if (needle[i] == needle[j]) {
                j++;
            }
            pi[i] = j;
        }
        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && haystack[i] != needle[j]) {
                j = pi[j - 1];
            }
            if (haystack[i] == needle[j]) {
                j++;
            }
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }
};
作者：LeetCode-Solution

[35]搜索插入位置

给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。

请必须使用时间复杂度为O(log n)的算法。

示例 1:

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

示例 2:

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

示例 3:

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

提示:

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

题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int searchInsert(vector<int> &nums, int target) {
        //这题就是二分查找的改造
        int low = 0;//low指针指向前面的元素
        int high = nums.size() - 1;//high指针指向后面的元素
        int mid;//mid指针指向low和high指针的中间
        while (low <= high) {//low指针和high指针没有相遇
            mid = (low + high) / 2;//mid指向low和high的中间
            if (nums[mid] < target) {//mid指向的元素小于目标值
                low = mid + 1;//说明target只可能出现在mid和high的中间
            }
            if (nums[mid] > target) {//mid指向的元素大于目标值
                high = mid - 1;//说明target只可能出现在mid和low的中间
            }
            if (nums[mid] == target) {//找到了，直接返回目标值的位置
                return mid;
            }
        }
        return high + 1;//说明在数组最终没有这个元素，返回最靠近这个元素的后一个位置
    }
};

思路：

这题其实主要考察的就是二分查找，所以拿到手看到查找就想到直接遍历一遍就可以了，但是看到要求是O(log n)的时间复杂度，就知道了这题目考察的应该就是二分查找了，所以还是比较容易上手的。

二分查找解释：首先，假设表中元素是按升序排列，将表中间位置记录的关键字与查找关键字比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果中间位置记录的关键字大于查找关键字，则进一步查找前一子表，否则进一步查找后一子表。重复以上过程，直到找到满足条件的记录，使查找成功，或直到子表不存在为止，此时查找不成功。

在这题中我们就是完全按照二分查找的思路进行就可以了，找到就直接返回就可以了。不过在找不到的时候，我们需要进行分析下返回的是什么值。在这题中，如果找不到我们需要返回这个元素应该插入的位置。由于遍历的时候low指针只有大于等于high指针的时候才进行返回，所以这个元素当找不到的时候，插入的位置就是high指针指向的后一个位置，所以我们需要返回的是high+1。

LeetCode题解类似就不做介绍了

[53]最大子数组和

给你一个整数数组nums，请你找出一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

子数组是数组中的一个连续部分。

示例 1：

1
2
3
输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
输出：6
解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。

示例 2：

1
2
输入：nums = [1]
输出：1

示例 3：

1
2
输入：nums = [5,4,-1,7,8]
输出：23

提示：

  • $1 <= nums.length <= 10^5$

    $-10^4 <= nums[i] <= 10^4$

题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int maxSubArray(vector<int> &nums) {
        int dp = 0;//记录变化的值，更新作用
        int max = nums[0];//记录最大值
        for (int i = 0; i < nums.size(); ++i) {
            if (dp + nums[i] > nums[i]) {//dp加上当前值大于当前值，说明加上这个值会产生最大值
                dp += nums[i];
            } else {//dp加上当前值小于当前值，说明前面的值只会导致更小，需要舍弃
                dp = nums[i];
            }
            if (max < dp) {//变化最大值
                max = dp;
            }
        }
        return max;
    }
};

思路：

这题目考察的就是动态规划，不过一般的方法也可以求出来，但是就不是O(n)的时间复杂度了。所以在这题还是需要使用动态规划。

这题目由于不需要返回最大子数组是说明，所以利用这个特点，思路就是用dp记录局部最优值，用max记录全局最优值。每遍历一个新元素时，判断（已遍历的连续子数组的和）加上（当前元素值），与（当前元素值）对比谁更大。

①如果已遍历的连续子数组的和 + 当前元素值 >= 当前元素值说明（已遍历的连续子数组的和）是大于等于0的，令dp= 已遍历的连续子数组的和 + 当前元素值。

②如果已遍历的连续子数组的和 + 当前元素值 < 当前元素值说明（已遍历的连续子数组的和）是小于0的，加上这部分只会拖累当前元素，故应该直接抛弃掉这部分，令dp= 当前元素值。

③对比dp和max，如果dp更大，则更新到max中。

这样就可以完成搜寻到最大子数组和了。

LeetCode题解

方法一：动态规划

思路和算法

思路和上述一致

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int pre = 0, maxAns = nums[0];
        for (const auto &x: nums) {
            pre = max(pre + x, x);
            maxAns = max(maxAns, pre);
        }
        return maxAns;
    }
};
作者：LeetCode-Solution

方法二：分治

思路和算法

这个分治方法类似于「线段树求解最长公共上升子序列问题」的 pushUp 操作。 也许读者还没有接触过线段树，没有关系，方法二的内容假设你没有任何线段树的基础。当然，如果读者有兴趣的话，推荐阅读线段树区间合并法解决多次询问的「区间最长连续上升序列问题」和「区间最大子段和问题」，还是非常有趣的。

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
class Solution {
public:
    struct Status {
        int lSum, rSum, mSum, iSum;
    };

    Status pushUp(Status l, Status r) {
        int iSum = l.iSum + r.iSum;
        int lSum = max(l.lSum, l.iSum + r.lSum);
        int rSum = max(r.rSum, r.iSum + l.rSum);
        int mSum = max(max(l.mSum, r.mSum), l.rSum + r.lSum);
        return (Status) {lSum, rSum, mSum, iSum};
    };

    Status get(vector<int> &a, int l, int r) {
        if (l == r) {
            return (Status) {a[l], a[l], a[l], a[l]};
        }
        int m = (l + r) >> 1;
        Status lSub = get(a, l, m);
        Status rSub = get(a, m + 1, r);
        return pushUp(lSub, rSub);
    }

    int maxSubArray(vector<int>& nums) {
        return get(nums, 0, nums.size() - 1).mSum;
    }
};
作者：LeetCode-Solution

[58]最后一个单词的长度

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

题解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int lengthOfLastWord(string s) {
        int start = 0;//最后一个单词起始位置
        int end = 0;//最后一个单词结束位置
        //遍历s
        for (int i = s.length() - 1; i >= 0; i--) {
            if (start != 0 && s[i] == ' ') {//已经定位了start，记录单词的结束位置
                end = i;
                break;
            }
            if (s[i] != ' ' && start == 0) {//记录单词起始位置
                start = i;
            }
        }
        if (end == 0 && s[end] != ' ') {//可能s就只有一个单词并且s中第一个字符不是空格
            return start + 1;
        }
        //包括第一个符号是空格的情况和其他情况
        return start - end;
    }
};

思路：

这题目就是单纯的找最后一个单词，所以在思考的时候的想法还是比较简单的，一开始想的是直接正则表达式，但是不知道C++怎么写（Java曾经使用过）。所以就是想到最基本的方法，不过也还比较简单。

主要就是遍历字符串（从后面开始遍历，因为记录最后一个单词的长度），首先定义一个变量start记录字符串最后一个单词出现的最后一个字母，然后向前走，找到这个单词结束的位置并记录下来退出循环。如果没有找到这个最后一个单词前面的空格那就说明s字符串就是一个单词，所以我们这里有个判断end结指向的位置是否是第一个并且这个位置是字母还是空格，是字母就直接返回start+1（这里可以自己假设字符串“str ”和“ str”），否则返回start-end；

LeetCode题解类似

[66]加一

给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。

最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。

你可以假设除了整数 0 之外，这个整数不会以零开头。

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 1 <= digits.length <= 100
  • 0 <= digits[i] <= 9

题解：

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
class Solution {
public:
    vector<int> plusOne(vector<int> &digits) {
        bool flag = false;//标记最高位是否有进位
        digits[digits.size() - 1] += 1;//让最低位加1
        for (int i = digits.size() - 1; i >= 0; i--) {
            if (i == 0 && digits[i] >= 10) {//判断最高位是否需要进位
                digits[i] %= 10;//需要进位
                flag = true;//标记进位
                break;
            }
            if (digits[i] >= 10) {//对每个数位进行判断进位操作
                digits[i - 1] += 1;
                digits[i] %= 10;
            }
        }
        vector<int> newDigits;
        if (flag) {
            newDigits.push_back(1);//需要进位，先让最高位等于1
        }
        for (int i = 0; i < digits.size(); ++i) {
            newDigits.push_back(digits[i]);//将剩余数字填入新的数组
        }
        return newDigits;
    }
};

思路：

这题就是单纯的考察进位操作，所以还是比较的简单的。

主要的思路就是将最低位数字加1，然后从最低位数字开始遍历，如果需要进位，就让后面的数字进行加1（这里利用的是数组的特点，可以保存int型数据，大于10也没有关系），对于最高位数字就需要额外判断。如果最高位需要进位就在新的数组里面先放数字1再将digits数组里面的数字放进新的需要返回的数组，否则就直接将digits数组放进新的数组里面。

LeetCode题解

方法一：找出最长的后缀 99

思路

当我们对数组digits加一时，我们只需要关注digits的末尾出现了多少个9即可。我们可以考虑如下的三种情况：

  • 如果digits的末尾没有9，例如[1,2,3]，那么我们直接将末尾的数加一，得到[1,2,4]并返回；

  • 如果digits的末尾有若干个9，例如[1,2,3,9,9]，那么我们只需要找出从末尾开始的第一个不为9的元素，即3，将该元素加一，得到[1,2,4,9,9]。随后将末尾的9全部置零，得到[1,2,4,0,0]并返回。

  • 如果digits的所有元素都是9，例如[9,9,9,9,9]，那么答案为[1,0,0,0,0,0]。我们只需要构造一个长度比digits多1的新数组，将首元素置为1，其余元素置为0即可。

算法

我们只需要对数组digits进行一次逆序遍历，找出第一个不为9的元素，将其加一并将后续所有元素置零即可。如果digits中所有的元素均为9，那么对应着「思路」部分的第三种情况，我们需要返回一个新的数组。

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int n = digits.size();
        for (int i = n - 1; i >= 0; --i) {
            if (digits[i] != 9) {
                ++digits[i];
                for (int j = i + 1; j < n; ++j) {
                    digits[j] = 0;
                }
                return digits;
            }
        }

        // digits 中所有的元素均为 9
        vector<int> ans(n + 1);
        ans[0] = 1;
        return ans;
    }
};
作者：LeetCode-Solution

[67]二进制求和

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

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

示例 1:

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

示例 2:

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

提示：

  • 每个字符串仅由字符'0'或'1'组成。
  • $1 <= a.length, b.length <= 10^4$
  • 字符串如果不是"0"，就都不含前导零。

题解：

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
class Solution {
public:
    string addBinary(string a, string b) {
        //从后往前操作字符相加，最后进行翻转就可以了
        int i = a.length() - 1, j = b.length() - 1;
        char carry = '0';//进位数
        string result = "";
        bool flag;
        while (i >= 0 && j >= 0) {
            //分四种情况讨论
            flag = true;
            //说明要进位，当前这个位置上的数字说明是1
            if (a[i] + b[j] + carry - '0' - '0' == '3') {
                carry = '1';
                result += "1";
                flag = false;
            }
            //说明要进位，当前这个位置上的数字说明是0
            if (a[i] + b[j] + carry - '0' - '0' == '2' && flag) {
                carry = '1';
                result += "0";
                flag = false;
            }
            //说明不要进位，当前这个位置上的数字说明是1
            if (a[i] + b[j] + carry - '0' - '0' == '1' && flag) {
                carry = '0';
                result += "1";
                flag = false;
            }
            //说明不要进位，当前这个位置上的数字说明是0
            if (a[i] + b[j] + carry - '0' - '0' == '0' && flag) {
                carry = '0';
                result += "0";
            }
            i--;
            j--;
        }
        //此时还有一串字符没有遍历完进行最后操作
        //i指向的字符串没有遍历完
        while (i >= 0) {
            flag = true;
            //和上述进位判断类似，由于只有两个数字相加只需要判断2，1，0三种情况
            if (a[i] + carry - '0' == '2') {
                carry = '1';
                result += "0";
                flag = false;
            }
            if (a[i] + carry - '0' == '1' && flag) {
                carry = '0';
                result += "1";
                flag = false;
            }
            if (a[i] + carry - '0' == '0' && flag) {
                carry = '0';
                result += "0";
                flag = false;
            }
            i--;
        }
        //j指向的字符串没有遍历完
        while (j >= 0) {
            flag = true;
            if (b[j] + carry - '0' == '2') {
                carry = '1';
                result += "0";
                flag = false;
            }
            if (b[j] + carry - '0' == '1' && flag) {
                carry = '0';
                result += "1";
                flag = false;
            }
            if (b[j] + carry - '0' == '0' && flag) {
                carry = '0';
                result += "0";
                flag = false;
            }
            j--;
        }
        //最后还要进位一个数字，就加上1
        if (carry == '1') {
            result += "1";
        }
        string ans;
        //翻转字符串
        for (int k = result.length() - 1; k >= 0; k--) {
            ans += result[k];
        }
        return ans;
    }
};

思路：

这题目就是直接进行字符的相加就可以，一开始不过都会想到进行转化成数字，但是想想这样子的操作太麻烦了，所以想到的就是直接进行字符的相加。

思路就是从末尾开始相加，对每个字符进行相加，并且加个carry进位的char类型的符号，一开始设定字符为0表示不用进位，当需要进位的时候就将它设置为1。由于可能两串字符串的长度可能不同，所以最后还需要进行遍历没有遍历完的字符串，进行最后的操作。在这里需要注意的是为了每个位置对应的相加操作只进行一次，所以我们加了个标志位flag，防止由于carry的改变导致再次进入后面的if判断进行再次的相加操作。

LeetCode题解

方法一：模拟

思路和算法

我们可以借鉴「列竖式」的方法，末尾对齐，逐位相加。在十进制的计算中「逢十进一」，二进制中我们需要「逢二进一」。

具体的，我们可以取n=max{∣a∣,∣b∣}，循环n次，从最低位开始遍历。我们使用一个变量carry表示上一个位置的进位，初始值为0。记当前位置对其的两个位为 $a_i$ 和 $b_i$，则每一位的答案为 $(carry+a_i +b_i )mod2$，下一位的进位为⌊$\frac{carry+a_i+a_j}{2}$ ⌋。重复上述步骤，直到数字a和b的每一位计算完毕。最后如果carry的最高位不为0，则将最高位添加到计算结果的末尾。

注意，为了让各个位置对齐，你可以先反转这个代表二进制数字的字符串，然后低下标对应低位，高下标对应高位。当然你也可以直接把a和b中短的那一个补0直到和长的那个一样长，然后从高位向低位遍历，对应位置的答案按照顺序存入答案字符串内，最终将答案串反转。这里的代码给出第一种的实现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    string addBinary(string a, string b) {
        string ans;
        reverse(a.begin(), a.end());
        reverse(b.begin(), b.end());

        int n = max(a.size(), b.size()), carry = 0;
        for (size_t i = 0; i < n; ++i) {
            carry += i < a.size() ? (a.at(i) == '1') : 0;
            carry += i < b.size() ? (b.at(i) == '1') : 0;
            ans.push_back((carry % 2) ? '1' : '0');
            carry /= 2;
        }

        if (carry) {
            ans.push_back('1');
        }
        reverse(ans.begin(), ans.end());

        return ans;
    }
};
作者：LeetCode-Solution

方法二：位运算

思路和算法

我们可以设计这样的算法来计算：

  • 把a和b转换成整型数字x和y，在接下来的过程中，x保存结果，y保存进位。

  • 当进位不为0时

    • 计算当前x和y的无进位相加结果：answer = x ^ y

    • 计算当前x和y的进位：carry = (x & y) << 1

    • 完成本次循环，更新x = answer，y = carry

  • 返回x的二进制形式

为什么这个方法是可行的呢？在第一轮计算中，answer的最后一位是x和y相加之后的结果，carry的倒数第二位是x和y最后一位相加的进位。接着每一轮中，由于carry是由x和y按位与并且左移得到的，那么最后会补零，所以在下面计算的过程中后面的数位不受影响，而每一轮都可以得到一个低 ii 位的答案和它向低i + 1位的进位，也就模拟了加法的过程。

1
2
3
4
5
6
7
8
9
class Solution:
    def addBinary(self, a, b) -> str:
        x, y = int(a, 2), int(b, 2)
        while y:
            answer = x ^ y
            carry = (x & y) << 1
            x, y = answer, carry
        return bin(x)[2:]
作者：LeetCode-Solution

[69]x的平方根

给你一个非负整数x，计算并返回x的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

注意：不允许使用任何内置指数函数和算符，例如pow(x, 0.5)或者x ** 0.5。

示例 1：

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

示例 2：

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

提示：

  • $0 <= x <= 2^{31} - 1$

题解：

方法一：投机取巧

1
2
3
4
5
6
7
class Solution {
public:
    int mySqrt(int x) {
        //直接开根号强制转换返回int数据类型，此时自定向下取整
        return (int) sqrt(x);
    }
};

方法二：二分查找

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
public:
    int mySqrt(int x) {
        if (x == 1) {//x是1就直接返回1
            return 1;
        }
        int low = 0, high = x;
        int mid;
        //利用二分法进行查找
        while (low < high) {
            mid = (low + high) / 2;
            if (mid <= x / mid && (mid + 1) > x / (mid + 1)) {//说明mid是那个解
                return mid;
            }
            if (mid < x / mid) {//说明解在mid和high之间
                low = mid;
            }
            if (mid > x / mid) {//说明解在mid和low之间
                high = mid;
            }
        }
        return 0;
    }
};

思路：

这题一开始拿到手还以为就是直接开根号出来进行直接取整就可以，后来看了下评论区发现那样子做其实并不好算是投机取巧了，所以就换了种方法写，也并不难，就相当于是二分法的变形吧。

思路主要就是每次折中进行查找，判断解会出现在哪个区间，就去那个区间进行查找，需要注意的是因为我们是进行向下取整的，所以我们需要在判断的时候判断mid <= x / mid && (mid + 1) > x / (mid + 1)，因为此时找到的是mid，不然解就出现在mid+1-high区间里面。

LeetCode题解

方法一：袖珍计算器算法

袖珍计算器算法」是一种用指数函数 $ \exp $ 和对数函数 $ \ln $ 代替平方根函数的方法。我们通过有限的可以使用的数学函数，得到我们想要计算的结果。

我们将 $\sqrt{x}$ 写成幂的形式 $ x^{1/2} $ ，再使用自然对数 $ e $ 进行换底，即可得到：

这样我们就可以得到 $\sqrt{x}$ 的值了。

注意：由于计算机无法存储浮点数的精确值（浮点数的存储方法可以参考IEEE 754，这里不再赘述），而指数函数和对数函数的参数和返回值均为浮点数，因此运算过程中会存在误差。例如当 $x=2147395600$ 时，$e^{\frac{1}{2} \ln x}$的计算结果与正确值 4634046340 相差 $10^{-11}$，这样在对结果取整数部分时，会得到 $46339$ 这个错误的结果。

因此在得到结果的整数部分 $\textit{ans}$ 后，我们应当找出 $\textit{ans}$ 与 $\textit{ans} + 1$ 中哪一个是真正的答案。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }
        int ans = exp(0.5 * log(x));
        return ((long long)(ans + 1) * (ans + 1) <= x ? ans + 1 : ans);
    }
};
作者：LeetCode-Solution

方法二：牛顿迭代

牛顿迭代法是一种可以用来快速求解函数零点的方法。

为了叙述方便，我们用$C$表示待求出平方根的那个整数。显然，$C$的平方根就是函数

的零点。

牛顿迭代法的本质是借助泰勒级数，从初始值开始快速向零点逼近。我们任取一个 $x0$ 作为初始值，在每一步的迭代中，我们找到函数图像上的点 $(x_i, f(x_i))$，过该点作一条斜率为该点导数$ f’(x_i)$ 的直线，与横轴的交点记为 $x{i+1}$ 。$x_{i+1}$ 相于 $x_i$ 而言距离零点更近。在经过多次迭代后，我们就可以得到一个距离零点非常接近的交点。下图给出了从 $x_0$ 开始迭代两次，得到 $x_1$ 和 $x_2$ 的过程。

牛顿迭代

算法

我们选择 $x_0 = C$ 作为初始值。在每一步迭代中，我们通过当前的交点 $x_i$，找到函数图像上的点 $(x_i, x_i^2 - C)$，作一条斜率为 $f’(x_i) = 2x_i$ 的直线，直线的方程为：

与横轴的交点为方程 $2xix - (x_i^2 + C) = 0$ 的解，即为新的迭代结果 $x{i+1}$x ：

在进行 $k$ 次迭代后，$x_k$ 的值与真实的零点 $\sqrt{C}$ 足够接近，即可作为答案。

细节

  • 为什么选择 $x_0 = C$ 作为初始值？

    • 因为 $y = x^2 - C$ 有两个零点 $-\sqrt{C}$ 和 $\sqrt{C}$ 。如果我们取的初始值较小，可能会迭代到 $-\sqrt{C}$ 这个零点，而我们希望找到的是 $\sqrt{C}$ 这个零点。因此选择 $x0 = C$ 作为初始值，每次迭代均有 $x{i+1} < x_i$，零点 $\sqrt{C}$ 在其左侧，所以我们一定会迭代到这个零点。

  • 迭代到何时才算结束？

    • 每一次迭代后，我们都会距离零点更进一步，所以当相邻两次迭代得到的交点非常接近时，我们就可以断定，此时的结果已经足够我们得到答案了。一般来说，可以判断相邻两次迭代的结果的差值是否小于一个极小的非负数 $\epsilon$，其中 $\epsilon$ 一般可以取 $10^{-6}$ 或 $10^{-7}$ 。

  • 如何通过迭代得到的近似零点得出最终的答案？

    • 由于 $y = f(x)$ 在$[\sqrt{C}, +\infty]$ 上是凸函数（convex function）且恒大于等于零，那么只要我们选取的初始值 $x_0$ 大于等于 $\sqrt{C}$ ，每次迭代得到的结果 $x_i$ 都会恒大于等于 $\sqrt{C}$ 。因此只要 $\epsilon$ 选择地足够小，最终的结果 $x_k$ 只会稍稍大于真正的零点 $\sqrt{C} $。在题目给出的 32 位整数范围内，不会出现下面的情况：

      真正的零点为 $n - 1/2\epsilon$，其中 $n$ 是一个正整数，而我们迭代得到的结果为 $n + 1/2\epsilon$。在对结果保留整数部分后得到 $n$，但正确的结果为 $n - 1$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    int mySqrt(int x) {
        if (x == 0) {
            return 0;
        }

        double C = x, x0 = x;
        while (true) {
            double xi = 0.5 * (x0 + C / x0);
            if (fabs(x0 - xi) < 1e-7) {
                break;
            }
            x0 = xi;
        }
        return int(x0);
    }
};
作者：LeetCode-Solution

总结：

在这一周主要就还是对字符串进行操作，在这周学到了新的算法，也重新对数学知识有了一定的了解，例如开跟号的题目，一般人都不会想到去列方程来求解一道编程题。在这几次的练习中，主要进行的是字符串的查找和匹配，在我看来，这一周最重要的就是KMP算法了，这其中的知识还是挺难的。