2020-10-28

学习过程中一些网站的收藏

Bookmarks

Bookmarks bar 算法 (3条未读私信) 全部动态_牛客网 力扣 (LeetCode) 官网 - 全球极客挚爱的技术成长平台 https://mp.weixin.qq.com/mp/homepage?__biz=MzI4Njc4MzMwMw==&hid=1&sn=58bf8e995138b26984c05fd51f198196

算法

剑指offer 26-35

26. 二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。

public class Solution {
    TreeNode head;
    TreeNode cur;
    public TreeNode Convert(TreeNode root) {
        if(root==null){
            return root;
        }
        inorder(root);
        return head;
    }
    private void inorder(TreeNode root){
        Stack<TreeNode> stack=new Stack<>();
        while(root!=null||!stack.isEmpty()){
            while(root!=null){
                stack.push(root);
                root=root.left;
            }
            root=stack.pop();
            if(head==null){
                head=root;
                cur=root;
            }else{
                cur.right=root;
                root.left=cur;
                cur=cur.right;
            }
            root=root.right;
        }
    }
}

27.字符串的排列

输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则按字典序打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。

public class Solution {
    TreeSet<String> res=new TreeSet<>();
    ArrayList<Character> list=new ArrayList<>();
    boolean[] used;
    public ArrayList<String> Permutation(String str) {
       if(str==null||str.length()==0){
           return new ArrayList<>();
       }
        used=new boolean[str.length()];
       help(str.toCharArray(),0);
       return new ArrayList<>(res);
    }
    private void help(char[] c,int index){
        if(index==c.length){
            StringBuffer sb=new StringBuffer();
            for(char cs:list){
                sb.append(cs);
            }
            res.add(sb.toString());
            return;
        }
        for(int i=0;i<c.length;i++){
            if(used[i]){
                continue;
            }
            used[i]=true;
            list.add(c[i]);
            help(c,index+1);
            list.remove(list.size()-1);
            used[i]=false;
        }
    }
}

28.数组中出现次数超过一半的数字

数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int count=0;
        int candidate=0;
        int len=array.length;
        if(len==0){
            return 0;
        }
        for(int i=0;i<len;i++){
            if(count==0){
                candidate=array[i];
                count++;
            }else{
                if(candidate==array[i]){
                    count++;
                }else{
                    count--;
                }
            }
        }
        if(count==0){
            return 0;
        }
        count=0;
        for(int n:array){
            if(candidate==n){
                count++;
            }
        }
        return count>len/2?candidate:0;
    }
}

29.最小的k个数

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。

public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        if(input.length<k||k<=0){
            return new ArrayList<>();
        }
        PriorityQueue<Integer> queue=new PriorityQueue<>(new Comparator<Integer>(){
            public int compare(Integer a,Integer b){
                return b-a;
            }
        });
        for(int i=0;i<input.length;i++){
            if(i<k){
                queue.add(input[i]);
            }else{
                if(queue.peek()>input[i]){
                    queue.poll();
                    queue.add(input[i]);
                }
            }
        }
        return new ArrayList<>(queue);
    }
}

30.连续子数组的最大和

返回最大连续子序列的和

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int max=array[0];
        int res=array[0];
        for(int i=1;i<array.length;i++){
            max=Math.max(max+array[i],array[i]);
            res=Math.max(res,max);
        }
        return res;
    }
}

31.整数中1出现的次数

求出1~~13的整数中1出现的次数,并算出100~~1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

public class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int count=0;
        for(int m=1;m<=n;m*=10){
            int a=n/m;
            int b=n%m;
            count+=(a+8)/10*m+(a%10==1?b+1:0);
        }
        return count;
    }
}

32.把数组排成最小的数

输入一个正整数数组，把数组里所有数字拼接起来排成一个数，打印能拼接出的所有数字中最小的一个。例如输入数组{3，32，321}，则打印出这三个数字能排成的最小数字为321323。

