剑指offer009 两个栈实现一个队列

Posted on 2020-01-14 In 剑指offer Valine:

Problem:

用两个栈来实现一个队列，完成队列的 Push（入队）和 Pop（出队）操作。

Intuition:

in 栈用来处理入栈（push）操作，out 栈用来处理出栈（pop）操作。一个元素进入 in 栈之后，出栈的顺序被反转。当元素要出栈时，需要先进入 out 栈，此时元素出栈顺序再一次被反转，因此出栈顺序就和最开始入栈顺序是相同的，先进入的元素先退出，这就是队列的顺序。

Solution:

Stack<Integer> in = new Stack<Integer>();
Stack<Integer> out = new Stack<Integer>();

public void push(int node) {
    in.push(node);
}

public int pop() throws Exception {
    if (out.isEmpty())
        while (!in.isEmpty())
            out.push(in.pop());

    if (out.isEmpty())
        throw new Exception("queue is empty");

    return out.pop();
}

剑指offer008 二叉树的下一个节点

Posted on 2020-01-14 In 剑指offer Valine:

Problem:

给定一个二叉树和其中的一个结点，请找出中序遍历顺序的下一个结点并且返回。注意，树中的结点不仅包含左右子结点，同时包含指向父结点的指针。

public class TreeLinkNode {

    int val;
    TreeLinkNode left = null;
    TreeLinkNode right = null;
    TreeLinkNode next = null; // 指向父结点的指针

    TreeLinkNode(int val) {
        this.val = val;
    }
}

Intuition:

Solution:

public class CodingInterview_008 {
    class TreeLinkNode {

        int val;
        TreeLinkNode left = null;
        TreeLinkNode right = null;
        TreeLinkNode next = null; // 指向父结点的指针

        TreeLinkNode(int val) {
            this.val = val;
        }
    }
     public TreeLinkNode GetNext(TreeLinkNode pNode){
         if(pNode.right!=null){
             TreeLinkNode node=pNode.right;
             while(node.left!=null){
                 node=node.left;
             }
             return node;
         }else{

             while(pNode.next!=null){
                 //注意下面的next是指向父节点
                 TreeLinkNode parent=pNode.next;
                 if(parent.left==pNode){
                     return parent;
                 }else{
                     pNode=parent;
                 }
             }
             return null;
         }
     }
}

剑指offer005 重建二叉树

Posted on 2020-01-13 In 剑指offer Valine:

Problem:

根据二叉树的前序遍历和中序遍历的结果，重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。

Intuition:

前序遍历的第一个值为根节点的值，使用这个值将中序遍历结果分成两部分，左部分为树的左子树中序遍历结果，右部分为树的右子树中序遍历的结果。然后分别对左右子树递归地求解。
每次递归就相当于在前序数组和中序数组中分别划一刀。首先我们根据root（前序数组的第一个元素）在中序数组中的位置对中序数组划一刀，这样这道划痕的左边部分就是左子树的中序遍历数组，划痕的右边就是右子树的中序遍历数组。然后我们记下左子树的大小，再对前序遍历的数组划一刀，这样就完成了这道题的递归过程。
我们这一题应该抓住的核心是前序遍历数组的第一个元素是root,然后该元素在中序遍历数组中的位置的左边即为左子树的元素，右边即为右子树的元素。

Solution:

 import java.util.Arrays;

public class CodingInterview_005 {

   class TreeNode{
       int val;
       TreeNode left;
       TreeNode right;
       TreeNode(int val){
           this.val=val;
       }
   }

   

    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if (pre.length == 0 || in.length == 0) {
            return null;
        }
        TreeNode root = new TreeNode(pre[0]);
        // 在中序中找到前序的根
        for (int i = 0; i < in.length; i++) {
            if (in[i] == pre[0]) {
                // 左子树，注意 copyOfRange 函数，左闭右开
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(in, 0, i));
                // 右子树，注意 copyOfRange 函数，左闭右开
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(in, i + 1, in.length));
                break;
            }
        }
        return root;
    }


}

泛型

Posted on 2019-10-31 In java Valine:

首先通过一个简单的例子看看泛型的基本使用。假如我们要创建一个礼物对象，但是礼物有很多种，可以是电脑，自行车或者是别的乱七八糟的任何东西。那么这个时候我们怎么描述礼物对象中内容呢？好像用object可以，但是每次使用object都要做强制类型转换，如果转换出错甚至要到运行时才能检测出来。那么这种情况我们就应该考虑用泛型来处理

