牛客必刷100题

Posted on 2023-02-24 Edited on 2023-05-08 In Java Word count in article: 94k Reading time ≈ 1:26

一、链表

BM1 反转链表

描述
给定一个单链表的头结点pHead(该头节点是有值的，比如在下图，它的val是1)，长度为n，反转该链表后，返回新链表的表头。

数据范围： 0≤n≤10000≤n≤1000

要求：空间复杂度 O(1)，时间复杂度 O(n)。

思路：迭代

public class Solution {
    public ListNode ReverseList(ListNode head) {
        ListNode prev = null;
        ListNode curr = head;
        while(curr != null){
            ListNode next = curr.next;
            curr.next = prev;
            prev = curr;
            curr = next;
        }
        return prev;
    }
}

BM2 链表内指定区间反转

将一个节点数为 size 链表 m 位置到 n 位置之间的区间反转，要求时间复杂度 O(n)O(n)，空间复杂度 O(1)O(1)。
例如：
给出的链表为 1→2→3→4→5→NULL1→2→3→4→5→NUL**L, m=2,n=4m=2,n=4,
返回 1→4→3→2→5→NULL1→4→3→2→5→NUL**L.

思路：一次遍历

public ListNode reverseBetween (ListNode head, int m, int n) {
        // write code here
        ListNode dummyNode = new ListNode(-1);
        dummyNode.next = head;
        ListNode pre = dummyNode;

        for(int i = 0 ; i < m-1 ; i++){
            pre = pre.next;
        }
        ListNode cur = pre.next;
        ListNode cur_next;
        for(int i = 0 ; i < n-m;i++){
            cur_next = cur.next;
            cur.next = cur_next.next;
            cur_next.next = pre.next;
            pre.next = cur_next;
        }
        return dummyNode.next;
    }
}

BM3 链表中的节点每k个一组翻转

将给出的链表中的节点每 k 个一组翻转，返回翻转后的链表
如果链表中的节点数不是 k 的倍数，将最后剩下的节点保持原样
你不能更改节点中的值，只能更改节点本身。

数据范围： 0≤n≤2000 0≤n≤2000 ， 1≤k≤20001≤k≤2000 ，链表中每个元素都满足 0≤val≤10000≤val≤1000
要求空间复杂度 O(1)O(1)，时间复杂度 O(n)O(n)

例如：

给定的链表是 1→2→3→4→5

对于 k=2, 你应该返回 2→1→4→3→5

对于 k=3 , 你应该返回 3→2→1→4→5

思路：递归

public ListNode reverseKGroup (ListNode head, int k) {
        // write code here
        ListNode tail = head;
        for(int i = 0 ; i < k ; i++){
            if(tail == null)    return head;
            tail = tail.next;
        }
        ListNode pre = null;
        ListNode cur = head;
        while(cur != tail){
            ListNode temp = cur.next;
            cur.next  = pre;
            pre =cur;
            cur = temp;
        }
        head.next = reverseKGroup(tail,k);
        return pre;
    }

BM4 合并两个排序的链表

输入两个递增的链表，单个链表的长度为n，合并这两个链表并使新链表中的节点仍然是递增排序的。

数据范围： 0≤n≤10000≤n≤1000，−1000≤节点值≤1000−1000≤节点值≤1000
要求：空间复杂度 O(1，时间复杂度 O(n)

思路：递归

这个题递归最容易理解

public class Solution {
    public ListNode Merge(ListNode list1,ListNode list2) {
        // list1 list2为空的情况
        if(list1 == null || list2 == null){
            return list1 != null ? list1 : list2;
        }
        // 两个链表元素依次对比
        if(list1.val <= list2.val){
            // 递归计算 list1.next, list2
            list1.next = Merge(list1.next, list2);
            return list1;
        }else{
            // 递归计算 list1, list2.next
            list2.next = Merge(list1, list2.next);
            return list2;
        } 
    }
}

BM6 判断链表中是否有环

判断给定的链表中是否有环。如果有环则返回true，否则返回false。

数据范围：链表长度 0≤n≤10000，链表中任意节点的值满足 ∣val∣<=100000

思路：快慢指针

如果有回环，快慢指针肯定会相遇

时间复杂度：O（N）

空间复杂度：O（1）

还有一种思路：使用HashSet来存节点，看是否用重复的就行，但这种方法的空间复杂度是O（N）

public class Solution {
    public boolean hasCycle(ListNode head) {
        //先判断链表为空的情况
        if(head == null) 
            return false;
        //快慢双指针
        ListNode fast = head; 
        ListNode slow = head;
        //如果没环快指针会先到链表尾
        while(fast != null && fast.next != null){ 
            //快指针移动两步
            fast = fast.next.next; 
            //慢指针移动一步
            slow = slow.next; 
            //相遇则有环
            if(fast == slow) 
                return true;
        }
        //到末尾则没有环
        return false; 
    }
}

BM7 链表中环的入口结点

给一个长度为n链表，若其中包含环，请找出该链表的环的入口结点，否则，返回null。

数据范围： n≤10000，1<=结点值<=10000

要求：空间复杂度 O(1)，时间复杂度 O(n)

思路：快慢指针

经典题目，主要在于数学推导部分。

可以直接背一下～

public class Solution {
    public ListNode detectCycle(ListNode head) {
        if(head == null) return null;
        ListNode slow = head,fast = head;
        while(fast != null){
            slow = slow.next;
            if(fast.next != null){
                fast = fast.next.next;
            }else{
                return null;
            }
            if(fast == slow ){
                ListNode ptr = head;
                while(ptr != slow){
                    ptr = ptr.next;
                    slow = slow.next;
                }
                return ptr;
            }
        }
        return null;
    }
}

BM8 链表中倒数最后k个结点

输入一个长度为 n 的链表，设链表中的元素的值为 ai ，返回该链表中倒数第k个节点。

如果该链表长度小于k，请返回一个长度为 0 的链表。

要求：空间复杂度 O(n)，时间复杂度 O(n)

进阶：空间复杂度 O(1)，时间复杂度 O(n)

思路：快慢指针

要得到倒数第k个，就可以声明两个指针

第一个指针先走k步，然后两个指针再一起走，等到第一个指针为null的时候，第二个指针即为倒数第k个节点

时间复杂度：O（N）

空间复杂度：O（1）

第二种空间复杂度为O（N）的思路就是使用栈就行～

public ListNode FindKthToTail (ListNode pHead, int k) {
        // write code here
        ListNode fast = pHead;
        ListNode slow = pHead;
        for(int i = 0 ; i < k ; i++){
            if(fast == null){
                return null;
            }
            fast = fast.next;
        }
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        return slow;
    }

BM9 删除链表的倒数第n个节点

给定一个链表，删除链表的倒数第 n 个节点并返回链表的头指针

例如，

给出的链表为: 1→2→3→4→5, n=2
删除了链表的倒数第 n个节点之后,链表变为1→2→3→5

数据范围：链表长度 0≤n≤1000，链表中任意节点的值满足 0≤val≤100

要求：空间复杂度 O(1)，时间复杂度 O(n)

备注：

题目保证 n 一定是有效的

思路：快慢指针

要求空间复杂度为O（1）。因此和上题一样的思路，但是和上题找到倒数第k个节点不同的是，这里需要删除，所以应该找到倒数k+1个节点，然后将它的next指向到倒数第k-1个节点。

所以很简单的思路就是把slow指向head的前面一个哑节点，也俗称dummyHead，这样的话不会造成越界～

public ListNode removeNthFromEnd (ListNode head, int n) {
        // write code here
        ListNode fast = head;
        ListNode dummyHead = new ListNode(-1);
        dummyHead.next = head;
        ListNode slow =dummyHead;

        for(int i = 0 ; i < n ; i++){
            fast = fast.next
        }
        while(fast != null){
            fast = fast.next;
            slow = slow.next;
        }
        slow.next = slow.next.next;
        return dummyHead.next;
    }

BM10 两个链表的第一个公共结点

输入两个无环的单向链表，找出它们的第一个公共结点，如果没有公共节点则返回空。（注意因为传入数据是链表，所以错误测试数据的提示是用其他方式显示的，保证传入数据是正确的）

数据范围： n≤100
要求：空间复杂度 O(1)，时间复杂度 O(n)

思路：双指针

很经典的一个题，很好理解。注意这里为什么判断条件是l1和l2是否相等，因为两个指针要么找到公共节点的时候相等，要么就是同时为null。

public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode l1 = pHead1, l2 = pHead2;
        while(l1 != l2){
            l1 = (l1==null)?pHead2:l1.next;
            l2 = (l2==null)?pHead1:l2.next;
        }
        return l1;
    }

BM11 链表相加(二)

假设链表中每一个节点的值都在 0 - 9 之间，那么链表整体就可以代表一个整数。

给定两个这种链表，请生成代表两个整数相加值的结果链表。

数据范围：0≤n,m≤1000000，链表任意值 0≤val≤9
要求：空间复杂度 O(n))，时间复杂度 O(n)

例如：链表 1 为 9->3->7，链表 2 为 6->3，最后生成新的结果链表为 1->0->0->0。

思路：直接模拟

public ListNode addInList (ListNode head1, ListNode head2) {
        // 进行判空处理
        if(head1 == null)
            return head2;
        if(head2 == null){
            return head1;
        }
        // 反转h1链表
        head1 = reverse(head1);
        // 反转h2链表
        head2 = reverse(head2);
        // 创建新的链表头节点
        ListNode head = new ListNode(-1);
        ListNode nHead = head;
        // 记录进位的数值
        int tmp = 0;
        while(head1 != null || head2 != null){
            // val用来累加此时的数值（加数+加数+上一位的进位=当前总的数值）
            int val = tmp;
            // 当节点不为空的时候，则需要加上当前节点的值
            if (head1 != null) {
                val += head1.val;
                head1 = head1.next;
            }
            // 当节点不为空的时候，则需要加上当前节点的值
            if (head2 != null) {
                val += head2.val;
                head2 = head2.next;
            }
            // 求出进位
            tmp = val/10;
            // 进位后剩下的数值即为当前节点的数值
            nHead.next = new ListNode(val%10);
            // 下一个节点
            nHead = nHead.next;

        }
        // 最后当两条链表都加完的时候，进位不为0的时候，则需要再加上这个进位
        if(tmp > 0){
            nHead.next = new ListNode(tmp);
        }
        // 重新反转回来返回
        return reverse(head.next);
    }

    // 反转链表
    ListNode reverse(ListNode head){
        if(head == null)
            return head;
        ListNode cur = head;
        ListNode node = null;
        while(cur != null){
            ListNode tail = cur.next;
            cur.next = node;
            node = cur;
            cur = tail;
        }
        return node;
    }

时间复杂度：O（N）
空间复杂度：O（1）

BM12 单链表的排序

给定一个节点数为n的无序单链表，对其按升序排序。

数据范围：0<n≤100000，保证节点权值在[−109,109][−109,109]之内。

要求：空间复杂度 O(n)，时间复杂度 O(nlogn)

思路：转化为数组排序

链表不能按照下表进行访问，因此可以借用数组。

public class Solution {
    public ListNode sortInList (ListNode head) {
        ArrayList<Integer> nums = new ArrayList(); 
        ListNode p = head;
        //遍历链表，将节点值加入数组
        while(p != null){ 
            nums.add(p.val);
            p = p.next;
        }
        p = head;
        //对数组元素排序
        Collections.sort(nums); 
        //遍历数组
        for(int i = 0; i < nums.size(); i++){ 
            //将数组元素依次加入链表
            p.val = nums.get(i); 
            p = p.next;
        }
        return head;
    }
}

时间复杂度：O(nlog2n)，sort函数一般为优化后的快速排序，复杂度为O(nlog2n)
空间复杂度：O(n)，存储链表元素值的辅助数组长度n

BM13 判断一个链表是否为回文结构

给定一个链表，请判断该链表是否为回文结构。

回文是指该字符串正序逆序完全一致。

数据范围：链表节点数 0≤n≤1050≤n≤105，链表中每个节点的值满足 ∣val∣≤107∣val∣≤107

思路：反转链表逐一判断

思路很清晰，找到中点，反转后逐一判断，需要注意的是奇数情况要考虑一下～

时间复杂度：O（N），遍历链表
空间复杂度：O（1）

还有一种更好理解的方法：将链表转化为list来做（只存数据大小），不过这种想法的空间复杂度为O（N）

import java.util.*;
/*
* public class ListNode {
*   int val;
*   ListNode next = null;
* }
*/
public class Solution {
  /**
   * 
   * @param head ListNode类 the head
   * @return bool布尔型
   */
  public boolean isPail(ListNode head) {
  ListNode q= head, p= head;
  //通过快慢指针找到中点
  while (q != null && q.next != null) {
      q = q.next.next;
      p = p.next;
  }
  //如果q不为空，说明链表的长度是奇数个
  if (q != null) {
      p = p.next;
  }
  //反转后半部分链表
  p = reverse(p);

  q = head;
  while (p != null) {
      //然后比较，判断节点值是否相等
      if (q.val != p.val)
          return false;
      q = q.next;
      p = p.next;
  }
  return true;
}
//反转链表
public ListNode reverse(ListNode head) {
  ListNode prev = null;
  while (head != null) {
      ListNode next = head.next;
      head.next = prev;
      prev = head;
      head = next;
  }
  return prev;
}
}

BM14 链表的奇偶重排

描述
给定一个单链表，请设定一个函数，将链表的奇数位节点和偶数位节点分别放在一起，重排后输出。

注意是节点的编号而非节点的数值。

数据范围：节点数量满足 0≤n≤105，节点中的值都满足 0≤val≤1000

要求：空间复杂度 O(n)，时间复杂度 O(n)

思路：双指针

定义一个双指针，一个指向奇数节点，一个指向偶数节点，遍历操作就好了～

时间复杂度：O（N）
空间复杂度：O（1）

