1116 | reconstruction queue according to height
Suppose you have an out-of-order group of people standing in a queue. Each person is represented by a pair of integers (h, k), where H is the height of the person and k is the number of people who should precede the person and are taller than or equal to H. For example, [5,2] indicates that there should be two people of height greater than or equal to 5, and [5,0] indicates that there should be no people of height greater than or equal to 5.
Write an algorithm that reconstructs the queue from the height h of each person so that it satisfies the number k requirement in each integer pair (h, k).
Example: input: [(7, 0], [4], [7, 1], [5, 0], [6, 1], [5, 2]] output: [[5, 0), (7, 0], [5, 2], [6, 1], [4], [7, 1]]
Hint: The total number is less than 1100.
Source: LeetCode link: leetcode-cn.com/problems/qu… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.
- Train of thought
Reordering the queue is sorting the array according to the rules they ask for, and the rules specify both h and k, so there is only one correct answer. According to the rules of the question, the sorting is mainly by h, but k will adjust the order. If you use swap or other ways, each swap will have to recalculate the two k values, so it is not possible to use the sorting idea that needs to swap. Selection sort might be an appropriate choice.
H and k affect each other, but for the element with the smallest h, k is exactly where it should be (everyone in front is taller than it, and k = 2 is preceded by I = 0 and I = 1, so its position is I = k = 2).
And then the second smallest element of h, it doesn’t have to have the same I as k, because if the smallest element of H was in front of it, its I would be k plus 1. That is, each element can be successfully sorted by placing it in the KTH of the remaining empty positions in ascending order of h.
- code
class Solution {
public int[][] reconstructQueue(int[][] people) {
int n = people.length;
int[][] result = new int[n][2];
for(int i = 0; i < n; i++){
result[i][0] = 0;
result[i][1] = -1;
}
Arrays.sort(people, new Comparator<int[] > () {@Override
public int compare(int[] o1, int[] o2) {
return o1[0] - o2[0]; }});int p = 0;
while(p < n){
//System.out.println(people[p][0] + "," + people[p][1]);
int rank = people[p][1];
for(int k = 0; k < result.length; k++){
if(result[k][1] = = -1) {// Whitespace can be inserted
if(rank == 0){
result[k][0] = people[p][0];
result[k][1] = people[p][1];
break;
} else{ rank--; }}else {
if(result[k][0] == people[p][0]){
rank--;
}
}
}
p++;
}
returnresult; }}Copy the code- To optimize the
The result array can be initialized to -1 without being initialized to null.
1117 | distance order matrix cells
The matrix of row R and column C is given, where the integer coordinates of the cells are (R, C), satisfying 0 <= R < R and 0 <= C < C.
In addition, we give a cell with coordinates (R0, c0) in the matrix.
Returns the coordinates of all the cells in the matrix, and press (r0, c0) distance from the smallest to the largest order, among them, the two cell (r1, c1) and (r2, c2), Manhattan distance is the distance between | r1 and r2 + | c1 and c2 | |. (You can return the answers in any order that satisfies this condition.)
Example 1: Input: R = 1, C = 2, R0 = 0, C0 = 0 Output: [[0,0],[0,1] Explanation: Distance from (r0, c0) to other cells is: [0,1] Example 2: Input: R = 2, C = 2, r0 = 0, c0 = 1 output: [[0, 1], [0, 0], [1, 1], [1, 0]] : from (r0, c0) to the other cells: [0,1, 2] [[0,1],[1,1],[0,0],[1,0]] will also be considered the correct answer. Example 3: input: R = 2, C = 3, r0 = 1, 2 c0 = output: [[1, 2], [0, 2], [1, 1], [0, 1], [1, 0] to [0, 0]] : from (r0, c0) to the other cells: ,1,1,2,2,3 [0] other answers that could satisfy the requirement of subject will be considered right, such as [[1, 2], [1, 1], [0, 2], [1, 0], [0, 1], [0, 0]].
1 <= R <= 100 1 <= C <= 100 0 <= r0 < R 0 <= c0 < C
Source: LeetCode link: leetcode-cn.com/problems/ma… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.
- Train of thought
The law of violence is the best in the world. Just start at a given point and iterate over the two-dimensional array in increasing distance, with the farthest distance acting as the exit of the loop, filtering out the out-of-range coordinates along the way.
Distance calculation is | r1 and r2 + | | c1 and c2 |, so each distance d can split out (Dr = 0 d, dc = d 0) of different combinations.
- code
class Solution {
public int[][] allCellsDistOrder(int R, int C, int r0, int c0) {
int[][] result = new int[R*C][2];
int max = calcMaxDistance(R,C,r0,c0);
int cursor = 0;
for(int i = 0; i <= max; i++){
cursor = addDistance(R,C,r0,c0,result, i, cursor);
}
return result;
}
private int addDistance(int R, int C, int r0, int c0, int[][] collection, intdistanceint cursor){
if(distance == 0){
collection[cursor][0] = r0;
collection[cursor][1] = c0;
return cursor+1;
}
int p = distance;
int q = 0;
int c = cursor;
while(p >= 0 && q <= distance){
if(p == 0) {if(r0 + p < R && c0 - q >= 0){
collection[c][0] = r0+p;
collection[c][1] = c0-q;
c++;
}
if(r0 + p < R && c0 + q < C){
collection[c][0] = r0+p;
collection[c][1] = c0+q;
c++;
}
p--;
q++;
continue;
}
if(q == 0) {if(r0 - p >=0 && c0 - q >= 0){
collection[c][0] = r0-p;
collection[c][1] = c0-q;
c++;
}
if(r0 + p < R && c0 - q >= 0){
collection[c][0] = r0+p;
collection[c][1] = c0-q;
c++;
}
p--;
q++;
continue;
}
if(r0 - p >=0 && c0 - q >= 0){
collection[c][0] = r0-p;
collection[c][1] = c0-q;
c++;
}
if(r0 + p < R && c0 - q >= 0){
collection[c][0] = r0+p;
collection[c][1] = c0-q;
c++;
}
if(r0 + p < R && c0 + q < C){
collection[c][0] = r0+p;
collection[c][1] = c0+q;
c++;
}
if(r0 - p >= 0 && c0 + q < C){
collection[c][0] = r0-p;
collection[c][1] = c0+q;
c++;
}
p--;
q++;
}
return c;
}
private int calcMaxDistance(int R, int C, int r0, int c0){
return Math.max(R-r0-1,r0) + Math.max(C-c0-1, c0); }}Copy the code1118 | gas station
There are N gas stations on a loop, and the ith gas station has a liter of gas.
You have a car with an infinite tank, and it costs you [I] liters of gas to go from the ith gas station to the I +1 gas station. You start at one of the gas stations with an empty tank.
Return the number of the gas station at the time of departure if you can make a full loop, otherwise -1.
Note: If the problem has a solution, the answer is the only one. Input arrays are all non-empty arrays of the same length. The elements in the input array are non-negative.
Example 1: input: gas = [1, 2, 3, 4, 5] cost =,4,5,1,2 [3] output: 3
Explanation: From station 3 (index 3), you can get 4 litres of petrol. In this case, the fuel tank has = 0 + 4 = 4 liters of gasoline to the no. 4 gas station, and 4-1 + 5 = 8 liters of gasoline to the No. 0 gas station, and 8-2 + 1 = 7 liters of gasoline to the No. 1 gas station. Now you have 7-3 + 2 = 6 liters of gas going to gas station no. 2, and 6-4 + 3 = 5 liters of gas going to gas station No. 3. You need to consume 5 liters of gas, which is just enough to go back to gas station No. 3. Therefore, 3 can be the starting index.
Example 2: input gas = [2,3,4] cost = [3,4,3] output -1
Explanation: You can’t start at gas station 0 or 1 because there isn’t enough gas to get you to the next station. We can get four litres of petrol from station No. 2. You can’t go back to gas station no. 2 because you’re going to use 4 liters of gas to get back, But you only have three liters in your tank. So, anyway, you can’t go all the way around the loop.
Source: LeetCode link: leetcode-cn.com/problems/ga… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.
- Train of thought
Violence method can be solved, simulate the starting situation from each position, calculate the amount of remaining fuel to each point, if the midway drops to a negative number, it is considered that the driving can not be a week. If any can return to the starting point, return the starting point number.
But the brute force method has a lot of redundant calculations. If it is possible to start from a, it means that the amount of oil at point A is greater than or equal to 0 when it starts from point A. When it reaches B, it is found that the amount of oil is negative. It can be proved that starting from point A +1 cannot pass point B, and points between a and B cannot pass point B.
So when you get a negative value, you just take the next point as the starting point, and the time complexity can be reduced from O(N²) to O(N).
- code
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int i = 0;
int n = gas.length;
while(i < n){
int sum = 0;
int p = 0;
while(p < n){
int j = (i + p) % n;
sum = sum + gas[j] - cost[j];
if(sum < 0) {break;
}
p++;
}
if(p == n){
return i;
} else {
i = i + p + 1; }}return -1; }}Copy the code- skills
int j = (i + p) % n; With short code to achieve cyclic access to the array.
1119 | mobile zero
Given an array nums, write a function to move all zeros to the end of the array while preserving the relative order of the non-zero elements.
Example:
Input: [0,1,0,3,12] output: [1,3,12,0,0]
Description:
Must operate on the original array, cannot copy additional arrays. Minimize the number of operations.
Source: LeetCode link: leetcode-cn.com/problems/mo… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.
- Train of thought
Since only 0 is special, we can iterate through the array, rewriting each non-0 digit in order to the front of the array, recording the overwritten position, followed by the complement of 0. The time is order N.
It worked, but it didn’t work very well. The entire array underwent a rewrite, too many redundant operations for data like [0,0,0,0,1]. Double Pointers are used to search for 0 and the next non-zero number respectively, and then exchange the values of the two, thus avoiding the redundant operation of rewriting 0. According to the measured results, the speed is improved.
- code
class Solution {
public void moveZeroes(int[] nums) {
if(nums.length == 0) {return;
}
int p = 0;
int q = 0;
while(true) {while(nums[p] ! =0){
p++;
if(p == nums.length){
return;
}
}
q = p;
while(nums[q] == 0){
q++;
if(q == nums.length){
return;
}
}
nums[p] = nums[q];
nums[q] = 0; }}}Copy the code- skills
Most of the time solutions with the same level of time complexity do not need to be distinguished, but there are differences between different solutions. The implication of the problem is to minimize the number of operations as much as possible, to think more carefully, to find a better solution.
1120 | for insertion sort list
Insert sort algorithm:
Insertion sort is iterative, moving one element at a time until all the elements can form an ordered output list. In each iteration, insert sort removes only one element to be sorted from the input data, finds its proper place in the sequence, and inserts it. Repeat until all input data has been inserted.
Example 1: input: 4 – > 2 – > 1 – > 3 output: 1 – > 2 – > 3 – > 4 example 2: input: – 1 – > 5 – > 4 – > 3 – > 0 output: 1 – > 0 – > 3 – > 4 – > 5
Source: LeetCode link: leetcode-cn.com/problems/in… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.
- Train of thought
The idea of insertion sort is to pick a new element at a time, and put it in the right place in the sorted linear list, without using extra space, but you need to move elements, and how to move elements in a linked list is a bit of a puzzle.
We split the list into two parts with a single node. The sorted elements are maintained on the left side and the unsorted elements are maintained on the right side. Each node on the right is selected and inserted into the left side. In addition to bounding nodes, moving elements is done by recording the previous element and dealing with the situation before the insertion of the end node.
- code
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; }} * * /
class Solution {
public ListNode insertionSortList(ListNode head) {
if(head == null) {return head;
}
ListNode pre = new ListNode(0);
pre.next = head;
ListNode lastSorted = head;
ListNode curr = head;
while(curr ! =null) {if(lastSorted.val <= curr.val){
lastSorted = curr;
} else {
ListNode temp = pre;
while(temp.next.val < curr.val){
temp = temp.next;
}
lastSorted.next = curr.next;
curr.next = temp.next;
temp.next = curr;
}
curr = lastSorted.next;
}
returnpre.next; }}Copy the code1121 | sorting list
Given the head of your list, please sort it in ascending order and return the sorted list.
Advanced: Can you sort linked lists in O(n log n) time complexity and constant space complexity?
Source: LeetCode link: leetcode-cn.com/problems/so… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.
- Train of thought
The day before just finished insertion sort, immediately arrange advanced practice needle not stamp.
Sorting is as memorable an algorithm as abandon, so let’s go straight to the progression. Logarithmic time complexity is possible with schemes such as quicksort, merge sort, and heap sort. Combined with the operation constraints of linked lists, merge sort is relatively easy to implement.
Merge sort is divided into two steps, which are divided first and then combined. The process of separation should be careful not to repeat and not to omit, and the process of combination should ensure the ascending order. When you split it, you need to get the middle point of the list, you can use the fast or slow pointer to achieve that, and find the middle point is also a problem, I don’t want to explain it in depth.
- code
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; }} * * /
class Solution {
public ListNode sortList(ListNode head) {
if(head == null) {return head;
}
return sortList(head, null);
}
private ListNode sortList(ListNode head, ListNode tail){
if(head == null) {return head;
}
if (head.next == tail) {
head.next = null;
return head;
}
ListNode fast = head;
ListNode slow = head;
while(fast ! = tail){ fast = fast.next; slow = slow.next;if(fast ! = tail){ fast = fast.next; } } ListNode mid = slow; ListNode leftSorted = sortList(head, mid); ListNode rightSorted = sortList(mid, tail);return merge(leftSorted, rightSorted);
}
private ListNode merge(ListNode la, ListNode lb){
ListNode pre = new ListNode(0);
ListNode p = la;
ListNode q = lb;
ListNode u = pre;
while(p ! =null|| q ! =null) {if(p == null){
u.next = q;
q = q.next;
} else if(q == null){
u.next = p;
p = p.next;
} else {
if(p.val > q.val){
u.next = q;
q = q.next;
} else {
u.next = p;
p = p.next;
}
}
u = u.next;
}
returnpre.next; }}Copy the code- skills
Finding the midpoints of lists and merging ordered lists are problems that have been solved before (and perhaps not so hard), and breaking down complex problems into simple combinations of problems is the process of solving them.
1122 | ectopic effective letter word
Given two strings s and t, write a function to determine whether t is an alphabetic allotopic of S.
Example 1: Enter s = “anagram”, t = “nagaram” Output: true Example 2: Enter S = “rat”, t = “car” Output: false
Note: You can assume that strings contain only lowercase letters.
Advanced: What if the input string contains Unicode characters? Can you adjust your solution to this situation?
Source: LeetCode link: leetcode-cn.com/problems/va… Copyright belongs to the Collar buckle network. Commercial reprint please contact official authorization, non-commercial reprint please indicate the source.
- Train of thought
The meaning of an allotopic word is:
- It’s made up of exactly the same kind of letters
- The number of each letter is exactly the same
Using a HashMap to record the number of letters in each occurrence gives the result twice. The time is order N.
- code
class Solution {
public boolean isAnagram(String s, String t) {
if(s.length() ! = t.length()){return false;
}
HashMap<Character, Integer> map = new HashMap<>();
for(int i = 0; i < s.length(); i++){
if(map.get(s.charAt(i)) == null){
map.put(s.charAt(i), 1);
} else {
Integer n = map.get(s.charAt(i));
map.put(s.charAt(i), n+1); }}for(int j = 0; j < t.length(); j++){
char c = t.charAt(j);
if(map.get(c) == null) {return false;
}
Integer m = map.get(c);
if(m == 0) {return false;
}
m = m - 1;
map.put(c, m);
}
return true; }}Copy the code- To optimize the
HashMap has auto-boxing/unboxing problems, which is a Java malpractice. Instead of using HashMap, you can use an array of size 26.
- Another solution
Sort s and t, and see if they’re equal.