ARTS-Week-9

发表于 | |

第九周

  • Alogrithm:Letter Combinations of a Phone Number
  • Reading:
  • Tech:分布式一致性算法
  • Share:clion远程调试指南

Alogrithm

题目—Letter Combinations of a Phone Number

美式电话号码上，输入号码，输出全部可能的字母组合。

首先确定这种要求全部可能的题需要遍历去搜索，暴力搜索用一个递归调用实现。

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
class Solution {
public:
    Solution() {
      phone_['2'] = "abc";
      phone_['3'] = "def";
      phone_['4'] = "ghi";
      phone_['5'] = "jkl";
      phone_['6'] = "mno";
      phone_['7'] = "pqrs";
      phone_['8'] = "tuv";
      phone_['9'] = "wxyz";
    }
    vector<string> letterCombinations(string digits) {
          std::vector<std::string> output = {};
            Dig2Letter("", digits, &output);
         return output;
    }

private:
    std::unordered_map<char, std::string> phone_;
    void Dig2Letter(const std::string& letter, const std::string& digits,
                std::vector<std::string>* output) {
      if (digits.size() < 1) return;
      int dig_ascii = (int)digits[0];
      if (dig_ascii > 57 || dig_ascii < 50) return;
      std::vector<std::string> s;
      for (char c : (phone_.find(digits[0])->second)) {
        if (digits.size() == 1) {
          output->emplace_back(letter + c);
        } else {
          Dig2Letter(letter + c, digits.substr(1), output);
        }
      }
      return;
    }
};

Tips:

  • string::substr的用法，ARTS4里有提过，到最后的话后一个参数可省略。

Zookeeper

基本概念

  • 数据模型
    • 和unix文件结构很像
  • 数据节点
    • 永久节点
    • 临时节点
    • 顺序节点
    • 属性：版本号、事物id、时间戳
  • 会话
    • 心跳检测
    • 发送请求并接受响应
    • 接受watcher事件通知
  • 权限
    • ACL机制 - 无继承性、设置后不能修改
    • 权限机制：用于：权限
  • 集群角色
    • Leader\Follower\Observer
  • 分布式一致性
    • CAP: Consistency\Availability\Partition tolerance
    • 单调一致（客户端可以通过Sync来达到强一致性）
      • 时序一致性
      • 原子性
      • 单一系统镜像
      • 持久性
    • Zab协议：2PC 3PC Paxos Zab Raft
    • Zab:- 恢复模式 - 广播模式
      • 广播模式下读写：读：直接读 写：Leader收到半数以上ACK
      • Leader选举：
  • 应用
    • 数据发布与订阅（配置中心、动态信息修改、全局变量存储）
    • 命名服务（ID生成器、分布式系统命名）
    • 分布式通知与协调（watcher-服务发现、心跳检测）
    • 分布式锁（可以数据库锁表、基于缓存、基于ZK）排他性、容错性、避免死锁
    • 集群管理（集群监控、Master选举）、分布式队列（FIFO队列、同步队列）
  • 实践
    • XFR、XID