import java.util.*;
public class Solution {
    public ListNode oddEvenList (ListNode head) {
        //如果链表为空，不用重排
        if(head == null) 
            return head;
        //even开头指向第二个节点，可能为空
        ListNode even = head.next; 
        //odd开头指向第一个节点
        ListNode odd = head; 
        //指向even开头
        ListNode evenhead = even; 
        while(even != null && even.next != null){
            //odd连接even的后一个，即奇数位
            odd.next = even.next; 
            //odd进入后一个奇数位
            odd = odd.next; 
            //even连接后一个奇数的后一位，即偶数位
            even.next = odd.next; 
            //even进入后一个偶数位
            even = even.next; 
        } 
        //even整体接在odd后面
        odd.next = evenhead; 
        return head;
    }
}

BM15 删除有序链表中重复的元素-I

删除给出链表中的重复元素（链表中元素从小到大有序），使链表中的所有元素都只出现一次
例如：
给出的链表为1→1→2,返回1→2.
给出的链表为1→1→2→3→3,返回1→2→3

数据范围：链表长度满足 0≤n≤100，链表中任意节点的值满足 ∣val∣≤100

思路：遍历

很容易想到的一个思路，遇到相同的数据，保留第一个遇到的即可。

public class Solution {
    public ListNode deleteDuplicates (ListNode head) {
        //空链表
        if(head == null) 
            return null;
        //遍历指针
        ListNode cur = head; 
        //指针当前和下一位不为空
        while(cur != null && cur.next != null){ 
            //如果当前与下一位相等则忽略下一位
            if(cur.val == cur.next.val) 
                cur.next = cur.next.next;
            //否则指针正常遍历
            else 
                cur = cur.next;
        }
        return head;
    }
}

时间复杂度：O（N）
空间复杂度：O（1）

BM16 删除有序链表中重复的元素-II

给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
例如：
给出的链表为1→2→3→3→4→4→5, 返回1→2→5.
给出的链表为1→1→1→2→3, 返回2→3.

数据范围：链表长度 0≤n≤100000≤n≤10000，链表中的值满足 ∣val∣≤1000∣val∣≤1000

要求：空间复杂度 O(n)，时间复杂度 O(n)

进阶：空间复杂度 O(1)，时间复杂度 O(n)

思路：遍历

注意，这个题和前面一题的不同之处在于：删除所有的相同元素

大部分逻辑和前面一个题一样～

import java.util.*;
public class Solution {
    public ListNode deleteDuplicates (ListNode head) {
        //空链表
        if(head == null) 
            return null;
        ListNode res = new ListNode(0);
        //在链表前加一个表头
        res.next = head; 
        ListNode cur = res;
        while(cur.next != null && cur.next.next != null){ 
            //遇到相邻两个节点值相同
            if(cur.next.val == cur.next.next.val){ 
                int temp = cur.next.val;
                //将所有相同的都跳过
                while (cur.next != null && cur.next.val == temp) 
                    cur.next = cur.next.next;
            }
            else 
                cur = cur.next;
        }
        //返回时去掉表头
        return res.next; 
    }
}

时间复杂度：O（N）
空间复杂度：O（1）

二、二分查找

BM17 二分查找-I

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

BM18 二维数组中的查找

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

[

[1,2,8,9],
[2,4,9,12],
[4,7,10,13],
[6,8,11,15]

]

给定 target = 7，返回 true。

给定 target = 3，返回 false。

数据范围：矩阵的长宽满足 0≤n,m≤500 ，矩阵中的值满足 0≤val≤109
进阶：空间复杂度 O(1) ，时间复杂度 O(n+m)

思路：二分查找

首先看四个角，左上与右下必定为最小值与最大值，而左下与右上就有规律了：左下元素大于它上方的元素，小于它右方的元素，右上元素与之相反。既然左下角元素有这么一种规律，相当于将要查找的部分分成了一个大区间和小区间，每次与左下角元素比较，我们就知道目标值应该在哪部分中，于是可以利用分治思维来做。

public class Solution {
    public boolean Find(int target, int [][] array) {
        //优先判断特殊
        if(array.length == 0)  
            return false;
        int n = array.length;
        if(array[0].length == 0)  
            return false;
        int m = array[0].length;
        //从最左下角的元素开始往左或往上
        for(int i = n - 1, j = 0; i >= 0 && j < m; ){ 
            //元素较大，往上走
            if(array[i][j] > target)   
                i--;
            //元素较小，往右走
            else if(array[i][j] < target) 
                j++;
            else
                return true;
        }
        return false;
    }
}

时间复杂度：O(m+n)，遍历矩阵的时候，最多经过矩阵的一行一列
空间复杂度：O(1)，常数级变量，无额外辅助空间

BM19 寻找峰值

给定一个长度为n的数组nums，请你找到峰值并返回其索引。数组可能包含多个峰值，在这种情况下，返回任何一个所在位置即可。

1.峰值元素是指其值严格大于左右相邻值的元素。严格大于即不能有等于

2.假设 nums[-1] = nums[n] = −∞−∞

3.对于所有有效的 i 都有 nums[i] != nums[i + 1]

4.你可以使用O(logN)的时间复杂度实现此问题吗？

思路：二分查找

nums[mid] < nums[mid + 1]说明在“上坡”，则可以使left = mid + 1（因为mid肯定不是峰值），向“峰”处压缩
nums[mid] > nums[mid + 1]说明在“下坡”，则应该使right = mid（mid可能是峰值），往“峰”处压缩

虽然开始left和right之间可能有多个峰值，但是随着left和right不断逼近，最后两者之间一定会压缩到一个峰值上，因为两者都是向“峰”不断靠近的，但是不会超过最终的“峰”

public class Solution {
    public int findPeakElement (int[] nums) {
        int left = 0;
        int right = nums.length - 1;
        //二分法
        while(left < right){ 
            int mid = (left + right) / 2;
            //右边是往上，一定有坡峰
            if(nums[mid] < nums[mid + 1])
                left = mid+1;
            //左边是往上，一定能找到波峰
            else
                right = mid;
        }
        //其中一个波峰
        return right; 
    }
}

BM20 数组中的逆序对

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

要求：空间复杂度 O(n)，时间复杂度 O(nlogn)

思路：归并排序

归并排序」与「逆序对」是息息相关的。归并排序体现了 “分而治之” 的算法思想，具体为：

分：不断将数组从中点位置划分开（即二分法），将整个数组的排序问题转化为子数组的排序问题；
治：划分到子数组长度为 1 时，开始向上合并，不断将较短排序数组合并为较长排序数组，直至合并至原数组时完成排序；

public class Solution {
    int count = 0;
    public int InversePairs(int [] array) {
        // 长度小于2则无逆序对
        if(array.length < 2)
            return 0;
        // 进入归并
        mergeSort(array,0,array.length-1);
        return count;
    }

    public void mergeSort(int[] array,int left,int right){
        // 找分割点
        int mid = left+(right-left)/2;
        if(left < right){
            // 左子数组
            mergeSort(array,left,mid);
            // 右子数组
            mergeSort(array,mid+1,right);
            // 并
            merge(array,left,mid,right);
        }
    }

    public void merge(int[] array,int left,int mid,int right){
        // 创建临时数组，长度为此时两个子数组加起来的长度
        int[] arr =  new int[right-left+1];
        // 临时数组的下标起点
        int c = 0;
        // 保存在原数组的起点下标值
        int s = left;
        // 左子数组的起始指针
        int l = left;
        // 右子数组的起始指针
        int r = mid+1;
        while(l <= mid && r <= right ){
            // 当左子数组的当前元素小的时候，跳过，无逆序对
            if(array[l] <= array[r]){
                // 放入临时数组
                arr[c] = array[l];
                // 临时数组下标+1
                c++;
                // 左子数组指针右移
                l++;
            }else{ // 否则，此时存在逆序对
                // 放入临时数组
                arr[c] = array[r];
                // 逆序对的个数为    左子数组的终点- 当前左子数组的当前指针
                count += mid+1-l;
                count %= 1000000007;
                // 临时数组+1
                c++;
                // 右子数组的指针右移
                r++;
            }
        }

        // 左子数组还有元素时，全部放入临时数组
        while(l <= mid)
            arr[c++] = array[l++];
        // 右子数组还有元素时，全部放入临时数组
        while(r <= right)
            arr[c++] = array[r++];
        // 将临时数组中的元素放入到原数组的指定位置
        for(int num:arr){
            array[s++] = num;
        }
    }
}

时间复杂度：O(NlogN)。归并排序的时间复杂度
空间复杂度：O(N)。临时数组的空间。

BM21 旋转数组的最小数字

有一个长度为 n 的非降序数组，比如[1,2,3,4,5]，将它进行旋转，即把一个数组最开始的若干个元素搬到数组的末尾，变成一个旋转数组，比如变成了[3,4,5,1,2]，或者[4,5,1,2,3]这样的。请问，给定这样一个旋转数组，求数组中的最小值。

数据范围：1≤n≤10000，数组中任意元素的值: 0≤val≤10000

要求：空间复杂度：O(1) ，时间复杂度：O(logn)

思路：二分查找

import java.util.ArrayList;
public class Solution {
    public int minNumberInRotateArray(int [] array) {
        int left = 0;
        int right = array.length - 1;
        while(left < right){
            int mid = (left + right) / 2;
            //最小的数字在mid右边
            if(array[mid] > array[right]) 
                left = mid + 1;
            //无法判断，一个一个试
            else if(array[mid] == array[right]) 
                right--;
            //最小数字要么是mid要么在mid左边
            else 
                right = mid;
        }
        return array[left];
    }
}

BM22 比较版本号

牛客项目发布项目版本时会有版本号，比如1.02.11，2.14.4等等

现在给你2个版本号version1和version2，请你比较他们的大小

版本号是由修订号组成，修订号与修订号之间由一个”.”连接。1个修订号可能有多位数字组成，修订号可能包含前导0，且是合法的。例如，1.02.11，0.1，0.2都是合法的版本号

每个版本号至少包含1个修订号。

修订号从左到右编号，下标从0开始，最左边的修订号下标为0，下一个修订号下标为1，以此类推。

比较规则：

一. 比较版本号时，请按从左到右的顺序依次比较它们的修订号。比较修订号时，只需比较忽略任何前导零后的整数值。比如”0.1”和”0.01”的版本号是相等的

二. 如果版本号没有指定某个下标处的修订号，则该修订号视为0。例如，”1.1”的版本号小于”1.1.1”。因为”1.1”的版本号相当于”1.1.0”，第3位修订号的下标为0，小于1

三. version1 > version2 返回1，如果 version1 < version2 返回-1，不然返回0.

思路：双指针

step 1：利用两个指针表示字符串的下标，分别遍历两个字符串。
step 2：每次截取点之前的数字字符组成数字，即在遇到一个点之前，直接取数字，加在前面数字乘10的后面。（因为int会溢出，这里采用long记录数字）
step 3：然后比较两个数字大小，根据大小关系返回1或者-1，如果全部比较完都无法比较出大小关系，则返回0.

import java.util.*;
public class Solution {
    public int compare (String version1, String version2) {
        int n1 = version1.length();
        int n2 = version2.length();
        int i = 0, j = 0;
        //直到某个字符串结束
        while(i < n1 || j < n2){
            long num1 = 0;
            //从下一个点前截取数字
            while(i < n1 && version1.charAt(i) != '.'){ 
                num1 = num1 * 10 + (version1.charAt(i) - '0');
                i++;
            }
            //跳过点
            i++; 
            long num2 = 0;
            //从下一个点前截取数字
            while(j < n2 && version2.charAt(j) != '.'){ 
                num2 = num2 * 10 + (version2.charAt(j) - '0');
                j++;
            }
            //跳过点
            j++; 
            //比较数字大小
            if(num1 > num2) 
                return 1;
            if(num1 < num2)
                return -1;
        }
        //版本号相同
        return 0; 
    }
}

时间复杂度：O(max(n,m))，其中m和n分别为两个字符串的长度，遍历两个字符串，复杂度选取较高值
空间复杂度：O(1)，常数级变量，无额外辅助空间

三、二叉树

BM23 二叉树的前序遍历

给你二叉树的根节点 root ，返回它节点值的前序遍历。

数据范围：二叉树的节点数量满足 1≤n≤100 1≤n≤100 ，二叉树节点的值满足 1≤val≤100 1≤val≤100 ，树的各节点的值各不相同

思路：递归

class Solution {
    public List<Integer> preorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<Integer>();
        preorder(root, res);
        return res;
    }

    public void preorder(TreeNode root, List<Integer> res) {
        if (root == null) {
            return;
        }
        res.add(root.val);
        preorder(root.left, res);
        preorder(root.right, res);
    }
}

BM24 二叉树的中序遍历

BM25 二叉树的后序遍历

这几个题就不记录了，套板子就行～

BM26 求二叉树的层序遍历

思路：BFS（广度优先搜索）

DFS（深度优先搜索）和 BFS（广度优先搜索）就像孪生兄弟，提到一个总是想起另一个。然而在实际使用中，我们用 DFS 的时候远远多于 BFS。那么，是不是 BFS 就没有什么用呢？

如果我们使用 DFS/BFS 只是为了遍历一棵树、一张图上的所有结点的话，那么 DFS 和 BFS 的能力没什么差别，我们当然更倾向于更方便写、空间复杂度更低的 DFS 遍历。不过，某些使用场景是 DFS 做不到的，只能使用 BFS 遍历。这就是本文要介绍的两个场景：「层序遍历」、「最短路径」

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> ret = new ArrayList<List<Integer>>();
        if (root == null) {
            return ret;
        }

        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            List<Integer> level = new ArrayList<Integer>();
            int currentLevelSize = queue.size();
            for (int i = 1; i <= currentLevelSize; ++i) {
                TreeNode node = queue.poll();
                level.add(node.val);
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
            ret.add(level);
        }
        
        return ret;
    }
}

时间复杂度：每个点进队出队各一次，故渐进时间复杂度为 O(n)。
空间复杂度：队列中元素的个数不超过 n 个，故渐进空间复杂度为 O(n)。