public class Solution {
    public String PrintMinNumber(int [] numbers) {
        int len=numbers.length;
        if(len==0){
            return "";
        }
        Integer[] arr=new Integer[len];
        int index=0;
        for(int n:numbers){
            arr[index++]=n;
        }
        Arrays.sort(arr,new Comparator<Integer>(){
            public int compare(Integer a,Integer b){
                return (a+""+b).compareTo(b+""+a);
            }
        });
        StringBuffer sb=new StringBuffer();
        for(Integer a:arr){
            sb.append(a);
        }
        return sb.toString();
    }
}

33.丑数

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

public class Solution {
    public int GetUglyNumber_Solution(int index) {
        if(index<1){
            return 0;
        }
        int[] dp=new int[index];
        dp[0]=1;
        int a=0;
        int b=0;
        int c=0;
        for(int i=1;i<index;i++){
            dp[i]=Math.min(dp[a]*2,Math.min(dp[b]*3,dp[c]*5));
            if(dp[i]==dp[a]*2){
                a++;
            }
            if(dp[i]==dp[b]*3){
                b++;
            }
            if(dp[i]==dp[c]*5){
                c++;
            }
        }
        return  dp[index-1];
    }
}

34.第一次只出现一次的字符

在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）

public class Solution {
     
    public int FirstNotRepeatingChar(String str) {
        int[] arr=new int[128];
        char[] cs=str.toCharArray();
        for(char p:cs){
            arr[p]++;
        }
        for(int i=0;i<cs.length;i++){
            if(arr[cs[i]]==1){
                return i;
            }
        }
        return -1;
    }
}

35.数组中的逆序对

在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组,求出这个数组中的逆序对的总数P。并将P对1000000007取模的结果输出。即输出P%1000000007

public class Solution {
    public int InversePairs(int [] array) {
        if(array == null || array.length == 0) {
            return 0;
        }
        return mergesort(array, 0, array.length - 1);
    }
 
private int mergesort(int[] arr, int l, int r) {
    if(l >= r) {
        return 0;
    }
    int mid = l + (r - l) / 2;
    return (mergesort(arr, l, mid) + mergesort(arr, mid + 1, r) + merge(arr, l, mid, r)) % 1000000007;
}
 
    private int merge(int[] arr, int l, int mid ,int r) {
        int[] help = new int[r - l + 1];
        int p = l;
        int q = mid + 1;
        int index = 0;
        int sum = 0;
        while(p <= mid && q <= r) {
            if(arr[p] <= arr [q]) {
                help[index++] = arr[p++];
            }else if( arr[p] > arr[q]){
                sum = (sum + mid - p + 1) % 1000000007;
                help[index++] = arr[q++];
            }
        }
        while(p <= mid) {
            help[index++] = arr[p++];
        }
        while( q <= r) {
            help[index++] = arr[q++];
        }
        for(int i = l; i <= r; i++) {
            arr[i] = help[i - l];
        }
        return sum % 1000000007;
    }
}

2020-10-20

算法

剑指offer 16-25

16. 合并两个有序链表

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

public class Solution {
    public ListNode Merge(ListNode list1, ListNode list2) {
        ListNode head = new ListNode(0);
        ListNode p = head;
        while (list1 != null && list2 != null) {
            if (list1.val <= list2.val) {
                p.next = list1;
                list1 = list1.next;
            } else {
                p.next = list2;
                list2 = list2.next;
            }
            p = p.next;
        }
        if (list1 != null) {
            p.next = list1;
        }
        if (list2 != null) {
            p.next = list2;
        }
        return head.next;
    }
}

17.树的子结构

输入两棵二叉树A，B，判断B是不是A的子结构。（ps：我们约定空树不是任意一个树的子结构）

public class Solution {
    public boolean HasSubtree(TreeNode root1, TreeNode root2) {
        if (root1 == null || root2 == null) {
            return false;
        }
        return help(root1, root2) || HasSubtree(root1.left, root2) || HasSubtree(root1.right, root2);
    }
    private boolean help(TreeNode root1, TreeNode root2) {
        if (root2 == null) {
            return true;
        }
        if (root1 == null) {
            return false;
        }
        if (root1.val != root2.val) {
            return false;
        }
        return help(root1.left, root2.left) && help(root1.right, root2.right);
    }
}

