【剑指offer】day15

不用加减乘除做加法

剑指 Offer 65. 不用加减乘除做加法 - 力扣（Leetcode）

题目要求

写一个函数，求两个整数之和，要求在函数体内不得使用 “+”、“-”、“*”、“/” 四则运算符号。

例子：

输入: a = 1, b = 1
输出: 2

提示：

• a, b 均可能是负数或 0
• 结果不会溢出 32 位整数

思路分析

位运算

进位和n与进位c的计算公式如下：

• 非进位和(异或运算)公式：n = a^b；

• 进位(与运算+左移一位)：c = a&b<<1;

• s = a+b -> n+c;

循环求n和c，直到c=0，返回n即可；(此时s=n)

代码实现

class Solution {
    public int add(int a, int b) {
        while(b!=0){ // 结束条件
            int c = (a&b)<<1; // c为进位
            a ^= b; //a为非进位和
            b = c; //b也为进位和
        }
        return a;// 将非进位和返回，即将n返回
    }
}

构建乘积数组

剑指 Offer 66. 构建乘积数组 - 力扣（Leetcode）

题目要求

给定一个数组 A[0,1,…,n-1]，请构建一个数组 B[0,1,…,n-1]，其中 B[i] 的值是数组 A 中除了下标 i 以外的元素的积, 即 B[i]=A[0]×A[1]×…×A[i-1]×A[i+1]×…×A[n-1]。不能使用除法。

例子：

输入: [1,2,3,4,5]
输出: [120,60,40,30,24]

提示：

• 所有元素乘积之和不会溢出 32 位整数
• a.length <= 100000

思路分析

该题不能使用除法

根据例子，列出下图：

1. 初始化数组b，b[0] = 1,辅助变量temp，初始值temp=1；
2. 计算上图中，b[i]的下三角个元素乘积，乘积入b[i]；
3. 计算上图中，b[i]的上三角个元素乘积，先使用temp记录，然后乘积入b[i]；
4. 将数组b返回；

代码实现

class Solution {
    public int[] constructArr(int[] a) {
        // 数组长度
        int len = a.length;
        // 特殊情况
        if(len == 0) return new int[0];
        // 定义b[]
        int [] b = new int[len];
        // 初始值
        b[0] = 1;
        // 定义temp变量
        int temp = 1;
        for(int i=1;i<len;i++){
            // 计算下三角，根据下标将a数组和b数组值相乘，然后放入b[i]
            b[i] = b[i-1] * a[i-1];
        }
        // 计算上三角
        for(int j=len-2;j>=0;j--){
            temp *= a[j+1];
            b[j] *= temp;
        }
        return b;
    }
}

把字符串转换成整数

面试题67. 把字符串转换成整数 - 力扣（Leetcode）

题目要求

写一个函数 StrToInt，实现把字符串转换成整数这个功能。不能使用 atoi 或者其他类似的库函数。

首先，该函数会根据需要丢弃无用的开头空格字符，直到寻找到第一个非空格的字符为止。

当我们寻找到的第一个非空字符为正或者负号时，则将该符号与之后面尽可能多的连续数字组合起来，作为该整数的正负号；假如第一个非空字符是数字，则直接将其与之后连续的数字字符组合起来，形成整数。

该字符串除了有效的整数部分之后也可能会存在多余的字符，这些字符可以被忽略，它们对于函数不应该造成影响。

注意：假如该字符串中的第一个非空格字符不是一个有效整数字符、字符串为空或字符串仅包含空白字符时，则你的函数不需要进行转换。

在任何情况下，若函数不能进行有效的转换时，请返回 0。

提示：

假设我们的环境只能存储 32 位大小的有符号整数，那么其数值范围为 [−231, 231 − 1]。如果数值超过这个范围，请返回 INT_MAX (231 − 1) 或 INT_MIN (−231) 。

例子1：

输入: "42"
输出: 42

例子2：

输入: "   -42"
输出: -42
解释: 第一个非空白字符为 '-', 它是一个负号。
     我们尽可能将负号与后面所有连续出现的数字组合起来，最后得到 -42 。

例子3：

输入: "4193 with words"
输出: 4193
解释: 转换截止于数字 '3' ，因为它的下一个字符不为数字。

例子4：

输入: "words and 987"
输出: 0
解释: 第一个非空字符是 'w', 但它不是数字或正、负号。
     因此无法执行有效的转换。

例子5：

输入: "-91283472332"
输出: -2147483648
解释: 数字 "-91283472332" 超过 32 位有符号整数范围。 
     因此返回 INT_MIN (−231) 。

思路分析

字符情况处理

