算法(三)

发表于2022-07-20更新于2023-04-25字数统计2.2k阅读时长12分阅读次数

前言

这是关于算法记录的第三篇博客，这篇博客分享一些有趣的题，主要是一些比较巧妙的算法题的解法，有些是数学相关的，另一些是位运算相关的。这些题没有什么很固定的模板可以套，但是解法又比较有趣。本博客题目均来自Leetcode题库。

数学题

204. 计数质数

给定整数 n ，返回 所有小于非负整数 n 的质数的数量。

解：关于求解质数的题，有一种较为高效的方法：质数筛法。实际上，在6.S081-Lab 1 Xv6 and Unix utilities中就通过多个进程之间管道通信实现了一个质数筛。这种方法的思路也比较简单，这里就不展开说明了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int countPrimes(int n) {
    vector<int> nums(n, 0);
    int count = 0;
    // 质数筛
    for (int i=2; i<n; ++i) {
        if (nums[i] == 0) {
            count ++;
            // 这里从 i^2 开始筛，因为前面的数已经被别的质数筛过了
            for (long long j=(long long)i*i; j<n; j+=i) {
                nums[j] = 1;
            }
        }
    }
    return count;
}

172. 阶乘后的零

给定一个整数 n ，返回 n! 结果中尾随零的数量。

解：这道题也是比较巧妙的一道题，阶乘计算过程中，将所有因数质因数分解之后只有 2*5 会产生尾随 0，且显然所有的因数中 2 的数量是要大于 5 的数量的，意识到这一点之后，这道题就转化为计算因数中 5 的数量。

1
2
3
4
5
6
7
8
9
10
11
int trailingZeroes(int n) {
    if (n == 0) {
        return 0;
    }
    int res = 0;
    while (n > 0) {
        res += n/5;
        n/=5;
    }
    return res;
}

326. 3 的幂

给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 true ；否则，返回 false 。

解：这道题最容易想到的办法当然就是循环里一直除以3，然后判断是不是 3 的幂。这里要介绍一个投机取巧的方法，由于题目的输入数为int类型，最大不超过2^31 - 1，这个范围内最大的 3 的 n 次幂是1162261467，由于 3 是质数，所以只要能除尽上面这个数的数就是 3 的幂。

1
2
3
bool isPowerOfThree(int n) {
    return n > 0 && 1162261467 % n == 0;
}

238. 除自身以外数组的乘积

给你一个整数数组 nums，返回 数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积 。
题目数据 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在  32 位 整数范围内。请不要使用除法，且在 O(n) 时间复杂度内完成此题。

解：这道题通过正反两次遍历来计算出结果，正序遍历的时候计算出nums[i]左侧所有数的乘机，逆序遍历的时候计算出其右侧所有数的乘积。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
vector<int> productExceptSelf(vector<int>& nums) {
    vector<int> res(nums.size(), 1);
    int tmp = nums[0];
    for (int i=1; i<nums.size(); ++i) {
        res[i] = tmp;
        tmp *= nums[i];
    }
    tmp = nums.back();
    for (int i=nums.size()-2; i>=0; --i) {
        res[i] *= tmp;
        tmp *= nums[i];
    }
    return res;
}

169. 多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

解：著名的 Boyer-Moore 投票算法，基本的思路是选定一个候选人candidate并维护其选票数count，遍历数组，当前元素等于候选人时增加选票，不等时减少选票，当选票数为0时更换候选人。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
int majorityElement(vector<int>& nums) {
    int count = 1;
    int candidate = 1e9 + 1;
    for (int num : nums) {
        if(num != candidate) {
            count --;
        } else {
            count ++;
        }
        if (count == 0) {
            candidate = num;
            count = 1;
        }
    }
    return candidate;
}

470. 用 Rand7() 实现 Rand10()

给定方法 rand7 可生成 [1,7] 范围内的均匀随机整数，试写一个方法 rand10 生成 [1,10] 范围内的均匀随机整数。

你只能调用 rand7() 且不能调用其他方法。请不要使用系统的 Math.random() 方法。

解：拒绝采样，通过调用两次rand7()组成矩阵能够等概率的产生 [1,49]之间的数，我们只取前40个数(不满足则重新采样)：

1
2
3
4
5
6
7
8
9
int rand10() {
    while (1) {
        int row = rand7();
        int col = rand7();
        int tmp = (row-1) * 7 + col;
        if (tmp > 40) continue;  // 不满足要求则重新采样
        return tmp % 10 + 1;
    }
}

