刷题训练

刷题学习
1、爬楼地，获取斐波那契数列。
2、两数之和，给定一个整数，一个数组，从数组中找出两个整数，其和为目标整数，返回这两个整数的下标
3、合并两个有序数组，合并之后元素都放在数组A中，并且仍然有序（数组A中有空余位置，比如{2,3,4,8,9,0,0,0}）
4、移动0，给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序
5、找出消失的数字。给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果
6、合并两个有序链表，合并完仍然有序
7、删除有序列表中的重复节点
8、环形列表，判断一个链表是否有环
9、找到环形列表的入口，如果没有环，返回null
10、相交链表，给出两个链表，找到他们相交的节点
11、反转链表
12、判断链表是否是回文链表
13、找到链表的中间节点
14、找到链表中倒数第K个节点

刷题学习

1、爬楼地，获取斐波那契数列。

使用递归得到斐波那契数列：（1，1，2，3，5，8，13 ……….每一项是前两项的和）
（1）、使用循环，从头往后找

private static  int printFibnachi01(int num) {
    if(num == 1){
        return 1;
    }else if(num == 2){
        return 1;
    }else {
        int pre = 1;
        int ppre = 1;
        int cur = 2;
        for (int i = 3; i <= num; i++) {
            cur = pre + ppre;
            ppre = pre;
            pre = cur;
        }
        return cur;
    }
}

（2）、使用递归

private static  int printFibnachi(int num) {
    if(num == 1){
        return 1;
    }else if(num == 2){
        return 1;
    }else {
        return printFibnachi(num-1) + printFibnachi(num-2);
    }
}

（3）、使用递归,上一种方法中会有大量重复计算，比如f(20)=f(19)+f(18),然后f(19)=f(18)+f(17), 而f(18)=f(17)+f(16)，增加一个map用来存放已经找到的数，当需要找某一个值得时候，先去这个map中，如果找不到再来集合中找，这样可以节省栈内存，避免过度压栈

private static Map<Integer,Integer> resultMap = new HashMap<>();
private static  int printFibnachi(int num) {
    if(num == 1){
        resultMap.put(1,1);
        return 1;
    }else if(num == 2){
        resultMap.put(2,1);
        return 1;
    }else {
        int pre = Objects.isNull(resultMap.get(num-1))?printFibnachi(num-1):resultMap.get(num-1);
        int ppre = Objects.isNull(resultMap.get(num-2))?printFibnachi(num-2):resultMap.get(num-2);
        resultMap.put(num,ppre+pre);
        return  pre+ppre;
    }
}

总结，简单使用递归，从原理上来说，易于理解，不过栈内存开销较大，如果递归层级太大，不适合实际使用。使用for循环可以避免，不过几个变量来回变换赋值得这个操作可能会有点绕。使用递归再定义一个集合来配合使用，可以有效结合。这种借助集合来暂存数据得思路，值得借鉴。顺便说一句，在实际开发中，程序中主要是使用各种集合来整理、处理各种数据，所以集合得使用必须熟练而灵活。

力扣还有一道爬楼梯得题和这个类似，只不过我还是没有理解，它是怎么转化成f(n) = f(n-1)+f(n-2)这个过程。
1：1
2：2（1+1，2）
3：3（1+1+1，1+2，2+1）
4：5（1+1+1+1，1+1+2，1+2+1，2+1+1，2+2）
5：8（1+1+1+1+1，1+1+1+2，1+1+2+1，1+2+1+1，1+2+2，2+1+1+1，2+1+2，2+2+1）

重新理解：假设有M(大于等于3)阶台阶，一共有f(m)中走法，每次只能走1个或2个台阶，那么这M阶可能的走法就包括两部分：前面+最后剩下1个台阶，前面+最后剩下2个台阶，所以所有的走法就等于这两种可能走法的和，那么转换过来也就是f(m-1)+f(m-2)，那么同理f(m-1) = f(m-2)+f(m-3),如此使用递归的思想,直到m=2和m=1。

2、两数之和，给定一个整数，一个数组，从数组中找出两个整数，其和为目标整数，返回这两个整数的下标

解法一：两层for循环，挨个遍历

private static int[] getTargetIndex01(int target, int[] arr) {
    int[] result = new int[2];
    for (int i = 0; i < arr.length - 1; i++) {
        for (int j = i+1; j < arr.length; j++) {
            if(arr[i] + arr[j] == target){
                result[0] = i;
                result[1] = j;
                return result;
            }
        }
    }
    return result;
}