可以适当记一下这个模版～理解起来就比较好记了，核心是利用队列的思想。

BM27 按之字形顺序打印二叉树

给定一个二叉树，返回该二叉树的之字形层序遍历，（第一层从左向右，下一层从右向左，一直这样交替）

数据范围：0≤n≤1500,树上每个节点的val满足 ∣val∣<=1500
要求：空间复杂度：O(n)，时间复杂度：O(n)

思路：BFS

和前面层序遍历一样，只不过需要加一个flag来判断是否当前层该逆序

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer> > Print(TreeNode pRoot) {
        TreeNode head = pRoot;
        ArrayList<ArrayList<Integer> > res = new ArrayList<ArrayList<Integer>>();
        if(head == null)
            //如果是空，则直接返回空list
            return res; 
        //队列存储，进行层次遍历
        Queue<TreeNode> temp = new LinkedList<TreeNode>(); 
        temp.offer(head);
        TreeNode p;
        boolean flag = true;
        while(!temp.isEmpty()){
            //记录二叉树的某一行
            ArrayList<Integer> row = new ArrayList<Integer>();  
            int n = temp.size();
            //奇数行反转，偶数行不反转
            flag = !flag; 
            //因先进入的是根节点，故每层节点多少，队列大小就是多少
            for(int i = 0; i < n; i++){
                p = temp.poll();
                row.add(p.val);
                //若是左右孩子存在，则存入左右孩子作为下一个层次
                if(p.left != null)
                    temp.offer(p.left);
                if(p.right != null)
                    temp.offer(p.right);
            }
            //奇数行反转，偶数行不反转
            if(flag)  
                Collections.reverse(row);
            res.add(row);
        }
        return res;
    }
}

时间复杂度：O(n)，每个节点访问一次，因为reverse的时间复杂度为O(n)，按每层元素reverse也相当于O(n)
空间复杂度：O(n)，队列的空间最长为O(n)

BM28 二叉树的最大深度

思路：递归

思路很简单，直接递归就好～

import java.util.*;
public class Solution {
    public int maxDepth (TreeNode root) {
        //空节点没有深度
        if(root == null) 
            return 0;
        //返回子树深度+1
        return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1; 
    }
}

BM29 二叉树中和为某一值的路径(一)

给定一个二叉树root和一个值 sum ，判断是否有从根节点到叶子节点的节点值之和等于 sum 的路径。

1.该题路径定义为从树的根结点开始往下一直到叶子结点所经过的结点

2.叶子节点是指没有子节点的节点

3.路径只能从父节点到子节点，不能从子节点到父节点

4.总节点数目为n

思路：递归

import java.util.*;
public class Solution {
    public boolean hasPathSum (TreeNode root, int sum) {
        //空节点找不到路径
        if(root == null) 
            return false;
        //叶子节点，且路径和为sum
        if(root.left == null && root.right == null && sum - root.val == 0) 
            return true;
        //递归进入子节点
        return hasPathSum(root.left, sum - root.val) || hasPathSum(root.right, sum - root.val); 
    }
}

BM30 二叉搜索树与双向链表

输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。如下图所示

思路：利用二叉搜索树的特征进行递归

核心：二叉搜索树最左端的元素一定最小，最右端的元素一定最大，符合“左中右”的特性，因此二叉搜索树的中序遍历就是一个递增序列，我们只要对它中序遍历就可以组装称为递增双向链表。

public class Solution {
    //返回的第一个指针，即为最小值，先定为null
    public TreeNode head = null;  
    //中序遍历当前值的上一位，初值为最小值，先定为null
    public TreeNode pre = null;   
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null)
            //中序递归，叶子为空则返回
            return null;     
        //首先递归到最左最小值  
        Convert(pRootOfTree.left); 
        //找到最小值，初始化head与pre
        if(pre == null){       
            head = pRootOfTree;
            pre = pRootOfTree;
        }
        //当前节点与上一节点建立连接，将pre设置为当前值
        else{       
            pre.right = pRootOfTree;
            pRootOfTree.left = pre;
            pre = pRootOfTree;
        }
        Convert(pRootOfTree.right);
        return head;
    }
}

时间复杂度：O(n)，其中nn为二叉树节点数，中序遍历所有节点
空间复杂度：O(n)，递归栈所需要的最大空间

BM31 对称的二叉树

给定一棵二叉树，判断其是否是自身的镜像（即：是否对称）
例如：下面这棵二叉树是对称的

思路：递归

public class Solution {
    boolean isSymmetrical(TreeNode pRoot) {
        if(pRoot == null) return true;
        return compare(pRoot.left,pRoot.right);
    }

    boolean compare(TreeNode left, TreeNode right){
      //可以两个都为空
        if(left == null && right == null)   return true;
       //只有一个为空或者节点值不同，必定不对称
        if(left == null || right == null || left.val != right.val) return false;
      //每层对应的节点进入递归比较
        return compare(left.left,right.right)&&compare(left.right,right.left);
    }
}

时间复杂度：O(n)，其中nn为二叉树的节点数，相当于遍历整个二叉树两次
空间复杂度：O(n)，最坏情况二叉树退化为链表，递归栈深度为nn

BM32 合并二叉树

已知两颗二叉树，将它们合并成一颗二叉树。合并规则是：都存在的结点，就将结点值加起来，否则空的位置就由另一个树的结点来代替。例如：

思路：递归

import java.util.*;
public class Solution {
    public TreeNode mergeTrees (TreeNode t1, TreeNode t2) {
        //若只有一个节点返回另一个，两个都为null自然返回null
        if (t1 == null) 
            return t2;
        if (t2 == null)
            return t1;
        //根左右的方式递归
        TreeNode head = new TreeNode(t1.val + t2.val);
        head.left = mergeTrees(t1.left, t2.left);
        head.right = mergeTrees(t1.right, t2.right);
        return head;
    }
}

BM33 二叉树的镜像

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

数据范围：二叉树的节点数 0≤n≤1000，二叉树每个节点的值 0≤val≤1000

要求：空间复杂度 O(n)。本题也有原地操作，即空间复杂度 O(1)的解法，时间复杂度 O(n)

import java.util.*;
public class Solution {
    public TreeNode Mirror (TreeNode pRoot) {
        //空树返回
        if(pRoot == null) 
            return null;
        //先递归子树
        TreeNode left = Mirror(pRoot.left);  
        TreeNode right = Mirror(pRoot.right);
        //交换
        pRoot.left = right; 
        pRoot.right = left;
        return pRoot;
    }
}

BM34 判断是不是二叉搜索树

给定一个二叉树根节点，请你判断这棵树是不是二叉搜索树。

二叉搜索树满足每个节点的左子树上的所有节点均小于当前节点且右子树上的所有节点均大于当前节点。

import java.util.*;
public class Solution {
    int pre = Integer.MIN_VALUE;
    //中序遍历
    public boolean isValidBST (TreeNode root) { 
        if (root == null)
            return true;
        //先进入左子树
        if(!isValidBST(root.left)) 
            return false;
        if(root.val < pre)
            return false;
        //更新最值
        pre = root.val;
        //再进入右子树
        return isValidBST(root.right); 
    }
}

BM35 判断是不是完全二叉树

给定一个二叉树，确定他是否是一个完全二叉树。

完全二叉树的定义：若二叉树的深度为 h，除第 h 层外，其它各层的结点数都达到最大个数，第 h 层所有的叶子结点都连续集中在最左边，这就是完全二叉树。（第 h 层可能包含 [1~2h] 个节点）

思路：层序遍历BFS

对完全二叉树最重要的定义就是叶子节点只能出现在最下层和次下层，所以我们想到可以使用队列辅助进行层次遍历——从上到下遍历所有层，每层从左到右，只有次下层和最下层才有叶子节点，其他层出现叶子节点就意味着不是完全二叉树。

step 1：先判断空树一定是完全二叉树。
step 2：初始化一个队列辅助层次遍历，将根节点加入。
step 3：逐渐从队列中弹出元素访问节点，如果遇到某个节点为空，进行标记，代表到了完全二叉树的最下层，若是后续还有访问，则说明提前出现了叶子节点，不符合完全二叉树的性质。
step 4：否则，继续加入左右子节点进入队列排队，等待访问。

import java.util.*;
public class Solution {
    public boolean isCompleteTree (TreeNode root) {
        //空树一定是完全二叉树
        if(root == null) 
            return true;
        //辅助队列
        Queue<TreeNode> queue = new LinkedList<>(); 
        queue.offer(root);
        TreeNode cur;
        //定义一个首次出现的标记位
        boolean notComplete = false;
        while(!queue.isEmpty()){
            cur = queue.poll();
            //标记第一次遇到空节点
            if(cur == null){ 
                notComplete = true;
                continue;
            }
            //后续访问已经遇到空节点了，说明经过了叶子
            if(notComplete) 
                return false;
            queue.offer(cur.left);
            queue.offer(cur.right);
        }
        return true;
    }
}

时间复杂度：O(n)，其中nn为二叉树节点数，层次遍历最坏情况下遍历每一个节点
空间复杂度：O(n)，最坏情况下，层次队列的最大空间为O(n)

BM36 判断是不是平衡二叉树

输入一棵节点数为 n 二叉树，判断该二叉树是否是平衡二叉树。

在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树

平衡二叉树（Balanced Binary Tree），具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。

思路：从底至顶

class Solution {
    public boolean isBalanced(TreeNode root) {
        return recur(root) != -1;
    }

    private int recur(TreeNode root) {
        if (root == null) return 0;
        int left = recur(root.left);
        if(left == -1) return -1;
        int right = recur(root.right);
        if(right == -1) return -1;
        return Math.abs(left - right) < 2 ? Math.max(left, right) + 1 : -1;
    }
}

BM37 二叉搜索树的最近公共祖先

给定一个二叉搜索树, 找到该树中两个指定节点的最近公共祖先。

1.对于该题的最近的公共祖先定义:对于有根树T的两个节点p、q，最近公共祖先LCA(T,p,q)表示一个节点x，满足x是p和q的祖先且x的深度尽可能大。在这里，一个节点也可以是它自己的祖先.

2.二叉搜索树是若它的左子树不空，则左子树上所有节点的值均小于它的根节点的值；若它的右子树不空，则右子树上所有节点的值均大于它的根节点的值

3.所有节点的值都是唯一的。

4.p、q 为不同节点且均存在于给定的二叉搜索树中。

思路：遍历

step 1：根据二叉搜索树的性质，从根节点开始查找目标节点，当前节点比目标小则进入右子树，当前节点比目标大则进入左子树，直到找到目标节点。这个过程成用数组记录遇到的元素。
step 2：分别在搜索二叉树中找到p和q两个点，并记录各自的路径为数组。
step 3：同时遍历两个数组，比较元素值，最后一个相等的元素就是最近的公共祖先。

import java.util.*;
public class Solution {
    //求得根节点到目标节点的路径
    public ArrayList<Integer> getPath(TreeNode root, int target) {
        ArrayList<Integer> path = new ArrayList<Integer>();
        TreeNode node = root;
        //节点值都不同，可以直接用值比较
        while(node.val != target){ 
            path.add(node.val);
            //小的在左子树
            if(target < node.val) 
                node = node.left;
            //大的在右子树
            else 
                node = node.right;
        }
        path.add(node.val);
        return path;
    }
    public int lowestCommonAncestor (TreeNode root, int p, int q) {
        //求根节点到两个节点的路径
        ArrayList<Integer> path_p = getPath(root, p); 
        ArrayList<Integer> path_q = getPath(root, q);
        int res = 0;
        //比较两个路径，找到第一个不同的点
        for(int i = 0; i < path_p.size() && i < path_q.size(); i++){ 
            int x = path_p.get(i);
            int y = path_q.get(i);
            //最后一个相同的节点就是最近公共祖先
            if(x == y) 
                res = path_p.get(i);
            else
                break;
        }
        return res;
    }
}

时间复杂度：O(n)，设二叉树共有nn个节点，因此最坏情况二叉搜索树变成链表，搜索到目标节点需要O(n)O(n)，比较路径前半段的相同也需要O(n)
空间复杂度：O(n)，记录路径的数组最长为n

BM38 在二叉树中找到两个节点的最近公共祖先

给定一棵二叉树(保证非空)以及这棵树上的两个节点对应的val值 o1 和 o2，请找到 o1 和 o2 的最近公共祖先节点。

数据范围：树上节点数满足 1≤n≤105 , 节点值val满足区间 [0,n)

要求：时间复杂度 O(n)

思路：回溯+DFS

step 1：利用dfs求得根节点到两个目标节点的路径：每次选择二叉树的一棵子树往下找，同时路径数组增加这个遍历的节点值。
step 2：一旦遍历到了叶子节点也没有，则回溯到父节点，寻找其他路径，回溯时要去掉数组中刚刚加入的元素。
step 3：然后遍历两条路径数组，依次比较元素值。
step 4：找到两条路径第一个不相同的节点即是最近公共祖先。

import java.util.*;
public class Solution {
    //记录是否找到到o的路径
    public boolean flag = false; 
    //求得根节点到目标节点的路径
    public void dfs(TreeNode root, ArrayList<Integer> path, int o){ 
        if(flag || root == null)
            return;
        path.add(root.val);
        //节点值都不同，可以直接用值比较
        if(root.val == o){ 
            flag = true;
            return;
        }
        //dfs遍历查找
        dfs(root.left, path, o); 
        dfs(root.right, path, o);
        //找到
        if(flag)
            return;
        //回溯
        path.remove(path.size() - 1);
    }
    public int lowestCommonAncestor (TreeNode root, int o1, int o2) {
        ArrayList<Integer> path1 = new ArrayList<Integer>(); 
        ArrayList<Integer> path2 = new ArrayList<Integer>(); 
        //求根节点到两个节点的路径
        dfs(root, path1, o1); 
        //重置flag，查找下一个
        flag = false; 
        dfs(root, path2, o2);
        int res = 0; 
        //比较两个路径，找到第一个不同的点
        for(int i = 0; i < path1.size() && i < path2.size(); i++){ 
            int x = path1.get(i);
            int y = path2.get(i);
            if(x == y) 
                //最后一个相同的节点就是最近公共祖先
                res = x; 
            else
                break;
        }
        return res;
    }
}

