前言：
记录一下时间：2022年3月9日。感觉去年的算法课学到的东西过于理论化，但是庆幸自己基础还不错也拿到了很不错的分数。刷算法总归来说有点心血来潮的感觉，其实很早就有打算，但是始终没有给自己安排出来合理的时间，终于今儿在图书馆看到了邻桌的计算机妹子在面对着一次次的LeetCode提交失败，我下定决心了开始刷哈哈哈哈哈，多少有点幸灾乐祸（bushi），但是还是想提升自己。
属于是随缘更新了，有的时候题目简单一天可能就做了四五个，有的时候理解起来比较麻烦就少一点，反正还有别的事情要做，这个坚持下来就好。

剑指Offer Day01

剑指 Offer II 001. 整数除法

题目概述

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

注意：

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

示例 1：

1
2
3
输入：a = 15, b = 2
输出：7
解释：15/2 = truncate(7.5) = 7

示例 2：

1
2
3
输入：a = 7, b = -3
输出：-2
解释：7/-3 = truncate(-2.33333..) = -2

示例 3：

1
2
输入：a = 0, b = 1
输出：0

示例 4：

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

提示:

  • $ 2^{31} \le a, b \le 2^{31} - 1 $
  • $ b != 0 $

思路分析

上来第一道题就开始卡住我，属实是开头有点小破防。

  • 首先考虑几种特殊情况，不能使用除号来实现除法，那我们就想到了一个比较经典的——快速减法，来实现除法的效果。这里使用了位操作
    • 如果说一个数除以另一个数，我们主要看这个被除数里面能包含多少个除数。一个栗子：38里面有多少个4，当38减去4的2指数倍数（除数右移操作等于扩大一倍）然后小于当前倍率下的数的时候（其实就是除数不能再扩大了，这里的扩大是指直接翻倍），我们得到当前右移的次数，这是当前结果下被数可以消除的除数的次数，用此时的被除数减去除数，生成新的被除数，并且将除数归为原来的大小。
    • 还是刚才的例子：38可以被4的4倍（ $ 2^{2}$ ）16除，能保证差大于当前除数16，但是不能被4的8倍（ $ 2^{3}$ ）除。所以我们知道了38里面至少有4个4，$ 38 - 16 = 22$ ，以此类推把剩下的被除数中含有的4的个数求出来，当被除数小于除数的时候，计算结束，因为我们不需要考虑小数位。
    • 因为这是位运算，位运算只能是涉及到2的整数倍乘除运算，我们只能等比扩大或者缩小4的2次方倍数（4翻到8，8翻到16……以此类推）
  • 因为数字界限问题，位运算可能会导致溢出，所以我们统一转化为负数进行运算，原理一样，但是相应大小号需要变化
  • 考虑特殊界限问题，除数b等于1的时候直接输出a；除数b等于-1而且a等于规定最小整数的时候，如果取反变成正数会导致溢出，所以按照题目要求我们返回整型最大值；a等于0结果直接为0
  • a，b两个数转化为负数的时候不需要考虑溢出问题
  • 通过按位异或确定最终结果正负性，并用一个boolean变量flag来保存，用作最后输出

代码实现 Java

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 divide(int a, int b) {
        if(a == 0) return 0;
        else if(b == 1) return a;
        else if(b == -1) return a == Integer.MIN_VALUE ? Integer.MAX_VALUE : -a;
        boolean positive = (a ^ b) >= 0;
        a = a < 0 ? a: -a;
        b = b < 0 ? b: -b;
        int ans = 0;
        while(a <= b){
            int base = 1;
            int divisor = b;
            while(a - divisor <= divisor){
                divisor <<= 1;
                base <<= 1;
            }
            ans += base;
            a -= divisor;
        }
        return positive ? ans : -ans;

    }
}

剑指 Offer II 002. 二进制加法

题目概述

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

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

示例1:

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

示例2:

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

提示：

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

思路分析

这道题相对于上一道来讲就比较简单，简单分析一下就写的来代码，但是有的方法还是忍不住去百度一下。

  • 一位一位去计算就好了，要注意考虑进位的问题，所以单独设置了一个flag变量来检测进位问题
  • 然后就是简单的，从最后一位开始计算01进位问题，然后在结果的对应位置输出相应的01数值
  • 如果想每次都是提取到最后一位，就将两个01数字串左移，然后进行运算，再append到结果串
  • 考虑两个数字串字符位数量不同问题，用0去填充
  • 考虑最末位进位问题，需要新增一位数位
  • 因为我们运算的最后一位被最先append到结果里面，所以需要reverse()一下

代码实现 Java

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
class Solution {
    public String addBinary(String a, String b) {
        StringBuilder ans = new StringBuilder(); //结果字符串
        int len_a = a.length() - 1; //查询最后一位的位置
        int len_b = b.length() - 1;
        int flag = 0; //初始进位为0
        while(len_a >= 0 || len_b >= 0){
            char temp_a = len_a >= 0 ? a.charAt(len_a--) : '0'; 
            char temp_b = len_b >= 0 ? b.charAt(len_b--) : '0';
            if(temp_a - '0' + temp_b - '0' > 1){
                if(flag > 0){
                    ans.append('1');
                    flag = 1;
                }
                else{
                    ans.append('0');
                    flag = 1;
                }
            }
            else if(temp_a - '0' + temp_b - '0' == 1){
                if(flag > 0){
                    ans.append('0');
                    flag = 1;
                }
                else{
                    ans.append('1');
                    flag = 0;
                }
            }
            else if(temp_a - '0' + temp_b - '0' == 0){
                if(flag > 0){
                    ans.append('1');
                    flag = 0;
                }
                else{
                    ans.append('0');
                    flag = 0;
                }
            }
        }
        if(flag == 1) //若进位还剩1，继续追加
            ans.append(flag);
        return ans.reverse().toString();
    }
}

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

题目概述

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

示例 1:

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

示例2:

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

说明 :

0 <= n <= 105

进阶:

给出时间复杂度为O(n*sizeof(integer))的解答非常容易。但你可以在线性时间O(n)内用一趟扫描做到吗？
要求算法的空间复杂度为O(n)。
你能进一步完善解法吗？要求在C++或任何其他语言中不使用任何内置函数（如 C++ 中的__builtin_popcount）来执行此操作。

思路分析

  • 首先是数组大小需要+1，因为包含了0
  • 这道题是位运算和动态规划的结合算法，属于是一个我最开始完全没想到的一个操作，很妙
  • 有一个规律性总结：
    • 0含有的1的个数为0，所以f(0)=0;其中f是统计字符1个数的一个构造函数
    • 如果值i是一个偶数，值i中含有1的个数于值i/2中含有1的个数是一样的，因为是相当于左移了一位，而且i的二进制最后一位必定是0
    • 如果i是一个奇数，那么f(i) = f(i/2) + 1，因为最后一位是1，必定会少一个1

代码实现 Java

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int[] countBits(int n) {
        int[] ans = new int[n + 1];
        ans[0] = 0;
        for (int i = 1; i <= n; i++) {
            ans[i] = (i & 1) == 1 ? ans[i - 1] + 1 : ans[i >> 1];
        }
        return ans;
    }
}