226. 翻转二叉树【简单】
226.翻转二叉树
简单
1.6K
相关企业
给你一棵二叉树的根节点 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
C语言
/** * Definition for a binary tree node. * struct TreeNode { * int val; * struct TreeNode *left; * struct TreeNode *right; * }; */ struct TreeNode* invertTree(struct TreeNode* root) { if (root == NULL) { return NULL; } struct TreeNode* left = invertTree(root->left); struct TreeNode* right = invertTree(root->right); root->left = right; root->right = 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 invertTree(TreeNode root) { if (root==null){ return null; } TreeNode tmp=root.left; root.left=root.right; root.right=tmp; invertTree(root.left); invertTree(root.right); return root; } }
234. 回文链表【简单】
- 回文链表
简单
1.7K
相关企业
给你一个单链表的头节点 head ，请你判断该链表是否为回文链表。如果是，返回 true ；否则，返回 false 。
示例 1： 输入：head = [1,2,2,1] 输出：true 示例 2： 输入：head = [1,2] 输出：false
提示：
链表中节点数目在范围[1, 105] 内
0 <= Node.val <= 9
进阶：你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
转为List 左右指针
/** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode() {} * ListNode(int val) { this.val = val; } * ListNode(int val, ListNode next) { this.val = val; this.next = next; } * } */ //转换为数组 class Solution { public boolean isPalindrome(ListNode head) { List<Integer> list=new ArrayList(); while(head!=null){ list.add(head.val); head=head.next; } int left=0; int right=list.size()-1; while(left<=right){ if(list.get(left)!=list.get(right)){ return false; } left++; right--; } return true; } }
236. 二叉树的最近公共祖先【中等】
二叉树的最近公共祖先
中等
2.3K
相关企业
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
百度百科中最近公共祖先的定义为：“对于有根树 T 的两个节点 p、q，最近公共祖先表示为一个节点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”
示例 1： 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1 输出：3 解释：节点 5 和节点 1 的最近公共祖先是节点 3 。 示例 2： 输入：root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4 输出：5 解释：节点 5 和节点 4 的最近公共祖先是节点 5 。因为根据定义最近公共祖先节点可以为节点本身。 示例 3： 输入：root = [1,2], p = 1, q = 2 输出：1
提示：
树中节点数目在范围 [2, 105] 内。
-109 <= Node.val <= 109
所有 Node.val 互不相同 。
p != q
p 和 q 均存在于给定的二叉树中。
参考
dfs
/** * Definition for a binary tree node. * public class TreeNode { * int val; * TreeNode left; * TreeNode right; * TreeNode(int x) { val = x; } * } */ class Solution { private TreeNode ans; public Solution(){ this.ans=null; } //递归 public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) { this.dfs(root,p,q); return this.ans; } public boolean dfs(TreeNode root,TreeNode p, TreeNode q){ if(root==null){ return false; } boolean lson=dfs(root.left,p,q); boolean rson=dfs(root.right,p,q); if((lson&&rson)||((root.val==p.val||root.val==q.val)&&(lson||rson))){ ans=root; } return lson||rson||(root.val == p.val || root.val == q.val); } }
238. 除自身以外数组的乘积【中等】
238.除自身以外数组的乘积
中等
1.5K
相关企业
给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。
请不要使用除法，且在 O(n) 时间复杂度内完成此题。
示例 1: 输入: nums = [1,2,3,4] 输出: [24,12,8,6] 示例 2: 输入: nums = [-1,1,0,-3,3] 输出: [0,0,9,0,0]
提示：
2 <= nums.length <= 105
-30 <= nums[i] <= 30
保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内
进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组不被视为额外空间。）
自己
判断数组中有几个0
class Solution { public int[] productExceptSelf(int[] nums) { int [] answer=new int[nums.length]; int product=1; int zeroCount=0; for(int i=0;i<nums.length;i++){ if(nums[i]==0){ zeroCount++; }else{ product*=nums[i]; } } for(int i=0;i<nums.length;i++){ if(zeroCount>0){ if(nums[i]!=0){ answer[i]=0; }else{ if(zeroCount>1){ answer[i]=0; }else{ answer[i]=product; } } }else{ answer[i]=product/nums[i]; } } return answer; } }
参考
class Solution { public int[] productExceptSelf(int[] nums) { int[] L=new int[nums.length]; int[] R=new int[nums.length]; L[0]=1; R[nums.length-1]=1; for(int i=0,j=nums.length-1;i<nums.length&&j>=0;i++,j--){ if(i!=0){ L[i]=L[i-1]*nums[i-1]; } if(j!=nums.length-1){ R[j]=R[j+1]*nums[j+1]; } } int[] res=new int[nums.length]; for(int i=0;i<nums.length;i++){ res[i]=L[i]*R[i]; } return res; } }
239. 滑动窗口最大值【困难】
239.滑动窗口最大值
提示
困难
2.4K
相关企业
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
示例 1： 输入：nums = [1,3,-1,-3,5,3,6,7], k = 3 输出：[3,3,5,5,6,7] 解释： 滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7 示例 2： 输入：nums = [1], k = 1 输出：[1]
提示：
1 <= nums.length <= 105
-104 <= nums[i] <= 104
1 <= k <= nums.length
参考
堆（优先队列）
class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int n=nums.length; //优先队列 存储[元素和下标] PriorityQueue<int []>pq=new PriorityQueue<int []>(new Comparator<int []>(){ public int compare(int[] pair1,int[] pair2){ return pair1[0]!=pair2[0]?pair2[0]-pair1[0]:pair2[1]-pair1[1]; } }); //初始优先队列 初始窗口的值 for(int i=0;i<k;i++){ pq.offer(new int[]{nums[i],i}); } int[] ans=new int[n-k+1]; ans[0]=pq.peek()[0]; for(int i=k;i<n;i++){ pq.offer(new int[]{nums[i],i});//加入 while(pq.peek()[1]<=i-k){//出现在滑动窗口的最左侧 pq.poll();//弹出 } ans[i-k+1]=pq.peek()[0]; } return ans; } }
参考
单调队列
class Solution { public int[] maxSlidingWindow(int[] nums, int k) { int n=nums.length; Deque<Integer> deque=new LinkedList<Integer>(); //初始化 初始窗口 for(int i=0;i<k;i++){ //当前遍历的值大于队尾，逐出 while(!deque.isEmpty()&&nums[i]>=nums[deque.peekLast()]){ deque.pollLast();//直到递增 } //加入目前递减队列 deque.offerLast(i); } int[] ans=new int[n-k+1]; ans[0]=nums[deque.peekFirst()];//初始窗口的最大值 for(int i=k;i<n;i++){ //当前遍历的值大于队尾，逐出 while(!deque.isEmpty()&&nums[i]>=nums[deque.peekLast()]){ deque.pollLast();//直到递增 } //加入目前递减队列 deque.offerLast(i); //最大值到了窗口的最左边了 while(deque.peekFirst()<=i-k){ deque.pollFirst(); } ans[i-k+1]=nums[deque.peekFirst()]; } return ans; } }
