剑指offer-8

2020-07-06

剑指offer day8

65、不用加减乘除做加法

a^b相当于a和b无进位的求和，而a&b相当于求每位的进位数，当且仅当a都为1时才为1。

但这里注意，9&1为1，而不是我们想要的是10，即我们这里还要对其进行左移一位。

即这里公式为 a^b^((a&b)<<1)表示每次求无进位和+每次求的的进位数

class Solution{
  public int add(int a,int b){
    return b==0?a:add(a^b,(a&b)<<1);
  }
}

66、构建乘积数组 https://leetcode-cn.com/problems/gou-jian-cheng-ji-shu-zu-lcof/

本题由前缀积形成。即每一个位置当前的元素为他的前缀积*后缀积。

因此我们需要两次遍历，第一次遍历求的左边部分的乘积，第二次遍历求得第二次遍历的乘积

class Solution{
  	public int[] constructArr(int nums[]){
      int left=1,right=1;
       int res[]=new int[nums.length];
      for(int i=0;i<nums.length;i++){
        res[i]=left;
          left*=nums[i];
      }
      for(int j=nums.length-1;j>=0;j--){
          res[j]*=right;
        right*=nums[j];
      }
      return res;
    }
}

67、把字符串转换为整数 https://leetcode-cn.com/problems/ba-zi-fu-chuan-zhuan-huan-cheng-zheng-shu-lcof/

常规的转换会很简单，但是这里我们要考虑前面的空格，正负号，以及数据溢出等情况。

class Solution {
    public int strToInt(String str) {
           int k=0;
      //去除空格
       while(k<str.length()&&str.charAt(k)==' ')k++;
      if(k==str.length()) return 0;
      //确定正负号
      int minus=1;
      if(str.charAt(k)=='-'){
        minus=-1;
        k++;
      }else if(str.charAt(k)=='+'){
        k++;
      }
      long res=0;
       while(k<str.length()&&str.charAt(k)>='0'&&str.charAt(k)<='9'){
           res=res*10+str.charAt(k)-'0';
            k++;
           if(res>Integer.MAX_VALUE) break;
       }
       res*=minus;
      if(res>Integer.MAX_VALUE) return Integer.MAX_VALUE;
      if(res<Integer.MIN_VALUE) return Integer.MIN_VALUE;
      return (int)res;
    }
}

68-1 二叉树的最近公共祖先 https://leetcode-cn.com/problems/er-cha-sou-suo-shu-de-zui-jin-gong-gong-zu-xian-lcof/

LCA问题

如果这题是普通的二叉树的最近公共祖先

class Solution{
  public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q){
    if(root==null||p==root||q==root) return root;
    TreeNode l=lowestCommonAncestor(root.left,p,q);
    TreeNode r=lowestCommonAncestor(root.right,p,q);
    if(l!=null&&r!=null) return root;
    else if(l==null) return r;
    else if(r==null) return l;
    return null;
  }
}

但是这题还给了一个二分搜索树的性质，如果我们继续这样做，就有点overhead了

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
           if(root==null) return null;
        //如果当前值大于两个节点的值，说明pq都在左子树
        if(root.val>p.val&&root.val>q.val) 
            return lowestCommonAncestor(root.left,p,q);
        //此时表明pq都在右子树
        if(root.val<p.val&&root.val<q.val) 
            return lowestCommonAncestor(root.right,p,q);
        //此时根节点为共同祖先
        return root;
    }
}

68-2 二叉树的最近公共祖先 https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof/

本题就是刚才所说的常规情况

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
           if(root==null||p==root||q==root) return root;
        TreeNode l=lowestCommonAncestor(root.left,p,q);
        TreeNode r=lowestCommonAncestor(root.right,p,q);
        if(l==null&&r==null) return null;
        else if(l==null) return r;
        else if(r==null) return l;
        return root;
    }
}

面试题36、https://leetcode-cn.com/problems/er-cha-sou-suo-shu-yu-shuang-xiang-lian-biao-lcof/

class Solution{
  private Node pre=null,head=null;
   public Node treeToDoublyList(Node root){
     if(root==null) return null;
        inOrder(root);
      head.left=pre;
     pre.right=head;
     return head;
   }
  private void inOrder(Node root){
         if(root==null) return ;
    inOrder(root.left);
    root.left=pre;
    if(pre!=null){
      pre.right=root;
    }
    else head=root;
    pre=root;
    inOrder(root.right);
  }
}