10.安卓程序员必须会的基础算法

1.冒泡排序

从头开始,不断的比较相邻的两个数,小的放前边,大的放后边,一次比较之后,最大的数字会出现在数组的尾端;不断重复这个过程,直到排序完成

细节问题:外层循环表示完成排序需要进行的次数,数组长度为n,就需要n-1次,因为每次都会得到一个最大的,那么假如数列长度为10,那么9次排序之后,有9个最大的数字已经被筛选出来,那么最后一次不需要再做比较,一定是最小的;内层循环控制每次排序需要比较的次数,数组长度为n,则需要比较n-1次,这是-1的原因;每次比较完成之后,最大的数字已经排在尾端,所以下一次比较会新增一个不需要参与比较的数字,这就是-i的原因

特点:稳定;平均时间复杂度O(n2),最坏时间复杂度O(n2),最佳时间复杂度O(n),空间复杂度O(1)

冒泡排序.gif
    public static void bubbleSort(int[] arr) {
        int temp;
        for (int i = 0; i < arr.length - 1; i++) {
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
        }
    }

2.选择排序

冒泡排序第一次排序完成之后,会得到最大的数字,而选择排序是第一次排序之后,得到最小的数字。顾名思义,选择排序就是从未排序的序列中选择出最小(或最大,这里以从小到大排序为例说明)的数字放在数组的首位,不断的重复这个过程,直到排序完成,既然是选择最小的数字,那么一定有一个记录本次比较最小值的操作

细节问题:外层循环同样是控制需要进行的次数,长度为n,需要进行n-1次;内层循环控制每次需要比较的次数,选择排序每进行一层比较,就会得到一个最小的数字,放在最左边,那么这个得到的最小的数字就不需要再参与比较,所以j=i+1,内层循环每循环一次,就能得到这个数列中最小的元素的index,如果它比本次比较的起始位置(当前i位置)的值小,则交换即可。

特点:不稳定(数列中有相同元素的情况下,如a = b,a本来在b的前边,但是排序之后,二者的位置可能被交换);平均时间复杂度O(n2),最坏时间复杂度O(n2),最佳时间复杂度O(n2),空间复杂度O(1)

选择排序.gif
    public static void selectSort(int[] arr) {
        int minIndex,temp;
        for (int i = 0; i < arr.length - 1; i++) {
            minIndex = I;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                }
            }
            temp = arr[i];
            arr[i] = arr[minIndex];
            arr[minIndex] = temp;
        }
    }

3.简单插入排序

工作原理是通过构建有序序列,对于未排序数据,在已排序序列中从后向前扫描,找到相应位置并插入。

1.从第一个元素开始,该元素可以认为已经被排序;
2.取出下一个元素,在已经排序的元素序列中从后向前扫描;
3.如果该元素(已排序)大于新元素,将该元素移到下一位置;
4.重复步骤3,直到找到已排序的元素小于或者等于新元素的位置;
5.将新元素插入到该位置后;
6.重复步骤2~5。

插入排序.gif
    public static void insertSort(int[] arr) {
        int current,preIndex;
        for (int i = 1; i < arr.length; i++) {
            preIndex = i - 1;
            current = arr[I];
            while (preIndex >= 0 && arr[preIndex] > current){
                arr[preIndex + 1] = arr[preIndex];
                preIndex--;
            }
            arr[preIndex+1] = current;
        }
    }

3.堆排序

参考://www.greatytc.com/p/938789fde325
堆排序的堆并不是java内存的堆的概念,它依托于一个完全二叉树的结构来实现排序,首先将数列调整成一个大顶堆(还有称为大根堆的)或者小顶堆(小根堆),以大顶堆为例(父节点中的元素不小于任意子节点的元素这种情形。所以,在一个大顶堆中,一个节点的元素在其子树所有元素组成的集合中必定是最大值),调整完成之后,最大的数字是这个完全二叉树的根节点,接下来把这个最大的值和完全二叉树的最后一个节点交换,交换之后可能会破坏大顶堆的结构(父节点中的元素不小于(不大于)任意子节点的元素),所以交换之后需要同时再次调整大顶堆,重复这个操作直到排序完成
什么是完全二叉树? 如 [2,4,1,3,8,6,9]形成一个完全二叉树

截屏2021-08-22 上午10.24.05.png

关键点:

1.当我们知道某一数字在数组中的索引后,就可以计算出二叉树中该数字的左右子节点的索引,或者父节点在数组中的索引。以数字4为例,它的数组表示为A[1],根据二叉树特点,其父节点为2,即A[0];同时其左节点为3,右节点为8,分别对应A[3],A[4],可得出一个结论,A[i]的左节点为A[2i+1],右节点为A[2i+2],父节点为A[i/2]

