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;
  }
}

题目：
 
 
 
老师想给孩子们分发糖果，有 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;
    }
}

题目：
 
 
 
在一条环路上有 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，打印其格雷编码序列。即使有多个不同答案，你也只需要返回其中一种。
 
 
格雷编码序列必须以 0 开头。
 
 
来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/gray-code
 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 
 
示例 1:
 
 
 
输入: 2
 输出: [0,1,3,2]
 解释: 00 - 0
 01 - 1
 11 - 3
 10 - 2
 
 
对于给定的 n，其格雷编码序列并不唯一。 例如，[0,2,3,1] 也是一个有效的格雷编码序列。
 
 
00 - 0
 10 - 2
 11 - 3
 01 - 1
 
 
示例 2:
 
 
 
输入: 0
 输出: [0]
 解释: 我们定义格雷编码序列必须以 0 开头。
 给定编码总位数为 n 的格雷编码序列，其长度为 2n。当 n = 0 时，长度为 20 = 1。
 因此，当 n = 0 时，其格雷编码序列为 [0]。
 
 
解析
 设二进制位数为n，位数n+1的值等于n的值前加0并上n的值的倒序前加上1
 
class Solution {
    public List<Integer> grayCode(int n) {
        List<Integer> res = new ArrayList<Integer>() {{ add(0); }};
        int head = 1;
        for (int i = 0; i < n; i++) {
            for (int j = res.size() - 1; j >= 0; j--)
                res.add(head + res.get(j));
            head <<= 1;  求位数
        }
        return res;
    }
}