1. 首位空格：删除即可；
2. 符号位：+，-和无符号三种情况，新建变量保存，返回之前判断正负；
3. 非数字字符：遇到首个非数字字符，直接返回；
4. 数字字符：
   • 字符转数字：该数字的ASCII码与数字0的ASCII码相减即可；
   • 数字拼接：从左向右遍历，假定当前字符为c，当前数字为x，结果为res，则拼接公式：res = 10 * res + x; x = ascii(c) - ascii('0');
5. 数字越界问题：在每轮数字拼接前，判断 res 在该轮拼接后是否超过 214748364721474836472147483647 ，若超过则加上符号位直接返回；

代码实现

class Solution {
    public int strToInt(String str) {
        // 把字符串转为字符数组存放
        char[] c =str.trim().toCharArray();
        // 特殊情况
        if(c.length == 0) return 0;
        // 定义变量
        int res = 0,max = Integer.MAX_VALUE / 10;
        int i=1,sign = 1;
        // 判断+ - 符号
        if(c[0] == '-'){
            sign = -1;
        }else if(c[0] != '+'){
            i = 0;
        }
        // for循环遍历
        for(int j = i; j < c.length;j++){
            // 不为数字0~9
            if(c[j] < '0' || c[j] > '9') break;
            // 判断是否越界
            if(res > max || res == max && c[j] > '7'){
                if(sign == 1){
                    return Integer.MAX_VALUE;
                }else{
                    return Integer.MIN_VALUE;
                }
            }
            // 拼接res
            res = res * 10 +(c[j] - '0');
        }
        return res * sign;
    }
}

二叉搜索树的最近公共祖先

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先 - 力扣（Leetcode）

题目要求

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉搜索树: root = [6,2,8,0,4,7,9,null,null,3,5]

例子：

输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 8
输出: 6 
解释: 节点 2 和节点 8 的最近公共祖先是 6。
    
输入: root = [6,2,8,0,4,7,9,null,null,3,5], p = 2, q = 4
输出: 2
解释: 节点 2 和节点 4 的最近公共祖先是 2, 因为根据定义最近公共祖先节点可以为节点本身。

提示：

• 所有节点的值都是唯一的。
• p、q 为不同节点且均存在于给定的二叉搜索树中。

思路分析

二叉搜索树的左子树一定小于根节点，右子树一定大于根节点

• p>root,q>root，那么p和q一定在右子树；
• p<root,q<root，那么p和q一定在右子树；

代码实现

/**
 * 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) {
        // 循环查找
        while(root != null){
            // 说明p和q在左子树
            if(root.val > p.val && root.val > q.val){
                root = root.left;
            }else if(root.val <p.val && root.val < q.val){
                // 说明p和q在右子树
                root = root.right;
            }else{
                // 在根节点的两边
                return root;
            }
        }
        return null;
    }
}

二叉树的最近公共祖先

剑指 Offer 68 - II. 二叉树的最近公共祖先 - 力扣（Leetcode）

题目要求

给定一个二叉树, 找到该树中两个指定节点的最近公共祖先。

百度百科中最近公共祖先的定义为：“对于有根树 T 的两个结点 p、q，最近公共祖先表示为一个结点 x，满足 x 是 p、q 的祖先且 x 的深度尽可能大（一个节点也可以是它自己的祖先）。”

例如，给定如下二叉树: root = [3,5,1,6,2,0,8,null,null,7,4]

例子：

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 1
输出: 3
解释: 节点 5 和节点 1 的最近公共祖先是节点 3。

输入: root = [3,5,1,6,2,0,8,null,null,7,4], p = 5, q = 4
输出: 5
解释: 节点 5 和节点 4 的最近公共祖先是节点 5。因为根据定义最近公共祖先节点可以为节点本身。

提示：

• 所有节点的值都是唯一的。
• p、q 为不同节点且均存在于给定的二叉树中。

思路分析

递归

我们递归遍历整棵二叉树，定义$f_x$ 表示$x$节点的子树中是否包含p节点或q节点，如果包含为 true，否则为 false;

那么一定满足关系式：($f_l$ && $f_r$) || ((x = p || x = q) && ($f_l$ || $f_r$));

其中l和r分别代表x的左右子节点；

代码实现

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    // 定义二叉树，保存公共祖先节点
    private TreeNode ans;
    // 构造函数
    public Solution(){
        this.ans = null;
    }
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        // 调用递归方法
        dfs(root,p,q);
        // 返回公共祖先节点
        return this.ans;
    }
    // 递归方法
    public boolean dfs(TreeNode root,TreeNode p,TreeNode q){
        // 特殊情况
        if(root == null) return false;
        // 递归左右子树
        boolean l = dfs(root.left,p,q);
        boolean r = dfs(root.right,p,q);
        // 关系式，主要满足条件就更新ans节点
        if((l && r) || ((root.val == p.val || root.val == q.val) && (l || r))){
            ans = root;
        }
        return l || r || (root.val == p.val || root.val == q.val);
    }
}