解法二：引入一个map,遍历的同时，进行判断。遍历数组，得到目标值和当前数的差值，拿这个差值去map中查，如果找不到，把当前值带下标(key是值，value下标)存入map，如果有，那么这个值和当前值就是要找的两个数。时间复杂度O(n)？应该会多一点吧，因为存入map和从map中获取也需要时间。数据量大的时候应该效果比较明显。
这个方法在于巧妙的引入一个外部结构来记录已经遍历过的数据，不需要重复遍历。这种思维需要好好学习。

int target = 14;
int[] arr = new int[]{2,5,2,6,4,8};
int[] re = new int[2];
Map<Integer,Integer> map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
    int temp = target - arr[i];
    if(Objects.isNull(map.get(temp))){
        map.put(arr[i],i);
    }else {
        re[0] = map.get(temp);
        re[1] = i;
    }
}

3、合并两个有序数组，合并之后元素都放在数组A中，并且仍然有序（数组A中有空余位置，比如{2,3,4,8,9,0,0,0}）

解法一：将数组B中的元素放入数组A，然后直接利用Arrays.sort()的方法，sort()的底层使用的是快速排序，使用快速排序本身是挺快的，这种情况下使用，并不是最好，因为数组原本就是有序的，这样没有把这个有序的特点利用起来。

int[] arrA = new int[]{2,3,4,8,9,0,0,0};
int[] arrB = new int[]{1,4,5};
//找到数组A最后一个有效元素
int indexA = 0;
for (int i = 0; i < arrA.length; i++) {
    if(arrA[i] == 0){
        indexA = i;
        break;
    }
}
//将B中的元素合并到A中
for (int i = 0; i < arrB.length; i++) {
    arrA[indexA+i] = arrB[i];
}
Arrays.sort(arrA);
for (int i : arrA) {
    System.out.print(i+" ");
}

解法二：借助一个辅助数组，使用两个指针，分别对两个数组开始从头遍历，并进行比较，较小的元素放入新数组中，最后再把新数组的元素放入数组A中。需要注意的是，在第一个while循环结束时，两个数组中有一个的元素还没有完全放入新数组，所以还需要进行判断一下，把剩下的元素放入新数组

int[] arrA = new int[]{2,3,4,8,9,0,0,0};
int[] arrB = new int[]{1,4,5};
int indexA = 0;
for (int i = 0; i < arrA.length; i++) {
    if(arrA[i] == 0){
        indexA = i;
        break;
    }
}
//定义辅助数组和指针
int[] temp = new int[arrA.length];
int a = 0;
int b = 0;
int c = 0;
while (a<=indexA-1 && b<=arrB.length-1){
    if(arrA[a]<=arrB[b]){
        temp[c++] = arrA[a++];
    }else {
        temp[c++] = arrB[b++];
    }
}
while (a<indexA){
    temp[c++] = arrA[a++];
}
while (b<arrB.length){
    temp[c++] = arrB[b++];
}
for (int i = 0; i < temp.length; i++) {
    arrA[i] = temp[i];
}

解法三：解法二的时间复杂度有所提升，但是因为借助了一个辅助数组，所以空间复杂度就大了，这个题有一个特殊要求，就是排序后需要把元素放入数组A，所以可以借助这一点，因为数组A前面的元素是有序的，而后面都是0，后面0的个数又刚好等于数组B的个数。所以采用一种新思路，从后往前遍历两个数组，然后从大到小倒着排列所有的数，也是倒着放入数组A。因为数组A后面都是0，那么吧A和B比较之后较大的元素，依次放入。

int[] arrA = new int[]{2,3,4,8,9,0,0,0};
int[] arrB = new int[]{1,4,5};
int indexA = 0;
for (int i = 0; i < arrA.length; i++) {
    if(arrA[i] == 0){
        indexA = i;
        break;
    }
}
int a = indexA -1;
int b = arrB.length -1;
int c = arrA.length-1;
int[] temp = new int[arrA.length];
while (a>=0 && b>=0){
    if(arrA[a]>=arrB[b]){
        temp[c--] = arrA[a--];
    }else {
        temp[c--] = arrB[b--];
    }
}
while (a>=0){
    temp[c--] = arrA[a--];
}
while (b>=0){
    temp[c--] = arrB[b--];
}
for (int i = 0; i < temp.length; i++) {
    arrA[i] = temp[i];
}

4、移动0，给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序

解法一

    private static void moveZeroes(int[] nums) {
        if (nums == null) {
            return;
        }
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if(nums[i] != 0){
               nums[j] = nums[i];
               j++;
            }
        }
        for (int i=j;i<nums.length;i++){
            nums[i] = 0;
        }
    }