18.二叉树的镜像

操作给定的二叉树，将其变换为源二叉树的镜像。

public class Solution {
    public void Mirror(TreeNode root) {
        if (root == null) {
            return;
        }
        TreeNode tmp = root.left;
        root.left = root.right;
        root.right = tmp;
        Mirror(root.left);
        Mirror(root.right);
    }
}

19.顺时针打印矩阵

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

import java.util.ArrayList;
public class Solution {
    public ArrayList<Integer> printMatrix(int [][] matrix) {
        ArrayList<Integer> res=new ArrayList<>();
       int m=matrix.length;
        if(m==0){
            return res;
        }
        int n=matrix[0].length;
        int left=0;
        int right=n-1;
        int up=0;
        int down=m-1;
        while(true){
            for(int i=left;i<=right;i++){
                res.add(matrix[up][i]);
            }
            if(++up>down){
                break;
            }
            for(int i=up;i<=down;i++){
                res.add(matrix[i][right]);
            }
            if(--right<left){
                break;
            }
            for(int i=right;i>=left;i--){
                res.add(matrix[down][i]);
            }
            if(--down<up){
                break;
            }
            for(int i=down;i>=up;i--){
                res.add(matrix[i][left]);
            }
            if(++left>right){
                break;
            }
        }
        return res;
    }
}

20.包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。

public class Solution {
 
    Stack<Integer> stack=new Stack<>();
    Stack<Integer> min=new Stack<>();
    public void push(int node) {
        stack.push(node);
        if(min.isEmpty()||min.peek()>=node){
            min.push(node);
        }else{
            min.push(min.peek());
        }
    }
     
    public void pop() {
        if(stack.isEmpty()&&min.isEmpty()){
            return;
        }
        stack.pop();
        min.pop();
    }
     
    public int top() {
        if(stack.isEmpty()&&min.isEmpty()){
            return -1;
        }
        return stack.peek();
    }
     
    public int min() {
        if(stack.isEmpty()&&min.isEmpty()){
            return -1;
        }
        return min.peek();
    }
}

21.栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）

public class Solution {
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        int index=0;
      Stack<Integer> stack = new Stack<>();
        for(int i=0;i<pushA.length;i++){
            stack.push(pushA[i]);
            while(!stack.isEmpty()&&(stack.peek()==popA[index])){
                stack.pop();
                index++;
            }
        }
        return stack.isEmpty();
    }
}

22.从上往下打印二叉树

从上往下打印出二叉树的每个节点，同层节点从左至右打印。

public class Solution {
    public ArrayList<Integer> PrintFromTopToBottom(TreeNode root) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        if(root==null){
            return res;
        }
        Queue<TreeNode> queue=new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            int size=queue.size();
            for(int i=0;i<size;i++){
                TreeNode node=queue.poll();
                res.add(node.val);
                if(node.left!=null){
                    queue.add(node.left);
                }
                if(node.right!=null){
                    queue.add(node.right);
                }
            }
        }
        return res;
    }
}

23.二叉搜索树的后序遍历序列

输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则返回true,否则返回false。假设输入的数组的任意两个数字都互不相同。

public class Solution {
    public boolean VerifySquenceOfBST(int [] sequence) {
        int len=sequence.length;
        if(len==0){
            return false;
        }
        return help(sequence,0,len-1);
    }
     
    private boolean help(int[] sequence,int l,int r){
        if(l>=r){
            return true;
        }
        int key=sequence[r];
        int i=l;
        for(;i<r;i++){
            if(sequence[i]>key){
                break;
            }
        }
        for(int j=i;j<r;j++){
            if(sequence[j]<key){
                return false;
            }
        }
        return help(sequence,l,i-1)&&help(sequence,i+1,r);
    }
}

24.二叉树中和为某一值的路径

输入一颗二叉树的根节点和一个整数，按字典序打印出二叉树中结点值的和为输入整数的所有路径。路径定义为从树的根结点开始往下一直到叶结点所经过的结点形成一条路径。

