头像

长街听风




在线 



长街听风
3小时前

@[TOC]

剑指 Offer 44. 数字序列中某一位的数字

数字以0123456789101112131415…的格式序列化到一个字符序列中。在这个序列中,第5位(从下标0开始计数)是5,第13位是1,第19位是4,等等。

请写一个函数,求任意第n位对应的数字。

示例 1:

输入: n = 3
输出: 3

示例 2:

输入: n = 11
输出: 0

限制:

0 <= n < 2^31
注意:本题与主站 400 题相同:https://leetcode-cn.com/problems/nth-digit/

解题思路

首先我们知道的是,1 位数有 10 个,2 位数有 90 个,3 位数有 9 * 100 个,4 位数有 9 * 1000 个,以此类推,如下表
|数字范围 | 数量 |位数 | 占多少位 |
|–|–|–|–|
| 1 ~ 9 | 9 | 1 |9 |
| 10 ~ 99 |90 |2 | 180 |
| 100 ~ 999 |900 | 3 | 2700|
| …| … |… |… |

  1. 假如我们需要求的是序列的第1001位是什么,我们可以发现1001 > 9,所以第1001位肯定在1~9这九位数字之后,接下来我们又发现(1001 - 9) > 180,所以第1001位也不可能是一个两位数中的某位,而(1001 - 9 - 180)< 2700,因此可以断定序列的第1001位是一个三位数中的某一位。

  2. 现在已经知道了序列的第1001位是一个三位数中的某一位,那到底是哪一个三位数呢,很简单,计算方法为(1001 - 9 - 180)/ 3向上取整,即100 + ((1001 - 9 - 180 + 3 - 1)/ 3 ) - 1= 370。看下方注1中的上取整公式即可。

  3. 好的,现在也知道了它是属于370的某位的,那到底是哪一位,求余就好了(1001 - 9 - 180)% 3 = 2;所以答案是370中的第二位,即7

注1: n / i上取整的公式为(n + i - 1)/ i
原因:
- n能整除i时,则i - 1/i = 0;
- n不能整除i时,由于n是整数,则最少也会余1,所以(i - 1 + 大于1小于i的数) / i = 1,实现了上取整。

注2:题目中第几位是从0开始计数的,即第0位,第1位,第2...,而我们上面例子刚好也是从0开始计数,即0就是第0位,1就是第1位,也就是说,题目中表达的第1001位指的就是我们表格中从1开始计数的第1001位。

总结上述过程为:
- 确定序列的第n位应该是一个几位数中的某一位,比如是三位数
- 确定是几位数的第几个数,然后确定具体数值,比如是三位数的第271 个数,则数值是100 + 271 - 1 = 370
- 确定属于那个数的第几位,比如是370的第二位,即7

时间复杂度: $O(log_{10}n)$ 也即$O(logn)$

总的时间复杂度即三步操作的时间复杂度

int 的范围 $2∗10^9$,所以最多是 10 位数,因此第一步操作的时间最多是$log_{10}n = 10$次,是 $O(1)$ 的时间复杂度,第二步除法向上取整,也是 $O(1)$ 的,第三步求是第几位数字是 $O(log_{10}n)$ 的,因为在二进制表示中取某一位可以每次右移1 位(即除以 2),所以是 $O(log_2n)$级别的,同理在十进制中取某一位可以每次右移1 位(即除以10),所以是$O(log_{10}n)$ 级别的

Java代码

class Solution {
    public int findNthDigit(int n) {
        //1.第n位是一个几位数中的某一位
        //i表示是几位数,s表示该位数的数有多少个,如1位数9个,2位数的有90个...
        //base表示一个几位数的起点,如一位数起点是1,二位数起点是10...
        //当输入的n是int的最大值时,位数为9位,此时s *= 10执行九次的话会int越界的,故用long接收
        long i = 1,s = 9,base = 1;
        while(n > i * s){
            n -= i * s;
            i++;
            s *= 10;
            base *= 10;
        }

        //2.看它是几位数的第几个数,然后就可以知道它的数值了(n + i - 1) / i为n/i上取整公式
        long num = base + (n + i - 1) / i - 1;

        //3.确定属于那个数的第几位
        //求余数即可,r = 0 表示是最后一位(也就是 i,几位数就是几),r != 0,则r是几就是第几位
        long r = n % i == 0 ? i : n % i;

        //取出num的第r位,去掉后面的i - r位即可
        //如12345的第三位,后面还有两位45,我们将这两位去掉才好取出顺数的第三位
        for(int j = 1; j <= i - r;j++){
            num /= 10;
        }

        return (int)num % 10;//取出现在的个位就是我们的结果
    }
}

