devbox
程序诗人2
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

leetcode3_给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集

作者：程序诗人2 | 2024-01-31 13:03:53

赞

踩

给你一个整数数组 nums ,数组中的元素 互不相同 。返回该数组所有可能的子集(幂集

78.给你一个整数数组 nums ，数组中的元素 互不相同 。返回该数组所有可能的子集（幂集）。

解集 不能 包含重复的子集。你可以按 任意顺序 返回解集。

示例 1：

输入：nums = [1,2,3]
输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]
示例 2：

输入：nums = [0]
输出：[[],[0]]
 

提示：

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同

有想法，为空返回空，接下来就是上一个+上一个的组合里加新元素的所有。实现起来很困难。

  1. class Solution {
  2.     public List<List<Integer>> subsets(int[] nums) {
  3.         List<List<Integer>> res=new ArrayList<>();
  4.         List<Integer> temp=new ArrayList<>();
  5.         //先放一个空进来
  6.         res.add(temp);
  7.         for(int i=0;i<nums.length;i++){
  8.             //因为内层循环一直在给res做添加，所以必须保存内层循环开始前的尺寸。
  9.             int k=res.size();
  10.             for(int j=0;j<k;j++){
  11.                 temp=res.get(j);
  12.                 //为什么这里一定要新建一个temp1？add方法的返回值是一个对象的引用，不是一个简单的值！！！
  13.                 List<Integer> temp1=new ArrayList<>(temp);
  14.                 temp1.add(nums[i]);
  15.                 res.add(temp1);
  16.             }
  17.         }
  18.         return res;
  19.     }
  20. }

答案的递归法：

  1. class Solution {
  2.     List<Integer> t = new ArrayList<Integer>();
  3.     List<List<Integer>> ans = new ArrayList<List<Integer>>();
  5.     public List<List<Integer>> subsets(int[] nums) {
  6.         dfs(0, nums);
  7.         return ans;
  8.     }
  9.  
  10.     public void dfs(int cur, int[] nums) {
  11.         if (cur == nums.length) {
  12.             ans.add(new ArrayList<Integer>(t));
  13.             return;
  14.         }
  15.         t.add(nums[cur]);
  16.         dfs(cur + 1, nums);
  17.         t.remove(t.size() - 1);
  18.         dfs(cur + 1, nums);
  19.     }
  20. }

1.动态规划

  1. class Solution {
  2.     public List<List<Integer>> subsets(int[] nums) {
  3.         List<List<Integer>> res=new ArrayList<>();
  4.         List<Integer> initSub=new ArrayList<>();
  5.         res.add(initSub);//加一个null
  6.         for (int i = 0; i < nums.length; i++) {
  7.             int time=res.size();
  8.             for (int j = 0; j < time; j++) {
  9.                 List<Integer> list=res.get(j);
  10.                 List<Integer> sub=new ArrayList<>(list);
  11.                 sub.add(nums[i]);
  12.                 res.add(sub);
  13.             }
  14.         }
  15.         return res;
  16.     }
  17. }

461.两个整数之间的 汉明距离 指的是这两个数字对应二进制位不同的位置的数目。

给你两个整数 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

  1. class Solution {
  2.     public int hammingDistance(int x, int y) {
  3.         int res=x^y;
  4.         int num=0;
  5.         while(res!=0){
  6.             int temp=res&1;
  7.             num+=temp;
  8.             res=res>>1;
  9.         }
  10.         return num;
  11.     }
  12. }
94. 给定一个二叉树的根节点 root ，返回它的 中序 遍历。

示例 1：


输入：root = [1,null,2,3]
输出：[1,3,2]
示例 2：

输入：root = []
输出：[]
示例 3：

输入：root = [1]
输出：[1]
示例 4：


输入：root = [1,2]
输出：[2,1]
示例 5：


输入：root = [1,null,2]
输出：[1,2]
 

提示：