202. 快乐数

编写一个算法来判断一个数 n 是不是快乐数。

「快乐数」 定义为：

  • 对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和。
  • 然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。
  • 如果这个过程 结果为 1，那么这个数就是快乐数。
1
2
3
4
5
6
7
输入：n = 19
输出：true
解释：
1^2 + 9^2 = 82
8^2 + 2^2 = 68
6^2 + 8^2 = 100
1^2 + 0^2 + 0^2 = 1

解：这显然是一个循环的过程，我们可以不断的计算一个数的各个位置的平方和，作为下一个数，再不断迭代计算下一个数，知道产生1，或者得到之前已经存在的某个数(可以从理论上证明这也计算下去并不会溢出)。我们可以使用哈希表记录之前出现过的数：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
bool isHappy(int n) {
    set<int> st;
    while (!st.count(n)) {
        st.insert(n);
        int tmp = 0;
        // get next num
        while (n) {
            tmp += (n%10) * (n%10);
            n /= 10;
        }
        n = tmp;
        if (n == 1) return true;
    }
    return false;
}

这道题换一种想法，把每个数当作一个节点，就变成了判断是否存在圈的问题，可以使用Floyd判圈方法(之前判断链表中是否存在圈就是这个方法)，使用快慢两个指针，当指针重合时则存在圈。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public:
    bool isHappy(int n) {
        // 快慢指针判圈
        int slow = n;
        int fast = getNext(n);
        while (slow != fast) {
            if (slow == 1) return true;
            slow = getNext(slow);
            fast = getNext(getNext(fast));
        }
        return slow == 1;
    }

private:
    int getNext(int num) {
        int res = 0;
        while (num != 0) {
            int tmp = num % 10;
            res += tmp * tmp;
            num /= 10;
        }
        return res;
    }

位运算

136. 只出现一次的数字

给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。

解：这道题是十分经典有有趣的一道题，需要知道一个数和自己本身做异或会得到 0，一个数与 0 做异或运算会得到这个数本身，且异或操作满足交换律。所以这道题可以把所有数异或起来就能得到只出现一次的数了。

1
2
3
4
5
6
7
int singleNumber(vector<int>& nums) {
    int res = 0;
    for (int num : nums) {
        res ^= num;
    }
    return res;
}

268. 丢失的数字

给定一个包含 [0, n] 中 n 个数的数组 nums ，找出 [0, n] 这个范围内没有出现在数组中的那个数。

解：和上面那道题一样。

1
2
3
4
5
6
7
8
9
int missingNumber(vector<int>& nums) {
    int res = 0;
    for (int i=0; i<nums.size(); ++i) {
        res ^= i;
        res ^= nums[i];
    }
    res ^= nums.size();
    return res;
}

还有一种解法是使用高斯求和公式。

318. 最大单词长度乘积

给你一个字符串数组 words ，找出并返回 length(words[i]) * length(words[j]) 的最大值，并且这两个单词不含有公共字母。如果不存在这样的两个单词，返回 0 。

解：可以用位来记录每个单词中字母是否出现。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int maxProduct(vector<string>& words) {
    size_t res = 0;
    int n = words.size();
    vector<int> mp(n, 0);   // int 的低 26 位记录 26 个字母是否出现
    for (int i=0; i<n; ++i) {
        for (char ch:words[i]) {
            mp[i] |= 1 << (ch - 'a');
        }
    }
    for (int i=0; i<n; ++i) {
        for (int j=i+1; j<n; ++j) {
            if ((mp[i] & mp[j]) == 0) {
                // 两个单词没有共同字符
                res = max(res, words[i].size() * words[j].size());
            }
        }
    }
    return res;
}

693. 交替位二进制数

给定一个正整数，检查它的二进制表示是否总是 0,1 交替出现：换句话说，就是二进制表示中相邻两位的数字永不相同。

解：第一种逐位判断的方法就不提了，可以将原数n和n>>1做异或运算，如果n是0,1交替出现的话，其结果必是前面均为 0，后面全是 1，且是充要条件。然后后者的充要条件是 a & (a+1) == 0

1
2
3
4
5
bool hasAlternatingBits(int n) {
    long a = n ^ (n >> 1);
    return (a & (a + 1)) == 0;
}

参考文献

  1. https://github.com/changgyhub/leetcode_101