❤ 2021.8.26 ❤
知道LeetCode这个东西有一两年了,一见到就很有学习的冲动,但是自己太菜,一直做比较简单的硬件开发,没怎么接触过算法数据结构之类的东西,当时选了最简单的第一题就被劝退了,甚至我都不知道答题窗口里的函数结构怎么用。。。
前两天师妹心血来潮要刷LeetCode,我趁机也刷一刷也好有人能讨论讨论。
→→→时光倒流!
❤ 2021.8.24 ❤
今天的题目是
删除排序数组中的重复项
芜湖挺简单的,但是不会。。。
根据我多年来的考研经验,不会的题先背答案再说!
答案是这么说的
嗯。。。很好理解,然后(参考别人的答案)自己写了代码
int removeDuplicates(int* nums, int numsSize)
{
int left = 0;
//双指针法
for (int right = 1; right < numsSize; right++)
{
if (nums[left] != nums[right])
{
nums[++left] = nums[right];
}
}
return ++left;
}
运行,没有问题,提交,得
经过我(对照别人的答案)缜密分析,发现可能是我没考虑空数组的情况于是
int removeDuplicates(int* nums, int numsSize)
{
int left = 0;
//判断数组是否为空
if (numsSize == 0)
return 0;
//双指针法
for (int right = 1; right < numsSize; right++)
{
if (nums[left] != nums[right])
{
nums[++left] = nums[right];
}
}
return ++left;
}
这下没问题了
第一次成功提交答案,纪念一下。。。
再次特别感谢师妹,告诉我验证答案的时候要用printf。。。(用单片机的时候被printf虐待过的人飘过。。。)
另外师妹告诉我在vs里使用c语言需要新建空文件,然后添加源文件手动修改扩展名为.c才是真正用c语言的编译器编译的,学到了学到了。
然后我还看了另一种思路
大概意思就是通过遍历寻找相同项,然后按顺序依次把数组元素修改为相同元素中的最后一项。
感觉没有上一种方法那么好理解,但是异曲同工吧。
❤ 2021.8.25 ❤
今天的题目是
买卖股票的最佳时机 II
首先吐槽一下这个题目,你家买股票能知道未来n天的价格变化呀你是神仙么?
这次读完题目后我没有立刻查答案,而是先思考了一下。
我的思路是:
首先我把所有情况都计算出来,算出每种买卖方式的能挣到的钱,然后取最大值。
想法很简单,在写代码的时候遇到问题,就是我并不知道题目给出的天数具体有几天,也就是说不知道数组的成员数,可能会有很长的一个数组,于是在写代码的时候不能用for循环,因为不知道需要嵌套几层。我想到用递归的方法去做,但是感觉有点复杂(而且我不会。。。),于是我还是去看了答案。。。
答案有几种思路,第一种是动态规划,用递推公式
有点复杂,大概看懂了,但是代码实现有点复杂,我看了下一种思路。
这个就很有意思了,用下面网友的话说就是
我的理解就是,明天要涨我就买(或手里有股票不操作),明天要跌我就卖(或手里没股票不操作),只要一分不亏,最后一定能得到最大收益。
然后我写了代码
int maxProfit(int* prices, int pricesSize)
{
int iProfit = 0;
if (pricesSize == 0)
return 0;
for (int i = 0; i < pricesSize - 1; i++)
{
int j = prices[i + 1] - prices[i];
if (j > 0)
iProfit = iProfit + j;
}
return iProfit;
}
OK没有问题,提交
喵喵喵?这评分也太低了吧!
不过我还是要吐槽一下,python真香!
❤ 2021.8.26 ❤
今天的题目是
旋转数组
第一眼看到这个题目,我去好简单啊哈哈哈(pia打脸)
我的想法是这样的:
1、最简单的方法当然是建立临时数组,但是内存占用较多,空间复杂度肯定不达标。
2、于是我想到可以每次只移动一位,循环k次。
代码如下
void rotate2(int* nums, int numsSize, int k)
{
int Temp;
if (k == 0)
return 0;
k %= numsSize;
for (int i = 1; i < k + 1; i++)
{
Temp = nums[numsSize - 1];
for (int j = numsSize - 1; j > 0; j--)
{
nums[j] = nums[j - 1];
}
nums[0] = Temp;
}
}
这个代码呢,经过测试是没有问题的,但是。。。
耗时太长了。。。晕
3、于是我换了一种思路,在参考了答案之后,我尝试了这个环形移动的方法
每次替换第ik个元素,当ik超过数组长度时取余,代码如下
void rotate3(int* nums, int numsSize, int k)
{
int Temp1,Temp2;
if (k == 0)
return 0;
k %= numsSize;
Temp1 = nums[0];
for (int i = 0; i < numsSize; i++)
{
Temp2 = nums[((i + 1) * k) % numsSize];
nums[((i + 1) * k) % numsSize] = Temp1;
Temp1 = Temp2;
}
}
但是。。。但是!我遇到了参考答案里说的,数组长度是k的整数倍的问题,答案里说用visit函数,过滤掉已经访问过的元素,但是我不知道在c语言里怎么用,所以pass。。。
4、最后我用了多次反转的方法(这种方法是怎么想出来的!!??)
代码如下
void reverse(int* nums,int start,int end)
{
while (end > start)
{
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start++;
end--;
}
}
void rotate(int* nums, int numsSize, int k)
{
if (k == 0)
return 0;
k %= numsSize;
reverse(nums, 0, numsSize-1);
reverse(nums, 0, k - 1);
reverse(nums, k, numsSize-1);
}
还要自己写reverse()函数,就挺麻烦。。。
而且我第一次提交的时候没注意reverse()函数和rotate()函数的元素对应问题,提交之后报错了
我就很奇怪,为啥别人的代码和我的差不多,但是速度就比我快了不止一点半点。。。