200，924，739，179，1，20，93
200. 岛屿数量
中等
给你一个由 '1'（陆地）和 '0'（水）组成的的二维网格，请你计算网格中岛屿的数量。
岛屿总是被水包围，并且每座岛屿只能由水平方向和/或竖直方向上相邻的陆地连接形成。
此外，你可以假设该网格的四条边均被水包围。
示例 1：
输入：grid = [ ["1","1","1","1","0"], ["1","1","0","1","0"], ["1","1","0","0","0"], ["0","0","0","0","0"] ] 输出：1
class Solution {
public int numIslands(char[][] grid) {
if (grid == null || grid.length == 0) {
return 0; // 如果网格为空，返回0，可以不写
}
int nr = grid.length; // 网格的行数
int nc = grid[0].length; // 网格的列数
int num_islands = 0; // 初始化岛屿数量为0
// 遍历网格的每个单元格
for (int r = 0; r < nr; r++) {
for (int c = 0; c < nc; c++) {
// 如果发现一个新的岛屿（'1'）
if (grid[r][c] == '1') {
++num_islands; // 岛屿数量加1
dfs(grid, r, c); // 使用DFS将整个岛屿标记为已访问
}
}
}
return num_islands; // 返回岛屿的总数
}
// 帮助函数，用于在网格上执行深度优先搜索（DFS）
void dfs(char[][] grid, int r, int c) {
int nr = grid.length; // 网格的行数
int nc = grid[0].length; // 网格的列数
// 检查是否越界或者已经访问过（'0'）
if (r < 0 || c < 0 || r >= nr || c >= nc || grid[r][c] == '0') {
return; // 如果不是有效的DFS单元格，则返回
}
grid[r][c] = '0'; // 将当前单元格标记为已访问，设置为'0'
// 递归地对上下左右相邻的单元格执行DFS
dfs(grid, r - 1, c); // 上
dfs(grid, r + 1, c); // 下
dfs(grid, r, c - 1); // 左
dfs(grid, r, c + 1); // 右
}
// 计算岛屿的数量
}
924. 尽量减少恶意软件的传播
困难
给出了一个由 n 个节点组成的网络，用 n × n 个邻接矩阵图 graph 表示。在节点网络中，当 graph[i][j] = 1 时，表示节点 i 能够直接连接到另一个节点 j。
一些节点 initial 最初被恶意软件感染。只要两个节点直接连接，且其中至少一个节点受到恶意软件的感染，那么两个节点都将被恶意软件感染。这种恶意软件的传播将继续，直到没有更多的节点可以被这种方式感染。
假设 M(initial) 是在恶意软件停止传播之后，整个网络中感染恶意软件的最终节点数。
如果从 initial 中移除某一节点能够最小化 M(initial)， 返回该节点。如果有多个节点满足条件，就返回索引最小的节点。
请注意，如果某个节点已从受感染节点的列表 initial 中删除，它以后仍有可能因恶意软件传播而受到感染。
示例 1：
输入：graph = [[1,1,0],[1,1,0],[0,0,1]], initial = [0,1] 输出：0
示例 2：
输入：graph = [[1,0,0],[0,1,0],[0,0,1]], initial = [0,2] 输出：0
示例 3：
输入：graph = [[1,1,1],[1,1,1],[1,1,1]], initial = [1,2] 输出：1
739. 每日温度
中等
给定一个整数数组 temperatures ，表示每天的温度，返回一个数组 answer ，其中 answer[i] 是指对于第 i 天，下一个更高温度出现在几天后。如果气温在这之后都不会升高，请在该位置用 0 来代替。
示例 1:
输入: temperatures = [73,74,75,71,69,72,76,73]
输出: [1,1,4,2,1,1,0,0]
class Solution {
public int[] dailyTemperatures(int[] temperatures) {
int length = temperatures.length; // 获取温度数组的长度
int[] ans = new int[length]; // 初始化答案数组，每个元素默认值为0
Deque<Integer> stack = new LinkedList<Integer>(); // 使用栈来存储温度的索引
for (int i = 0; i < length; i++) {
int temperature = temperatures[i]; // 获取当前索引的温度
// 当栈非空且当前温度大于栈顶温度对应的索引的温度
while (!stack.isEmpty() && temperature > temperatures[stack.peek()]) {
int prevIndex = stack.pop(); // 弹出栈顶索引
ans[prevIndex] = i - prevIndex; // 计算温差天数，并将其填入答案数组
}
stack.push(i); // 将当前索引压入栈
}
return ans; // 返回结果数组
}
}
179. 最大数
中等
给定一组非负整数 nums，重新排列每个数的顺序（每个数不可拆分）使之组成一个最大的整数。
注意：输出结果可能非常大，所以你需要返回一个字符串而不是整数。
示例 1：
输入：nums = [10,2]输出："210"
示例 2：
输入：nums = [3,30,34,5,9]输出："9534330"
1. 两数之和
已解答
简单
相关标签
相关企业
提示
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
你可以按任意顺序返回答案。
示例 1：
输入：nums = [2,7,11,15], target = 9 输出：[0,1] 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> hashtable = new HashMap<>();
for (int i = 0; i < nums.length; i++) {
if (hashtable.containsKey(target - nums[i])) {
return new int[]{hashtable.get(target - nums[i]), i};
}
hashtable.put(nums[i], i);
}
return new int[0];
}
}
20. 有效的括号
简单
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
示例 1：
输入：s = "()" 输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]" 输出：false
class Solution {
public boolean isValid(String s) {
Deque<Character> stack = new ArrayDeque<>();
int n = s.length();
for (int i = 0; i < n; i++) {
char ch = s.charAt(i);
if (ch == '(') {
stack.push(')');
} else if (ch == '[') {
stack.push(']');
} else if (ch == '{') {
stack.push('}');
} else if (!stack.isEmpty() && ch == stack.peek()) {
stack.pop();
} else {
return false;
}
}
return stack.isEmpty();
}
}
93. 复原 IP 地址
中等
相关标签
相关企业
有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
- 例如：
"0.1.2.201"和"192.168.1.1"是 有效 IP 地址，但是"0.011.255.245"、"192.168.1.312"和"192.168@1.1"是 无效 IP 地址。
给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能的有效 IP 地址，这些地址可以通过在 s 中插入 '.' 来形成。你 不能 重新排序或删除 s 中的任何数字。你可以按 任何 顺序返回答案。
示例 1：
输入：s = "25525511135" 输出：["255.255.11.135","255.255.111.35"]
示例 2：
输入：s = "0000" 输出：["0.0.0.0"]
示例 3：
输入：s = "101023" 输出：["1.0.10.23","1.0.102.3","10.1.0.23","10.10.2.3","101.0.2.3"]
import java.util.ArrayList;
import java.util.List;
class Solution {
List<String> ans = new ArrayList<>(); // 保存所有可能的 IP 地址
StringBuilder path = new StringBuilder(); // 保存当前的 IP 地址段
// 入口函数，给定字符串 s，返回所有合法的 IP 地址
public List<String> restoreIpAddresses(String s) {
backTrack(s, 0, 0); // 开始回溯
return ans; // 返回结果
}
// 回溯函数，startIndex 表示当前处理到的字符串位置，count 表示已处理的 IP 地址段数
private void backTrack(String s, int startIndex, int count) {
// 如果处理了 4 段并且已经用完所有数字，则保存结果
if (count == 4 && startIndex == s.length()) {
ans.add(path.deleteCharAt(path.length() - 1).toString()); // 去掉末尾的点
return;
}
// 如果超过 4 段，则直接返回
if (count > 4) {
return;
}
// 遍历字符串，尝试取一个、两个或三个字符作为一个 IP 地址段
for (int i = startIndex; i < s.length() && i < startIndex + 3; i++) {
String str = s.substring(startIndex, i + 1); // 当前取的 IP 地址段
if (isTrue(str)) { // 判断是否合法
int len = path.length(); // 记录当前路径长度
path.append(str).append("."); // 添加 IP 地址段
backTrack(s, i + 1, count + 1); // 递归处理剩余的字符串
path.setLength(len); // 回溯，恢复路径长度
}
}
}
// 判断一个字符串是否为合法的 IP 地址段
private boolean isTrue(String s) {
// 如果长度大于1且首字符为0，则不是合法的 IP 地址段
if (s.length() > 1 && s.charAt(0) == '0') {
return false;
}
// 将字符串转换为整数，判断是否在 0 到 255 之间
int a = Integer.parseInt(s);
return a >= 0 && a <= 255;
}
}