public class Solution {
    ArrayList<ArrayList<Integer>> res=new ArrayList<>();
    ArrayList<Integer> list = new ArrayList<>();
    public ArrayList<ArrayList<Integer>> FindPath(TreeNode root,int target) {
        if(root==null){
            return res;
        }
        help(root,target);
        return res;
    }
     
    private void help(TreeNode root,int target){
        if(root==null){
            return;
        }
        target-=root.val;
        list.add(root.val);
        if(root.left==null&&root.right==null&&target==0){
            res.add(new ArrayList<>(list));
        }
        help(root.left,target);
        help(root.right,target);
        list.remove(list.size()-1);
    }
}

25.复杂链表的复制

输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针random指向一个随机节点），请对此链表进行深拷贝，并返回拷贝后的头结点。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）

public class Solution {
    public RandomListNode Clone(RandomListNode head)
    {
        if(head==null){
            return head;
        }
        Map<RandomListNode,RandomListNode>map=new HashMap<>();
        RandomListNode cur=head;
        while(cur!=null){
            map.put(cur,new RandomListNode(cur.label));
            cur=cur.next;
        }
        cur=head;
        while(cur!=null){
            RandomListNode p=map.get(cur);
            p.next=map.get(cur.next);
            p.random=map.get(cur.random);
            cur=cur.next;
        }
        return map.get(head);
    }
}

2020-10-16

零拷贝（Zero-copy）学习

概念

零拷贝（Zero-copy）是一种高效的数据传输机制，是指计算机执行操作时，CPU不需要先将数据从某处内存复制到另一个特定区域

传统IO传输方法

public static void main(String[] args) throws IOException {
    File file = new File("test.txt");
    RandomAccessFile accessFile = new RandomAccessFile(file, "rw");
    byte[] arr = new byte[(int) file.length()];
    accessFile.read(arr);
    Socket socket = new ServerSocket(6666).accept();
    socket.getOutputStream().write(arr);
}

从操作系统层面来看这一次传输操作

1.JVM向OS发出read()系统调用，触发上下文切换，从用户态切换到内核态。

2.从外部存储（如硬盘）读取文件内容，通过直接内存访问（DMA）存入内核地址空间的缓冲区。

3.将数据从内核缓冲区拷贝到用户空间缓冲区，read()系统调用返回，并从内核态切换回用户态。

4.JVM向OS发出write()系统调用，触发上下文切换，从用户态切换到内核态。

5.将数据从用户缓冲区拷贝到内核中与目的地Socket关联的缓冲区。

6.数据最终经由Socket通过DMA传送到硬件（如网卡）缓冲区，write()系统调用返回，并从内核态切换回用户态。

上面总共是经过了4次上下文切换（严格来讲是模式切换），并且数据也被来回拷贝了4次

第2、3次拷贝（也就是从内核空间到用户空间的来回复制）是没有意义的，数据应该可以直接从内核缓冲区直接送入Socket缓冲区。零拷贝机制就实现了这一点。不过零拷贝需要由操作系统直接支持，不同OS有不同的实现方法

零拷贝

下面的零拷贝机制下的时序图。

零拷贝消除了从内核空间到用户空间的来回复制，因此“zero-copy”这个词实际上是站在内核的角度来说的，并不是完全不会发生任何拷贝。

在Java NIO包中提供了零拷贝机制对应的API，即FileChannel.transferTo()方法，可将拷贝次数变为3次，上下文切换次数减少到2次。

Scatter/Gather的优化

从“Read buffer”到“Socket buffer”，在一般的Block DMA方式中，源物理地址和目标物理地址都得是连续的，所以一次只能传输物理上连续的一块数据，每传输一个块发起一次中断，直到传输完成，所以必须要在两个缓冲区之间拷贝数据。

而Scatter/Gather DMA方式则不同，会预先维护一个物理上不连续的块描述符的链表，描述符中包含有数据的起始地址和长度。传输时只需要遍历链表，按序传输数据，全部完成后发起一次中断即可，效率比Block DMA要高。也就是说，硬件可以通过Scatter/Gather DMA直接从内核缓冲区中取得全部数据，不需要再从内核缓冲区向Socket缓冲区拷贝数据。

对内存映射（mmap）的支持

