IT博客汇
  • 首页
  • 精华
  • 技术
  • 设计
  • 资讯
  • 扯淡
  • 权利声明
    • 登录 注册

    leetcode-SecondWeek

    JayHrn发表于 2023-12-19 09:35:28
    love 0

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

    [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算法了，这其中的知识还是挺难的。



沪ICP备19023445号-2号
友情链接