初级算法

数组

1.删除排序数组中的重复项

题目

给你一个 升序排列 的数组 nums ，请你 原地 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。

由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。

将最终结果插入 nums 的前 k 个位置后返回 k 。

不要使用额外的空间，你必须在原地修改输入数组 并在使用 O(1) 额外空间的条件下完成。

示例 1：

输入：nums = [1,1,2]
输出：2, nums = [1,2,_]
解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。

示例 2：

输入：nums = [0,0,1,1,1,2,2,3,3,4]
输出：5, nums = [0,1,2,3,4]
解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/x2gy9m/

我的解法

速度太慢！

class Solution { 
public:    
	int removeDuplicates(vector<int>& nums) {
    	for (vector<int>::iterator itor = nums.begin(); itor != nums.end(); )        
        {
        	int x,y;
            x=*itor;
            ++itor;
            if(itor!=nums.end())
            	y=*itor;
            else
            	break;
            if(x==y)
            {
            	nums.erase(itor);
                itor--;
            }
        }
        return nums.size();
        }
};

官解

双指针

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) {
            return 0;
        }
        int fast = 1, slow = 1;
        while (fast < n) {
            if (nums[fast] != nums[fast - 1]) {
                nums[slow] = nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
};

或者：

//双指针解决
public int removeDuplicates(int[] A) {
    //边界条件判断
    if (A == null || A.length == 0)
        return 0;
    int left = 0;
    for (int right = 1; right < A.length; right++)
        //如果左指针和右指针指向的值一样，说明有重复的，
        //这个时候，左指针不动，右指针继续往右移。如果他俩
        //指向的值不一样就把右指针指向的值往前挪
        if (A[left] != A[right])
            A[++left] = A[right];
    return ++left;
}

2.买卖股票的最佳时机 II

题目

给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。

在每一天，你可以决定是否购买和/或出售股票。你在任何时候 最多 只能持有 一股 股票。你也可以先购买，然后在 同一天 出售。

返回 你能获得的 最大 利润 。

示例 1：

输入：prices = [7,1,5,3,6,4]
输出：7
解释：在第 2 天（股票价格 = 1）的时候买入，在第 3 天（股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
     随后，在第 4 天（股票价格 = 3）的时候买入，在第 5 天（股票价格 = 6）的时候卖出, 这笔交易所能获得利润 = 6 - 3 = 3 。
     总利润为 4 + 3 = 7 。

示例 2：

输入：prices = [1,2,3,4,5]
输出：4
解释：在第 1 天（股票价格 = 1）的时候买入，在第 5 天 （股票价格 = 5）的时候卖出, 这笔交易所能获得利润 = 5 - 1 = 4 。
	 总利润为 4 。

示例 3：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 交易无法获得正利润，所以不参与交易可以获得最大利润，最大利润为 0 。

提示：

1 <= prices.length <= 3 * 104
0 <= prices[i] <= 104

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/x2zsx1/

我的解法

贪心

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        int ans=0;
        for(int i=0;i<n-1;i++)
        {
            if(prices[i+1]-prices[i]>0)
            {
                ans+=prices[i+1]-prices[i];
            }
        }
        return ans;
    }
};

官解

DP（可延伸，学习思路）

定义dp[i][0]表示第i+1天交易完之后手里没有股票的最大利润，dp[i][1]表示第i+1天交易完之后手里持有股票的最大利润。

当天交易完之后手里没有股票可能有两种情况，一种是当天没有进行任何交易，又因为当天手里没有股票，所以当天没有股票的利润只能取前一天手里没有股票的利润。一种是把当天手里的股票给卖了，既然能卖，说明手里是有股票的，所以这个时候当天没有股票的利润要取前一天手里有股票的利润加上当天股票能卖的价格。这两种情况我们取利润最大的即可，所以可以得到

dp[i][0]=max(dp[i-1][0],dp[i-1][1]+prices[i]);

当天交易完之后手里持有股票也有两种情况，一种是当天没有任何交易，又因为当天手里持有股票，所以当天手里持有的股票其实前一天就已经持有了。还一种是当天买入了股票，当天能买股票，说明前一天手里肯定是没有股票的，我们取这两者的最大值，所以可以得到

dp[i][1]=max(dp[i-1][1],dp[i-1][0]-prices[i]);

动态规划的递推公式有了，那么边界条件是什么，就是第一天

如果买入：dp[0][1]=-prices[0];

如果没买：dp[0][0]=0;

3.旋转数组

题目

给你一个数组，将数组中的元素向右轮转 k 个位置，其中 k 是非负数。

示例 1:

输入: nums = [1,2,3,4,5,6,7], k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右轮转 1 步: [7,1,2,3,4,5,6]
向右轮转 2 步: [6,7,1,2,3,4,5]
向右轮转 3 步: [5,6,7,1,2,3,4]

示例 2:

输入：nums = [-1,-100,3,99], k = 2
输出：[3,99,-1,-100]
解释: 
向右轮转 1 步: [99,-1,-100,3]
向右轮转 2 步: [3,99,-1,-100]

提示：

1 <= nums.length <= 105
-231 <= nums[i] <= 231 - 1
0 <= k <= 105

进阶：

尽可能想出更多的解决方案，至少有 三种 不同的方法可以解决这个问题。
你可以使用空间复杂度为 O(1) 的 原地 算法解决这个问题吗？

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/x2skh7/

我的解法

左右部分交换

class Solution {
public:
    void rotate(vector<int>& nums, int k) {
        int n=nums.size();
        k%=n;
        reverse(nums,0,n-k-1);
        reverse(nums,n-k,n-1);
        reverse(nums,0,n-1);
    }

    void reverse(vector<int>& nums,int l,int r)
    {
        while(l<r)
            swap(nums[l++],nums[r--]);
    }
};

官解

1.同我的解法

2.环状替换

我们从位置 $0$ 开始，最初令$\text{temp}=\text{nums}[0]$。根据规则，位置 $0$ 的元素会放至 $(0+k)\mathrm{mod}n(0+k)modn$ 的位置，令$x=(0+k)modn$，此时交换 $temp$ 和 $nums[x]$，完成位置 $x$ 的更新。然后，我们考察位置 $x$，并交换 $temp$ 和 $\text{nums}[(x+k)\mathrm{mod}n]$，从而完成下一个位置的更新。不断进行上述过程，直至回到初始位置 $0$。

容易发现，当回到初始位置 $0$ 时，有些数字可能还没有遍历到，此时我们应该从下一个数字开始重复的过程，可是这个时候怎么才算遍历结束呢？我们不妨先考虑这样一个问题：从 00 开始不断遍历，最终回到起点 $0$ 的过程中，我们遍历了多少个元素？

由于最终回到了起点，故该过程恰好走了整数数量的圈，不妨设为 a 圈；再设该过程总共遍历了 b 个元素。因此，我们有 $an=bk$，即 anan 一定为n,k 的公倍数。又因为我们在第一次回到起点时就结束，因此 a 要尽可能小，故 $a_n$ 就是 n,k 的最小公倍数 $\text{lcm}(n,k)$，因此 b就为 $lcm(n,k)/k$。

这说明单次遍历会访问到 $\text{lcm}(n,k)/k$ 个元素。为了访问到所有的元素，我们需要进行遍历的次数为$\frac{\text{n}}{\text{lcm}(n,k)/k}=\frac{\text{nk}}{\text{lcm}(n,k)}=\text{gcd}(n,k)$

一些思考

1.贝祖定理:若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。(d是ax+by能到达的最小正值)

2.单次遍历到的点之间一定是等间隔的(反证法可以证明)

4.存在重复元素

题目

给你一个整数数组 nums 。如果任一值在数组中出现 至少两次 ，返回 true ；如果数组中每个元素互不相同，返回 false 。

示例 1：

输入：nums = [1,2,3,1]
输出：true

示例 2：

输入：nums = [1,2,3,4]
输出：false

示例 3：

输入：nums = [1,1,1,3,3,4,3,2,4,2]
输出：true

提示：

1 <= nums.length <= 105
-109 <= nums[i] <= 109

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/x248f5/

我的解法

利用哈希表作重复性检查

class Solution {
public:
    bool containsDuplicate(vector<int>& nums) {
        unordered_set<int> set;
        int n=nums.size();
        for(int i=0;i<n;i++)
        {
            pair<unordered_set<int>::iterator, bool> ret=set.insert(nums[i]);
            if(!ret.second)
            {
                return true;
            }
        }
        return false;
    }
};

官解

同我的解法

5.只出现一次的数字

题目

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

说明：

你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？

示例 1:

输入: [2,2,1]
输出: 1

示例 2:

输入: [4,1,2,1,2]
输出: 4

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/x21ib6/

我的解法

利用异或(数电实验头歌平台做过类似签到题)

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int ans=0;
        for(auto x:nums)
        {
            ans=ans^x;
        }
        return ans;
    }
};

官解

同我的解法

6.两个数组的交集 II

题目

给你两个整数数组 nums1 和 nums2 ，请你以数组形式返回两数组的交集。返回结果中每个元素出现的次数，应与元素在两个数组中都出现的次数一致（如果出现次数不一致，则考虑取较小值）。可以不考虑输出结果的顺序。

示例 1：

输入：nums1 = [1,2,2,1], nums2 = [2,2]
输出：[2,2]

示例 2:

输入：nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出：[4,9]

提示：

1 <= nums1.length, nums2.length <= 1000
0 <= nums1[i], nums2[i] <= 1000

进阶：

如果给定的数组已经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小，哪种方法更优？
如果 nums2 的元素存储在磁盘上，内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/x2y0c2/

我的解法

排序 + 双指针

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        sort(nums1.begin(),nums1.end());
        sort(nums2.begin(),nums2.end());
        int p1=0,p2=0;
        vector<int> ans;
        while(p1<nums1.size()&&p2<nums2.size())
        {
            if(nums1[p1]<nums2[p2])
            {
                p1++;
            }
            else if(nums1[p1]>nums2[p2])
            {
                p2++;
            }
            else
            {
                ans.push_back(nums1[p1]);
                p1++;p2++;
            }
        }
        return ans;
    }
};

官解

1.哈希表

class Solution {
public:
    vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
        if(nums1.size() > nums2.size()) return intersect(nums2, nums1);//为了减小空间复杂度(可删)
        map<int, int> m;
        vector<int> res;
        for(auto i : nums1) ++m[i];
        for(auto i : nums2) if(m.count(i) && m[i]) --m[i], res.push_back(i);
        return res;
    } 
};

2.同我的解法

7.加一

题目

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

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

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/x2cv1c/

我的解法

class Solution {
public:
    vector<int> plusOne(vector<int>& digits) {
        int n=digits.size();
        int pos=n-1;
        digits[pos]++;
        while(pos>=0&&digits[pos]==10)
        {
            if(pos!=0)
            {
                digits[pos--]=0;
                digits[pos]++;
            }
            else
            {
                digits[pos]=0;
                digits.insert(digits.begin(),1);
            }
        }
        return digits;
    }
};

官解

差不多,没什么意思

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-oqH5u6Uw-1658465561542)(C:\Users\LJQ\AppData\Roaming\Typora\typora-user-images\image-20220707173748328.png)]

8.移动零

题目

给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。

请注意 ，必须在不复制数组的情况下原地对数组进行操作。

示例 1:

输入: nums = [0,1,0,3,12]
输出: [1,3,12,0,0]