时间复杂度：O(n)，其中nn为二叉树节点数，递归遍历二叉树每一个节点求路径，后续又遍历路径
空间复杂度：O(n)，最坏情况二叉树化为链表，深度为nn，递归栈深度和路径数组为n

这个回溯值得看一下

BM40 重建二叉树

给定节点数为 n 的二叉树的前序遍历和中序遍历结果，请重建出该二叉树并返回它的头结点。

例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6}，则重建出如下图所示。

step 1：先根据前序遍历第一个点建立根节点。
step 2：然后遍历中序遍历找到根节点在数组中的位置。
step 3：再按照子树的节点数将两个遍历的序列分割成子数组，将子数组送入函数建立子树。
step 4：直到子树的序列长度为0，结束递归。

import java.util.*;
public class Solution {
    public TreeNode reConstructBinaryTree(int [] pre,int [] vin) {
        int n = pre.length;
        int m = vin.length;
        //每个遍历都不能为0
        if(n == 0 || m == 0) 
            return null;
        //构建根节点
        TreeNode root = new TreeNode(pre[0]);
        for(int i = 0; i < vin.length; i++){
            //找到中序遍历中的前序第一个元素
            if(pre[0] == vin[i]){ 
                //构建左子树
                root.left = reConstructBinaryTree(Arrays.copyOfRange(pre, 1, i + 1), Arrays.copyOfRange(vin, 0, i)); 
                //构建右子树
                root.right = reConstructBinaryTree(Arrays.copyOfRange(pre, i + 1, pre.length), Arrays.copyOfRange(vin, i + 1, vin.length));
                break;
            }
        }
        return root;
    }
}

时间复杂度：O(n)，其中n为数组长度，即二叉树的节点数，构建每个节点进一次递归，递归中所有的循环加起来一共n次
空间复杂度：O(n)，递归栈最大深度不超过n，辅助数组长度也不超过n，重建的二叉树空间属于必要空间，不属于辅助空间

BM41 输出二叉树的右视图

四、堆/栈/队列

BM42 用两个栈实现队列

用两个栈来实现一个队列，使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。

思路：栈

直接模拟就好

import java.util.Stack;
public class Solution {
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();
  //这里最好还是用Deque<Integer> stack = new ArrayDeque<>();来声明栈
    
    public void push(int node) {
        stack1.push(node);
    }
    
    public int pop() {
        //将第一个栈中内容弹出放入第二个栈中
        while(!stack1.isEmpty()) 
            stack2.push(stack1.pop()); 
        //第二个栈栈顶就是最先进来的元素，即队首
        int res = stack2.pop(); 
        //再将第二个栈的元素放回第一个栈
        while(!stack2.isEmpty()) 
            stack1.push(stack2.pop());
        return res;
    }
}

BM43 包含min函数的栈

定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的 min 函数，输入操作时保证 pop、top 和 min 函数操作时，栈中一定有元素。

思路：

import java.util.Stack;

public class Solution {
    //用于栈的push 与 pop
    Stack<Integer> s1 = new Stack<Integer>(); 
    //用于存储最小min
    Stack<Integer> s2 = new Stack<Integer>(); 
  
  //这里最好还是用Deque<Integer> stack = new ArrayDeque<>();来声明栈
    public void push(int node) {
        s1.push(node);  
        //空或者新元素较小，则入栈
        if(s2.isEmpty() || s2.peek() > node)  
            s2.push(node);
        else
            //重复加入栈顶
            s2.push(s2.peek());  
    }
    
    public void pop() {
        s1.pop();
        s2.pop();
    }
    
    public int top() {
        return s1.peek();
    }
    
    public int min() {
        return s2.peek();
    }
}

BM44 有效括号序列

给出一个仅包含字符’(‘,’)’,’{‘,’}’,’[‘和’]’,的字符串，判断给出的字符串是否是合法的括号序列
括号必须以正确的顺序关闭，”()”和”()[]{}”都是合法的括号序列，但”(]”和”([)]”不合法。

数据范围：字符串长度 0≤n≤10000

要求：空间复杂度 O(n)，时间复杂度 O(n)

思路：模拟栈

step 1：创建辅助栈，遍历字符串。
step 2：每次遇到小括号的左括号、中括号的左括号、大括号的左括号，就将其对应的呦括号加入栈中，期待在后续遇到。
step 3：如果没有遇到左括号但是栈为空，说明直接遇到了右括号，不合法。
step 4：其他情况下，如果遇到右括号，刚好会与栈顶元素相同，弹出栈顶元素继续遍历。
step 5：理论上，只要括号是匹配的，栈中元素最后是为空的，因此检查栈是否为空即可最后判断是否合法。

import java.util.*;
public class Solution {
    public boolean isValid (String s) {
        //辅助栈
        Stack<Character> st = new Stack<Character>();
        //遍历字符串
        for (int i = 0; i < s.length(); i++) {
            //遇到左小括号
            if (s.charAt(i) == '(')
                //期待遇到右小括号
                st.push(')');
            //遇到左中括号
            else if (s.charAt(i) == '[')
                //期待遇到右中括号
                st.push(']');
            //遇到左打括号
            else if (s.charAt(i) == '{')
                //期待遇到右打括号
                st.push('}');
            //必须有左括号的情况下才能遇到右括号
            else if (st.isEmpty() || st.pop() != s.charAt(i))
                return false;
        }
        //栈中是否还有元素
        return st.isEmpty();
    }
}

BM45 滑动窗口的最大值

给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。

输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
输出: [3,3,5,5,6,7]
解释:

滑动窗口的位置最大值

[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7

思路：单调队列

import java.util.*;
public class Solution {
    public ArrayList<Integer> maxInWindows(int [] num, int k) {
        ArrayList<Integer> res = new ArrayList<>();
        if (num.length == 0 || k == 0) return res;
        Deque<Integer> deque = new ArrayDeque<Integer>();
        
        for (int j = 0, i = 1 - k ; j < num.length; i++, j++) {
          // 删除 deque 中对应的 nums[i-1]
            if (i > 0 && deque.peekFirst() == num[i - 1])
                deque.removeFirst();
          // 保持 deque 递减
            while (!deque.isEmpty() && deque.peekLast() < num[j])
                deque.removeLast();
            deque.addLast(num[j]);
            // 记录窗口最大值
            if (i >= 0)
                res.add(deque.peekFirst());
        }
        return res;
    }
}

BM46 最小的K个数

给定一个长度为 n 的可能有重复值的数组，找出其中不去重的最小的 k 个数。例如数组元素是4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4(任意顺序皆可)。

数据范围：0≤k,n≤10000，数组中每个数的大小0≤val≤1000

要求：空间复杂度 O(n) ，时间复杂度 O(nlogk)

思路1：sort快排

import java.util.*;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        //排除特殊情况
        if(k == 0 || input.length == 0) 
            return res;
        //排序
        Arrays.sort(input); 
        //因为k<=input.length,取前k小
        for(int i = 0; i < k; i++){ 
            res.add(input[i]);
        }
        return res;
    }
}

时间复杂度：O(nlog2n)，sort函数属于优化后的快速排序，复杂度为O(nlog2n)O(nlo**g2n)
空间复杂度：O(1)，无额外辅助空间使用

思路2：堆排序

优先队列即PriorityQueue，是一种内置的机遇堆排序的容器，分为大顶堆与小顶堆，大顶堆的堆顶为最大元素，其余更小的元素在堆下方，小顶堆与其刚好相反。且因为容器内部的次序基于堆排序，因此每次插入元素时间复杂度都是O(log2n)，而每次取出堆顶元素都是直接取出。

step 1：利用input数组中前k个元素，构建一个大小为k的大顶堆，堆顶为这k个元素的最大值。
step 2：对于后续的元素，依次比较其与堆顶的大小，若是比堆顶小，则堆顶弹出，再将新数加入堆中，直至数组结束，保证堆中的k个最小。
step 3：最后将堆顶依次弹出即是最小的k个数。

import java.util.*;
public class Solution {
    public ArrayList<Integer> GetLeastNumbers_Solution(int [] input, int k) {
        ArrayList<Integer> res = new ArrayList<Integer>();
        //排除特殊情况
        if(k == 0 || input.length == 0) 
            return res;
        //大根堆 
        PriorityQueue<Integer> q = new PriorityQueue<>((o1, o2)->o2.compareTo(o1));
        //构建一个k个大小的堆  
        for(int i = 0; i < k; i++)
            q.offer(input[i]);
        for(int i = k; i < input.length; i++){
            //较小元素入堆
            if(q.peek() > input[i]){  
                q.poll();
                q.offer(input[i]);
            }
        }
        //堆中元素取出入数组
        for(int i = 0; i < k; i++) 
            res.add(q.poll());
        return res;
    }
}

时间复杂度：O(nlog2k)，构建和维护大小为kk的堆，需要log2klog2k，加上遍历整个数组
空间复杂度：O(k)，堆空间为k个元素

BM47 寻找第K大

有一个整数数组，请你根据快速排序的思路，找出数组中第 k 大的数。

给定一个整数数组 a ,同时给定它的大小n和要找的 k ，请返回第 k 大的数(包括重复的元素，不用去重)，保证答案存在。

要求：时间复杂度 O(nlogn)，空间复杂度 O(1)

数据范围：0≤n≤1000， 1≤K≤n，数组中每个元素满足 0≤val≤10000000

思路1：随机选择

速排序的思想–随机选择法，时间复杂度 O(n) 需要理解两个思想，快排的分治，二分查找的剪枝分治法，每个分支“都要”递归，例如：快速排序，O(n*lg(n)) 减治法，“只要”递归一个分支，例如：二分查找O(lg(n))，随机选择O(n) TopK的另一个解法：随机选择 + partition。

其实要找第k大，前面的排序再取值已经知道了第K大的数，下标是len - k。那么partition能直接定位到len - k 的位置就找到了结果。如何找呢，就用到了二分查找的思想，不断接近len-k的位置，最终返回结果。

import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        return quickSort(a, 0, a.length - 1, K);
    }

    private int quickSort(int[] arr, int left, int right, int k){
        int p = partition(arr, left, right);
        // 改进后，很特殊的是，p是全局下标，只要p对上topK坐标就可以返回
        if (p == arr.length - k) {
            return arr[p];
        }else if (p < arr.length - k) {
            // 如果基准在左边，这在右边找
            return quickSort(arr, p + 1, right,k);
        }else {
            return quickSort(arr, left, p - 1,k);
        }
    }

    private int partition(int[] arr, int left, int right) {
        // 可优化成随机，或中位数
        int key = arr[left];
        while (left < right) {
            while (left < right && arr[right] >= key) right--;
            arr[left] = arr[right];
            while (left < right && arr[left] <= key) left++;
            arr[right] = arr[left];
        }
        arr[left] = key;
        return left;
    }
}

思路2：内置方法

全局排序，时间复杂度取决于排序算法，一般是 O(n*lgn)。相信大多数朋友看到这题的思路就是排序，返回第k大的值，甚至还有小机灵鬼直接调用内置方法

import java.util.*;

public class Solution {
    public int findKth(int[] a, int n, int K) {
        // write code here
        Arrays.sort(a);
        return a[n-K];
    }
}

BM48 数据流中的中位数

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

思路：优先级队列

困难题目，详解参考：k神。讲的很到位

有一点需要注意：

A（小顶堆，存储较大的一半）
B（大顶堆，存储较小的一半）

假设插入数字 num 遇到情况 m=n的时候，也即数据为偶数的时候。由于 num 可能属于 “较小的一半” （即属于 B ），因此不能将 nums 直接插入至 A（小顶堆，存储较大的一半）。而应先将 num 插入至 B ，再将 B 堆顶元素插入至 A 。这样就可以始终保持 A 保存较大一半、 B 保存较小一半。

import java.util.*;

public class Solution {
    Queue<Integer> A,B;
    public Solution(){
        A = new PriorityQueue<>();
        B = new PriorityQueue<>(Comparator.reverseOrder());
    }
    public void Insert(int num) {
        if(A.size() != B.size()){
            A.add(num);
            B.add(A.poll());
        }else{
            B.add(num);
            A.add(B.poll());
        }
    }

    public Double GetMedian() {
        return (Double)(A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0);
    }
}

BM49 表达式求值

请写一个整数计算器，支持加减乘三种运算和括号。

数据范围：0≤∣s∣≤100，保证计算结果始终在整型范围内

要求：空间复杂度： O(n)，时间复杂度 O(n)

五、哈希

BM50 两数之和

给出一个整型数组 numbers 和一个目标值 target，请在数组中找出两个加起来等于目标值的数的下标，返回的下标按升序排列。

（注：返回的数组下标从1开始算起，保证target一定可以由数组里面2个数字相加得到）

思路：哈希

很简单～不记录了

主要是要记得：map.containsKey（）、return new int[]{}这两个语法

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

给一个长度为 n 的数组，数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。

例如输入一个长度为9的数组[1,2,3,2,2,2,5,4,2]。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。

数据范围：n≤5000，数组中元素的值 0≤val≤10000

要求：空间复杂度：O(1)，时间复杂度 O(n)

思路：哈希

一样很简答的一题

import java.util.*;

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int res = 0;
        Map<Integer,Integer> map = new HashMap<>();
        int len = array.length;
        for(int i = 0 ; i < len ; i++){
            map.put(array[i],map.getOrDefault(array[i],0)+1);
            if(map.get(array[i]) > len/2){
                res = array[i];
            }
        }
        return res;
    }
}

BM52 数组中只出现一次的两个数字

