1. leetcode455 Distribution of biscuits
1.1 Solution ideas
1.2 Code implementation π΄
class Solution {
public int findContentChildren(int[] g, int[] s) { // Cookies are S and kids' appetite is G
Arrays.sort(g);
Arrays.sort(s);
int i = 0;
int j = 0;
while (i < s.length && j < g.length) {
if (s[i] >= g[j]) {
j++;
}
i++;
}
returnj; }}Copy the code2. leetcode322 Change change
2.1 Solution ideas
In this case, greedy + backtracking cannot improve performance. The optimal solution is dynamic programming, which will be written later. 
3. leetcode45 Jump Game II
3.1 Solution idea
3.2 Code implementation 1: DFS(timeout)
class Solution {
private int minSteps = Integer.MAX_VALUE;
public int jump(int[] nums) {
dfs(nums, 0.new ArrayList<>());
return minSteps == Integer.MAX_VALUE ? 0 : minSteps;
}
private void dfs(int[] nums, int jumpedIndex, List<Integer> path) {
if (jumpedIndex == nums.length - 1) {
minSteps = Math.min(minSteps, path.size());
return;
}
for (int i = 1; i <= nums[jumpedIndex]; i++) {
if (jumpedIndex + i >= nums.length)
continue;
path.add(i);
// jumpedIndex + I, which indicates the jump to the next step
dfs(nums, jumpedIndex + i, path);
path.remove(path.size() - 1); }}}Copy the code3.2 Code implementation 2: BFS(timeout)
class Solution {
public int jump(int[] nums) {
if (nums.length == 1)
return 0;
Queue<Integer> queue = new ArrayDeque<>();
queue.offer(0);
int level = 0;
while(! queue.isEmpty()) {int size = queue.size();
for (int i = 0; i < size; i++) {
int jumpedIndex = queue.poll();
if (jumpedIndex == nums.length - 1)
return level;
for (int j = 1; j <= nums[jumpedIndex]; j++) {
queue.offer(jumpedIndex + j);
}
}
level++;
}
return 0; }}Copy the code3.3 Code implementation 3: Greed
class Solution {
// Greedy strategy: Take the longest jump at each step
public int jump(int[] nums) {
if (nums.length == 1)
return 0;
int steps = 0;
int start = 0, end = 0;
while (end < nums.length - 1) { // There is no need to walk when you reach the last position
int maxPos = 0;
// Each time from [start, end] select the maximum distance to jump
for (int i = start; i <= end; i++) {
maxPos = Math.max(maxPos,i + nums[i]);
}
start = end + 1;
end = maxPos;
steps++;
}
returnsteps; }}Copy the code3.4 Code implementation 4: π΄ Greedy (only traversed once)
class Solution {
// Greedy strategy: Take the longest jump at each step
public int jump(int[] nums) {
if (nums.length == 1)
return 0;
int steps = 0;
int maxPos = 0, end = 0;
for (int i = 0; i < nums.length - 1; i++) {
// Count each position and get the maximum position
maxPos = Math.max(maxPos, i + nums[i]);
if(i == end) { steps++; end = maxPos; }}returnsteps; }}Copy the code4. leetcode55 Jumping games
4.1 Solution idea
4.2 Code implementation π΄
class Solution {
public boolean canJump(int[] nums) {
int maxPos = 0;
for (int i = 0; i < nums.length; i++) {
if (maxPos < i)
return false;
maxPos = Math.max(maxPos, i + nums[i]);
}
return true; }}Copy the code4. leetcode1578 Avoid minimal deletion costs for duplicate letters
4.1 Solution idea
4.2 Code implementation π΄
class Solution {
public int minCost(String s, int[] cost) {
int res = 0;
int len = s.length();
int i = 0;
while (i < len) {
char c = s.charAt(i);
int maxCost = 0;
int sumCost = 0;
while (i < len && s.charAt(i) == c) {
maxCost = Math.max(maxCost, cost[i]);
sumCost += cost[i];
i++;
}
res += sumCost - maxCost;
}
returnres; }}Copy the code5. leetcode402 Remove the K digits
5.1 Solution Ideas
5.2 Code implementation 1: Greedy, time complexity O(K * N)
class Solution {
public String removeKdigits(String num, int k) {
StringBuilder sb = new StringBuilder(num);
for (int i = 0; i < k; i++) {
boolean hasDeleted = false;
for (int j = 1; j < sb.length(); j++) {
// If the preceding number is large, delete it
if (sb.charAt(j) < sb.charAt(j - 1)) {
sb.deleteCharAt(j - 1);
hasDeleted = true;
break; }}// Delete the last character
if(! hasDeleted) sb.deleteCharAt(sb.length() -1);
}
// Delete characters preceded by 0
int len = sb.length();
while(len ! =0) {
if (sb.charAt(0) > '0')
break;
sb.deleteCharAt(0);
len = sb.length();
}
return sb.length() == 0 ? "0": sb.toString(); }}Copy the code5.3 Code implementation 2: π΄ Greedy + monotonous stack (time complexity O(k + N), space complexity O(n))
class Solution {
public String removeKdigits(String num, int k) {
Deque<Character> deque = new ArrayDeque<>();
for (int i = 0; i < num.length(); i++) {
char c = num.charAt(i);
while(! deque.isEmpty() && k >0 && deque.peek() > c) {
deque.pop();
k--;
}
deque.push(c);
}
for (int i = 0; i < k; i++) {
deque.pop();
}
StringBuilder sb = new StringBuilder();
boolean isFirst = true;
while(! deque.isEmpty()) {char c = deque.pollLast();
if (c == '0' && isFirst)
continue;
sb.append(c);
isFirst = false;
}
return sb.length() == 0 ? "0": sb.toString(); }}Copy the code6 leetcode409 Longest palindrome string
6.1 Solving the problem
A palindrome string can be formed by dividing characters with even occurrences. 2. Only one character with odd occurrences can be added to the middle of a palindrome string
6.2 Code implementation π΄
class Solution {
public int longestPalindrome(String s) {
int[] counter = new int[128];
int ans = 0;
for (char c : s.toCharArray()) {
counter[c]++;
}
for (int v : counter) {
ans += v / 2 * 2;
// Only one character can occur an odd number of times
if (v % 2= =1 && ans % 2= =0) { ans++; }}returnans; }}Copy the code7. leetcode680 Verify palindrome string β ±
7.1 How to Solve the problem
1. Greedy strategy: Try to delete either the beginning or the end of a character only when the two characters are not equal
7.2 Code implementation: π΄ greedy
class Solution {
// Greedy strategy: try to delete either the beginning or the end of a character only if the two characters are not equal
// Time complexity O(n)
// Space complexity O(1)
public boolean validPalindrome(String s) {
int left = 0;
int right = s.length() - 1;
while (left < right) {
if (s.charAt(left) == s.charAt(right)) {
left++;
right--;
} else {
// Delete left or right characters
// Then check whether the remaining characters are palindromes
return validPalindrome(s, left + 1, right) ||
validPalindrome(s, left, right - 1); }}return true;
}
private boolean validPalindrome(String s, int left, int right) {
while (left < right) {
if (s.charAt(left) == s.charAt(right)) {
left++;
right--;
} else {
return false; }}return true; }}Copy the code8. leetcode316 Remove duplicate letters
8.1 Ideas for solving the problem
1. Record characters in a stringsIs used to determine whether the current character is followed by a character to be popped
2. Maintain a monotonic stack
3. Use a Boolean array to record whether it already exists on the stack
8.2 code implementation: π΄ greedy + monotonous stack
class Solution {
public String removeDuplicateLetters(String s) {
// 1. Calculate the last index of a character in string s
int[] lastIndex = new int[26];
for (int i = 0; i < s.length(); i++) {
lastIndex[s.charAt(i) - 'a'] = i;
}
// 2. Maintain monotone stack
Deque<Character> stack = new ArrayDeque<>();
// Is used to record whether a character already exists in the stack
boolean[] exits = new boolean[26];
for (int i = 0; i < s.length(); i++) {
char c = s.charAt(i);
if (exits[c - 'a'])
continue;
/ / conditions:
// (1). The current character is less than the top character of the stack
// (2). The top character of the stack appears after the current character
while(! stack.isEmpty() && stack.peek() > c && lastIndex[stack.peek() -'a'] > i) {
char top = stack.pop();
exits[top - 'a'] = false;
}
stack.push(c);
exits[c - 'a'] = true;
}
// 3. Concatenate the stack characters into the result
StringBuilder res = new StringBuilder();
while(! stack.isEmpty()) { res.append(stack.pollLast()); }returnres.toString(); }}Copy the code9. leetcode1047 Removes all adjacent duplicates from a string
9.1 Solution Idea
1. Use the stack 
0-slowRepresents characters that do not need to be deleted,fastPointers are used to traverse the entire string
9.2 Code implementation 1: π΄ Use stack
class Solution {
public String removeDuplicates(String s) {
Deque<Character> stack = new ArrayDeque<>();
for (char c : s.toCharArray()) {
if(! stack.isEmpty() && stack.peek() == c) { stack.pop(); }else {
stack.push(c);
}
}
StringBuilder sb = new StringBuilder();
while(! stack.isEmpty()){ sb.append(stack.pollLast()); }returnsb.toString(); }}Copy the code9.3 Code implementation 2: π΄ Using fast and slow Pointers (space complexity reduced to O(1))
class Solution {
public String removeDuplicates(String s) {
char[] chars = s.toCharArray();
int slow = -1;
int fast = 0;
while (fast < s.length()) {
if (slow >= 0 && chars[fast] == chars[slow]) {
slow--;
} else {
slow++;
chars[slow] = chars[fast];
}
fast++;
}
return new String(chars, 0, slow + 1); }}Copy the code10. leetcode1209 Removes all adjacent duplicates II from the string
10.1
1. Use the stack 
10.2 Code implementation 1: π΄ Use stack (time complexity: O(N), space complexity: O(N))
class Solution {
class Pair {
char ch;
int count;
public Pair(char ch, int count) {
this.ch = ch;
this.count = count; }}public String removeDuplicates(String s, int k) {
Deque<Pair> stack = new ArrayDeque<>();
for (int i = 0; i < s.length(); i++) {
if(stack.isEmpty() || s.charAt(i) ! = stack.peek().ch) { stack.push(new Pair(s.charAt(i), 1));
} else {
stack.peek().count++;
if (stack.peek().count == k) {
stack.pop();
}
}
}
StringBuilder sb = new StringBuilder();
while(! stack.isEmpty()) { Pair p = stack.pollLast();for (int i = 0; i < p.count; i++) { sb.append(p.ch); }}returnsb.toString(); }}Copy the code10.3 Code implementation 2: π΄ Use fast and slow Pointers
class Solution {
public String removeDuplicates(String s, int k) {
char[] chars = s.toCharArray();
Deque<Integer> count = new ArrayDeque<>();
int slow = 0;
for (int fast = 0; fast < chars.length; slow++, fast++) {
if(slow ! = fast) { chars[slow] = chars[fast]; }if (slow == 0|| chars[slow] ! = chars[slow -1]) {
count.push(1);
} else {
int incremented = count.pop() + 1;
if (incremented == k) {
slow -= k;
} else{ count.push(incremented); }}}return new String(chars, 0, slow); }}Copy the code11. leetcode976 The maximum perimeter of a triangle
11.1 Solution Ideas
Without loss of generality, we assume that the sides of a triangle are longa.b.cmeetA, b, c or less or less, then the sufficient and necessary conditions for these three sides to form a triangle with non-zero area area+b>c.
11.2 Code implementation π΄
class Solution {
public int largestPerimeter(int[] nums) {
Arrays.sort(nums);
for (int i = nums.length - 1; i >= 2; i--) {
if (nums[i - 2] + nums[i - 1] > nums[i]) {
return nums[i - 2] + nums[i - 1] + nums[i]; }}return 0; }}Copy the code12. leetcode674 Longest continuous increasing sequence
12.1 Solution Idea
12.2 Code implementation (greedy + dual pointer)π΄
class Solution {
public int findLengthOfLCIS(int[] nums) {
int res = 1;
for (int start = 0, end = 1; end < nums.length; end++) {
if (nums[end] <= nums[end - 1]) {
start = end;
continue;
}
res = Math.max(res, end - start + 1);
}
returnres; }}Copy the code13. leetcode738 Monotonically increasing numbers
13.1 Solving the problem
1. Iterate to find the first non-increasing sequence
2. Roll back check until it is an increasing sequence
3. Replace all the numbers after the last change of the high level9
13.2 Code implementation π΄
class Solution {
public int monotoneIncreasingDigits(int n) {
char[] strN = String.valueOf(n).toCharArray();
int i = 1;
// 1. Find the first decrement bit
while (i < strN.length && strN[i - 1] <= strN[i])
i++;
if (i < strN.length) {
// 2. Keep the first digit -1 until the first digit is less than or equal to the second digit
while (i > 0 && strN[i - 1] > strN[i]) {
strN[i - 1] - =1;
i--;
}
// 3. Set all digits after I to 9
i++;
while (i < strN.length) {
strN[i++] = '9';
}
return Integer.parseInt(new String(strN));
} else {
returnn; }}}Copy the code14. leetcode134 Gas station
14.1 How to Solve the problem
Summary: If x does not get to y+1, then it is impossible to get to y+1 from any point x to Y. Because if you start at any one of these points, you’re going to start at zero, and if you start at x, you’re not going to start at zero, you might still have some oil left. If you can’t get to y plus 1 without starting at 0, you can’t even get to y plus 1 if you start at 0.
14.2 Code implementation π΄
class Solution {
public int canCompleteCircuit(int[] gas, int[] cost) {
int totalGas = 0;
int currGas = 0;
int startStation = 0;
for (int i = 0; i < gas.length; i++) {
totalGas += gas[i] - cost[i];
currGas += gas[i] - cost[i];
if (currGas < 0) {
startStation = i + 1;
currGas = 0; }}return totalGas >= 0 ? startStation : -1; }}Copy the code15. leetcode767 Refactoring string
15.1 How to solve the problem
15.2 Code implementation π΄
class Solution {
public String reorganizeString(String s) {
// 1. Count the number of occurrences of each character
char[] chars = s.toCharArray();
int n = chars.length;
int[] count = new int[26];
for (char c : chars) {
count[c - 'a'] + +;if (count[c - 'a'] > (n + 1) / 2)
return "";
}
// 2. Get the most common character
int maxCountIndex = 0;
for (int i = 0; i < 26; i++) {
if (count[i] > count[maxCountIndex])
maxCountIndex = i;
}
// 3. Place the most frequently occurring character on the even index first
char[] res = new char[n];
int index = 0;
while (count[maxCountIndex] > 0) {
res[index] = (char) (maxCountIndex + 'a');
index += 2;
count[maxCountIndex]--;
}
// 4. Put other characters in other places
for (int i = 0; i < 26; i++) {
while (count[i] > 0) {
if (index >= n) {
index = 1;
}
res[index] = (char) (i + 'a');
index += 2; count[i]--; }}return newString(res); }}Copy the code16. leetcode621 Task scheduler
16.1 How to solve the problem
1. Minimum time required to complete all tasks = Number of standby tasks + Number of all tasks
16.2 Code implementation π΄
class Solution {
public int leastInterval(char[] tasks, int n) {
int[] counter = new int[26];
int maxAppearCount = 0; // Maximum number of occurrences of the task with the most occurrences
int maxTaskCount = 0; // Maximum number of tasks
for (char task : tasks) {
counter[task - 'A'] + +;if (counter[task - 'A'] == maxAppearCount) {
maxTaskCount++;
} else if (counter[task - 'A'] > maxAppearCount) {
maxAppearCount = counter[task - 'A'];
maxTaskCount = 1; }}int partCount = maxAppearCount - 1; // The number of spare parts
int partLength = n - (maxTaskCount - 1); // The length of the spare part
int emptySlots = partCount * partLength; // Number of free slots
int availableTasks = tasks.length - maxAppearCount * maxTaskCount; // The number of available tasks
int idles = Math.max(0, emptySlots - availableTasks); // Number of standby tasks
return tasks.length + idles; // Minimum time required to complete all tasks = number of tasks available + Number of tasks available}}Copy the code17. leetcode670 The biggest exchange
17.1 How to Solve the problem
Greedy strategy: Swap the value behind the high value, and the larger the better
17.2 Code Implementation 1: Violence
class Solution {
public int maximumSwap(int num) {
char[] chars = String.valueOf(num).toCharArray();
int max = num;
for (int i = 0; i < chars.length; i++) {
for (int j = i + 1; j < chars.length; j++) {
swap(chars, i, j);
max = Math.max(max, Integer.parseInt(newString(chars))); swap(chars, i, j); }}return max;
}
private void swap(char[] chars, int i, int j) {
chartemp = chars[i]; chars[i] = chars[j]; chars[j] = temp; }}Copy the code17.3 Code implementation 2: π΄ Greedy
class Solution {
public int maximumSwap(int num) {
char[] chars = String.valueOf(num).toCharArray();
// Record the subscript of the last occurrence of each number
int[] last = new int[10];
for (int i = 0; i < chars.length; i++) {
last[chars[i] - '0'] = i;
}
// Scan from high to low to find the largest number to the right of the current position and swap
for (int i = 0; i < chars.length; i++) {
// Find the largest, so find backwards
for (int d = 9; d > chars[i] - '0'; d--) {
if (last[d] > i) {
char temp = chars[i];
chars[i] = chars[last[d]];
chars[last[d]] = temp;
// Only one swap is allowed, so return directly
return Integer.parseInt(newString(chars)); }}}returnnum; }}Copy the code18. leetcode861 The score after flipping the matrix
18.1 How to solve the problem
18.2 Code implementation π΄
class Solution {
public int matrixScore(int[][] grid) {
int rows = grid.length;
int cols = grid[0].length;
// make each line start with 1
for (int row = 0; row < rows; row++) {
if (grid[row][0] = =0) {
/ / line
for (int col = 0; col < cols; col++) {
grid[row][col] ^= 1; }}}int res = 0;
// The greater the number of 1, the greater the number
for (int col = 0; col < cols; col++) {
int count = 0;
// Count the number of 1's in the col column
for (int row = 0; row < rows; row++) {
count += grid[row][col];
}
int maxOneCount = Math.max(count, rows - count);
res += maxOneCount * (1 << (cols - col - 1));
}
returnres; }}Copy the code19. leetcode1029 Both scheduling
19.1 How to solve the problem
Optimal scheme: selectprice_A - price_BThe smallest N people, fly them to city A, and the rest to city B
19.2 Code implementation :π΄ greedy
class Solution {
public int twoCitySchedCost(int[][] costs) {
Arrays.sort(costs, new Comparator<int[] > () {@Override
public int compare(int[] o1, int[] o2) {
return (o1[0] - o1[1]) - (o2[0] - o2[1]); }});int n = costs.length / 2;
int total = 0;
for (int i = 0; i < n; i++) {
total += costs[i][0] + costs[i + n][1];
}
returntotal; }}Copy the code20. leetcode330 Complete the array as required
20.1 How to solve the problem
Greedy thinking: Join every timenumsAll of these numbers have to be as large as possible to cover a larger area. 2. For positive integersx, if all numbers in the interval [1, x-1] have been covered, andxIn the array, the numbers in the range [1, 2X-1] are also overwritten. 
20.2 Code implementation π΄
class Solution {
public int minPatches(int[] nums, int n) {
int res = 0;
// Greedy guarantees that all numbers in the range [1, x-1] will be covered
long x = 1;
int index = 0;
while (x <= n) {
if (index < nums.length && nums[index] <= x) {
// Because of greedy thinking, we always guarantee that all values less than x will be covered
// [1, x + x - 1] [1, x + nums[index] - 1]
x += nums[index];
index++;
} else {
res++; // Put x in the array
// For positive integer x, if all numbers in the interval [1, x-1] are already covered.
// If x is in an array, all numbers in the range [1, 2x-1] are also overwritten
x *= 2; }}returnres; }}Copy the code