树中节点数目在范围 [0, 100] 内
-100 <= Node.val <= 100

 一开始执迷于把链表拿到复制，后来想起可以自己写一个带链表的方法。

  1. class Solution {
  2.     public List<Integer> inorderTraversal(TreeNode root) {
  3.         List<Integer> list=new ArrayList<Integer>();
  4.         inorder(root,list);
  5.         return list;
  6.     }
  7.     public static void inorder(TreeNode root,List<Integer> res){
  8.         if(root==null){
  9.            res=null;
  10.            return;
  11.         }
  12.         if(root.left!=null){
  13.            inorder(root.left,res);
  14.         }
  15.         res.add(root.val);
  16.         if(root.right!=null){
  17.             inorder(root.right,res);
  18.         }
  19.     }
  20. }

1.迭代-迭代的本质是维护一个空间复杂度为n的栈。

  1. class Solution {
  2.     public List<Integer> inorderTraversal(TreeNode root) {
  3.         List<Integer> list=new ArrayList<Integer>();
  4.         //迭代法，维护一个队列存储结果
  5.         Deque<TreeNode> deque=new LinkedList<>();
  6.         while(root!=null||!deque.isEmpty()){
  7.             while(root!=null){
  8.                 deque.push(root);
  9.                 root=root.left;
  10.             }
  11.             root=deque.pop();
  12.             list.add(root.val);
  13.             //
  14.             root=root.right;
  15.         }
  16.         return list;
  17.     }
  18. }

2.Morris中序遍历-莫里斯遍历

  1. class Solution {
  2.     public List<Integer> inorderTraversal(TreeNode root) {
  3.         List<Integer> res = new ArrayList<Integer>();
  4.         TreeNode predecessor = null;
  5.         while(root!=null){
  6.             if(root.left!=null){
  7.                 //向左走一步
  8.                 predecessor=root.left;
  9.                 while(predecessor.right!=null){
  10.                 //走到左子树的最右节点
  11.                 predecessor=predecessor.right;
  12.                 }
  13.                 //让根节点称为最右节点的右节点，并剪断根节点的左树
  14.                 predecessor.right=root;
  15.                 TreeNode temp=root.left;
  16.                 root.left=null;
  17.                 root=temp;
  18.             }else{
  19.                 //现在左边的树已经完全变成了一个链表，只有右节点了，
  20.                 //所以往右走，如果后面又遇到了有左节点的节点，往左走一步，继续噶右树，类似递归
  21.                 res.add(root.val);
  22.                 root=root.right;
  23.             }
  24.         }
  25.         return res;
  26.     }
  27. }

226.给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。

示例 1：

输入：root = [4,2,7,1,3,6,9]
输出：[4,7,2,9,6,3,1]
示例 2：

输入：root = [2,1,3]
输出：[2,3,1]
示例 3：

输入：root = []
输出：[]
 

提示：

树中节点数目范围在 [0, 100] 内
-100 <= Node.val <= 100

递归就完事了

  1. class Solution {
  2.     public TreeNode invertTree(TreeNode root) {
  3.         if(root==null){
  4.             return null;
  5.         }
  6.         TreeNode temp1=invertTree(root.left);
  7.         TreeNode temp2=invertTree(root.right);
  8.         root.left=temp2;
  9.         root.right=temp1;
  10.         return root;
  11.     }
  12. }

 想想迭代怎么做。

  1. class Solution {
  2. 	public TreeNode invertTree(TreeNode root) {
  3. 		//递归终止条件
  4. 		if(root == null) {
  5. 			return null;
  6. 		}
  7.      Stack<TreeNode> stack = new Stack<>();
  8.       stack.push(root);
  9.       while(!stack.isEmpty()) {
  10.         //当前节点出栈
  11.         TreeNode node = stack.pop();
  12.         //将当前节点的左右子树交换
  13. 		TreeNode tmp = node.right;
  14. 		node.right = node.left;
  15. 		node.left = tmp;
  16.         //右子树入栈
  17.         if(node.right != null) {
  18.           stack.push(node.right);
  19.         }
  20.         //左子树入栈
  21.         if(node.left != null) {
  22.           stack.push(node.left);
  23.         }
  24.       }
  25.       return root;
  26. 	}
  27. }