以上机制，如果想在传输时修改数据本身，就无能为力了，不过，很多操作系统也提供了内存映射机制，对应的系统调用为mmap()/munmap()。通过它可以将文件数据映射到内核地址空间，直接进行操作

但是呢，这样会造成4次上下文切换，另外，它需要在快表（TLB）中始终维护着所有数据对应的地址空间，直到刷写完成，因此处理缺页的overhead也会更大。在使用该机制时，需要权衡效率。

NIO框架中提供了MappedByteBuffer用来支持mmap。它与常用的DirectByteBuffer一样，都是在堆外内存分配空间。相对地，HeapByteBuffer在堆内内存分配空间。

参考：https://www.jianshu.com/p/193cae9cbf07

2020-10-12

操作系统

浅谈操作系统概论

计算机系统的组成
硬件：中央处理器（cpu），存储器（外存，内存），输入输出设备

操作系统

程序

2.操作系统的发展

顺序处理

简单批处理系统: 使用一个监控程序按顺序自动将作业装入内存处理

多道批处理系统：主存同时存放多个用户作业，提高效率

分时系统：将cpu的单位时间划分成若干个时间片，轮流分配给各联机用户使用

实时系统：不以作业为处理对象，而是数据或信息作为处理对象，对外部时间作出及时响应和处理

嵌入式系统

3. 操作系统的组成

进程管理，内存管理，设备管理，文件管理

4.用户于操作系统的接口（主要讲系统调用）

系统调用：通过系统调用命令，向操作系统提出资源请求或获得系统的一些功能服务

CPU的两种操作方式：用户态，内核态

系统调用命令：进程控制，文件管理，设备管理，权限管理

系统调用流程：1.通过陷入使系统切换到核心态（需要硬件支持）；2.将程序计数器和处理机的当前状态存入任务的堆栈中；3.将系统调用号存入核心堆栈中；4.执行汇编代码保持通用寄存器的内容；5. 执行相应操作系统例程来完成系统调用；6.返回到用户方式

5.操作系统的运行方式

2020-10-05

算法

剑指offer 6-15

6. 矩形覆盖

我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2n的大矩形，总共有多少种方法？

public class Solution {
    public int RectCover(int target) {
        if(target <= 2) {
            return  target;
        }
        return RectCover(target - 1) + RectCover(target - 2);
    }
}

7. 斐波那契数列

大家都知道斐波那契数列，现在要求输入一个整数n，请你输出斐波那契数列的第n项（从0开始，第0项为0，第1项是1）。n<=39

public class Solution {
    public int Fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        return Fibonacci(n - 1) + Fibonacci(n - 2);
    }
}

8. 跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级。求该青蛙跳上一个n级的台阶总共有多少种跳法（先后次序不同算不同的结果）

public class Solution {
    public int JumpFloor(int target) {
        if(target <= 2) {
            return  target;
        }
        return JumpFloor(target - 1) + JumpFloor(target - 2);
    }
}

9.变态跳台阶

一只青蛙一次可以跳上1级台阶，也可以跳上2级……它也可以跳上n级。求该青蛙跳上一个n级的台阶总共有多少种跳法。

public class Solution {
    public int JumpFloorII(int target) {
        if (target <= 2){
            return target;
        }
        return 2 * JumpFloorII(target - 1);
    }
}

10.矩形覆盖

我们可以用21的小矩形横着或者竖着去覆盖更大的矩形。请问用n个21的小矩形无重叠地覆盖一个2n的大矩形，总共有多少种方法？

public class Solution {
    public int RectCover(int target) {
        if (target <= 2) {
            return  target;
        }
        return RectCover(target - 1) + RectCover(target - 2);
         
    }
}

11.二进制中1的个数

输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。

public class Solution {
    public int NumberOf1(int n) {
        int count = 0;
        while(n != 0) {
            n = n &(n-1);
            count++;
        }
        return count;
    }
}

12.数值的整数次方

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。保证base和exponent不同时为0