示例 2:

输入: nums = [0]
输出: [0]

提示:

1 <= nums.length <= 104
-231 <= nums[i] <= 231 - 1

进阶：你能尽量减少完成的操作次数吗？

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/x2ba4i/

我的解法

双指针

class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int j=0;
        int n=nums.size();
        for(int i=0;i<n;i++)
        {
            if(nums[i]!=0)
            {
                nums[j++]=nums[i];
            }
        }
        nums.resize(j);
        nums.resize(n);
    }
};

官解

同我的解法

9.两数之和

题目

给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。

你可以按任意顺序返回答案。

示例 1：

输入：nums = [2,7,11,15], target = 9
输出：[0,1]
解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。

示例 2：

输入：nums = [3,2,4], target = 6
输出：[1,2]

示例 3：

输入：nums = [3,3], target = 6
输出：[0,1]

提示：

2 <= nums.length <= 104
-109 <= nums[i] <= 109
-109 <= target <= 109
只会存在一个有效答案

进阶：你可以想出一个时间复杂度小于 O(n2) 的算法吗？

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/x2jrse/

我的解法

利用key记录nums[i],value记录位置i(同时表示是否出现过)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> map;
        int n=nums.size();
        for(int i=0;i<n;i++)
        {
            int x=nums[i];
            if(map.find(target-x)!=map.end())
            {
                vector<int> ans;
                ans.push_back(map[target-x]-1);
                ans.push_back(i);
                return ans;
            }
            else
            {
                map[x]=i+1;
            }
        }
        vector<int> ans;
        return ans;
    }
};

官解

同我的解法(哈希表)

注意到暴力枚举的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此，我们需要一种更优秀的方法，能够快速寻找数组中是否存在目标元素。如果存在，我们需要找出它的索引。

没必要加1(我本来担心nums[0]=0事实上即使这样也没关系,还是对unordered_map的理解不到位)

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, int> hashtable;
        for (int i = 0; i < nums.size(); ++i) {
            auto it = hashtable.find(target - nums[i]);
            if (it != hashtable.end()) {
                return {it->second, i};
            }
            hashtable[nums[i]] = i;
        }
        return {};
    }
};

10.有效的数独

请你判断一个 9 x 9 的数独是否有效。只需要 根据以下规则 ，验证已经填入的数字是否有效即可。

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3x3 宫内只能出现一次。（请参考示例图）

注意：

一个有效的数独（部分已被填充）不一定是可解的。
只需要根据以上规则，验证已经填入的数字是否有效即可。
空白格用 ‘.’ 表示。

示例 1：

输入：board = 
[["5","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：true

示例 2：

输入：board = 
[["8","3",".",".","7",".",".",".","."]
,["6",".",".","1","9","5",".",".","."]
,[".","9","8",".",".",".",".","6","."]
,["8",".",".",".","6",".",".",".","3"]
,["4",".",".","8",".","3",".",".","1"]
,["7",".",".",".","2",".",".",".","6"]
,[".","6",".",".",".",".","2","8","."]
,[".",".",".","4","1","9",".",".","5"]
,[".",".",".",".","8",".",".","7","9"]]
输出：false
解释：除了第一行的第一个数字从 5 改为 8 以外，空格内其他数字均与 示例1 相同。 但由于位于左上角的 3x3 宫内有两个 8 存在, 因此这个数独是无效的。

提示：

board.length == 9
board[i].length == 9
board[i][j] 是一位数字（1-9）或者 '.'

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/x2f9gg/

我的解法

按照题目遍历检查

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        for(int i=0;i<9;i++)
        {
            unordered_map<char,int> map;
            for(int j=0;j<9;j++)
            {
                if(board[i][j]!='.')
                {
                    if(map.find(board[i][j])!=map.end())
                    {
                        return false;
                    }
                    else
                    {
                        map[board[i][j]]=1;
                    }
                }
            }
        }

        for(int i=0;i<9;i++)
        {
            unordered_map<char,int> map;
            for(int j=0;j<9;j++)
            {
                if(board[j][i]!='.')
                {
                    if(map.find(board[j][i])!=map.end())
                    {
                        return false;
                    }
                    else
                    {
                        map[board[j][i]]=1;
                    }
                }
            }
        }

        for(int i=0;i<3;i++)
        {
            for(int j=0;j<3;j++)
            {
                unordered_map<char,int> map;
                for(int x=0;x<3;x++)
                {
                    for(int y=0;y<3;y++)
                    {
                        if(board[3*i+x][3*j+y]!='.')
                        {
                            if(map.find(board[3*i+x][3*j+y])!=map.end())
                            {
                                return false;
                            }
                            else
                            {
                                map[board[3*i+x][3*j+y]]=1;
                            }
                        }
                    }
                }
            }
        }
        return true;
    }
};

官解

一步到位啊!遍历三遍干神马!

哈希表→数组→位

大多数的哈希表计数问题，都能转换为使用数组解决。虽然时间复杂度一样，但哈希表的更新和查询复杂度为均摊 O(1)，而定长数组的的更新和查询复杂度则是严格 O(1)。

位运算更进一步，我们可以使用一个 intint 来记录 某行/某列/某个小方块 的数值填入情况：使用从低位开始的 [1, 9][1,9] 位来记录该数值是否已被填入。

class Solution {
public:
    bool isValidSudoku(vector<vector<char>>& board) {
        int rows[9][9];
        int columns[9][9];
        int subboxes[3][3][9];
        
        //初始化位为0
        memset(rows,0,sizeof(rows));
        memset(columns,0,sizeof(columns));
        memset(subboxes,0,sizeof(subboxes));
        
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                char c = board[i][j];
                if (c != '.') {
                    int index = c - '0' - 1;
                    rows[i][index]++;
                    columns[j][index]++;
                    subboxes[i / 3][j / 3][index]++;
                    if (rows[i][index] > 1 || columns[j][index] > 1 || subboxes[i / 3][j / 3][index] > 1) {
                        return false;
                    }
                }
            }
        }
        return true;
    }
};

11.旋转图像

给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：

输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]

示例 2：

输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]

提示：

n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnhhkv/

我的解法

环状替换

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        //[i,j]->[j,n-1-i]
        int n=matrix.size();
        for(int i=0;i<n/2;i++)
        {
            for(int j=0;j<n-1-2*i;j++)
            {
                int temp=matrix[i][i+j];
                int temp_x=i,temp_y=i+j;
                for(int k=0;k<3;k++)
                {
                    swap(temp,matrix[temp_y][n-1-temp_x]);
                    int t=temp_x;
                    temp_x=temp_y;
                    temp_y=n-1-t;
                }
                matrix[i][i+j]=temp;
            }
        }
    }
};

官解

环状替换

找对替换方向

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < (n + 1) / 2; ++j) {
                int temp = matrix[i][j];
                matrix[i][j] = matrix[n - j - 1][i];
                matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
                matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
                matrix[j][n - i - 1] = temp;
            }
        }
    }
};

翻转代替旋转

类似3.旋转数组

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4AVM7QA5-1658465561544)(C:\Users\LJQ\AppData\Roaming\Typora\typora-user-images\image-20220710205812888.png)]

class Solution {
public:
    void rotate(vector<vector<int>>& matrix) {
        int n = matrix.size();
        // 水平翻转
        for (int i = 0; i < n / 2; ++i) {
            for (int j = 0; j < n; ++j) {
                swap(matrix[i][j], matrix[n - i - 1][j]);
            }
        }
        // 主对角线翻转
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < i; ++j) {
                swap(matrix[i][j], matrix[j][i]);
            }
        }
    }
};

字符串

1.反转字符串

编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 s 的形式给出。

不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。

示例 1：

输入：s = ["h","e","l","l","o"]
输出：["o","l","l","e","h"]

示例 2：

输入：s = ["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]

提示：

1 <= s.length <= 105
s[i] 都是 ASCII 码表中的可打印字符

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnhbqj/

我的解法

class Solution {
public:
    void reverseString(vector<char>& s) {
        int n=s.size();
        for(int i=0;i<n/2;i++)
        {
            swap(s[i],s[n-1-i]);
        }
    }
};

官解

同我的解法

2.整数反转

给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。

如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。

假设环境不允许存储 64 位整数（有符号或无符号）。

示例 1：

输入：x = 123
输出：321

示例 2：

输入：x = -123
输出：-321

示例 3：

输入：x = 120
输出：21

示例 4：

输入：x = 0
输出：0

提示：

-231 <= x <= 231 - 1

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnx13t/

我的解法

123=100+20+3

-123=-100+（-20）+（-3）

计算机除法规则：向0取整
-123/10=-12
-123%10=-3

官解

细节证明[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QKfHYNLt-1658465561545)(C:\Users\LJQ\AppData\Roaming\Typora\typora-user-images\image-20220711181644715.png)]

3.字符串中的第一个唯一字符

给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。

示例 1：

输入: s = "leetcode"
输出: 0

示例 2:

输入: s = "loveleetcode"
输出: 2

示例 3:

输入: s = "aabb"
输出: -1

提示:

1 <= s.length <= 105
s 只包含小写字母

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xn5z8r/

我的解法

哈希表记录出现次数

class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char,int> map;
        for(int i=0;i<s.size();i++)
        {
            map[s[i]]++;
        }
        for(int i=0;i<s.size();i++)
        {
            if(map[s[i]]==1)
            {
                return i;
            }
        }
        return -1;
    }
};

可改成数组

class Solution {
public:
    int firstUniqChar(string s) {
        //unordered_map<char,int> map;
        int map[26]={0};
        
        for(int i=0;i<s.size();i++)
        {
            map[s[i]-'a']++;
        }

        for(int i=0;i<s.size();i++)
        {
            if(map[s[i]-'a']==1)
            {
                return i;
            }
        }
        return -1;
    }
};

官解

一

同我的解法

二

class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<int, int> position;
        int n = s.size();
        for (int i = 0; i < n; ++i) {
            if (position.count(s[i])) {
                position[s[i]] = -1;
            }
            else {
                position[s[i]] = i;
            }
        }
        int first = n;
      
        for (auto [_, pos]: position) {//学习到新写法
            if (pos != -1 && pos < first) {
                first = pos;
            }
        }
        
        if (first == n) {
            first = -1;
        }
        return first;
    }
};

map遍历原来可以这样写！

        for (auto [_, pos]: position) {//学习到新写法
            if (pos != -1 && pos < first) {
                first = pos;
            }
        }

三.队列

思路与算法

我们也可以借助队列找到第一个不重复的字符。队列具有「先进先出」的性质，因此很适合用来找出第一个满足某个条件的元素。

具体地，我们使用与方法二相同的哈希映射，并且使用一个额外的队列，按照顺序存储每一个字符以及它们第一次出现的位置。当我们对字符串进行遍历时，设当前遍历到的字符为 c，如果 c 不在哈希映射中，我们就将 cc 与它的索引作为一个二元组放入队尾，否则我们就需要检查队列中的元素是否都满足「只出现一次」的要求，即我们不断地根据哈希映射中存储的值（是否为 −1）选择弹出队首的元素，直到队首元素「真的」只出现了一次或者队列为空。

在遍历完成后，如果队列为空，说明没有不重复的字符，返回 −1，否则队首的元素即为第一个不重复的字符以及其索引的二元组。

小贴士