2.开始位置(从最后一个非叶子结点开始(叶结点自然不用调整,第一个非叶子结点 arr.length/2-1(完全二叉树),从左至右,从下至上进行调整。)

堆排序过程.gif
    public static void heap(int[] arr, int size, int index) {
        //左子节点的index(完全二叉树)
        //A[i]的左节点为A[2i+1],右节点为A[2i+2],父节点为A[i/2]
        int leftNode = 2 * index + 1;
        //右子节点的index
        int rightNode = 2 * index + 2;

        //设置最大值
        int max = index;

        //进行和左子节点比较
        if (leftNode < size && arr[leftNode] > arr[max]) {
            max = leftNode;
        }
        //和右子节点比较
        if (rightNode < size && arr[rightNode] > arr[max]) {
            max = rightNode;
        }

        //找到最大的节点之后就替换
        if (max != index) {
            int temp = arr[index];
            arr[index] = arr[max];
            arr[max] = temp;
            //然后如果还有的话就继续替换
            heap(arr, size, max);
        }

    }

    public static int [] heapSort(int [] arr){
        //开始位置(从最后一个非叶子结点开始(叶结点自然不用调整,第一个非
        //叶子结点 arr.length/2-1(完全二叉树),从左至右,从下至上进行调整。)
        int start = (arr.length) / 2 - 1;
        //1.得到一个大顶堆
        for (int i = start; i >= 0; i--) {
            heap(arr, arr.length, i);
        }

        //2.根结点和尾节点交换,并再次调整维持大顶堆
        for (int i = arr.length - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            //每交换一次之后,最大的值已经到了堆的最后一个节点,所以这个
            //最大值不需要再参与排序,所以heap第二个参数size = i
            heap(arr, i, 0);
        }
        return arr;
    }

总体复杂度为O(n*log n)

3.top-k排序

1.整体排序

将n个数排序之后,取出最大的k个

2.局部排序

只对最大的k个排序,冒泡排序冒泡k次,就会得到前k个最大元素

3.堆

a.只找到TopK,省去了排序过程,先用前k个元素生成一个小顶堆,这个小顶堆用于存储,当前最大的k个元素。
b.接着,从第k+1个元素开始扫描,和堆顶(堆中最小的元素)比较,如果被扫描的元素大于堆顶,则替换堆顶的元素,并调整堆,以保证堆内的k个元素,总是当前最大的k个元素。
c.直到扫描完所有n-k个元素,最终堆中的k个元素,就是TopK

快速排序

快速排序是由冒泡排序改进而得到的,是一种分区交换排序方法。思想如下:
一趟快速排序采用从两头向中间扫描的方法,同时交换与基准记录逆序的记录。

1.在待排序的N个记录中任取一个元素(通常取第一个记录)作为基准,称为基准记录;
2.定义两个索引 left 和 right 分别表示“首索引” 和 “尾索引”,key 表示“基准值”;
3.首先,尾索引向前扫描,直到找到比基准值小的记录(left != righ),并替换首索引对应的值;
4.然后,首索引向后扫描,直到找到比基准值大于的记录(left != righ),并替换尾索引对应的值;
5.若在扫描过程中首索引等于尾索引(left = right),则一趟排序结束;将基准值(key)替换首索引所对应的值;
6.再进行下一趟排序时,待排序列被分成两个区:[0,left-1],[righ+1,end]
7.对每一个分区重复步骤2~6,直到所有分区中的记录都有序,排序成功。

快速排序最好时间复杂度为nlogn,最坏时间复杂度为n的平方,平均时间复杂度为nlogn

快速排序1.jpg
快速排序2.jpg
快速排序3.jpg
快速排序4.jpg
快速排序5.jpg
快速排序6.jpg
快速排序7.jpg
快速排序8.jpg
    private static void quickSort(int[] arr, int leftIndex, int rightIndex) {
        if (leftIndex >= rightIndex) {
            return;
        }
        int left = leftIndex;
        int right = rightIndex;
        //待排序的第一个元素作为基准值
        int key = arr[leftIndex];
        //从左右两边交替扫描,直到left = right
        //左往右查找的话,每次停下来的位置对应的元素必然比基准要大,如果这
        //时跳出循环的话,这个较大元素就会被换到前面,得到的结果就是错的;而先
        //从右往左查找的话,停下来的位置对应的元素必然比基准要小,如果这时跳出
        //循环的话,这个较小元素就会被换到前面。所以,如果我们要排升序的序列,
        //一定记得先从右往左查找!顺序不错,结果才会正确。
        while (left < right) {
            while (left < right  && arr[right] >= key) {
                //从右往左扫描,找到第一个比基准值小的元素
                right--;
            }
            while (left < right && arr[left] <= key) {
                //从左往右扫描,找到第一个比基准值大的元素
                left++;
            }
            if (left < right){
                int temp = arr[left];
                arr[left] = arr[right];
                arr[right] = temp;
            }
        }
        //基准值归位
        arr[leftIndex] = arr[left];
        arr[left] = key;
        //对基准值左边的元素进行递归排序
        quickSort(arr, leftIndex, left - 1);
        //对基准值右边的元素进行递归排序。
        quickSort(arr, right + 1, rightIndex);
    }

4,二分查找

一般二分查找
    public static int binarySearch(int arr[], int num) {
        int left = 0;
        int right = arr.length - 1;
        //等号必须加,不然部分情况无法搜索到结果
        while (left <= right) {
            // 等同于(left+ right) /2 只是可以避免溢出
            int center = left + (right - left) / 2;
            if (arr[center] > num) {
                right = center - 1;
            } else if (arr[center] < num) {
                left = center + 1;
            } else {
                return center;
            }
        }
        return -1;
    }
左边界二分查找
    static int leftBoundBinarySearch(int[] nums, int target) {
        int left = 0;
        int right = nums.length-1; // 注意
        //while的条件不能是<= ,比如当前left = 3, right = 4,那么mid = 3,
        // 更新right = 3,然后满足while,并且mid = 3,更新right = 3,就会死循环
        while (left < right) { // 注意
            int center = left + (right - left) / 2;
            if (nums[center] == target) {
                //如果找到相等的,继续向左查找,这里right必须设置为等于,
                // 以防止如果没有左边界,还能返回当前找到的值
                right = center;
            } else if (nums[center] < target) {
                //已经不想等了,就没有必要下次参与查找了
                left = center + 1;
            } else if (nums[center] > target) {
                //已经不想等了,就没有必要下次参与查找了
                right = center-1;
            }
        }
        return left;
    }
右边界二分查找
    static int rightBoundBinarySearch(int[] arr, int target) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            // +1 其实是上取整,避免最后left 和right对应值相等且等于target,这样center还是等于left,然后判断赋值left = center ,这样就死循环了
            int center = left + (right - left + 1) / 2;
            if (arr[center] > target) {
                right = center - 1;
            } else if (arr[center] < target) {
                left = center + 1;
            } else {
                left = center;
            }
        }
        return left;
    }