public class Gift<T> {//generic
    private final T value;
    private final Double cost;
    //创建gift的时候确定T的类型
    public Gift(T value,Double cost){
        this.value=value;
        this.cost=cost;
    }

   public T getValue(){
        return  value;
   }

   public Double getCost(){
        return cost;
   }

}

public class GiftGiver {
    Computer computer=new Computer();
    //<>括号里是interface或者class
    Gift<Computer> giftToJon=new Gift<Computer>(computer,1500d);
    Bicycle bicycle=new Bicycle();
    Gift<Bicycle> giftToBob=new Gift<Bicycle>(bicycle,500d);

    //Computer jonGift=giftToBob.getValue();如果不小心对应错了类型，编译器会自动帮我们检查错误。而如果用原始的object强制类型转换则需要等到运行时才能检查到错误
    //Bicycle bobGift=giftToJon.getValue();
    Computer jonGift=giftToJon.getValue();
    Bicycle bobGift=giftToBob.getValue();
}

从上面的代码可以看出，我们使用泛型的时候只需要在调用的时候指出泛型类型就可以了。接下来我们看看泛型的特征
1.一个类或者接口可以有0或者多个泛型类型
2.通常用一个字母来表示泛型类型（编译器当然不在乎你用多个，你可以用Cat,Dog来表示泛型，但是这样可读性会变差。读者会认为泛型里面只能是你写的那个类，但是实际上你用的是泛型）
3.带泛型的类型不能保持其原继承关系（下面的例子有讲解）

4.泛型里面的内容本身可以是某类的子类或者父类
例子：

1	<T extends Computer> or <T super Computer>

5.泛型类型会在编译时被擦除（从JVM的视角来看，泛型压根不存在）
6.不能实例化类型变量
public Pair(){
first=new T();//error
second=new T();//error
}

下面来通过一个例子来解释第三条

public class Echo<T> {
    public T echo(T value){
        return value;
    }

    public Echo<T> echo(Echo<T> value){
        return value;
    }
}

public class EchoChamber {
    public static void main(String[] args) {
        Echo<Number> numberEcho=new Echo<>();
        //Integer 是 Number的子类，所以可以直接传10。但是Echo<Integer>不是Echo<Number>的子类
        numberEcho.echo(10);
        numberEcho.echo(10d);
        numberEcho.echo(10f);
        numberEcho.echo(10L);
        //这里下面四行会报错，can't resolve method 'echo java.Generics.Echo<java.lang.Integer>'
        //原因是numberEcho中泛型类型是<Number>,Integer虽然继承Nunber,但是Echo<Integer>并不继承Echo<Number>
        numberEcho.echo(new Echo<Integer>());
        numberEcho.echo(new Echo<Double>());
        numberEcho.echo(new Echo<Float>());
        numberEcho.echo(new Echo<Long>());
    }
}

泛型的这个特征我们把它叫做invariant的。这一点和数组是反着的，数组我们叫covariant.因为我们学数组的时候都知道，如果A继承数组B,那么A类型的数组也可以在多态中替代B类型的数组。无论S与T有什么联系，echo~~与echo都没有什么联系。~~

在非泛型类中也可以使用泛型方法

public class ArrayAlg {
    public static void main(String[] args) {
        String middle= ArrayAlg.<String> getMiddle("John","Q.","Public");
        System.out.println(middle);
    }
    public static <T> T getMiddle(T...a){
        return a[a.length/2];
    }
}

在泛型中，一个泛型类型可以被多个条件约束。

//下面T可以实现多个接口，但是只能继承一个类
public class MultipleBounds<T extends Number &Comparable& Serializable> {
    private final T number;
    public MultipleBounds(T number){
        this.number=number;
    }

    public T getNumber(){
        return number;
    }

}

在泛型中，泛型类型可以被其他泛型类型约束

//下面如果T是String这种没有子类的类型,那么S只能是String
public class BoundedGenericTypes<T,S extends T> {
    private final T value;
    private final S subValue;
    public BoundedGenericTypes(T value,S subValue){
        this.value=value;
        this.subValue=subValue;
    }

    public T getValue(){
        return value;
    }

    public S getSubValue(){
        return subValue;
    }
}

这里插入一个小考题，下面这段代码会被编译通过吗？

1
2
3

public class GenericsAreNotStatic<T>{
    private static T reference;
}

答案是不行，因为静态成员是所有类成员公用的，你在这里制定静态成员是泛型的。那么加入我们的对象中一个T取的是String,另一个T取的是Integer,这里就无法确定reference的类型了。