在维护队列时，我们使用了「延迟删除」这一技巧。也就是说，即使队列中有一些字符出现了超过一次，但它只要不位于队首，那么就不会对答案造成影响，我们也就可以不用去删除它。只有当它前面的所有字符被移出队列，它成为队首时，我们才需要将它移除。

class Solution {
public:
    int firstUniqChar(string s) {
        unordered_map<char, int> position;
        queue<pair<char, int>> q;
        int n = s.size();
        for (int i = 0; i < n; ++i) {
            if (!position.count(s[i])) {
                position[s[i]] = i;
                q.emplace(s[i], i);
            }
            else {
                position[s[i]] = -1;
                while (!q.empty() && position[q.front().first] == -1) {
                    q.pop();
                }
            }
        }
        return q.empty() ? -1 : q.front().second;
    }
};

4.有效的字母异位词

给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。

注意：若 s 和 t 中每个字符出现的次数都相同，则称 s 和 t 互为字母异位词。

示例 1:

输入: s = "anagram", t = "nagaram"
输出: true

示例 2:

输入: s = "rat", t = "car"
输出: false

提示:

1 <= s.length, t.length <= 5 * 104
s 和 t 仅包含小写字母

进阶: 如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xn96us/

我的解法

排序后比较

class Solution {
public:
    bool isAnagram(string s, string t) {
        sort(s.begin(),s.end());
        sort(t.begin(),t.end());

        return s==t;
    }
};

官解

哈希表

从另一个角度考虑，t 是 s 的异位词等价于「两个字符串中字符出现的种类和次数均相等」。由于字符串只包含 26 个小写字母，因此我们可以维护一个长度为 26 的频次数组 table，先遍历记录字符串 s 中字符出现的频次，然后遍历字符串 t，减去 table 中对应的频次，如果出现 table[i]<0，则说明 t 包含一个不在 s 中的额外字符，返回 false 即可。

5.验证回文串

给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。

说明：本题中，我们将空字符串定义为有效的回文串。

示例 1:

输入: "A man, a plan, a canal: Panama"
输出: true
解释："amanaplanacanalpanama" 是回文串

示例 2:

输入: "race a car"
输出: false
解释："raceacar" 不是回文串

提示：

1 <= s.length <= 2 * 105
字符串 s 由 ASCII 字符组成

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xne8id/

我的解法

class Solution {
public:
    bool isPalindrome(string s) {
        int l=0,r=s.size()-1;
        while(l<r)
        {
            while(l<s.size()&&!((s[l]>='A'&&s[l]<='Z')||(s[l]>='a'&&s[l]<='z')||(s[l]>='0'&&s[l]<='9')))
                l++;
            while(r>-1&&!((s[r]>='A'&&s[r]<='Z')||(s[r]>='a'&&s[r]<='z')||(s[r]>='0'&&s[r]<='9')))
                r--;

            if(l<=r)
            {
                if(s[l]>='A'&&s[l]<='Z')
                {
                    s[l]-='A'-'a';
                }
                if(s[r]>='A'&&s[r]<='Z')
                {
                    s[r]-='A'-'a';
                }


                if(s[l++]!=s[r--])
                {
                    return false;
                }
            }
            else
            {
                break;
            }
        }
        return true;
    }
};

官解

学习关于字符串的API！

原型：extern int isalnum(int c);
用法：
#include <ctype.h>/* 包含 <ctype.h> */
功能：判断字符变量c是否为字母或数字
说明：当c为数字0-9或字母a-z及A-Z时，返回非零值，否则返回零。

int tolower ( int c );tolower() 函数用来将大写字母转换为小写字母。
int toupper ( int c );toupper() 函数用来将小写字母转换为大写字母。

class Solution {
public:
    bool isPalindrome(string s) {
        string sgood;
        for (char ch: s) {
            if (isalnum(ch)) {
                sgood += tolower(ch);
            }
        }
        string sgood_rev(sgood.rbegin(), sgood.rend());//reverse(s.begin(),s.end())
        return sgood == sgood_rev;
    }
};

6.字符串转换整数 (atoi)

请你来实现一个 myAtoi(string s) 函数，使其能将字符串转换成一个 32 位有符号整数（类似 C/C++ 中的 atoi 函数）。

函数 myAtoi(string s) 的算法如下：

读入字符串并丢弃无用的前导空格
检查下一个字符（假设还未到字符末尾）为正还是负号，读取该字符（如果有）。 确定最终结果是负数还是正数。 如果两者都不存在，则假定结果为正。
读入下一个字符，直到到达下一个非数字字符或到达输入的结尾。字符串的其余部分将被忽略。
将前面步骤读入的这些数字转换为整数（即，“123” -> 123， “0032” -> 32）。如果没有读入数字，则整数为 0 。必要时更改符号（从步骤 2 开始）。
如果整数数超过 32 位有符号整数范围 [−231, 231 − 1] ，需要截断这个整数，使其保持在这个范围内。具体来说，小于 −231 的整数应该被固定为 −231 ，大于 231 − 1 的整数应该被固定为 231 − 1 。
返回整数作为最终结果。
注意：

本题中的空白字符只包括空格字符 ' ' 。
除前导空格或数字后的其余字符串外，请勿忽略 任何其他字符。

示例 1：

输入：s = "42"
输出：42
解释：加粗的字符串为已经读入的字符，插入符号是当前读取的字符。
第 1 步："42"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："42"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："42"（读入 "42"）
           ^
解析得到整数 42 。
由于 "42" 在范围 [-231, 231 - 1] 内，最终结果为 42 。

示例 2：

输入：s = "   -42"
输出：-42
解释：
第 1 步："   -42"（读入前导空格，但忽视掉）
            ^
第 2 步："   -42"（读入 '-' 字符，所以结果应该是负数）
             ^
第 3 步："   -42"（读入 "42"）
               ^
解析得到整数 -42 。
由于 "-42" 在范围 [-231, 231 - 1] 内，最终结果为 -42 。

示例 3：

输入：s = "4193 with words"
输出：4193
解释：
第 1 步："4193 with words"（当前没有读入字符，因为没有前导空格）
         ^
第 2 步："4193 with words"（当前没有读入字符，因为这里不存在 '-' 或者 '+'）
         ^
第 3 步："4193 with words"（读入 "4193"；由于下一个字符不是一个数字，所以读入停止）
             ^
解析得到整数 4193 。
由于 "4193" 在范围 [-231, 231 - 1] 内，最终结果为 4193 。

提示：

0 <= s.length <= 200
s 由英文字母（大写和小写）、数字（0-9）、' '、'+'、'-' 和 '.' 组成

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnoilh/

我的解法

class Solution {
public:
    int myAtoi(string s) {
        int begin=0;
        while(!(s[begin]=='+'||s[begin]=='-'||isdigit(s[begin])))
        {
            if(isspace(s[begin]))
                begin++;
            else
                return 0;
        }
        int sign=1;
        if(s[begin]=='-')
        {
            sign=-1;
            begin++;
        }
        else if(s[begin]=='+')
        {
            begin++;
        }

        int ans=0;
        while(begin<s.size()&&isdigit(s[begin]))
        {
            if((ans<214748364&&ans>-214748364)||(ans==214748364&&s[begin]<'8')||(ans==-214748364&&s[begin]<'9'))
            {
                ans=ans*10+sign*(s[begin++]-'0');
            }
            else if(ans>0)
                return 2147483647;
            else
                return -2147483648;
        }
        return ans;
    }
};

官解

自动机
思路

字符串处理的题目往往涉及复杂的流程以及条件情况，如果直接上手写程序，一不小心就会写出极其臃肿的代码。因此，为了有条理地分析每个输入字符的处理方法，我们可以使用自动机这个概念：

我们的程序在每个时刻有一个状态 s，每次从序列中输入一个字符 c，并根据字符 c 转移到下一个状态 s’。这样，我们只需要建立一个覆盖所有情况的从 s 与 c 映射到 s’ 的表格即可解决题目中的问题。

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-K1gu2X8c-1658465561546)(C:\Users\LJQ\AppData\Roaming\Typora\typora-user-images\image-20220712142059328.png)]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-wKlxeNio-1658465561546)(C:\Users\LJQ\AppData\Roaming\Typora\typora-user-images\image-20220712142156482.png)]

C++中如何实现自动机：

class Automaton {
    string state = "start";
    unordered_map<string, vector<string>> table = {
        {"start", {"start", "signed", "in_number", "end"}},
        {"signed", {"end", "end", "in_number", "end"}},
        {"in_number", {"end", "end", "in_number", "end"}},
        {"end", {"end", "end", "end", "end"}}
    };

    int get_col(char c) {
        if (isspace(c)) return 0;
        if (c == '+' or c == '-') return 1;
        if (isdigit(c)) return 2;
        return 3;
    }
public:
    int sign = 1;
    long long ans = 0;

    void get(char c) {
        state = table[state][get_col(c)];//状态转移
        if (state == "in_number") {
            ans = ans * 10 + c - '0';
            ans = sign == 1 ? min(ans, (long long)INT_MAX) : min(ans, -(long long)INT_MIN);
        }
        else if (state == "signed")
            sign = c == '+' ? 1 : -1;
    }
};

class Solution {
public:
    int myAtoi(string str) {
        Automaton automaton;
        for (char c : str)
            automaton.get(c);
        return automaton.sign * automaton.ans;
    }
};

7.*实现 strStr()

实现 strStr() 函数。

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

说明：

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

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

示例 1：

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

示例 2：

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

提示：

1 <= haystack.length, needle.length <= 104
haystack 和 needle 仅由小写英文字符组成

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnr003/

我的解法

KMP

class Solution {
public:
    int strStr(string haystack, string needle) {
        int n=needle.size();
        //计算next数组
        int* next=new int[n];
        next[0]=-1;
        for(int i=1;i<n;i++)
        {
            int k=next[i-1];
            while(k>=0&&needle[k]!=needle[i-1])
            {
                k=next[k];
            }
            if(k==-1)
            {
                next[i]=0;
            }
            else
            {
                next[i]=k+1;
            }
        }

		//字符串比对
        int i=0,j=0;
        while(i<haystack.size()&&j<n)
        {
            if(haystack[i]==needle[j])
            {
                i++;j++;
            }
            else
            {
                if(j!=0)
                    j=next[j];
                else
                    i++;
            }
        }
        if(j==n)
        {
            return i-n;
        }
        else
        {
            return -1;
        }
    }
};

关于模式串向右移动的位数为：j - next[j]的思考

1.有没有可能跳的太多了?

证明:

一方面证明只有跳相同前后缀长度才有可能匹配

​ 证:

​ ∵P[0,x]≠P[y,i] (否则的话为相同前后缀)=T[a,b]

​ ∴不可能匹配

另一方面有最长相同前后缀长度保证不会跳多

