No.1 设计有序流
解题思路
依照题意编码即可.
代码展现
class OrderedStream {private final String[] strings;
private int ptr;
public OrderedStream(int n) {strings = new String[n];
ptr = 0;
}
public List<String> insert(int id, String value) {
id--; // 数组下标从 0 开始
strings[id] = value;
List<String> res = new ArrayList<>();
for (; ptr < strings.length && strings[ptr] != null; ptr++) {res.add(strings[ptr]);
}
return res;
}
}No.2 确定两个字符串是否靠近
解题思路
解读、剖析失去两个字符串靠近的条件:
- 字符集雷同
- 每种字符呈现的次数形成的序列雷同
代码展现
class Solution {public boolean closeStrings(String word1, String word2) {int[] cnt1 = new int[26];
for (int i = 0; i < word1.length(); i++) {cnt1[word1.charAt(i) - 'a']++;
}
int[] cnt2 = new int[26];
for (int i = 0; i < word2.length(); i++) {cnt2[word2.charAt(i) - 'a']++;
}
// 字符集雷同
for (int i = 0; i < 26; i++) {
// 字符 i 若在 word1 中呈现, 那么在 word2 中也必须呈现
if (cnt1[i] + cnt2[i] != 0 && cnt1[i] * cnt2[i] == 0) {return false;}
}
// 次数序列雷同
Arrays.sort(cnt1);
Arrays.sort(cnt2);
for (int i = 0; i < 26; i++) {if (cnt1[i] != cnt2[i]) {return false;}
}
return true;
}
}No.3 将 x 减到 0 的最小操作数
解题思路
两根指针, 详见正文.
代码展现
class Solution {public int minOperations(int[] nums, int x) {
// 预处理出前缀和与后缀和, 不便后续计算
int[] prefixSum = new int[nums.length];
int[] suffixSum = new int[nums.length];
prefixSum[0] = nums[0];
for (int i = 1; i < nums.length; i++) {prefixSum[i] = prefixSum[i - 1] + nums[i];
}
suffixSum[nums.length - 1] = nums[nums.length - 1];
for (int i = nums.length - 2; i >= 0; i--) {suffixSum[i] = suffixSum[i + 1] + nums[i];
}
// 两根指针 left 和 right
int res = nums.length + 1;
int left = 0, right = 0;
// [0, left) + [right, nums.length)
for (; left < nums.length; left++) {while (right < nums.length && calcSum(left, right, prefixSum, suffixSum) > x) {right++;}
if (calcSum(left, right, prefixSum, suffixSum) == x) {
int len = left + nums.length - right;
res = Math.min(res, len);
}
}
return res > nums.length ? -1 : res;
}
private int calcSum(int left, int right, int[] prefixSum, int[] suffixSum) {// [0, left) + [right, nums.length)
return (left > 0 ? prefixSum[left - 1] : 0) +
(right < suffixSum.length ? suffixSum[right] : 0);
}
}
No.4 最大化网格幸福感
解题思路
深度优先搜寻 (回溯).
实质上就是枚举每一个格子是调配内向的人, 还是外向的人, 还是不调配.
下述代码展现思路, 能够计算出正确答案, 然而会超出工夫限度.
进一步优化能够将 grid 进行压缩并且记忆化, 方可通过.
代码展现
class Solution {
private int res;
public int getMaxGridHappiness(int m, int n, int introvertsCount, int extrovertsCount) {
res = 0;
dfs(0, 0, m, n, new byte[m][n], introvertsCount, extrovertsCount);
return res;
}
private void dfs(int x, int y, int m, int n, byte[][] grid, int introvertsCount, int extrovertsCount) {if (y == n) {
x++;
y = 0;
}
if (x == m || introvertsCount + extrovertsCount == 0) {res = Math.max(calc(grid), res);
return;
}
// 优化点: 就算剩下的人都取最大幸福值也不如以后答案优良, 进行搜寻.
if (introvertsCount * 120 + extrovertsCount * 120 + calc(grid) <= res) {return;}
if (extrovertsCount > 0) {grid[x][y] = 2;
dfs(x, y + 1, m, n, grid, introvertsCount, extrovertsCount - 1);
grid[x][y] = 0;
}
if (introvertsCount > 0) {grid[x][y] = 1;
dfs(x, y + 1, m, n, grid, introvertsCount - 1, extrovertsCount);
grid[x][y] = 0;
}
dfs(x, y + 1, m, n, grid, introvertsCount, extrovertsCount);
}
private int calc(byte[][] grid) {int[] dx = {1, -1, 0, 0};
int[] dy = {0, 0, 1, -1};
int res = 0;
for (int i = 0; i < grid.length; i++) {for (int j = 0; j < grid[0].length; j++) {if (grid[i][j] == 0) {continue;}
res += grid[i][j] == 1 ? 120 : 40;
int inc = grid[i][j] == 1 ? -30 : 20;
for (int k = 0; k < 4; k++) {int x = i + dx[k];
int y = j + dy[k];
if (x < 0 || y < 0 || x >= grid.length || y >= grid[0].length) {continue;}
if (grid[x][y] > 0) {res += inc;}
}
}
}
return res;
}}