一个整型数组里除了两个数字只出现一次，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param array int整型一维数组 
     * @return int整型一维数组
     */
    public int[] FindNumsAppearOnce (int[] array) {
        // write code here
        ArrayList<Integer> res = new ArrayList<>();
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0 ; i < array.length ;i++){
            map.put(array[i],map.getOrDefault(array[i],0)+1);
        }
        for(int i = 0 ; i < array.length ; i ++){
            if(map.get(array[i]) == 1){
                res.add(array[i]);
            }
        }
        return res.get(0) < res.get(1)?new int[]{res.get(0),res.get(1)}:new int[]{res.get(1),res.get(0)};
    }
}

BM53 缺失的第一个正整数

给定一个无重复元素的整数数组nums，请你找出其中没有出现的最小的正整数

import java.util.*;
public class Solution {
    public int minNumberDisappeared (int[] nums) {
        int n = nums.length;
        HashMap<Integer, Integer> mp = new HashMap<Integer, Integer>(); 
        //哈希表记录数组中出现的每个数字
        for(int i = 0; i < n; i++) 
            mp.put(nums[i], 1);
        int res = 1;
        //从1开始找到哈希表中第一个没有出现的正整数
        while(mp.containsKey(res)) 
            res++;
        return res;
    }
}

BM 54 三数之和

思路：排序+双指针

import java.util.*;
public class Solution {
    public ArrayList<ArrayList<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        ArrayList<ArrayList<Integer>> res = new ArrayList<>();
        for (int k = 0; k < nums.length - 2; k++) {
            if (nums[k] > 0) break;
            if (k > 0 && nums[k] == nums[k - 1]) continue;
            int i = k + 1, j = nums.length - 1;
            while (i < j) {
                int sum = nums[k] + nums[i] + nums[j];
                if (sum < 0) {
                    while (i < j && nums[i] == nums[++i]);
                } else if (sum > 0) {
                    while (i < j && nums[j] == nums[--j]);
                } else {
                    res.add(new ArrayList<Integer>(Arrays.asList(nums[k], nums[i], nums[j])));
                    while (i < j && nums[i] == nums[++i]);
                    while (i < j && nums[j] == nums[--j]);
                }
            }
        }
        return res;
    }
}

BM55 没有重复项数字的全排列

给出一组数字，返回该组数字的所有排列

例如：

[1,2,3]的所有排列如下
[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2], [3,2,1].
（以数字在数组中的位置靠前为优先级，按字典序排列输出。）

数据范围：数字个数 0<n≤6

要求：空间复杂度 O(n!) ，时间复杂度 O(n!）

思路：回溯

这个理解有点难，可以适当记一下～

import java.util.*;

public class Solution {
    List<List<Integer>> res;

    public ArrayList<ArrayList<Integer>> permute(int[] num) {
      res = new ArrayList<List<Integer>>();
      // 存一种排列
        LinkedList<Integer> list = new LinkedList<Integer>();
      // 递归进行
        backTrack(num,list);
        return res;
    }

    public void backTrack(int[] num , LinkedList<Integer> list){
      // 当list中的长度等于数组的长度，则证明此时已经找到一种排列了
        if(list.size() == num.length){
          // add进返回结果集中
            res.add(new ArrayList<Integer>(list));
            return ;
        }
      // 遍历num数组
        for(int i = 0 ; i < num.length ; i++){
          // 若当前位置中的数已经添加过了则跳过
            if(list.contains(num[i]))
                continue;
          // 选择该数
            list.add(num[i]);
          // 继续寻找
            backTrack(num,list);
          // 撤销最后一个
            list.removeLast();
        }
    }
}

更快的写法：

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();

        List<Integer> output = new ArrayList<Integer>();
        for (int num : nums) {
            output.add(num);
        }

        int n = nums.length;
        backtrack(n, output, res, 0);
        return res;
    }

    public void backtrack(int n, List<Integer> output, List<List<Integer>> res, int first) {
        // 所有数都填完了
        if (first == n) {
            res.add(new ArrayList<Integer>(output));
        }
        for (int i = first; i < n; i++) {
            // 动态维护数组
            Collections.swap(output, first, i);
            // 继续递归填下一个数
            backtrack(n, output, res, first + 1);
            // 撤销操作
            Collections.swap(output, first, i);
        }
    }
}

或者：

其实这种写法和第一种写法本质上一样～

最好背下面这个！


class Solution {
    List<List<Integer>> list ;
    boolean[] visit;
  
    public List<List<Integer>> permute(int[] nums) {
       list = new ArrayList<>();
       visit = new boolean[nums.length];
       List<Integer> tmp = new ArrayList<>();
       permute(nums,0,tmp);
       return list;
    }

    public void permute(int[] nums,int dp,List<Integer> tmp){
        if(dp == nums.length){
            list.add(new ArrayList(tmp));
            return;
        }

        for(int i = 0;i < nums.length;i++){
            if(!visit[i]){
                tmp.add(nums[i]);
                visit[i] = true;

                permute(nums,dp+1,tmp);

                tmp.remove(tmp.size()-1);
                visit[i] = false;
            }
        }
    }
}

BM56 有重复项数字的全排列

给出一组可能包含重复项的数字，返回该组数字的所有排列。结果以字典序升序排列。

思路：回溯

和上个题目一样，区别是要加一个判断条件

class Solution {
    List<List<Integer>> res;
    boolean[] visit;

    public List<List<Integer>> permuteUnique(int[] nums) {
        res = new ArrayList<List<Integer>>();
        ArrayList<Integer> temp = new ArrayList<>();
        visit = new boolean[nums.length];
        Arrays.sort(nums);
        backTrack(nums, 0 , temp);
        return res;
    }

    public void backTrack(int[] nums , int dp , ArrayList<Integer> temp ){
        if(temp.size() == nums.length){
            res.add(new ArrayList<Integer>(temp));
            return;
        }

        for(int i = 0 ; i < nums.length ; i++){
          //关键在于这里：如果当前数已经被访问过了，或者当前数和前面一个数一样而且前面一个数没有访问过
          //就直接跳过本次循环，
            if(visit[i] || (i > 0 && nums[i] == nums[i - 1] && !visit[i - 1])){
                continue;
            }
            temp.add(nums[i]);
            visit[i] = true;

            backTrack(nums,dp+1 ,temp);

            temp.remove(temp.size()-1);
            visit[i] = false;
        }
    }
}

BM57 岛屿数量

给一个01矩阵，1代表是陆地，0代表海洋，如果两个1相邻，那么这两个1属于同一个岛。我们只考虑上下左右为相邻。

岛屿: 相邻陆地可以组成一个岛屿（相邻:上下左右）判断岛屿个数。

思路：dfs

比较简单的想法就是：找到一个1，就把离这个1最近的1全部变为0～

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for(int i = 0 ; i < grid.length ; i++){
            for(int j = 0 ; j < grid[0].length;j++){
                if(grid[i][j] == '1'){
                    dfs(grid,i,j);
                    count++;
                }
            }
        }
        return count;
    }

    public void dfs(char[][] grid,int i , int j){
        if(i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0' )   return;
        grid[i][j] = '0';
        dfs(grid,i-1,j);
        dfs(grid,i+1,j);
        dfs(grid,i,j-1);
        dfs(grid,i,j+1);
    }
}

BM58 字符串的排列

输入一个长度为 n 字符串，打印出该字符串中字符的所有排列，你可以以任意顺序返回这个字符串数组。

例如输入字符串ABC,则输出由字符A,B,C所能排列出来的所有字符串ABC,ACB,BAC,BCA,CBA和CAB。

思路：回溯

和前面的回溯一样，可以套模版


import java.util.*;

public class Solution {
    ArrayList<String> res;
    boolean[] visit;

    public ArrayList<String> Permutation(String str) {
        res = new ArrayList<String>();
        visit = new boolean[str.length()];

        char[] chars = str.toCharArray();
        Arrays.sort(chars);
        String str_new = new String(chars);
        StringBuilder temp = new StringBuilder();

        backTrack(str_new , 0 ,temp );
        return res;
    }

    public void backTrack(String str , int dp , StringBuilder temp){
        if(dp == str.length()){
            res.add(new String(temp));
            return;
        }
        for(int i = 0 ; i < str.length();i++){
            if(visit[i] || (i>0 && str.charAt(i) == str.charAt(i-1) && !visit[i-1])){
                continue;
            }
            temp.append(str.charAt(i));
            visit[i] = true;

            backTrack(str,dp+1,temp);
            temp.deleteCharAt(temp.length()-1);
            visit[i] = false;
        }
    }
}

BM60 括号生成

给出n对括号，请编写一个函数来生成所有的由n对括号组成的合法组合。

例如，给出n=3，解集为：

“((()))”, “(()())”, “(())()”, “()()()”, “()(())”

import java.util.*;


public class Solution {
    /**
     * 
     * @param n int整型 
     * @return string字符串ArrayList
     */
    public ArrayList<String> generateParenthesis (int n) {
        // write code here
        ArrayList<String> res = new ArrayList<String>();
        if(n == 0){
            return res;
        }
        dfs("" , n , n ,res);
        return res;
    }

    public void dfs(String str , int left ,int right , ArrayList<String> res){
        if(left == 0 && right == 0){
            res.add(str);
            return ;
        }
        if(left > right){
            return ;
        }
        if(left > 0){
            dfs(str+"(" , left-1 , right , res);
        }
        if(right > 0){
            dfs(str+")" , left , right-1 ,res);
        }
    }
}

BM61 矩阵最长递增路径

给定一个 n 行 m 列矩阵 matrix ，矩阵内所有数均为非负整数。你需要在矩阵中找到一条最长路径，使这条路径上的元素是递增的。并输出这条最长路径的长度。

这个路径必须满足以下条件：

\1. 对于每个单元格，你可以往上，下，左，右四个方向移动。你不能在对角线方向上移动或移动到边界外。

\2. 你不能走重复的单元格。即每个格子最多只能走一次。

思路：记忆搜索

结合了dfs的想法～

class Solution {

    // 上下左右四个方向
    int[][] dirs = new int[][]{{1, 0}, {-1, 0}, {0, 1}, {0, -1}};

    public int longestIncreasingPath(int[][] matrix) {
        // 从每一个点出发，往下深搜，看它最远能到哪
        int m = matrix.length;
        int n = matrix[0].length;

        // 记忆化
        int[][] memo = new int[m][n];
        
        // 每个点都要作为起始点遍历一下
        int ans = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                // 已经遍历过的就不用遍历了
                if (memo[i][j] == 0) {
                    ans = Math.max(ans, dfs(matrix, m, n, i, j, memo));
                }
                // 这里为什么不用再比较一次 ans 和 memo[i][j]呢？
                // 因为遍历前面节点的时候已经把后面的节点遍历了
                // 说明后面的节点肯定比前面的节点的最长路径短
                // 所以，不用多判断一次了
            }
        }

        return ans;
    }

    private int dfs(int[][] matrix, int m, int n, int i, int j, int[][] memo) {
        // 已经遍历过，直接返回
        if (memo[i][j] != 0) {
            return memo[i][j];
        }

        // 否则，看四个方向是否有满足条件的节点去扩散
        // 每个节点的初始路径为1
        int ans = 1;
        for (int[] dir : dirs) {
            int nextI = i + dir[0];
            int nextJ = j + dir[1];
            if (nextI >= 0 && nextJ >= 0 && nextI < m && nextJ <n && matrix[nextI][nextJ] > matrix[i][j]) {
                ans = Math.max(ans, dfs(matrix, m, n, nextI, nextJ, memo) + 1);
            }
        }

        // 记录到缓存中
        memo[i][j] = ans;
        return ans;
    }
}

七、动态规划

BM62 斐波那契数列

public class Solution {
    public int Fibonacci(int n) {
        if(n <= 1){
            return n;
        }
        int[] dp = new int[n+1];
        dp[0] = 0;
        dp[1] = 1;
        for(int i = 2 ; i <= n ;i++){
            dp[i] = dp[i-2]+dp[i-1];
        }
        return dp[n];
    }
}

BM63 跳台阶

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

数据范围：1≤�≤401≤n≤40

要求：时间复杂度：�(�)O(n) ，空间复杂度： �(1)O(1)

public class Solution {
    public int jumpFloor(int target) {
        int[] dp = new int[target+1];
        dp[0] = 1;
        dp[1] = 1;
        for(int i = 2 ; i <= target ;i++){
            dp[i] = dp[i-1]+dp[i-2];
        }
        return dp[target];
    }
}

BM64 最小花费爬楼梯

给定一个整数数组 �� cos**t ，其中 ��[�] cos**t[i] 是从楼梯第� i 个台阶向上爬需要支付的费用，下标从0开始。一旦你支付此费用，即可选择向上爬一个或者两个台阶。

你可以选择从下标为 0 或下标为 1 的台阶开始爬楼梯。

请你计算并返回达到楼梯顶部的最低花费。

数据范围：数组长度满足 1≤�≤105 1≤n≤105 ，数组中的值满足 1≤��≤104 1≤costi≤104

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 
     * @param cost int整型一维数组 
     * @return int整型
     */
    public int minCostClimbingStairs (int[] cost) {
        // write code here

        int len = cost.length;
        int[] dp = new int[len+1];
        dp[0] = 0;
        dp[1] = 0;
        for(int i = 2 ; i < len+1 ; i++){
            dp[i] = Math.min((dp[i-1]+cost[i-1]),(dp[i-2]+cost[i-2]));
        }
        return dp[len];
    }
}

BM65 最长公共子序列(二)

给定两个字符串str1和str2，输出两个字符串的最长公共子序列。如果最长公共子序列为空，则返回”-1”。目前给出的数据，仅仅会存在一个最长的公共子序列

思路：动态规划

和leetcode的题目很类似：剑指 Offer II 095. 最长公共子序列

只不过leetcode只用返回长度，本题需要返回公共子序列

但是想法还是一样的。

import java.util.*;