​ 易证

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-2TvkcoGv-1658465561547)(https://cdn.jsdelivr.net/gh/xzljq/picbed/img/image-20220715121527139.png)]

2.跳跃的本质:排除不可能匹配的情况

关于如何计算next数组的几个疑惑与思考

1.若P[i]=P[k],为什么next[i+1]=next[i]+1不可能更大了

即证明next[i+1]≤next[i]+1

证明:反证法若next[i+1]>next[i]+1,可证明next[i]并非最大

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YdYRKeYw-1658465561548)(https://cdn.jsdelivr.net/gh/xzljq/picbed/img/image-20220715094551439.png)]

2.若P[i]≠P[k],希望找到次长相同前后缀为什么k=next[k]

证明:

∵next[i+1]≤next[i]+1且当P[i]≠P[k]时严格小于

∴所有的相同前后缀都有[0,x] [y,i] (长度小于k)的形式

设次长前后缀为[0,x] [y,i]

∵[0,x]=[y,i]=[z,k]

∴找[0,i]的次长前后缀等价于找[0,k]的最长前后缀

3.计算next[i+1] ([0,i]最长相同前后缀)的过程本质就是找[0,i-1]最长/次长/次次长/…长相同前后缀,然后判断[k]是否等于[i]取舍

证明:

若要[0,k]=[i-k,i],则一定要求有[0,k-1]=[i-k,i-1]

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-CajwmHXc-1658465561549)(https://cdn.jsdelivr.net/gh/xzljq/picbed/img/image-20220715111801190.png)]

KMP时间复杂度分析

KMP算法的一次比较只会产生两种结果，一种就是匹配成功主串的指针向前移动，一种是匹配失败模式串整体向前移动，两者都移动完时算法必然结束。前面的移动必为m次，后面的移动最多m次。所以最大的时间复杂度为2m，差异只存在于模式串移动的幅度

8.外观数列

给定一个正整数 n ，输出外观数列的第 n 项。

「外观数列」是一个整数序列，从数字 1 开始，序列中的每一项都是对前一项的描述。

你可以将其视作是由递归公式定义的数字字符串序列：

countAndSay(1) = “1”
countAndSay(n) 是对 countAndSay(n-1) 的描述，然后转换成另一个数字字符串。
前五项如下：

1. 1
   

2. 11
   

3. 21
   

4. 1211
   

5. 111221
   

第一项是数字 1
描述前一项，这个数是 1 即 “ 一 个 1 ”，记作 “11”
描述前一项，这个数是 11 即 “ 二 个 1 ” ，记作 “21”
描述前一项，这个数是 21 即 “ 一 个 2 + 一 个 1 ” ，记作 “1211”
描述前一项，这个数是 1211 即 “ 一 个 1 + 一 个 2 + 二 个 1 ” ，记作 “111221”
要 描述 一个数字字符串，首先要将字符串分割为 最小 数量的组，每个组都由连续的最多 相同字符 组成。然后对于每个组，先描述字符的数量，然后描述字符，形成一个描述组。要将描述转换为数字字符串，先将每组中的字符数量用数字替换，再将所有描述组连接起来。

例如，数字字符串 “3322251” 的描述如下图：

示例 1：

输入：n = 1
输出："1"
解释：这是一个基本样例。

示例 2：

输入：n = 4
输出："1211"
解释：
countAndSay(1) = "1"
countAndSay(2) = 读 "1" = 一 个 1 = "11"
countAndSay(3) = 读 "11" = 二 个 1 = "21"
countAndSay(4) = 读 "21" = 一 个 2 + 一 个 1 = "12" + "11" = "1211"

提示：

1 <= n <= 30

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnpvdm/

我的解法

class Solution {
public:
    string countAndSay(int n) {
        
        string s="1";
        for(int x=1;x<n;x++)
        {
            int i=0,j=0;
            while(i<s.size())
            {
                while(j<s.size()&&s[j]==s[i])
                    j++;
                char ch=s[i];
                s.erase(i,j-i);
                s.insert(i,to_string(j-i));
                s.insert(i+1,1,ch);
                i+=to_string(j-i).size()+1;
                j=i;
            }
        }
        return s;
    }
};

官解

同我的解法差不多,不过另起了一个数组

9.最长公共前缀

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

示例 1：

输入：strs = ["flower","flow","flight"]
输出："fl"

示例 2：

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

提示：

1 <= strs.length <= 200
0 <= strs[i].length <= 200
strs[i] 仅由小写英文字母组成

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnmav1/

我的解法

class Solution {
public:
    string longestCommonPrefix(vector<string>& strs) {
        int n=strs.size();
        int min=strs[0].size();
        int pos=0;
        for(int i=1;i<n;i++)
        {
            if(strs[i].size()<min)
            {
                min=strs[i].size();
                pos=i;
            }
        }
        string ans;
        for(int i=0;i<min;i++)
        {
            for(int j=0;j<n-1;j++)
            {
                if(strs[j][i]!=strs[j+1][i])
                    return ans;
            }
            ans+=strs[0][i];
        }
        return ans;
    }
};

官解

横向扫描

LCP(S1…Sn)=LCP(LCP(LCP(S1,S2),S3),…Sn)

纵向扫描

分治

LCP(S1…Sn)=LCP(LCP(S1…Sk),LCP(Sk+1…Sn))

二分查找

在 [0,minLength] 的范围内通过二分查找得到最长公共前缀的长度

链表

1.删除链表中的节点

请编写一个函数，用于 删除单链表中某个特定节点 。在设计函数时需要注意，你无法访问链表的头节点 head ，只能直接访问 要被删除的节点 。

题目数据保证需要删除的节点 不是末尾节点 。

示例 1：

输入：head = [4,5,1,9], node = 5
输出：[4,1,9]
解释：指定链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9

示例 2：

输入：head = [4,5,1,9], node = 1
输出：[4,5,9]
解释：指定链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9

提示：

链表中节点的数目范围是 [2, 1000]
-1000 <= Node.val <= 1000
链表中每个节点的值都是 唯一 的
需要删除的节点 node 是 链表中的节点 ，且 不是末尾节点

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnarn7/

我的解法

class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val;
        node->next = node->next->next;
    }
};

官解

最好释放内存

class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val = node->next->val;
        ListNode* next = node->next;
        node->next = node->next->next;
        delete(next);
    }
};

2.删除链表的倒数第N个节点

给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。

示例 1：

输入：head = [1,2,3,4,5], n = 2
输出：[1,2,3,5]

示例 2：

输入：head = [1], n = 1
输出：[]

示例 3：

输入：head = [1,2], n = 1
输出：[1]

提示：

链表中结点的数目为 sz
1 <= sz <= 30
0 <= Node.val <= 100
1 <= n <= sz

进阶：你能尝试使用一趟扫描实现吗？

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xn2925/

我的解法

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* front=head,*behind=head,*last=head;

        for(int i=0;i<n;i++)
        {
            front=front->next;
        }
        if(front!=NULL)
        {
            front=front->next;
            behind=behind->next;
        }
        else
        {
            return head->next;
        }
        while(front!=NULL)
        {
            front=front->next;
            behind=behind->next;
            last=last->next;
        }
        if(behind->next==NULL)
            last->next=NULL;
        else
        {
            behind->val=behind->next->val;
            behind->next=behind->next->next;
        }
        return head;
    }
};

官解

在对链表进行操作时，一种常用的技巧是添加一个哑节点（dummy node），它的 next 指针指向链表的头节点。这样一来，我们就不需要对头节点进行特殊的判断了。

双指针

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        ListNode* first = head;
        ListNode* second = dummy;
        for (int i = 0; i < n; ++i) {
            first = first->next;
        }
        while (first) {
            first = first->next;
            second = second->next;
        }
        second->next = second->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }
};

栈

class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        ListNode* dummy = new ListNode(0, head);
        stack<ListNode*> stk;
        ListNode* cur = dummy;
        while (cur) {
            stk.push(cur);
            cur = cur->next;
        }
        for (int i = 0; i < n; ++i) {
            stk.pop();
        }
        ListNode* prev = stk.top();
        prev->next = prev->next->next;
        ListNode* ans = dummy->next;
        delete dummy;
        return ans;
    }
};

3.反转链表

给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。

我的解法

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        if(!head)
        {
            return NULL;
        }
        stack<ListNode*> stk;
        ListNode* cur=head;
        while(cur)
        {
            stk.push(cur);
            cur=cur->next;
        }
        head=stk.top();
        while(!stk.empty())
        {
            cur=stk.top();
            stk.pop();
            if(stk.empty())
                cur->next=NULL;
            else
                cur->next=stk.top();
        }
        return head;
    }
};

官解

class Solution {
public:
    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

4.合并两个有序链表

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

示例 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 均按 非递减顺序 排列

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnnbp2/

我的解法

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* list1, ListNode* list2) {
        ListNode* head;
        if(list1&&list2)
        {
            if(list1->val>list2->val)
            {
                list2->next=mergeTwoLists(list1, list2->next);
                return list2;
            }
            else
            {
                list1->next=mergeTwoLists(list1->next, list2);
                return list1;
            }
        }
        else if(list1)
        {
            return list1;
        }
        else
        {
            return list2;
        }
    }
};

官解

同我的解法

5.回文链表

给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。

示例 1：

输入：head = [1,2,2,1]
输出：true

示例 2：

输入：head = [1,2]
输出：false

提示：

链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9

进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnv1oc/

我的解法

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        int n=0;
        ListNode* cur=head,*head1,*head2;
        while(cur)
        {
            n++;
            cur=cur->next;
        }
        if(n==1)
        {
            return true;
        }
        cur=head;

        for(int i=0;i<n/2-1;i++)
        {
            cur=cur->next;
            //cout<<cur->val<<endl;
        }
        head1=cur;
        if(n%2)
        {
            head2=cur->next->next;
        }
        else
        {
            head2=cur->next;
        }
        cur->next=NULL;
        reverseList(head);
        cout<<n<<endl;
        cout<<head1->val<<" "<<head2->val<<endl;
        while(head1)
        {
            if(head1->val==head2->val)
            {
                head1=head1->next;
                head2=head2->next;
            }
            else
            {
                return false;
            }
        }
        return true;

    }

    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr) {
            ListNode* next = curr->next;
            curr->next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
};

官解

递归

class Solution {
    ListNode* frontPointer;
public:
    bool recursivelyCheck(ListNode* currentNode) {
        if (currentNode != nullptr) {
            if (!recursivelyCheck(currentNode->next)) {
                return false;
            }
            if (currentNode->val != frontPointer->val) {
                return false;
            }
            frontPointer = frontPointer->next;
        }
        return true;
    }

    bool isPalindrome(ListNode* head) {
        frontPointer = head;
        return recursivelyCheck(head);
    }
};

快慢指针

思路同我的解法!

我们可以将链表的后半部分反转（修改链表结构），然后将前半部分和后半部分进行比较。比较完成后我们应该将链表恢复原样。虽然不需要恢复也能通过测试用例，但是使用该函数的人通常不希望链表结构被更改。

该方法虽然可以将空间复杂度降到 O(1)，但是在并发环境下，该方法也有缺点。在并发环境下，函数运行时需要锁定其他线程或进程对链表的访问，因为在函数执行过程中链表会被修改。

我们也可以使用快慢指针在一次遍历中找到：慢指针一次走一步，快指针一次走两步，快慢指针同时出发。当快指针移动到链表的末尾时，慢指针恰好到链表的中间。通过慢指针将链表分为两部分。

class Solution {
public:
    bool isPalindrome(ListNode* head) {
        if (head == nullptr) {
            return true;
        }

        // 找到前半部分链表的尾节点并反转后半部分链表
        ListNode* firstHalfEnd = endOfFirstHalf(head);
        ListNode* secondHalfStart = reverseList(firstHalfEnd->next);

        // 判断是否回文
        ListNode* p1 = head;
        ListNode* p2 = secondHalfStart;
        bool result = true;
        while (result && p2 != nullptr) {
            if (p1->val != p2->val) {
                result = false;
            }
            p1 = p1->next;
            p2 = p2->next;
        }        

        // 还原链表并返回结果
        firstHalfEnd->next = reverseList(secondHalfStart);
        return result;
    }

