881. 救生艇
難度中等208收藏分享切換為英文接收動態反饋
給定陣列 people 。people[i]表示第 i 個人的體重 ，船的數量不限，每艘船可以承載的最大重量為 limit。
每艘船最多可同時載兩人，但條件是這些人的重量之和最多為 limit。
返回 承載所有人所需的最小船數 。
示例 1：
輸入： people = [1,2], limit = 3
輸出： 1
解釋： 1 艘船載 (1, 2)
複製程式碼示例 2：
輸入： people = [3,2,2,1], limit = 3
輸出： 3
解釋： 3 艘船分別載 (1, 2), (2) 和 (3)
複製程式碼示例 3：
輸入： people = [3,5,3,4], limit = 5
輸出： 4
解釋： 4 艘船分別載 (3), (3), (4), (5)
複製程式碼提示：
- 1 <= people.length <= 5 * 104
- 1 <= 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++;
}
}
return res;
}
}
複製程式碼
883. 三維形體投影面積
難度簡單66收藏分享切換為英文接收動態反饋
在 n x n 的網格 grid 中，我們放置了一些與 x，y，z 三軸對齊的 1 x 1 x 1 立方體。
每個值 v = grid[i][j] 表示 v 整整個正方體疊放在單元格 (i, j) 上。
現在，我們檢視這些立方體是否在 xy 、yz 和 zx 平面上的投影。
投影 就像影子，將 三維 形體對映到一個 二維 平面上。從頂部、前面和側面看立方體時，我們會看到“影子”。
返回 所有三個投影的總面積 。
示例 1：
輸入： [[1,2],[3,4]]
輸出： 17
解釋： 這裡有該形體在三個軸對齊平面上的三個投影(“陰影部分”)。
複製程式碼示例 2:
輸入： grid = [[2]]
輸出： 5
複製程式碼示例 3：
輸入： [[1,0],[0,2]]
輸出： 8
複製程式碼提示：
- n == grid.length == grid[i].length
- 1 <= n <= 50
- 0 <= 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];
}
return res + n*n;
}
}
複製程式碼
884. 兩句話中的不常見單詞
難度簡單154收藏分享切換為英文接收動態反饋
句子 是一串由空格分隔的單詞。每個 單詞 **僅由小寫字母組成。
如果某個單詞在其中一個句子中恰好出現一次，在另一個句子中卻 沒有出現 ，那麼這個單詞就是 不常見的 **。
給你兩個 句子 s1 和 s2 ，返回所有 不常用單詞 的列表。返回列表中單詞可以按 任意順序 組織。
示例 1：
輸入： s1 = "this apple is sweet", s2 = "this apple is sour"
輸出： ["sweet","sour"]
複製程式碼示例 2：
輸入： s1 = "apple apple", s2 = "banana"
輸出： ["banana"]
複製程式碼提示：
- 1 <= s1.length, s2.length <= 200
- s1 和 s2 由小寫英文字母和空格組成
- s1 和 s2 都不含前導或尾隨空格
- s1 和 s2 中的所有單詞間均由單個空格分隔
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(new String[list.size()]);
}
}
複製程式碼
885. 螺旋矩陣 III
難度中等74收藏分享切換為英文接收動態反饋
在 R 行 C 列的矩陣上，我們從 (r0, c0) 面朝東面開始
這裡，網格的西北角位於第一行第一列，網格的東南角位於最後一行最後一列。
現在，我們以順時針按螺旋狀行走，訪問此網格中的每個位置。
每當我們移動到網格的邊界之外時，我們會繼續在網格之外行走（但稍後可能會返回到網格邊界）。
最終，我們到過網格的所有 R * C 個空間。
按照訪問順序返回表示網格位置的座標列表。
示例 1：
輸入： R = 1, C = 4, r0 = 0, c0 = 0
輸出： [[0,0],[0,1],[0,2],[0,3]]
複製程式碼示例 2：
輸入： 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],[3,2],[2,2],[1,2],[0,2],[4,5],[4,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]]
複製程式碼提示：
- 1 <= R <= 100
- 1 <= C <= 100
- 0 <= r0 < R
- 0 <= 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}為當前位置，num為當前查詢的數字，dir為當前的方向
int Left = c0 - 1, Right = c0 + 1, Upper = r0 - 1, Bottom = r0 + 1; //四個方向的邊界
while (num <= R * C) {
if (x >= 0 && x < R && y >= 0 && y < C) { //{x， y}位置在矩陣中
res[num - 1] = new int[]{x, y};
num++;
}
if (dir == 0 && y == Right) { //向右到右邊界
dir += 1; //調轉方向向下
Right += 1; //右邊界右移
}
else if (dir == 1 && x == Bottom) { //向下到底邊界
dir += 1;
Bottom += 1; //底邊界下移
}
else if (dir == 2 && y == Left) { //向左到左邊界
dir += 1;
Left--; //左邊界左移
}
else if (dir == 3 && x == Upper) { //向上到上邊界
dir = 0;
Upper--; //上邊界上移
}
x += around[dir][0]; //下一個節點
y += around[dir][1];
}
return res;
}
}
複製程式碼
886. 可能的二分法
難度中等155收藏分享切換為英文接收動態反饋
給定一組 n 人（編號為 1, 2, ..., n）， 我們想把每個人分進任意大小的兩組。每個人都可能不喜歡其他人，那麼他們不應該屬於同一組。
給定整數 n 和陣列 dislikes ，其中 dislikes[i] = [ai, bi] ，表示不允許將編號為 ai 和 bi的人歸入同一組。當可以用這種方法將所有人分進兩組時，返回 true；否則返回 false。
示例 1：
輸入： n = 4, dislikes = [[1,2],[1,3],[2,4]]
輸出： true
解釋： group1 [1,4], group2 [2,3]
複製程式碼示例 2：
輸入： n = 3, dislikes = [[1,2],[1,3],[2,3]]
輸出： false
複製程式碼示例 3：
輸入： n = 5, dislikes = [[1,2],[2,3],[3,4],[4,5],[1,5]]
輸出： false
複製程式碼提示：
- 1 <= n <= 2000
- 0 <= dislikes.length <= 104
- dislikes[i].length == 2
- 1 <= dislikes[i][j] <= n
- ai < bi
- dislikes 中每一組都 不同
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;
}
}
複製程式碼
887. 雞蛋掉落
難度困難748收藏分享切換為英文接收動態反饋
給你 k 枚相同的雞蛋，並可以使用一棟從第 1 層到第 n 層共有 n 層樓的建築。
已知存在樓層 f ，滿足 0 <= f <= n ，任何從 高於 f 的樓層落下的雞蛋都會碎，從 f 樓層或比它低的樓層落下的雞蛋都不會破。
每次操作，你可以取一枚沒有碎的雞蛋並把它從任一樓層 x 扔下（滿足 1 <= x <= n）。如果雞蛋碎了，你就不能再次使用它。如果某枚雞蛋扔下後沒有摔碎，則可以在之後的操作中 重複使用 這枚雞蛋。
請你計算並返回要確定 f 確切的值 的 最小操作次數 是多少？
示例 1：
輸入： k = 1, n = 2
輸出： 2
解釋：
雞蛋從 1 樓掉落。如果它碎了，肯定能得出 f = 0 。
否則，雞蛋從 2 樓掉落。如果它碎了，肯定能得出 f = 1 。
如果它沒碎，那麼肯定能得出 f = 2 。
因此，在最壞的情況下我們需要移動 2 次以確定 f 是多少。
複製程式碼示例 2：
輸入： k = 2, n = 6
輸出： 3
複製程式碼示例 3：
輸入： k = 3, n = 14
輸出： 4
複製程式碼提示：
- 1 <= k <= 100
- 1 <= 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; // 操作的次數
while (dp[K] < N){
for (int i = K; i > 0; i--) // 從後往前計算
dp[i] = dp[i] + dp[i-1] + 1;
ans++;
}
return ans;
}
}
複製程式碼
888. 公平的糖果交換
難度簡單188收藏分享切換為英文接收動態反饋
愛麗絲和鮑勃擁有不同總數量的糖果。給你兩個陣列 aliceSizes 和 bobSizes ，aliceSizes[i] 是愛麗絲擁有的第 i 盒糖果中的糖果數量，bobSizes[j] 是鮑勃擁有的第 j 盒糖果中的糖果數量。
兩人想要互相交換一盒糖果，這樣在交換之後，他們就可以擁有相同總數量的糖果。一個人擁有的糖果總數量是他們每盒糖果數量的總和。
返回一個整數陣列 answer，其中 answer[0] 是愛麗絲必須交換的糖果盒中的糖果的數目，answer[1] 是鮑勃必須交換的糖果盒中的糖果的數目。如果存在多個答案，你可以返回其中 任何一個 。題目測試用例保證存在與輸入對應的答案。
示例 1：
輸入： aliceSizes = [1,1], bobSizes = [2,2]
輸出： [1,2]
複製程式碼示例 2：
輸入： aliceSizes = [1,2], bobSizes = [2,3]
輸出： [1,2]
複製程式碼示例 3：
輸入： aliceSizes = [2], bobSizes = [1,3]
輸出： [2,3]
複製程式碼示例 4：
輸入： aliceSizes = [1,2,5], bobSizes = [2,4]
輸出： [5,4]
複製程式碼提示：
- 1 <= aliceSizes.length, bobSizes.length <= 104
- 1 <= aliceSizes[i], bobSizes[j] <= 105
- 愛麗絲和鮑勃的糖果總數量不同。
- 題目資料保證對於給定的輸入至少存在一個有效答案。
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;
}
}
複製程式碼
889. 根據前序和後序遍歷構造二叉樹
難度中等220收藏分享切換為英文接收動態反饋
給定兩個整數陣列，preorder 和 postorder ，其中 preorder 是一個具有 無重複 值的二叉樹的前序遍歷，postorder 是同一棵樹的後序遍歷，重構並返回二叉樹。
如果存在多個答案，您可以返回其中 任何 一個。
示例 1：
輸入： preorder = [1,2,4,5,3,6,7], postorder = [4,5,2,6,7,3,1]
輸出： [1,2,3,4,5,6,7]
複製程式碼示例 2:
輸入: preorder = [1], postorder = [1]
輸出: [1]
複製程式碼提示：
- 1 <= preorder.length <= 30
- 1 <= preorder[i] <= preorder.length
- preorder 中所有值都 不同
- postorder.length == preorder.length
- 1 <= postorder[i] <= postorder.length
- postorder 中所有值都 不同
- 保證 preorder 和 postorder 是同一棵二叉樹的前序遍歷和後序遍歷
/**
* 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));
return node;
}
}
複製程式碼
890. 查詢和替換模式
難度中等120收藏分享切換為英文接收動態反饋
你有一個單詞列表 words 和一個模式 pattern，你想知道 words 中的哪些單詞與模式匹配。
如果存在字母的排列 p ，使得將模式中的每個字母 x 替換為 p(x) 之後，我們就得到了所需的單詞，那麼單詞與模式是匹配的。
（回想一下，字母的排列是從字母到字母的雙射：每個字母對映到另一個字母，沒有兩個字母對映到同一個字母。）
返回 words 中與給定模式匹配的單詞列表。
你可以按任何順序返回答案。
示例：
輸入： words = ["abc","deq","mee","aqq","dkd","ccc"], pattern = "abb"
輸出： ["mee","aqq"]
解釋： "mee" 與模式匹配，因為存在排列 {a -> m, b -> e, ...}。
"ccc" 與模式不匹配，因為 {a -> c, b -> c, ...} 不是排列。
因為 a 和 b 對映到同一個字母。
複製程式碼提示：
- 1 <= words.length <= 50
- 1 <= 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;
}
}