接下来我们看看泛型特征的第五条，泛型类型会在编译时被擦除。那么我们的java编译器是如何处理泛型的呢？
实际上编译器就是帮我们加上了强制类型转换

public class RuntimeGenerics<T> {
    public static void main(String[] args) {
        RuntimeGenerics<Number> runtimeGenericNumber=new RuntimeGenerics<Number>(10);
        //compiler inserts the following
        //Number numberValue=(Number) runtimeGenericNumber.getValue();
        Number numberValue=runtimeGenericNumber.getValue();
    }

    private final T value;
    public RuntimeGenerics(T value){
        this.value=value;
    }

    public T getValue(){
        return value;
    }
}

由于泛型类型会在编译时被擦除，那么我们可以得到以下几条结论
1.泛型类型的尖括号里不能是基础数据类型（不能在运行时将基础数据类型转换为其autobox后的类型）
2.不能用instance of 来对泛型进行类型检查（instance of 是运行时进行检查）
顺带提一下，getClass总是返回原始类型。例如：
Pair stringPair=…
Pair empolyeePair=…;
if(stringPair.getClass()==employeePair.getClass())//they are equal
比较的结果是true,因为getClass只返回原始类型Pair
3.不能抛出或捕获泛型类的实例（原因同上）
4.不能使用带泛型类型的array(前面提过，array是covariant,generic type是invariant的)

接下来我们看看泛型的继承

public class GenericClass<T> {
    private final T value;
    public GenericClass(T value){
        this.value=value;
    }

    public T getValue(){
        return value;
    }
}

//extends GenericClass<T>这个<T>一定不能少，否则编译器将用object取代T
public class SubGenericClass<T> extends GenericClass<T> {
    public SubGenericClass(T value){
        super(value);
    }
    @Override
    public T getValue(){
        return  super.getValue();
    }
}

接下来我们来聊java泛型中的重点，通配符。
我们还是先来看一个例子来看看没有通配符会发生什么。

public class GiftPrinter {
    public static void main(String[] args) {
        Gift<Computer> computerGift=new Gift<>(new Computer(),1500d);
        GiftPrinter printer=new GiftPrinter();
        //编译器报错：print Gift<Object> can't be applied to Gift<Computer>
        //虽然Gift 继承自Object,但是显然编译器并不认为Gift<Computer>与Gift<Object>有任何关系
        printer.print(computerGift);
    }
    public void print(Gift<Object> gift){
        System.out.printf("%s%n",gift);
    }
}

那么这个时候通配符的作用就出现了，我们用通配符重写print方法
public void print(Gift<?> gift){
System.out.printf(“%s,%n”,gift);
}
通配符的意思是说我不管你Gift<>尖括号里装什么东西，编译器你都让它通过。

关于通配符有下面一点要注意：
通配符只能用于实例上（不能用于class或者method）
比如，我们不能写 public Class Type,public void methodName()
而这样写就是可以的：public void methodName(Gift<?> gift)

上面的例子中通配符是没有限定条件的，但是我们也可以给通配符加上限定条件，请看下面代码

public class BoundedWildCard {
    public void subClasses(Gift<? extends Number> gift){

    }

    public void superClasses(Gift<? super Integer> gift){
        
    }
}

剑指offer004 逆向打印链表

Posted on 2019-10-31 In 剑指offer Valine:

Problem:

从尾到头反过来打印出链表中每个结点的值。

Intuition:

所有逆序的操作都应该想到 stack 这个先进后出的数据结构

1.建立一个辅助栈 stack 和一个存储结构 ArrayList
2.将原来链表中的值一个个 push到 stack中
3.将 stack中存储的值一个个 pop 到 ArrayList

Solution:


public class CodingInterview_004 {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        Stack<Integer> stack = new Stack<>();
        while (listNode != null) {
            stack.add(listNode.val);
            listNode = listNode.next;
        }
        ArrayList<Integer> ret = new ArrayList<>();
        while (!stack.isEmpty())
            ret.add(stack.pop());
        return ret;
    }
}

剑指offer003 替换空格

Posted on 2019-10-31 In 剑指offer Valine:

Problem:

将一个字符串中的空格替换成 “%20”。
只能在当前字符串内进行操作，不允许新建字符串。

Input:
“A B”

Output:
“A%20B”

Intuition:

在字符串尾部填充任意字符，使得字符串的长度等于替换之后的长度。因为一个空格要替换成三个字符（%20），因此当遍历到一个空格时，需要在尾部填充两个任意字符。

令 P1 指向字符串原来的末尾位置，P2 指向字符串现在的末尾位置。P1 和 P2 从后向前遍历，当 P1 遍历到一个空格时，就需要令 P2 指向的位置依次填充 02%（注意是逆序的），否则就填充上 P1 指向字符的值。