二分查找变形

给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
请必须使用时间复杂度为 O(log n) 的算法。

    public static int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length - 1;
        while(left <= right) {
            int mid = left+(right-left)/2;
            if(nums[mid] == target) {
                return mid;
            } else if(nums[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return left;
    }

实现 int sqrt(int x) 函数。
计算并返回 x 的平方根,其中 x 是非负整数。
由于返回类型是整数,结果只保留整数的部分,小数部分将被舍去。
由于x 平方根的整数部分ans 是满足k的平方≤x 的最大值,因此我们可以对k 进行二分查找,从而得到答案。
找到最后一个满足a的平方小于等于x的情况下,a的值,和上边的二分查找变形,找插入位置刚好相反

        int left = 0;
        int right = x;
        while(left <= right){
            int middle = (right - left) / 2 + left;

            if((long)middle*middle < x){
                left = middle+1;
            }else if((long)middle * middle > x){
                right = middle - 1;
            }else{
                return middle;
            }
        }
        return right;

5.数组类

1.删除有序数组中的重复项(小米)

给你一个有序数组 nums ,请你 原地 删除重复出现的元素,使每个元素 只出现一次 ,返回删除后数组的新长度。注意关键词有序,因为有序,所以重复的元素一定是紧挨着的
不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

例如:输入:nums = [0,0,1,1,1,2,2,3,3,4]
输出:5, nums = [0,1,2,3,4]
解释:函数应该返回新的长度 5 , 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。

思路:定义两个指针fast 和slow,分别为快指针和慢指针,快指针表示遍历数组到达的下标位置,慢指针表示下一个不同元素要填入的下标位置,初始时两个指针都指向下标1,假设数组nums 的长度为n。将快指针fast 依次遍历从1到n−1 的每个位置,对于每个位置,如果nums[fast]≠nums[fast−1],说明nums[fast] 和之前的元素都不同,因此将nums[fast] 的值复制到nums[slow],然后将slow的值加1,即指向下一个位置,遍历结束之后,从 nums[0] 到 nums[slow−1]的每个元素都不相同且包含原数组中的每个不同的元素,因此新的长度即为slow,返回slow 即可。


删除元素.png
    public static int removeDuplicates(int[] nums) {
        if (nums == null || nums.length == 0){
            return 0;
        }
        int fast=1,slow = 1;
        while(fast < nums.length){
            if (nums[fast] != nums[fast - 1]){
                nums[slow] = nums[fast];
                slow++;
            }
            fast++;
        }
        return slow;
    }
2.找出数组中任意一个重复的数字(小米)

在一个长度为 n 的数组 nums 里的所有数字都在 0~n-1 的范围内。数组中某些数字是重复的,但不知道有几个数字重复了,也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。

这道题看起来很简单,直接用个集合存一下,有重复的就反回,但是假如不准使用其他数据结构,对空间复杂度要求为O(1)的时候就不行了

参考选择排序的方式来解(快慢指针解法):

    public static int findRepeatNumber2(int[] nums) {
        for (int i = 0; i < nums.length; i++) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    return nums[I];
                }
            }
        }
        return -1;
    }

变形一下:

    public static int findRepeatNumber3(int[] nums) {
        int i = 0;
        while (i < nums.length) {
            for (int j = i + 1; j < nums.length; j++) {
                if (nums[i] == nums[j]) {
                    return nums[j];
                }
            }
            I++;
        }
        return 0;
    }
3. 0~n-1中缺失的数字(Google,Tencent)

