字节跳动算法⾯试试题汇总2020 1，树的最⼩深度
树的深度
树的深度描述的树从根到当前节点的层级信息。
求数的最⼩深度
解法：遍历所有的层级信息，最⼩的。即出来当前节点为null，说明即⽗节点的深度较⼩。
public static int minDepth(TreeNode root){
if (root==null){
六一串词return 0;
}
return Math.min(minDepth(root.left)+1,minDepth(root.right)+1);
}
求树的最⼤深度
解法：遍历所有的层级信息，最⼤的。
public static int MaxDepth(TreeNode root) {
if (root == null) {
return 0;
}
return 1+Math.max(MaxDepth(root.left),MaxDepth(root.right));
}
有关桥的对联2，两个树节点的公共祖先——有⽗节点，链表相交
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root==null){
皇子皮肤return null;
}
if (root.val==p.val||root.val==q.val) return root;
TreeNode findleft=lowestCommonAncestor(root.left,p,q);
TreeNode findright=lowestCommonAncestor(root.right,p,q);
if (findleft !=null&&findright!=null) return root;
else if (findleft==null) return findright;
else return findleft;
}
}
3，利⽤不均匀硬币产⽣等概率
1，本来硬币朝上朝下的概率可以认为是55开，但是现在我们这个硬币朝上和朝下的概率分别是0.4和0.6，那么要怎么通过抛硬币实现均匀概率呢？
其实只需要算排列组合的概率即可：
依次抛两枚硬币，两次都是正⾯朝上：0.4^2=0.16
第⼀枚朝上，第⼆枚朝下：0.4*0.6=0.24
第⼀枚朝下，第⼆枚朝上：0.6*0.4=0.24
两枚都朝下：0.6^2=0.36
所以我们只需要⽐较⼀次丢两枚硬币出现朝上朝下和朝下朝上的概率即可，其余结果则重新抛
2,rand_m⽣成rand_n
归纳总结：将这个问题进⼀步抽象，已知random_m()随机数⽣成器的范围是[0, m） 求random_n()⽣成[0, n）范围的函数，m < n && n <= m *m。
设t为n的最⼤倍数，且满⾜t<m*m，即 t = ((m*m)/n)*n;
int Rand_n()
{
室内净化空气植物int x;
do
{
t = ((m * m) / n) * n;
x = Rand_m() * m + Rand_m ();
}
while (x >= t);
return x % n;
}
4，给你⼀个字符串，需要输出它们组成的下⼀个⽐这个数⼤的整数，⽐如1234需要输出1243，要是输⼊1243则需要输出1324.
5，只⽤加减乘相等基本运算实现正整数的开⽅（⼆分）
import java.math.BigDecimal;
public class Sqrt {
private static final double PRECISION = 6;
public static double sqrt(double num) throws RuntimeException{ if(num < 0){
throw new RuntimeException("num should bigger than 0!");
}
if(num == 0 || num == 1){
return num;
}
return sqrt0(0, num, num);
}
private static double sqrt0(double low, double high, double num){ double mid = (low + high) / 2;
BigDecimal bd = new BigDecimal(mid);
if(bd.precision() >= PRECISION){
return mid;非传统安全包括哪些内容
}
if((mid * mid) == num){
return mid;
}else if((mid * mid) < num){
return sqrt0(mid, high, num);
锂电池汽车}else {
return sqrt0(low, mid, num);
}
}
public static void main(String[] args) {
System.out.println(sqrt(2));
}
}
版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。
发表评论