在这里插入图片描述




长街听风
5小时前

@[TOC]

剑指 Offer 43. 1~n 整数中 1 出现的次数

输入一个整数 n ,求1~nn个整数的十进制表示中1出现的次数。

例如,输入121~12这些整数中包含1 的数字有1、10、1112,1一共出现了5次。

示例 1:

输入: n = 12
输出: 5

示例 2:

输入: n = 13
输出: 6

限制:

1 <= n < 2^31

注意:本题与主站 233 题相同:https://leetcode-cn.com/problems/number-of-digit-one/

解法一:暴力求解

最直观的做法,就是累加1 ~ n中每个整数出现1的次数,我们可以通过对10求余数判断整数的个位数字是不是1,如果这个数字大于10,则除以10之后再判断个位数字是不是1

Java代码

class Solution {
    public int countDigitOne(int n) {
        int res = 0;
        for(int i = 1;i <= n;i++){
            int num = i;
            while(num != 0){
                if(num % 10 == 1) res++;
                num /= 10;
            }
        }
        return res;
    }
}

在这里插入图片描述
遗憾的是TLE了,在上述思路中,我们对每个数字都要做除法和求余运算,以求出该数字中1出现的次数。而我们知道,对于一个数字n,它有$O(logn)$位,如100有$log_{10}100 +1=3$ 位,即求一个数n有多少位的时间复杂度是$O(logn)$的,又我们需要求n个数字,即n次,那么总时间复杂度就是$O(nlogn)$,当输入的n非常大的时候,需要大量的计算,运算效率不高,导致超时了。

解法二:数位统计

我们假设 n = abcdef,其中等号右边a1~9中的某个数字,其余的可为0~9中某个数字,我们需要做的就是统计每个位上,如个位、十位、百位…上能出现1的次数的总和。

假设求c位置为1的个数:
此时c左边和右边的值分别为 lVal = ab, rVal = def, 而t = 1000,表示c的位置是千位的位置
此时则有如下两种情况:
1. lval[0, ab-1];右边可以从0 取到999,也就是此时c位置可以出现10001,我们用t表示,因为t就是1000, 此时res += lval * t;
2. lvalab
- 如果c=0,没有任何元素,及c位此时一次1都无法出现
- 如果c=1,右边可以取[0,def]也就是def+1个元素,res += def+1
- 如果c>1,右边可以从0取到999,也就是t=1000, 此时res += t;

举例 :

假如n = 123456
1. 假设当前计算千位上出现1的个数,在千位上有 _ _x_ _ _x的左边有 12,右边有 456
当左边是[0,11]时,千位上可以为1,且千位右边的三位可以是0~999,即千位上的数字我们固定为1,左边是[0-11]的任意一个数字时,右边可以是0~999,共1000个选择,所以千位是1的个数是 12 * 1000
2. 如果左边是12
- x = 0;千位上没有1
- x = 1,那么前三位固定了是121,但后三位可以是0~456,共457个数,故千位出现1的次数应加上457
- x > 1;此时我们如果把千位x固定为1,后面三位可以是0~999,共1000个数,故千位出现1的次数应加上1000,n = 123456时就是走的该情况

Java代码

class Solution {
    public int countDigitOne(int n) {
       int res = 0;
        List<Integer> numbers = new ArrayList<>();
        while (n != 0){
            numbers.add(n % 10);
            n /= 10;
        }
        for (int i = numbers.size() - 1; i >= 0 ; i--) {//枚举每一个数位、个位、十位、百位...
            int lVal = 0, rVal = 0; // i位置元素 左右两边的值
            int t = 1;
            //数位左边的数字
            for (int j = numbers.size() - 1; j > i; j--) lVal = lVal * 10 + numbers.get(j);
            //数位右边的数字
            for(int j = i - 1; j >=0; j--) {
                rVal = rVal * 10 + numbers.get(j);
                t *= 10;
            }

            // 左边
            res += lVal * t;

            // 右边
            if (numbers.get(i) == 1) {
                res += rVal + 1;
            } else if (numbers.get(i) > 1) {
                res += t;
            }
        }
        return res;
    }
}

在这里插入图片描述




长街听风
22小时前

@[TOC]

剑指 Offer 42. 连续子数组的最大和

输入一个整型数组,数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。

要求时间复杂度为$O(n)$。

示例1:

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

