2018年9月

在英语中,我们有一个叫做 词根(root)的概念,它可以跟着其他一些词组成另一个较长的单词——我们称这个词为 继承词(successor)。例如,词根an,跟随着单词 other(其他),可以形成新的单词 another(另一个)。

现在,给定一个由许多词根组成的词典和一个句子。你需要将句子中的所有继承词用词根替换掉。如果继承词有许多可以形成它的词根,则用最短的词根替换它。

你需要输出替换之后的句子。

示例 1:

输入: dict(词典) = ["cat", "bat", "rat"]
sentence(句子) = "the cattle was rattled by the battery"
输出: "the cat was rat by the bat"
注:

输入只包含小写字母。
1 <= 字典单词数 <=1000
1 <= 句中词语数 <= 1000
1 <= 词根长度 <= 100
1 <= 句中词语长度 <= 1000

解题关键:tire树干净利落。

class Solution {
    class Node{
        private char val;
        private boolean isEnd;
        private Node[] words = new Node[26];
        public Node(char val){
            this.val = val;
            this.isEnd = false;
        }
    }
    public void insert(Node curNode,String word){
        for(char c:word.toCharArray()){
            if(curNode.words[c - 'a'] == null){
                curNode.words[c - 'a'] = new Node(c);
            }
            curNode = curNode.words[c - 'a'];
        }
        curNode.isEnd = true;
    }
    public String search(Node node,String str){
        StringBuilder cur = new StringBuilder();
        for(char c:str.toCharArray()){
            if(node.words[c - 'a'] == null){
                break;
            }
            cur.append(c);
            node = node.words[c - 'a'];
            if(node.isEnd){
                return cur.toString();
            }
        }
        return str;
    }
    public String replaceWords(List<String> dict, String sentence) {
        if (dict == null || dict.size() == 0 || sentence == null || sentence.length() == 0) {
            return "";
        }
        Node root=new Node(' ');
        for(String v:dict){
            insert(root,v);
        }
        String[] exp = sentence.split(" ");
        StringBuffer bf = new StringBuffer();
        for(String v:exp){
            bf.append(search(root,v));
            bf.append(" ");
        }
        return bf.toString().trim();
    }
}

给定一个平衡括号字符串 S,按下述规则计算该字符串的分数:

() 得 1 分。
AB 得 A + B 分,其中 A 和 B 是平衡括号字符串。
(A) 得 2 * A 分,其中 A 是平衡括号字符串。

示例 1:

输入: "()"
输出: 1
示例 2:

输入: "(())"
输出: 2
示例 3:

输入: "()()"
输出: 2
示例 4:

输入: "(()(()))"
输出: 6

提示:

S 是平衡括号字符串,且只含有 ( 和 ) 。
2 <= S.length <= 50
一个solve接收一个arr 和从i到j
当count = 0 时候说明遇到了对称的() 那么如果k-i == 1则说明括号里面没内容 否则 2*solve(arr,i,j) i = k+1 i 向右移动 继续循环

class Solution {
    private int solve(char[] arr,int i,int j){
        int ans = 0,count = 0;
        for(int k = i;k<j;k++){
            count += arr[k] == '(' ? 1 : - 1;
            if(count == 0){//找到对称的()
                if(k - i == 1){//里面没内容
                    ans++;//++不进去扫
                }else{//有内容 从左到k
                    ans += 2*solve(arr,i+1,k);
                }//i 往右移动
                i = k+1;
            }
        }
        return ans;
    }
    public int scoreOfParentheses(String S) {
        return solve(S.toCharArray(),0,S.length());
    }
}

给定一个整数数组 nums ,你可以对它进行一些操作。

每次操作中,选择任意一个 nums[i] ,删除它并获得 nums[i] 的点数。之后,你必须删除每个等于 nums[i] - 1 或 nums[i] + 1 的元素。

开始你拥有 0 个点数。返回你能通过这些操作获得的最大点数。

示例 1:

输入: nums = [3, 4, 2]
输出: 6
解释:
删除 4 来获得 4 个点数,因此 3 也被删除。
之后,删除 2 来获得 2 个点数。总共获得 6 个点数。
示例 2:

