• 剑指offer【面试】

    前言

    写作于
    2022-08-18 18:11:19

    发布于
    2022-11-21 20:05:00

    学习算法

    推荐

    https://leetcode.cn/problem-list/e8X3pBZi/

    剑指 Offer II

    剑指 Offer II 001. 整数除法

    剑指 Offer II 001. 整数除法

    给定两个整数 a 和 b ，求它们的除法的商 a/b ，要求不得使用乘号 ‘*’、除号 ‘/’ 以及求余符号 ‘%’ 。

    注意：

    • 整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2
    • 假设我们的环境只能存储 32 位有符号整数，其数值范围是 [−231, 231−1]。本题中，如果除法结果溢出，则返回 231 − 1

    方法一：二分查找

    思路与算法

    根据「前言」部分的讨论，我们记被除数为 X，除数为 Y，并且 X 和 Y 都是负数。我们需要找出 X/Y 的结果 Z。ZZ 一定是正数或 0。

    根据除法以及余数的定义，我们可以将其改成乘法的等价形式，即：

    Z×Y≥X>(Z+1)×Y

    因此，我们可以使用二分查找的方法得到 ZZ，即找出最大的 Z 使得Z×Y≥X 成立。

    由于我们不能使用乘法运算符，因此我们需要使用「快速乘」算法得到 Z×Y 的值。「快速乘」算法与「快速幂」类似，前者通过加法实现乘法，
    后者通过乘法实现幂运算。「快速幂」算法可以参考「50. Pow(x, n)」的官方题解，「快速乘」算法只需要在「快速幂」算法的基础上，
    将乘法运算改成加法运算即可。

    细节

    由于我们只能使用 32 位整数，因此二分查找中会有很多细节。

    首先，二分查找的下界为 1，上界为 231−1。唯一可能出现的答案为2 31的情况已经被我们在「前言」部分进行了特殊处理，因此答案的最大值为 231−1。如果二分查找失败，那么答案一定为 0。

    在实现「快速乘」时，我们需要使用加法运算，然而较大的 Z 也会导致加法运算溢出。例如我们要判断A+B 是否小于 C 时（其中 A,B,C 均为负数），A+B 可能会产生溢出，因此我们必须将判断改为 A31+ 1, 231 - 1] 范围内，这样就不会产生溢出。

    代码

    class Solution {
    public int divide(int a, int b) {
        // 考虑被除数为最小值的情况
        if (a == Integer.MIN_VALUE) {
            if (b == 1) {
                return Integer.MIN_VALUE;
            }
            if (b == -1) {
                return Integer.MAX_VALUE;
            }
        }
        // 考虑除数为最小值的情况
        if (b == Integer.MIN_VALUE) {
            return a == Integer.MIN_VALUE ? 1 : 0;
        }
        // 考虑被除数为 0 的情况
        if (a == 0) {
            return 0;
        }
        
        // 一般情况，使用二分查找
        // 将所有的正数取相反数，这样就只需要考虑一种情况
        boolean rev = false;
        if (a > 0) {
            a = -a;
            rev = !rev;
        }
        if (b > 0) {
            b = -b;
            rev = !rev;
        }
        
        int left = 1, right = Integer.MAX_VALUE, ans = 0;
        while (left <= right) {
            // 注意溢出，并且不能使用除法
            int mid = left + ((right - left) >> 1);
            boolean check = quickAdd(b, mid, a);
            if (check) {
                ans = mid;
                // 注意溢出
                if (mid == Integer.MAX_VALUE) {
                    break;
                }
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }

        return rev ? -ans : ans;
    }

    // 快速乘
    public boolean quickAdd(int y, int z, int x) {
        // x 和 y 是负数，z 是正数
        // 需要判断 z * y >= x 是否成立
        int result = 0, add = y;
        while (z != 0) {
            if ((z & 1) != 0) {
                // 需要保证 result + add >= x
                if (result < x - add) {
                    return false;
                }
                result += add;
            }
            if (z != 1) {
                // 需要保证 add + add >= x
                if (add < x - add) {
                    return false;
                }
                add += add;
            }
            // 不能使用除法
            z >>= 1;
        }
        return true;
    }
}


    • 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
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79

    方法二：类二分查找

    前言

    常规意义下的二分查找为：给定区间 [l, r][l,r]，取该区间的中点 ⌊ (l+r)/2 ⌋，根据 mid 处是否满足某一条件，来决定移动左边界 l 还是右边界 r。

    我们也可以考虑另一种二分查找的方法：

    • 记 kk 为满足 2k ≤r−l<2 k+1的 k 值。

    • 二分查找会进行 k+1 次。在第 i (1≤i≤k+1) 次二分查找时，设区间为 [li, ri]，我们取 mid=l i +2 k+1−i ：

    • 如果 mid 不在 [li, ri] 的范围内，那么我们直接忽略这次二分查找；

    • 如果 mid 在 [li, ri] 的范围内，并且 mid 处满足某一条件，我们就将 li 更新为 mid，否则同样忽略这次二分查找。

    • 最终 li 即为二分查找的结果。这样做的正确性在于：

    设在常规意义下的二分查找的答案为 ans，记 δ 为 ans 与左边界的差值 ans−l。δ 不会大于 r−l，并且δ 一定可以用 2k, 2k-1, 2k-2,…, 21, 20 中的若干个元素之和表示（考虑 \deltaδ 的二进制表示的意义即可）。因此上述二分查找是正确的。

    思路与算法

    基于上述的二分查找的方法，我们可以设计出如下的算法：

    • 我们首先不断地将 Y 乘以 2（通过加法运算实现），并将这些结果放入数组中，其中数组的第 i 项就等于Y×2 。这一过程直到 Y 的两倍严格小于 X 为止。

    • 我们对数组进行逆序遍历。当遍历到第 i 项时，如果其大于等于 X，我们就将答案增加 2i，并且将 XX 中减去这一项的值。

    本质上，上述的逆序遍历就模拟了二分查找的过程。

    代码

    class Solution {
    public int divide(int a, int b) {
        // 考虑被除数为最小值的情况
        if (a == Integer.MIN_VALUE) {
            if (b == 1) {
                return Integer.MIN_VALUE;
            }
            if (b == -1) {
                return Integer.MAX_VALUE;
            }
        }
        // 考虑除数为最小值的情况
        if (b == Integer.MIN_VALUE) {
            return a == Integer.MIN_VALUE ? 1 : 0;
        }
        // 考虑被除数为 0 的情况
        if (a == 0) {
            return 0;
        }
        
        // 一般情况，使用类二分查找
        // 将所有的正数取相反数，这样就只需要考虑一种情况
        boolean rev = false;
        if (a > 0) {
            a = -a;
            rev = !rev;
        }
        if (b > 0) {
            b = -b;
            rev = !rev;
        }

        List<Integer> candidates = new ArrayList<Integer>();
        candidates.add(b);
        int index = 0;
        // 注意溢出
        while (candidates.get(index) >= a - candidates.get(index)) {
            candidates.add(candidates.get(index) + candidates.get(index));
            ++index;
        }
        int ans = 0;
        for (int i = candidates.size() - 1; i >= 0; --i) {
            if (candidates.get(i) >= a) {
                ans += 1 << i;
                a -= candidates.get(i);
            }
        }

        return rev ? -ans : ans;
    }
}


    • 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
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52

    剑指 Offer II 002. 二进制加法

    给定两个 01 字符串 a 和 b ，请计算它们的和，并以二进制字符串的形式输出。

    输入为 非空 字符串且只包含数字 1 和 0。

    示例 1:

    输入: a = "11", b = "10"
输出: "101"

    • 1
    • 2

    示例 2:

    输入: a = "1010", b = "1011"
输出: "10101"
 

    • 1
    • 2
    • 3

    提示：

    • 每个字符串仅由字符 ‘0’ 或 ‘1’ 组成。
    • 1 <= a.length, b.length <= 10^4
    • 字符串如果不是 “0” ，就都不含前导零。

    自己

    思路

    写一个方法完成a+b+c=x y
    a,b为加数；c为低位进位
    x 为向高位的进位 y为本位和

    每次取字符串1位进行运算

    class Solution {
    public String addBinary(String a, String b) {
        StringBuffer ans=new StringBuffer();
        int lena=a.length()-1;
        int lenb=b.length()-1;

        int m=0;
        int n=0;
        while(lena>=0&&lenb>=0){

            int c = a.charAt(lena)-'0';
            int d = b.charAt(lenb)-'0';

            ArrayList<Integer> add = addB(c, d, n);
            m = add.get(0);//本位和
            n = add.get(1);//进位

            ans.append(m);
            if (lena==0&&lenb==0){
                if (n==1){
                    ans.append('1');
                }
            }
            lena--;
            lenb--;
        }

        while(lena>=0){

            int c = a.charAt(lena)-'0';


            ArrayList<Integer> add = addB(c, 0, n);
            m = add.get(0);//本位和
            n = add.get(1);//进位

            ans.append(m);
            if (lena==0){
                if (n==1){
                    ans.append('1');
                }
            }
            lena--;

        }

        while(lenb>=0){

            int d = b.charAt(lenb)-'0';

            ArrayList<Integer> add = addB(0, d, n);
            m = add.get(0);//本位和
            n = add.get(1);//进位

            ans.append(m);

            if (lenb==0){
                if (n==1){
                    ans.append('1');
                }
            }

            lenb--;
        }
        StringBuffer reverse = ans.reverse();
        return reverse.toString();
    }
    //0+0=00 0+1=01 1+0=01 1+1=10  本位和 进位 x加数 y加数 z进位
    public static ArrayList<Integer> addB(int x, int y,int z) {
        ArrayList<Integer> list=new ArrayList<>();
       int i=x+y+z;
       int m=i%2;//本位和
       int n=(i-m)/2;//进位
       list.add(m);
       list.add(n);
       return list;
    }
    
}

    • 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
    • 37
    • 38
    • 39
    • 40
    • 41
    • 42
    • 43
    • 44
    • 45
    • 46
    • 47
    • 48
    • 49
    • 50
    • 51
    • 52
    • 53
    • 54
    • 55
    • 56
    • 57
    • 58
    • 59
    • 60
    • 61
    • 62
    • 63
    • 64
    • 65
    • 66
    • 67
    • 68
    • 69
    • 70
    • 71
    • 72
    • 73
    • 74
    • 75
    • 76
    • 77
    • 78
    • 79

    方法一：模拟

    class Solution {
    public String addBinary(String a, String b) {
        StringBuffer ans = new StringBuffer();

        int n = Math.max(a.length(), b.length()), carry = 0;
        for (int i = 0; i < n; ++i) {
            carry += i < a.length() ? (a.charAt(a.length() - 1 - i) - '0') : 0;
            carry += i < b.length() ? (b.charAt(b.length() - 1 - i) - '0') : 0;
            ans.append((char) (carry % 2 + '0'));
            carry /= 2;
        }

        if (carry > 0) {
            ans.append('1');
        }
        ans.reverse();

        return ans.toString();
    }
}



    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22

    剑指 Offer II 003. 前 n 个数字二进制中 1 的个数

    给定一个非负整数 n ，请计算 0 到 n 之间的每个数字的二进制表示中 1 的个数，并输出一个数组。

    示例 1:

    输入: n = 2
输出: [0,1,1]
解释: 
0 --> 0
1 --> 1
2 --> 10

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    示例 2:

    输入: n = 5
输出: [0,1,1,2,1,2]
解释:
0 --> 0
1 --> 1
2 --> 10
3 --> 11
4 --> 100
5 --> 101

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9

    说明 :

    • 0 <= n <= 105

    进阶:

    • 给出时间复杂度为 O(n*sizeof(integer)) 的解答非常容易。但你可以在线性时间 O(n) 内用一趟扫描做到吗？
    • 要求算法的空间复杂度为 O(n) 。
    • 你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的 __builtin_popcount ）来执行此操作。
    class Solution {
    public int[] countBits(int n) {
        int [] ans=new int[n+1];
        for (int i = 0; i <=n; i++) {
             ans[i]=countB(i);
        }

        return ans;

    }
    public static int countB(int x){
        int count=0;
        while(x!=0){

            int e=x&1;
            if(e==1){
                count++;
            }


            x=x>>1;

        }
        return count;
    }
}

    • 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
  • 相关阅读:
    Flink 基础概念
    Vue 通过 Hash、Histroy 实现一个SPA、VueRouter 的简单实现(分享)
    HDFS架构设计理念以及优缺点
    集美大学-浙大版《C语言程序设计实验与习题指导（第3版）》
    国产有什么低价好用的电容笔？四大款热销电容笔推荐
    《人生七年》纪录片中问的问题
    PC端使子组件的弹框关闭
    高教社杯数模竞赛特辑论文篇-2023年E题：基于小波变换和背包模型的小浪底水库最优监测方案研究（附获奖论文及Python代码实现）
    459. 重复的子字符串（力扣LeetCode）
    ListUtil java
  • 原文地址：https://blog.csdn.net/qq_51625007/article/details/126378780