LeetCode解析—121.买卖股票的最佳时机
题目：

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

如果你最多只允许完成一笔交易（即买入和卖出一支股票），设计一个算法来计算你所能获取的最大利润。 注意你不能在买入股票前卖出股票。

示例 1:

输入: [7,1,5,3,6,4] 输出: 5 解释: 在第 2 天（股票价格 = 1）的时候买入，在第 5 天（股票价格 =

6）的时候卖出，最大利润 = 6-1 = 5 。

注意利润不能是 7-1 = 6, 因为卖出价格需要大于买入价格。 示例 2: 输入: [7,6,4,3,1] 输出: 0

简单介绍：

题目：买卖股票的最佳时机。题目难度：简单。

使用语言：java。
解题思路：

先定义最大值为0，这样他由大到小变会最大值是0。再用排序将数组中的数字相加做比较，输出最大值。
在这里插入代码片
package leerCode;


/**
 *
 * @author boom
 */
public class besttime {
    public int maxProfit(int[] prices){
        int max=0;
        for(int i=0;i<prices.length;i++)
        {
            for(int j=i+1;j<prices.length;j++)
            {               
                    int temp=prices[i]-prices[j];
                    if(max<temp)max=temp;               
        }        
    }
        return max;
  }
}

学习目标：

一周刷6个

学习内容：

两数之和 哈希表

考虑到用暴力破解的话时间复杂度为O(n²)，那么要降低时间复杂度就要损耗掉空间，这样才能降低时间复杂度，用一遍哈希时间复杂度诶O(n)。

用到hashMap对象的get()、put()、containsKey()方法。

执行用时2ms。

遍历数组的思路：定义一个值为temp = target-num[i],然后判断该值temp是否在哈希表中,如果在那就返回哈希表中的该temp的索引下标，

不在的话就把键值对存进哈希表中。

public int[] twoSum(int[] nums, int target) {

         Map<Integer, Integer> map=new HashMap<Integer, Integer>();

        for (int i = 0,len = nums.length;i<len;i++){

            int temp = target - nums[i];

            if(map.containsKey(temp)){

                return new int [] {map.get(temp),i};

            }

            map.put(nums[i]，i);

        }

        throw new

        IllegalArgumentException("no two sum solution");

    }

学习时间：

下班后

我的第一篇博客

题目：

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。
你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i]

升。你从其中的一个加油站出发，开始时油箱为空。
如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/gas-station

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例:

输入:

gas  = [1,2,3,4,5]

cost = [3,4,5,1,2]

输出: 3

解释:

从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油 开往 4 号加油站，此时油箱有 4

1 + 5 = 8 升汽油 开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油 开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油 开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油 开往 3 号加油站，你需要消耗 5

升汽油，正好足够你返回到 3 号加油站。 因此，3 可为起始索引。


分析：

我们定义当前的油量curr_tank 和总油量total_tank ，总油量用来判断能不能走完一圈，当前油量为了确定以哪里为起点，首先，我们用一开始为起点，如果加的油可以支撑到下一个加油站，则循环，如果不行，我们就将当前的油量归零，以下一个加油站为起点，而前面的加油站n因为已经算过够支撑走到加油站n+1，所以不用管

class Solution {
  public int canCompleteCircuit(int[] gas, int[] cost) {
    int n = gas.length;

    int total_tank = 0;
    int curr_tank = 0;
    int starting_station = 0;
    for (int i = 0; i < n; ++i) {
      total_tank += gas[i] - cost[i];
      curr_tank += gas[i] - cost[i];
      // If one couldn't get here,
      if (curr_tank < 0) {
        // Pick up the next station as the starting one.
        starting_station = i + 1;
        // Start with an empty tank.
        curr_tank = 0;
      }
    }
    return total_tank >= 0 ? starting_station : -1;
  }
}

题目：

老师想给孩子们分发糖果，有 N 个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分。
你需要按照以下要求，帮助老师给这些孩子分发糖果：
每个孩子至少分配到 1 个糖果。
相邻的孩子中，评分高的孩子必须获得更多的糖果。

那么这样下来，老师至少需要准备多少颗糖果呢？
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/candy

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

示例:

输入: [1,0,2]

输出: 5

解释: 你可以分别给这三个孩子分发 2、1、2 颗糖果。

输入: [1,2,2]

输出: 4

解释: 你可以分别给这三个孩子分发 1、2、1 颗糖果。

第三个孩子只得到 1 颗糖果，这已满足上述两个条件。

分析：

首先，我们定义一个数组来存放每个小孩子的糖果，因为每个人必须有糖果，用Arrays.fill来初始化数组各个值为1，我们再去比较，这里有个细节，就是要左右都比较，要遍历2次，第一次遍历先从左向右 若右边的孩子评分比左边高 则右边的糖果数等于左边的糖果数加一，第二次遍历先从右向左 若左边的孩子评分比右边高且左边的孩子糖果数小于等于右边的 则左边的糖果数等于右 边的糖果数加一 同时求和

public class Solution {
    public int candy(int[] ratings) {
        int[] candies = new int[ratings.length];
        Arrays.fill(candies, 1);
        for (int i = 1; i < ratings.length; i++) {
            if (ratings[i] > ratings[i - 1]) {
                candies[i] = candies[i - 1] + 1;
            }
        }
        int sum = candies[ratings.length - 1];
        for (int i = ratings.length - 2; i >= 0; i--) {
            if (ratings[i] > ratings[i + 1]) {
                candies[i] = Math.max(candies[i], candies[i + 1] + 1);
            }
            sum += candies[i];
        }
        return sum;
    }
}