1 快乐数

1.1 题目描述

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

「快乐数」定义为：对于一个正整数，每一次将该数替换为它每个位置上的数字的平方和，然后重复这个过程直到这个数变为 1，也可能是 无限循环 但始终变不到 1。如果 可以变为 1，那么这个数就是快乐数。

如果 n 是快乐数就返回 True ；不是，则返回 False 。

示例：

输入：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.2 思路解析

刚开始还以为这是个数学题，总是想着是不是会出现6和8的组合才是快乐数，仔细想又不是这样，因为如果数字的位数多的话完全可以不是6和8的组合凑成10，100，或者1000这样子。

后来看解析焕然大悟，真是太久没有写题了，一个浅显的道理都没有意识到：如果不是快乐数，那么通过求平方算出来的数字一定会出现重复的数字，由于是在数组中查找对应元素，所以用哈希表最快，所以数据结构选用set.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
set<int> mySet;
    int computeJoyNum(int n){
    if (n)
        return pow(n % 10,2) + computeJoyNum(n/10);
    return 0;
    }

    bool isHappy(int n) {
        int m = n;
        while(mySet.find(m) == mySet.end()){
            mySet.insert(m);
            m = computeJoyNum(m);
            if (m == 1) return true;
        }
        return false;
    }

这里需要注意，CPP中的求幂运算是std::pow函数，^是按位异或运算。

2 两数之和

2.1 题目描述

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。

示例:

给定 nums = [2, 7, 11, 15], target = 9

因为 nums[0] + nums[1] = 2 + 7 = 9

所以返回 [0, 1]

2.2 思路解析

这个题只涉及两个数，所以在总体策略上，只需要将数组元素插入到一个我们自己构建的容器中，只要这个容器的查找速度够快，就能实现优于O(n$^2$)的时间复杂度。

刚开始我想到的其实是用set，我想着set内的元素是有序的，也许可以使用distance函数输出下标，但是提交的时候发现不对，查找资料后发现set的底层使用红黑树实现的，内部元素是有序的，但是不支持随机访问，也就是说不能通过下标的方式对元素进行查找。

所以我就在想换什么容器，数组的话当然可以，但是数组的查找效率太低，就算采用边排序边查找的方式，总共算下来的时间复杂度也要O($n^2$)。

于是考虑用map，可是map的底层实现也是红黑树，对于这种关联容器来说，cpp中STL与之绑定的迭代器是双向迭代器，而不是随机访问迭代器，所以不支持下标的随机访问。但是好在我们可以用空间换时间，map是一种键-值关联的数据结构，我们只需要在map的值的地方存取下标就好了。

注意这里键是nums中的元素，值是对应元素的下标。不能交换位置，因为在unordered_map中，查找键的时间复杂度是O($log_{}{n}$)，而查找值的时间复杂度是O($n$)。

1
2
3
4
5
6
7
8
9
10
11
12
13
vector<int> twoSum(vector<int>& nums, int target) {
       vector<int> ans;
       unordered_map<int,int> s;  //临时存储判断过的数字
       for (int i = 0; i < nums.size(); i++){
           if (s.find(target - nums[i])!= s.end()){
               ans.push_back(s.find(target - nums[i])->second);
               ans.push_back(i);
               return ans;
           }
           s.insert({nums[i],i});
       }
       return ans;

我们使用unordered_map是因为其底层实现是哈希表，查找和插入元素的时间复杂度是O(1)。如果用map的话时间复杂度是O($log_{}{n}$)，性能不如哈希表实现。

2.3 总结归纳

2.3.1 Map用法总结

std::map 是 C++ 标准库中的关联容器，提供了基于键值对的映射。以下是对 std::map 常用的一些操作：

  1. 插入元素：

    • 使用 insert 函数插入键值对：
      1
      2
      3
      std::map<int, std::string> myMap;
      myMap.insert({1, "one"});
      myMap.insert(std::make_pair(2, "two"));

  2. 访问元素：

    • 使用键访问元素，注意如果键不存在，会插入一个默认值：
      1
      2
      std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}};
      std::string value = myMap[1]; // 访问键为 1 的值
    • 使用 find 函数查找元素，避免插入默认值：
      1
      2
      3
      4
      auto it = myMap.find(1);
      if (it != myMap.end()) {
          std::string value = it->second;
      }

  3. 删除元素：

    • 使用 erase 函数删除指定键的元素：
      1
      myMap.erase(1); // 删除键为 1 的元素
    • 使用迭代器删除指定位置的元素：
      1
      2
      3
      4
      auto it = myMap.find(1);
      if (it != myMap.end()) {
          myMap.erase(it);
      }

  4. 遍历元素：

    • 使用迭代器遍历整个 std::map：

      1
      2
      3
      4
      5
      for (auto it = myMap.begin(); it != myMap.end(); ++it) {
          int key = it->first;
          std::string value = it->second;
          // 使用 key 和 value 进行操作
      }

    • 使用范围循环（C++11 及以上版本）：

      1
      2
      3
      4
      5
      for (const auto& pair : myMap) {
          int key = pair.first;
          std::string value = pair.second;
          // 使用 key 和 value 进行操作
      }

  5. 获取容器大小：

    1
    size_t size = myMap.size(); // 返回键值对的数量

  6. 判断元素是否存在：

    1
    2
    3
    if (myMap.find(1) != myMap.end()) {
        // 键为 1 的元素存在
    }

  7. 清空容器：

    1
    myMap.clear(); // 清空所有键值对

2.3.2 迭代器回顾