提示:

  • 1 <= arr.length <= 10^5
  • -100 <= arr[i] <= 100

注意:本题与主站 53 题相同:https://leetcode-cn.com/problems/maximum-subarray/

解题思路

经典的dp问题,dp[i]表示以第i个元素结尾的连续子数组的最大和,则有
- 之前以第i-1个元素结尾的连续子数组的最大和dp[i - 1]小于0时,那以第i个元素结尾的最大连续子数组的最大和dp[i]就是该元素本身nums[i]
- 否则以第i个元素结尾的最大连续子数组的最大和dp[i]就是以第i-1个元素结尾的连续子数组的最大和dp[i-1]加上第i个元素的值nums[i]

即状态转移为:dp[i] = Math.max(dp[i - 1] ,0) + nums[i];

题目要求最大值,那我们用一个变量res保存最大值即可。

Java代码

class Solution {
    public int maxSubArray(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int[] dp = new int[nums.length];

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

在这里插入图片描述




长街听风
22小时前

@[TOC]

剑指 Offer 41. 数据流中的中位数

如何得到一个数据流中的中位数?如果从数据流中读出奇数个数值,那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值,那么中位数就是所有数值排序之后中间两个数的平均值。

例如,

[2,3,4] 的中位数是 3

[2,3] 的中位数是 (2 + 3) / 2 = 2.5

设计一个支持以下两种操作的数据结构:

  • void addNum(int num) - 从数据流中添加一个整数到数据结构中。
  • double findMedian() - 返回目前所有元素的中位数。

示例 1:

输入:
[“MedianFinder”,”addNum”,”addNum”,”findMedian”,”addNum”,”findMedian”]
[[],[1],[2],[],[3],[]]
输出:[null,null,null,1.50000,null,2.00000]

示例 2:

输入:
[“MedianFinder”,”addNum”,”findMedian”,”addNum”,”findMedian”]
[[],[2],[],[3],[]]
输出:[null,null,2.00000,null,2.50000]

限制:

  • 最多会对 addNum、findMedian 进行 50000 次调用。

注意:本题与主站 295 题相同:https://leetcode-cn.com/problems/find-median-from-data-stream/

解题思路

我们可以用两个来做,也就是优先级队列,如下图:我们用一个大顶堆来存数据流中较小的数,而用小顶堆来存数据流中较大的数,那么我们就有
- 如果数据数据流中元素个数为奇数,中位数便是大顶堆的堆顶元素,下图1
- 如果数据数据流中元素个数为偶数,中位数便是(大顶堆的堆顶元素 + 小顶堆的堆顶元素)/ 2.0,下图2
在这里插入图片描述

那么当数据流中有新数据进来时,我们要如何维护这两个堆呢?

很简单,我想通过上图大家也发现了,从下往上看的话(注意:这里是为了描述方便以及容易理解才将两个堆画成图示样子的,实际两个堆是完全独立的),两个堆中的元素刚好是有序的,这也是为什么堆顶的元素就是中位数的原因,因为在中间位置嘛,所以我们首先要维护的就是有序,即让两个堆中的元素有图中所示一样的关系。

  1. 我们可以每次新增元素时都放入大顶堆中,然后比较两个堆顶的元素,如果大顶堆的堆顶元素比小顶堆的堆顶元素大,则不符合有序了,如下图1,此时只需要交换两个堆顶的元素使之有序即可,下图2
    在这里插入图片描述

  2. 由于要保证两个堆顶的元素处于中间位置,因此两个堆中的元素个数最多只能相差1,又我们每次都是将新数据插入大顶堆,所以为了维护解题思路下面奇数偶数时所说的求中位数方法一直正确,我们需要每次插入元素后都判断一下是否大顶堆中的元素个数是否不止比小顶堆中元素个数多1了,如果是,则应该调整,将大顶堆堆顶元素放入小顶堆,如下图。

在这里插入图片描述

Java代码

class MedianFinder {
    Queue<Integer> minQueue;
    Queue<Integer> maxQueue;

    /** initialize your data structure here. */
    public MedianFinder() {
        minQueue = new PriorityQueue<>();
        maxQueue = new PriorityQueue<>(new Comparator<Integer>(){
                @Override
                public int compare(Integer o1,Integer o2){
                    return o2 - o1;
                }
        });
    }

    public void addNum(int num) {
        maxQueue.add(num);
        if(!minQueue.isEmpty() && maxQueue.peek() > minQueue.peek()){
            int temp1 = maxQueue.poll();
            int temp2 = minQueue.poll();
            maxQueue.add(temp2);
            minQueue.add(temp1);
        }
        if(maxQueue.size() > minQueue.size() + 1){
            int temp = maxQueue.poll();
            minQueue.add(temp);
        }
    }

    public double findMedian() {
        int count = minQueue.size() + maxQueue.size();//数据流中当前共有多少数
        if((count & 1) != 0){//奇数
            return maxQueue.peek();
        }else{//偶数
            //注意需要返回的是double类型,故除2.0,写成2的话是整数除法,返回int型
            return (maxQueue.peek() + minQueue.peek()) / 2.0;
        }
    }
}

/**
 * Your MedianFinder object will be instantiated and called as such:
 * MedianFinder obj = new MedianFinder();
 * obj.addNum(num);
 * double param_2 = obj.findMedian();
 */

在这里插入图片描述




@[TOC]

剑指 Offer 40. 最小的k个数

输入整数数组 arr ,找出其中最小的 k个数。例如,输入4、5、1、6、2、7、3、88个数字,则最小的4个数字是1、2、3、4

示例 1:

输入: arr = [3,2,1], k = 2
输出: [1,2] 或者 [2,1]

示例 2:

输入: arr = [0,1,2,1], k = 1
输出: [0]

限制:

  • 0 <= k <= arr.length <= 10000
  • 0 <= arr[i] <= 10000

解法一:排序

对数组快速排序,然后返回前k个数即可。

时间复杂度: $O(nlogn)$

Java代码

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] res = new int[k];
        Arrays.sort(arr);
        for(int i = 0;i < k;i++){
            res[i] = arr[i];
        }
        return res;
    }
}

