“This is the 34th day of my participation in the First Challenge 2022. For details: First Challenge 2022.”
Some of the problems in the LeetCode problem set may have been skipped directly, so clean up the previous brush with LeetCode
881. The lifeboat
Switch to English to receive dynamic feedback
Given an array of people. People [I] is the weight of the ith person, there is no limit to the number of boats, and the maximum weight each boat can carry is the limit.
Each boat can carry up to two people at a time, provided that the combined weight of these people is maximum limit.
Return the maximum number of boats needed to carry everyone.
Example 1:
Input: people = [1,2], limit = 3Copy the codeExample 2:
Input: people = [3,2,2,1], limit = 3Copy the codeExample 3:
Input: people = [3,5,3,4], limit = 5Copy the code
Tip:
1 <= people.length <= 5 * 1041 <= people[i] <= limit <= 3 * 104
class Solution {
public int numRescueBoats(int[] num, int limit) {
Arrays.sort(num);
int right = num.length - 1;
int left = 0;
int res = 0;
while (left <= right) {
if (num[left] + num[right] > limit) {
right--;
res++;
} else{ left++; right--; res++; }}returnres; }}Copy the code883. Projection area of three-dimensional form
Switch to English to receive dynamic feedback
In the grid of n x n, we placed some 1 x 1 x 1 cubes aligned with the x, y, and z axes.
Each value v = grid[I][j] indicates that V cubes are stacked on the cell (I, j).
Now, let’s look at the projections of these cubes onto the XY, yz, and Zx planes.
A projection is like a shadow that maps a three-dimensional shape onto a two-dimensional surface. When we look at the cube from the top, front and side, we see “shadows”.
Returns the total area of all three projections.
Example 1:
Input: [[1,2],[3,4]] output: 17 explanation: there are three projections (" shaded parts ") of the form on three axially aligned planes.Copy the codeExample 2:
Input: grid = [[2]] Output: 5Copy the codeExample 3:
Input: [[1,0],[0,2]] output: 8Copy the code
Tip:
n == grid.length == grid[i].length1 <= n <= 500 <= grid[i][j] <= 50
class Solution {
public int projectionArea(int[][] grid) {
int[] x = new int[grid.length];
int[] y = new int[grid.length];
int n = grid.length;
int res = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
x[i] = (int)Math.max(x[i], grid[i][j]);
y[j] = (int)Math.max(y[j], grid[i][j]);
if (grid[i][j] == 0) { res--; }}}for (int i = 0; i < n; i++) {
res = res + x[i] + y[i];
}
returnres + n*n; }}Copy the code884. Uncommon words in two sentences
Switch to English to receive dynamic feedback
A sentence is a string of words separated by Spaces. Each word ** consists only of lowercase letters.
If a word appears exactly once in one sentence but not in the other, it is an uncommon word.
Given two sentences s1 and s2, return a list of all uncommon words. Returns a list of words that can be organized in any order.
Example 1:
S1 = "this apple is sweet" s2 = "this apple is sour" output: ["sweet","sour"]Copy the codeExample 2:
Input: s1 = "apple ", s2 = "banana" output: ["banana"]Copy the code
Tip:
1 <= s1.length, s2.length <= 200s1和s2The value consists of lowercase letters and Spacess1和s2There are no leading or trailing Spacess1和s2All words are separated by a single space
class Solution {
public String[] uncommonFromSentences(String s1, String s2) {
String[] strs = s1.split("");
Map<String,Integer> map = new HashMap<String,Integer>();
for (String s : strs) {
map.put(s,map.getOrDefault(s,0) + 1);
}
strs = s2.split("");
for (String s : strs) {
map.put(s, map.getOrDefault(s,0) + 1);
}
List<String> list = new LinkedList<String>();
for (String s : map.keySet()) {
if (map.get(s) == 1) { list.add(s); }}return list.toArray(newString[list.size()]); }}Copy the code885. Spiral matrix III
Switch to English to receive dynamic feedback
On the matrix with row R and column C, we start with (r0, c0) facing east
Here, the northwest corner of the grid is in the first row, first column, and the southeast corner of the grid is in the last row, last column.
Now, we walk clockwise in a spiral to visit each location in the grid.
Whenever we move outside the grid boundary, we continue to walk outside the grid (but may return to the grid boundary later).
And finally, we’ve been to all R * C Spaces of the grid.
Returns a list of coordinates representing grid positions in access order.
Example 1:
Input: R = 1, C = 4, r0 = 0, c0 = 0 output: [[0, 0], [0, 1], [0, 2], [0, 3]]Copy the code
Example 2:
Input: R = 5, C = 6, r0 = 1, c0 = 4 [[1, 4], [1, 5], [2, 5], [2, 4], [2, 3], [1, 3], [0, 3], [0, 4], [0, 5], [3, 5], [3, 4], [3], [3, 2], [2], [1, 2], [0, 2], [4, 5], [4], [4, 3], [4, 2 ], [4, 1], [3, 1], [2, 1], [1, 1], [0, 1], [4, 0], [3, 0], [2, 0], [1, 0], [0, 0]]Copy the code
Tip:
1 <= R <= 1001 <= C <= 1000 <= r0 < R0 <= c0 < C
class Solution {
public int[][] spiralMatrixIII(int R, int C, int r0, int c0) {
int[][] res = new int[R*C][2];
int[][] around = {{0.1}, {1.0}, {0, -1}, {-1.0}};
int x = r0, y = c0, num = 1, dir = 0; //{x, y} is the current position, num is the current number, dir is the current direction
int Left = c0 - 1, Right = c0 + 1, Upper = r0 - 1, Bottom = r0 + 1; // The boundary of the four directions
while (num <= R * C) {
if (x >= 0 && x < R && y >= 0 && y < C) { //{x, y} positions are in the matrix
res[num - 1] = new int[]{x, y};
num++;
}
if (dir == 0 && y == Right) { // Go right to the right border
dir += 1; // Turn around and go down
Right += 1; // Move the right boundary to the right
}
else if (dir == 1 && x == Bottom) { // Down to the bottom of the boundary
dir += 1;
Bottom += 1; // The bottom boundary moves down
}
else if (dir == 2 && y == Left) { // Go left to the left boundary
dir += 1;
Left--; // The left boundary moves to the left
}
else if (dir == 3 && x == Upper) { // Up to the upper boundary
dir = 0;
Upper--; // The upper boundary is moved up
}
x += around[dir][0]; // Next node
y += around[dir][1];
}
returnres; }}Copy the code886. Possible dichotomy
Switch to English to receive dynamic feedback
Given a group of n people (numbered 1, 2… N), we want to put everyone into two groups of any size. Everyone may not like everyone else, so they shouldn’t be in the same group.
Given an integer N and an array for meals, where meals [I] = [ai, bi] indicate that persons numbered AI and BI are not allowed to be grouped in the same group. Returns true when you can divide everyone into two groups using this method; Otherwise return false.
Example 1:
Enter: n = 4, snacks = [[1,2],[1,3],[2,4]] output: true explanation: group1 [1,4], group2 [2,3]Copy the codeExample 2:
Input: n = 3, dislikes = [[1, 2], [1, 3], [2, 3]] output: falseCopy the codeExample 3:
Input: n = 5, dislikes = [[1, 2], [2, 3], [3, 4], [4, 5], [1, 5]] output: falseCopy the code
Tip:
1 <= n <= 20000 <= dislikes.length <= 104dislikes[i].length == 21 <= dislikes[i][j] <= nai < bidislikesEach of the groups indifferent
class Solution {
ArrayList<Integer>[] list;
Map<Integer,Integer> color;
public boolean possibleBipartition(int n, int[][] bool) {
list = new ArrayList[n + 1];
color = new HashMap<Integer,Integer>();
for (int i = 0; i <= n; i++) {
list[i] = new ArrayList<Integer>();
}
for (int i = 0; i< bool.length; i++) {
list[bool[i][0]].add(bool[i][1]);
list[bool[i][1]].add(bool[i][0]);
}
for (int node = 1; node <= n; node++) {
if(! color.containsKey(node)) {if(! dfs(node,0)) {
return false; }}}return true;
}
public boolean dfs(int node, int group) {
if(color.containsKey(node)) {
return color.get(node) == group;
}
color.put(node,group);
for (int i : list[node]) {
if(! dfs(i,group ^1)) {
return false; }}return true; }}Copy the codeThe egg falls
Difficulty 748 Switch to English to receive dynamic feedback
You are given k of the same eggs and can use a building with n floors from the first to the NTH.
It is known that there exists a floor F such that 0 <= f <= n, and any egg dropped from a floor above f will break, and no egg dropped from floor F or a floor below it will break.
For each operation, you can take an unbroken egg and drop it from any floor X (1 <= x <= n). If the egg breaks, you can’t use it again. If an egg does not break after being dropped, it can be reused in subsequent operations.
Please calculate and return what is the minimum number of operations required to determine the exact value of f?
Example 1:
Input: k = 1, n = 2 Output: 2 Explanation: The egg fell from the first floor. If it breaks, I'm sure that f is equal to 0. Otherwise, the egg falls from the 2nd floor. If it breaks, I'm sure that f is equal to 1. If it doesn't break, then you definitely get f is equal to 2. So in the worst case we have to move it 2 times to figure out what f is.Copy the codeExample 2:
Input: k = 2, n = 6 Output: 3Copy the codeExample 3:
Input: k = 3, n = 14 Output: 4Copy the code
Tip:
1 <= k <= 1001 <= n <= 104
class Solution {
// public int superEggDrop(int K, int N) {
// if (N == 1) {
// return 1;
/ /}
// int[][] f = new int[N + 1][K + 1];
// for (int i = 1; i <= K; ++i) {
// f[1][i] = 1;
/ /}
// int ans = -1;
// for (int i = 2; i <= N; ++i) {
// for (int j = 1; j <= K; ++j) {
// f[i][j] = 1 + f[i - 1][j - 1] + f[i - 1][j];
/ /}
// if (f[i][K] >= N) {
// ans = i;
// break;
/ /}
/ /}
// return ans;
/ /}
public int superEggDrop(int K, int N) {
int[] dp = new int[K + 1];
int ans = 0; // The number of operations
while (dp[K] < N){
for (int i = K; i > 0; i--) // Calculate from back to front
dp[i] = dp[i] + dp[i-1] + 1;
ans++;
}
returnans; }}Copy the code888. Fair candy exchange
Switch to English to receive dynamic feedback
Alice and Bob have different total amounts of candy. Give you two arrays aliceSizes and bobSizes. AliceSizes [I] is the number of the candy in the i-box that Alice owns, and bobSizes[j] is the number of the candy in the j-box that Bob owns.
The two want to exchange a box of candy with each other so that after the exchange, they can have the same total amount of candy. The total number of sweets a person owns is the total number of sweets they have in each box.
Return an integer array answer, where answer[0] is the number of sweets in the candy box that Alice must exchange and answer[1] is the number of sweets in the candy box that Bob must exchange. If more than one answer exists, you can return any one of them. The problem test case ensures that there is an answer to the input.
Example 1:
Input: aliceSizes = [1,1], bobSizes = [2,2]Copy the codeExample 2:
Input: aliceSizes = [1,2], bobSizes = [2,3]Copy the codeExample 3:
Input: aliceSizes = [2], bobSizes = [1,3] output: [2,3]Copy the codeExample 4:
Input: aliceSizes = [1,2,5], bobSizes = [2,4] output: [5,4]Copy the code
Tip:
1 <= aliceSizes.length, bobSizes.length <= 1041 <= aliceSizes[i], bobSizes[j] <= 105- Alice and Bob have different total amounts of candy.
- Question data guarantees that at least one valid answer exists for a given input.
class Solution {
public int[] fairCandySwap(int[] a, int[] b) {
int sumA = 0, sumB = 0;
boolean[] bool = new boolean[100001];
for (int i : a) {
sumA += i;
bool[i] = true;
}
for (int i : b) {
sumB += i;
}
int res = (sumA - sumB) / 2;
for (int i : b) {
if (i + res >= 0 && i + res <= bool.length && bool[i + res]) {
return new int[]{i + res,i}; }}return null; }}Copy the codeConstruct a binary tree based on preorder and postorder traversal
Switch to English to receive dynamic feedback
Given two arrays of integers, preorder and Postorder, where preorder is a pre-traversal of a binary tree with no duplicate values and Postorder is a post-traversal of the same tree, reconstructing and returning the binary tree.
If more than one answer exists, you can return any one of them.
Example 1:
Input: preorder =,2,4,5,3,6,7 [1], postorder =,5,2,6,7,3,1 [4] output:,2,3,4,5,6,7 [1]Copy the codeExample 2:
Input: preOrder = [1], poStorder = [1]Copy the code
Tip:
1 <= preorder.length <= 301 <= preorder[i] <= preorder.lengthpreorderAll values indifferentpostorder.length == preorder.length1 <= postorder[i] <= postorder.lengthpostorderAll values indifferent- ensure
preorder和postorderIs pre-order traversal and post-order traversal of the same binary tree
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode() {} * TreeNode(int val) { this.val = val; } * TreeNode(int val, TreeNode left, TreeNode right) { * this.val = val; * this.left = left; * this.right = right; *} *} */
class Solution {
public TreeNode constructFromPrePost(int[] pre, int[] post) {
int n = pre.length;
if (n == 0) return null;
TreeNode node = new TreeNode(pre[0]);
if (n == 1) return node;
int left = 0;
for (int i = 0; i < n; i++) {
if (pre[1] == post[i]) {
left = i + 1;
}
}
node.left = constructFromPrePost(Arrays.copyOfRange(pre, 1, left + 1), Arrays.copyOfRange(post, 0, left));
node.right = constructFromPrePost(Arrays.copyOfRange(pre, left + 1, n), Arrays.copyOfRange(post, left, n - 1));
returnnode; }}Copy the codeFind and replace mode
Switch to English to receive dynamic feedback
You have a list of words and a pattern pattern, and you want to know which words in the words match the pattern.
Words match patterns if there is a permutation p of letters such that by replacing each letter x in the pattern with p(x) we get the word we want.
(Recall that the alphabetic arrangement is a bijection from letter to letter: each letter maps to another letter, and no two letters map to the same letter.)
Returns a list of words in words that match the given pattern.
You can return the answers in any order.
Example:
Input: words = [" ABC ", "deq", "mee", "aqq", "DKD", "CCC"], the pattern = "abb" output: [" mee ", "aqq]" explanation: "Mee" matches the pattern because there are permutations {a -> m, b -> e... }. "CCC" does not match the pattern because {a -> C, b -> C,... } is not permutation. Because a and B map to the same letter.Copy the code
Tip:
1 <= words.length <= 501 <= pattern.length = words[i].length <= 20
class Solution {
public List<String> findAndReplacePattern(String[] words, String pattern) {
ArrayList<String> list = new ArrayList<String>();
for (String s : words) {
if(compare(s,pattern)) { list.add(s); }}return list;
}
public boolean compare(String s1, String s2) {
char[] str1 = s1.toCharArray();
char[] str2 = s2.toCharArray();
Map<Character, Character> map = new HashMap<Character, Character>();
for (int i = 0; i < str1.length; i++) {
if(! map.containsKey(str1[i])) map.put(str1[i], str2[i]);if(map.get(str1[i]) ! = str2[i])return false;
}
boolean[] bool = new boolean[26];
for (char c : map.values()) {
if(bool[c - 'a']) return false;
bool[c-'a'] = true;
}
return true; }}Copy the code