一个长度为n-1的递增排序数组中的所有数字都是唯一的,并且每个数字都在范围0~n-1之内。在范围0~n-1内的n个数字中有且只有一个数字不在该数组中,请找出这个数字。
注意是有序的
如果没有任何一个缺失的数字,那么这个数组应该是这样的:
arr[0] = 0;
arr[1] = 1;
arr[2] = 2;
arr[3] = 3;
......
arr[n-1] = n-1;
也就是说,数组下标和数组值相同,但是缺了一个,那么一定从某一个index开始,index != value。这种题的解法看起来很简单,直接遍历,找到这个index和value不想等的数字返回,不过还有更好的解法-二分查找(有序数组,又是要找某个数,就要想到二分查找

    public static int findLostNum(int[] nums) {
        int start = 0;
        int end = nums.length - 1;
        while(start < end){
            int middle = (end - start) / 2 + start;
            if(nums[middle] > middle){
                end = middle;
            }else{
                start = middle + 1;
            }
        }
        // 当左边界与右边界相等时,可能已经指向该缺失的数字,但是还有一种可能是缺失的数字就在最后一个数组的后边
        // 即[0,1,2],缺少3,长度为3,即n=4,数的范围0~3
        return start == nums[start]?start+1:start;
4.给定一个存放整数的数组,重新排列数组使得数组左边为奇数,右边为偶数。 要求:空间复杂度O(1),时间复杂度为O(n)

注意:空间复杂度要求为O(1),那么就不能使用额外的数据结构,只能直接来操作这个数组,这里还是用双指针法来处理。既然奇数在左,偶数在右,那么定义两个指针,一个从左往右,一个从右往左(可以看作二分查找的变形),从左往右找到第一个偶数,从右往左找到第一个奇数,交换两个数字的位置,然后重复上边的步骤

    public static int[] reSortArray(int[] nums) {
        int left = 0, right = nums.length - 1;
        while (left < right) {
            while (left < right && nums[left] % 2 != 0) {
                left++;
            }
            while (left < right && nums[right] % 2 == 0) {
                right--;
            }
            if (left < right) {
                int temp = nums[left];
                nums[left] = nums[right];
                nums[right] = temp;
            }
        }
        return nums;
    }

6.链表类

1.反转单链表(小米/美团/快手)

a.非递归方法:
定义一个函数,输入一个链表的头节点,反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL

思路:在遍历链表时,将当前节点的next 指针改为指向前一个节点。由于节点没有引用其前一个节点,因此必须事先存储其前一个节点。在更改引用之前,还需要存储后一个节点。最后返回新的头引用。

反转单链表-1.png
反转单链表-2.png
反转单链表-3.png
反转单链表-4.png
反转单链表-5.png
    public class Node {
        int value;
        Node next;

        Node(int x) {
            value = x;
        }
    }

    public static Node reverseList(Node head) {
        Node cur = head, pre = null;
        while (cur != null) {
            Node tmp = cur.next;
            cur.next = pre;
            pre = cur;
            cur = tmp;
        }
        return pre;
    }

b.递归方法:

    public static Node reverseList2(Node head) {
        return recur(head, null);    // 调用递归并返回
    }

    private static Node recur(Node cur, Node pre) {
        if (cur == null) return pre; // 终止条件
        Node res = recur(cur.next, cur);  // 递归后继节点
        cur.next = pre;              // 修改节点引用指向
        return res;                  // 返回反转链表的头节点
    }
2.链表的中间结点(中国平安)

给定一个头结点为 head 的非空单链表,返回链表的中间结点,如果有两个中间结点,则返回第二个中间结点。


快慢指针.png
    public static Node getMiddleNode(Node head) {
        Node fast = head;
        Node slow = head;
        while(fast != null && fast.next != null){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
3.如何检测一个链表是否有环(优酷腾讯滴滴)

A -> B -> C -> D -> E -> A这样的链表表示有环,链表的头节点和链表的尾节点相连;或者另一种情况,链表并非首尾相连,而是尾节点指向了中间某节点A -> B -> C -> D -> E -> C, 这样也表示这个链表有环

思路:设置一个快指针fast,一个慢指针slow,二者初始都指向链表头,fast一次走两步,slow一次走一步,两个指针同时向前移动,每移动一次,两个指针都要进行比较,如果快指针等于慢指针,则证明这是个有环的单链表。

如果是有环的链表,那么这个链表就没有尾部, while (fast != null && fast.next != null) 会一直成立,直到找到两个值相同的节点;如果没有环,那么当fast节点到达尾端的时候就会跳出循环,恰恰证明了这个链表没有环

    public static boolean isLoop(Node head) {
        boolean flag = false;
        Node slow = head;
        Node fast = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if (fast.value == slow.value) {
                flag = true;
                break;
            }
        }
        return flag;
    }
4.相交链表(华为)

给你两个单链表的头节点 headA和headB ,请你找出并返回两个单链表相交的起始节点。如果两个链表没有交点,返回null 。


公共节点.png

思路:
设第一个公共节点为 node ,链表 headA的节点数量为
a ,链表 headB的节点数量为b ,两链表的公共尾部的节点数量为c ,则有
头节点 headA 到 node 前,共有a−c 个节点
头节点 headB 到 node 前,共有b−c 个节点

考虑构建两个节点指针 A , B 分别指向两链表头节点 headA ,headB ,做如下操作:
指针 A 先遍历完链表 headA ,再开始遍历链表 headB ,当走到 node 时,共走步数为a+(b−c)

指针 B 先遍历完链表 headB ,再开始遍历链表 headA ,当走到 node 时,共走步数为b+(a−c)

此时指针 A , B 重合,并有两种情况
a+(b−c)=b+(a−c)

若两链表有公共尾部 (即 c>0 ) :指针A , B同时指向第一个公共节点node
若两链表无公共尾部 (即c=0 ) :指针 A , B 同时指向null

    public static Node getIntersectionNode(Node headA, Node headB) {
        if (headA == null || headB == null) {
            return null;
        }
        Node first = headA;
        Node second = headB;
        while (first != second) {
            first = first == null ? headB : first.next;
            second = second == null ? headA : second.next;
        }
        return first;
    }
5.链表中倒数第k个节点

输入一个链表,输出该链表中倒数第k个节点

示例:
给定一个链表: 1->2->3->4->5, 和 k = 2.返回链表 4->5.


倒数节点.gif
    public Node getNodeEnd(Node head, int k) {
        Node former = head, latter = head;
        for (int i = 0; i < k; I++)
            former = former.next;
        while (former != null) {
            former = former.next;
            latter = latter.next;
        }
        return latter;
    }

时间复杂度O(N) :N 为链表长度;总体看, former 走了N 步, latter 走了(N−k) 步。
空间复杂度O(1) : 双指针 former , latter 使用常数大小的额外空间。

6.两数相加(今日头条,美团)

给你两个 非空 链表来代表两个非负整数。数字最高位位于链表开始位置。它们的每个节点只存储一位数字。将这两数相加会返回一个新的链表。
你可以假设除了数字 0 之外,这两个数字都不会以零开头
如:
输入:l1 = [7,2,4,3], l2 = [5,6,4]
输出:[7,8,0,7]


两链表相加.png
    public Node addTwoNumbers(Node l1, Node l2) {
        Stack<Integer> stack1 = new Stack<>();
        Stack<Integer> stack2 = new Stack<>();
        while (l1 != null) {
            stack1.push(l1.value);
            l1 = l1.next;
        }
        while (l2 != null) {
            stack2.push(l2.value);
            l2 = l2.next;
        }

        int carry = 0;
        Node head = null;
        while (!stack1.isEmpty() || !stack2.isEmpty() || carry > 0) {
            int sum = carry;
            sum += stack1.isEmpty() ? 0 : stack1.pop();
            sum += stack2.isEmpty() ? 0 : stack2.pop();
            //构建一个节点
            Node node = new Node(sum % 10);
            //头插法中,第一个构建的节点作为最终的尾节点,尾节点
            //的next指向null,head指向null,新建的节点也指向null
            node.next = head;
            //移动head节点指向当前创建的节点,作为头节点,下一次循环
            //新建的节点仍会被作为新节点的next节点,就这样不停的移动head指针
            head = node;
            carry = sum / 10;
        }
        return head;
    }

时间复杂度:O(max(m,n)),其中m 和n 分别为两个链表的长度。我们需要遍历两个链表的全部位置,而处理每个位置只需要
O(1) 的时间。
空间复杂度:O(m+n),其中m 和n 分别为两个链表的长度。空间复杂度主要取决于我们把链表内容放入栈中所用的空间。

变形
给你两个 非空 的链表,表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的,并且每个节点只能存储 一位 数字。请你将两个数相加,并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外,这两个数都不会以 0 开头。

由于输入的两个链表都是逆序存储数字的位数的,因此两个链表中同一位置的数字可以直接相加。我们同时遍历两个链表,逐位计算它们的和,并与当前位置的进位值相加

    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode head = null, tail = null;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int n1 = l1 != null ? l1.val : 0;
            int n2 = l2 != null ? l2.val : 0;
            int sum = n1 + n2 + carry;
            if (head == null) {
                head = tail = new ListNode(sum % 10);
            } else {
                tail.next = new ListNode(sum % 10);
                tail = tail.next;
            }
            carry = sum / 10;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (carry > 0) {
            tail.next = new ListNode(carry);
        }
        return head;
    }

7.队列,堆栈

1.用两个栈实现队列

根据栈先进后出的特性,我们每次往第一个栈里插入元素后,第一个栈的底部元素是最后插入的元素,第一个栈的顶部元素是下一个待删除的元素。为了维护队列先进先出的特性,我们引入第二个栈,用第二个栈维护待删除的元素,在执行删除操作的时候我们首先看下第二个栈是否为空。如果为空,我们将第一个栈里的元素一个个弹出插入到第二个栈里,这样第二个栈里元素的顺序就是待删除的元素的顺序,要执行删除操作的时候我们直接弹出第二个栈的元素返回即可。


两个栈实现队列.gif
public class TwoStackQueue {

    private final Stack<Integer> stackPush;
    private final Stack<Integer> stackPop;

    public TwoStackQueue() {
        stackPush = new Stack();
        stackPop = new Stack();
    }

    public void addTail(int num) {
        stackPush.push(num);
    }

    public int removeHead() {
        if (stackPop.isEmpty()) {
            while (!stackPush.isEmpty()) {
                stackPop.push(stackPush.pop());
            }
        }
        return stackPop.pop();
    }

8.二叉树

1.前序遍历

递归

public static void preOrderRecur(TreeNode head) {
    if (head == null) {
        return;
    }
    System.out.print(head.value + " ");
    preOrderRecur(head.left);
    preOrderRecur(head.right);
}

迭代

    public List<Integer> preorderTraversal(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList();
        List<Integer> list = new ArrayList();
        while(root != null || !stack.isEmpty()){
            while(root != null){
                list.add(root.val);
                stack.push(root);
                root = root.left;
            }
            TreeNode node = stack.pop();
            root = node.right;
        }
        return list;
}
2.中序遍历

递归

public static void preOrderRecur(TreeNode head) {
    if (head == null) {
        return;
    }
    preOrderRecur(head.left);
    System.out.print(head.value + " ");
    preOrderRecur(head.right);
}

迭代

    public List<Integer> inorderTraversal(TreeNode root) {
        LinkedList<TreeNode> stack = new LinkedList();
        List<Integer> list = new ArrayList();
        while(root != null || !stack.isEmpty()){
            while(root != null){
                stack.push(root);
                root = root.left;
            }
            TreeNode node = stack.pop();
            list.add(node.val);
            root = node.right;
        }      
        return list;
}
3.后序遍历

递归

public static void postOrderRecur(TreeNode head) {
    if (head == null) {
        return;
    }
    postOrderRecur(head.left);
    postOrderRecur(head.right);
    System.out.print(head.value + " ");
}

迭代

    public List<Integer> postorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList();
        LinkedList<TreeNode> stack = new LinkedList();

        TreeNode pre = null;
        while(root != null || !stack.isEmpty()){
            while(root != null){
                stack.push(root);
                root = root.left;
            }

            TreeNode node = stack.pop();
            if(node.right == null || node.right == pre){
                list.add(node.val);
                pre = node;
                root = null;
            }else{
                stack.push(node);
                root = node.right;
            }
        }
        return list;
}
4.检查子树(爱奇艺)

检查子树。你有两棵非常大的二叉树:T1,有几万个节点;T2,有几万个节点。设计一个算法,判断 T2 是否为 T1 的子树。
如果 T1 有这么一个节点 n,其子树与 T2 一模一样,则 T2 为 T1 的子树,也就是说,从节点 n 处把树砍断,得到的树与 T2 完全相同。
示例1:
输入:t1 = [1, 2, 3], t2 = [2]
输出:true
示例2:
输入:t1 = [1, null, 2, 4], t2 = [3, 2]
输出:false

    public boolean checkSubTree(TreeNode n1, TreeNode n2) {
        if (n2 == null) {
            return true;
        }
        if (n1 == null) {
            return false;
        }
        return isEquals(n1, n2) || checkSubTree(n1.left, n2) || checkSubTree(n1.right, n2);
    }

    private boolean isEquals(TreeNode n1, TreeNode n2) {
        if (n1 == n2) {
            return true;
        }
        if (n1 == null || n2 == null) {
            return false;
        }
        return n1.value == n2.value && isEquals(n1.left, n2.left) && isEquals(n1.right, n2.right);
    }

    class TreeNode {
        int value;
        TreeNode left;
        TreeNode right;
    }

时间复杂度分析:最差情况下,t1在小于t2子树高度以上节点都要比对M次,M是t2节点的大小,所以时间复杂度为O(N*M)

变形:
给你两棵二叉树的根节点 p 和 q ,编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。

    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null){
            return true;
        }
        if(p == null || q == null){
            return false;
        }

        return p.val == q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
}
给定一个二叉树,检查它是否是镜像对称的。

