04树与图
难度中等65
节点间通路。给定有向图，设计一个算法，找出两个节点之间是否存在一条路径。
递归, 从target反向寻找路径,
注意点 :
-
这个方法无法解决自环的问题:
比如:
findWhetherExistsPath(6, new int[][]{{1,2},{2,3},{3,4},{4,5},{4,1}},5,1) 自环
但是题目给的数据没有涉及到自环的,
解决自环问题:
1
2
3
4
5
6
7
8
9
10
11
12
13
| class Solution {
public boolean findWhetherExistsPath(int n, int[][] graph, int start, int target) {
if(start==target) return true;
boolean res=false;
for(int[] arr:graph){
if(arr[1]==target){
res= findWhetherExistsPath(n,graph,start,arr[0]);
}
if(res) return res;
}
return res;
}
}
|
解决自环问题:
DFS
难度简单135
给定一个有序整数数组，元素各不相同且按升序排列，编写一个算法，创建一棵高度最小的二叉搜索树。
因为题目给的是一个升序数组，需要构建二叉搜索树，
当构造二叉搜索树的左右平衡时深度是最小。
如果想要左右平衡可以让根节点是排序数组的中点，这样左边有x个右边也约有x个，大致保持一致。
构造树一般采用的是前序遍历，
因为先构造中间节点，然后递归构造左子树和右子树。先要找到数组中中间值和对应的下标，
中间值构造根节点，下标用来下一步分割数组。
中间值所在的下标左区间 构造左子树,中间值所在的下标右区间 构造右子树。
步骤:
-
递归截止条件:
-
left>right
-
遍历数组 : left -> right , 找到数组的中间值以及对应的下标,
mid= left+ (right-left)/2
-
然后创建根节点 new TreeNode(nums[mid])
-
接着递归左右子树:
root.left=process(left,mid,nums)root.left=process(mid+1,right,nums)
-
最后返回根节点 return root
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
class Solution {
public TreeNode sortedArrayToBST(int[] nums) {
return process(0,nums.length,nums);
}
TreeNode process(int left,int right,int[]nums){
if (left>=right) return null;
int mid=left+(right-left)/2;
TreeNode root=new TreeNode(nums[mid]);
root.left=process(left,mid,nums);
root.right=process(mid+1,right,nums);
return root;
}
}
|
难度中等78
给定一棵二叉树，设计一个算法，创建含有某一深度上所有节点的链表（比如，若一棵树的深度为 D，则会创建出 D 个链表）。返回一个包含所有深度的链表的数组。
层序遍历+ 链表构造
边遍历, 边new 链表节点
image-20220816233118771
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public ListNode[] listOfDepth(TreeNode tree) {
if(tree==null) return new ListNode[0];
Queue<TreeNode> queue=new LinkedList<>();
List<ListNode> list=new ArrayList<>();
ListNode head=new ListNode(Integer.MAX_VALUE);
queue.add(tree);
while(queue.size()!=0){
int size=queue.size();
ListNode cur=head;
for (int i = 0; i < size; i++) {
TreeNode tmp=queue.poll();
cur.next=new ListNode(tmp.val);
cur=cur.next;
if(tmp.left!=null)
queue.add(tmp.left);
if(tmp.right!=null)
queue.add(tmp.right);
}
list.add(head.next);
}
ListNode []res=new ListNode[list.size()];
for (int i = 0; i < res.length; i++) {
res[i]=list.get(i);
}
return res;
}
}
|
难度简单91
实现一个函数，检查二叉树是否平衡。在这个问题中，平衡树的定义如下：任意一个节点，其两棵子树的高度差不超过 1。
平衡二叉树的条件:
- 左右子树的都是平衡二叉树
- 左右子树最大深度相差不超过1
递归求解即可
image-20220816234444257
1
2
3
4
5
6
7
8
9
| class Solution {
public boolean isBalanced(TreeNode root) {
return root==null||(isBalanced(root.left)&&isBalanced(root.right)&&Math.abs(calDepth(root.left)-calDepth(root.right))<=1);
}
public int calDepth(TreeNode root){
if(root==null) return 0;
return Math.max(calDepth(root.left),calDepth(root.right))+1;
}
}
|
难度中等85
实现一个函数，检查一棵二叉树是否为二叉搜索树。
- 中序遍历二叉树, 如果是二叉搜索树, 那么得到的序列 一定是有序的
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
| 2ms
class Solution {
List<Integer> list=new ArrayList<>();
public boolean isValidBST(TreeNode root) {
inOrder(root);
for (int i = 0; i < list.size()-1; i++) {
if(list.get(i)>=list.get(i+1)){
return false;
}
}
return true;
}
public void inOrder(TreeNode root){
if(root==null) return ;
inOrder(root.left);
list.add(root.val);
inOrder(root.right);
}
}
|
写法一
注意灵活运用 二叉搜索树的特性以及 Integer 的特性 (包装类)
根据二叉搜索树的特性, 在递归调用左右子树的时候, 可以更改上下界
- 递归左子树时, 上下界为:
(low, val)
- 右子树 :
(val, high)
函数调用时的入口为: dfs(root,Integer.MIN_VALUE,Integer.MAX_VALUE)
- 但是有一个这样的样例 :
image-20220817143818261
所以还是定义为null
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
| class Solution {
public boolean isValidBST(TreeNode root) {
return dfs(root,null,null);
}
public boolean dfs(TreeNode root,Integer low,Integer high){
if(root==null) return true;
int val=root.val;
if(low!=null&&val<=low) {
return false;
}
if(high!=null&&val>=high){
return false;
}
return dfs(root.left,low,val)&&dfs(root.right,val,high);
}
}
|
写法二
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
|
class Solution {
public boolean isValidBST(TreeNode root) {
return helper(root, null, null);
}
public boolean helper(TreeNode node, Integer lower, Integer upper) {
if (node == null) {
return true;
}
int val = node.val;
if (lower != null && val <= lower) {
return false;
}
if (upper != null && val >= upper) {
return false;
}
if (!helper(node.right, val, upper)) {
return false;
}
if (!helper(node.left, lower, val)) {
return false;
}
return true;
}
}
|
难度中等203
设计一个算法，找出二叉搜索树中指定节点的“下一个”节点（也即中序后继）。
如果指定节点没有对应的“下一个”节点，则返回null。
由于本题的要求是寻找目标节点的中序遍历(左根右)的下一个节点,
因此对应的当前的节点的val与目标节点的val 有两种对应情况:
root.val<= p.val , 此时 p的下一个节点是在右子树上root.val > p.val , 此时 p的下一个节点是在左子树上
一直递归, 知道递归到叶子节点 ,返回
1
2
3
4
5
6
7
8
9
10
| class Solution {
public TreeNode inorderSuccessor(TreeNode root, TreeNode p) {
if(root==null) return null;
if(root.val<=p.val){
return inorderSuccessor(root.right,p);
}
TreeNode ans= inorderSuccessor(root.left,p);
return ans==null?root:ans;
}
}
|
难度中等81
设计并实现一个算法，找出二叉树中某两个节点的第一个共同祖先。不得将其他的节点存储在另外的数据结构中。注意：这不一定是二叉搜索树。
image-20220817160512405
题目对应的有三种情况:
-
两个节点分别位于根节点的左右子树中 :
left!=null && right!=null
此时直接return root 即可
-
两个节点都位于左子树
-
right=null
-
此时直接返回left
-
因为最终的返回结果是第一次的递归 , 当后面的所有的递归都结束, 回到第一层时 , 对应的root 也会逐层传递
image-20220817161123975例如下面的 7 , 4 他们的最近公共祖先 2 就会被逐级传递 最终, 回到第一层 ,然后返回 2
-
两个节点都位于右子树:
1
2
3
4
5
6
7
8
9
10
| class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null||root==p||root==q) return root;
TreeNode left=lowestCommonAncestor(root.left,p,q);
TreeNode right=lowestCommonAncestor(root.right,p,q);
if(left==null) return right;
if(right==null) return left;
return root;
}
}
|
难度中等66
检查子树。你有两棵非常大的二叉树：T1，有几万个节点；T2，有几万个节点。设计一个算法，判断 T2 是否为 T1 的子树。
如果 T1 有这么一个节点 n，其子树与 T2 一模一样，则 T2 为 T1 的子树，也就是说，从节点 n 处把树砍断，得到的树与 T2 完全相同。
简单解法
- 在较小、较简单的问题中，我们可以考虑对两棵树的遍历结果进行比较，该遍历结果通常用字符串表示。如果T2 是T1 的一棵子树，那么T2 的遍历结果应该是T1 的遍历结果的一个子串。
遍历方式的选择
中序遍历当然行不通。我们可以试试两棵二叉搜索树。二叉查找树的中序遍历结果总是
有序的。因此，即使两棵有着相同节点的二叉搜索树结构不同，其也总是有着相同的中序遍历
结果。
-
如果只是
简单的前序遍历
, 不同的两个树依然有可能是 相同的结果
- 但是如果吧
null 值也存储, 那么两个不同的树的前序遍历的结果是必然不会相同的
前序遍历 , 将null值记为 n , 将序列存储在字符串中, 最后调用contains() 返回即可
空间:O(m+n)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public boolean checkSubTree(TreeNode t1, TreeNode t2) {
StringBuilder s1=new StringBuilder("");
StringBuilder s2=new StringBuilder("");
dfs(t1,s1);
dfs(t2,s2);
return s1.toString().contains(s2.toString());
}
public void dfs(TreeNode root,StringBuilder s){
if(root==null){
s.append('n');
return;
}
s.append(root.val);
dfs(root.left,s);
dfs(root.right,s);
}
}
|
解法二:
先遍历大的树, 如果匹配到了与小树的根节点相同的值, 就调用treeMatch()
image-20220817163956815
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution {
TreeNode lessTree=null;
boolean res=false;
public boolean checkSubTree(TreeNode t1, TreeNode t2) {
lessTree=t2;
dfs(t1);
return res;
}
public void dfs(TreeNode root){
if(root==null) return;
if(root.val==lessTree.val){
res=treeMatch(root,lessTree);
}
dfs(root.left);
dfs(root.right);
}
public boolean treeMatch(TreeNode t1,TreeNode t2){
if(t1==null&&t2==null) return true;
if(t1==null||t2==null) return false;
return t1.val==t2.val&&treeMatch(t1.left,t2.left)&&treeMatch(t1.right,t2.right);
}
}
|
难度中等118
给定一棵二叉树，其中每个节点都含有一个整数数值(该值或正或负)。设计一个算法，打印节点数值总和等于某个给定值的所有路径的数量。注意，路径不一定非得从二叉树的根节点或叶节点开始或结束，但是其方向必须向下(只能从父节点指向子节点方向)。
一篇文章解决所有二叉树路径问题（问题分析+分类模板+题目剖析） - 求和路径 - 力扣（LeetCode）
法一:
DFS
- 可以从根节点开始 计算
- 可以从中间的节点开始计算
直接层序遍历, 暴力解法 ,
注意 : 一条路径, 可以出现多次目标值, (节点的val可以是负数) , 因此当 root.val == target时 ,不要返回, 继续计算!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| class Solution {
int ans=0;
public int pathSum(TreeNode root, int sum) {
if(root==null) return ans;
Queue<TreeNode> queue=new LinkedList<>();
queue.add(root);
while(queue.size()!=0){
int size=queue.size();
for (int i = 0; i < size; i++) {
TreeNode tmp=queue.poll();
dfs(tmp,sum);
if(tmp.left!=null) queue.add(tmp.left);
if(tmp.right!=null) queue.add(tmp.right);
}
}
return ans;
}
public void dfs(TreeNode root, int target){
if(root==null) return ;
if(root.val==target){
ans++;
}
dfs(root.left,target-root.val);
dfs(root.right,target-root.val);
}
}
class Solution {
public int pathSum(TreeNode root, int sum) {
if (root == null) {
return 0;
}
int ret = rootSum(root, sum);
ret += pathSum(root.left, sum);
ret += pathSum(root.right, sum);
return ret;
}
public int rootSum(TreeNode root, int sum) {
int ret = 0;
if (root == null) {
return 0;
}
int val = root.val;
if (val == sum) {
ret++;
}
ret += rootSum(root.left, sum - val);
ret += rootSum(root.right, sum - val);
return ret;
}
}
|
**法二 **
我们仔细思考一下，解法一中应该存在许多重复计算。我们定义节点的前缀和为：
我们利用先序遍历二叉树，记录下根节点 root 到当前节点 pp 的路径上除当前节点以外所有节点的前缀和，在已保存的路径前缀和中查找是否存在前缀和刚好等于当前节点到根节点的前缀和 curr减去 sum。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
| class Solution {
public int pathSum(TreeNode root, int sum) {
Map<Long, Integer> prefix = new HashMap<Long, Integer>();
prefix.put(0L, 1);
return dfs(root, prefix, 0, sum);
}
public int dfs(TreeNode root, Map<Long, Integer> prefix, long curr, int sum) {
if (root == null) {
return 0;
}
int ret = 0;
curr += root.val;
ret = prefix.getOrDefault(curr - sum, 0);
prefix.put(curr, prefix.getOrDefault(curr, 0) + 1);
ret += dfs(root.left, prefix, curr, sum);
ret += dfs(root.right, prefix, curr, sum);
prefix.put(curr, prefix.getOrDefault(curr, 0) - 1);
return ret;
}
}
|
05位运算
难度简单58
给定两个整型数字 N 与 M，以及表示比特位置的 i 与 j（i <= j，且从 0 位开始计算）。
编写一种方法，使 M 对应的二进制数字插入 N 对应的二进制数字的第 i ~ j 位区域，不足之处用 0 补齐。具体插入过程如图所示。
思路:
- 分段append , 最终
StringBuilder存储的是二进制形式的 结果, 倒序改成十进制即可
1
2
3
| for (int i1 = 0; i1 < chars.length; i1++) {
ans+=Math.pow(2,mic++)*(chars[i1]-'0');
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
| class Solution {
public int insertBits(int N, int M, int i, int j) {
StringBuilder res=new StringBuilder();
int idx=0;
while(idx<i){
res.append(N&1);
N>>=1;
idx++;
}
while(idx<=j){
res.append(M&1);
M>>=1;
N>>=1;
idx++;
}
while(N!=0){
res.append(N&1);
N>>=1;
idx++;
}
int ans=0;
int mic=0;
char[]chars=res.toString().toCharArray();
for (int i1 = 0; i1 < chars.length; i1++) {
ans+=Math.pow(2,mic++)*(chars[i1]-'0');
}
return ans;
}
}
|
难度中等40
二进制数转字符串。给定一个介于0和1之间的实数（如0.72），类型为double，打印它的二进制表达式。如果该数字无法精确地用32位以内的二进制表示，则打印“ERROR”。
小数转二进制:
文字描述该过程如下：
- 将该数字乘以2，取出整数部分作为二进制表示的第1位；
- 然后再将小数部分乘以2，将得到的整数部分作为二进制表示的第2位；
- 以此类推，直到小数部分为0。
- 特殊情况： 小数部分出现循环，无法停止，则用有限的二进制位无法准确表示一个小数，这也是在编程语言中表示小数会出现误差的原因
下面以 0.625 举例
0.625 -> 1 .25 sb.append((int)num) ; num -=1;0.25 -> 0.5 sb.append((int)num) ;0.5 -> 1 sb.append((int)num) ;return
不难发现, Num-=1 只有在 num >=1 的时候 才会执行,
因此可以将上面的表示翻译成下面的代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| class Solution {
public String printBin(double num) {
StringBuilder sb=new StringBuilder("");
int cnt=0;
while(num%1!=0){
if(cnt>=32) return "ERROR";
num*=2;
sb.append((int)num);
if(num>=1){
num-=1;
}
cnt++;
}
return "0."+sb.toString();
}
}
|
难度简单82
给定一个32位整数 num，你可以将一个数位从0变为1。请编写一个程序，找出你能够获得的最长的一串1的长度。
遍历数字的二进制位,
当两段1的中间只有一个 0 的时候
- 可以将每一个部分的1序列 与相邻的部分的1序列 看做是一个 , 此时的长度就是两段1 的长度 + 中间的那个0的长度(1)
previousLength+currentLength+1- 遍历维护
maxLength最后返回即可
在遍历的过程中，追踪当前 1 序列的长度和上一段 1 序列的长度。当发现一个比特位为 0 时，更新 previousLength 的值。
使用 num&2 ==0? 来判断num的下一个比特位是否为0
- 如果下一个比特位是 1，那么
previousLength 应被置为 currentLength 的值。
- 如果下一个比特位是 0，我们则不能合并这两个 1 序列。因此，将
previousLength 的值置为 0。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int reverseBits(int num) {
if(~num==0) return Integer.BYTES*8;
int currentLength=0,previousLength=0;
int maxLength=1;
while(num!=0){
if((num&1)==1){
currentLength++;
}else if((num&1)==0){
previousLength=(num&2)==0?0:currentLength;
currentLength=0;
}
maxLength=Math.max(previousLength+currentLength+1,maxLength);
num>>>=1;
}
return maxLength;
}
}
|
难度中等55
下一个数。给定一个正整数，找出与其二进制表达式中1的个数相同且大小最接近的那两个数（一个略大，一个略小）。
蛮力法
取较大的数字(getNext())
下面以 13948为例
image-20220819212250408
经过思考不难得出下面的结论:
- 若将某个 0 翻转成 1，就必须将某个 1 翻转为 0。
- 进行位翻转时，如果 0 变 1 的位处于 1 变 0 的位的左边，这个数字就会变大。
- 我们想让这个数变大，但又不致太大。因此，必须翻转最右边的 0，且它的右边必须还有个 1。
换句话说，我们要翻转最右边但非拖尾的 0。用上面的例子来说，拖尾 0 位于第 0 到第 1个位置。
因此，最右边但不是拖尾的 0 处在位置 7。我们把这个位置记作 p。
- 步骤(1)：翻转最右边、非拖尾的 0
image-20220819213552962
- 步骤(2)：将 p 右方的所有位清零
- 由步骤(1)可知，c0 = 2，c1 = 5，p = 7
image-20220819213623891
- 步骤(3)：回填 c1 - 1 个 1
image-20220819213648408
image-20220819213657712
取较小的数字(getPrev())
getPrev 的实现方法与 getNext 极为相似。
- 计算 c0 和 c1。注意 c1 是拖尾 1 的个数，而 c0 为紧邻拖尾 1 的左方一连串 0 的个数。
- 将最右边、非拖尾 1 变为 0，其位置为 p = c1 + c0。
- 将位 p 右边的所有位清零。
- 在紧邻位置 p 的右方，插入 c1 + 1 个 1。
注意，步骤(2)将位 p 清零，而步骤(3)将位 0 到位 p - 1 清零，我们可以将这两步合并
image-20220819222057969
代码实现如下:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
| class Solution {
public int[] findClosedNumbers(int num) {
int[] res = new int[2];
if (num <=0 || num>=Integer.MAX_VALUE) {
res[0] = -1;
res[1] = -1;
} else {
res[0] = getNextI(num);
res[1] = getPrevI(num);
}
return res;
}
public int getNextI(int n){
int c=n,c0=0,c1=0;
while(c!=0&&(c&1)==0){
c0++;
c>>=1;
}
while(c!=0&&(c&1)==1){
c1++;
c>>=1;
}
if (c0 + c1 == 31 || c0 +c1 ==0) {
return -1;
}
int p=c0+c1;
n|=1<<p;
n&=~((1<<p)-1);
n|=((1<<(c1-1))-1);
return n;
}
private int getPrevI(int n) {
int c=n,c1=0,c0=0;
while((c&1)==1){
c1++;
c>>=1;
}
if(c==0) return -1;
while((c&1)==0&&c!=0){
c0++;
c>>=1;
}
int p=c0+c1;
n&=((~0)<<(p+1));
n|=((1<<(c1+1))-1)<<(p-c1-1);
return n;
}
}
|
难度简单44
整数转换。编写一个函数，确定需要改变几个位才能将整数A转成整数B。
调整大小, 使得A 始终为较大的那个数字
遍历A, B 的二进制 , 如果遇到了不同的数位 就res++
当B ==0 之后
继续遍历A 的数位 , 如果A 的数位==1 res++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
| class Solution {
public int convertInteger(int A, int B) {
if(A>B){
A^=B;
B^=A;
A^=B;
}
int res=0;
while(B!=0){
if((A&1)!=(B&1)) res++;
A>>>=1;
B>>>=1;
}
while(A!=0){
if((A&1)==1) res++;
A>>>=1;
}
return res;
}
}
|
难度简单69
配对交换。编写程序，交换某个整数的奇数位和偶数位，尽量使用较少的指令（也就是说，位0与位1交换，位2与位3交换，以此类推）。
先操作奇数位，然后再操作偶数位。
有办法将数字 n 的奇数位左移或右移 1 位吗？
- 当然有。我们可以用 10101010（即 0xAA）作为掩码，提取奇数位，并将它们右移 1位，移到偶数位的位置。
- 对于偶数位，可以施以同样的操作。最后，将两次操作的结果合并成一个值。
- 这种做法共需 5 条指令
- 16进制5是0101 a是1010，分别进行与运算的话刚好取了奇数位和偶数位，再进行移位（也就是乘二除二），相加。
奇数位右移，偶数位左移，取或得结果。
0xaaaaaaaa = 10101010101010101010101010101010 (偶数位为1，奇数位为0）
0x55555555 = 01010101010101010101010101010101 (偶数位为0，奇数位为1）
十六进制的一位, 会被分解成二进制的四位
a=10 => 8+2 => 1010
5 = > 4+1=> 0101
下面以29为例
29: 11101 => 101110
&0xaaaaaaaa =>01000 >>>1 => 00100
&0x55555555 =>10101 << 1 => 101010
00100 | 101010 = > 101110
1
2
3
4
5
6
| class Solution {
public int exchangeBits(int x) {
return ( ((x&0xaaaaaaaa) >>>1)| ((x&0x55555555)<<1) );
}
}
|
