134. Gas Station
There are n gas stations along a circular route, where the amount of gas at the ith station is gas[i].
You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from the ith station to its next (i + 1)th station. You begin the journey with an empty tank at one of the gas stations.
Given two integer arrays gas and cost, return the starting gas station's index if you can travel around the circuit once in the clockwise direction, otherwise return -1. If there exists a solution, it is guaranteed to be unique
Example 1:
Input: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
Output: 3
Explanation:
Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4. Your tank = 4 - 1 + 5 = 8
Travel to station 0. Your tank = 8 - 2 + 1 = 7
Travel to station 1. Your tank = 7 - 3 + 2 = 6
Travel to station 2. Your tank = 6 - 4 + 3 = 5
Travel to station 3. The cost is 5. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.
Example 2:
Input: gas = [2,3,4], cost = [3,4,3]
Output: -1
Explanation:
You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0. Your tank = 4 - 3 + 2 = 3
Travel to station 1. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.
Constraints:
n == gas.length == cost.length
1 <= n <= 105
0 <= gas[i], cost[i] <= 10^4
Original Page
Direct Method (but it causes time limited exceed
public int canCompleteCircuit(int[] gas, int[] cost) {
for(int i=0; i<gas.length; i++){
int index = i+1==gas.length?0:i+1;
int res = i;
if(cost[i] > gas[i]){
continue;
}
int sum = gas[i]-cost[i];
while(sum >=0 && index!=i){
sum += gas[index];
sum -= cost[index];
index ++;
if(index == gas.length){
index = 0;
}
}
if (index == i && sum >= 0){
return res;
}
}
return -1;
}
time: O(n^2)
public int canCompleteCircuit(int[] gas, int[] cost) {
if(gas.length != cost.length){
return -1;
}
// int diff[] = IntStream.range(0,gas.length)
// .map(i->gas[i] - cost[i])
// .toArray();
int diff[] = new int[gas.length];
int sum = 0;
for(int i=0; i< gas.length; i++){
diff[i] = gas[i] - cost[i];
sum += diff[i];
}
if(sum<0){
return -1;
}
int tank = 0;
int start = -1;
for(int i=0; i<diff.length; i++){
if(start == -1 && diff[i] <0){
continue;
}
if(start == -1 && diff[i] >=0){
start = i;
}
if(start != -1){
tank += diff[i];
}
if(tank <0){
tank = 0;
start = -1;
}
}
return start;
}
time: O(n)
860. Lemonade Change
At a lemonade stand, each lemonade costs $5. Customers are standing in a queue to buy from you and order one at a time (in the order specified by bills). Each customer will only buy one lemonade and pay with either a $5, $10, or $20 bill. You must provide the correct change to each customer so that the net transaction is that the customer pays $5.
Note that you do not have any change in hand at first.
Given an integer array bills where bills[i] is the bill the ith customer pays, return true if you can provide every customer with the correct change, or false otherwise.
Example 1:
Input: bills = [5,5,5,10,20]
Output: true
Explanation:
From the first 3 customers, we collect three $5 bills in order.
From the fourth customer, we collect a $10 bill and give back a $5.
From the fifth customer, we give a $10 bill and a $5 bill.
Since all customers got correct change, we output true.
Example 2:
Input: bills = [5,5,10,10,20]
Output: false
Explanation:
From the first two customers in order, we collect two $5 bills.
For the next two customers in order, we collect a $10 bill and give back a $5 bill.
For the last customer, we can not give the change of $15 back because we only have two $10 bills.
Since not every customer received the correct change, the answer is false.
Constraints:
1 <= bills.length <= 10^5
bills[i] is either 5, 10, or 20.
Original Page
public boolean lemonadeChange(int[] bills) {
int five = 0;
int ten = 0;
for(int i=0; i<bills.length; i++){
if(bills[i] == 5){
five++;
}
else if(bills[i] == 10){
five--;
ten++;
if(five < 0 ){
return false;
}
} else{
if(ten > 0){
ten--;
five--;
if(five<0){
return false;
}
}else{
five -=3;
if(five<0){
return false;
}
}
}
}
return true;
}
135. Candy
There are n children standing in a line. Each child is assigned a rating value given in the integer array ratings.
You are giving candies to these children subjected to the following requirements:
Each child must have at least one candy.
Children with a higher rating get more candies than their neighbors.
Return the minimum number of candies you need to have to distribute the candies to the children.
Example 1:
Input: ratings = [1,0,2]
Output: 5
Explanation: You can allocate to the first, second and third child with 2, 1, 2 candies respectively.
Example 2:
Input: ratings = [1,2,2]
Output: 4
Explanation: You can allocate to the first, second and third child with 1, 2, 1 candies respectively.
The third child gets 1 candy because it satisfies the above two conditions.
Constraints:
n == ratings.length
1 <= n <= 2 * 10^4
0 <= ratings[i] <= 2 * 10^4
Original Page
public int candy(int[] ratings) {
int[] candy = new int[ratings.length];
candy[0] = 1;
for(int i=1; i<candy.length; i++){
if(ratings[i] > ratings[i-1]){
candy[i] = candy[i-1]+1;
}else{
candy[i] = 1;
}
}
int sum = candy[candy.length-1];
for(int i=candy.length-2; i>=0; i--){
if(ratings[i] > ratings[i+1]){
candy[i] = Math.max(candy[i], candy[i+1]+1);
}else{
candy[i] = Math.max(1, candy[i]);
}
sum += candy[i];
}
return sum;
}
Processing the left and right neighbours by two loops is important.
406. Queue Reconstruction by Height
You are given an array of people, people, which are the attributes of some people in a queue (not necessarily in order). Each people[i] = [hi, ki] represents the ith person of height hi with exactly ki other people in front who have a height greater than or equal to hi.
Reconstruct and return the queue that is represented by the input array people. The returned queue should be formatted as an array queue, where queue[j] = [hj, kj] is the attributes of the jth person in the queue (queue[0] is the person at the front of the queue).
Example 1:
Input: people = [[7,0],[4,4],[7,1],[5,0],[6,1],[5,2]]
Output: [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]]
Explanation:
Person 0 has height 5 with no other people taller or the same height in front.
Person 1 has height 7 with no other people taller or the same height in front.
Person 2 has height 5 with two persons taller or the same height in front, which is person 0 and 1.
Person 3 has height 6 with one person taller or the same height in front, which is person 1.
Person 4 has height 4 with four people taller or the same height in front, which are people 0, 1, 2, and 3.
Person 5 has height 7 with one person taller or the same height in front, which is person 1.
Hence [[5,0],[7,0],[5,2],[6,1],[4,4],[7,1]] is the reconstructed queue.
Example 2:
Input: people = [[6,0],[5,0],[4,0],[3,2],[2,2],[1,4]]
Output: [[4,0],[5,0],[2,2],[3,2],[1,4],[6,0]]
Constraints:
1 <= people.length <= 2000
0 <= hi <= 10^6
0 <= ki < people.length
It is guaranteed that the queue can be reconstructed.
Original Page
public int[][] reconstructQueue(int[][] people) {
Arrays.sort(people, (a,b) -> {
if(a[0]!=b[0]){
return Integer.compare(b[0], a[0]);
}
return Integer.compare(a[1], b[1]);
});
for(int i=0; i<people.length; i++){
int index = people[i][1];
int length = i-index;
int[] element = people[i];
System.arraycopy(people,index, people, index+1, length);
people[index] = element;
}
return people;
}
Similar to the above question we have to divide into 2 steps to figure this problem out.
Top comments (0)