448. 找到所有数组中消失的数字【简单】
448.找到所有数组中消失的数字
简单
1.1K
相关企业
给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果。
示例 1： 输入：nums = [4,3,2,7,8,2,3,1] 输出：[5,6] 示例 2： 输入：nums = [1,1] 输出：[2]
提示：
n == nums.length
1 <= n <= 105
1 <= nums[i] <= n
进阶：你能在不使用额外空间且时间复杂度为 O(n) 的情况下解决这个问题吗? 你可以假定返回的数组不算在额外空间内。
原地哈希
class Solution { public List<Integer> findDisappearedNumbers(int[] nums) { int n = nums.length; for (int num : nums) { int x = (num - 1) % n;//num会改变，但它取模的值不回变 0~n-1 nums[x] += n;//num会改变为num+n } System.out.println(Arrays.toString(nums)); List<Integer> ret = new ArrayList<Integer>(); for (int i = 0; i < n; i++) { if (nums[i] <= n) { ret.add(i + 1); } } return ret; } }
461. 汉明距离【简单】
461.汉明距离
简单
650
相关企业
两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。
给你两个整数 x 和 y，计算并返回它们之间的汉明距离。
示例 1： 输入：x = 1, y = 4 输出：2 解释： 1 (0 0 0 1) 4 (0 1 0 0) ↑ ↑ 上面的箭头指出了对应二进制位不同的位置。 示例 2： 输入：x = 3, y = 1 输出：1
提示：
0 <= x, y <= 231 - 1
异或+bitcount
class Solution { public int hammingDistance(int x, int y) { return Integer.bitCount(x^y); } }
494. 目标和【中等】
494.目标和
中等
1.7K
相关企业
给你一个整数数组 nums 和一个整数 target 。
向数组中的每个整数前添加 ‘+’ 或 ‘-’ ，然后串联起所有整数，可以构造一个 表达式 ：
例如，nums = [2, 1] ，可以在 2 之前添加 ‘+’ ，在 1 之前添加 ‘-’ ，然后串联起来得到表达式 “+2-1” 。
返回可以通过上述方法构造的、运算结果等于 target 的不同 表达式 的数目。
示例 1： 输入：nums = [1,1,1,1,1], target = 3 输出：5 解释：一共有 5 种方法让最终目标和为 3 。 -1 + 1 + 1 + 1 + 1 = 3 +1 - 1 + 1 + 1 + 1 = 3 +1 + 1 - 1 + 1 + 1 = 3 +1 + 1 + 1 - 1 + 1 = 3 +1 + 1 + 1 + 1 - 1 = 3 示例 2： 输入：nums = [1], target = 1 输出：1
提示：
1 <= nums.length <= 20
0 <= nums[i] <= 1000
0 <= sum(nums[i]) <= 1000
-1000 <= target <= 1000
参考
回溯
class Solution { int count=0; public int findTargetSumWays(int[] nums, int target) { backtrack(nums,target,0,0); return count; } public void backtrack(int[] nums,int target,int index,int sum){ if(index==nums.length){ if(sum==target){ count++; } }else{ backtrack(nums,target,index+1,sum+nums[index]); backtrack(nums,target,index+1,sum-nums[index]); } } }
参考
动态规划
class Solution { public int findTargetSumWays(int[] nums, int target) { int sum=0; for(int num:nums){ sum+=num; } int diff=sum-target; if(diff<0||diff%2!=0){ return 0; } int n=nums.length,neg=diff/2; int[][] dp=new int[n+1][neg+1]; dp[0][0]=1; for(int i=1;i<=n;i++){ int num=nums[i-1]; for(int j=0;j<=neg;j++){ dp[i][j]=dp[i-1][j]; if(j>=num){ dp[i][j]+=dp[i-1][j-num]; } } } return dp[n][neg]; } }
538. 把二叉搜索树转换为累加树【中等】
538.把二叉搜索树转换为累加树
中等
911
相关企业
给出二叉 搜索 树的根节点，该树的节点值各不相同，请你将其转换为累加树（Greater Sum Tree），使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。
提醒一下，二叉搜索树满足下列约束条件：
节点的左子树仅包含键 小于 节点键的节点。
节点的右子树仅包含键 大于 节点键的节点。
左右子树也必须是二叉搜索树。
注意：本题和 1038: https://leetcode-cn.com/problems/binary-search-tree-to-greater-sum-tree/ 相同
示例 1： 输入：[4,1,6,0,2,5,7,null,null,null,3,null,null,null,8] 输出：[30,36,21,36,35,26,15,null,null,null,33,null,null,null,8] 示例 2： 输入：root = [0,null,1] 输出：[1,null,1] 示例 3： 输入：root = [1,0,2] 输出：[3,3,2] 示例 4： 输入：root = [3,2,4,1] 输出：[7,9,4,10]
提示：
树中的节点数介于 0 和 104 之间。
每个节点的值介于 -104 和 104 之间。
树中的所有值 互不相同 。
给定的树为二叉搜索树。
参考
递归
/** * 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 { int sum=0; public TreeNode convertBST(TreeNode root) { if(root!=null){ convertBST(root.right); sum+=root.val; root.val=sum; convertBST(root.left); } return root; } }
官方
递归
/** * 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 convertBST(TreeNode root) { int sum = 0; TreeNode node = root; while (node != null) { if (node.right == null) { sum += node.val; node.val = sum; node = node.left; } else { TreeNode succ = getSuccessor(node); if (succ.left == null) { succ.left = node; node = node.right; } else { succ.left = null; sum += node.val; node.val = sum; node = node.left; } } } return root; } public TreeNode getSuccessor(TreeNode node) { TreeNode succ = node.right; while (succ.left != null && succ.left != node) { succ = succ.left; } return succ; } }
543. 二叉树的直径【简单】
543.二叉树的直径
简单
1.4K
相关企业
给你一棵二叉树的根节点，返回该树的 直径 。
二叉树的 直径 是指树中任意两个节点之间最长路径的 长度 。这条路径可能经过也可能不经过根节点 root 。
两节点之间路径的 长度 由它们之间边数表示。
示例 1： 输入：root = [1,2,3,4,5] 输出：3 解释：3 ，取路径 [4,2,1,3] 或 [5,2,1,3] 的长度。 示例 2： 输入：root = [1,2] 输出：1
提示：
树中节点数目在范围 [1, 104] 内
-100 <= Node.val <= 100
官方
/** * 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 { int ans; public int diameterOfBinaryTree(TreeNode root) { ans = 1; depth(root); return ans - 1; } public int depth(TreeNode node) { if (node == null) { return 0; // 访问到空节点了，返回0 } int L = depth(node.left); // 左儿子为根的子树的深度 int R = depth(node.right); // 右儿子为根的子树的深度 ans = Math.max(ans, L+R+1); // 计算d_node即L+R+1 并更新ans return Math.max(L, R) + 1; // 返回该节点为根的子树的深度 } }
560. 和为 K 的子数组【中等】
560.和为 K 的子数组
提示
中等
2K
相关企业
给你一个整数数组 nums 和一个整数 k ，请你统计并返回 该数组中和为 k 的连续子数组的个数 。
示例 1：
输入：nums = [1,1,1], k = 2
输出：2
示例 2：
输入：nums = [1,2,3], k = 3
输出：2
提示：
1 <= nums.length <= 2 * 104
-1000 <= nums[i] <= 1000
-107 <= k <= 107
暴力
class Solution { int count=0; public int subarraySum(int[] nums, int k) { //从左到右扫描 for(int i=0;i<nums.length;i++){ rightSubarraySum(nums,i,k); } return count; } //右边的连续子数组的求和 public void rightSubarraySum(int[] nums,int left,int k){ int sum=0; for(int i=left;i<nums.length;i++){ sum+=nums[i]; if(sum==k){ count++; } } } }
参考
前缀和
class Solution { public int subarraySum(int[] nums, int k) { int count=0; int pre=0; //存储前缀和(0,i),前缀和是pre的个数 Map<Integer,Integer> map=new HashMap<>(); map.put(0,1);//为了应对原数组求和=k for(int i=0;i<nums.length;i++){ pre+=nums[i]; if(map.containsKey(pre-k)){ count+=map.get(pre-k); } map.put(pre,map.getOrDefault(pre,0)+1); } return count; } }
581. 最短无序连续子数组【中等】
581.最短无序连续子数组
中等
1.1K
相关企业
给你一个整数数组 nums ，你需要找出一个 连续子数组 ，如果对这个子数组进行升序排序，那么整个数组都会变为升序排序。
请你找出符合题意的 最短 子数组，并输出它的长度。
示例 1：
输入：nums = [2,6,4,8,10,9,15]
输出：5
解释：你只需要对 [6, 4, 8, 10, 9] 进行升序排序，那么整个表都会变为升序排序。
示例 2：
输入：nums = [1,2,3,4]
输出：0
示例 3：
输入：nums = [1]
输出：0
提示：
1 <= nums.length <= 104
-105 <= nums[i] <= 105
进阶：你可以设计一个时间复杂度为 O(n) 的解决方案吗？
自己
class Solution { public int findUnsortedSubarray(int[] nums) { //极小值大于等于左边有序数组的最大值 //极大值小于等于左右边有序数组的最小值 //可以预处理，尽最大努力找到左右两边的有序数组的边界，但是可能会超越 //讨论数组由小变大 int len=nums.length; int left=0; int right=len-1; for(left=0;left<len;left++){ if(left+1<len&&nums[left+1]<nums[left]){ break; } } for(right=len-1;right>=0;right--){ if(right-1>=0&&nums[right-1]>nums[right]){ break; } } //说明原数组有序 if(right==-1&&left==len){ return 0; } //预处理之后的数组往两边扩散 int i=left; int j=right; for(i=left;i>=0;i--){ for(j=right;j<len;j++){ int leftMax=i-1>=0?nums[i-1]:Integer.MIN_VALUE;//哨兵 int rightMin=j+1<len?nums[j+1]:Integer.MAX_VALUE;//哨兵 int[] minAndMax = findMinAndMax(nums, i, j); //因为有了预处理可以这样判断 if(minAndMax[0]>=leftMax&&minAndMax[1]<=rightMin){ return j-i+1; } } } return j-i+1; } //计算数组的最小最大值 public int[] findMinAndMax(int[] nums,int left,int right){ int min=nums[left]; int max=nums[right]; for(int i=left;i<=right;i++){ min=Math.min(min,nums[i]); max=Math.max(max,nums[i]); } return new int[]{min,max}; } }
自己
双指针改进
class Solution { public int findUnsortedSubarray(int[] nums) { //极小值大于左边有序数组的最大值 //极大值小于右边有序数组的最小值 //可以预处理，尽最大努力找到左右两边的有序数组的边界，但是可能会超越 //讨论数组由小变大 int len = nums.length; int left = 0; int right = len - 1; for (left = 0; left < len; left++) { if (left + 1 < len && nums[left + 1] < nums[left]) { break; } } for (right = len - 1; right >= 0; right--) { if (right - 1 >= 0 && nums[right - 1] > nums[right]) { break; } } //说明原数组有序 if (right == -1 && left == len) { return 0; } //预处理之后的数组往两边扩散 int i = left; int j = right; /* for(i=left;i>=0;i--){ for(j=right;j<len;j++){ int leftMax=i-1>=0?nums[i-1]:Integer.MIN_VALUE;//哨兵 int rightMin=j+1<len?nums[j+1]:Integer.MAX_VALUE;//哨兵 int[] minAndMax = findMinAndMax(nums, i, j); if(minAndMax[0]>=leftMax&&minAndMax[1]<=rightMin){ return j-i+1; } } } */ //双指针 while (i >=0&& j<len) { int leftMax = i - 1 >= 0 ? nums[i - 1] : Integer.MIN_VALUE;//哨兵 int rightMin = j + 1 < len ? nums[j + 1] : Integer.MAX_VALUE;//哨兵 int[] minAndMax = findMinAndMax(nums, i, j); if(minAndMax[0]>=leftMax&&minAndMax[1]<=rightMin){ return j-i+1; } //往左扩散 极小值不需变化 if(i-1>=0&&minAndMax[0]<nums[i-1]){ i--; } //往右扩散 极大值不需变化 if(j+1<len&&minAndMax[1]>nums[j+1]){ j++; } } return j - i + 1; } //计算数组的最小最大值 public int[] findMinAndMax(int[] nums, int left, int right) { int min = nums[left]; int max = nums[right]; for (int i = left; i <= right; i++) { min = Math.min(min, nums[i]); max = Math.max(max, nums[i]); } return new int[]{min, max}; } }
暴力
class Solution { public int findUnsortedSubarray(int[] nums) { int len= nums.length; int[] nums1 = Arrays.copyOf(nums, len); Arrays.sort(nums1); int left=len; int right=-1; //找不同 for(int i=0;i<len;i++){ if(nums1[i]!=nums[i]){ left=i; break; } } for(int i=len-1;i>=0;i--){ if(nums1[i]!=nums[i]){ right=i; break; } } if(left==len&&right==-1){ return 0; } return right-left+1; } }
官方
class Solution { public int findUnsortedSubarray(int[] nums) { int n = nums.length; int maxn = Integer.MIN_VALUE, right = -1; int minn = Integer.MAX_VALUE, left = -1; for (int i = 0; i < n; i++) { if (maxn > nums[i]) { right = i; } else { maxn = nums[i]; } if (minn < nums[n - i - 1]) { left = n - i - 1; } else { minn = nums[n - i - 1]; } } return right == -1 ? 0 : right - left + 1; } }