解法二：思想与上面类似，关键点还是在于使用两个指针分别指向0和非0元素

    private static void moveZeroes(int[] nums) {
        if (nums == null) {
            return;
        }
        int j = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != 0) {
                int tmp = nums[i];
                nums[i] = nums[j];
                nums[j++] = tmp;
            }
        }
    }

5、找出消失的数字。给你一个含 n 个整数的数组 nums ，其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字，并以数组的形式返回结果

方法一：定义一个大小为N的辅助数组，元素为布尔类行，默认为false,
遍历数据，得到的元素，将这个值作为下标，更新对应辅助数组这个下标的元素状态为true
遍历辅助数组，元素为false的元素就是消失的数字，返回下标

int[] arr = new int[]{1,4,2,4,8,8,8,8};
//得到结果
Object[] re = findLostNum(arr);
for (Object o : re) {
    System.out.println(o);
}
//方法：
private Object[] findLostNum(int[] arr) {
    boolean[] temp = new boolean[arr.length];
    for (boolean b : temp) {
        b = false;
    }
    for (int i : arr) {
        temp[i-1] = true;
    }
    List<Integer> re = new ArrayList<>();
    for (int i = 1; i < temp.length ; i++) {
        if(!temp[i-1]){
            re.add(i);
        }
    }
    return re.toArray();
}

方法二：利用本数组，元素与下标的关系，遍历数组，得到每一个元素，
把这个元素的值当做下标，操作对应位置的元素，把这个位置的元素设置为负数，判断一个如果为正，就加个负号
遍历完成之后，元素仍然为正的位置下标值就是数组中没有的数字

int[] arr = new int[]{1,4,2,4,8,8,8,8};
//得到结果
Object[] re = findLostNum(arr);
for (Object o : re) {
    System.out.println(o);
}
//方法
private Object[] findLostNum(int[] arr) {
    for (int i : arr) {
        int temp = i;
        if(i<0){
            temp = -i;
        }
        if(arr[temp-1] >0){
            arr[temp-1] = -arr[temp-1];
        }
    }
    List<Integer> re = new ArrayList<>();
    for (int i = 1; i < arr.length ; i++) {
        if(arr[i-1] > 0){
            re.add(i);
        }
    }
    return re.toArray();
}

6、合并两个有序链表，合并完仍然有序

方法：

private Node mergeLinkList(Node node14, Node node04) {
        //合并两个有序链表
        Node result = new Node();
        Node re = result;
        Node a = node04;
        Node b = node14;
        //循环比较
        while (a != null && b != null){
            if(a.getValue()>=b.getValue()){
                re.setNext(a);
                a = a.getNext();
            }else {
                re.setNext(b);
                b = b.getNext();
            }
            re = re.getNext();
        }
        //处理剩余节点
        if( a != null){
            re.setNext(a);
        }
        if(b != null){
            re.setNext(b);
        }
        return result.getNext();
    }

测试：

//构造有序链表
Node node01 = new Node(1,null);
Node node02 = new Node(3,node01);
Node node03 = new Node(4,node02);
Node node04 = new Node(5,node03);
Node node11 = new Node(5,null);
Node node12 = new Node(5,node11);
Node node13 = new Node(6,node12);
Node node14 = new Node(7,node13);
//调用方法
Node node = mergeLinkList(node14, node04);
//测试
while (node != null){
    System.out.println(node.getValue());
    node = node.getNext();
}

7、删除有序列表中的重复节点

方法：

private Node deleteRepeatNode(Node node){
    if(node == null){
        return null;
    }
    //遍历链表节点，定义一个当前节点，如果当前节点的值与下一个节点的值相等，就直接将当前节点指向下一个节点的下一个节点
    Node cur = node;
    while (node != null){
        if(node.getValue().equals(node.getNext().getValue())){
            node.setNext(node.getNext().getNext());
        }
    }
    return cur;
}

测试：

void linkSortTest(){
    //构造有序链表
    Node node11 = new Node(5,null);
    Node node12 = new Node(5,node11);
    Node node13 = new Node(6,node12);
    Node node14 = new Node(6,node13);
    Node node15 = new Node(7,node14);
    Node result = deleteRepeatNode(node15);
    while (result != null){
        System.out.println(result.getValue());
        result = result.getNext();
    }
}

这里的Node类中的属性修饰符使用了private，如果使用public修饰，其实就不需要get(),set()方法。通常这种方法应该是和Node类在同一个文件下，这样方便操作，这种方法也是类似于工具类的方法

8、环形列表，判断一个链表是否有环

方法：