public class Solution {
    /**
     * longest common subsequence
     * @param s1 string字符串 the string
     * @param s2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String s1, String s2) {
        // write code here
        int n = s1.length(),m = s2.length();
        int[][] dp = new int[n+1][m+1];
        for(int i = 1 ; i <= n;i++){
            char char1 = s1.charAt(i-1);
            for(int j = 1 ; j <= m;j++){
                char char2 = s2.charAt(j-1);
                if(char1 == char2){
                    dp[i][j] = 1+dp[i-1][j-1];
                }else{
                    dp[i][j] = Math.max(dp[i-1][j],dp[i][j-1]);
                }
            }
        }
      //return dp[n][m]; 这上面即为leecode题目的代码
      //下面部分即为根据长度来反向收集字符
      
        if(dp[n][m] == 0 ) return "-1";
        StringBuilder res = new StringBuilder();
        while(n>0 && m>0){
            if(s1.charAt(n-1) == s2.charAt(m-1)){
                res.append(s1.charAt(n-1));
                n--;m--;
            }else{
                if(dp[n-1][m] > dp[n][m-1]){
                    n--;
                }else{
                    m--;
                }
            }
        }
        return res.reverse().toString();
    }
}

BM66 最长公共子串

给定两个字符串str1和str2,输出两个字符串的最长公共子串

题目保证str1和str2的最长公共子串存在且唯一。

思路：动态规划

本题和前面一题的区别在于：需要连续才能认定为子串

step 1：我们可以用dp{i}{j}表示在str1中以第i个字符结尾在str2中以第j个字符结尾时的公共子串长度，
step 2：遍历两个字符串填充dp数组，转移方程为：如果遍历到的该位两个字符相等，则此时长度等于两个前一位长度+1，dp{i}{j} = dp{i-1}{j-1}+1，如果遍历到该位时两个字符不相等，则置为0，因为这是子串，必须连续相等，断开要重新开始。
step 3：每次更新dp{i}{j}后，我们维护最大值，并更新该子串结束位置。
step 4：最后根据最大值结束位置即可截取出子串。

import java.util.*;


public class Solution {
    /**
     * longest common substring
     * @param str1 string字符串 the string
     * @param str2 string字符串 the string
     * @return string字符串
     */
    public String LCS (String str1, String str2) {
        // write code here
        int n = str1.length() , m = str2.length();
        int[][] dp = new int[n+1][m+1];
        int max = 0 , end = 0;
        for(int i = 1 ; i <= n ;i++){
            for(int j = 1 ; j <= m ; j++){
                if(str1.charAt(i-1) == str2.charAt(j-1)){
                    dp[i][j] = 1+ dp[i-1][j-1];
                }else{
                  //如果遍历到该位时两个字符不相等，则置为0，因为这是子串，必须连续相等，断开要重新开始。
                    dp[i][j] = 0;
                }
                if(dp[i][j] > max){
                  //如果出现新的最长，则更新字符串结束为止和max
                    max = dp[i][j];
                    end = i-1;
                }
            }
        }
        return str1.substring(end - max +1,end+1);
    }
}

BM67 不同路径的数目(一)

一个机器人在m×n大小的地图的左上角（起点）。

机器人每次可以向下或向右移动。机器人要到达地图的右下角（终点）。

可以有多少种不同的路径从起点走到终点？

import java.util.*;


public class Solution {
    /**
     * 
     * @param m int整型 
     * @param n int整型 
     * @return int整型
     */
    public int uniquePaths (int m, int n) {
        // write code here
        int[][] dp = new int[m][n];
        for(int i = 0 ; i < m ; i++){
            dp[i][0] = 1;
        }
        for(int i = 0 ; i < n ; i++){
            dp[0][i] = 1;
        }
        for(int i = 1 ; i < m ; i++){
            for(int j = 1 ; j < n ;j++){
                dp[i][j] = dp[i-1][j] + dp[i][j-1];
            }
        }
        return dp[m-1][n-1];
    }
}

BM68 矩阵的最小路径和

给定一个 n * m 的矩阵 a，从左上角开始每次只能向右或者向下走，最后到达右下角的位置，路径上所有的数字累加起来就是路径和，输出所有的路径中最小的路径和。

import java.util.*;


public class Solution {
    /**
     * 
     * @param matrix int整型二维数组 the matrix
     * @return int整型
     */
    public int minPathSum (int[][] matrix) {
        // write code here
        int row = matrix.length , col = matrix[0].length;
        int[][] dp = new int[row][col];
        dp[0][0] = matrix[0][0];
        for(int i = 1 ; i < row ; i++){
            dp[i][0] = matrix[i][0] + dp[i - 1][0];
        }
        for(int j = 1 ; j < col ; j++){
            dp[0][j] = matrix[0][j] + dp[0][j - 1];
        }
        
        for(int i = 1 ; i < row ; i++){
            for(int j = 1 ; j < col ; j++){
                dp[i][j] = matrix[i][j] + (dp[i - 1][j] > dp[i][j - 1] ? dp[i][j - 1] : dp[i - 1][j]);
            }
        }
        return dp[row-1][col-1];
    }
}

BM69 把数字翻译成字符串

有一种将字母编码成数字的方式：’a’->1, ‘b->2’, … , ‘z->26’。

现在给一串数字，返回有多少种可能的译码结果

import java.util.*;
public class Solution {
    public int solve (String nums) {
        //排除0
        if(nums.equals("0"))  
            return 0;
        //排除只有一种可能的10 和 20
        if(nums == "10" || nums == "20")  
            return 1;
        //当0的前面不是1或2时，无法译码，0种
        for(int i = 1; i < nums.length(); i++){  
            if(nums.charAt(i) == '0')
                if(nums.charAt(i - 1) != '1' && nums.charAt(i - 1) != '2')
                    return 0;
        }
        int[] dp = new int[nums.length() + 1];
        //辅助数组初始化为1
        Arrays.fill(dp, 1);  
        for(int i = 2; i <= nums.length(); i++){
            //在11-19，21-26之间的情况
            if((nums.charAt(i - 2) == '1' && nums.charAt(i - 1) != '0') || (nums.charAt(i - 2) == '2' && nums.charAt(i - 1) > '0' && nums.charAt(i - 1) < '7'))
               dp[i] = dp[i - 1] + dp[i - 2];
            else
                dp[i] = dp[i - 1];
        }
        return dp[nums.length()];
    }
}

BM70 兑换零钱(一)

给定数组arr，arr中所有的值都为正整数且不重复。每个值代表一种面值的货币，每种面值的货币可以使用任意张，再给定一个aim，代表要找的钱数，求组成aim的最少货币数。

如果无解，请返回-1.

1 2	输入：[5,2,3],20 返回值：4

思路：完全背包问题——动态规划

先遍历物品，再遍历背包——求组合数

class Solution {
    public int coinChange(int[] coins, int amount) {
        int max = Integer.MAX_VALUE;
        int[] dp = new int[amount + 1];
        //初始化dp数组为最大值
        for (int j = 0; j < dp.length; j++) {
            dp[j] = max;
        }
        //当金额为0时需要的硬币数目为0
        dp[0] = 0;
        for (int i = 0; i < coins.length; i++) {
            //正序遍历：完全背包每个硬币可以选择多次
            for (int j = coins[i]; j <= amount; j++) {
                //只有dp[j-coins[i]]不是初始最大值时，该位才有选择的必要
                if (dp[j - coins[i]] != max) {
                    //选择硬币数目最小的情况
                    dp[j] = Math.min(dp[j], dp[j - coins[i]] + 1);
                }
            }
        }
        return dp[amount] == max ? -1 : dp[amount];
    }
}

先遍历背包，再遍历物品——求排列数

import java.util.*;
public class Solution {
    public int minMoney (int[] arr, int aim) {
        //小于1的都返回0
        if(aim < 1) 
            return 0;
        int[] dp = new int[aim + 1];
        //dp[i]表示凑齐i元最少需要多少货币数
        Arrays.fill(dp, aim + 1); 
        dp[0] = 0; 
        //遍历1-aim元
        for(int i = 1; i <= aim; i++){ 
            //每种面值的货币都要枚举
            for(int j = 0; j < arr.length; j++){ 
                //如果面值不超过要凑的钱才能用
                if(arr[j] <= i) 
                    //维护最小值
                    dp[i] = Math.min(dp[i], dp[i - arr[j]] + 1); 
            }
        }
        //如果最终答案大于aim代表无解
        return dp[aim] > aim ? -1 : dp[aim]; 
    }
}

BM71 最长上升子序列(一)

给定一个长度为 n 的数组 arr，求它的最长严格上升子序列的长度。

所谓子序列，指一个数组删掉一些数（也可以不删）之后，形成的新数组。例如 [1,5,3,7,3] 数组，其子序列有：[1,3,3]、[7] 等。但 [1,6]、[1,3,5] 则不是它的子序列。

1
2
3

输入：[6,3,1,5,2,3,7]
返回：4
说明：该数组最长上升子序列为 [1,2,3,7] ，长度为4

思路：动态规划

1、状态方程的含义

本题，状态方程的含义：dp[i]表示i之前包括i的以nums[i]结尾的最长递增子序列的长度

2、状态转移方程

位置i的最长升序子序列等于j从0到i-1各个位置的最长升序子序列 + 1 的最大值。

所以：if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);

注意这里不是要dp[i] 与 dp[j] + 1进行比较，而是我们要取dp[j] + 1的最大值。

3、确定遍历顺序

dp[i] 是有0到i-1各个位置的最长递增子序列推导而来，那么遍历i一定是从前向后遍历。

j其实就是遍历0到i-1，那么是从前到后，还是从后到前遍历都无所谓，只要吧 0 到 i-1 的元素都遍历了就行了。所以默认习惯从前向后遍历。

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * 给定数组的最长严格上升子序列的长度。
     * @param arr int整型一维数组 给定的数组
     * @return int整型
     */
    public int LIS (int[] arr) {
        // write code here
        int[] dp = new int[arr.length];
        Arrays.fill(dp,1);
        for(int i = 0 ; i < dp.length ; i++){
            for(int j = 0 ; j < i ; j++){
                if(arr[i] > arr[j]){
                    dp[i] = Math.max(dp[i],dp[j]+1);
                }
            }
        }
        int res = 0 ;
        for(int i = 0 ; i < dp.length ;i++){
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}

BM72 连续子数组的最大和

输入一个长度为n的整型数组array，数组中的一个或连续多个整数组成一个子数组，子数组最小长度为1。求所有子数组的和的最大值。

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

import java.util.*;

public class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int[] dp = new int[array.length];
        int min = Integer.MIN_VALUE;
        Arrays.fill(dp,min);
        dp[0] = array[0];
        for(int i = 1 ; i < array.length ; i++){
            if(dp[i-1] < 0){
                dp[i] = array[i];
            }else{
                dp[i] = Math.max(dp[i],dp[i-1]+array[i]);
            }
        }
        int res = Integer.MIN_VALUE ;
        for(int i = 0 ; i < dp.length ; i++){
            res = Math.max(res,dp[i]);
        }
        return res;
    }
}

BM73 最长回文子串

对于长度为n的一个字符串A（仅包含数字，大小写英文字母），请设计一个高效算法，计算其中最长回文子串的长度。

思路：中心扩展

step 1：遍历字符串每个字符。
step 2：以每次遍历到的字符为中心（分奇数长度和偶数长度两种情况），不断向两边扩展。
step 3：如果两边都是相同的就是回文，不断扩大到最大长度即是以这个字符（或偶数两个）为中心的最长回文子串。
step 4：我们比较完每个字符为中心的最长回文子串，取最大值即可。

import java.util.*;
public class Solution {
    public int fun(String s, int begin, int end){
        //每个中心点开始扩展
        while(begin >= 0 && end < s.length() && s.charAt(begin) == s.charAt(end)){ 
            begin--;
            end++;
        }
        //返回长度
        return end - begin - 1; 
    } 
    public int getLongestPalindrome (String A) {
        int maxlen = 1;
        //以每个点为中心
        for(int i = 0; i < A.length() - 1; i++) 
            //分奇数长度和偶数长度向两边扩展
            maxlen = Math.max(maxlen, Math.max(fun(A, i, i), fun(A, i, i + 1))); 
        return maxlen;
    }
}

BM74 数字字符串转化成IP地址

现在有一个只包含数字的字符串，将该字符串转化成IP地址的形式，返回所有可能的情况。

例如：

给出的字符串为”25525522135”,

返回[“255.255.22.135”, “255.255.221.35”]. (顺序没有关系)

思路：回溯

step 1：使用step记录分割出的数字个数，index记录递归的下标，结束递归是指step已经为4，且下标到达字符串末尾。
step 2：在主体递归中，每次加入一个字符当数字，最多可以加入三个数字，剩余字符串进入递归构造下一个数字。
step 3：然后要检查每次的数字是否合法（不超过255且没有前导0）.
step 4：合法IP需要将其连接，同时递归完这一轮后需要回溯。

import java.util.*;
public class Solution {
    //记录分段IP数字字符串
    private String nums = ""; 
    //step表示第几个数字，index表示字符串下标
    public void dfs(String s, ArrayList<String> res, int step, int index){ 
        //当前分割出的字符串
        String cur = ""; 
        //分割出了四个数字
        if(step == 4){ 
            //下标必须走到末尾
            if(index != s.length()) 
                return;
            res.add(nums);
        }else{
            //最长遍历3位
            for(int i = index; i < index + 3 && i < s.length(); i++){ 
                cur += s.charAt(i);
                //转数字比较
                int num = Integer.parseInt(cur); 
                String temp = nums;
                //不能超过255且不能有前导0
                if(num <= 255 && (cur.length() == 1 || cur.charAt(0) != '0')){ 
                    //添加点
                    if(step - 3 != 0) 
                        nums += cur + ".";
                    else
                        nums += cur;
                    //递归查找下一个数字
                    dfs(s, res, step + 1, i + 1); 
                    //回溯
                    nums = temp; 
                }
            }
        }
    }
    public ArrayList<String> restoreIpAddresses (String s) {
        ArrayList<String> res = new ArrayList<String>();
        dfs(s, res, 0, 0);
        return res;
    }
}

BM78 打家劫舍(一)

你是一个经验丰富的小偷，准备偷沿街的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即，如果偷了第一家，就不能再偷第二家；如果偷了第二家，那么就不能偷第一家和第三家。

