ARTS Week-2

发表于 | 分类于 | |

第二周，

Alogrithm

题目—Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
      unsigned int pre_sum = 0;
      ListNode *prev_node = nullptr, *output = nullptr;
      while (l1 != nullptr || l2 != nullptr) {
        unsigned int a = 0, b = 0, sum = 0;
        if (l1 != nullptr) {
          a = l1->val;
          l1 = l1->next;
        }
        if (l2 != nullptr) {
          b = l2->val;
          l2 = l2->next;
        }
        pre_sum = adder(a, b, pre_sum, &sum);
        auto node = new ListNode(sum);
        if (prev_node == nullptr) {
          output = node;
        } else {
          prev_node->next = node;
        }
        prev_node = node;
      }
      if (pre_sum != 0) {
        prev_node->next = new ListNode(pre_sum);
      }
      return output;
    }
private:
    inline int adder(const unsigned int &a,
                     const unsigned int &b,
                     const unsigned int &pre_sum,
                     unsigned int *res) {
      int sum = a + b + pre_sum;
      *res = sum % 10;
      return sum / 10;
    }
};

68ms，还是慢，需要想想怎么优化。

在网上找到的duolabaobao的答案

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
 
 
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
    ListNode *preHead = new ListNode(0);
    ListNode *p = preHead;

    int carry = 0, sum;
    while (l1 || l2 || carry) {
      sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + carry;
      carry = sum / 10;
      p->next = new ListNode(sum % 10);
      p = p->next;
      l1 = l1 ? l1->next : NULL;
      l2 = l2 ? l2->next : NULL;
    }
    return preHead->next;
}

简洁了特别多，主要在于如下几点：

  • 不用傻乎乎写if (l1 != nullptr)而直接判断if (l1)就好
  • 赋值判断可以直接通过<condition>?<true>:<false>实现

传上去发现也得64ms

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode* root = new ListNode(0), *first = root;
        int carry = 0;
        
        while ( l1 || l2 )
        {
            int n1 = l1 ? l1->val : 0;
            int n2 = l2 ? l2->val : 0;
            int ans = n1 + n2 + carry;
            carry = ans / 10;
            root->next = new ListNode(ans%10);
            root = root->next;
            if ( l1 ) l1 = l1->next;
            if ( l2 ) l2 = l2->next;
        }
        if (carry)
            root->next = new ListNode(1);
        
        return first->next;
        
    }
};

前面的问题在于while的判断次数比较多，需要把carray单独拆出来不用那么复杂的判断再跑一遍。同时不能有太多判断什么的操作放在里面，初始化什么的尽量在外面做好。

题目 - Longest Substring Without Repeating Characters

查找没有重复字母的最大子串。

最Brute Force的方法略去，想到可以做一个string记录目前检验的子串，用一个int存储当前最大长度的子串长度。用一个循环遍历每个字母，如果这个字母在buf子串里出现过，就更新buf子串去掉前面的部分并对比目前最大子串长度值看是否需要更新。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int Solution::lengthOfLongestSubstring(std::string s) {
  std::string buf = "";
  int max = 0;
  for (auto i : s) {
    auto res = buf.find(i);
    if(res == -1) {
      buf += i;
    } else {
      if (buf.length() > max) max = buf.length();
      buf = buf.substr(res + 1) + i;
    }
  }
  if (buf.length() > max) max = buf.length();
  return max;
}

由于std::string::find的复杂度为O(N * M)，在本例中M为1，所以最差时间复杂度为O(N^2)，好处是后面一个N不会大于128(ASCII)，所以其实可以说是O(128N)，但还可以再优化。

优化的方向是放弃用一个字符串来存储找到的字段，直接用HashMap存储字母-位置的对应关系，用一个int记录目前不重复字符串的头位置。如果遇到重复只用更新头位置和对应关系里的位置，并更新最大长度就好。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
int Solution::lengthOfLongestSubstring(std::string s) {
  std::unordered_map<char, int> map;
  int max = 0, start = 0;
  for (int i = 0; i != s.length(); i++) {
    auto found = map.find(s[i]);
    if (found != map.end() && found->second >= start) {
      max = (max > (i - start)) ? max : (i - start);
      start = found->second + 1;
    }
    map[s[i]] = i;
  }
  max = (max > (s.length() - start)) ? max : (s.length() - start);
  return max;
}

Review

本周文章是一个2016年的slide : gRPC Design and Implementation :
Review - gRPC Design and Implementation

Tip

安装过程用有很多时候需要知道电脑或服务器的架构，比如说到底是：

  • x86
  • x86-64/amd64
  • MIPS
  • ARM
    其中的那种。

这个问题可以通过一行命令：

1
uname -p

解决。或者可以使用：

1
2
3
lscpu
# or
less /proc/cpuinfo

了解

Share

本周推荐Youtube上一个节目频道：
Vox Borders

讲各种有趣的边境故事的。