另类加法，走方格的方案数,最近公共祖先-白红宇

另类加法，走方格的方案数,最近公共祖先

阅读量：589 次

发布时间：2019-03-11

本文共 1703 字，大约阅读时间需要 5 分钟。


   
技术问题解答
   
    
   
    题目一：另类加法
    
   
    题目：给定两个整数A和B，编写一个函数返回A+B的值，但不得使用+或其他算术运算符。
    
   
    解题思路：
    
   
    1. 二进制位相异或的结果就是两个数对应位相加的结果，不考虑进位。
    
   
    2. 二进制与后左移一位的结果，就是两个数相加进位后的结果。
    
   
    两个数相加，如果不考虑进位，那么这两个数异或的值就是这两个数的和。
    
   
    import java.util.*;public class UnusualAdd {// 判断B是否为0，若为0则直接返回A        public int addAB(int A, int B) {            if(B==0){                return A;            }            int sum=0;            int carry=0;            while(B!=0){                sum=A^B;                carry=(A&B)<<1;                A=sum;                B=carry;            }            return A;        }
    
   
        题目二：走方格的方案数
    
   
    题目：
    
   
    请计算n*m的棋盘格子（n为横向的格子数，m为竖向的格子数）沿着各自边缘线从左上角走到右下角，总共有多少种走法，要求不能走回头路，即：只能往右和往下走，不能往左和往上走。
    
   
    import java.util.*;public class Main{// 从标准输入读取m和n值        public static void main(String[] args){            Scanner scan=new Scanner(System.in);            while(scan.hasNext()){                int m=scan.nextInt();                int n=scan.nextInt();                System.out.println(med(m,n));            }        }        public static int med(int m,int n){            if((n==1&&m>=1) || (m==1&&n>=1)){                return m+n;            }            return med(m-1,n) + med(m,n-1);        }
    
   
        题目三：最近公共祖先
    
   
    题目：
    
   
    将一棵无穷大的满二叉树的结点按根结点一层一层地从左往右编号，根结点编号为1。现给定a，b为两个结点。设计一个算法，返回a、b最近的公共祖先的编号。注意其祖先也可能是结点本身。
    
   
    import java.util.*;public class LCA {// 利用二进制位相减法求最短公共祖先        public int getLCA(int a, int b){            while(a!=b){                if(a>b){                    a=a/2;                }else{                    b=b/2;                }            }            return a;        }