    ListNode* reverseList(ListNode* head) {
        ListNode* prev = nullptr;
        ListNode* curr = head;
        while (curr != nullptr) {
            ListNode* nextTemp = curr->next;
            curr->next = prev;
            prev = curr;
            curr = nextTemp;
        }
        return prev;
    }

    ListNode* endOfFirstHalf(ListNode* head) {
        ListNode* fast = head;
        ListNode* slow = head;
        while (fast->next != nullptr && fast->next->next != nullptr) {
            fast = fast->next->next;
            slow = slow->next;
        }
        return slow;
    }
};

6.*环形链表

给你一个链表的头节点 head ，判断链表中是否有环。

如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。注意：pos 不作为参数进行传递 。仅仅是为了标识链表的实际情况。

如果链表中存在环 ，则返回 true 。 否则，返回 false 。

示例 1：

输入：head = [3,2,0,-4], pos = 1
输出：true
解释：链表中有一个环，其尾部连接到第二个节点

示例 2：

输入：head = [1,2], pos = 0
输出：true
解释：链表中有一个环，其尾部连接到第一个节点。

示例 3：

输入：head = [1], pos = -1
输出：false
解释：链表中没有环。

提示：

链表中节点的数目范围是 [0, 104]
-105 <= Node.val <= 105
pos 为 -1 或者链表中的一个 有效索引 。

进阶：你能用 O(1)（即，常量）内存解决此问题吗？

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnwzei/

我的解法

想不到如何用O(1)内存解决

用哈希表检查重复

class Solution {
public:
    bool hasCycle(ListNode *head) {
        unordered_set<ListNode*> hash;
        ListNode* cur=head;
        while(cur)
        {
            if(hash.find(cur)!=hash.end())
            {
                return true;
            }
            hash.insert(cur);
            cur=cur->next;
        }
        return false;
    }
};

官解

快慢指针
思路及算法

本方法需要读者对「Floyd 判圈算法」（又称龟兔赛跑算法）有所了解。

假想「乌龟」和「兔子」在链表上移动，「兔子」跑得快，「乌龟」跑得慢。当「乌龟」和「兔子」从链表上的同一个节点开始移动时，如果该链表中没有环，那么「兔子」将一直处于「乌龟」的前方；如果该链表中有环，那么「兔子」会先于「乌龟」进入环，并且一直在环内移动。等到「乌龟」进入环时，由于「兔子」的速度快，它一定会在某个时刻与乌龟相遇，即套了「乌龟」若干圈。

我们可以根据上述思路来解决本题。具体地，我们定义两个指针，一快一满。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。

class Solution {
public:
    bool hasCycle(ListNode* head) {
        if (head == nullptr || head->next == nullptr) {
            return false;
        }
        ListNode* slow = head;
        ListNode* fast = head->next;
        while (slow != fast) {
            if (fast == nullptr || fast->next == nullptr) {
                return false;
            }
            slow = slow->next;
            fast = fast->next->next;
        }
        return true;
    }
};

树

二叉树的最大深度

给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7

返回它的最大深度 3 。

我的解法

class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root==NULL)
        {
            return 0;
        }
        return max(maxDepth(root->left),maxDepth(root->right))+1;
    }
};

验证二叉搜索树

给你一个二叉树的根节点 root ，判断其是否是一个有效的二叉搜索树。

有效 二叉搜索树定义如下：

• 节点的左子树只包含 小于 当前节点的数。

• 节点的右子树只包含 大于 当前节点的数。

• 所有左子树和右子树自身必须也是二叉搜索树。

示例 1：

输入：root = [2,1,3]
输出：true

示例 2：

输入：root = [5,1,4,null,null,3,6]
输出：false
解释：根节点的值是 5 ，但是右子节点的值是 4 。

提示：

树中节点数目范围在[1, 104] 内
-231 <= Node.val <= 231 - 1

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xn08xg/

我的解法

class Solution {
public:
    bool isValidBST(TreeNode* root) {
        return (root->left?((findmostright(root->left)->val<root->val)&&isValidBST(root->left)):true)&&
                (root->right?((findmostleft(root->right)->val>root->val)&&isValidBST(root->right)):true);
    }

    TreeNode* findmostleft(TreeNode* root)
    {
        TreeNode* cur=root;
        while(cur->left)
        {
            cur=cur->left;
        }
        return cur;
    }

    TreeNode* findmostright(TreeNode* root)
    {
        TreeNode* cur=root;
        while(cur->right)
        {
            cur=cur->right;
        }
        return cur;
    }
};

官解

上下边界递归

class Solution {
public:
    bool helper(TreeNode* root, long long lower, long long upper) {
        if (root == nullptr) {
            return true;
        }
        if (root -> val <= lower || root -> val >= upper) {
            return false;
        }
        return helper(root -> left, lower, root -> val) && helper(root -> right, root -> val, upper);
    }
    bool isValidBST(TreeNode* root) {
        return helper(root, LONG_MIN, LONG_MAX);
    }
};

中序遍历

二叉搜索树「中序遍历」得到的值构成的序列一定是升序的，这启示我们在中序遍历的时候实时检查当前节点的值是否大于前一个中序遍历到的节点的值即可。如果均大于说明这个序列是升序的，整棵树是二叉搜索树，否则不是，下面的代码我们使用栈来模拟中序遍历的过程。

//非递归遍历
class Solution {
public:
    bool isValidBST(TreeNode* root) {
        stack<TreeNode*> s;
        TreeNode* T=root;
        long long inorder=-2147483649;
        while(T||!s.empty())
        {
            if(T!=NULL)
            {
                s.push(T);
                T=T->left;//先遍历左子树 
            }
            else
            {
                T=s.top();//栈顶元素是该点的父节点 
                s.pop();
                if(T->val<=inorder)
                {
                    return false;
                }
                inorder=T->val;
                T=T->right;//再遍历右子树 
            }
        }
        return true;
    }
};

//递归遍历
//前一个结点，全局的
TreeNode prev;
public boolean isValidBST(TreeNode root) {
    if (root == null)
        return true;
    //访问左子树
    if (!isValidBST(root.left))
        return false;
    //访问当前节点：如果当前节点小于等于中序遍历的前一个节点直接返回false。
    if (prev != null && prev.val >= root.val)
        return false;
    prev = root;
    //访问右子树
    if (!isValidBST(root.right))
        return false;
    return true;
}

二叉树遍历总结

递归

先说一下递归遍历二叉树，三种序列遍历方式的大致结构是一样的，都是先递归遍历左子树，再递归遍历右子树，区别就在于访问节点的顺序不同

先序遍历是先访问根节点再访问左子树和右子树，所以是在一开始就输出节点值，而中序遍历是先访问左子树再访问根节点最后访问右子树，也就是说在递归遍历完当前节点左子树后进行当前节点值输出，而后序遍历是访问完当前节点左子树和右子树后再进行当前节点值的输出

void traverse(BiTree T,int op)
{
	if(T==NULL) return;
	if(op==1)//先序遍历 
	{
		printf("%c",T->data);
		traverse(T->lchild,op);
		traverse(T->rchild,op);
	}
	else if(op==2)//中序遍历
	{
		traverse(T->lchild,op);
		printf("%c",T->data);
		traverse(T->rchild,op);
	}
	else//后序遍历 
	{
		traverse(T->lchild,op);
		traverse(T->rchild,op);
		printf("%c",T->data);
	}
}

非递归

非递归遍历二叉树的实现过程的大体框架也是一样的，与递归遍历的区别就体现在非递归遍历需要我们去用栈来辅助实现，由于递归可以帮我们省去许多细节，而在非递归访问二叉树的实现中就需要单独处理每一个细节了。

先看前序遍历，当我们遍历到一个节点时就应该将其输出，所以我们在一开始先输出节点值，再把当前节点存入栈，然后访问左子树，当左子树为空时再取出栈顶元素，此时栈顶元素就是当前元素的父节点（哪一种遍历方式都一样），然后再访问右子树，这就是前序遍历的非递归实现过程

而中序遍历的非递归实现过程也是一样的，只是我们输出节点值的代码不是放在一开始，而是在左子树为空即将访问右子树时进行节点值的输出，其他就与前序遍历的方法是一样的了。

最后说一下后序遍历，这个就比较复杂了，我们是先访问左子树和右子树最后才输出根节点的值，所以我们遍历到一个左子树已被访问的节点时，右子树有几种可能的情况，第一种是无右子树，那么直接进行当前节点值的输出即可，第二种情况是有右子树且未被访问，那么这个时候我们就要去访问右子树，最后一种情况就是有右子树且已被访问，那么这个时候就是直接输出当前节点值了，当前节点没有右子树的情况非常容易判断，关键就是在当前节点有右子树的情况下如何判断右子树是否已经被访问过，这个问题在递归访问过程中是不需要考虑的，因为递归完右子树就说明右子树已被访问，但是在非递归访问中就不得不开一个变量记录上一个访问的节点，因为是最后访问右子树，所以如果当前节点的右子树被访问，那么上一个被访问的点一定是当前节点右子树的根节点，利用这一点我们就可以区分当前节点的右子树是否已被访问。

void traverse_qian(BiTree T)//前序遍历
{
	stack<BiTree> s;
	while(T||!s.empty())
	{
		if(T!=NULL)
		{
			printf("%c",T->data);//先序遍历先输出根节点 
			s.push(T);
			T=T->lchild;//先遍历左子树 
		}
		else
		{
			T=s.top();//栈顶元素是该点的父节点 
			s.pop();
			T=T->rchild;//再遍历右子树 
		}
	}
}

void traverse_zhong(BiTree T)//中序遍历 
{
	stack<BiTree> s;
	while(T||!s.empty())
	{
		if(T!=NULL)
		{
			s.push(T);
			T=T->lchild;//先遍历左子树 
		}
		else
		{
			T=s.top();//栈顶元素是该点的父节点 
			s.pop();
			printf("%c",T->data);//中序遍历是当左子树节点全部遍历后再输出 
			T=T->rchild;//再遍历右子树 
		}
	}
}

void traverse_hou(BiTree T)//后序遍历
{
	BiTree last=NULL;//上次访问过的点 
	stack<BiTree> s;
	while(T||!s.empty())
	{
		if(T!=NULL)
		{
			s.push(T);
			T=T->lchild;//先遍历左子树 
		}
		else
		{
			T=s.top();
			if(T->rchild!=NULL&&T->rchild!=last)//右子树存在并且未访问过就遍历右子树,右子树根节点若是被访问过也是在当前节点的上一个节点访问的 
			{
				T=T->rchild;//访问右子树
				s.push(T);
				T=T->lchild;
			}
			else//如果右子树不存在或者已经被放问过就直接输出父亲节点并回溯即可 
			{
				s.pop();
				printf("%c",T->data);
				last=T;
				T=NULL;
			}
		}
	}
}

对称二叉树

给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：

输入：root = [1,2,2,3,4,4,3]
输出：true

示例 2：

输入：root = [1,2,2,null,3,null,3]
输出：false

提示：

树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100

进阶：你可以运用递归和迭代两种方法解决这个问题吗？

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xn7ihv/

我的解法

class Solution {
public:
    bool isSymmetric(TreeNode* root) {
        return check(root->left,root->right);
    }