例如,二叉树 [1,2,2,3,4,4,3] 是对称的。

    1
   / \
  2   2
 / \ / \
3  4 4  3

如果同时满足下面的条件,两个树互为镜像:
它们的两个根结点具有相同的值
每个树的右子树都与另一个树的左子树镜像对称

我们可以实现这样一个递归函数,通过「同步移动」两个指针的方法来遍历这棵树,p 指针和q 指针一开始都指向这棵树的根,随后p 右移时,q 左移,p 左移时,q 右移。每次检查当前p 和q 节点的值是否相等,如果相等再判断左右子树是否对称。

public boolean isSymmetric(TreeNode root) {
        TreeNode left = root;
        TreeNode right = root;
        return check(left,right);
    }
    public boolean check(TreeNode left,TreeNode right){
        if(left == null && right == null){
            return true;
        }
        if(left == null || right == null){
            return false;
        }
        return left.val == right.val && check(left.left,right.right) && check(left.right, right.left);
    }
给定一个二叉树,找出其最大深度。

二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
如果我们知道了左子树和右子树的最大深度l 和r,那么该二叉树的最大深度即max(l,r)+1
而左子树和右子树的最大深度又可以以同样的方式进行计算。因此我们可以用「深度优先搜索」的方法来计算二叉树的最大深度。具体而言,在计算当前二叉树的最大深度时,可以先递归计算出其左子树和右子树的最大深度,然后在O(1) 时间内计算出当前二叉树的最大深度。递归在访问到空节点时退出。

    public int maxDepth(TreeNode root) {
        if(root == null){
            return 0;
        }else{
            int leftMaxLength = maxDepth(root.left);
            int rightMaxLength = maxDepth(root.right);
            return Math.max(leftMaxLength,rightMaxLength)+1;
        }
    }
