#yyds干货盘点# LeetCode刷题集81-90

2021年11月24日 阅读数:4
这篇文章主要向大家介绍#yyds干货盘点# LeetCode刷题集81-90,主要内容包括基础应用、实用技巧、原理机制等方面,希望对大家有所帮助。

博主私藏的LeetCode刷题集合
有些较难的问题都有思路和注释node

81. 搜索旋转排序数组 II

假设按照升序排序的数组在预先未知的某个点上进行了旋转。数组

( 例如,数组 [0,0,1,2,2,5,6] 可能变为 [2,5,6,0,0,1,2] )。markdown

编写一个函数来判断给定的目标值是否存在于数组中。若存在返回 true,不然返回 false。ide

示例 1:函数

输入: nums = [2,5,6,0,0,1,2], target = 0
输出: true
示例 2:优化

输入: nums = [2,5,6,0,0,1,2], target = 3
输出: false
进阶:编码

这是 搜索旋转排序数组 的延伸题目,本题中的 nums 可能包含重复元素。
这会影响到程序的时间复杂度吗?会有怎样的影响,为何?3d

class Solution {
     public boolean search(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;
        while (low <= high) {
            // 去重
            while (low < high && nums[low] == nums[low + 1]) {
                low++;
            }
            while (low < high && nums[high] == nums[high - 1]) {
                high--;
            }
            // 如下代码与题目33题一致,无修改地方
            int mid = (low + high) / 2;
            if (nums[mid] == target) {
                return true;
            }
            // 把数组大体分为两组,一组为左侧未旋转有序数组,一组为右侧旋转有序数组
            // 如[3 4 5 1 2], [3,4,5]称为左侧,[1,2]称为右侧

            // 0~mid有序,向后规约条件
            // nums[mid] >= nums[0] 表示0~mid有序
            // target > nums[mid] 表示target位于左侧且大于nums[mid],向后规约
            // target < nums[0] 表示target位于右侧,向后规约
            if (nums[mid] >= nums[0] && (target > nums[mid] || target < nums[0])) {
                low = mid + 1;
            } else if (nums[mid] < nums[0] && target > nums[mid] && target < nums[0]) { // 0~mid无序(即包含翻转点),向后规约条件
                // nums[mid] < nums[0] 表示nums[mid]位于右侧
                low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return false;
    }
}

82. 删除排序链表中的重复元素 II

给定一个排序链表,删除全部含有重复数字的节点,只保留原始链表中 没有重复出现 的数字。code

示例 1:blog

输入: 1->2->3->3->4->4->5
输出: 1->2->5
示例 2:

输入: 1->1->1->2->3
输出: 2->3

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
         //baseCase
        if (head == null || head.next == null) {
            return head;
        }

        ListNode next = head.next;
        //若是是这种状况
        //      1 --> 1 --> 1 --> 2 --> 3
        //     head  next
        //1.则须要移动next直到出现与当前head.value不相等的状况(含null)
        //2.而且此时的head已经不能要了,由于已经head是重复的节点
        //--------------else-------------
        //      1 --> 2 --> 3
        //     head  next
        //3.若是没有出现1的状况,则递归返回的节点就做为head的子节点
        if (head.val == next.val) {
            //1
            while (next != null && head.val == next.val) {
                next = next.next;
            }
            //2
            head = deleteDuplicates(next);
        } else {
            //3
            head.next = deleteDuplicates(next);
        }
        return head;
    }
}

83. 删除排序链表中的重复元素

给定一个排序链表,删除全部重复的元素,使得每一个元素只出现一次。

示例 1:

输入: 1->1->2
输出: 1->2
示例 2:

输入: 1->1->2->3->3
输出: 1->2->3

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
      public ListNode deleteDuplicates(ListNode head) {
        if(head == null || head.next == null){
            return head;
        }
        head.next = deleteDuplicates(head.next);
        if(head.val == head.next.val) head = head.next;
        return head;
    }
}

84. 柱状图中最大的矩形

给定 n 个非负整数,用来表示柱状图中各个柱子的高度。每一个柱子彼此相邻,且宽度为 1 。