在这里插入图片描述

解法二:优先队列

用一个大顶堆,遍历一次数组,每次都将元素加入大顶堆,如果此时大顶堆的元素大于k个了,则把堆顶的元素去掉,即保证大顶堆中保留的一直是最小的k个数

注:这里用优先队列的效果还没有上面直接快速排序好,在这里用优先队列就是简要介绍一下他的用法,因为后面有好几道题都需要用优先队列。

Java代码

class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        int[] res = new int[k];
        //PriorityQueue是Queue的一个实现类
        //默认是小顶堆,建立大顶堆则需要构造时传自定义的Comparator参数
        Queue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>(){
            @Override
            public int compare(Integer o1,Integer o2){
                return o2 - o1;//从大到小排
            }
        });

        //大顶堆中保留最小的k个数
        for(int i = 0;i < arr.length;i++){
            queue.add(arr[i]);
            if(queue.size() > k) queue.poll();
        }

        for(int i = 0;i < k;i++){
            res[i] = queue.poll();
        }

        return res;
    }
}

在这里插入图片描述




@[TOC]

剑指 Offer 39. 数组中出现次数超过一半的数字

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

你可以假设数组是非空的,并且给定的数组总是存在多数元素。

示例 1:

输入: [1, 2, 3, 2, 2, 2, 5, 4, 2]
输出: 2

限制:

1 <= 数组长度 <= 50000

注意:本题与主站 169 题相同:https://leetcode-cn.com/problems/majority-element/

解法一:排序

排序后,次数超过一半的数字肯定在最中间。
时间复杂度:$O(nlogn)$,空间复杂度:$O(1)$

Java代码

class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
    }
}

在这里插入图片描述

解法二:哈希表

遍历一遍数组,统计各个元素出现的次数,遇到一个次数过半的数了,可以立即返回。
时间复杂度:$O(n)$,空间复杂度:$O(n)$

Java代码

class Solution {
    public int majorityElement(int[] nums) {
        Map<Integer,Integer> map = new HashMap<>();
        for(int i = 0;i < nums.length;i++){
            int val = map.getOrDefault(nums[i],0);
            if(val == 0){
                map.put(nums[i],1);
            }else{
                map.put(nums[i],val + 1);
            }
            if(map.get(nums[i]) > nums.length / 2) return nums[i];
        }
        return -1;
    }
}

在这里插入图片描述

解法三:摩尔投票法

有一个数字出现的次数超过了数组长度的一半,也即该数字出现的次数超过了其他所有数字出现的次数之和。

那么最坏的情况也不过是其他所有数字都给它投反对票,也无法将它的票抵消掉。所以最后剩下的那个数一定是那个次数超过一半的数。

时间复杂度:$O(n)$,空间复杂度:$O(1)$

Java代码