    bool check(TreeNode* left,TreeNode* right)
    {
        if(left==nullptr&&right==nullptr)
        {
            return true;
        }
        else if(left==nullptr||right==nullptr)
        {
            return false;
        }
        else if(left->val!=right->val)
        {
            return false;
        }
        else
        {
            return check(left->left,right->right)&&check(left->right,right->left);
        }
    }
};

官解

递归：同我的解法

迭代：

二叉树的层序遍历

给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：

输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]

示例 2：

输入：root = [1]
输出：[[1]]

示例 3：

输入：root = []
输出：[]

提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnldjj/

我的解法

class Solution {
public:
    vector<vector<int>> levelOrder(TreeNode* root) {
        vector<vector<int>> ans;
        if(!root)
        {
            return ans;
        }
        queue<TreeNode*> q;
        q.push(root);
        while(!q.empty())
        {
            int n=q.size();
            vector<int> level;
            for(int i=0;i<n;i++)
            {
                TreeNode* t=q.front();
                q.pop();
                if(t)
                {
                    level.push_back(t->val);
                    if(t->left)
                        q.push(t->left);
                    if(t->right)
                        q.push(t->right);
                    
                }
            }
            ans.push_back(level);
        }
        return ans;
    }
};

将有序数组转换为二叉搜索树

给你一个整数数组 nums ，其中元素已经按 升序 排列，请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。

示例 1：

输入：nums = [-10,-3,0,5,9]
输出：[0,-3,9,-10,null,5]
解释：[0,-10,5,null,-3,null,9] 也将被视为正确答案：

示例 2：

输入：nums = [1,3]
输出：[3,1]
解释：[1,null,3] 和 [3,1] 都是高度平衡二叉搜索树。

提示：

1 <= nums.length <= 104
-104 <= nums[i] <= 104
nums 按 严格递增 顺序排列

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xninbt/

我的解法

贪心递归构造

class Solution {
public:
    TreeNode* sortedArrayToBST(vector<int>& nums) {
        return sortedArrayToBST(nums,0,nums.size()-1);
    }

    TreeNode* sortedArrayToBST(vector<int>& nums,int left,int right) {
        if(left>right)
        {
            return NULL;
        }
        else if(left==right)
        {
            TreeNode* tn=new TreeNode(nums[left]);
            return tn;
        }
        int mid=(left+right)/2;
        TreeNode* tn=new TreeNode(nums[mid],sortedArrayToBST(nums,left,mid-1),sortedArrayToBST(nums,mid+1,right));
        return tn;
    }
};

正确性证明

对于一个长度为 x 的区间，由它构建出的二叉树的最大高度应该等于对长度为 x 的有序序列进行二分查找「查找成功」时的「最大」比较次数，为 $\lfloor {\log }_{2}x\rfloor +1$，记为 $h(x)$。

「引理 A」 长度为 k的区间与长度为 k+1 的区间（其中 $k\ge 1$）按照以上方法构造出的二叉树的最大高度差不超过 1。

证明过程如下：

要证明「引理 A」即我们要证明：

$\begin{array}{rl}h(k+1)-h(k)=& [\lfloor {\log }_2(k+1)\rfloor +1]-[\lfloor {\log }_2(k)\rfloor +1]\\ =& \lfloor {\log }_2(k+1)\rfloor -\lfloor {\log }_2(k)\rfloor \le 1\end{array}$

易证

「正确性证明」 假设我们要讨论的区间长度为k，我们用数学归纳法来证明：

k = 1，k=2 时显然成立；

假设 k = m 和 k = m + 1 时正确性成立。

那么根据「引理 A」，长度为 m 和 m + 1 的区间构造出的子树都是平衡的，并且它们的高度差不超过 1；

当 k = 2(m + 1) - 1 时，创建出的节点的值等于第m + 1个元素的值，它的左边和右边各有长度为 m 的区间，根据「假设推论」，k = 2(m + 1) - 1 时构造出的左右子树都是平衡树，且树形完全相同，故高度差为 0，所以 k = 2(m + 1) - 1 时，正确性成立；

当 k = 2(m + 1) 时，创建出的节点的值等于第 m + 1 个元素的值，它的左边的区间长度为 m，右边区间的长度为 m + 1，那么 k = 2(m + 1) 时构造出的左右子树都是平衡树，且高度差不超过 1，所以 k = 2(m + 1) 时，正确性成立；

通过这种归纳方法，可以覆盖所有的k≥1。故在 k≥1 时，正确性成立，证毕。

排序和搜索

合并两个有序数组

给你两个按 非递减顺序 排列的整数数组 nums1 和 nums2，另有两个整数 m 和 n ，分别表示 nums1 和 nums2 中的元素数目。

请你 合并 nums2 到 nums1 中，使合并后的数组同样按 非递减顺序 排列。

注意：最终，合并后数组不应由函数返回，而是存储在数组 nums1 中。为了应对这种情况，nums1 的初始长度为 m + n，其中前 m 个元素表示应合并的元素，后 n 个元素为 0 ，应忽略。nums2 的长度为 n 。

示例 1：

输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
输出：[1,2,2,3,5,6]
解释：需要合并 [1,2,3] 和 [2,5,6] 。
合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。

示例 2：

输入：nums1 = [1], m = 1, nums2 = [], n = 0
输出：[1]
解释：需要合并 [1] 和 [] 。
合并结果是 [1] 。

示例 3：

输入：nums1 = [0], m = 0, nums2 = [1], n = 1
输出：[1]
解释：需要合并的数组是 [] 和 [1] 。
合并结果是 [1] 。
注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。

提示：

nums1.length == m + n
nums2.length == n
0 <= m, n <= 200
1 <= m + n <= 200
-109 <= nums1[i], nums2[j] <= 109

进阶：你可以设计实现一个时间复杂度为 O(m + n) 的算法解决此问题吗？

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnumcr/

我的解法

三指针

class Solution {
public:
    void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
        int i=m-1,j=n-1,k=m+n-1;
        while(i>=0&&j>=0)
        {
            if(nums1[i]<nums2[j])
            {
                nums1[k--]=nums2[j--];
            }
            else
            {
                nums1[k--]=nums1[i--];
            }
        }
        while(j>=0)
        {
            nums1[k--]=nums2[j--];
        }
    }
};

正确性证明

第一个错误的版本

你是产品经理，目前正在带领一个团队开发新的产品。不幸的是，你的产品的最新版本没有通过质量检测。由于每个版本都是基于之前的版本开发的，所以错误的版本之后的所有版本都是错的。

假设你有 n 个版本 [1, 2, …, n]，你想找出导致之后所有版本出错的第一个错误的版本。

你可以通过调用 bool isBadVersion(version) 接口来判断版本号 version 是否在单元测试中出错。实现一个函数来查找第一个错误的版本。你应该尽量减少对调用 API 的次数。

示例 1：

输入：n = 5, bad = 4
输出：4
解释：
调用 isBadVersion(3) -> false 
调用 isBadVersion(5) -> true 
调用 isBadVersion(4) -> true
所以，4 是第一个错误的版本。

示例 2：

输入：n = 1, bad = 1
输出：1

提示：

1 <= bad <= n <= 231 - 1

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnto1s/

我的解法

二分查找,$O（lo{g}_n）$

class Solution {
public:
    int firstBadVersion(int n) {
        return find(1,n);
    }
    int find(int l,int r)
    {
        if(l>=r)
        {
            return l;
        }
        else
        {
            int mid=(int)(((long long)l+(long long)r)/2);
            if(isBadVersion(mid)&&isBadVersion(mid+1))
            {
                r=mid;
                return find(l,r);
            }
            else if(!isBadVersion(mid)&&!isBadVersion(mid+1))
            {
                l=mid;
                return find(l,r);
            }
            else
            {
                return mid+1;
            }
        }
    }
};

官解

class Solution {
public:
    int firstBadVersion(int n) {
        int left = 1, right = n;
        while (left < right) { // 循环直至区间左右端点相同
            int mid = left + (right - left) / 2; // 防止计算时溢出
            if (isBadVersion(mid)) {
                right = mid; // 答案在区间 [left, mid] 中
            } else {
                left = mid + 1; // 答案在区间 [mid+1, right] 中
            }
        }
        // 此时有 left == right，区间缩为一个点，即为答案
        return left;
    }
};

动态规划

爬楼梯

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

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

示例 2：

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

提示：

1 <= n <= 45

我的解法

class Solution {
public:
    int climbStairs(int n) {
        int* dp=new int[n+1];
        dp[0]=1;
        dp[1]=1;
        for(int i=2;i<=n;i++)
        {
            dp[i]=dp[i-1]+dp[i-2];
        }
        return dp[n];
    }
};

买卖股票的最佳时机

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0 。

示例 1：

输入：[7,1,5,3,6,4]
输出：5
解释：在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。
     注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票。

示例 2：

输入：prices = [7,6,4,3,1]
输出：0
解释：在这种情况下, 没有交易完成, 所以最大利润为 0。

提示：

1 <= prices.length <= 105
0 <= prices[i] <= 104

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xn8fsh/

我的解法

一

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int n=prices.size();
        vector<int> dp1;//前面的最小值
        vector<int> dp2;//最大能赚多少
        dp1.resize(n);
        dp2.resize(n);
        dp1[0]=prices[0];
        dp2[0]=0;
        for(int i=1;i<n;i++)
        {
            dp1[i]=min(dp1[i-1],prices[i]);
            dp2[i]=max(dp2[i-1],prices[i]-dp1[i]);
        }
        return dp2[n-1];
    }
};

二

计算差数组，转化为最大子序和问题

官解

我们只需要遍历价格数组一遍，记录历史最低点，然后在每一天考虑这么一个问题：如果我是在历史最低点买进的，那么我今天卖出能赚多少钱？当考虑完所有天数之时，我们就得到了最好的答案。

最大子序和

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

1 <= nums.length <= 105
-104 <= nums[i] <= 104

进阶：如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的 分治法 求解。

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xn3cg3/

我的解法

动态规划

$dp[i]$为[x,i]的最大子序和（x∈[0,i]）

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        int n=nums.size();
        vector<int> dp;
        dp.resize(n);
        dp[0]=nums[0];
        for(int i=1;i<n;i++)
        {
            dp[i]=max(nums[i],dp[i-1]+nums[i]);
        }
        int max=-2147483647;
        for(int i=0;i<n;i++)
        {
            if(dp[i]>max)
                max=dp[i];
        }
        return max;
    }
};

递归

class Solution {
public:
    int maxSubArray(vector<int>& nums) {
        return get(nums,0,nums.size()-1);
    }
    int get(vector<int>& nums,int l,int r)
    {
        if(l==r)
        {
            return nums[l];
        }
        int mid=(l+r)/2;
        int cross_l=0,cross_r=0,max_l=-2147483648,max_r=-2147483648;
        for(int i=mid;i>=l;i--)
        {
            cross_l+=nums[i];
            max_l=max(max_l,cross_l);
        }
        for(int i=mid+1;i<=r;i++)
        {
            cross_r+=nums[i];
            max_r=max(max_r,cross_r);
        }
        return max(max(get(nums,l,mid),get(nums,mid+1,r)),max_l+max_r);
    }
};

官解

动态规划

可以节约空间复杂度O（n）→O（1）

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;
    }
};

递归

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;
    }
};

打家劫舍

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

1 <= nums.length <= 100
0 <= nums[i] <= 400

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnq4km/

我的解法