给你一个整数数组 nums ,其中元素已经按 升序 排列,请你将其转换为一棵 高度平衡 二叉搜索树。

高度平衡 二叉树是一棵满足「每个节点的左右两个子树的高度差的绝对值不超过 1 」的二叉树。
选择中间位置左边的数字作为根节点

    public TreeNode sortedArrayToBST(int[] nums) {
        return transferArrayToTree(nums,0,nums.length - 1);
    }

    public TreeNode transferArrayToTree(int[] nums,int left,int right){
        if(left > right){
            return null;
        }
        int mid = (left + right)/2;
        TreeNode node = new TreeNode(nums[mid]);
        node.left = transferArrayToTree(nums,left,mid - 1);
        node.right = transferArrayToTree(nums,mid+1,right);
        return node;
    }
给定一个单链表,其中的元素按升序排序,将其转换为高度平衡的二叉搜索树。

本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
将给定的有序链表转换为二叉搜索树的第一步是确定根节点,如何找出这样的一个根节点呢?我们可以找出链表元素的中位数作为根节点的值.找出链表中位数节点的方法多种多样,其中较为简单的一种是快慢指针法

class Solution {
    public TreeNode sortedListToBST(ListNode head) {
        ListNode h = head;
        ListNode t = null;
        return linkListToTree(h,t);
    }

    public TreeNode linkListToTree(ListNode left,ListNode right){
        if(left == right){
            return null;
        }
        ListNode mid = getMidleNode(left,right);
        TreeNode node = new TreeNode(mid.val);
        node.left = linkListToTree(left,mid);
        node.right = linkListToTree(mid.next,right);
        return node;
    }

    public ListNode getMidleNode(ListNode left,ListNode right){
        ListNode fast = left;
        ListNode slow = left;
        //注意这里比较关键,不能通过fast != null && fast.next != null 判断
        while(fast != right && fast.next != right){
            fast = fast.next.next;
            slow = slow.next;
        }
        return slow;
    }
}
给你二叉树的根结点 root ,将它展开为一个单链表

展开后的单链表应该同样使用 TreeNode ,其中 right 子指针指向链表中下一个结点,而左子指针始终为 null 。
展开后的单链表应该与二叉树 先序遍历 顺序相同。

    1
   / \
  2   5
 / \   \
3   4   6

//将 1 的左子树插入到右子树的地方
    1
     \
      2         5
     / \         \
    3   4         6        
//将原来的右子树接到左子树的最右边节点
    1
     \
      2          
     / \          
    3   4  
         \
          5
           \
            6
            
 //将 2 的左子树插入到右子树的地方
    1
     \
      2          
       \          
        3       4  
                 \
                  5
                   \
                    6   
        
 //将原来的右子树接到左子树的最右边节点
    1
     \
      2          
       \          
        3      
         \
          4  
           \
            5
             \
              6         
  
  ......
    public void flatten(TreeNode root) {
        while(root != null){
            if(root.left == null){
                root = root.right;
            }else{
                TreeNode temp = root.left;
                while(temp.right != null){
                    temp = temp.right;
                }
                temp.right = root.right;
                root.right = root.left;
                root.left = null;
                root = root.right;
            }
        }
    }
5.二叉树的序列化和反序列化

