- 前言
- 一、删除排序数组中的重复项
- 二、买卖股票的最大时机2
- 总结
前言
来了实验室，挺安静，这么安静的环境就得思考点事情。
一、删除排序数组中的重复项
题目：给你一个 升序排列的数组 nums ，请原地删除重复出现的元素，使每个元素只出现一次 ，返回删除后数组的新长度。元素的相对顺序应该保持 一致。
摘要：升序的数组、原地删除、删除重复元素使每个元素只出现一次、元素的相对位置不能变、返回新长度
原思想：两个指针，一个控制左边、一个控制右边，如果左指针指向元素和右指针指向元素相同，那么右指针指向下一个元素，左指针也指向下一个元素，当左右指针指向元素不同时，使右指针指向元素覆盖左指针指向元素；
原代码：
class Solution {
public int removeDuplicates(int[] nums) {
int i = 0;
for (int j = 1; j < nums.length; j++) {
if (nums[i] != nums[j]) {
nums[i] = nums[j];
}
i++；
}
return i + 1;
}
}
问题：应该在遇到左右指针不一致时，才移动左指针，比如输入的数组是[1,1,1,2]，这样的话输出的数组是[1,1,2];没有实现删除重复元素的目的
新思想:还是左右指针，右边做检查，左边不动，只有当左右指针指向元素不同时，才使左指针+1，并将右指针指向元素替换左指针指向元素
新代码:
class Solution {
public int removeDuplicates(int[] nums) {
int i = 0;
for (int j = 1; j < nums.length; j++) {
if (nums[i] != nums[j]) {
i++;
nums[i] = nums[j];
}
}
return i + 1;
}
}
题目：给你一个整数数组 prices ，其中 prices[i] 表示某支股票第 i 天的价格。
在每一天，你可以决定是否购买和/或出售股票。你在任何时候最多只能持有一股股票。你也可以先购买，然后在同一天出售。返回你能获得的最大利润 。
摘要：prices[i]是某支股票第i天的价格、每天只能购买或卖出股票、看怎么买入卖出能收获这几天内的最大利润、返回最大利润
原想法：按数组一个一个循环，也就是第一次，从第0个开始，循环后面的数组，找到这一次循环的最大值，然后从第1个开始，循环后面的数组，找到这一次循环的最大值，并和上一次循环的最大值比较，如果比它大就替换，否则保留，依次往后。
原代码：
class Solution {
public int maxProfit(int[] prices) {
int max = 0;
int i=0;
for(;i=prices[j]){
continue;
}
else if(max 问题：每次循环只是单词循环的最大，没有考虑到卖出之后又买入的可能，比如[7,1,6,3,5]，股民完全可以在1买入6卖出，再3买入，5卖出，收获最大利益，而不是1买入后6卖出就不管了
新思想：
1.要考虑股票这类问题的性质，获得最大收益就是在最低点买入，最高点卖出，每次都这样，就可以收获最大利润，也就是说，我买入的阶段都是在上涨阶段
2.这里涉及一个算法：贪心算法
贪心算法是指：在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，算法得到的是在某种意义上的局部最优解；
也就是说，我一段时期的最大收益，可以考虑每个局部的最大收益之和；
对于这道题来说，就是前后元素相减，为正数的值之和；
对于1思想的新代码：
public int maxProfit(int[] prices) {
if (prices == null || prices.length < 2)
return 0;
int total = 0, index = 0, length = prices.length;
while (index < length) {
//如果股票下跌就一直找，直到找到股票开始上涨为止
while (index < length - 1 && prices[index] >= prices[index + 1])
index++;
//股票上涨开始的值，也就是这段时间上涨的最小值
int min = prices[index];
//一直找到股票上涨的最大值为止
while (index < length - 1 && prices[index] <= prices[index + 1])
index++;
//计算这段上涨时间的差值，然后累加
total += prices[index++] - min;
}
return total;
}
对于2思想的新代码：
public int maxProfit(int[] prices) {
int total = 0;
for (int i = 0; i < prices.length - 1; i++) {
//原数组中如果后一个减去前一个是正数，说明是上涨的，
//我们就要累加，否则就不累加
//Math.max(x,y)返回x和y中的较大值
total += Math.max(prices[i + 1] - prices[i], 0);
}
return total;
}
1.先加再 *** 作，还是 *** 作完加，还是到 *** 作的时候再加，是不同的场景，
for(xxx++)肯定是每次都加 {
if（）{xxx+ 再 *** 作}//到满足条件 *** 作的时候才进行
或
if(){ *** 作完 xxx+}//到满足条件 *** 作的时候再进行
xxx++每次循环都加一次
}
2.一个问题拿住，先提取关键字，搞清楚问什么要什么，有什么约束
3.然后要想这个问题有什么特点，比如股票的特点，最低最高，重复项的特点，一次重复还是多次重复，隔三岔五重复还是连续重复
4.先有思路然后写代码，写代码中再想思路；
欢迎分享，转载请注明来源：内存溢出
微信扫一扫
支付宝扫一扫
评论列表（0条）