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;}}