求在该柱状图中,可以勾勒出来的矩形的最大面积。

在这里插入图片描述

以上是柱状图的示例,其中每一个柱子的宽度为 1,给定的高度为 [2,1,5,6,2,3]。

在这里插入图片描述

图中阴影部分为所能勾勒出的最大矩形面积,其面积为 10 个单位。

示例:

输入: [2,1,5,6,2,3]
输出: 10

class Solution {
    /**
 * 利用单调栈  求解,整体思路是 以柱子i高度为矩形高度时所能造成最大面积(利用性质找出第i个柱子向左边和右边遍历时第一个比它低的柱子)
 * 单调栈定义:只存高度递增的柱子
 * 性质
 * 出栈时:
 * 那么若是单调栈为空了:说明没有比这个柱子更低的了(矩形宽度为这根柱子的序号:左边沿为0)
 * 若是单调栈不为空:说明栈里面的柱子高度都小,那么左边沿为栈顶柱子的序号
 *
 * 矩形右边沿为i 由于你出栈 就说明你比别人低了,这已是你能达到的面积极限了.出栈记录面积
* **/
public static int largestRectangleArea(int[] heights) {
    int heightn[] =new int[heights.length+1];
    for (int i = 0; i < heights.length; i++) {
        heightn[i] = heights[i];
    }
    heightn[heights.length] = 0;   //最后增长个高度为0 的柱子,以便吧单调栈里面的都弹出去。
    Deque<Integer> stack =new ArrayDeque<>(); //存储序号
    int maxS=0;
    for (int i = 0; i < heightn.length;i++) {
        while (!stack.isEmpty() && heightn[i]<heightn[stack.peek()]){  //一直出栈 直到碰见小的
            int temp=stack.pop();                      
                                    //这里是递减数列得长度
            maxS= Math.max(maxS,( ( stack.isEmpty()?i:(i-stack.peek()-1) )*heights[temp] ));
        }
        stack.push(i); //入栈
    }
    return maxS;
}
}

85. 最大矩形

给定一个仅包含 0 和 1 的二维二进制矩阵,找出只包含 1 的最大矩形,并返回其面积。

示例:

输入:
[
["1","0","1","0","0"],
["1","0","1","1","1"],
["1","1","1","1","1"],
["1","0","0","1","0"]
]
输出: 6

PS:
使用单调栈方法求解(同84)

class Solution {
      public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int[] height = new int[matrix[0].length];
        int globalmax = 0;
        for (int i = 0; i < matrix.length; i++){
            for (int j = 0; j < matrix[0].length; j++){
                if (matrix[i][j] == '0') height[j] = 0;
                else height[j]++;
            }
            globalmax = Math.max(globalmax, maxrow(height));
        }
        return globalmax;
    }
    public int maxrow(int[] height){
        Stack<Integer> st = new Stack<>();
        int localmax = 0;
        for (int i = 0; i <= height.length; i++){
            int h = (i == height.length)? 0 : height[i];
            while (!st.isEmpty() && height[st.peek()] >= h){
                int maxheight = height[st.pop()];
                int area = st.isEmpty()? i * maxheight : maxheight * (i - st.peek() -1);
                localmax = Math.max(localmax, area);
            }
            st.push(i);
        }
        return localmax;
    }
}

86. 分隔链表

给定一个链表和一个特定值 x,对链表进行分隔,使得全部小于 x 的节点都在大于或等于 x 的节点以前。

你应当保留两个分区中每一个节点的初始相对位置。

示例:

输入: head = 1->4->3->2->5->2, x = 3
输出: 1->2->2->4->3->5

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
      public ListNode partition(ListNode head, int x) {
        ListNode dummyHead1 = new ListNode(0);
        ListNode dummyHead2 = new ListNode(0);
        ListNode node1 = dummyHead1;
        ListNode node2 = dummyHead2;
        while (head != null) {
            if (head.val < x) {
                node1.next = head;
                head = head.next;
                node1 = node1.next;
                node1.next = null;
            } else {
                node2.next = head;
                head = head.next;
                node2 = node2.next;
                node2.next = null;
            }
        }
        node1.next = dummyHead2.next;
        return dummyHead1.next;
    }
}