public class Solution {
    public double Power(double base, int exponent) {
        if(base == 0.0) {
            return 0.0;
        }
        if(exponent == 0) {
            return 1.0;
        }
        if(exponent < 0) {
            exponent = -exponent;
            base = 1 / base;
        }
        return fastpow(base, exponent);
  }
     
    private double fastpow(double base,int exponent) {
        if(exponent == 0){
            return 1;
        }
        double half = fastpow(base, exponent / 2);
        if (exponent % 2 == 0) {
            return half * half;
        } else {
            return half * half * base;
        }
    }
}

13.调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

public class Solution {
    public void reOrderArray(int [] array) {
        int i = 0;
        while (i < array.length) {
            while (array[i] % 2 == 1) {
                i++;
                if (i == array.length) {
                    return;
                }
            }
            int j = i;
            while (array[j] % 2 == 0) {
                j++;
                if(j == array.length) {
                    return;
                }
            }
            int tmp = array[j];
            while (j > i) {
                array[j] = array[j - 1];
                j--;
            }
            array[i] = tmp;
        }
    }
}

14.链表中倒数第k个结点

输入一个链表，输出该链表中倒数第k个结点。

public class Solution {
    public ListNode FindKthToTail(ListNode head, int k) {
        ListNode p = head;
        ListNode q = head;
        while(q != null) {
            q = q.next;
            if (--k == 0) {
                break;
            }
        }
        if (q == null && k == 0) {
            return head;
        }
        if (q == null) {
            return null;
        }
        while (q != null) {
            p = p.next;
            q = q.next;
        }
        return p;
    }
}

15.反转链表

输入一个链表，反转链表后，输出新链表的表头。

public class Solution {
    public ListNode ReverseList(ListNode head) {
        if(head == null || head.next == null) {
            return head;
        }
        ListNode pre = null;
        ListNode cur = head;
        ListNode next = null;
        while (cur != null) {
            next = cur.next;
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        return pre;
    }
}

2020-09-27

算法

剑指offer 1-5

1. 二维数组中的查找

在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。

public class Solution {
    public boolean Find(int target, int [][] array) {
        int m = array.length;
        if(m == 0) {
            return false;
        }
        int n = array[0].length;
        int i = m - 1;
        int j = 0;
        while (i >= 0 && j < n) {
            if (array[i][j] == target) {
                return true;
            } else if(array[i][j] > target) {
                i--;
            } else {
                j++;
            }
        }
        return false;
    }
}

2. 替换空格

请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。

public class Solution {
    public String replaceSpace(StringBuffer str) {
        String s = str.toString();
        StringBuffer sb = new StringBuffer();
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ' ') {
                sb.append("%20");
            } else {
                sb.append(s.charAt(i));
            }
        }
        return sb.toString();
    }
}

3. 从尾到头打印链表

输入一个链表，按链表从尾到头的顺序返回一个ArrayList。

public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode head) {
        ArrayList<Integer> res = new ArrayList<>();
        while (head != null) {
            res.add(0,head.val);
            head = head.next;
        }
        return res;
    }
}

4. 重建二叉树

输入某二叉树的前序遍历和中序遍历的结果，请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建二叉树并返回。

public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
        if (pre.length == 0) {
            return null;
        }
        int key = pre[0];
        if (pre.length != in.length) {
            return  null;
        }
        int len = pre.length;
        int i = 0;
        for (; i < len; i++) {
            if (in[i] == key) {
                break;
            }
        }
        TreeNode root = new TreeNode(key);
        root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), 
                                        Arrays.copyOfRange(in, 0, i));
        root.right=reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, len),
                                        Arrays.copyOfRange(in, i + 1, len));
        return root;
    }
}

5. 用两个栈实现队列

用两个栈来实现一个队列，完成队列的Push和Pop操作。队列中的元素为int类型。

public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
    public void push(int node) {
        stack1.push(node);
    }
    public int pop() {
        if(!stack2.isEmpty()){
            return stack2.pop();
        }else{
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
            return stack2.pop();
        }
    }
}

2020-09-19

算法

手撕KMP

之前看到一个好的KMP理解方法，记录一下

参考：https://mp.weixin.qq.com/s?__biz=Mzg2NzA4MTkxNQ==&mid=2247485979&idx=2&sn=56d4d0dd11951c29c9e6f94803d92e03&scene=21#wechat_redirect

