前言
记录了个人学习LeetCode初级算法的过程，本身是作为考研数据结构的强化练习，均使用C语言完成。
数组
删除排序数组中的重复项
题目描述
给你一个升序排列的数组 nums ，请你原地删除重复出现的元素，使每个元素只出现一次，返回删除后数组的新长度。元素的相对顺序应该保持 一致 。
由于在某些语言中不能改变数组的长度，所以必须将结果放在数组nums的第一部分。更规范地说，如果在删除重复项之后有 k 个元素，那么 nums 的前 k 个元素应该保存最终结果。
将最终结果插入 nums 的前 k 个位置后返回 k 。
不要使用额外的空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
判题标准:
系统会用下面的代码来测试你的题解:
int[] nums = [...]; // 输入数组
int[] expectedNums = [...]; // 长度正确的期望答案
int k = removeDuplicates(nums); // 调用
assert k == expectedNums.length;
for (int i = 0; i < k; i++) {
assert nums[i] == expectedNums[i];
}
如果所有断言都通过，那么您的题解将被 通过。
示例 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 。不需要考虑数组中超出新长度后面的元素。
提示：
- 1 <= nums.length <= 3 * 104
- 104 <= nums[i] <= 104
- nums 已按 升序 排列
作者：力扣 (LeetCode)
链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/x2gy9m/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
解答
花费了7min50s
int removeDuplicates(int* nums, int numsSize){
int* pn = nums;
int newSize = 1;
for(int i = 0;i < numsSize; i++){
if(*pn == *nums)
pn++;
else{
newSize++;
nums++;
*nums = *pn;
pn++;
}
}
return newSize;
}
思路
因为题目中说是升序数组，所以后面的数是大于等于前面的数的，而相等的数必定会相邻，如此，只需要记下前一个不重复的数，然后创建一个工作指针，按照数组的大小依次遍历整个数组，如若碰到了不同的数，只需要将其记录到新的数组中，并且使数组的大小加1即可，而且题目中允许我们不处理后面多余的元素，这也使得我们的算法不需要新数组的辅助，可以实现原地。
题解
int removeDuplicates(int* nums, int numsSize) {
if (numsSize == 0) {
return 0;
}
int fast = 1, slow = 1;
while (fast < numsSize) {
if (nums[fast] != nums[fast - 1]) {
nums[slow] = nums[fast];
++slow;
}
++fast;
}
return slow;
}
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/remove-duplicates-from-sorted-array/solution/shan-chu-pai-xu-shu-zu-zhong-de-zhong-fu-tudo/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
总结
题解的思路和我们是相同的，本质上都是使用了双指针，我使用的是指针，而题解使用的是数组下标的方式，区别不大，但是可以发现题解的代码比我的要更加简洁精炼一些，本质上是我使用的工作指针每轮循环中是固定需要加1的，所以其实不需要if-else的判断，只需要对发现不重复数据的情况进行处理即可。
买卖股票的最佳时机 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 * 1040 <= prices[i] <= 104
作者：力扣 (LeetCode)
链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/x2zsx1/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
解答
花费17min18s
int maxProfit(int* prices, int pricesSize){
int in, out, now, all;
all = 0;
int state = 1;
for(int i = 1;i < pricesSize; i++){
if(*(prices + i - 1) < *(prices + i) && state == 1){
in = *(prices + i - 1);
state = 0;
}
if(*(prices + i - 1) > *(prices + i) && state == 0){
out = *(prices + i - 1);
state = 1;
all = all + out - in;
}
if(i == pricesSize - 1 && state == 0){
out = *(prices + i);
all = all + out - in;
}
}
return all;
}
思路
题目是一道情景题，完全可以按照常识进行分析，可以将股票每天的变化看成是一个函数，只不过现在我们只有离散的数据，所以这个题目本质上就是求出函数所有的极大值和极小值，所以只需要不断计算梯度（导数），然后找到梯度（导数）变化的点，其中极小值点对应函数值记为买入，极大值点对应函数值记为卖出，然后每当出现卖出的时候，向总收益中添加一笔（卖出 - 买入），最后考虑到数组是离散的，还需要对端点进行特殊处理。
题解
方法一：动态规划
int maxProfit(int* prices, int pricesSize) {
int dp0 = 0, dp1 = -prices[0];
for (int i = 1; i < pricesSize; ++i) {
int newDp0 = fmax(dp0, dp1 + prices[i]);
int newDp1 = fmax(dp1, dp0 - prices[i]);
dp0 = newDp0;
dp1 = newDp1;
}
return dp0;
}
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/solution/mai-mai-gu-piao-de-zui-jia-shi-ji-ii-by-leetcode-s/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
方法二：贪心算法
int maxProfit(int* prices, int pricesSize) {
int ans = 0;
for (int i = 1; i < pricesSize; ++i) {
ans += fmax(0, prices[i] - prices[i - 1]);
}
return ans;
}
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-ii/solution/mai-mai-gu-piao-de-zui-jia-shi-ji-ii-by-leetcode-s/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
总结
动态规划解法
题解给的方法都比较有意思，通过状态转移方程进行解释也十分的直观，这里不妨使用动态规划的基本思路来分析一遍。首先回顾动态规划问题的基本设计步骤：
- 刻画一个最优解的结构特征
- 递归地定义最优解的值
- 计算最优解的值
- 利用计算出的信息构造一个最优解
首先，使用动态规划的话我们需要找出最优子结构（如果一个问题的最优解包含其子问题的最优解，我们就称此问题具有最优子结构），对于这道题，题目要求我们求出最后一天时能得到的最大利润，我们设有n天，也就是说需要知道第n天时我们能获得的最大利润，那么这时就产生了一个子问题，第n-1天时最大利润是多少，如此，最优子结构就浮现出来了。
然后我们就需要重构最优解，现在我们需要将问题拆分成两个部分，已知第k天的最大利润，我们怎么得到第k+1天的最大利润。其实很简单，就是看昨天持有的股票如果今天卖了是赚还是亏，如果卖了会赚就卖，卖了不赚就不卖，然后与昨天的最大利润进行对比，去最大值作为今天的最大利润，这也是题解中转移方程的含义。
由此，我们需要定义两个参数，分别是第i天的最大利润和第i天持有股票时的最大利润，有了这两个参数我们就能够通过上述的方法递归地求解问题，而这两个参数是我们所能够获得的。
不过最后我们可以发现，这道题可以使用动态规划的思想，但是并不是十分好用，动态规划的特点是对重叠子问题进行备忘，相对而言这道题使用贪心算法是很直观的，容易想到也容易实现。
贪心算法解法
我们已经发现该问题可以确定出具有最优子结构，那么贪心算法也就进入了我们的考虑范围之内，要想使用贪心算法，除了需要证明具有最优子结构外，比较重要的一点是需要确保贪心选择总是安全的。
所谓贪心，在该问题中就是每天都假设进行股票的买卖，然后看是否产生了收益，对于第i天购入的股票，我们都在第i+1天考虑卖出这个操作，如果卖出是赚的我们就卖，如果不赚，我们就可以采取“昨天不买”的操作，毕竟问题中我们就像一个先知，知道未来的走势，也就是说，贪心算法就像我们炒股炒短期，我们每天可能的收益就是max{0, a[i] - a[i-1]}，a代表的是股票的价格。具体数学上如何证明安全性就暂且不管了，至少从逻辑上我们是有这个直觉的。
总结
不同解法的思路还是有加大区别的，这道题用暴力解法也能够做出来，不过官方提供的思路还是很有学习的价值的。题解中将问题阐述得简单易懂，平时思考时也要注意问题的简化。
旋转数组
题目描述
给你一个数组，将数组中的元素向右轮转 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 - 10 <= k <= 105
作者：力扣 (LeetCode)
链接：https://leetcode.cn/leetbook/read/top-interview-questions-easy/x2skh7/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
解答
花费6min18s
void reverse(int* nums, int begin, int end){
while(begin != end && (begin - 1) != end){
int temp = nums[begin];
nums[begin] = nums[end];
nums[end] = temp;
begin++;
end--;
}
}
void rotate(int* nums, int numsSize, int k){
k %= numsSize;
reverse(nums, 0, numsSize - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, numsSize - 1);
}
思路
考研常客，旋转数组，最容易想到的标准解法，通过多次翻转达到数组轮转的效果，原地算法，时间复杂度O(n)，没有多说的含金量，可以尝试多种解法。
题解
方法一：使用额外数组
void rotate(int* nums, int numsSize, int k) {
int newArr[numsSize];
for (int i = 0; i < numsSize; ++i) {
newArr[(i + k) % numsSize] = nums[i];
}
for (int i = 0; i < numsSize; ++i) {
nums[i] = newArr[i];
}
}
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/rotate-array/solution/xuan-zhuan-shu-zu-by-leetcode-solution-nipk/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
方法二：环状替代
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
void swap(int* a, int* b) {
int t = *a;
*a = *b, *b = t;
}
void rotate(int* nums, int numsSize, int k) {
k = k % numsSize;
int count = gcd(k, numsSize);
for (int start = 0; start < count; ++start) {
int current = start;
int prev = nums[start];
do {
int next = (current + k) % numsSize;
swap(&nums[next], &prev);
current = next;
} while (start != current);
}
}
作者：LeetCode-Solution
链接：https://leetcode.cn/problems/rotate-array/solution/xuan-zhuan-shu-zu-by-leetcode-solution-nipk/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
方法三：数组翻转
void swap(int* a, int* b) {
int t = *a;
*a = *b, *b = t;
}
void reverse(int* nums, int start, int end) {
while (start < end) {
swap(&nums[start], &nums[end]);
start += 1;
end -= 1;
}
}
void rotate(int* nums, int numsSize, int k) {
k %= numsSize;
reverse(nums, 0, numsSize - 1);
reverse(nums, 0, k - 1);
reverse(nums, k, numsSize - 1);
}
作者：demigodliu
链接：https://leetcode.cn/problems/rotate-array/solution/shu-zu-fan-zhuan-xuan-zhuan-shu-zu-by-de-5937/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
总结
典型题，数组翻转是最容易实现的方法，并且拥有O(n)的时间复杂度和O(1)的空间复杂度，是必须记住的内容。方法一是最朴实的，也很容易想到，本质上是解析轮转前后数组的变化，然后进行映射。方法二相对比较有意思，但是因为要设定一个终止条件，实现起来稍微复杂一点，题解中使用最大公约数的方法十分巧妙。
存在重复元素
题目描述
给你一个整数数组 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
解答
花费15min（结果未通过）
void swap(int* nums, int i, int j){
int temp;
temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
int Partition(int* nums, int p, int r){
int x = nums[r];
int i = p - 1;
for(int j = p;j < r;j++){
if(nums[j] <= x){
i++;
swap(nums, i, j);
}
}
swap(nums, i + 1, r);
return i + 1;
}
void quickSort(int* nums, int p, int r){
if(p < r){
int q = Partition(nums, p, r);
quickSort(nums, p, q - 1);
quickSort(nums, q, r);
}
}
bool containsDuplicate(int* nums, int numsSize){
quickSort(nums, 0 ,numsSize - 1);
for(int i = 0; i < numsSize; i++){
if(nums[i] == nums[i + 1])
return true;
}
return false;
}
思路
思路肯定有两种，一是使用hashmap，也就是哈希表，遍历整个数组，与哈希表进行比对，如果出现新元素则在哈希表中记录，如若出现重复元素则可直接返回true；二是先进行排序，然后再遍历整个数组，将相邻的元素之间进行比较，判断是否出现了相同的元素。
总结
思路还是很简单的，但是并不好使用C语言进行实现，题解中是直接使用了qsort，也就是快速排序，上面解答中也是使用的快速排序的思想，但是并没有进行优化，只是最朴实的快排，也如预料的超时了，题解中使用C语言实现哈希表的方法不是很熟悉，用C++的话是十分方便的。
其实还有想过使用红黑树来对数组进行存储和查找，但是实现起来有些繁琐，和C++使用map的话是一个道理，C++的map容器底层也是利用的红黑树，从而做到容器中没有相同的值。由此说来使用C++的话也可以使用map容器解决，因为向map容器中加值时如果出现重复是会返回false的，但是效率上面是不如哈希表的，既然都用了容器，还是直接哈希表更好一些。
如果是限定了正整数返回，且值的取值范围较为有限，例如[1~n]，则，可以直接定义一个数组a[n]来对已存在的元素进行标记，使用额外的数组来进行标记也是一种空间换时间的做法，特殊情况下非常好用。
加一
题目描述
给定一个由整数组成的非空数组所表示的非负整数，在该数的基础上加一。
最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外，这个整数不会以零开头。
解题思路
该问题主要涉及到的是进位判断，我直接使用int carry来记录进位的数据，并且设定初始值为1，对数组从后往前进行遍历，判断如果+1之后变为了10，则直接赋值为0，然后保持carry值为1，即存在进位，如果+1之后不为10，则直接打破循环。
具体的代码实现中还需要加上一些特殊情况的考虑。、
解题代码
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
int index = digits.size() - 1;
int carry = 1;
while(index){
digits[index] += carry;
if(digits[index] == 10){
digits[index] = 0;
index--;
continue;
}
else{
carry = 0;
break;
}
}
digits[0] += carry;
if(digits[0] == 10){
digits[0] = 0;
digits.insert(digits.begin(), 1);
}
return digits;
}
};
值得注意的就是对于[*]（只有一个数字）和[9,9,9]（值全部为9）两种特殊情况的判断，需要纳入到整体的逻辑中去。
移动零
题目描述
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
请注意 ，必须在不复制数组的情况下原地对数组进行操作。
解题思路
最开始想到的方法就是记录0的个数为n，然后让所有非零的数全部前移，最后将后面的n个数全部赋值为0；本质上与双指针的解法类似。
解题代码
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int n = 0;
int s = nums.size();
for(int i = 0; i < s; i++){
if(nums[i] == 0){
n++;
}
else{
nums[i - n] = nums[i];
}
}
for(int i = s - n; i < s; i++){
nums[i] = 0;
}
}
};
字符串
整数反转
题目描述
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。
假设环境不允许存储 64 位整数（有符号或无符号）。
解题思路
这道题初见时我的思路是先将整数转换为字符串，然后对字符串进行反转，最后再将字符串转换回整数，但是该问题中涉及到了越界的判断，这使得该方法变得有些繁琐，如果允许使用cstring库的话，可以使用其中的atoi函数，该函数在发现越界后会返回0，但是LeetCode只允许使用stio函数，该函数会触发异常，不便于使用。
根据题解的思路，该题可以从数学上进行分析，借用评论区题解的图：
由此来编写代码。
解题代码
class Solution {
public:
int reverse(int x) {
int result = 0;
while(x != 0){
if(result < INT_MIN / 10 || result > INT_MAX / 10)
return 0;
result = result * 10 + x % 10;
x /= 10;
}
return result;
}
};
需要注意的只有一点，在进行result * 10操作之前就要对result的范围进行判断是否超界，在java代码中似乎不需要这么麻烦，但是c++需要注意这一点。
字符串中的第一个唯一字符
题目描述
给定一个字符串 s ，找到 它的第一个不重复的字符，并返回它的索引 。如果不存在，则返回 -1 。
解题思路
唯一字符的主要特征就是数量为1，那么只需要统计出字符串中每种字符的数量即可知道字符串中的唯一字符有哪些，然后再遍历一遍字符串，寻找第一个唯一字符即可；因为题目限制了字符范围为小写字母，因此可以手搓哈希表。
解题代码
class Solution {
public:
int firstUniqChar(string s) {
int* map = new int[26]{};
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;
}
};
需要注意的一点是，之前我使用了int* map = new int[26]的方式来开辟内存空间，但是最后没能得到理想的结果，不论我的输入是什么，最后的输出都变成了-1，由此我猜想是new开辟的数组没有正常的初始值，故改为了int* map = new int[26]{}，最后成功通过。这是LeetCode所提供的的编译器的特性，有些编译器在new开辟数组时会自动用0初始化，例如我本地的编译器和lightly提供的编译器。