class Solution {
    public int majorityElement(int[] nums) {
        if(nums == null || nums.length == 0) return 0;
        int base = nums[0];
        int count = 1;
        for(int i = 1;i < nums.length; i++){
            if(nums[i] == base){
                count++;
            }else{
                count--;
            }
            if(count == 0){
                base = nums[i];
                count = 1;
            }
        }
        return base;
    }
}

在这里插入图片描述




@[TOC]

剑指 Offer 38. 字符串的排列

输入一个字符串,打印出该字符串中字符的所有排列。

你可以以任意顺序返回这个字符串数组,但里面不能有重复元素。

示例:

输入: s = “abc”
输出: [“abc”,”acb”,”bac”,”bca”,”cab”,”cba”]

限制:
1 <= s 的长度 <= 8

[HTML_REMOVED]

解题思路

深度优先遍历和去重技巧的结合。

根据字符串排列的特点,考虑深度优先搜索所有排列方案。即通过字符摆放,先固定第 1位字符( n 种情况)、再固定第 2 位字符(n-1种情况)、… 、最后固定第n位字符( 1 种情况)。

说的通俗一点就是把n个数字放到n个框里,有多少种放法,对于每个框,我们都有n个数字,即n个选择,但我们要判断手中的数字是否已经放入其他框了,故需要用到一个标记数组
在这里插入图片描述
上图是没有重复字符的情况,如果出现了重复字符怎么办,这就涉及到去重了,有重复字符的情况如下图。

在这里插入图片描述

我们会发现abb’ab’bbab'b’abbb'ab’ba是重复的,为什么会出现这种情况?

我们可以先回忆一下初中就学过的掷骰子,掷两个骰子,出现(4,2)(2,4)是视为两种不同的情况的,但是出现(3,3)(3,3)则只视为一种情况,因为“第一个骰子点数是3,第二个骰子点数也是3”与“第二个骰子点数是3,第一个骰子点数也是3”是完全相同的结果。

引申到排列中,为了举例方便,这里用数字11'2345

  1. 第一个框放1,然后让1'2345五个数字全排列放在其余位置
  2. 第一个框放1',然后让12345五个数字全排列放在其余位置

不难发现,情况一和二得到的排列结果将一模一样。道理和掷骰子一样,不管是把1还是1'放第一个框,它们终归都是1,然后后面的框放的也同样都是12345的全排列,那么最终产生的所有排列结果的集合肯定是一样的。

由此为了去重,我们可以定义一个规则,即对于相同数,我们人为定序,如上例子中11'2345,我们指定重复数字首次要放入某一个框位时,只能放重复数字的第一个,如这里只能放1,放1'的情况直接过滤,其他框位同理。

Java代码

class Solution {

    private String[] res;
    //最开始并不知道res最终的长度会是多少,故先把排列结果都放到list中
    //之后转到res中即可
    private List<String> list = new ArrayList<>();

    public String[] permutation(String s) {
        if(s == null || s.length() == 0) return new String[0];
        boolean[] isVisited = new boolean[s.length()];

        //由于要去重,故得先排序,因此将String转为char数组再排序
        char[] chs = s.toCharArray();
        Arrays.sort(chs);

        dfs(chs,new StringBuilder(),isVisited);

        //将结果放到数组中,因为返回结果需要的是String数组
        res = new String[list.size()];
        for(int i = 0;i < list.size();i++){
            res[i] = list.get(i);
        }
        return res;

    }

    public void dfs(char[] chs,StringBuilder sb,boolean[] isVisited){
        if(sb.length() == chs.length){
            list.add(new StringBuilder(sb.toString()).toString());
            return ;
        }
        for(int i = 0;i < chs.length;i++){
            //全排列算法去重条件模板
            //如果这个字符和前一个字符相同且前一个字符还没有用过,continue
            //即我们规定重复字符首次要放入某一个框位时,只能放重复字符的第一个
            //比如a,a',b是可以的,但是a',a,b和其重复,应该去重,故当要达到产生a',a,b那一层递归栈时
            //由于a'与前一个字符a相同,且a还没有用过,所以continue,这刚好去重,是我们想要的结果
            if(i > 0 && chs[i] == chs[i - 1] && !isVisited[i - 1]) continue;
            if(!isVisited[i]){
                sb.append(chs[i]);
                isVisited[i] = true;
                dfs(chs,sb,isVisited);
                //恢复现场
                sb.deleteCharAt(sb.length() - 1);
                isVisited[i] = false;
            }
        }
    }
}

在这里插入图片描述