给定一个整数数组nums，数组中的元素表示每个房间存有的现金数额，请你计算在不被发现的前提下最多的偷窃金额。

思路

1、确定dp数组（dp table）以及下标的含义

**dp[i]：考虑下标i（包括i）以内的房屋，最多可以偷窃的金额为dp[i]**。

2、确定递推公式

决定dp[i]的因素就是第i房间偷还是不偷。

如果偷第i房间，那么dp[i] = dp[i - 2] + nums[i] ，即：第i-1房一定是不考虑的，找出下标i-2（包括i-2）以内的房屋，最多可以偷窃的金额为dp[i-2] 加上第i房间偷到的钱。

如果不偷第i房间，那么dp[i] = dp[i - 1]，即考虑i-1房，（注意这里是考虑，并不是一定要偷i-1房，这是很多同学容易混淆的点）

// 动态规划
class Solution {
	public int rob(int[] nums) {
		if (nums == null || nums.length == 0) return 0;
		if (nums.length == 1) return nums[0];

		int[] dp = new int[nums.length];
		dp[0] = nums[0];
		dp[1] = Math.max(dp[0], nums[1]);
		for (int i = 2; i < nums.length; i++) {
			dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
		}

		return dp[nums.length - 1];
	}
}

BM79 打家劫舍(二)

你是一个经验丰富的小偷，准备偷沿湖的一排房间，每个房间都存有一定的现金，为了防止被发现，你不能偷相邻的两家，即，如果偷了第一家，就不能再偷第二家，如果偷了第二家，那么就不能偷第一家和第三家。沿湖的房间组成一个闭合的圆形，即第一个房间和最后一个房间视为相邻。

给定一个长度为n的整数数组nums，数组中的元素表示每个房间存有的现金数额，请你计算在不被发现的前提下最多的偷窃金额。

思路：动态规划

相较于前一题目，只需要分开讨论即可。对于一个数组，成环的话主要有如下三种情况：

1、情况一：考虑不包含首尾元素
2、情况二：考虑包含首元素，不包含尾元素
3、情况三：考虑包含尾元素，不包含首元素

而情况二和情况三都包含了情况一了，所以只考虑情况二和情况三就可以了。

class Solution {
    public int rob(int[] nums) {
        if (nums == null || nums.length == 0)
            return 0;
        int len = nums.length;
        if (len == 1)
            return nums[0];
        return Math.max(robAction(nums, 0, len - 1), robAction(nums, 1, len));
    }

    int robAction(int[] nums, int start, int end) {
        int x = 0, y = 0, z = 0;
        for (int i = start; i < end; i++) {
            y = z;
            z = Math.max(y, x + nums[i]);
            x = y;
        }
        return z;
    }
}

BM80 买卖股票的最好时机(一)

假设你有一个数组prices，长度为n，其中prices[i]是股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益

1.你可以买入一次股票和卖出一次股票，并非每天都可以买入或卖出一次，总共只能买入和卖出一次，且买入必须在卖出的前面的某一天

2.如果不能获取到任何利润，请返回0

3.假设买入卖出均无手续费

思路：贪心

class Solution {
    public int maxProfit(int[] prices) {
        // 找到一个最小的购入点
        int low = Integer.MAX_VALUE;
        // res不断更新，直到数组循环完毕
        int res = 0;
        for(int i = 0; i < prices.length; i++){
            low = Math.min(prices[i], low);
            res = Math.max(prices[i] - low, res);
        }
        return res;
    }
}

BM81 买卖股票的最好时机(二)

假设你有一个数组prices，长度为n，其中prices[i]是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益

你可以多次买卖该只股票，但是再次购买前必须卖出之前的股票
如果不能获取收益，请返回0
假设买入卖出均无手续费

思路：动态规划

如果第i天持有股票即dp[i][0]，那么可以由两个状态推出来

第i-1天就持有股票，那么就保持现状，所得现金就是昨天持有股票的所得现金即：dp[i - 1][0]
第i天买入股票，所得现金就是昨天不持有股票的所得现金减去今天的股票价格即：dp[i - 1][1] - prices[i]

再来看看如果第i天不持有股票即dp[i][1]的情况，依然可以由两个状态推出来

第i-1天就不持有股票，那么就保持现状，所得现金就是昨天不持有股票的所得现金即：dp[i - 1][1]
第i天卖出股票，所得现金就是按照今天股票价格卖出后所得现金即：prices[i] + dp[i - 1][0]

// 动态规划
class Solution 
    // 实现1：二维数组存储
    // 可以将每天持有与否的情况分别用 dp[i][0] 和 dp[i][1] 来进行存储
    // 时间复杂度：O(n)，空间复杂度：O(n)
    public int maxProfit(int[] prices) {
        int n = prices.length;
        int[][] dp = new int[n][2];     // 创建二维数组存储状态
        dp[0][0] = 0;                   // 初始状态
        dp[0][1] = -prices[0];
        for (int i = 1; i < n; ++i) {
            dp[i][0] = Math.max(dp[i - 1][0], dp[i - 1][1] + prices[i]);    // 第 i 天，没有股票
            dp[i][1] = Math.max(dp[i - 1][1], dp[i - 1][0] - prices[i]);    // 第 i 天，持有股票
        }
        return dp[n - 1][0];    // 卖出股票收益高于持有股票收益，因此取[0]
    }
}

BM82 买卖股票的最好时机(三)

假设你有一个数组prices，长度为n，其中prices[i]是某只股票在第i天的价格，请根据这个价格数组，返回买卖股票能获得的最大收益
\1. 你最多可以对该股票有两笔交易操作，一笔交易代表着一次买入与一次卖出，但是再次购买前必须卖出之前的股票
\2. 如果不能获取收益，请返回0
\3. 假设买入卖出均无手续费

思路：动态规划

关键在于至多买卖两次，这意味着可以买卖一次，可以买卖两次，也可以不买卖。

1、确定dp数组以及下标的含义

一天一共就有五个状态，

没有操作（其实我们也可以不设置这个状态）
第一次持有股票
第一次不持有股票
第二次持有股票
第二次不持有股票

dp[i][j]中 i表示第i天，j为 [0 - 4] 五个状态，dp[i][j]表示第i天状态j所剩最大现金。

2、确定递推公式

达到dp[i][1]状态，有两个具体操作：

操作一：第i天买入股票了，那么dp[i][1] = dp[i-1][0] - prices[i]
操作二：第i天没有操作，而是沿用前一天买入的状态，即：dp[i][1] = dp[i - 1][1]

那么dp[i][1]究竟选 dp[i-1][0] - prices[i]，还是dp[i - 1][1]呢？

一定是选最大的，所以 dp[i][1] = max(dp[i-1][0] - prices[i], dp[i - 1][1]);

同理dp[i][2]也有两个操作：

操作一：第i天卖出股票了，那么dp[i][2] = dp[i - 1][1] + prices[i]
操作二：第i天没有操作，沿用前一天卖出股票的状态，即：dp[i][2] = dp[i - 1][2]

所以dp[i][2] = max(dp[i - 1][1] + prices[i], dp[i - 1][2])

同理可推出剩下状态部分：

dp[i][3] = max(dp[i - 1][3], dp[i - 1][2] - prices[i]);

dp[i][4] = max(dp[i - 1][4], dp[i - 1][3] + prices[i]);

class Solution {
    public int maxProfit(int[] prices) {
        int len = prices.length;
        // 边界判断, 题目中 length >= 1, 所以可省去
        if (prices.length == 0) return 0;

        /*
         * 定义 5 种状态:
         * 0: 没有操作, 1: 第一次买入, 2: 第一次卖出, 3: 第二次买入, 4: 第二次卖出
         */
        int[][] dp = new int[len][5];
        dp[0][1] = -prices[0];
        // 初始化第二次买入的状态是确保 最后结果是最多两次买卖的最大利润
        dp[0][3] = -prices[0];

        for (int i = 1; i < len; i++) {
            dp[i][1] = Math.max(dp[i - 1][1], -prices[i]);
            dp[i][2] = Math.max(dp[i - 1][2], dp[i][1] + prices[i]);
            dp[i][3] = Math.max(dp[i - 1][3], dp[i][2] - prices[i]);
            dp[i][4] = Math.max(dp[i - 1][4], dp[i][3] + prices[i]);
        }

        return dp[len - 1][4];
    }
}

时间复杂度：O(n)
空间复杂度：O(1)

八、字符串

BM83 字符串变形

对于一个长度为 n 字符串，我们需要对它做一些变形。

首先这个字符串中包含着一些空格，就像”Hello World”一样，然后我们要做的是把这个字符串中由空格隔开的单词反序，同时反转每个字符的大小写。

比如”Hello World”变形后就变成了”wORLD hELLO”。

数据范围: 1≤�≤1061≤n≤106 , 字符串中包括大写英文字母、小写英文字母、空格。

进阶：空间复杂度 �(�)O(n) ，时间复杂度 �(�)O(n)

思路：双反转

step 1：遍历字符串，遇到小写字母，转换成大写，遇到大写字母，转换成小写，遇到空格正常不变。
step 2：第一次反转整个字符串，这样基本的单词逆序就有了，但是每个单词的字符也是逆的。
step 3：再次遍历字符串，以每个空间为界，将每个单词反转回正常。

import java.util.*;
public class Solution {
    public String trans(String s, int n) {
        if(n==0) 
            return s;
        StringBuffer res=new StringBuffer();
        for(int i = 0; i < n; i++){
            //大小写转换
            if(s.charAt(i) <= 'Z' && s.charAt(i) >= 'A')   
                res.append((char)(s.charAt(i) - 'A' + 'a'));
            else if(s.charAt(i) >= 'a' && s.charAt(i) <= 'z') 
                res.append((char)(s.charAt(i) - 'a' + 'A'));
            else 
                //空格直接复制
                res.append(s.charAt(i));  
        } 
        //翻转整个字符串
        res = res.reverse();
        for (int i = 0; i < n; i++){
            int j = i;
            //以空格为界，二次翻转
            while(j < n && res.charAt(j) != ' ')  
                j++;
            String temp = res.substring(i,j);
            StringBuffer buffer = new StringBuffer(temp);
            temp = buffer.reverse().toString();
            res.replace(i,j,temp);
            i = j;
        }
        return res.toString();
    }
}

BM84 最长公共前缀

给你一个大小为 n 的字符串数组 strs ，其中包含n个字符串 , 编写一个函数来查找字符串数组中的最长公共前缀，返回这个公共前缀。

数据范围： 0≤�≤50000≤n≤5000， 0≤��(��)≤50000≤len(strsi)≤5000

进阶：空间复杂度 �(1)O(1)，时间复杂度 �(�∗��)O(n∗len)

思路：遍历

import java.util.*;
public class Solution {
    public String longestCommonPrefix (String[] strs) {
        int n = strs.length;
        //空字符串数组
        if(n == 0) 
            return "";
        //遍历第一个字符串的长度
        for(int i = 0; i < strs[0].length(); i++){ 
            char temp = strs[0].charAt(i); 
            //遍历后续的字符串
            for(int j = 1; j < n; j++) 
                //比较每个字符串该位置是否和第一个相同
                if(i == strs[j].length() || strs[j].charAt(i) != temp) 
                    //不相同则结束
                    return strs[0].substring(0, i); 
        }
        //后续字符串有整个字一个字符串的前缀
        return strs[0]; 
    }
}

BM85 验证IP地址

验证一个ip地址是否非法，合法的话到底是IPv4还是IPv6

思路：正则表达式

1
2
3

IPv4：(([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])\\.){3}([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])

IPv6：([0-9a-fA-F]{1,4}\\:){7}[0-9a-fA-F]{1,4}

Ipv4正则表达式解释

1
(([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])\\.){3}([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])
该正则表达式用于匹配IPv4地址，其具体含义如下：

([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])：匹配0-255之间的数字。

\\.：匹配.字符。

(…){3}：匹配前面的表达式3次。

([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])：匹配0-255之间的数字。

因此，该正则表达式匹配的字符串是由四个数字组成，每个数字之间用.分隔，其中每个数字的取值范围是0-255。

正则表达式([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])是用来匹配IPv4地址中每个数字的取值范围的。IPv4地址中每个数字的取值范围是0-255，因此该正则表达式用来匹配这个范围内的数字。

该正则表达式中，每个|符号分隔的部分都表示一个数字的取值范围，具体解释如下：

[0-9]：匹配0-9之间的单个数字。

[1-9][0-9]：匹配10-99之间的数字。

1[0-9][0-9]：匹配100-199之间的数字。

2[0-4][0-9]：匹配200-249之间的数字。

25[0-5]：匹配250-255之间的数字。

因此，这些部分组合在一起，就能够匹配0-255之间的数字。例如，23、128、199、245、255都是符合该正则表达式的数字。

IPv6正则表达式解释：

1
([0-9a-fA-F]{1,4}\\:){7}[0-9a-fA-F]{1,4}
该正则表达式用于匹配IPv6地址，其具体含义如下：

([0-9a-fA-F]{1,4}\\:){7}：匹配由7组数字和冒号组成的字符串，每组数字的长度为1-4个字符，中间用:分隔。

[0-9a-fA-F]{1,4}：匹配长度为1-4个字符的数字和字母。

因此，该正则表达式匹配的字符串是由8组数字和冒号组成，其中每组数字的长度为1-4个字符，中间用:分隔。每组数字的取值范围是0-9和a-f（大小写不区分）。

import java.util.*;

import java.util.regex.*;


public class Solution {
    /**
     * 验证IP地址
     * @param IP string字符串 一个IP地址字符串
     * @return string字符串
     */
    public String solve (String IP) {
        // write code here
        String ipv4 = "(([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])\\.){3}([0-9]|[1-9][0-9]|1[0-9][0-9]|2[0-4][0-9]|25[0-5])";
        Pattern ipv4_pattern = Pattern.compile(ipv4);
        String ipv6 = "([0-9a-fA-F]{1,4}\\:){7}[0-9a-fA-F]{1,4}";
        Pattern ipv6_pattern = Pattern.compile(ipv6);
        if(ipv4_pattern.matcher(IP).matches()){
            return "IPv4";
        }else if(ipv6_pattern.matcher(IP).matches()){
            return "IPv6";
        }else{
            return "Neither";
        }
    }
}