96.给你一个整数 n ，求恰由 n 个节点组成且节点值从 1 到 n 互不相同的 二叉搜索树 有多少种？返回满足题意的二叉搜索树的种数。

示例 1：


输入：n = 3
输出：5
示例 2：

输入：n = 1
输出：1
 

提示：

1 <= n <= 19

 1.动态规划

  1. class Solution {
  2.     public int numTrees(int n) {
  3.         int[] G=new int[n+1];
  4.         G[0]=1;
  5.         G[1]=1;
  6.         for(int i=2;i<=n;i++){
  7.             for(int j=1;j<=i;j++){
  8.                 G[i]+=G[j-1]*G[i-j];
  9.             }
  10.         }
  11.         return G[n];
  12.     }
  13. }

2.数学公式法

  1. class Solution {
  2.     public int numTrees(int n) {
  3.         // 提示：我们在这里需要用 long 类型防止计算过程中的溢出
  4.         long C = 1;
  5.         for (int i = 0; i < n; ++i) {
  6.             C = C * 2 * (2 * i + 1) / (i + 2);
  7.         }
  8.         return (int) C;
  9.     }
  10. }

101.给你一个二叉树的根节点 root ， 检查它是否轴对称。

示例 1：


输入：root = [1,2,2,3,4,4,3]
输出：true
示例 2：


输入：root = [1,2,2,null,3,null,3]
输出：false
 

提示：

树中节点数目在范围 [1, 1000] 内
-100 <= Node.val <= 100
 

进阶：你可以运用递归和迭代两种方法解决这个问题吗？

1.递归 -一开始就想到这个方法了，甚至想到了用两个根节点，但是把问题想复杂了，老是去判断子节点，应该直接判断根节点。

  1. class Solution {
  2.     public boolean isSymmetric(TreeNode root) {
  3.         return check(root,root);
  4.     }
  5.     public boolean check(TreeNode p,TreeNode q){
  6.         if(p==null&&q==null){
  7.             return true;
  8.         }
  9.         if(p==null||q==null){
  10.             return false;
  11.         }
  12.         return (p.val==q.val)&&check(p.left,q.right)&&check(p.right,q.left);
  13.     }
  14. }

2.迭代-使用到队列和两个方法，offer和poll方法，其作用类似于add和remove，但是不会抛出异常，只会返回false和null。

  1. class Solution {
  2.     public boolean isSymmetric(TreeNode root) {
  3.         return check(root,root);
  4.     }
  5.     public boolean check(TreeNode p,TreeNode q){
  6.         Queue<TreeNode> queue=new LinkedList<>();
  7.         queue.offer(p);
  8.         queue.offer(q);
  9.         while(!queue.isEmpty()){
  10.             TreeNode temp1=queue.poll();
  11.             TreeNode temp2=queue.poll();
  12.             if(temp1==null&&temp2==null){
  13.                 continue;
  14.             }
  15.             if(temp1==null||temp2==null){
  16.                 return false;
  17.             }
  18.             if(temp1.val!=temp2.val){
  19.                 return false;
  20.             }
  21.             queue.offer(temp1.left);
  22.             queue.offer(temp2.right);
  23.             queue.offer(temp1.right);
  24.             queue.offer(temp2.left);
  25.             
  26.         }
  27.         return true;
  28.     }
  29. }

48.给定一个 n × n 的二维矩阵 matrix 表示一个图像。请你将图像顺时针旋转 90 度。

你必须在 原地 旋转图像，这意味着你需要直接修改输入的二维矩阵。请不要 使用另一个矩阵来旋转图像。

示例 1：


输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
输出：[[7,4,1],[8,5,2],[9,6,3]]
示例 2：