输入: nums = [2, 2, 3, 3, 3, 4]
输出: 9
解释:
删除 3 来获得 3 个点数,接着要删除两个 2 和 4 。
之后,再次删除 3 获得 3 个点数,再次删除 3 获得 3 个点数。
总共获得 9 个点数。
注意:

nums的长度最大为20000。
每个整数nums[i]的大小都在[1, 10000]范围内。

解题关键:
takei 为本次拿的点数
skipi 为上次take和skip哪个大

class Solution {
    public int deleteAndEarn(int[] nums) {
        int[] sum = new int[10001];
        for(int v:nums){
            sum[v] += v;
        }
        int take = 0;
        int skip = 0;
        for(int v:sum){
            int takei = skip + v; //上次跳加这次
            int skipi = Math.max(skip,take);//上上次跳跟上次比较哪个个大选哪个
            take = takei;
            skip = skipi;
        }
        return Math.max(take,skip);
    }
}

数据链路层使用的信道主要有以下类型:

  • 点对点信道
  • 广播信道

路由器在转发分组时只需要使用底三层网络协议

使用点对点信道的数据链路层

链路:从一个结点到相邻结点的一段物理线路
数据链路:实现通信协议控制数据的传输的有硬件和软件构成了数据链路。

帧:数据链路层的协议数据单元

网络层交下来的IP数据报在首部和尾部添加数据封装成帧

三个基本问题:

  • 封装成帧
    在一段数据的前后分别添加首部和尾部,这样就构成了一个帧。

每一种链路层协议都规定了所能传送的帧的数据部分长度上限-最大传送单元(Maximum Transfer Unit)
在首部添加SOH(Start Of Header) 十六进制编码分别是:01
在尾部添加EOT(End Of Transmission) 十六进制编码分别是:04

  • 透明传输
    传送的帧不允许与SOH或EOT相同否则会出错。

解决办法:在发送数据如果出现控制字符(SOH、EOT)则在前面加入转义字符ESC(1B)这种办法称为字节填充、字符填充

  • 差错检测
    误码率BER(Bit Error Rate): 传输错误的比特占所传输比特总数的比率

目前广泛采用循环冗余检验CRC(Cyclic Redundancy Check)的检错技术
为了进行检错而添加的冗余码常称为帧检测序列FCS(Frame Check Sequence)

为了支持差错检测所以必须在数据链路层把数据进行拆分成帧 每一帧加上冗余码(FCS)

差错检测有两种:

  • 比特差错
  • 传输差错
    数据链路层实现了比特差错 传输差错是指帧的接收顺序跟发送顺序不一致甚至帧有丢失帧有重复

所以数据链路层并不是可靠传输

目前互联网采用区别对待
对于通信质量良好的有线传输线路 数据链路层不进行传输差错检测而是交给上层协议(如TCP)

对于通信质量较差的无线传输线路,数据链路层使用确认和重传机制,数据链路层向上提供可靠传输服务。

点对点协议PPP

用户计算机和ISP进行通信时所采用的数据链路层协议

PPP协议应满足的需求:

  • 简单
  • 封装成帧
  • 透明性
  • 多种网络层协议
  • 多种类型链路
  • 差错检测
  • 检测连接状态
  • 最大传送单元
  • 网络层地址协商
  • 数据压缩协商

协议组成:

  • 一个将IP数据报封装到串行链路的方法
  • 一个用来建立、配置和测试数据链路连接的链路控制协议LCP(Link Control Protocol)
  • 一套网络协议NCP(Network Control Protocol)

PPP帧格式:
首部的第一个字段和尾部的第二个字段都是标志字段F(Flag) 规定为0x7E
PPP首部的第四个字段是2字节的协议字段 当协议字段为0x0021时PPP帧的信息字段就是IP数据报,若为0xC021则为LCP数据报,若为0x8021表示这是网络层的控制数据 尾部中的第一个字段(2字节)是使用CRC的帧检验序列FCS。

字节填充
当信息字段出现和标志字段一样的比特0x7E组合时,转义字符定义为0x7D并使用字节填充

零比特填充
PPP协议在使用SONET/SDH链路时 采用同步传输 而不是异步传输有5个连续的1则填入一个0

PPP协议的工作状态

当个人电脑通过调制解调器发出的载波信号,PPP就进入了链路建立 状态 目的是建立链路层的LCP连接

