1、构建乘积数组
1.1 题目描述：
给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B 中的元素 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。
1.2 题解
1.2.1
根据表格的主对角线（全为 11 ），可将表格分为 上三角 和 下三角 两部分。分别迭代计算下三角和上三角两部分的乘积，即可 不使用除法 就获得结果
public int[] constructArr(int[] a
) {
if (a
.length
==0)return new int[0];
int[] res
=new int[a
.length
];
res
[0]=1;
for(int i
=1;i
<a
.length
;i
++){
res
[i
]=res
[i
-1]*a
[i
-1];
}
int temp
=1;
for(int j
=a
.length
-2;j
>=0;j
--){
temp
*=a
[j
+1];
res
[j
]*=temp
;
}
return res
;
}
2、把字符串转换成整数
2.1 题目描述：
写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。 首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。 当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。 该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。 注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。 在任何情况下，若函数不能进行有效的转换时，请返回 0。
2.2 题解
2.2.1
public int strToInt(String str
) {
char[] c
= str
.trim().toCharArray();
if(c
.length
== 0) return 0;
int res
= 0, bndry
= Integer
.MAX_VALUE
/ 10;
int i
= 1, sign
= 1;
if(c
[0] == '-') sign
= -1;
else if(c
[0] != '+') i
= 0;
for(int j
= i
; j
< c
.length
; j
++) {
if(c
[j
] < '0' || c
[j
] > '9') break;
if(res
> bndry
|| res
== bndry
&& c
[j
] > '7') return sign
== 1 ? Integer
.MAX_VALUE
: Integer
.MIN_VALUE
;
res
= res
* 10 + (c
[j
] - '0');
}
return sign
* res
;
}
3、二叉搜索树的最近公共祖先
3.1 题目描述：
给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。
3.2 题解
3.2.1
public TreeNode
lowestCommonAncestor(TreeNode root
, TreeNode p
, TreeNode q
) {
while(root
!= null
) {
if(root
.val
< p
.val
&& root
.val
< q
.val
)
root
= root
.right
;
else if(root
.val
> p
.val
&& root
.val
> q
.val
)
root
= root
.left
;
else break;
}
return root
;
}
4、二叉树的最近公共祖先
4.1 题目描述：
给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。
4.2 题解
4.2.1
递归解析： 终止条件： 1.当越过叶节点，则直接返回 null ； 2.当 root 等于 p, q ，则直接返回 root；递推工作： 1. 开启递归左子节点，返回值记为 left ； 2.开启递归右子节点，返回值记为 right ；返回值： 根据 left 和 right ，可展开为四种情况； 1.当 left 和 right 同时为空 ：说明 root 的左 / 右子树中都不包含 p,q，返回 null ； 2.当 left 和 right同时不为空 ：说明 p, q 分列在 root 的 异侧 （分别在 左 / 右子树），因此 root 为最近公共祖先，返回 root； 3.当 left为空 ，right 不为空 ：p,q 都不在 root的左子树中，直接返回 right 。 具体可分为两种情况： 1). p,q 其中一个在 root 的 右子树 中，此时 right 指向 p（假设为 p ）； 2)p,q 两节点都在 root的 右子树 中，此时的 right 指向 最近公共祖先节点 ； 4.当 left不为空 ， rightright 为空 ：与情况 3. 同理；
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
&& right
== null
) return null
;
if(left
== null
) return right
;
if(right
== null
) return left
;
return root
;
}
