贪心算法——LintCode加油站问题，下一个排列问题
一. 加油站问题：
在一条环路上有 N 个加油站，其中第 i 个加油站有汽油gas[i]，并且从第_i_个加油站前往第_i_+1个加油站需要消耗汽油cost[i]。
你有一辆油箱容量无限大的汽车，现在要从某一个加油站出发绕环路一周，一开始油箱为空。
求可环绕环路一周时出发的加油站的编号，若不存在环绕一周的方案，则返回-1。
您在真实的面试中是否遇到过这个题？
Yes
样例
现在有4个加油站，汽油量gas[i]=[1, 1, 3, 1]，环路旅行时消耗的汽油量cost[i]=[2, 2, 1, 1]。则出发的加油站的编号为2。
算法思路：首先从第一个加油站出发，定义count变量记录经过每一个加油站时的汽油剩余量，当汽油剩余量小于0，且没有环路一周时，则表示这个方案失败，接着从下一个站点出发，一直到最后一个剩余油量大于一，则再走出发站点之前的站点，如果最后剩余量大于等于0，则返回出发站点。如果以每一个站点作为出发站点都走了一遍，且失败，则返回-1；
代码如下：
```
public class Solution {
/**
* @param gas: an array of integers
* @param cost: an array of integers
* @return: an integer
*/
public static int canCompleteCircuit(int[] gas, int[] cost)
{
int count = 0;
for (int i = 0; i < gas.length; i++)
{
int num = 0;
for (int j = i; j < gas.length; j++)
{
num = num + gas[j] - cost[j];
if (num < 0)
break;
}
if (i == 0 && num >= 0)
return 0;
if (i > 0 && num >= 0)
{
for (int j = 0; j < i; j++)
{
num = num + gas[j] - cost[j];
if (num < 0)
return -1;
}
if (num >= 0)
return i;
}
}
return -1;
}
}
```
二 .下一个排列
给定一个整数数组来表示排列，找出其之后的一个排列。
您在真实的面试中是否遇到过这个题？
Yes
样例
给出排列[1,3,2,3]，其下一个排列是[1,3,3,2]
给出排列[4,3,2,1]，其下一个排列是[1,2,3,4]
算法思路：首先从后向前遍历，找到第一个，后一个数大于前一个的数的位置，并记录下前一个数的位置，在这个数之后找次大于它的数，找到后，交换两个数的位置，对后面的数进行升序排列，此时数组则为目标数组；如果遍历一遍找不到，后一个数字大于前一个数的数字，则表示该数组是降序的，即目标数组是升序的。
代码如下：
```
public class Solution {
/**
* @param nums: an array of integers
* @return: return nothing (void), do not return anything, modify nums in-place instead
*/
public static int[] nextPermutation(int[] nums)
{
if (nums.length == 1)
return nums;
int k = -1;
for (int i = nums.length - 1; i >= 1; i--)
{
if (nums[i] > nums[i - 1])
{
k = i - 1;
break;
}
}
if (k == -1)
{
Arrays.sort(nums);
return nums;
}
int smax = nums[k + 1], h = 0;
for (int i = k + 1; i < nums.length; i++)
{
if (nums[i] > nums[k] && nums[i] <= smax)
{
smax = nums[i];
h = i; //次大于的位置
}
}
int q = nums[k];
nums[k] = smax;
nums[h] = q;
for (int i = k + 1; i < nums.length - 1; i++)
{
for (int j = i + 1; j < nums.length; j++)
{
int p;
if (nums[i] > nums[j])
{
p = nums[i];
nums[i] = nums[j];
nums[j] = p;
}
}
}
return nums;
}
}···
```