可以先序遍历这颗二叉树,遇到空子树的时候序列化成 NULL,否则继续递归序列化。那么我们如何反序列化呢?首先我们需要把原先的序列分割开来得到先序遍历的元素列表,然后从左向右遍历这个序列:
如果当前的元素为 NULL,则当前为空树
否则先解析这棵树的左子树,再解析它的右子树


    public static String serialize(TreeNode node) {
        return serialize2(node, "");
    }

    public static String serialize2(TreeNode node, String str) {
        if (node == null) {
            str += "NULL,";
        } else {
            str += node.value + ",";
            str = serialize2(node.left, str);
            str = serialize2(node.right, str);
        }
        return str;
    }

    public static TreeNode deserialize(String str) {
        String[] split = str.split(",");
        List<String> list = new LinkedList<>(Arrays.asList(split));
        return deserialize2(list);
    }

    public static TreeNode deserialize2(List<String> list) {
        if ("NULL".equals(list.get(0))) {
            list.remove(0);
            return null;
        }
        String s = list.get(0);
        TreeNode node = new TreeNode(Integer.parseInt(s));
        list.remove(0);
        node.left = deserialize2(list);
        node.right = deserialize2(list);
        return node;
    }

时间复杂度:在序列化和反序列化函数中,我们只访问每个节点一次,因此时间复杂度为O(n),其中n 是节点数,即树的大小。
空间复杂度:在序列化和反序列化函数中,我们递归会使用栈空间,故渐进空间复杂度为O(n)。

给定一个字符串,请你找出其中不含有重复字符的最长字串的长度(字节跳动)

我们不妨以abcabcbb为例,找出从每一个字符开始的,不包含重复字符的最长子串,那么其中最长的那个字符串即为答案。对于示例一中的字符串,我们列举出这些结果,其中括号中表示选中的字符以及最长的字符串:

以(a)bcabcbb 开始的最长字符串为(abc)abcbb;
以a(b)cabcbb 开始的最长字符串为a(bca)bcbb
以ab(c)abcbb 开始的最长字符串为ab(cab)cbb
以abc(a)bcbb 开始的最长字符串为abc(abc)bb;
以abca(b)cbb 开始的最长字符串为abca(bc)bb
以abcab(c)bb开始的最长字符串为abcab(cb)b;
以abcabc(b)b开始的最长字符串为abcabc(b)b
以abcabcb(b) 开始的最长字符串为abcabcb(b)。
发现了什么?如果我们依次递增地枚举子串的起始位置,那么子串的结束位置也是递增的!这里的原因在于,假设我们选择字符串中的第k 个字符作为起始位置,并且得到了不包含重复字符的最长子串的结束位置为rk。那么当我们选择第k+1 个字符作为起始位置时,首先从k+1到rk
的字符显然是不重复的,并且由于少了原本的第k 个字符,我们可以尝试继续增大人rk,直到右侧出现了重复字符为止。

这样一来,我们就可以使用「滑动窗口」来解决这个问题了:

我们使用两个指针表示字符串中的某个子串(或窗口)的左右边界,其中左指针代表着上文中枚举子串的起始位置,而右指针即为上文中的rk;在每一步的操作中,我们会将左指针向右移动一格,表示 我们开始枚举下一个字符作为起始位置,然后我们可以不断地向右移动右指针,但需要保证这两个指针对应的子串中没有重复的字符。在移动结束后,这个子串就对应着 以左指针开始的,不包含重复字符的最长子串。我们记录下这个子串的长度;
在循环结束后,我们找到的最长的子串的长度即为答案。

    public static int lengthOfLongestSubstring(String s) {
              int left = 0;
        HashSet<Character> set = new HashSet();
        int max = 0;
        for(int i = 0; i < s.length();i++){
            if(i != 0){
                set.remove(s.charAt(i - 1));
            }
            while(left < s.length() && !set.contains(s.charAt(left))){
                set.add(s.charAt(left));
                left++;
            }
            max = Math.max(max,left-i);
        }
        return max;
    }
7.反转字符串中的单词

开辟一个新字符串。然后从头到尾遍历原字符串,直到找到空格为止,此时找到了一个单词,并能得到单词的起止位置。随后,根据单词的起止位置,可以将该单词逆序放到新字符串当中。如此循环多次,直到遍历完原字符串,就能得到翻转后的结果。

    public static String reverseWords(String s) {
        int start = 0;
        int length = s.length();
        StringBuilder builder = new StringBuilder();
        while(start < length){

            int lastStart = start;

            while(start < length && s.charAt(start) != ' '){
                start++;
            }
            for(int i = start -1 ; i >=lastStart;i--){
                builder.append(s.charAt(i));
            }

            while(start < length && s.charAt(start) == ' '){
                builder.append(' ');
                start++;
            }

        }
        return builder.toString();
    }

时间复杂度,O(N),其中N 为字符串的长度。原字符串中的每个字符都会在O(1) 的时间内放入新字符串中。
空间复杂度,O(N)。我们开辟了与原字符串等大的空间。

8.动态规划

给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例 1:

输入:nums = [-2,1,-3,4,-1,2,1,-5,4]
输出:6
解释:连续子数组 [4,-1,2,1] 的和最大,为 6 。

这道题用动态规划的思路并不难解决,比较难的是后文提出的用分治法求解,但由于其不是最优解法,所以先不列出来
动态规划的是首先对数组进行遍历,当前最大连续子序列和为 sum,结果为 temp
如果 sum > 0,则说明 sum 对结果有增益效果,则 sum 保留并加上当前遍历数字
如果 sum <= 0,则说明 sum 对结果无增益效果,需要舍弃,则 sum 直接更新为当前遍历数字
每次比较 sum 和 temp的大小,将最大值置为temp,遍历结束返回结果
时间复杂度:O(n)