发送LCP的配置请求帧
链路的另一端会响应以下几种响应的一种:

  • 配置确认帧 所有选项都接受
  • 配置否认帧 所有选项都理解但不能接受
  • 配置拒绝帧 选项有的无法识别或不能接受,需要协商

然后就进入了鉴别状态 验证用户的账号密码 鉴别失败进入链路终止状态 成功则进入网络层协议
当网络层配置完毕后,链路就进入了链路打开状态

使用广播信道的数据链路层(局域网)

局域网具有如下一些优点:

  • 具有广播功能
  • 便于系统的扩展和逐渐演变,各设备的位置可灵活调整改变。
  • 提高了系统的可靠性、可用性、生存性

以太网 = 局域网

共享信道有两种方法:

  • 静态划分信道 (频分复用、波分复用、时分复用)
  • 动态媒体接入控制:
    • 随机接入 所有用户可随机地发送消息 如果同一时刻有多个用户同时发送消息则可能发生碰撞 则要有解决碰撞的网络协议 (常用)
    • 受控接入 用户不能随机地发送信息而必须服从一定的控制,轮询。

以太网的两个标准:

  • DIX Ethernet V2
  • IEEE 802.3

出于有关厂商的激烈竞争 IEEE委员会被迫制定了及格不同的局域网标准 把局域网的数据链路层 拆成两个子层 逻辑链路控制LLC(Logical Link Control)子层 和 媒体接入控制层MAC(Medium Access Control)子层

直到后面只剩下DIX Ethernet V2 而不是IEEE 802.3 因此就只剩下了MAC层

适配器的作用(网卡)

适配器的一个重要功能就是要进行数据串行传输和并行传输的转换
适配器在接收到了正确的帧时使用中断来通知该计算机 并交付协议栈中的网络层,当计算机要发送IP数据报时,就由协议栈把IP数据报下交给适配器,组装成帧后发送到局域网。
计算机的硬件地址放在适配器ROM中,计算机的软件地址-IP地址放在计算机存储器中。

每一个适配器都有一个地址

为了通信的简便,以太网采取了以下两种措施:

  • 采用较为灵活的无连接的工作方式 不需要建立连接 以太网提供的服务尽最大努力的交付,不可靠的交付 对有差错帧是否需要重传则由高层来决定。
  • 同一时间内只允许一台计算机发送数据 CSMA/CD 发送的时候检测是否有计算机发送数据 有则等待 如果同时冲突了则大家都停止传输

CSMA/CD 协议要点:

  • 多点接入
  • 载波监听 用电子技术检测总线上有没有其他计算机在发送
  • 碰撞检测 边发送边监听 适配器边发送边检测信道上的信号电压的变化情况 当几个计算机同时在总线上发送数据时 电压变化幅度会增大,当适配器检测到的信号电压变化幅度超过一定阈值时,就认为总线上有多个计算机在传送数据。

CSMA/CD协议的以太网是双向交替通信(半双工通信)
以太网使用截断二进制指数退避算法来确定重传的时机,当发生碰撞时会推迟在一个随机的时间发送

强化碰撞 如果发现碰撞则还需要人为的再传送一些干扰的比特来让所有用户知道现在已经发生了碰撞

整个CSMA/CD协议的过程:
1.准备发送 适配层从网络层获得一个分组 加上以太网的首部和尾部,组成以太网帧,放入适配器缓存中,在发送之前先检测信道
2.检测信道
3.发送过程仍检测信道
发送失败:则执行指数退避算法

每发送一帧都要缓存一下如果发现碰撞则要推迟发送

使用集线器的星形拓扑

集线器
集线器工作在物理层 每个接口仅仅简单的转发比特

以太网的MAC层

局域网中,硬件地址又称为物理地址、MAC地址
目前的局域网适配器实际上使用的都是6字节MAC地址

IEEE的注册管理机构RA(Registration Authority)是局域网全球地址的法定管理机构

生产局域网适配器的厂商向IEEE购买前三个字节构成的号 这个号正式名称为 组织唯一标志符OUI(Organizationally Unique Identifier) 也叫公司标识符 生产的时候硬件地址就被写死在适配器上

发往计算机的帧有以下三种帧:

  • 单播帧 收到的MAC地址与本站的硬件地址相同
  • 广播帧 发送给本局域网上所有站点的帧
  • 多播帧 发送给本局域网上一部分站点的帧