这里的去重对于刚接触的同学来说确实不太好理解(我刚开始学的时候也绕了一天,绕明白后就感觉是常识了。。。),为了更好的理解,下面来两道扩展题,尤其是第二道题,实在没想明白去重时,可以跟着第二题的代码模拟一下代码执行过程,说不定突然理解了,我当时貌似就是这样绕过来的。

扩展题一:LeetCode 46. 全排列

给定一个 没有重复 数字的序列,返回其所有可能的全排列。

示例:

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

解题思路

深度优先即可,可以理解成把n个数字放到n个框里,有多少种放法,对于每个框,我们都有n个数字,即n个选择,但我们要判断手中的数字是否已经放入其他框了,故用到一个标记数组。

Java代码

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums == null) return res;
        boolean[] isVisited = new boolean[nums.length];
        dfs(res,new ArrayList<>(),nums,isVisited);
        return res;
    }


    private void dfs(List<List<Integer>> res,List<Integer> list,int[] nums,boolean[] isVisited){
        //总共就nums.length个框,当list.size() = nums.length时,说明手中数字都放完了
        if(list.size() == nums.length){
            res.add(new ArrayList<>(list));//添加的是list副本
            return;
        }
        for(int i = 0;i<nums.length;i++){
            if(!isVisited[i]){
                list.add(nums[i]);
                isVisited[i] = true;
                dfs(res,list,nums,isVisited);
                //回溯时,将list,isVisited还原为上一级栈的状态
                list.remove(list.size()-1);
                isVisited[i] = false;
            }
        }   
    }
}

在这里插入图片描述


扩展题二:LeetCode 47. 全排列 II

给定一个可包含重复数字的序列nums ,按任意顺序 返回所有不重复的全排列。

示例 1:

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

示例 2:

输入: nums = [1,2,3]
输出: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

提示:

  • 1 <= nums.length <= 8
  • -10 <= nums[i] <= 10

解题思路

与上题一样,但多个去重,去重方式看代码注释处注意这里去重得先排序(我之前自己有时也忘记了,然后在那里检查哪里出了错,0.0)。

Java代码

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        if(nums == null) return res;

        Arrays.sort(nums);//要去重,故先排序

        boolean[] isVisited = new boolean[nums.length];
        dfs(res,new ArrayList<>(),nums,isVisited);
        return res;
    }


    private void dfs(List<List<Integer>> res,List<Integer> list,int[] nums,boolean[] isVisited){
        //总共就nums.length个框,当list.size() = nums.length时,说明手中数字都排完了
        if(list.size() == nums.length){
            res.add(new ArrayList<>(list));//添加的是list副本
            return;
        }
        for(int i = 0;i<nums.length;i++){
            //如果这个数和前一个数相同且前一个数还没有用过,continue
            //即我们规定重复数字首次要放入某一个框位时,只能放重复数字的第一个
            //比如1,1',2是可以的,但是1',1,2和其重复,应该去重,故当要达到产生1',1,2那一层递归栈时
            //由于1'与前一个数1相同,且1还没有用过,所以continue,这刚好去重,是我们想要的结果
            if(i>0 && nums[i] == nums[i-1] && !isVisited[i-1]) continue;
            if(!isVisited[i]){
                list.add(nums[i]);
                isVisited[i] = true;
                dfs(res,list,nums,isVisited);
                //回溯时,将list,isVisited还原为上一级栈的状态
                list.remove(list.size()-1);
                isVisited[i] = false;
            }
        }   
    }
}

在这里插入图片描述




@[TOC]

剑指 Offer 37. 序列化二叉树

请实现两个函数,分别用来序列化和反序列化二叉树。

示例:

你可以将以下二叉树:

    1
   / \
  2   3
     / \
    4   5

序列化为 "[1,2,3,null,null,4,5]"

注意:本题与主站 297 题相同:https://leetcode-cn.com/problems/serialize-and-deserialize-binary-tree/

解题思路

做过一定数量二叉树题目的同学一定会发现,题目如果用数组形式表示一颗二叉树时,都是用层序遍历表示的,并且null也会给出,因为这样才好唯一确定一棵树。因此这里序列化我们也用层序遍历,为完整表示二叉树,考虑将叶节点下的 null也记录。在此基础上,对于列表中任意某节点 node ,其左子节点 node.left 和右子节点 node.right 在序列中的位置便是唯一确定的了。