class Solution {
public:
    int rob(vector<int>& nums) {
        int n=nums.size();
        vector<int> dp1,dp2;
        //dp1[i]:偷i
        //dp2[i]:不偷i
        dp1.resize(n);
        dp2.resize(n);
        dp1[0]=nums[0];
        dp2[0]=0;
        for(int i=1;i<n;i++)
        {
            dp1[i]=dp2[i-1]+nums[i];
            dp2[i]=max(dp1[i-1],dp2[i-1]);
        }
        return max(dp1[n-1],dp2[n-1]);
    }
};

官解

不同的DP定义

用 dp[i] 表示前 i 间房屋能偷窃到的最高总金额，那么就有如下的状态转移方程：

$\text{dp}[i]=\max (\text{dp}[i-2]+\text{nums}[i],\text{dp}[i-1])$

节约空间

上述方法使用了数组存储结果。考虑到每间房屋的最高总金额只和该房屋的前两间房屋的最高总金额相关，因此可以使用滚动数组，在每个时刻只需要存储前两间房屋的最高总金额。

class Solution {
public:
    int rob(vector<int>& nums) {
        if (nums.empty()) {
            return 0;
        }
        int size = nums.size();
        if (size == 1) {
            return nums[0];
        }
        int first = nums[0], second = max(nums[0], nums[1]);
        for (int i = 2; i < size; i++) {
            int temp = second;
            second = max(first + nums[i], second);
            first = temp;
        }
        return second;
    }
};

设计问题

这类问题通常要求你实现一个给定的类的接口，并可能涉及使用一种或多种数据结构。 这些问题对于提高数据结构是很好的练习。

打乱数组

给你一个整数数组 nums ，设计算法来打乱一个没有重复元素的数组。打乱后，数组的所有排列应该是 等可能 的。

实现 Solution class:

• Solution(int[] nums) 使用整数数组 nums 初始化对象

• int[] reset() 重设数组到它的初始状态并返回

• int[] shuffle() 返回数组随机打乱后的结果

示例 1：

输入
["Solution", "shuffle", "reset", "shuffle"]
[[[1, 2, 3]], [], [], []]
输出
[null, [3, 1, 2], [1, 2, 3], [1, 3, 2]]

解释
Solution solution = new Solution([1, 2, 3]);
solution.shuffle();    // 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。例如，返回 [3, 1, 2]
solution.reset();      // 重设数组到它的初始状态 [1, 2, 3] 。返回 [1, 2, 3]
solution.shuffle();    // 随机返回数组 [1, 2, 3] 打乱后的结果。例如，返回 [1, 3, 2]

提示：

1 <= nums.length <= 50
-106 <= nums[i] <= 106
nums 中的所有元素都是 唯一的
最多可以调用 104 次 reset 和 shuffle

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xn6gq1/

官解

就一洗牌算法没什么意思直接抄了

class Solution {
public:
    Solution(vector<int>& nums) {
        this->nums = nums;
        this->original.resize(nums.size());
        copy(nums.begin(), nums.end(), original.begin());
    }
    
    vector<int> reset() {
        copy(original.begin(), original.end(), nums.begin());
        return nums;
    }
    
    vector<int> shuffle() {
        for (int i = 0; i < nums.size(); ++i) {
            int j = i + rand() % (nums.size() - i);
            swap(nums[i], nums[j]);
        }
        return nums;
    }
private:
    vector<int> nums;
    vector<int> original;
};

作者：LeetCode-Solution
链接：https://leetcode.cn/problems/shuffle-an-array/solution/da-luan-shu-zu-by-leetcode-solution-og5u/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

*最小栈

设计一个支持 push ，pop ，top 操作，并能在常数时间内检索到最小元素的栈。

实现 MinStack 类:

• MinStack() 初始化堆栈对象。
• void push(int val) 将元素val推入堆栈。
• void pop() 删除堆栈顶部的元素。
• int top() 获取堆栈顶部的元素。
• int getMin() 获取堆栈中的最小元素。

示例 1:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.

提示：

-231 <= val <= 231 - 1
pop、top 和 getMin 操作总是在 非空栈 上调用
push, pop, top, and getMin最多被调用 3 * 104 次

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnkq37/

官解

辅助栈

要做出这道题目，首先要理解栈结构先进后出的性质。

对于栈来说，如果一个元素 a 在入栈时，栈里有其它的元素 b, c, d，那么无论这个栈在之后经历了什么操作，只要 a 在栈中，b, c, d 就一定在栈中，因为在 a 被弹出之前，b, c, d 不会被弹出。

因此，在操作过程中的任意一个时刻，只要栈顶的元素是 a，那么我们就可以确定栈里面现在的元素一定是 a, b, c, d。

那么，我们可以在每个元素 a 入栈时把当前栈的最小值 m 存储起来。在这之后无论何时，如果栈顶元素是 a，我们就可以直接返回存储的最小值 m。

class MinStack {
    stack<int> x_stack;
    stack<int> min_stack;
public:
    MinStack() {
        min_stack.push(INT_MAX);
    }
    
    void push(int x) {
        x_stack.push(x);
        min_stack.push(min(min_stack.top(), x));
    }
    
    void pop() {
        x_stack.pop();
        min_stack.pop();
    }
    
    int top() {
        return x_stack.top();
    }
    
    int getMin() {
        return min_stack.top();
    }
};

不需要辅助栈

记录差值

class MinStack {
public:
    stack<long long> stk;
    long long min;
    MinStack() {
        stack<long long> s;
        stk=s;
        min=2147483648;
    }
    
    void push(int val) {
        if(stk.empty())
        {
            stk.push(0);
            min=val;
        }
        else
        {
            long long diff=(long long)val-min;
            if(diff>=0)
            {
                stk.push(diff);
            }
            else
            {
                min=val;
                stk.push(diff);
            }
        }
    }
    
    void pop() {
        if(!stk.empty())
        {
            if(stk.top()>0)
            {
                stk.pop();
            }
            else{
                min-=stk.top();
                stk.pop();
            }
        }
    }
    
    int top() {
        if(stk.top()<0)
        {
            return min;
        }
        else
        {
            return min+stk.top();
        }
    }
    
    int getMin() {
        return min;
    }
};

数学

Fizz Buzz

给你一个整数 n ，找出从 1 到 n 各个整数的 Fizz Buzz 表示，并用字符串数组 answer（下标从 1 开始）返回结果，其中：

answer[i] == “FizzBuzz” 如果 i 同时是 3 和 5 的倍数。
answer[i] == “Fizz” 如果 i 是 3 的倍数。
answer[i] == “Buzz” 如果 i 是 5 的倍数。
answer[i] == i （以字符串形式）如果上述条件全不满足。

示例 1：

输入：n = 3
输出：[“1”,“2”,“Fizz”]
示例 2：

输入：n = 5
输出：[“1”,“2”,“Fizz”,“4”,“Buzz”]
示例 3：

输入：n = 15
输出：[“1”,“2”,“Fizz”,“4”,“Buzz”,“Fizz”,“7”,“8”,“Fizz”,“Buzz”,“11”,“Fizz”,“13”,“14”,“FizzBuzz”]

提示：

1 <= n <= 104

我的解法

class Solution {
public:
    vector<string> fizzBuzz(int n) {
        vector<string> v;
        v.resize(n);
        for(int i=1;i<=n;i++)
        {
            if(i%15==0)
            {
                v[i-1]="FizzBuzz";
            }
            else if(i%3==0)
                v[i-1]="Fizz";
            else if(i%5==0)
                v[i-1]="Buzz";
            else
                v[i-1]=to_string(i);
        }
        return v;
    }
};

*计数质数

给定整数 n ，返回 所有小于非负整数 n 的质数的数量 。

示例 1：

输入：n = 10
输出：4
解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。

示例 2：

输入：n = 0
输出：0

示例 3：

输入：n = 1
输出：0

提示：

0 <= n <= 5 * 106

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnzlu6/

官解

埃氏筛
枚举没有考虑到数与数的关联性，因此难以再继续优化时间复杂度。接下来我们介绍一个常见的算法，该算法由希腊数学家厄拉多塞（Eratosthenes）提出，称为厄拉多塞筛法，简称埃氏筛。

我们考虑这样一个事实：如果 x 是质数，那么大于 x 的 x 的倍数 2x,3x,… 一定不是质数，因此我们可以从这里入手。

我们设 isPrime[i] 表示数 ii 是不是质数，如果是质数则为 1，否则为 0。从小到大遍历每个数，如果这个数为质数，则将其所有的倍数都标记为合数（除了该质数本身），即 0，这样在运行结束的时候我们即能知道质数的个数。

这种方法的正确性是比较显然的：这种方法显然不会将质数标记成合数；另一方面，当从小到大遍历到数 x 时，倘若它是合数，则它一定是某个小于 x 的质数 y 的整数倍，故根据此方法的步骤，我们在遍历到 y 时，就一定会在此时将 x 标记为 isPrime[x]=0。因此，这种方法也不会将合数标记为质数。

当然这里还可以继续优化，对于一个质数 xx，如果按上文说的我们从 2x 开始标记其实是冗余的，应该直接从 x⋅x 开始标记，因为 2x,3x,… 这些数一定在 x 之前就被其他数的倍数标记过了，例如 2 的所有倍数，3 的所有倍数等。

class Solution {
public:
    int countPrimes(int n) {
        vector<int> isPrime(n, 1);
        int ans = 0;
        for (int i = 2; i < n; ++i) {
            if (isPrime[i]) {
                ans += 1;
                if ((long long)i * i < n) {
                    for (int j = i * i; j < n; j += i) {
                        isPrime[j] = 0;
                    }
                }
            }
        }
        return ans;
    }
};

欧拉筛（线性筛）

看讲解吧

讲解

讲的很不错：https://zhuanlan.zhihu.com/p/100051075

3的幂

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。

整数 n 是 3 的幂次方需满足：存在整数 x 使得 n == 3x

示例 1：

输入：n = 27
输出：true

示例 2：

输入：n = 0
输出：false

示例 3：

输入：n = 9
输出：true

示例 4：

输入：n = 45
输出：false

提示：

-231 <= n <= 231 - 1

进阶：你能不使用循环或者递归来完成本题吗？

链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/xnsdi2/

我的解法

class Solution {
public:
    bool isPowerOfThree(int n) {
        if(n<=0)
            return false;
        if(n==1)
            return true;
        if(n%3==0)
        {
            return isPowerOfThree(n/3);
        }
        else
        {
            return false;
        }
    }
};

官解

方法一同我的解法

迭代（节省递归栈空间）

class Solution {
public:
    bool isPowerOfThree(int n) {
        while (n && n % 3 == 0) {
            n /= 3;
        }
        return n == 1;
    }
};

方法二

32 位有符号整数的范围内，最大的 3 的幂为 3^19 = 1162261467。我们只需要判断 n 是否是 3^19约数即可。

与方法一不同的是，这里需要特殊判断 n 是负数或 0 的情况。

class Solution {
public:
    bool isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
};

罗马数字转整数

罗马数字包含以下七种字符: 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 。

我的解法