从后向前遍是为了在改变 P2 所指向的内容时，不会影响到 P1 遍历原来字符串的内容。

Solution:

 public class CodingInterview_003 {

    public String replaceSpace(StringBuffer str) {
        int P1 = str.length() - 1;
        for (int i = 0; i <= P1; i++)
            if (str.charAt(i) == ' ')
                str.append("  ");

        int P2 = str.length() - 1;
        while (P1 >= 0 && P2 > P1) {
            char c = str.charAt(P1--);
            if (c == ' ') {
                str.setCharAt(P2--, '0');
                str.setCharAt(P2--, '2');
                str.setCharAt(P2--, '%');
            } else {
                str.setCharAt(P2--, c);
            }
        }
        return str.toString();
    }
}

数据链路层

Posted on 2019-10-30 Edited on 2019-11-19 In 计算机网络 Valine:

CSMA/CD

为什么要有CSMA/CD？
CSMA/CD就是解决在有多个主机占据同一条信道的情况下如何来分配信道资源的问题。在CSMA/CD这个协议下，站点在发送数据之前需要先监听信道。如果信道空闲，站点就可以发送数据；如果信道忙，则站点不能发送数据。

CSMA/CD 表示载波监听多点接入 / 碰撞检测。

多点接入：说明这是总线型网络，许多主机以多点的方式连接到总线上。
载波监听：每个主机都必须不停地监听信道。在发送前，如果监听到信道正在使用，就必须等待。
碰撞检测：在发送中，如果监听到信道已有其它主机正在发送数据，就表示发生了碰撞。虽然每个主机在发送数据之前都已经监听到信道为空闲，但是由于电磁波的传播时延的存在，还是有可能会发生碰撞。
记端到端的传播时延为 τ，最先发送的站点最多经过 2τ 就可以知道是否发生了碰撞，称 2τ 为争用期。只有经过争用期之后还没有检测到碰撞，才能肯定这次发送不会发生碰撞。

当发生碰撞时，站点要停止发送，等待一段时间再发送。这个时间采用截断二进制指数退避算法来确定。从离散的整数集合 {0, 1, .., (2k-1)} 中随机取出一个数，记作 r，然后取 r 倍的争用期作为重传等待时间。

MAC地址

MAC 地址是链路层地址，长度为 6 字节（48 位），用于唯一标识网络适配器（网卡）。

一台主机拥有多少个网络适配器就有多少个 MAC 地址。例如笔记本电脑普遍存在无线网络适配器和有线网络适配器，因此就有两个 MAC 地址。

虚拟局域网（VLAN）

虚拟局域网可以建立与物理位置无关的逻辑组，只有在同一个虚拟局域网中的成员才会收到链路层广播信息。

例如下图中 (A1, A2, A3, A4) 属于一个虚拟局域网，A1 发送的广播会被 A2、A3、A4 收到，而其它站点收不到。

使用 VLAN 干线连接来建立虚拟局域网，每台交换机上的一个特殊接口被设置为干线接口，以互连 VLAN 交换机。IEEE 定义了一种扩展的以太网帧格式 802.1Q，它在标准以太网帧上加进了 4 字节首部 VLAN 标签，用于表示该帧属于哪一个虚拟局域网。

ARP协议

首先明确，ARP协议解决的是局域网内如何通过IP地址得到MAC地址的问题。

那么ARP的流程是怎么样的呢？

ARP Request，Reply里面packet里面的内容是什么？

ICMP

子网划分

Posted on 2019-10-30 In 计算机网络 Valine:

五类IP地址

这里面五类地址里面A,B,C类地址的范围以及它们分别能用的主机地址位数要记住，笔试出题很可能会只给地址类型，然后让你根据该地址类型以及主机数量进行子网划分。

无分类编址

无分类编址 CIDR 消除了传统 A 类、B 类和 C 类地址以及划分子网的概念，使用网络前缀和主机号来对 IP 地址进行编码，网络前缀的长度可以根据需要变化。

IP 地址 ::= {< 网络前缀号 >, < 主机号 >}

CIDR 的记法上采用在 IP 地址后面加上网络前缀长度的方法，例如 128.14.35.7/20 表示前 20 位为网络前缀。

CIDR 的地址掩码可以继续称为子网掩码，子网掩码首 1 长度为网络前缀的长度。