package com.CSDN;

public class KMP {
    private int[][] dp;
    private String pat;
    public KMP(String pat){
        this.pat=pat;
        int m=pat.length();
        dp=new int[m][256];
        dp[0][pat.charAt(0)]=1;
        int X=0;
        for(int j=1;j<m;j++){
            for(int c=0;c<256;c++){
                if(pat.charAt(j)==c){
                    dp[j][c]=j+1;
                }else{
                    dp[j][c]=dp[X][c];
                }
            }
            X=dp[X][j];
        }
    }

    public int serach(String txt){
        int m=pat.length();
        int n=txt.length();
        int j=0;
        for (int i = 0; i < n; i++) {
            j=dp[j][txt.charAt(i)];
            if(j==m){
                return i-m+1;
            }
        }
        return -1;
    }

    public static void main(String[] args) {
        KMP K=new KMP("bcja");
        System.out.println(K.serach("abcjdsbcjahfksd"));

    }
}

2020-09-15

算法

动态规划-数组

两个数组最长公共子数组

public static void main(String[] args) {
        int[] arr1={3,4576,768,3,35,68,7,43};
        int[] arr2={54,67,3,3,768,3,35,564};//768,3,35
        int m=arr1.length;
        int n=arr2.length;
        int[][] dp=new int[m][n];
        int start=0;
        int end=0;
        int maxlen=0;
        for (int i = 1; i <=m ; i++) {
            for (int j = 1; j <=n ; j++) {
                if(arr1[i-1]==arr2[j-1]){
                    dp[i][j]=dp[i-1][j-1]+1;
                    if(dp[i][j]>maxlen){
                        maxlen=dp[i][j];
                        start=i-maxlen;
                        end=i;
                    }
                }
            }
        }
        List<Integer> res=new ArrayList<>();
        for(int i=start;i<end;i++){
            res.add(arr1[i]);
        }
        System.out.println(res);
    }

两个数组最长公共子序列长度

public static void main(String[] args) {
    int[] arr1={1,9999,777777,3,8888888,5,7,9,33333333};
    int[] arr2={12,334,456,87,1,3,5,456,7,9,435,12};
    int m=arr1.length;
    int n=arr2.length;
    int[][] dp=new int[m+1][n+1];
    for(int i=1;i<=m;i++){
        for(int j=1;j<=n;j++){
            if(arr1[i-1]==arr2[j-1]){
                dp[i][j]=dp[i-1][j-1]+1;
            }else{
                dp[i][j]=Math.max(dp[i-1][j],dp[i][j-1]);
            }
        }
    }
    System.out.println(dp[m][n]);
}

连续子数组之和最大值

public int maxSubArray(int[] nums) {
    if(nums.length==0){
        return 0;
    }
    int sum=0;
    int res=Integer.MIN_VALUE;
    for(int i=0;i<nums.length;i++){
        sum=Math.max(sum+nums[i],nums[i]);
        res=Math.max(res,sum);
    }
    return res;
}

连续子数组乘积最大值

    int m=nums.length;
    if(m==0){
        return 0;
    }
    int max=nums[0];
    int min=nums[0];
    int res=nums[0];
    for(int i=1;i<m;i++){
        if(nums[i]<0){
            int tmp=max;
            max=min;
            min=tmp;
        }
        max=Math.max(max*nums[i],nums[i]);
        min=Math.min(min*nums[i],nums[i]);
        res=Math.max(res,max);
    }
    return res;
}

最长上升子序列

public int lengthOfLIS(int[] nums) {
    int n=nums.length;
    if(n==0){
        return 0;
    }
    int[] dp=new int[n];
    Arrays.fill(dp,1);
    for(int i=0;i<n;i++){
        for(int j=0;j<i;j++){
            if(nums[i]>nums[j]){
                dp[i]=Math.max(dp[i],dp[j]+1);
            }
        }
    }
    int res=0;
    for(int i=0;i<n;i++){
        res=Math.max(res,dp[i]);
    }
    return res;
}