输入：matrix = [[5,1,9,11],[2,4,8,10],[13,3,6,7],[15,14,12,16]]
输出：[[15,13,2,5],[14,3,4,1],[12,6,8,9],[16,7,10,11]]
 

提示：

n == matrix.length == matrix[i].length
1 <= n <= 20
-1000 <= matrix[i][j] <= 1000

1.先上下翻，再对角线翻。

  1. class Solution {
  2.     public void rotate(int[][] matrix) {
  3.         int x=matrix.length;
  4.         int temp;
  5.         //左右翻一次
  6.         for(int i=0;i<(x/2);i++){
  7.             for(int j=0;j<x;j++){
  8.                 temp=matrix[i][j];
  9.                 matrix[i][j]=matrix[x-1-i][j];
  10.                 matrix[x-1-i][j]=temp;
  11.             }
  12.         }
  13.         //再沿对角线来一次
  14.         for(int i=0;i<x;i++){
  15.             for(int j=0;j<i;j++){
  16.                 temp=matrix[i][j];
  17.                 matrix[i][j]=matrix[j][i];
  18.                 matrix[j][i]=temp;
  19.             }
  20.         }
  21.     }
  22. }

2.使用辅助数组-平平无奇

  1. class Solution {
  2.     public void rotate(int[][] matrix) {
  3.         int n = matrix.length;
  4.         int[][] matrix_new = new int[n][n];
  5.         for (int i = 0; i < n; ++i) {
  6.             for (int j = 0; j < n; ++j) {
  7.                 matrix_new[j][n - i - 1] = matrix[i][j];
  8.             }
  9.         }
  10.         for (int i = 0; i < n; ++i) {
  11.             for (int j = 0; j < n; ++j) {
  12.                 matrix[i][j] = matrix_new[i][j];
  13.             }
  14.         }
  15.     }
  16. }

3.原地翻转-一直转反了方向emo了

  1. class Solution {
  2.     public void rotate(int[][] matrix) {
  3.         int n = matrix.length;
  4.         for (int i = 0; i < n / 2; ++i) {
  5.             for (int j = 0; j < (n + 1) / 2; ++j) {
  6.                 int temp = matrix[i][j];
  7.                 matrix[i][j] = matrix[n - j - 1][i];
  8.                 matrix[n - j - 1][i] = matrix[n - i - 1][n - j - 1];
  9.                 matrix[n - i - 1][n - j - 1] = matrix[j][n - i - 1];
  10.                 matrix[j][n - i - 1] = temp;
  11.             }
  12.         }
  13.     }
  14. }

46.给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。

示例 1：

输入：nums = [1,2,3]
输出：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]
示例 2：

输入：nums = [0,1]
输出：[[0,1],[1,0]]
示例 3：

输入：nums = [1]
输出：[[1]]
 

提示：

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整数 互不相同

和那个子集很像，于是自己尝试写了一下，差点忘记add这个坏东西。

  1. class Solution {
  2.     public List<List<Integer>> permute(int[] nums) {
  3.         //回溯
  4.         List<List<Integer>> res=new ArrayList<>();
  5.         List<Integer> temp=new ArrayList<>();
  6.         //找到nums长度-1的数组的结果，假设一共k个数组
  7.         //然后把nums[i]插到k个数组的所有位置，一共nums.length个位置
  8.         //每次用temp存储插好的数组，插一次就往res里加一次
  9.         //返回最终结果
  10.         if(nums.length==1){
  11.             temp.add(nums[0]);
  12.             res.add(temp);
  13.             return res;
  14.         }
  15.         int[] pre=new int[nums.length-1];
  16.         for(int i=0;i<pre.length;i++){
  17.             pre[i]=nums[i];
  18.         }
  19.         List<List<Integer>> preRes=permute(pre);
  20.         for(int i=0;i<preRes.size();i++){
  21.             for(int j=0;j<nums.length;j++){
  22.                 temp=preRes.get(i);
  23.                 List<Integer> temp1=new ArrayList<>(temp);
  24.                 temp1.add(j,nums[nums.length-1]);
  25.                 res.add(temp1);
  26.              }
  27.         }
  28.          return res;    
  29.     }
  30. }

 虽然一会忘记add，一会忘记写递归结束条件，一会写错条件，但最后靠自己写出来，挺高兴，说明子集那个题目也学会了。