public int maxSubArray(int[] nums) {
//优化空间前
        // int arr[] = new int[nums.length];
        // arr[0] = nums[0];

        // int max = nums[0];
        // for(int i = 1; i < nums.length; i++){
        //     if(arr[i - 1] > 0){
        //         arr[i] = arr[i - 1] + nums[i];
        //     }else{
        //         arr[i] = nums[i];
        //     }
        //     max = Math.max(max,arr[i]);
        // }
        // return max;

//优化空间后
        int pre = nums[0];
        int max = nums[0];
        for(int i = 1; i < nums.length; i++){
            pre = Math.max(pre + nums[i],nums[i]);
            max = Math.max(pre,max);
        }
        return max;

9.汉诺塔问题

1.只有一个盘子的时候,只需要从将A塔上的一个盘子移到C塔上。
2.当A塔上有两个盘子是,先将A塔上的1号盘子(编号从上到下)移动到B塔上,再将A塔上的2号盘子移动的C塔上,最后将B塔上的小盘子移动到C塔上。
3.当A塔上有3个盘子时,先将A塔上编号1至2的盘子(共2个)移动到B塔上(需借助C塔),然后将A塔上的3号最大的盘子移动到C塔,最后将B塔上的两个盘子借助A塔移动到C塔上。
4.当A塔上有n个盘子是,先将A塔上编号1至n-1的盘子(共n-1个)移动到B塔上(借助C塔),然后将A塔上最大的n号盘子移动到C塔上,最后将B塔上的n-1个盘子借助A塔移动到C塔上。
5.综上所述,除了只有一个盘子时不需要借助其他塔外,其余情况均一样(只是事件的复杂程度不一样)。

发现:
中间的一步是把最大的一个盘子由A移到C上去;
中间一步之上可以看成把A上n-1个盘子通过借助辅助塔(C塔)移到了B上,
中间一步之下可以看成把B上n-1个盘子通过借助辅助塔(A塔)移到了C上;

    public static void hannoi(int n, char A, char B, char C) {
        if (n == 1) {
            move(n, A, C);
        } else {
            hannoi(n - 1, A, C, B);
            move(n, A, C);
            hannoi(n - 1, B, A, C);
        }
    }

    private static void move(int n, char a, char c) {
        System.out.println("把" + n + "从" + a + "移动到" + c);
    }
最后编辑于
©著作权归作者所有,转载或内容合作请联系作者
  • 序言:七十年代末,一起剥皮案震惊了整个滨河市,随后出现的几起案子,更是在滨河造成了极大的恐慌,老刑警刘岩,带你破解...
    沈念sama阅读 211,639评论 6 492
  • 序言:滨河连续发生了三起死亡事件,死亡现场离奇诡异,居然都是意外死亡,警方通过查阅死者的电脑和手机,发现死者居然都...
    沈念sama阅读 90,277评论 3 385
  • 文/潘晓璐 我一进店门,熙熙楼的掌柜王于贵愁眉苦脸地迎上来,“玉大人,你说我怎么就摊上这事。” “怎么了?”我有些...
    开封第一讲书人阅读 157,221评论 0 348
  • 文/不坏的土叔 我叫张陵,是天一观的道长。 经常有香客问我,道长,这世上最难降的妖魔是什么? 我笑而不...
    开封第一讲书人阅读 56,474评论 1 283
  • 正文 为了忘掉前任,我火速办了婚礼,结果婚礼上,老公的妹妹穿的比我还像新娘。我一直安慰自己,他们只是感情好,可当我...
    茶点故事阅读 65,570评论 6 386
  • 文/花漫 我一把揭开白布。 她就那样静静地躺着,像睡着了一般。 火红的嫁衣衬着肌肤如雪。 梳的纹丝不乱的头发上,一...
    开封第一讲书人阅读 49,816评论 1 290
  • 那天,我揣着相机与录音,去河边找鬼。 笑死,一个胖子当着我的面吹牛,可吹牛的内容都是我干的。 我是一名探鬼主播,决...
    沈念sama阅读 38,957评论 3 408
  • 文/苍兰香墨 我猛地睁开眼,长吁一口气:“原来是场噩梦啊……” “哼!你这毒妇竟也来了?” 一声冷哼从身侧响起,我...
    开封第一讲书人阅读 37,718评论 0 266
  • 序言:老挝万荣一对情侣失踪,失踪者是张志新(化名)和其女友刘颖,没想到半个月后,有当地人在树林里发现了一具尸体,经...
    沈念sama阅读 44,176评论 1 303
  • 正文 独居荒郊野岭守林人离奇死亡,尸身上长有42处带血的脓包…… 初始之章·张勋 以下内容为张勋视角 年9月15日...
    茶点故事阅读 36,511评论 2 327
  • 正文 我和宋清朗相恋三年,在试婚纱的时候发现自己被绿了。 大学时的朋友给我发了我未婚夫和他白月光在一起吃饭的照片。...
    茶点故事阅读 38,646评论 1 340
  • 序言:一个原本活蹦乱跳的男人离奇死亡,死状恐怖,灵堂内的尸体忽然破棺而出,到底是诈尸还是另有隐情,我是刑警宁泽,带...
    沈念sama阅读 34,322评论 4 330
  • 正文 年R本政府宣布,位于F岛的核电站,受9级特大地震影响,放射性物质发生泄漏。R本人自食恶果不足惜,却给世界环境...
    茶点故事阅读 39,934评论 3 313
  • 文/蒙蒙 一、第九天 我趴在偏房一处隐蔽的房顶上张望。 院中可真热闹,春花似锦、人声如沸。这庄子的主人今日做“春日...
    开封第一讲书人阅读 30,755评论 0 21
  • 文/苍兰香墨 我抬头看了看天上的太阳。三九已至,却和暖如春,着一层夹袄步出监牢的瞬间,已是汗流浃背。 一阵脚步声响...
    开封第一讲书人阅读 31,987评论 1 266
  • 我被黑心中介骗来泰国打工, 没想到刚下飞机就差点儿被人妖公主榨干…… 1. 我叫王不留,地道东北人。 一个月前我还...
    沈念sama阅读 46,358评论 2 360
  • 正文 我出身青楼,却偏偏与公主长得像,于是被迫代替她去往敌国和亲。 传闻我的和亲对象是个残疾皇子,可洞房花烛夜当晚...
    茶点故事阅读 43,514评论 2 348

推荐阅读更多精彩内容