混杂模式可直接把所有的帧都记录下来

以太网V2的MAC帧结构

目的地址6字节 源地址6字节 类型2地址 数据46-1500地址 FCS4字节

如果只在物理层进行拓展局域网的话那么整个拓展后的局域网受限于各个子局域网的最低碰撞率 成为碰撞域

所以目前的做法是在数据链路层拓展以太网(交换机) 全双工通信 他不是共享线路 所以他不采用CSMA/CD协议

交换机的交换表一开始是空的 然后经过一次传输 把发送方的MAC地址和接口写入交换表 以后只要发往MAC地址的数据都转发给接口

虚拟局域网VLAN(Virtual LAN)

利用以太网交换机可以很方便地实现虚拟局域网VLAN(Virtual LAN) 虚拟局域网是由一些局域网网段构成的与物理位置无关的逻辑组,而这些网段具有某些共同需求,每一个VLAN的帧都有一个明确的标志符,指明发送这个帧的计算机属于哪一个VLAN

虚拟局域网可以限制接受广播信息的计算机数

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字: '0', '1', '2', '3', '4', '5', '6', '7', '8', '9' 。每个拨轮可以自由旋转:例如把 '9' 变为 '0','0' 变为 '9' 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 '0000' ,一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字,一旦拨轮的数字和列表里的任何一个元素相同,这个锁将会被永久锁定,无法再被旋转。

字符串 target 代表可以解锁的数字,你需要给出最小的旋转次数,如果无论如何不能解锁,返回 -1。

示例 1:

输入:deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出:6
解释:
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的,
因为当拨动到 "0102" 时这个锁就会被锁定。
示例 2:

输入: deadends = ["8888"], target = "0009"
输出:1
解释:
把最后一位反向旋转一次即可 "0000" -> "0009"。
示例 3:

输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
输出:-1
解释:
无法旋转到目标数字且不被锁定。
示例 4:

输入: deadends = ["0000"], target = "8888"
输出:-1

提示:

死亡列表 deadends 的长度范围为 [1, 500]。
目标数字 target 不会在 deadends 之中。
每个 deadends 和 target 中的字符串的数字会在 10,000 个可能的情况 '0000' 到 '9999' 中产生。
解题关键:
实际上每一位有10种变化情况,总共有4位,所以有10^4种状态,初始从”0000”开始衍变,到target的最短路径可以用BFS来表达。当然,当衍变到deadends中的某些状态时,就不能再衍变了。典型的BFS+状态记录。

实际上求转盘锁的最短次数其实就是求达到指定数值的层数 则采用BFS 如果采用DFS的话不容易找到最短层数。

Yes, definitely you can apply DFS here. As the whole search space is 10^4 = 10000, DFS can work here too. But why many people choose BFS instead? Because the problem here asks for the minimum number of steps to achieve the target state. Using BFS, we can report the answer as long as we reach the target state. But using DFS, we can't guarantee that the initial target state that we reach is the optimal solution. You still have to search the whole search space. Think about the problem that to find the depth of a binary tree, it is quite similar in this sense.

class Solution {
    public int openLock(String[] deadends, String target) {
        Set<String> vis = new HashSet();
        for(String v:deadends){
            vis.add(v);
        }
        if(vis.contains("0000")){
            return -1;
        }
        vis.add("0000");
        int[] way = new int[]{1,-1};
        Queue<String> queue = new ArrayDeque();
        queue.offer("0000");
        int sum = 0;
        while(!queue.isEmpty()){
            int size = queue.size();
            for(int i = 0;i<size;i++){ //队首取出来判断是否相等 不相等则继续BFS
                String now = queue.poll();
                if(now.equals(target)){
                    return sum;
                }
                //四个位置上每一个位置上的+1 -1 都加入队列中
                for(int j = 0;j<4;j++){
                    for(int k = 0;k<2;k++){
                        char[] cs = now.toCharArray();
                        int digit = (cs[j] - '0' + way[k] + 10) % 10;//算出当前位置的数
                        cs[j] = (char) ('0' + digit);
                        String nxt = new String(cs);
                        if (!vis.contains(nxt)) {//当前节点是否走过 未走过则加入
                            vis.add(nxt);
                            queue.offer(nxt);
                        }
                    }
                }
            }
            sum++;
        }
        return -1;
    }
}