87. 扰乱字符串

给定一个字符串 s1,咱们能够把它递归地分割成两个非空子字符串,从而将其表示为二叉树。

下图是字符串 s1 = "great" 的一种可能的表示形式。

    great
   /    \
  gr    eat
 / \    /  \
g   r  e   at
           / \
          a   t

在扰乱这个字符串的过程当中,咱们能够挑选任何一个非叶节点,而后交换它的两个子节点。

例如,若是咱们挑选非叶节点 "gr" ,交换它的两个子节点,将会产生扰乱字符串 "rgeat" 。

    rgeat
   /    \
  rg    eat
 / \    /  \
r   g  e   at
           / \
          a   t

咱们将 "rgeat” 称做 "great" 的一个扰乱字符串。

一样地,若是咱们继续交换节点 "eat" 和 "at" 的子节点,将会产生另外一个新的扰乱字符串 "rgtae" 。

    rgtae
   /    \
  rg    tae
 / \    /  \
r   g  ta  e
       / \
      t   a

咱们将 "rgtae” 称做 "great" 的一个扰乱字符串。

给出两个长度相等的字符串 s1 和 s2,判断 s2 是不是 s1 的扰乱字符串。

示例 1:

输入: s1 = "great", s2 = "rgeat"
输出: true
示例 2:

输入: s1 = "abcde", s2 = "caebd"
输出: false

PS:两种方法dfs执行效率高一点(其实dp的效率应该更高,但小编能力有限了)

class Solution {
      public boolean isScramble(String s1, String s2) {
        if (s1.length()==0 && s2.length()==0) return true;
        if (s1.length()!=s2.length()) return false;
        return dfs(s1.toCharArray(), s2.toCharArray(), 0, 0, s1.length());
    }
    private boolean dfs(char[] s1, char[] s2, int start1, int start2, int len){
        if (len==1) {
            return s1[start1]==s2[start2];
        }
        if (!equals(s1, s2, start1, start2, len)) {
            return false;
        }
        for (int i=1; i<len; i++){

            //两个字符串是否相等                    个人搜索位置日后走i,个人结束就要往前走i防止超限
            if (dfs(s1, s2, start1, start2, i) && dfs(s1, s2, start1+i, start2+i, len-i)) return true;
        //  |i到len-1|这块进行翻转
            if (dfs(s1, s2, start1, start2+len-i, i) && dfs(s1, s2, start1+i, start2, len-i)) return true;
        }
        return false;
    }
    public boolean equals(char[] s1, char[] s2, int start1, int start2, int len){
        int[] charArr = new int[26];
        for (int i=0; i<len; i++) {
            charArr[s1[start1+i] - 'a']++;
            charArr[s2[start2+i] - 'a']--;
        }
        for (int item : charArr) {
            if (item != 0) return false;
        }
        return true;
    }
}
class Solution {
    public boolean isScramble(String s1, String s2) {
         if(s1==null&&s2!=null||s2==null&&s1!=null||s1.length()!=s2.length()) return false;
    boolean[][][] dp=new boolean[s1.length()][s2.length()][s1.length()+1];
    //初始化len=1
    for (int i = 0; i < s1.length(); i++) {//第一个字符串的起点
        for (int j = 0; j < s2.length(); j++) {//第二个字符串的起点
            if(s1.charAt(i)==s2.charAt(j)) dp[i][j][1]=true;
        }
    }
    for (int len = 2; len <=s1.length(); len++) {//区间长度
        for (int i = 0; i < s1.length(); i++) {//第一个字符串的起点,终点i+len-1
            for (int j = 0; j < s2.length(); j++) {//第二个字符串的起点,终点j+len-1
                for (int k = 1; k <len; k++) {//左边区间的长度,由于要划分红两个区间,因此左边那个区间的长度是1...len-1(至少为一,至多也得给第二个区间留一个)
                    if(i+k<s1.length()&&j+k<s1.length()&&j+len-k<s1.length()&&((dp[i][j][k]&&dp[i+k][j+k][len-k])||(dp[i][j+len-k][k]&&dp[i+k][j][len-k]))){
                        dp[i][j][len]=true;
                        break;
                    }
                }
            }
        }
    }
    return dp[0][0][s1.length()];
    }
}

