日常学习0102

1. leetcode

leetcode 777 题

• 题目描述

  在一个由 'L' , 'R' 和 'X' 三个字符组成的字符串（例如"RXXLRXRXL"）中进行移动操作。一次移动操作指用一个"LX"替换一个"XL"，或者用一个"XR"替换一个"RX"。现给定起始字符串start和结束字符串end，请编写代码，当且仅当存在一系列移动操作使得start可以转换成end时， 返回True。

• 解析

  这个题目，我一开始采用的是个模拟策略，按照规则去交换字符串，但是找不到一个一定可行的交换策略，就感觉自己的思路是错的。看了题解。其实按照交换规则字符串在进行移动操作过程中字符串中的L的位置只能向左移动（XL（这里不是替换，是被换成） LX），R的位置只能向右移动（RX XR），但是L,R的相对顺序是不变的(LL,LR,RL,RR是不支持移动操作的)且L,R的数量不会改变。通过上面可以总结两点，如果start可以转换成end,那么：1. start 和 end 中LR数量相等且，相对顺序不变（即不包含X时，)。 2. 在不包含X的start, end中，相同位置下的L , 在原start 的位置小于等于在原end的位置，相同位置下R的位置，正相反。

• code

class Solution {
public:
    bool canTransform(string start, string end) {
        int size = start.size();
        if(size != end.size())
            return false;

        string nox_start = remove_x(start);
        string nox_end = remove_x(end);

        if(nox_end != nox_start)
            return false;
        return check(end, start, 'L') && check(start, end, 'R');
    }

    bool check(const string& start, const string& end, char c){
        int e = 0, size = start.size();
        for(int i = 0; i < size; i++){
            if(start[i] == c){
                while(e < size && end[e]!= c)
                    e++;
                if(e < i)
                    return false;
                e++;
            }
        }
        return true;
    }


    string remove_x(string str){
        string res = {};
        int size = str.size();
        for(int i = 0; i < size; i++){
            if(str[i] == 'X')
                continue;
            res.push_back(str[i]);
        }
        return res;
    }
};

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/swap-adjacent-in-lr-string
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

2. HDFS

hdfs 架构图

• NameNode 负责管理HDFS 文件目录树和文件元数据信息（fsimage HDFS 元数据镜像文件和 editlog HDFS 日志改动文件），监视DataNode的健康情况，如果DataNode宕机择，将HDFS其中数据移出备份。 NameNode 一个集群一个。
• Secondary NameNode (Checkpoint Node 0.21.0+) 定期合并fsimage 和 editlog, 并传输给NameNode.
• DataNode 一个Slave一般安装一个DataNode, 负责实际的数据存储，并需要定期向NameNode 汇报数据情况。 DataNode 以block（固定大小，默认64M）的基本形式存储数据。当上传到HDFS的数据过大时，会对数据切成多个block, 每个block 会分别存在多个（默认3）DataNode 中。

3. MapReduce

hadoop MapReduce 架构图

• JobTracker 监督TaskTracker的健康状态，如果有异常将任务转移到其他的节点，JobTracker会跟踪任务的执行转台和资源状态，让Task Scheduler 在资源空闲时，分配任务使用资源。
• TaskTracker 定时向JobTracker 汇报运行情况和资源状况和执行JobTracker的命令。TaskTacker 以 “slot”为单位分配资源（CPU,内存）给Task, Task 只有获取到“Slot”才会执行。Task Scheduler的作用就是分配TaskTracker中空闲的“Slot”给Task

• Task 分为Map Task 和 Reduce Task. HDFS 存储单位时block， MapReduce的处理单位split, split 会包含数据长度，起始位置等，全部由用户定义，一个split 交付给一个 Map Task处理.

  
  
  block 和 split的关系