private Boolean cycle(Node node01) {
    if(node01 == null){
        return false;
    }
    Node slow = node01;
    Node fast = node01.next;
    while (slow.next != null && fast.next.next != null){
        if(slow == fast){
            return true;
        }
        slow = slow.next;
        fast = fast.next.next;
    }
    return false;
}

测试：

void linkSortTest(){
    //构造有序链表
    Node node01 = new Node(1,null);
    Node node02 = new Node(2,null);
    Node node03 = new Node(3,null);
    Node node04 = new Node(4,null);
    Node node05 = new Node(5,null);
    Node node06 = new Node(6,null);
    Node node07 = new Node(7,null);
    node01.next = node02;
    node02.next = node03;
    node03.next = node04;
    node04.next = node05;
    node05.next = node06;
    node06.next = node07;
    node07.next = node01;
    Boolean re = cycle(node01);
    System.out.println(re);
}

9、找到环形列表的入口，如果没有环，返回null

方法：

private Node findEntrence(Node head){
    if(head == null){
        return null;
    }
    Node slow = head;
    Node fast = head;
    while (slow != null && fast.next != null){
        slow = slow.next;
        fast = fast.next.next;
        if(slow == fast){
            slow = head;
            while (slow != fast){
                slow = slow.next;
                fast = fast.next;
            }
            return slow;
        }
    }
    return null;
}

测试：

 void linkSortTest(){
     //构造有序链表
     Node node01 = new Node(1,null);
     Node node02 = new Node(2,null);
     Node node03 = new Node(3,null);
     Node node04 = new Node(4,null);
     Node node05 = new Node(5,null);
     Node node06 = new Node(6,null);
     Node node07 = new Node(7,null);
     node01.next = node02;
     node02.next = node03;
     node03.next = node04;
     node04.next = node05;
     node05.next = node06;
     node06.next = node07;
     node07.next = node01;
     System.out.println(findEntrence(node01).value);
 }

10、相交链表，给出两个链表，找到他们相交的节点

方法：

private Node findOverlapNode(Node node1, Node node2) {
    if(node1 == null || node2 == null){
        return null;
    }
    //计算两个列表长度
    int l1 = 0;
    int l2 = 0;
    Node n1 = node1;
    while (n1.next != null){
        l1++;
        n1 = n1.next;
    }
    Node n2 = node2;
    while (n2.next != null){
        l2++;
        n2 = n2.next;
    }
    //长链表跳过差值长度，短链表头结点开始
    if(l1 > l2){
        int n = l1 - l2;
        n1 = node1;
        for (int i = 0; i < n; i++) {
            n1 = n1.next;
        }
        n2 = node2;
    }else {
        int n = l2 - l1;
        n2 = node2;
        for (int i = 0; i < n; i++) {
            n2 = n2.next;
        }
        n1 = node1;
    }
    while (n1.next != null && n2.next != null){
        while ( n1 != n2){
            n1 = n1.next;
            n2 = n2.next;
        }
        return n1;
    }
    return null;
    //        //使用双指针
    //        Node n1 = node1;
    //        Node n2 = node2;
    //        while (n1 != n2){
    //            n1 = n1.next == null ? node2 : n1.next;
    //            n2 = n2.next == null ? node1 : n2.next;
    //        }
    //        return n1;
    //        //引入一个hashMap
    //        Set<Node> set = new HashSet<>();
    //        Node n1 = node1;
    //        while (n1.next != null){
    //            Node node = n1;
    //            set.add(node);
    //            n1 = n1.next;
    //        }
    //        Node n2 = node2;
    //        while (n2.next != null){
    //            if(set.contains(n2)){
    //                return n2;
    //            }
    //            n2 = n2.next;
    //        }
    //        return null;
    //        //暴戾穷举
    //        Node n1 = node1;
    //        while (n1.next != null){
    //            Node n2 = node2;
    //            while (n2.next != null){
    //                if(n1 == n2){
    //                    return n1;
    //                }
    //                n2 = n2.next;
    //            }
    //            n1 = n1.next;
    //        }
    //        return null;
}

测试：

void linkSortTest(){
    //构造有序链表
    Node node01 = new Node(1,null);
    Node node02 = new Node(2,null);
    Node node03 = new Node(3,null);
    Node node04 = new Node(4,null);
    Node node05 = new Node(5,null);
    Node node06 = new Node(6,null);
    Node node07 = new Node(7,null);
    Node node08 = new Node(8,null);
    Node node09 = new Node(9,null);
    Node node010 = new Node(10,null);
    Node node011 = new Node(11,null);
    Node node012 = new Node(12,null);
    node01.next = node02;
    node02.next = node03;
    node03.next = node04;
    node04.next = node05;
    node05.next = node06;
    node06.next = node07;
    //        node07.next = node01;
    node07.next = null;
    node08.next = node09;
    node09.next = node010;
    node010.next = node011;
    node011.next = node012;
    node012.next = node03;
    Node re = findOverlapNode(node01,node08);
    System.out.println(re.value);
}