PS:

//dp[i][j][k][l] 表示s1的i-j和s2的k-l是否互为扰乱字符串,由于j-i=l-k,因此优化成 //dp[i][j][k] 表示s1的i...i+k和s2的j...j+k是否互为扰乱字符串

88. 合并两个有序数组

给定两个有序整数数组 nums1 和 nums2,将 nums2 合并到 nums1 中,使得 num1 成为一个有序数组。

说明:

初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你能够假设 nums1 有足够的空间(空间大小大于或等于 m + n)来保存 nums2 中的元素。
示例:

输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3

输出: [1,2,2,3,5,6]

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p = m-- + n-- - 1;
        while (m >= 0 && n >= 0) {
            nums1[p--] = nums1[m] > nums2[n] ? nums1[m--] : nums2[n--];
        }

        while (n >= 0) {
            nums1[p--] = nums2[n--];
        }
    }
}

89. 格雷编码

格雷编码是一个二进制数字系统,在该系统中,两个连续的数值仅有一个位数的差别。

给定一个表明编码总位数的非负整数 n,打印其格雷编码序列。格雷编码序列必须以 0 开头。

示例 1:

输入: 2
输出: [0,1,3,2]
解释:
00 - 0
01 - 1
11 - 3
10 - 2

对于给定的 n,其格雷编码序列并不惟一。
例如,[0,2,3,1] 也是一个有效的格雷编码序列。

00 - 0
10 - 2
11 - 3
01 - 1
示例 2:

输入: 0
输出: [0]
解释: 咱们定义格雷编码序列必须以 0 开头。
给定编码总位数为 n 的格雷编码序列,其长度为 2n。当 n = 0 时,长度为 20 = 1。
所以,当 n = 0 时,其格雷编码序列为 [0]。

PS:
关键是搞清楚格雷编码的生成过程, G(i) = i ^ (i/2);
如 n = 3:
G(0) = 000,
G(1) = 1 ^ 0 = 001 ^ 000 = 001
G(2) = 2 ^ 1 = 010 ^ 001 = 011
G(3) = 3 ^ 1 = 011 ^ 001 = 010
G(4) = 4 ^ 2 = 100 ^ 010 = 110
G(5) = 5 ^ 2 = 101 ^ 010 = 111
G(6) = 6 ^ 3 = 110 ^ 011 = 101
G(7) = 7 ^ 3 = 111 ^ 011 = 100

class Solution {
    public List<Integer> grayCode(int n) {

        List<Integer> ret = new ArrayList<>();
        for(int i = 0; i < 1<<n; ++i)
            ret.add(i ^ i>>1);
        return ret;
    }
}

90. 子集 II

给定一个可能包含重复元素的整数数组 nums,返回该数组全部可能的子集(幂集)。

说明:解集不能包含重复的子集。

示例:

输入: [1,2,2]
输出:
[
[2],
[1],
[1,2,2],
[2,2],
[1,2],
[]
]

PS:

先进行排序,保证重复元素挨在一块儿
记录每次遍历生成的新序列的长度,这里用left表示每次遍历的开始位置,right结束位置,len表示长度
根据与前面元素是否重复,来决定left的取值,也就是开始遍历的位置

其实和子集1仍是差很少的

class Solution {
      public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> retList = new ArrayList<>();
        retList.add(new ArrayList<>());
        if(nums == null || nums.length == 0) return retList;
        Arrays.sort(nums);

        List<Integer> tmp = new ArrayList<>();
        tmp.add(nums[0]);
        retList.add(tmp);
        if(nums.length == 1) return retList;

        int lastLen = 1;

        for(int i = 1; i < nums.length; i++){
            int size = retList.size();
            if(nums[i] != nums[i-1]){
                lastLen = size;
            }

            for(int j = size - lastLen; j < size; j++){
                List<Integer> inner = new ArrayList(retList.get(j));
                inner.add(nums[i]);
                retList.add(inner);
            }
        }
        return retList;
    }
}