ARTS-Week-7

发表于 分类于 Disqus： 本文字数： 2.2k 阅读时长 ≈ 2 分钟

第七周

  • Alogrithm:Three Sum
  • Reading:Static Libraries vs. Dynamic Libraries
  • Tech:ELF目标文件与readelf
  • Share:TIMELAPSE OF THE FUTURE: A Journey to the End of Time

Alogrithm

题目—3 Sum

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:
Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

排序之后先用循环加二分查找实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
 public:
  std::vector<std::vector<int>> threeSum(std::vector<int>& nums) {
    std::sort(nums.begin(), nums.end());
    std::vector<std::vector<int>> out;
    for (int i = 0; i < nums.size(); ++i) {
      if (nums[i] > 0) break;
      if (i > 0 && nums[i] == nums[i - 1]) continue;
      for (int j = i + 1; j < nums.size(); ++j) {
        if (nums[j] > - nums[i] || -(nums[j]+ nums[i]) < nums[j]) break;
        if (j - i > 1 && nums[j] == nums[j - 1]) continue;
        if(std::binary_search(nums.begin() + j + 1, nums.end(), -(nums[i] + nums[j]))) {
          std::vector<int> tmp = {nums[i], nums[j], -(nums[i] + nums[j])};
          out.emplace_back(tmp);
        }
      }
    }
    return out;
  }
}

发现用了两层循环明显不够快，可以考虑参考上周Container With Most Water的解法。

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:
    vector<vector<int>> threeSum(vector<int>& nums) {
     std::sort(nums.begin(), nums.end());
     std::vector<std::vector<int>> out;
     for (int i = 0; i < nums.size(); ++i) {
       if (nums[i] > 0 || nums.size() - i < 3) break;
       if (i > 0 && nums[i] == nums[i - 1]) continue;
       int j = i + 1, k = nums.size() - 1;
       while (j < k) {
         if (nums[i] + nums[j] + nums[k] == 0) {
           std::vector<int> tmp = {nums[i], nums[j], nums[k]};
           out.emplace_back(tmp);
           int c = nums[j];
           while (c == nums[j] && j < nums.size() - 1 ) ++j;
            continue;
         }
         if (nums[i] + nums[j] < -nums[k]) ++j;
         else --k;
       }
     }
     return out;
    }
};

Reading

为了周末参加RustCon Asia，本周断断续续看了看Rust的相关东西，为了避免教程里各种针对其他语言的细节描述。我是通过GitHub上的教程：Rust for C++ programmers学的。

简而言之，总结起来目前C/C++程序员使用C/C++的主要原因或者是希望对系统底层操作，要不就是希望挤出系统的最后一滴能力。（虽然入坑原因是因为前者，不过貌似现在还留在这个圈子里的原因是两者都不是[笑]）

而Rust主要的目的就是解决在开发者需要对内存直接操作、要求不使用内存回收等机制的前提下，做到内存安全。正如冷笑话所言：Segmentfault.com sponsor rust which do not have segmentfault，rust用Ownership/Reference/Borrowing等机制几乎解决了内存泄露、未定义内存、野指针等问题。

Tech

想谈谈Go和Rust的特点，