class Solution {
public:
    int romanToInt(string s) {
        if(s=="")
        {
            return 0;
        }
        if(s[0]=='M')
        {
            s.erase(0,1);
            return 1000+romanToInt(s);
        }
        else if(s[0]=='D')
        {
            s.erase(0,1);
            return 500+romanToInt(s);
        }
        else if(s[0]=='C')
        {
            if(s[1]=='D')
            {
                s.erase(0,2);
                return 400+romanToInt(s);
            }
            else if(s[1]=='M')
            {
                s.erase(0,2);
                return 900+romanToInt(s);
            }
            else
            {
                s.erase(0,1);
                return 100+romanToInt(s);
            }
        }
        else if(s[0]=='L')
        {
            s.erase(0,1);
            return 50+romanToInt(s);
        }
        else if(s[0]=='X')
        {
            if(s[1]=='L')
            {
                s.erase(0,2);
                return 40+romanToInt(s);
            }
            else if(s[1]=='C')
            {
                s.erase(0,2);
                return 90+romanToInt(s);
            }
            else
            {
                s.erase(0,1);
                return 10+romanToInt(s);
            }
        }
        else if(s[0]=='V')
        {
            s.erase(0,1);
            return 5+romanToInt(s);
        }
        else
        {
            if(s[1]=='V')
            {
                s.erase(0,2);
                return 4+romanToInt(s);
            }
            else if(s[1]=='X')
            {
                s.erase(0,2);
                return 9+romanToInt(s);
            }
            else
            {
                s.erase(0,1);
                return 1+romanToInt(s);
            }
        }
    }
};

官解

通常情况下，罗马数字中小的数字在大的数字的右边。若输入的字符串满足该情况，那么可以将每个字符视作一个单独的值，累加每个字符对应的数值即可。

例如 XXVII 可视作 X+X+V+I+I=10+10+5+1+1=27。

若存在小的数字在大的数字的左边的情况，根据规则需要减去小的数字。对于这种情况，我们也可以将每个字符视作一个单独的值，若一个数字右侧的数字比它大，则将该数字的符号取反。

例如 XIV 可视作 X−I+V=10−1+5=14。

class Solution {
private:
    unordered_map<char, int> symbolValues = {
        {'I', 1},
        {'V', 5},
        {'X', 10},
        {'L', 50},
        {'C', 100},
        {'D', 500},
        {'M', 1000},
    };

public:
    int romanToInt(string s) {
        int ans = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            int value = symbolValues[s[i]];
            if (i < n - 1 && value < symbolValues[s[i + 1]]) {
                ans -= value;
            } else {
                ans += value;
            }
        }
        return ans;
    }
};

其他

位1的个数

编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。

提示：

请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在上面的 示例 3 中，输入表示有符号整数 -3。

示例 1：

输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

示例 2：

输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。

示例 3：

输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。

提示：

输入必须是长度为 32 的 二进制串 。

进阶：

如果多次调用这个函数，你将如何优化你的算法？

我的解答

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int ans=0;
        while(n!=0)
        {
            if(n%2==1)
            {
                ans++;
            }
            n=n>>1;
        }
        return ans;
    }
};

官解

位运算优化

观察这个运算：n & (n−1)，其运算结果恰为把 n 的二进制位中的最低位的 1 变为 0 之后的结果。

时间复杂度：循环次数等于 n 的二进制位中 1 的个数

eg.1000…0001我的解法需要32次，优化解法只需两次

class Solution {
public:
    int hammingWeight(uint32_t n) {
        int ret = 0;
        while (n) {
            n &= n - 1;
            ret++;
        }
        return ret;
    }
};

汉明距离

两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 x 和 y，计算并返回它们之间的汉明距离。

示例 1：

输入：x = 1, y = 4
输出：2
解释：
1   (0 0 0 1)
4   (0 1 0 0)
       ↑   ↑
上面的箭头指出了对应二进制位不同的位置。

示例 2：

输入：x = 3, y = 1
输出：1

我的解法

class Solution {
public:
    int hammingDistance(int x, int y) {
        int n=x^y;
        int ans=0;
        while(n!=0)
        {
            n&=(n-1);
            ans++;
        }
        return ans;
    }
};

官解

方法一：内置位计数功能

大多数编程语言都内置了计算二进制表达中 1 的数量的函数。在工程中，我们应该直接使用内置函数。

class Solution {
public:
    int hammingDistance(int x, int y) {
        return __builtin_popcount(x ^ y);
    }
};

颠倒二进制位

颠倒给定的 32 位无符号整数的二进制位。

提示：

• 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
• 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 2 中，输入表示有符号整数 -3，输出表示有符号整数 -1073741825。

示例 1：

输入：n = 00000010100101000001111010011100
输出：964176192 (00111001011110000010100101000000)
解释：输入的二进制串 00000010100101000001111010011100 表示无符号整数 43261596，
     因此返回 964176192，其二进制表示形式为 00111001011110000010100101000000。

示例 2：

输入：n = 11111111111111111111111111111101
输出：3221225471 (10111111111111111111111111111111)
解释：输入的二进制串 11111111111111111111111111111101 表示无符号整数 4294967293，
     因此返回 3221225471 其二进制表示形式为 10111111111111111111111111111111 。

提示：

输入是一个长度为 32 的二进制字符串

进阶: 如果多次调用这个函数，你将如何优化你的算法？

我的解法

class Solution {
public:
    uint32_t reverseBits(uint32_t n) {
        uint32_t ans=0;
        for(int i=0;i<32;i++)
        {
            ans<<=1;ans+=n%2;
            n>>=1;
        }
        return ans;
    }
};

官解

方法二：位运算分治
思路

若要翻转一个二进制串，可以将其均分成左右两部分，对每部分递归执行翻转操作，然后将左半部分拼在右半部分的后面，即完成了翻转。

由于左右两部分的计算方式是相似的，利用位掩码和位移运算，我们可以自底向上地完成这一分治流程。

class Solution {
private:
    const uint32_t M1 = 0x55555555; // 01010101010101010101010101010101
    const uint32_t M2 = 0x33333333; // 00110011001100110011001100110011
    const uint32_t M4 = 0x0f0f0f0f; // 00001111000011110000111100001111
    const uint32_t M8 = 0x00ff00ff; // 00000000111111110000000011111111

public:
    uint32_t reverseBits(uint32_t n) {
        n = n >> 1 & M1 | (n & M1) << 1;
        n = n >> 2 & M2 | (n & M2) << 2;
        n = n >> 4 & M4 | (n & M4) << 4;
        n = n >> 8 & M8 | (n & M8) << 8;
        return n >> 16 | n << 16;
    }
};

杨辉三角

给定一个非负整数 numRows，生成「杨辉三角」的前 numRows 行。

在「杨辉三角」中，每个数是它左上方和右上方的数的和。

示例 1:

输入: numRows = 5
输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]

示例 2:

输入: numRows = 1
输出: [[1]]

提示:

1 <= numRows <= 30

我的解法

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ans;
        vector<int> v(1,1);
        ans.push_back(v);
        for(int i=1;i<numRows;i++)
        {
            vector<int> row;
            row.push_back(1);
            for(int j=0;j<i-1;j++)
            {
                row.push_back(ans[i-1][j]+ans[i-1][j+1]);
            }
            row.push_back(1);
            ans.push_back(row);
        }
        return ans;
    }
};

官解

学学人家代码怎么写的

class Solution {
public:
    vector<vector<int>> generate(int numRows) {
        vector<vector<int>> ret(numRows);//利用好构造函数！
        for (int i = 0; i < numRows; ++i) {
            ret[i].resize(i + 1);
            ret[i][0] = ret[i][i] = 1;
            for (int j = 1; j < i; ++j) {
                ret[i][j] = ret[i - 1][j] + ret[i - 1][j - 1];
            }
        }
        return ret;
    }
};

有效的括号

给定一个只包括 ‘(’，‘)’，‘{’，‘}’，‘[’，‘]’ 的字符串 s ，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

示例 1：

输入：s = "()"
输出：true

示例 2：

输入：s = "()[]{}"
输出：true

示例 3：

输入：s = "(]"
输出：false

示例 4：

输入：s = "([)]"
输出：false

示例 5：

输入：s = "{[]}"
输出：true

提示：

1 <= s.length <= 104
s 仅由括号 '()[]{}' 组成

我的解法

栈

class Solution {
public:
    bool isValid(string s) {
        int n=s.size();
        stack<char> stk;
        for(int i=0;i<n;i++)
        {
            if(s[i]=='('||s[i]=='['||s[i]=='{')
            {
                stk.push(s[i]);
            }
            else
            {
                if(s[i]==')')
                {
                    if(!stk.empty()&&stk.top()=='(')
                    {
                        stk.pop();
                    }
                    else
                    {
                        return false;
                    }
                }
                else if(s[i]==']')
                {
                    if(!stk.empty()&&stk.top()=='[')
                    {
                        stk.pop();
                    }
                    else
                    {
                        return false;
                    }
                }
                else if(s[i]=='}')
                {
                    if(!stk.empty()&&stk.top()=='{')
                    {
                        stk.pop();
                    }
                    else
                    {
                        return false;
                    }
                }
            }
        }
        if(stk.empty())
            return true;
        else    
            return false;
    }
};

官解

学学人家这代码！

学会用map，别一天到晚枚举

class Solution {
public:
    bool isValid(string s) {
        int n = s.size();
        if (n % 2 == 1) {
            return false;
        }

        unordered_map<char, char> pairs = {
            {')', '('},
            {']', '['},
            {'}', '{'}
        };
        stack<char> stk;
        for (char ch: s) {
            if (pairs.count(ch)) {
                if (stk.empty() || stk.top() != pairs[ch]) {
                    return false;
                }
                stk.pop();
            }
            else {
                stk.push(ch);
            }
        }
        return stk.empty();
    }
};

缺失数字

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

示例 1：

输入：nums = [3,0,1]
输出：2
解释：n = 3，因为有 3 个数字，所以所有的数字都在范围 [0,3] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 2：

输入：nums = [0,1]
输出：2
解释：n = 2，因为有 2 个数字，所以所有的数字都在范围 [0,2] 内。2 是丢失的数字，因为它没有出现在 nums 中。

示例 3：

输入：nums = [9,6,4,2,3,5,7,0,1]
输出：8
解释：n = 9，因为有 9 个数字，所以所有的数字都在范围 [0,9] 内。8 是丢失的数字，因为它没有出现在 nums 中。

示例 4：

输入：nums = [0]
输出：1
解释：n = 1，因为有 1 个数字，所以所有的数字都在范围 [0,1] 内。1 是丢失的数字，因为它没有出现在 nums 中。

提示：

n == nums.length
1 <= n <= 104
0 <= nums[i] <= n
nums 中的所有数字都 独一无二

进阶：你能否实现线性时间复杂度、仅使用额外常数空间的算法解决此问题?

我的解法

异或

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n=nums.size();
        int ans=0;
        for(int i=0;i<n+1;i++)
        {
            ans^=i;
        }
        for(int i=0;i<n;i++)
        {
            ans^=nums[i];
        }
        return ans;
    }
};

官解

另一种解法（数学求和）

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int total = n * (n + 1) / 2;
        int arrSum = 0;
        for (int i = 0; i < n; i++) {
            arrSum += nums[i];
        }
        return total - arrSum;
    }
};

总结

早就意识到自己算法能力偏薄弱了但迟迟没有做出努力

大二结束了才开始刷题或许有些为时已晚，但今天开始总比明天开始更好

下次刷题就不按这种每一题都做笔记的方式了，有些浪费时间也不易浏览

以后只对有难度的题/有感悟的每个单独的题专门写一个笔记出来

总的来说还是感谢自己这几天的坚持