C++ 标准库中的迭代器分为五种主要类型，按功能和能力的不同逐步增强，分别是：

  1. 输入迭代器（Input Iterator）： 只能读取序列中的元素，但不能修改。支持逐个元素读取和后移，不支持随机访问。
  2. 输出迭代器（Output Iterator）： 只能写入序列中的元素，但不能读取。支持逐个元素写入和后移，不支持随机访问。
  3. 前向迭代器（Forward Iterator）： 具备输入和输出迭代器的所有功能，并且可以多次遍历同一范围。支持逐个元素读写、前移和后移，不支持随机访问。
  4. 双向迭代器（Bidirectional Iterator）： 具备前向迭代器的所有功能，并且可以反向遍历。支持逐个元素读写、前移和后移，但不支持随机访问。
  5. 随机访问迭代器（Random Access Iterator）： 具备双向迭代器的所有功能，并且支持随机访问。可以通过迭代器进行跳跃式的访问和修改。支持逐个元素读写、前移、后移、随机访问、加法和减法运算等。

不同的 C++ 容器提供不同类型的迭代器。以下是一些常见容器及其迭代器类型：

  1. 数组：

    • 迭代器类型：随机访问迭代器
      1
      2
      3
      int arr[] = {1, 2, 3, 4, 5};
      int* begin = std::begin(arr);
      int* end = std::end(arr);

  2. 向量（std::vector）：

    • 迭代器类型：随机访问迭代器
      1
      2
      3
      std::vector<int> vec = {1, 2, 3, 4, 5};
      auto it = vec.begin();
      auto end = vec.end();

  3. 列表（std::list）：

    • 迭代器类型：双向迭代器
      1
      2
      3
      std::list<int> myList = {1, 2, 3, 4, 5};
      auto it = myList.begin();
      auto end = myList.end();

  4. 双端队列（std::deque）：

    • 迭代器类型：随机访问迭代器
      1
      2
      3
      std::deque<int> myDeque = {1, 2, 3, 4, 5};
      auto it = myDeque.begin();
      auto end = myDeque.end();

  5. 集合（std::set）：

    • 迭代器类型：双向迭代器
      1
      2
      3
      std::set<int> mySet = {1, 2, 3, 4, 5};
      auto it = mySet.begin();
      auto end = mySet.end();

  6. 映射（std::map）：

    • 迭代器类型：双向迭代器（针对 std::map 和 std::set 中的键值对）
      1
      2
      3
      std::map<int, std::string> myMap = {{1, "one"}, {2, "two"}, {3, "three"}};
      auto it = myMap.begin();
      auto end = myMap.end();

  7. 无序集合（std::unordered_set）：

    • 迭代器类型：前向迭代器（C++11 及以上版本）
      1
      2
      3
      std::unordered_set<int> myUnorderedSet = {1, 2, 3, 4, 5};
      auto it = myUnorderedSet.begin();
      auto end = myUnorderedSet.end();

  8. 无序映射（std::unordered_map）：

    • 迭代器类型：前向迭代器（C++11 及以上版本）
      1
      2
      3
      std::unordered_map<int, std::string> myUnorderedMap = {{1, "one"}, {2, "two"}, {3, "three"}};
      auto it = myUnorderedMap.begin();
      auto end = myUnorderedMap.end();

这只是一些基本的例子，具体的迭代器类型可能还受到 C++ 标准库实现的影响。在编写代码时，可以使用 std::begin 和 std::end 函数来获取容器的起始和结束迭代器。在 C++11 及以上版本，可以使用 auto 关键字简化迭代器的声明。

3 四数之和

3.1 题目描述

给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。

为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -2^28 到 2^28 - 1 之间，最终结果不会超过 2^31 - 1 。

例如:

输入:

  • A = [ 1, 2]
  • B = [-2,-1]
  • C = [-1, 2]
  • D = [ 0, 2]

输出:

2

解释:

两个元组如下:

  1. (0, 0, 0, 1) -> A[0] + B[0] + C[0] + D[1] = 1 + (-2) + (-1) + 2 = 0
  2. (1, 1, 0, 0) -> A[1] + B[1] + C[0] + D[0] = 2 + (-1) + (-1) + 0 = 0

3.2 思路解析

本题看着是一个组合数学的问题，但其实可以把两个数组能加和出的数字合在一个容器中，因为本题只需要我们输出元组个数，所以我们可以用map来存储加和出的数字及其出现次数。

最开始我的想法是A和B统计一次，C和D再统计一次，然后再进行哈希表的匹配搜索。

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
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
    unordered_map<int,int> sums1;
    unordered_map<int,int> sums2;
    int ans = 0;
    for (int i:nums1){
        for (int j:nums2){
            if (sums1.find(i + j)==sums1.end())
                sums1.insert({i+j,1});
            else{
                sums1.find(i+j)->second++;
            }
        }
    }
    for (int i:nums3){
        for (int j:nums4){
            if (sums2.find(i+j) == sums2.end())
                sums2.insert({i+j,1});
            else{
                sums2.find(i+j)->second++;
            }
        }
    }
    for (auto& pair:sums1){
        if (sums2.find(-1 * pair.first) != sums2.end())
            ans += (pair.second * sums2.find(-1 * pair.first)->second);
    }
    return ans;
}

但是看了解析之后，发现其实还有更加高效的办法，其实只需要统计A和B的加和情况。然后在遍历C和D的过程中进行哈希搜索。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int fourSumCount(vector<int>& nums1, vector<int>& nums2, vector<int>& nums3, vector<int>& nums4) {
    unordered_map<int,int> sums1{0};
    int counts = 0;
    // 首先计算nums1和nums2的加和可能情况
    for (int i:nums1){
        for (int j:nums2)
            sums1[i + j]++;
    }
    for (int i:nums3){
        for (int j:nums4)
            if (sums1[-i-j])
                counts += sums1[-i-j];
    }
    return counts;
}