Java代码

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Codec {

    // Encodes a tree to a single string.
    public String serialize(TreeNode root) {
        StringBuilder sb = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        if(root == null) return "null";

        //层序遍历,用“,”隔开每个元素,最后会多出一个“,”但是没什么关系。
       //因为反序列化时,用‘,’切分,自然就去掉最后的‘,’了
        queue.add(root);
        sb.append(root.val).append(",");
        while(!queue.isEmpty()){
            TreeNode cur = queue.poll();
            if(cur.left != null){
                queue.add(cur.left);
                sb.append(cur.left.val).append(",");
            }else{
                sb.append("null,");
            }
            if(cur.right != null){
                queue.add(cur.right);
                sb.append(cur.right.val).append(",");
            }else{
                sb.append("null,");
            }
        }
        //System.out.print(sb.toString());用于查看是否序列化成功
        return sb.toString();
    }

    // Decodes your encoded data to tree.
    public TreeNode deserialize(String data) {
        String[] strs = data.split(",");

        if(strs.length == 0 || strs[0].equals("null")) return null;

        TreeNode root = new TreeNode(Integer.valueOf(strs[0]));
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        int index = 1;
        while(index < strs.length){
            TreeNode node = queue.poll();
            if (node != null) {//按照层序遍历特性,当前节点不是null的话,就从数组中读取两个值作为其左右子节点
                TreeNode left = strs[index].equals("null") ? null : new TreeNode(Integer.valueOf(strs[index]));
                index++;
                queue.add(left);
                node.left = left;

                TreeNode right = strs[index].equals("null") ? null : new TreeNode(Integer.valueOf(strs[index]));
                index++;
                queue.add(right);
                node.right = right;
            }
        }
        return root;
    }
}

// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));

在这里插入图片描述




@[TOC]

剑指 Offer 36. 二叉搜索树与双向链表

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

为了让您更好地理解问题,以下面的二叉搜索树为例:
在这里插入图片描述

我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表,第一个节点的前驱是最后一个节点,最后一个节点的后继是第一个节点。

下图展示了上面的二叉搜索树转化成的链表。“head”表示指向链表中有最小元素的节点。

在这里插入图片描述

特别地,我们希望可以就地完成转换操作。当转化完成以后,树中节点的左指针需要指向前驱,树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针

注意:本题与主站 426 题相同:https://leetcode-cn.com/problems/convert-binary-search-tree-to-sorted-doubly-linked-list/

注意:此题对比原题有改动,即这里需要形成循环链表

[HTML_REMOVED]

解题思路

根据二叉搜索树的特点,我们知道对其进行中序遍历,得到的元素顺序刚好就是有序的。

我们只需要在中序遍历的时候,用一个pre指针保存当前遍历节点cur的前一个节点即可。

回忆一下我们最开始学二叉树中序遍历时候的代码:

public void inOrder(TreeNode root){
    if(root.left != null){
        inOrder(root.left);
    }

    System.out.println(root.val);

    if(root.right != null){
        inOrder(root.right);
    }
}

上面的代码就是按二叉树的中序遍历,打印出每个节点的值。

而本题中我们不是要打印出当前节点cur(代码中我写的root)的值,而是需要将他连在他的前一个节点pre的后面。我们让pre.right = cur即可,但要形成双向链表,故cur也应该有一个指针指向pre才行,因为中序遍历到了cur节点,根据中序遍历特性,说明cur节点的左子树是访问结束了的,可以放心的改他的left指针,因此我们让cur.left = pre,这样就形成了双向链表了。

最后一步,找到链表的头节点和尾结点,将他们相连形成循环链表。

Java代码

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
    //建立了一个Node指针而已,而不是新建了一个节点,故还是符合题目不能新建节点的要求的
      private Node pre = null;

    public Node treeToDoublyList(Node root) {
        if(root == null) return root;

        inOrder(root);

        //现在pre指向的是链表的尾结点,
        //我们要找到头节点,将他们相连形成循环双向链表
        Node cur = pre;
        while(cur.left != null){
            cur = cur.left;
        }
        cur.left = pre;
        pre.right = cur;

        return cur;
    }

    private void inOrder(Node root){
        if(root.left != null){
            inOrder(root.left);
        }
        //第一个节点最开始没有前一节点,为了统一操作所有节点,所以该if不能省
        if(pre != null){
            pre.right = root;
            root.left = pre;
        }
        pre = root;//更新pre为当前节点,因为当前节点就是下一个节点的前一节点

        if(root.right != null){
            inOrder(root.right);
        }
    }
}

在这里插入图片描述

要注意的一个地方

