一. 加油站問題：
在一條環(huán)路上有 N 個加油站，其中第 i 個加油站有汽油gas[i]，并且從第_i_個加油站前往第_i_+1個加油站需要消耗汽油cost[i]。
你有一輛油箱容量無限大的汽車，現(xiàn)在要從某一個加油站出發(fā)繞環(huán)路一周，一開始油箱為空。
求可環(huán)繞環(huán)路一周時出發(fā)的加油站的編號，若不存在環(huán)繞一周的方案，則返回-1。
您在真實的面試中是否遇到過這個題？
Yes
樣例
現(xiàn)在有4個加油站，汽油量gas[i]=[1, 1, 3, 1]，環(huán)路旅行時消耗的汽油量cost[i]=[2, 2, 1, 1]。則出發(fā)的加油站的編號為2。
算法思路：首先從第一個加油站出發(fā)，定義count變量記錄經(jīng)過每一個加油站時的汽油剩余量，當汽油剩余量小于0，且沒有環(huán)路一周時，則表示這個方案失敗，接著從下一個站點出發(fā)，一直到最后一個剩余油量大于一，則再走出發(fā)站點之前的站點，如果最后剩余量大于等于0，則返回出發(fā)站點。如果以每一個站點作為出發(fā)站點都走了一遍，且失敗，則返回-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;
? ?}
}
```
二 .下一個排列
給定一個整數(shù)數(shù)組來表示排列，找出其之后的一個排列。
您在真實的面試中是否遇到過這個題？
Yes
樣例
給出排列[1,3,2,3]，其下一個排列是[1,3,3,2]
給出排列[4,3,2,1]，其下一個排列是[1,2,3,4]
算法思路：首先從后向前遍歷，找到第一個，后一個數(shù)大于前一個的數(shù)的位置，并記錄下前一個數(shù)的位置，在這個數(shù)之后找次大于它的數(shù)，找到后，交換兩個數(shù)的位置，對后面的數(shù)進行升序排列，此時數(shù)組則為目標數(shù)組；如果遍歷一遍找不到，后一個數(shù)字大于前一個數(shù)的數(shù)字，則表示該數(shù)組是降序的，即目標數(shù)組是升序的。
代碼如下：
```
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; ?
? ?}
}···
```
