矩阵置零(数组、哈希表)
给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地(http://baike.baidu.com/item/%E5%8E%9F%E5%9C%B0%E7%AE%97%E6%B3%95) 算法。 进阶：
- 一个直观的解决方案是使用 O(mn) 的额外空间，但这并不是一个好的解决方案。
- 一个简单的改进方案是使用 O(m + n) 的额外空间，但这仍然不是最好的解决方案。
- 你能想出一个仅使用常量空间的解决方案吗？
示例 1：
输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
输出：[[1,0,1],[0,0,0],[1,0,1]]
示例 2：
输入：matrix = [[0,1,2,0],[3,4,5,2],[1,3,1,5]]
输出：[[0,0,0,0],[0,4,5,0],[0,3,1,0]]
提示：
- m == matrix.length
- n == matrix[0].length
- 1 <= m, n <= 200
- -231 <= matrix[i][j] <= 231 - 1
解答：
class Solution {
public void setZeroes(int[][] matrix) {
int[] xNum = new int[matrix[0].length];
int[] yNum = new int[matrix.length];
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
if (matrix[i][j] == 0) {
xNum[j] = 1;
yNum[i] = 1;
}
}
}
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[i].length; j++) {
if (xNum[j] == 1 || yNum[i] == 1) {
matrix[i][j] = 0;
}
}
}
}
}
从中序与后序遍历序列构造二叉树(树、数组)
根据一棵树的中序遍历与后序遍历构造二叉树。 注意: 你可以假设树中没有重复的元素。 例如，给出 中序遍历 inorder = [9,3,15,20,7] 后序遍历 postorder = [9,15,7,20,3] 返回如下的二叉树： 3 / \ 9 20 / \ 15 7
解答：
public class TreeNode {
int val;
TreeNode left;
TreeNode right;
TreeNode(int x) {
val = x;
}
}
class Solution {
public TreeNode buildTree(int[] inorder, int[] postorder) {
return helper(inorder, postorder, postorder.length - 1, 0, inorder.length - 1);
}
public TreeNode helper(int[] inorder, int[] postorder, int postEnd, int inStart, int inEnd) {
if (inStart > inEnd) {
return null;
}
int currentVal = postorder[postEnd];
TreeNode current = new TreeNode(currentVal);
int inIndex = 0;
for (int i = inStart; i <= inEnd; i++) {
if (inorder[i] == currentVal) {
inIndex = i;
}
}
TreeNode left = helper(inorder, postorder, postEnd - (inEnd - inIndex) - 1, inStart, inIndex - 1);
TreeNode right = helper(inorder, postorder, postEnd - 1, inIndex + 1, inEnd);
current.left = left;
current.right = right;
return current;
}
}
存在重复元素(数组、哈希表)
给定一个整数数组，判断是否存在重复元素。 如果存在一值在数组中出现至少两次，函数返回 true 。如果数组中每个元素都不相同，则返回 false 。
示例 1: 输入: [1,2,3,1] 输出: true 示例 2: 输入: [1,2,3,4] 输出: false 示例 3: 输入: [1,1,1,3,3,4,3,2,4,2] 输出: true
解答：
class Solution {
public boolean containsNearbyAlmostDuplicate(int[] nums, int k, int t) {
if (k < 1 || t < 0)
return false;
SortedSet<Long> binTree = new TreeSet<>();
for (int i = 0; i < nums.length; i++) {
SortedSet<Long> son = binTree.subSet((long) nums[i] - t, (long) nums[i] + t + 1);
if (!son.isEmpty())
return true;
if (i >= k)
binTree.remove((long) nums[i - k]);
binTree.add((long) nums[i]);
}
return false;
}
}
本文内容到此结束了， 如有收获欢迎点赞????收藏????关注✔️，您的鼓励是我最大的动力。 如有错误❌疑问????欢迎各位大佬指出。 主页：共饮一杯无的博客汇总????????
保持热爱，奔赴下一场山海。????????????