一. 加油站問(wèn)題：
在一條環(huán)路上有 N 個(gè)加油站摔吏，其中第 i 個(gè)加油站有汽油gas[i]，并且從第_i_個(gè)加油站前往第_i_+1個(gè)加油站需要消耗汽油cost[i]纵装。
你有一輛油箱容量無(wú)限大的汽車(chē)征讲，現(xiàn)在要從某一個(gè)加油站出發(fā)繞環(huán)路一周，一開(kāi)始油箱為空橡娄。
求可環(huán)繞環(huán)路一周時(shí)出發(fā)的加油站的編號(hào)诗箍，若不存在環(huán)繞一周的方案，則返回-1挽唉。
您在真實(shí)的面試中是否遇到過(guò)這個(gè)題滤祖？
Yes
樣例
現(xiàn)在有4個(gè)加油站，汽油量gas[i]=[1, 1, 3, 1]瓶籽，環(huán)路旅行時(shí)消耗的汽油量cost[i]=[2, 2, 1, 1]匠童。則出發(fā)的加油站的編號(hào)為2。
算法思路：首先從第一個(gè)加油站出發(fā)塑顺，定義count變量記錄經(jīng)過(guò)每一個(gè)加油站時(shí)的汽油剩余量汤求，當(dāng)汽油剩余量小于0，且沒(méi)有環(huán)路一周時(shí)茬暇，則表示這個(gè)方案失敗首昔，接著從下一個(gè)站點(diǎn)出發(fā)，一直到最后一個(gè)剩余油量大于一糙俗，則再走出發(fā)站點(diǎn)之前的站點(diǎn)勒奇，如果最后剩余量大于等于0，則返回出發(fā)站點(diǎn)巧骚。如果以每一個(gè)站點(diǎn)作為出發(fā)站點(diǎn)都走了一遍赊颠，且失敗格二，則返回-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;
? ?}
}
```
二 .下一個(gè)排列
給定一個(gè)整數(shù)數(shù)組來(lái)表示排列竣蹦，找出其之后的一個(gè)排列顶猜。
您在真實(shí)的面試中是否遇到過(guò)這個(gè)題？
Yes
樣例
給出排列[1,3,2,3]痘括，其下一個(gè)排列是[1,3,3,2]
給出排列[4,3,2,1]长窄，其下一個(gè)排列是[1,2,3,4]
算法思路：首先從后向前遍歷，找到第一個(gè)纲菌，后一個(gè)數(shù)大于前一個(gè)的數(shù)的位置挠日，并記錄下前一個(gè)數(shù)的位置，在這個(gè)數(shù)之后找次大于它的數(shù)翰舌，找到后嚣潜，交換兩個(gè)數(shù)的位置，對(duì)后面的數(shù)進(jìn)行升序排列椅贱，此時(shí)數(shù)組則為目標(biāo)數(shù)組懂算；如果遍歷一遍找不到，后一個(gè)數(shù)字大于前一個(gè)數(shù)的數(shù)字庇麦，則表示該數(shù)組是降序的计技，即目標(biāo)數(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; ?
? ?}
}···
```