细心的朋友可能会发现,这里的pre我设置成了成员变量,而不是作为参数传递。可能你会觉得这也没什么,作为成员变量不过就是可以避免每次调用函数时都要多写这个参数而已,那你就错了。这里pre必须作为成员变量,而不能作为参数传递,因为我们知道java中都是进行值传递的,传递一个引用对象进去,在形参里面改变他的成员变量会改变实参(原对象),但是形参改变指向的话并不会影响实参(原对象)的指向。

为了表述简单,以链表为例画图如下:
在这里插入图片描述

所以如果我们将代码写成下面的形式,则TreeToDoublyList函数中pre一直是指向null的,这样我们就不方便找训练链表的首尾指针了。而写成成员变量则每次改变的都是pre成员变量,他最后就是指着树的中序遍历的最后一个节点,也就是链表的尾结点。

/*
// Definition for a Node.
class Node {
    public int val;
    public Node left;
    public Node right;

    public Node() {}

    public Node(int _val) {
        val = _val;
    }

    public Node(int _val,Node _left,Node _right) {
        val = _val;
        left = _left;
        right = _right;
    }
};
*/
class Solution {
    public Node treeToDoublyList(Node root) {
        if(root == null) return root;
        Node pre = null;
        inOrder(root,pre);

        //现在pre指向的是链表的尾结点,
        //我们要找到头节点,将他们相连形成循环双向链表
        Node cur = pre;
        while(cur.left != null){
            cur = cur.left;
        }
        cur.left = pre;
        pre.right = cur;

        return cur;
    }

    private void inOrder(Node root,Node pre){
        if(root.left != null){
            inOrder(root.left,pre);
        }

        if(pre != null){
            pre.right = root;
            root.left = pre;
        }
        pre = root;

        if(root.right != null){
            inOrder(root.right,pre);
        }
    }
}



@[TOC]

剑指 Offer 35. 复杂链表的复制

请实现 copyRandomList 函数,复制一个复杂链表。在复杂链表中,每个节点除了有一个 next 指针指向下一个节点,还有一个 random 指针指向链表中的任意节点或者 null

示例 1:

在这里插入图片描述

输入: head = [[7,null],[13,0],[11,4],[10,2],[1,0]]
输出:[[7,null],[13,0],[11,4],[10,2],[1,0]]

示例 2:
在这里插入图片描述

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

示例 3:
在这里插入图片描述

输入: head = [[3,null],[3,0],[3,null]]
输出:[[3,null],[3,0],[3,null]]

示例 4:

输入: head = []
输出:[]
解释: 给定的链表为空(空指针),因此返回 null。

提示:

  • -10000 <= Node.val <= 10000
  • Node.random 为空(null)或指向链表中的节点。
  • 节点数目不超过 1000

注意:本题与主站 138 题相同:https://leetcode-cn.com/problems/copy-list-with-random-pointer/

[HTML_REMOVED]

解题思路

我们假设原链表如下图所示,为了图简洁清晰,我们简化了示例1中的图,只让1311random不为空,此外不管是next指针还是random指针,指向空的均未画出,红色表示random指针。
在这里插入图片描述
第一步: 我们可以将每个节点都先复制一遍(此时复制时,random指针暂时不管),并接在原节点和其下一个节点的中间,如下图:
在这里插入图片描述

第二步: 复制random节点,遍历原链表的每一个节点,让p.next.random = p.random.next;如图中蓝色的13节点,当执行p.next.random = p.random.next后,就是绿色的13节点的random指针指向了绿色的7节点,也即完成了一个节点的random指针的复制,后面的节点以此类推。

在这里插入图片描述
第三步: 分开两个链表,并将原链表还原。

[HTML_REMOVED]

Java代码

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;

        //第一步:复制每个节点,并插在原节点和其下一个节点之间
        Node cur = head;
        while(cur != null){
            Node copy = new Node(cur.val);
            copy.next = cur.next;
            cur.next = copy;
            cur = cur.next.next;;
        }

        //第二步:复制random指针
        cur = head;
        while(cur != null ){
            if(cur.random != null){
                 cur.next.random = cur.random.next;
            }
            cur = cur.next.next;
        }

        //第三步:分开两个链表,并将原链表还原。
        Node dummy = new Node(-1);//复制链表的虚拟头节点
        Node help = dummy;//辅助建立复制的链表
        cur = head;
        while(cur != null){
            help.next = cur.next;
            help = help.next;
            cur.next = cur.next.next;
            cur = cur.next;
        }

        return dummy.next;
    }
}

在这里插入图片描述