LeetCode刷题笔记(6)

605、种花

今天继续刷了贪心算法的四道题目，贪心算法在算法题里面是一种普遍运用的思想，先假设一种情况为最好的情况，如果发现有更优的答案则替换，题目做起来还是比较得心应手的。

• 假设你有一个很长的花坛，一部分地块种植了花，
• 另一部分却没有。可是，花卉不能种植在相邻的地块上，
• 它们会争夺水源，两者都会死去。
• 给定一个花坛（表示为一个数组包含0和1，
• 其中0表示没种植花，1表示种植了花），和一个数 n 。
• 能否在不打破种植规则的情况下种入 n 朵花？能则返回True，不能则返回False。
• 输入: flowerbed = [1,0,0,0,1], n = 1
• 输出: True

public boolean canPlaceFlowers(int[] flowers, int n){int len = flowers.length;int cnt = 0;for(int i = 0; i < len && cnt < n; i++){if (flowers[i]==1){continue;}int pre = i ==0 ? 0: flowers[i-1];int next = i == len-1 ? 0 : flowers[i+1];if(pre == 0 && next == 0){cnt++;flowers[i]=1;}}return cnt >=n;}//方法二：public class Solution {public boolean canPlaceFlowers(int[] flowerbed, int n) {int i = 0, count = 0;while (i < flowerbed.length) {if (flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0) && (i == flowerbed.length - 1 || flowerbed[i + 1] == 0)) {//这个判断条件绝了，充分考虑到头和尾为0的情况flowerbed[i] = 1;count++;}i++;}return count >= n;}}

总结：我自己写的时候没有考虑到如果输入的数组第一个是0的情况，第二个方法中的判别条件是非常好的。

392、是否为字串

• 给定字符串 s 和 t ，判断 s 是否为 t 的子序列。
• 你可以认为 s 和 t 中仅包含英文小写字母。
• 字符串 t 可能会很长（长度 ~= 500,000），
• 而 s 是个短字符串（长度 <=100）。
• 字符串的一个子序列是原始字符串删除一些（也可以不删除）字
• 符而不改变剩余字符相对位置形成的新字符串。（例如，"ace"是"abcde"的一个子序列，而"aec"不是）。
• 示例 1:
• s = “abc”, t = “ahbgdc”
• 返回 true.
  解题思路：
  如果是匹配一个较短字符串 s ，
  对于 s中每一个char 都优先匹配最开始遇到的，直接扫描一遍 t 即可：

public class isSubsequence392 {public boolean isSubsequence(String s, String t){int i = 0;for(char ch : s.toCharArray()){while (i<t.length()&& t.charAt(i)!=ch) i++;i++;}return i <=t.length();}
}

总结：很简单的，就是看更长的字符串String中是否包含短的字符串中的每个字符

121、股票收益问题1

给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
*

• 如果你最多只允许完成一笔交易（即买入和卖出一支股票一次），设计一个算法来计算你所能获取的最大利润。
• 输入: [7,1,5,3,6,4]
• 输出: 5
• 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 = 6）的时候卖出，最大利润 = 6-1 = 5 。

•  注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格；同时，你不能在买入前卖出股票
  

方法一解题思路：
贪心算法，从左向右，维护一个最小值low，
与每一天的股票价格做差，差最大的为答案。
方法二解题思路：
只要记录前面的最小价格，将这个最小价格作为买入价格，然后将当前的价格作为售出价格，查看当前收益是不是最大收益。

//方法一：
public int maxProfit(int[] prices){int maxP = 0;int low = Integer.MAX_VALUE;for(int p : prices){if(p < low){low = p;}maxP = Math.max(maxP,p-low);}return maxP;}//方法二：public int maxProfit2(int[] prices){int n = prices.length;if(n==0) return 0;int soFarMin = prices[0];int max = 0;for(int i = 1; i < n; i++){if(soFarMin>prices[i]) soFarMin=prices[i];else max = Math.max(max,prices[i]-soFarMin);}return max;}

总结：第二个方法非常好也是比较容易理解的

122、股票收益问题2

• 给定一个数组，它的第 i 个元素是一支给定股票第 i 天的价格。
• 设计一个算法来计算你所能获取的最大利润。
• 你可以尽可能地完成更多的交易（多次买卖一支股票）。
• 输入: [7,1,5,3,6,4]
• 输出: 7
• 解释: 在第 2 天（股票价格 = 1）的时候买入，
• 在第 3 天（股票价格 = 5）的时候卖出,
  *这笔交易所能获得利润 = 5-1 = 4 。
  *随后，在第 4 天（股票价格 = 3）的时候买入，
• 在第 5 天（股票价格 = 6）的时候卖出,
• 这笔交易所能获得利润 = 6-3 = 3 。
  解题思路：
  遍历整个股票交易日价格列表 price，策略是所有上涨交易日都买卖（赚到所有利润），所有下降交易日都不买卖（永不亏钱）。
  设 tmp 为第 i-1 日买入与第 i 日卖出赚取的利润，即 tmp = prices[i] - prices[i - 1] ；
  当该天利润为正 tmp > 0，则将利润加入总利润 profit；当利润为 00 或为负，则直接跳过；
  遍历完成后，返回总利润 profit。
  对于 [a, b, c, d]，如果有 a <= b <= c <= d ，
  那么最大收益为 d - a。而 d - a = (d - c) + (c - b) + (b - a) ，因此当访问到一个 prices[i]
  且 prices[i] - prices[i-1] > 0，
  那么就把 prices[i] - prices[i-1] 添加到收益中。

public int maxProfit(int[] prices){int profit = 0;for(int i = 1; i < prices.length; i++){int tmp = prices[i]-prices[i-1];if(tmp > 0) profit += tmp;}return profit;}

总结：这个方法好在把原题目的跳过去的意思，变成了每天是否是下降，也就是邻近的两个数字进行比较。