时间复杂度：O*(n)，regex_match函数默认O*(n)
空间复杂度：O(1)，没有使用额外空间

BM86 大数加法

以字符串的形式读入两个数字，编写一个函数计算它们的和，以字符串形式返回。

数据范围：�.��ℎ,�.��ℎ≤100000s.lengt**h,t.lengt**h≤100000，字符串仅由’0’~‘9’构成

要求：时间复杂度 �(�)O(n)

1 2	输入："1","99" 返回值："100"

思路：模拟法

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     * 计算两个数之和
     * @param s string字符串 表示第一个整数
     * @param t string字符串 表示第二个整数
     * @return string字符串
     */
    public String solve (String s, String t) {
        // write code here
        //若是其中一个为空，返回另一个
        if(s.length() <= 0) return t;
        if(t.length() <= 0) return s;

        //让s为较长的，t为较短的
        if(s.length() < t.length()){
            String temp = s;
            s = t;
            t = temp;
        }
        int carry = 0;//进位标志
        StringBuilder res = new StringBuilder();
        //从后往前遍历较长的字符串
        for(int i = s.length()-1 ; i >= 0 ;i--){
            //转数字加上进位
            int temp = s.charAt(i) - '0' + carry;
            //转较短的字符串相应的从后往前的下标
            int j = i - s.length() + t.length();
            //如果较短字符串还有
            if( j >= 0){
                //转数组相加
                temp += t.charAt(j) - '0';
            }
            //取进位
            carry = temp/10;
            //去十位
            temp = temp %10;
            //修改结果
            res.append((char)(temp+'0'));
        }
        if(carry == 1){
            res.append('1');
        }
        res.reverse();
        return res.toString();
    }
}

时间复杂度：�(�)O(n)，其中�n为较长字符的长度，遍历字符串
空间复杂度：�(1)O(1)，常数级空间，没有使用额外辅助空间

九、双指针

BM87 合并两个有序的数组

给出一个有序的整数数组 A 和有序的整数数组 B ，请将数组 B 合并到数组 A 中，变成一个有序的升序数组

注意：
1.保证 A 数组有足够的空间存放 B 数组的元素， A 和 B 中初始的元素数目分别为 m 和 n，A的数组空间大小为 m+n

2.不要返回合并的数组，将数组 B 的数据合并到 A 里面就好了，且后台会自动将合并后的数组 A 的内容打印出来，所以也不需要自己打印

\3. A 数组在[0,m-1]的范围也是有序的

思路：三指针

import java.util.*;
public class Solution {
    public void merge(int A[], int m, int B[], int n) {
        //指向数组A的结尾
        int i = m - 1; 
        //指向数组B的结尾
        int j = n - 1; 
        //指向数组A空间的结尾处
        int k = m + n - 1; 
        //从两个数组最大的元素开始，直到某一个数组遍历完
        while(i >= 0 && j >= 0){ 
            //将较大的元素放到最后
            if(A[i] > B[j]) 
                A[k--] = A[i--];
            else
                A[k--] = B[j--];
        }
        //数组A遍历完了，数组B还有，则还需要添加到数组A前面
        if(i < 0){ 
            while(j >= 0)
                A[k--] = B[j--];
        } 
        //数组B遍历完了，数组A前面正好有，不用再添加
    }
}

BM88 判断是否为回文字符串

给定一个长度为 n 的字符串，请编写一个函数判断该字符串是否回文。如果是回文请返回true，否则返回false。

字符串回文指该字符串正序与其逆序逐字符一致。

思路：双指针

import java.util.*;


public class Solution {
    /**
     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
     *
     * @param str string字符串 待判断的字符串
     * @return bool布尔型
     */
    public boolean judge (String str) {
        // write code here
        int left = 0, right = str.length() - 1;
        while (left < right) {
            if (str.charAt(left) != str.charAt(right)){
                return false;
            }
            left++;
            right--;
        }
        return true;
    }
}

BM89 合并区间

给出一组区间，请合并所有重叠的区间。

请保证合并后的区间按区间起点升序排列。

思路：排序+贪心

import java.util.*;
public class Solution {
    public ArrayList<Interval> merge(ArrayList<Interval> intervals) {
        ArrayList<Interval> res = new ArrayList<>();
        //去除特殊情况
        if(intervals.size() == 0) 
            return res;
        //重载比较，按照区间首排序
        Collections.sort(intervals, new Comparator<Interval>(){
            public int compare(Interval o1, Interval o2){
                if(o1.start != o2.start)
                    return o1.start - o2.start;
                else
                    return o1.end - o2.end;
            }
        }); 
        //放入第一个区间
        res.add(intervals.get(0)); 
        int count = 0;
        //遍历后续区间，查看是否与末尾有重叠
        for(int i = 1; i < intervals.size(); i++){
            Interval o1 = intervals.get(i);
            Interval origin = res.get(count);
            if(o1.start > origin.end){
                res.add(o1);
                count++;
            //区间有重叠，更新结尾
            }else{ 
                res.remove(count);
                Interval s = new Interval(origin.start, o1.end);
                if(o1.end < origin.end)
                    s.end = origin.end;
                res.add(s);
            }
        }
        return res;
    }
}

BM91 反转字符串

写出一个程序，接受一个字符串，然后输出该字符串反转后的字符串。（字符串长度不超过1000）

public class Solution {
    /**
     * 反转字符串
     * @param str string字符串 
     * @return string字符串
     */
    public String solve (String str) {
        // write code here
        StringBuilder res = new StringBuilder(str);
        return res.reverse().toString();
    }
}

BM92 最长无重复子数组

给定一个长度为n的数组arr，返回arr的最长无重复元素子数组的长度，无重复指的是所有数字都不相同。

子数组是连续的，比如[1,3,5,7,9]的子数组有[1,3]，[3,5,7]等等，但是[1,3,7]不是子数组

思路：滑动窗口+哈希

import java.util.*;
public class Solution {
    public int maxLength (int[] arr) {
        //哈希表记录窗口内非重复的数字
        HashMap<Integer, Integer> mp = new HashMap<>(); 
        int res = 0;
        //设置窗口左右边界
        for(int left = 0, right = 0; right < arr.length; right++){ 
            //窗口右移进入哈希表统计出现次数
            if(mp.containsKey(arr[right]))
                mp.put(arr[right],mp.get(arr[right])+1); 
            else
                mp.put(arr[right],1);
            //出现次数大于1，则窗口内有重复
            while(mp.get(arr[right]) > 1) 
                //窗口左移，同时减去该数字的出现次数
                mp.put(arr[left],mp.get(arr[left++])-1); 
            //维护子数组长度最大值
            res = Math.max(res, right - left + 1); 
        }
        return res;
    }
}

BM93 盛水最多的容器

给定一个数组height，长度为n，每个数代表坐标轴中的一个点的高度，height[i]是在第i点的高度，请问，从中选2个高度与x轴组成的容器最多能容纳多少水

1.你不能倾斜容器

2.当n小于2时，视为不能形成容器，请返回0

3.数据保证能容纳最多的水不会超过整形范围，即不会超过231-1

思路：双指针+贪心

import java.util.*;
public class Solution {
    public int maxArea (int[] height) {
        //排除不能形成容器的情况
        if(height.length < 2) 
            return 0;
        int res = 0; 
        //双指针左右界
        int left = 0; 
        int right = height.length - 1;
        //共同遍历完所有的数组
        while(left < right){ 
            //计算区域水容量
            int capacity = Math.min(height[left], height[right]) * (right - left); 
            //维护最大值
            res = Math.max(res, capacity); 
            //优先舍弃较短的边
            if(height[left] < height[right]) 
                left++;
            else
                right--;
         }
        return res;
    }
}

BM94 接雨水问题

给定一个整形数组arr，已知其中所有的值都是非负的，将这个数组看作一个柱子高度图，计算按此排列的柱子，下雨之后能接多少雨水。(数组以外的区域高度视为0)

思路：双指针

step 1：检查数组是否为空的特殊情况
step 2：准备双指针，分别指向数组首尾元素，代表最初的两个边界
step 3：指针往中间遍历，遇到更低柱子就是底，用较短的边界减去底就是这一列的接水量，遇到更高的柱子就是新的边界，更新边界大小。

import java.util.*;
public class Solution {
    public long maxWater (int[] arr) {
        //排除空数组
        if(arr.length == 0) 
            return 0;
        long res = 0;
        //左右双指针
        int left = 0; 
        int right = arr.length - 1; 
        //中间区域的边界高度
        int maxL = 0; 
        int maxR = 0;
        //直到左右指针相遇
        while(left < right){ 
            //每次维护往中间的最大边界
            maxL = Math.max(maxL, arr[left]); 
            maxR = Math.max(maxR, arr[right]);
            //较短的边界确定该格子的水量
            if(maxR > maxL) 
                res += maxL - arr[left++]; 
            else
                res += maxR - arr[right--];
        }
        return res;
    }
}

十、贪心

BM96 主持人调度（二）

有 n 个活动即将举办，每个活动都有开始时间与活动的结束时间，第 i 个活动的开始时间是 starti ,第 i 个活动的结束时间是 endi ,举办某个活动就需要为该活动准备一个活动主持人。

一位活动主持人在同一时间只能参与一个活动。并且活动主持人需要全程参与活动，换句话说，一个主持人参与了第 i 个活动，那么该主持人在 (starti,endi) 这个时间段不能参与其他任何活动。求为了成功举办这 n 个活动，最少需要多少名主持人。

思路：贪心

import java.util.*;
public class Solution {
    public int minmumNumberOfHost (int n, int[][] startEnd) {
        int[] start = new int[n];
        int[] end = new int[n];
        //分别得到活动起始时间
        for(int i = 0; i < n; i++){
            start[i] = startEnd[i][0];
            end[i] = startEnd[i][1];
        }
        //单独排序
        Arrays.sort(start, 0, start.length);
        Arrays.sort(end, 0, end.length);
        int res = 0;
        int j = 0;
        for(int i = 0; i < n; i++){
            //新开始的节目大于上一轮结束的时间，主持人不变
            if(start[i] >= end[j]) 
                j++;  
            else
                //主持人增加
                res++;  
        }
        return res;
    }
}

在排序之后，数组中的元素位置发生了改变，但是我们通过两个指针来比较的是活动的起始时间和结束时间，这些时间并没有改变，因此排序之后不会影响判断过程。

十一、模拟

BM97 旋转数组

一个数组A中存有 n 个整数，在不允许使用另外数组的前提下，将每个整数循环向右移 M（ M >=0）个位置，即将A中的数据由（A0 A1 ……AN-1 ）变换为（AN-M …… AN-1 A0 A1 ……AN-M-1 ）（最后 M 个数循环移至最前面的 M 个位置）。如果需要考虑程序移动数据的次数尽量少，要如何设计移动的方法？

数据范围：0<�≤1000<n≤100，0≤�≤10000≤m≤1000

进阶：空间复杂度 �(1)O(1)，时间复杂度 �(�)O(n)

输入：
6,2,[1,2,3,4,5,6]
复制
返回值：
[5,6,1,2,3,4]

思路：模拟

public class Solution {
    public int[] solve (int n, int m, int[] a) {
        //取余，因为每次长度为n的旋转数组相当于没有变化
        m = m % n; 
        //第一次逆转全部数组元素
        reverse(a, 0, n - 1); 
        //第二次只逆转开头m个
        reverse(a, 0, m - 1); 
        //第三次只逆转结尾m个
        reverse(a, m, n - 1); 
        return a;
    }
    //反转函数
    public void reverse(int[] nums, int start, int end){ 
        while(start < end){
            swap(nums, start++, end--);
        }
    }
    //交换函数
    public void swap(int[] nums, int a, int b){ 
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

时间复杂度：O*(n)，三次reverse函数的复杂度都最坏为O*(n)
空间复杂度：O*(1)，没有使用额外的辅助空间

BM98 螺旋矩阵

思路：直接模拟

处理好边界条件即可

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> order = new ArrayList<Integer>();
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return order;
        }
        int rows = matrix.length, columns = matrix[0].length;
        int left = 0, right = columns - 1, top = 0, bottom = rows - 1;
        while (left <= right && top <= bottom) {
            for (int column = left; column <= right; column++) {
                order.add(matrix[top][column]);
            }
            for (int row = top + 1; row <= bottom; row++) {
                order.add(matrix[row][right]);
            }
            if (left < right && top < bottom) {
                for (int column = right - 1; column > left; column--) {
                    order.add(matrix[bottom][column]);
                }
                for (int row = bottom; row > top; row--) {
                    order.add(matrix[row][left]);
                }
            }
            left++;
            right--;
            top++;
            bottom--;
        }
        return order;
    }
}

BM99 顺时针旋转矩阵

思路：矩阵转置+矩阵反转

截屏2023-05-04 20.44.46

import java.util.*;
public class Solution {
    public int[][] rotateMatrix(int[][] mat, int n) {
        int length = mat.length;
        //矩阵转置
        for(int i = 0; i < length; ++i){
            for(int j = 0; j < i; ++j){
                //交换上三角与下三角对应的元素
                int temp = mat[i][j];
                mat[i][j] = mat[j][i];
                mat[j][i] = temp;
            }
        }
        //每行翻转
        for (int i = 0; i < length; i++) {
            for (int j = 0; j < length/2; j++){
                int temp = mat[i][j];
                mat[i][j] = mat[i][length - j - 1];
                mat[i][length - j - 1] = temp;
            }
        }
        return mat;
    }
}

时间复杂度：O(n2)，转置需要遍历矩阵，逐行翻转也是O*(n2)
空间复杂度：O*(1)，常数级变量，没有使用额外辅助空间