一个 CIDR 地址块中有很多地址，一个 CIDR 表示的网络就可以表示原来的很多个网络，并且在路由表中只需要一个路由就可以代替原来的多个路由，减少了路由表项的数量。把这种通过使用网络前缀来减少路由表项的方式称为路由聚合，也称为构成超网。

在路由表中的项目由“网络前缀”和“下一跳地址”组成，在查找时可能会得到不止一个匹配结果，应当采用最长前缀匹配来确定应该匹配哪一个。

子网划分规则

通过在主机号字段中拿一部分作为子网号，把两级 IP 地址划分为三级 IP 地址。

IP 地址 ::= {< 网络号 >, < 子网号 >, < 主机号 >}

要使用子网，必须配置子网掩码。一个 B 类地址的默认子网掩码为 255.255.0.0，如果 B 类地址的子网占两个比特，那么子网掩码为 11111111 11111111 11000000 00000000，也就是 255.255.192.0。

注意，外部网络看不到子网的存在。

子网例题

例题1:欲将B类IP地址168.195.0.0划分成27个子网。（方法一、利用子网数来计算）

公式：2^n-2≥x，其中x为所需的子网数，n为所需借的子网位数。
168.195.00000000.00000000
从原来的主机部分开始，从前向后借子网位。
该例中需27个子网，按公式，需借5位，可划分出如下子网：
168.195.00000 000.00000000
168.195.00001 000.00000000
168.195.00010 000.00000000
……
168.195.11110 000.00000000
168.195.11111 000.00000000
共2^5=32个子网，其中有效子网30个，掩码均为/21。

例题2:如需将某C类地址划分20个子网，问第三个有效子网的网络地址、主机地址范围和广播地址？

解决步骤：
1、需20个子网，则需子网位为5，剩余主机位为3，子网的大小为8。
2、8*3=24，则第三个有效子网的地址为24/29。（第一问）这个29=24+5
3、24+8=32，下一个子网的地址为32/29。
4、广播地址为后一个子网的网络地址减1，为31。（第三问）
5、主机地址范围为25至30。

计算机网络基础

Posted on 2019-10-30 In 计算机网络 Valine:

主机间的通信方式（两类）

客户-服务器（C/S）：客户是服务的请求方，服务器是服务的提供方。
对等（P2P）：不区分客户和服务器

主机A与主机B如何通过internet相连？

ISP: interconnected internet service providers

如何将域名转换为IP地址？

首先，我们把域名转换为ip地址的软件系统叫做域名服务器，所有来自浏览器的文档请求都被发送到最近的域名服务器。该域名服务器将尝试将完全限定域名转换为IP地址。如果可以，则进行转换。否则，该服务器将这个完全限定域名发送给另外的域名服务器来实现转换操作。

计算机网络体系结构

Posted on 2019-10-30 In 计算机网络 Valine:

计算机网络体系结构（OSI模型）

应用层：为特定应用程序提供数据传输服务，例如 HTTP、DNS 等协议。数据单位为报文。
Key words: representation /encoding /session control

表示层：数据压缩、加密以及数据描述，这使得应用程序不必关心在各台主机中数据内部格式不同的问题。

会话层：建立及管理会话。

传输层：为进程提供通用数据传输服务。由于应用层协议很多，定义通用的传输层协议就可以支持不断增多的应用层协议。运输层包括两种协议：传输控制协议 TCP，提供面向连接、可靠的数据传输服务，数据单位为报文段；用户数据报协议 UDP，提供无连接、尽最大努力的数据传输服务，数据单位为用户数据报。TCP 主要提供完整性服务，UDP 主要提供及时性服务。
Key words: quality-of-service reliability /flow control /error correction

网络层：为主机提供数据传输服务。而传输层协议是为主机中的进程提供数据传输服务。网络层把传输层传递下来的报文段或者用户数据报封装成分组。
Key words: path determination /packet switching /IP

数据链路层：网络层针对的还是主机之间的数据传输服务，而主机之间可以有很多链路，链路层协议就是为同一链路的主机提供数据传输服务。数据链路层把网络层传下来的分组封装成帧。
Keywords: host-to-network /LAN and WAN technology detail

物理层：考虑的是怎样在传输媒体上传输数据比特流，而不是指具体的传输媒体。物理层的作用是尽可能屏蔽传输媒体和通信手段的差异，使数据链路层感觉不到这些差异。

数据在各层之间的传递

在向下的过程中，需要添加下层协议所需要的首部或者尾部，而在向上的过程中不断拆开首部和尾部。

路由器只有下面三层协议，因为路由器位于网络核心中，不需要为进程或者应用程序提供服务，因此也就不需要传输层和应用层