104.给定一个二叉树，找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。

说明: 叶子节点是指没有子节点的节点。

示例：
给定二叉树 [3,9,20,null,null,15,7]，

    3
   / \
  9  20
    /  \
   15   7
返回它的最大深度 3 。

一个是递归，看左右子树的深度最大值再加1；一个是广度优先搜索，感觉和那个轴对称类似，使用队列来存进来的节点。

1.递归

  1. class Solution {
  2.     public int maxDepth(TreeNode root) {
  3.         if(root==null){
  4.             return 0;
  5.         }else{
  6.             int leftDepth=maxDepth(root.left);
  7.             int rightDepth=maxDepth(root.right);
  8.             return Math.max(leftDepth,rightDepth)+1;
  9.         }
  10.     }
  11. }

2.广度优先搜索树

差点new queue去了，记得底层用链表。

  1. class Solution {
  2.     public int maxDepth(TreeNode root) {
  3.         Queue<TreeNode> queue=new LinkedList<>();
  4.         if(root==null){
  5.             return 0;
  6.         }
  7.         queue.offer(root);
  8.         int num=0;
  9.         //只要队列不为空，就说明没处理完所有节点
  10.         while(!queue.isEmpty()){
  11.             int size=queue.size();
  12.             //类似递归的思想，来遍历树
  13.             while(size>0){
  14.                 TreeNode temp=queue.poll();
  15.                 if(temp.left!=null){
  16.                     queue.offer(temp.left);
  17.                 }
  18.                 if(temp.right!=null){
  19.                     queue.offer(temp.right);
  20.                 }
  21.                 size--;
  22.             }
  23.             num++;
  24.         }
  25.         return num;
  26.     }
  27. }

102.给你二叉树的根节点 root ，返回其节点值的 层序遍历 。 （即逐层地，从左到右访问所有节点）。

示例 1：


输入：root = [3,9,20,null,null,15,7]
输出：[[3],[9,20],[15,7]]
示例 2：

输入：root = [1]
输出：[[1]]
示例 3：

输入：root = []
输出：[]
 

提示：

树中节点数目在范围 [0, 2000] 内
-1000 <= Node.val <= 1000

感觉类似前几个题目，用队列存储广度优先搜索。

  1. class Solution {
  2.     public List<List<Integer>> levelOrder(TreeNode root) {
  3.         List<List<Integer>> res=new ArrayList<>();
  4.         List<Integer> temp=new ArrayList<>();
  5.         TreeNode curr=root;
  6.         if(curr==null){
  7.             return res;
  8.         }
  9.         //根节点那一层
  10.         temp.add(curr.val);
  11.         List<Integer> temp1=new ArrayList<>(temp);
  12.         res.add(temp1);
  13.         //下一层
  14.         //还得是队列
  15.         Queue<TreeNode> q=new LinkedList<>();
  16.         q.offer(root);
  17.         while(!q.isEmpty()){
  18.             int size=q.size();
  19.             List<Integer> l=new ArrayList<>();
  20.             while(size>0){
  21.                 TreeNode treeNode=q.poll();
  22.                 if(treeNode.left!=null){
  23.                     q.offer(treeNode.left);
  24.                     l.add(treeNode.left.val);
  25.                 }
  26.                 if(treeNode.right!=null){
  27.                     q.offer(treeNode.right);
  28.                     l.add(treeNode.right.val);
  29.                 }
  30.                 size--;
  31.             }
  32.             //这一层遍历完了
  33.             List<Integer> r=new ArrayList<>(l);
  34.             if(r.size()>0){
  35.                 res.add(r);
  36.             }
  37.         }
  38.         return res;
  39.     }
  40. }

