不用加减乘除做加法

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

题目要求

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

例子:

1
2
输入: 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)

代码实现

1
2
3
4
5
6
7
8
9
10
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
输入: [1,2,3,4,5]
输出: [120,60,40,30,24]

提示:

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

思路分析

该题不能使用除法

根据例子,列出下图:

image-20221228124609830

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

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
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:

1
2
输入: "42"
输出: 42

例子2:

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

例子3:

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

例子4:

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

例子5:

1
2
3
4
输入: "-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 ,若超过则加上符号位直接返回;

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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]

img

例子:

1
2
3
4
5
6
7
输入: 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一定在右子树;

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
/**
* 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]

img

例子:

1
2
3
4
5
6
7
输入: 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 为不同节点且均存在于给定的二叉树中。

思路分析

递归

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

那么一定满足关系式:(flf_l && frf_r) || ((x = p || x = q) && (flf_l || frf_r));

其中lr分别代表x的左右子节点;

代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
/**
* 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);
}
}