11、反转链表

方法：

private Node reverseLink(Node head) {
    if(head == null){
        return null;
    }
    //定义两个节点临时记录，cur    pre
    Node cur = head;
    Node pre = null;
    while (cur.next != null){
        Node next = cur.next;
        cur.next = pre;
        pre = cur;
        cur = next;
    }
    //最后一个节点需要单独处理
    cur.next = pre;
    return cur;
}

测试：

 void linkSortTest(){
     //构造有序链表
     Node node01 = new Node(1,null);
     Node node02 = new Node(2,null);
     Node node03 = new Node(3,null);
     Node node04 = new Node(4,null);
     Node node05 = new Node(5,null);
     Node node06 = new Node(6,null);
     Node node07 = new Node(7,null);
     node01.next = node02;
     node02.next = node03;
     node03.next = node04;
     node04.next = node05;
     node05.next = node06;
     node06.next = node07;
     node07.next = null;
     Node re = reverseLink(node01);
     while (re != null){
         System.out.println(re.value);
         re = re.next;
     }
 }

12、判断链表是否是回文链表

解法一：借助一个数组，遍历链表之后，把所有的值存入数组，然后使用两个指针分别从收尾开始遍历数组，对元素进行判断，直到相遇
方法：

private static boolean palindrome01(Node head) {
    if(head == null){
        return false;
    }
    List<Integer> temp = new ArrayList<>();
    temp.add(head.value);
    Node node = head;
    while (node.next != null){
        node = node.next;
        temp.add(node.value);
    }
    int left = 0;
    int right = temp.size()-1;
    while (left<right){
        if(temp.get(left) != temp.get(right)){
            return false;
        }
        left++;
        right--;
    }
    return true;
}

解法二：借用双指针，找到中间节点，然后把后半部分翻转，然后一次比较两个链表
方法：

private static boolean palindrome002(Node head) {
    if(head == null){
        return false;
    }
    Node slow = head;
    Node fast = head;
    while (fast != null && fast.next != null){
        slow = slow.next;
        fast = fast.next.next;
    }
    if(fast != null){
        slow = slow.next;
    }
    Node temp = reverseLink(slow);
    slow = head;
    while (temp != null && slow != null){
        if(temp.value != slow.value){
            return false;
        }
        temp = temp.next;
        slow = slow.next;
    }
    return true;
}

测试：

public static void main(String[] args) {
    //回文链表  1235321 //构造有序链表
    Node node01 = new Node(1,null);
    Node node02 = new Node(2,null);
    Node node03 = new Node(3,null);
    Node node04 = new Node(4,null);
    Node node05 = new Node(3,null);
    Node node06 = new Node(2,null);
    Node node07 = new Node(1,null);
    node01.next = node02;
    node02.next = node03;
    node03.next = node04;
    node04.next = node05;
    node05.next = node06;
    node06.next = node07;
    node07.next = null;
    //解法一：借助一个数组，遍历链表之后，把所有的值存入数组，然后使用两个指针分别从收尾开始遍历数组，对元素进行判断，直到相遇
    boolean palindrome01 = palindrome01(node01);
    System.out.println(palindrome01);
    //解法二：借用双指针，找到中间节点，然后把后半部分翻转，然后一次比较两个链表
    boolean palindrome02 = palindrome002(node01);
    System.out.println(palindrome02);
}

13、找到链表的中间节点

上一题中间的一部分内容，快指针走到结尾，慢指针刚好到中间

Node slow = head;
Node fast = head;
while (fast != null && fast.next != null){
    slow = slow.next;
    fast = fast.next.next;
}

14、找到链表中倒数第K个节点

找到倒数第K个节点，先得到所有节点数n，倒数第K个，也就是正数第n-K+1。（还有一个方法，是引入一个列表或者hashMap，遍历节点的时候把节点数据存进去，然后在取数据）
方法：

 private static Node findKNode(Node head, Integer k) {
     if(head == null){
         return null;
     }
     Integer n = 0;
     Node node = head;
     while (node.next != null){
         n++;
         node = node.next;
     }
     if(n < k){
         return null;
     }
     node = head;
     for (int i = 0; i < n-k+1; i++) {
         node = node.next;
     }
     return node;
 }