答案也是广度优先搜索，不过略有不同。

75.给定一个包含红色、白色和蓝色、共 n 个元素的数组 nums ，原地对它们进行排序，使得相同颜色的元素相邻，并按照红色、白色、蓝色顺序排列。

我们使用整数 0、 1 和 2 分别表示红色、白色和蓝色。

必须在不使用库的sort函数的情况下解决这个问题。

示例 1：

输入：nums = [2,0,2,1,1,0]
输出：[0,0,1,1,2,2]
示例 2：

输入：nums = [2,0,1]
输出：[0,1,2]
 

提示：

n == nums.length
1 <= n <= 300
nums[i] 为 0、1 或 2
 

进阶：

你可以不使用代码库中的排序函数来解决这道题吗？
你能想出一个仅使用常数空间的一趟扫描算法吗？

本质上是要写一个含重复数字的排序算法，要求空间复杂度为O(1)，时间复杂度为O（n）。

1.双指针搞一哈-应该有两种解法

  1. class Solution {
  2.     public void sortColors(int[] nums) {
  3.         //双指针，指向头部
  4.         //遍历一次,如果遇到0，一起移动，遇到1，只有right移动
  5.         int left=0;
  6.         int right=0;
  7.         for(int i=0;i<nums.length;i++){
  8.             if(nums[i]==0){
  9.                 int temp=nums[i];
  10.                 nums[i]=nums[left];
  11.                 nums[left]=temp;
  12.                 //
  13.                 if(left<right){
  14.                     int temp1=nums[i];
  15.                     nums[i]=nums[right];
  16.                     nums[right]=temp1;
  17.                 }
  18.                 left++;
  19.                 right++;
  20.             }else if(nums[i]==1){
  21.                 int temp=nums[i];
  22.                 nums[i]=nums[right];
  23.                 nums[right]=temp;
  24.                 right++;
  25.             }
  26.         }
  27.     }
  28. }

 如果left和right之间有1了，那么这个0就和1交换了，所以需要在换一次。如果left和right一直相等，那就随便换。

  1. class Solution {
  2.     public void sortColors(int[] nums) {
  3.         //双指针，一个指向头部，一个指向尾部
  4.         //0放前面，2放后面
  5.         int left=0;
  6.         int right=nums.length-1;
  7.         for(int i=0;i<nums.length;i++){
  8.             //如果交换的也是个2,且i没有大过right，不然会多交换
  9.             while(i<right&&nums[i]==2){
  10.                 int temp=nums[i];
  11.                 nums[i]=nums[right];
  12.                 nums[right]=temp;
  13.                 right--;
  14.             }
  15.             if(nums[i]==0){
  16.                 int temp=nums[i];
  17.                 nums[i]=nums[left];
  18.                 nums[left]=temp;
  19.                 left++;
  20.             }
  21.         }
  22.     }
  23. }

2.单指针遍历两遍，第一遍把所有0放前面，第二遍把所有1放0后面。

  1. class Solution {
  2.     public void sortColors(int[] nums) {
  3.         int left=0;
  4.         //单指针遍历两次
  5.         //第一次先将所有的0放到数组前面
  6.         //第二次将所有的1放在0后面
  7.         for(int i=0;i<nums.length;i++){
  8.             if(nums[i]==0){
  9.                 int temp=nums[i];
  10.                 nums[i]=nums[left];
  11.                 nums[left]=temp;
  12.                 left++;
  13.             }
  14.         }
  15.          //此时left指向最后一个0的下一个
  16.                for(int i=left;i<nums.length;i++){
  17.                 if(nums[i]==1){
  18.                     int temp=nums[i];
  19.                     nums[i]=nums[left];
  20.                     nums[left]=temp;
  21.                     left++;
  22.                 }
  23.             }
  24.     }
  25. }

 

声明：本文内容由网友自发贡献，转载请注明出处：【wpsshop】
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号