Leaky Cauldron

基本计算器

Posted on 2022-08-08 Edited on 2022-09-11

Basic Calculator 系列在 LeetCode 上有三道：

LeetCode 224. Basic Calculator 只含加减和括号；
LeetCode 227. Basic Calculator II 只含加减乘除不含括号；
LeetCode 772. Basic Calculator III 加减乘除和括号都有。

这类题目重点在于解决运算的优先级问题，需要将数字和运算符按优先级依次处理以得到正确结果。

LeetCode 224

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

注意:不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：

输入：s = “1 + 1”
输出：2

示例 2：

输入：s = “ 2-1 + 2 “
输出：3

示例 3：

输入：s = “(1+(4+5+2)-3)+(6+8)”
输出：23

题解

保存每个数字前的符号并相加。

class Solution {
    public int calculate(String s) {
        int n = s.length();
        int[] signs = new int[n];
        signs[0] = 1;
        int sign = 1, result = 0, sIdx = 0;

        for (int i = 0; i < n; i++) {
            char cur = s.charAt(i);

            if (cur == '+') sign = signs[sIdx];
            else if (cur == '-') sign = -signs[sIdx];
            else if (cur == '(') signs[++sIdx] = sign;
            else if (cur == ')') sIdx--;
            else if (isDigit(cur)) {
                long num = cur - '0';
                while (i + 1 < n && isDigit(s.charAt(i + 1)))
                    num = num * 10 + s.charAt(++i) - '0';
                result += sign * num;
            }
        }

        return result;
    }

    private boolean isDigit(char num) {
        return '0' <= num && num <= '9';
    }
}

LeetCode 227

给你一个字符串表达式 s ，请你实现一个基本计算器来计算并返回它的值。

整数除法仅保留整数部分。

你可以假设给定的表达式总是有效的。所有中间结果将在 [-231, 231 - 1] 的范围内。

注意：不允许使用任何将字符串作为数学表达式计算的内置函数，比如 eval() 。

示例 1：

输入：s = “3+2*2”
输出：7

示例 2：

输入：s = “ 3/2 “
输出：1

示例 3：

输入：s = “ 3+5 / 2 “
输出：5

题解

先遍历计算乘除，再计算加减。

public class Solution {
    public int calculate(String s) {
        char sign = '+';
        int len = s.length(), idx = 0;
        int[] nums = new int[(len + 1) / 2];

        for (int i = 0; i < len; i++) {
            char cur = s.charAt(i);
            if (cur == ' ') continue;

            int num = 0;
            if (isDigit(cur)) {
                num = cur - '0';
                while (i + 1 < len && isDigit(s.charAt(i + 1)))
                    num = num * 10 - '0' + s.charAt(++i);
            }

            switch (sign) {
                case '+': nums[idx++] = num; break;
                case '-': nums[idx++] = -num; break;
                case '*': nums[idx - 1] *= num; break;
                case '/': nums[idx - 1] /= num; break;
            }

            sign = cur;
        }

        int result = 0;
        for (int i = 0; i < idx; i++) result += nums[i];

        return result;
    }

    private boolean isDigit(char ch) {
        return '0' <= ch && ch <= '9';
    }
}

LeetCode 772

实现一个基本的计算器来计算简单的表达式字符串。

表达式字符串只包含非负整数，算符 +、-、*、/ ，左括号 ( 和右括号 ) 。整数除法需要向下截断。

你可以假定给定的表达式总是有效的。所有的中间结果的范围为 [-231, 231 - 1] 。

示例 1：

输入：s = “1 + 1”
输出：2

示例 2：

输入：s = “6 - 4 / 2”
输出：4

示例 3：

输入：s = “2 * ( 5 + 5 * 2 ) / 3 + ( 6 / 2 + 8 )”
输出：21

示例 4：

输入：s = “( 2 + 6 * 3 + 5 - 3 * 14 / 7 + 2 ) * 5 ) + 3”
输出：-12

示例 5：

输入：s = “0”
输出：0

题解

去除括号带来的影响，相比于 227，差别仅在于将括号内的字符串递归地计算作为整体进行处理。

public class Solution {
    public int calculate(String s) {
        char sign = '+';
        int len = s.length(), idx = 0;
        int[] nums = new int[(len + 1) / 2];

        for (int i = 0; i < len; i++) {
            char cur = s.charAt(i);
            if (cur == ' ') continue;

            int num = 0;
            if (isDigit(cur)) {
                num = cur - '0';
                while (i + 1 < len && isDigit(s.charAt(i + 1)))
                    num = num * 10 - '0' + s.charAt(++i);
            } else if (cur == '(') {
                int j = findClosing(s.substring(i));
                num = calculate(s.substring(i + 1, i + j));
                i += j;
            }

            switch (sign) {
                case '+': nums[idx++] = num; break;
                case '-': nums[idx++] = -num; break;
                case '*': nums[idx - 1] *= num; break;
                case '/': nums[idx - 1] /= num; break;
            }

            sign = cur;
        }

        int result = 0;
        for (int i = 0; i < idx; i++) result += nums[i];

        return result;
    }

    private boolean isDigit(char ch) {
        return '0' <= ch && ch <= '9';
    }

    private int findClosing(String s) {
        int len = 0, depth = 0;

        for (char c : s.toCharArray()) {
            if (c == '(') depth++;
            else if (c == ')') {
                depth--;
                if (depth == 0) break;
            }
            len++;
        }

        return len;
    }
}

删除字符串中的所有相邻重复项 II

Posted on 2022-01-29 Edited on 2022-07-20

题目(LeetCode #1209)

给你一个字符串 s，「k 倍重复项删除操作」将会从 s 中选择 k 个相邻且相等的字母，并删除它们，使被删去的字符串的左侧和右侧连在一起。

你需要对 s 重复进行无限次这样的删除操作，直到无法继续为止。

在执行完所有删除操作后，返回最终得到的字符串。

本题答案保证唯一。

示例 1：

输入: s = “abcd”, k = 2
输出: “abcd”
解释: 没有要删除的内容。

示例 2：

输入: s = “deeedbbcccbdaa”, k = 3
输出: “aa”
解释：
先删除 “eee” 和 “ccc”，得到 “ddbbbdaa”
再删除 “bbb”，得到 “dddaa”
最后删除 “ddd”，得到 “aa”

示例 3：

输入: s = “pbbcggttciiippooaais”, k = 2
输出: “ps”

提示：

1 <= s.length <= 10^5
2 <= k <= 10^4
s 中只含有小写英文字母。

题解

可使用栈保存当前遍历的字符的连续出现次数。每次循环判断当前字符与前一个字符是否相同，若相同则栈顶元素自增。若自增至 k 则从字符串中删除这 k 个字符，同时修改遍历时的索引的值，直到遍历至字符串尾部即可。时间复杂度和空间复杂度均为 O(n)。

class Solution {
    public String removeDuplicates(String s, int k) {
        StringBuilder sb = new StringBuilder(s);
        int[] countStack = new int[sb.length()];
        int idx = 0;

        for (int i = 0; i < sb.length(); i++) {
            if (i == 0 || sb.charAt(i) != sb.charAt(i - 1)) {
                countStack[idx++] = 1;
            } else {
                int increment = countStack[--idx] + 1;
                if (increment == k) {
                    sb.delete(i - k + 1, i + 1);
                    i = i - k;
                } else {
                    countStack[idx++] = increment;
                }
            }
        }
        return sb.toString();
    }
}

点击计数器

Posted on 2022-01-19 Edited on 2022-07-20

题目(LeetCode #362)

Design a hit counter which counts the number of hits received in the past 5 minutes.

Each function accepts a timestamp parameter (in seconds granularity) and you may assume that calls are being made to the system in chronological order (ie, the timestamp is monotonically increasing). You may assume that the earliest timestamp starts at 1.

It is possible that several hits arrive roughly at the same time.

Example:

HitCounter counter = new HitCounter();

// hit at timestamp 1.
counter.hit(1);

// hit at timestamp 2.
counter.hit(2);

// hit at timestamp 3.
counter.hit(3);

// get hits at timestamp 4, should return 3.
counter.getHits(4);

// hit at timestamp 300.
counter.hit(300);

// get hits at timestamp 300, should return 4.
counter.getHits(300);

// get hits at timestamp 301, should return 3.
counter.getHits(301);

Follow up:
What if the number of hits per second could be very large? Does your design scale?

题解

解法一

使用队列保存所有的 timestamp，获取点击数时将所有与当前时间戳相距 5 分钟以上的元素弹出，返回剩余队列长度即可。

class HitCounter {
    private Queue<Integer> queue;

    public HitCounter() {
        queue = new ArrayDeque<>();
    }

    public void hit(int timestamp) {
        queue.add(timestamp);
    }

    public int getHits(int timestamp) {
        while (!queue.isEmpty() && timestamp - queue.peek() >= 300)
            queue.poll();

        return queue.size();
    }
}

解法二

对于 follow up 中的情况，可使用两个数组分别保存时间戳和点击次数，每次调用 hit 时将时间戳对 300 取余得到对应的索引，若该索引对应的时间戳与当前输入不同，则说明已超过 5 分钟。

class HitCounter {
    private int[] times, hits;

    public HitCounter() {
        times = new int[300];
        hits = new int[300];
    }

    public void hit(int timestamp) {
        int idx = timestamp % 300;
        if (times[idx] != timestamp) {
            times[idx] = timestamp;
            hits[idx] = 1;
        } else {
            hits[idx]++;
        }
    }

    public int getHits(int timestamp) {
        int cnt = 0;

        for (int i = 0; i < 300; i++) {
            if (timestamp - times[i] < 300) {
                cnt += hits[i];
            }
        }

        return cnt;
    }
}

第一个唯一数字

Posted on 2022-01-16 Edited on 2022-07-20

题目(LeetCode #1429)

You have a queue of integers, you need to retrieve the first unique integer in the queue.

Implement the FirstUnique class:

FirstUnique(int[] nums) Initializes the object with the numbers in the queue.
int showFirstUnique() returns the value of the first unique integer of the queue, and returns -1 if there is no such integer.
void add(int value) insert value to the queue.

Example 1:

Input: 
["FirstUnique","showFirstUnique","add","showFirstUnique","add","showFirstUnique","add","showFirstUnique"]
[[[2,3,5]],[],[5],[],[2],[],[3],[]]
Output: [null,2,null,2,null,3,null,-1] 
Explanation:
FirstUnique firstUnique = new FirstUnique([2,3,5]);
firstUnique.showFirstUnique(); // return 2 
firstUnique.add(5);            // the queue is now [2,3,5,5] 
firstUnique.showFirstUnique(); // return 2 
firstUnique.add(2);            // the queue is now [2,3,5,5,2] 
firstUnique.showFirstUnique(); // return 3 
firstUnique.add(3);            // the queue is now [2,3,5,5,2,3] 
firstUnique.showFirstUnique(); // return -1

Example 2:

Input: 
["FirstUnique","showFirstUnique","add","add","add","add","add","showFirstUnique"]
[[[7,7,7,7,7,7]],[],[7],[3],[3],[7],[17],[]]
Output: 
[null,-1,null,null,null,null,null,17]
Explanation: 
FirstUnique firstUnique = new FirstUnique([7,7,7,7,7,7]); 
firstUnique.showFirstUnique(); // return -1 
firstUnique.add(7);            // the queue is now [7,7,7,7,7,7,7] 
firstUnique.add(3);            // the queue is now [7,7,7,7,7,7,7,3] 
firstUnique.add(3);            // the queue is now [7,7,7,7,7,7,7,3,3] 
firstUnique.add(7);            // the queue is now [7,7,7,7,7,7,7,3,3,7] 
firstUnique.add(17);           // the queue is now [7,7,7,7,7,7,7,3,3,7,17] 
firstUnique.showFirstUnique(); // return 17

Example 3:

Input: 
["FirstUnique","showFirstUnique","add","showFirstUnique"]
[[[809]],[],[809],[]]
Output: 
[null,809,null,-1] 
Explanation:
FirstUnique firstUnique = new FirstUnique([809]); 
firstUnique.showFirstUnique(); // return 809 
firstUnique.add(809);          // the queue is now [809,809] 
firstUnique.showFirstUnique(); // return -1

题解

方法一：可以使用队列保存输入的所有数字，并创建一个 Map 来保存各数字的出现次数，执行 add 时直接将新元素添加至队尾；执行 firstUnique 时从队首逐个判断是否唯一，若不唯一则弹出该元素，直到找到第一个唯一的元素为止。这种方法时间和空间复杂度都是 O(n)，可能需要弹出很多元素才能找到结果。

方法二：创建一个队列保存输入的数字，并使用一个 Set 保存所有数字，添加元素时先判断该数字是否已经出现过，若出现过则从队列中移除该元素。时间和空间复杂度仍都为 O(n)，firstUnique 操作的时间复杂度降为 O(1)，但 add 操作最坏情况下仍为 O(n)。该解法中的队列可改用 LinkedHashSet，进一步降低 add 时移除重复元素的复杂度。

class FirstUnique {
    Set<Integer> unique = new LinkedHashSet<>();
    Set<Integer> all = new HashSet<>();

    public FirstUnique(int[] nums) {
        for (int num : nums) add(num);
    }

    public void add(int num) {
        if (all.add(num)) unique.add(num);
        else unique.remove(num);
    }

    public int showFirstUnique() {
        return unique.isEmpty() ? -1 : unique.iterator().next();
    }
}

锯齿迭代器

Posted on 2022-01-16 Edited on 2022-07-20

题目(LeetCode #281)

Given two 1d vectors, implement an iterator to return their elements alternately.

Example:

Input:
v1 = [1,2]
v2 = [3,4,5,6]

Output: [1,3,2,4,5,6]

Explanation: By calling next repeatedly until hasNext returns false,
             the order of elements returned by next should be: [1,3,2,4,5,6].

Follow up: What if you are given k 1d vectors? How well can your code be extended to such cases?

Clarification for the follow up question:

The “Zigzag” order is not clearly defined and is ambiguous for k > 2 cases. If “Zigzag” does not look right to you, replace “Zigzag” with “Cyclic”. For example:

Input:
[1,2,3]
[4,5,6,7]
[8,9]

Output: [1,4,8,2,5,9,3,6,7].

题解

k 为 2 的基础情况时，可使用两个索引 i 和 j 分别标记移动位置，hasNext() 判断两索引是否到达列表尾即可。

class ZigzagIterator {
    private List<Integer> v1;
    private List<Integer> v2;
    int i = 0, j = 0;

    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        this.v1 = v1;
        this.v2 = v2;
    }

    public int next() {
        return i > j ? v2.get(j++) : v1.get(i++);
    }

    public boolean hasNext() {
        if (i >= v1.size()) i = Integer.MAX_VALUE;
        if (j >= v2.size()) j = Integer.MAX_VALUE;
        return i < v1.size() || j < v2.size();
    }
}

Follow up 中 k > 2 时，可使用队列保存各个列表的迭代器。调用 next() 时，依次取出队首迭代器的值，并判断该迭代器是否还有后续元素，若仍有后续元素则将该迭代器重新加入队列中，重复该操作直到队列为空为止。

class ZigzagIterator {

    private Queue<Iterator<Integer>> queue;

    public ZigzagIterator(List<Integer> v1, List<Integer> v2) {
        queue = new LinkedList<>();
        if (!v1.isEmpty()) queue.add(v1.iterator());
        if (!v2.isEmpty()) queue.add(v2.iterator());
    }

    public int next() {
        Iterator<Integer> cur = queue.poll();
        int result = cur.next();
        if (cur.hasNext()) queue.add(cur);

        return result;
    }

    public boolean hasNext() {
        return !queue.isEmpty();
    }
}

数据流中的移动平均值

Posted on 2022-01-15 Edited on 2022-09-08

题目(LeetCode #346)

Given a stream of integers and a window size, calculate the moving average of all integers in the sliding window.

Example:

MovingAverage m = new MovingAverage(3);
m.next(1) = 1
m.next(10) = (1 + 10) / 2
m.next(3) = (1 + 10 + 3) / 3
m.next(5) = (10 + 3 + 5) / 3

题解

可使用固定大小的队列实现滑动窗口

import java.util.Queue;
import java.util.ArrayDeque;

class MovingAverage {
    private int maxSize;
    private double previousSum;
    private Queue<Integer> data;

    public MovingAverage(int maxSize) {
        this.maxSize = maxSize;
        data = new ArrayDeque<>();
    }

    public double next(int val) {
        if (data.size() == maxSize)
            previousSum -= data.poll();

        data.add(val);
        previousSum += val;

        return previousSum / data.size();
    }
}

class Solution {
    public static void main(String[] args) {
        MovingAverage m = new MovingAverage(3);
        System.out.println(m.next(1));
        System.out.println(m.next(10));
        System.out.println(m.next(3));
        System.out.println(m.next(5));
    }
}

华硕 USB-AC57 / RTL8812BU Ubuntu 20 驱动安装

Posted on 2021-07-26 Edited on 2022-07-20

0. 系统环境

1. 驱动安装

安装依赖

1	sudo apt update

1	sudo apt install -y dkms git build-essential

下载驱动

1	git clone https://github.com/morrownr/88x2bu.git

编译安装

cd 88x2bu

1	sudo ./install-driver.sh

1	sudo reboot

重启后通过 iwconfig 命令查看驱动状态，图中 wlx3c7c3faee542 即为 USB-AC57

启用网卡

1	sudo ifconfig wlx3c7c3faee542 up

2. 连接 WiFi

安装 wpasupplicant

1	sudo apt install wpasupplicant

创建 wpasupplicant 配置文件

1	sudo vi /etc/wpa_supplicant/wpa_supplicant.conf

在其中写入：

network={
    ssid="WiFi名称"
    psk="密码"
}

连接

1	sudo wpa_supplicant -i wlx3c7c3faee542 -c /etc/wpa_supplicant/wpa_supplicant.conf -B

使用 DHCP 获取 ip

1	sudo dhclient wlx3c7c3faee542

此时即可通过 USB-AC57 连接网络

3. 开机自动连接

编写脚本 conn_wifi.sh

#!/bin/bash
WIFINAME='wlx3c7c3faee542'

ifconfig $WIFINAME up &&
wpa_supplicant -i $WIFINAME -c /etc/wpa_supplicant/wpa_supplicant.conf -B &&
dhclient $WIFINAME

开机时执行该脚本，编辑 /etc/rc.local

#!/bin/sh

/bin/sh /home/chunyu/scripts/conn_wifi.sh

exit 0

若主机有多个网络连接，需要通过设置默认网关来通过 WiFi 连接网络，脚本改为：

#!/bin/bash
WIFINAME='wlx3c7c3faee542'

ifconfig $WIFINAME up &&
wpa_supplicant -i $WIFINAME -c /etc/wpa_supplicant/wpa_supplicant.conf -B &&
dhclient $WIFINAME &&
route del default gw 192.168.3.1 &&
route add default gw 192.168.0.1

其中后两行删除了默认的有线网关，添加了 WiFi 网关，地址需根据本机网络配置

1	sudo route -n

如网卡 wlx3c7c3faee542 的 Destination 为 192.168.0.0，则网关地址即为 192.168.0.1

康托展开与逆康托展开

Posted on 2020-09-10 Edited on 2022-07-20

康托展开

定义

康托展开是一个全排列到一个自然数的双射，常用于构建哈希表时的空间压缩。康托展开的实质是计算当前排列在所有由小到大全排列中的顺序，因此是可逆的。

公式

其中 a_i 为整数，且 0 ≤ a_i ≤ i, 1 ≤ i ≤ n .

解释

以 [4, 2, 3, 1] 为例，以 4 为第一位的排列之前的排列的第一位可能为 1、2、3，共 3 种情况，而第 2、3、4 位上的顺序又有 3! 种可能。此时 a_n = 3，n - 1 = 3, 故第一位为 4 的排列之前共有 18 种排列。以此类推，可计算在第一位为 4，第二位为 2 的情况之前的排列数量，此时比 2 小的只有一个数 1，故 a_n = 1, n - 2 = 2，故第二项为 2。后续过程类似，由于计算的是当前排列的次序，故还需将结果加 1。

class CantorExpansion {
    final int[] facts = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};

    public int getFactorial(int n) {
        if (n < 10) return facts[n];
        return n * getFactorial(n - 1);
    }

    public int cantor(int[] nums) {
        int result = 0;
        int arrLen = nums.length;
        for (int i = 0; i < arrLen; i++) {
            int cnt = 0;
            for (int j = i + 1; j < arrLen; j++) {
                if (nums[i] > nums[j]) cnt++;
            }
            result += cnt * getFactorial(arrLen - i - 1);
        }

        return result + 1;
    }

    public static void main(String[] args) {
        int nums[] = {4, 2, 3, 1};
        System.out.println(new CantorExpansion().cantor(nums));	// 22
    }
}

逆康托展开

因为排列的次序与排列是一一对应的，故可由排列数直接推得排列。

例如，对数组 [1, 2, 3, 4] 的全排列序列来说，求第 23 个排列：

首先减去 1 求得该序列前共有 22 种排列
再用 22 除 (4 - 1)!，商 3 余 4，故这个排列比第一位小的共有 3 个数，故第一位为 4
用 4 除 (3 - 1)!，商 2 余 0，故剩余的数中比第二位小的数共有 2 个，所以第二位为 3
用 0 除 (2 - 1)!，商 0 余 0，故剩余的数中比第三位小的数有 0 个，所以第三位为 1
用 0 除 (1 - 1)!，商 0 余 0，故比第四位小的数有 0 个，所以第四位为仅剩的 2

所以第 23 个排列为 4312。

class CantorExpansion {
    final int[] facts = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};

    public int getFactorial(int n) {
        if (n < 10) return facts[n];
        return n * getFactorial(n - 1);
    }

    public String inverseCantor(int[] nums, int n) {
        int arrLen = nums.length;
        char[] result = new char[arrLen];
        boolean[] isVisited = new boolean[arrLen];
        n--;
        for (int i = 0; i < arrLen; i++) {
            int tmpFact = getFactorial(arrLen - 1 - i);
            int cnt = n / tmpFact;
            n %= tmpFact;
            for (int j = 0; j < arrLen; j++) {
                if (isVisited[j]) continue;
                if (cnt-- == 0) {
                    isVisited[j] = true;
                    result[i] = (char) (nums[j] + '0');
                    break;
                }
            }
        }

        return String.valueOf(result);
    }

    public static void main(String[] args) {
        int nums[] = {1, 2, 3, 4};
        System.out.println(new CantorExpansion().inverseCantor(nums, 23)); // 4312
    }
}

例题(LeetCode #60)

第 k 个排列

给出集合 [1,2,3,…,n]，其所有元素共有 n! 种排列。

按大小顺序列出所有排列情况，并一一标记，当 n = 3 时, 所有排列如下：

“123”
“132”
“213”
“231”
“312”
“321”

给定 n 和 k，返回第 k 个排列。

说明：

给定 n 的范围是 [1, 9]。
给定 k 的范围是[1, n!]。

示例 1:

输入: n = 3, k = 3
输出: “213”

示例 2:

输入: n = 4, k = 9
输出: “2314”

题解

采用逆康托展开直接计算

Java

class Solution {
    final int[] facts = {1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880};

    public int getFactorial(int n) {
        if (n < 10) return facts[n];
        return n * getFactorial(n - 1);
    }

    public String getPermutation(int n, int k) {
        StringBuilder result = new StringBuilder();
        boolean[] isVisited = new boolean[n];
        k--;
        for (int i = 0; i < n; i++) {
            int tmpFact = getFactorial(n - 1 - i);
            int cnt = k / tmpFact;
            k %= tmpFact;
            for (int j = 0; j < n; j++) {
                if (isVisited[j]) continue;
                if (cnt-- == 0) {
                    isVisited[j] = true;
                    result.append(j + 1);
                    break;
                }
            }
        }

        return String.valueOf(result);
    }
}

Python

class Solution:
    def __init__(self):
        self.facts = [1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880]

    def get_fact(self, n: int) -> int:
        if n < 10: return self.facts[n]
        return n * self.get_fact(n - 1)

    def getPermutation(self, n: int, k: int) -> str:
        result = []
        is_visited = [False] * n
        k -= 1
        for i in range(n):
            tmp_fact = self.get_fact(n - 1 - i)
            cnt = k // tmp_fact
            k %= tmp_fact
            for j in range(n):
                if is_visited[j]: continue
                if cnt == 0:
                    is_visited[j] = True
                    result.append(str(j + 1))
                    break
                cnt -= 1

        return ''.join(result)

Go

import (
    "strconv"
    "strings"
)

var facts = []int{1, 1, 2, 6, 24, 120, 720, 5040, 40320, 362880}

func getFact(n int) int {
    if n < 10 {
        return facts[n]
    }
    return n * getFact(n-1)
}

func getPermutation(n int, k int) string {
    var result []string
    isVisited := make([]bool, n)
    k--
    for i := 0; i < n; i++ {
        tmpFact := getFact(n - 1 - i)
        cnt := k / tmpFact
        k %= tmpFact
        for j := 0; j < n; j++ {
            if isVisited[j] {
                continue
            }
            if cnt == 0 {
                isVisited[j] = true
                result = append(result, strconv.Itoa(j+1))
                break
            }
            cnt--
        }
    }

    return strings.Join(result, "")
}

Go 自定义类型排序

Posted on 2020-09-07 Edited on 2022-07-20

题目(LeetCode #56)

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

示例 1:

输入: intervals = [[1, 3], [2, 6], [8, 10], [15, 18]]
输出: [[1, 6], [8, 10], [15, 18]]
解释: 区间 [1, 3] 和 [2, 6] 重叠, 将它们合并为 [1, 6].

示例 2:

输入: intervals = [[1, 4], [4, 5]]
输出: [[1, 5]]
解释: 区间 [1, 4] 和 [4, 5] 可被视为重叠区间。

提示： intervals[i][0] <= intervals[i][1]

题解

先按照每个区间的左端点进行排序，保证可以合并的区间是连续的。
遍历区间数组，判断结果集中最后一个区间的右端点与当前数组的左端点的关系：
- 若 curInterval[0] < mergedList[-1][1] ，则区间无重合，直接将当前区间放入结果集即可
- 若 curInterval[0] >= mergedList[-1][1] ，则区间重合，需更新结果集中最后一个区间的右端点为 max(curInterval[1], mergerdList[-1][1])

快速排序

func merge(intervals [][]int) [][]int {
	if intervals == nil || len(intervals) <= 1 {
		return intervals
	}
	quickSort(intervals, 0, len(intervals)-1)

	var result [][]int
	result = append(result, intervals[0])
	for _, interval := range intervals[1:] {
		lastInterval := result[len(result)-1]
		if lastInterval[1] < interval[0] {
			result = append(result, interval)
		} else {
			lastInterval[1] = max(lastInterval[1], interval[1])
		}
	}

	return result
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

func quickSort(nums [][]int, L, R int) {
	if L < R {
		pIndex := partition(nums, L, R)
		quickSort(nums, L, pIndex-1)
		quickSort(nums, pIndex+1, R)
	}
}

func partition(nums [][]int, L, R int) int {
	P := nums[L]
	for L != R {
		for L < R && nums[R][0] >= P[0] {
			R--
		}
		nums[L] = nums[R]
		for L < R && nums[L][0] <= P[0] {
			L++
		}
		nums[R] = nums[L]
	}
	nums[L] = P

	return L
}

Go 内置排序

调用 sort 包对自定义类型进行排序时，需实现其中的 Less() 、Len() 、Swap() 三个方法。

import "sort"

func merge(intervals [][]int) [][]int {
	if intervals == nil || len(intervals) <= 1 {
		return intervals
	}
	sort.Sort(intss(intervals))

	var result [][]int
	result = append(result, intervals[0])
	for _, interval := range intervals[1:] {
		lastInterval := result[len(result)-1]
		if lastInterval[1] < interval[0] {
			result = append(result, interval)
		} else {
			lastInterval[1] = max(lastInterval[1], interval[1])
		}
	}

	return result
}

type intss [][]int

func (s intss) Swap(i, j int) {
	s[i], s[j] = s[j], s[i]
}

func (s intss) Less(i, j int) bool {
	return s[i][0] < s[j][0]
}

func (s intss) Len() int {
	return len(s)
}

func max(a, b int) int {
	if a > b {
		return a
	}
	return b
}

全排列

Posted on 2020-09-01 Edited on 2022-10-11

题目(LeetCode #46)

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

示例:

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

题解

使用 visited 数组标记已访问过的元素。

Java

import java.util.*;

class Solution {
    public List<List<Integer>> permute(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        dfs(results, nums, new ArrayList<>(), new int[nums.length]);

        return results;
    }

    public void dfs(List<List<Integer>> results, int[] nums, ArrayList<Integer> tmp, int[] visited) {
        if (tmp.size() == nums.length) {
            results.add(new ArrayList<>(tmp));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (visited[i] == 1) continue;
            tmp.add(nums[i]);
            visited[i] = 1;
            dfs(results, nums, tmp, visited);
            visited[i] = 0;
            tmp.remove(tmp.size() - 1);
        }
    }
}

Python

使用切片和 list 的加法，在向下递归时略过当前元素即实现了对访问过元素的标记。

class Solution:
    def permute(self, nums: list) -> list:
        results = []
        def dfs(nums, tmp):
            if not nums:
                results.append(tmp)
                return
            for i in range(len(nums)):
                dfs(nums[:i] + nums[i + 1:], tmp + [nums[i]])
        dfs(nums, [])
        return results

    def permute1(self, nums: list) -> list:
        return list(itertools.permutations(nums))

调用 Python 的内置函数实现如下

import itertools

class Solution:
    def permute(self, nums: list) -> list:
        return list(itertools.permutations(nums))

Go

Go 在实现时需注意 append(nums, 2) 不会修改 nums 数组存储的内容，但 append(nums[:i], 2) 会使 nums 数组发生改变。

package main

import "fmt"

func permute(nums []int) [][]int {
    var results [][]int
    dfs(&results, nums, []int{})

    return results
}

func dfs(results *[][]int, nums, tmp []int) {
    if len(nums) == 0 {
        *results = append(*results, append([]int{}, tmp...)) // 深拷贝
        return
    }

    for i := 0; i < len(nums); i++ {
        dfs(results, combinedArr(nums[:i], nums[i+1:]), combinedArr(tmp, []int{nums[i]}))
    }
}

func combinedArr(arr1, arr2 []int) []int {
    var result []int
    result = append(result, arr1...)
    result = append(result, arr2...)

    return result
}

进阶(LeetCode #47)

给定一个可包含重复数字的序列，返回所有不重复的全排列。

示例:

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

题解

参考题解

#46 中的算法流程如下，因 #47 包含重复元素，需对递归树进行剪枝：

观察可知，若两个分支的前几位排列相同，则这两个分支上的递归子树也相等，如 [1] 与 [1'] 、[2, 1] 与 [2, 1'] （即图上红框中内容）重复，可进行剪枝，在同一层判断 nums[i] == nums[i - 1] 是否成立即可。若只设定这一个剪枝条件，将使以下蓝框中的分支被误剪，导致返回空的解集：

为避免这种现象的产生，可借助 visited 数组对是否遍历过某分支进行标记，仅在前一个分支遍历完成（即 visited[i - 1] == 0 成立时）进行剪枝。故剪枝的判断条件为 i > 0 && nums[i] == nums[i - 1] && visited[i - 1] == 0 。

下图为递归时递归栈的调用顺序：

注：实际上 visited[i - 1] 等于 0、不等于 0、等于 1、不等于 1 四种情况下产生的结果相同，但若直接去掉则将返回空的解集🙃。visited[i - 1] 起到的是标记的作用，即只选择 visited[i - 1] 等于 0 或只选择等于 1 的分支，区别仅在于最终结果集中元素的顺序不同，详见这篇题解的补充说明部分。

Java

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums);
        dfs(res, nums, new ArrayList<>(), new int[nums.length]);
        return res;
    }

    public void dfs(List<List<Integer>> res, int[] nums, List<Integer> tmp, int[] visited) {
        if (tmp.size() == nums.length) {
            res.add(new ArrayList<>(tmp));
            return;
        }

        for (int i = 0; i < nums.length; i++) {
            if (visited[i] == 1) continue;

            if (i > 0 && nums[i] == nums[i - 1] && visited[i - 1] == 0) continue;

            tmp.add(nums[i]);
            visited[i] = 1;
            dfs(res, nums, tmp, visited);
            visited[i] = 0;
            tmp.remove(tmp.size() - 1);
        }
    }
}

Python

class Solution:
    def permuteUnique(self, nums: list) -> list:
        results = []
        arr_len = len(nums)
        def dfs(tmp: list, visited: list):
            if len(tmp) == arr_len:
                results.append(tmp[:])
                return

            for i in range(arr_len):
                if visited[i] or (i > 0 and nums[i] == nums[i - 1] and not visited[i - 1]): continue
                tmp.append(nums[i])
                visited[i] = 1
                dfs(tmp, visited)
                visited[i] = 0
                tmp.pop()

        nums.sort()
        dfs([], [0] * len(nums))
        return results

Go

import "sort"

func permuteUnique(nums []int) [][]int {
    var results [][]int
    sort.Ints(nums)
    arrLen := len(nums)
    dfs(&results, nums, []int{}, make([]int, arrLen), arrLen)

    return results
}

func dfs(results *[][]int, nums, tmp, visited []int, arrLen int) {
    if len(tmp) == arrLen {
        *results = append(*results, append([]int{}, tmp...)) // 注意深拷贝
        return
    }

    for i := 0; i < arrLen; i++ {
        if visited[i] == 1 || (i > 0 && nums[i] == nums[i - 1] && visited[i - 1] == 0) {
            continue
        }
        tmp = append(tmp, nums[i])
        visited[i] = 1
        dfs(results, nums, tmp, visited, arrLen)
        tmp = tmp[:len(tmp) - 1]
        visited[i] = 0
    }
}

其它解法

仿写 C++ 中的 nextPermutation 函数，该解法 #46、#47 均可 AC。

详见下一个排列

Java

import java.util.*;

class Solution {
    public List<List<Integer>> permuteUnique(int[] nums) {
        List<List<Integer>> results = new ArrayList<>();
        Arrays.sort(nums);
        results.add(arrToList(nums));
        while (nextPermutation(nums)) {
            results.add(arrToList(nums));
        }

        return results;
    }

    public List<Integer> arrToList(int[] nums) {
        List<Integer> result = new ArrayList<>();
        for (int num : nums) result.add(num);
        return result;
    }

    public boolean nextPermutation(int[] nums) {
        int arrLen = nums.length;
        int i = arrLen - 2, j = arrLen - 1, k = arrLen - 1;

        while (i >= 0 && nums[i] >= nums[j]) {
            i--; j--;
        }

        if (i == -1) return false;

        while (nums[i] >= nums[k]) k--;
        swap(nums, i, k);

        for (i = j, j = arrLen - 1; i < j; i++, j--) {
            swap(nums, i, j);
        }

        return true;
    }

    public void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}

Python

class Solution:
    def permuteUnique(self, nums: list) -> list:
        results = []
        arr_len = len(nums)

        def next_permutation() -> bool:
            i, j, k = arr_len - 2, arr_len - 1, arr_len - 1

            while i >= 0 and nums[i] >= nums[j]:
                i -= 1
                j -= 1

            if i == -1: return False

            while nums[i] >= nums[k]: k -= 1
            nums[i], nums[k] = nums[k], nums[i]

            i, j = j, arr_len - 1
            while i < j:
                nums[i], nums[j] = nums[j], nums[i]
                i += 1
                j -= 1

            return True

        nums.sort()
        results.append(nums[:])
        while next_permutation():
            results.append(nums[:])

        return results

Go

import "sort"

func permuteUnique(nums []int) [][]int {
    var results [][]int
    arrLen := len(nums)
    sort.Ints(nums)
    results = append(results, append([]int{}, nums...))

    for nextPermutation(nums, arrLen) {
        results = append(results, append([]int{}, nums...))
    }

    return results
}

func nextPermutation(nums []int, arrLen int) bool {
    i, j, k := arrLen - 2, arrLen - 1, arrLen - 1

    for i >= 0 && nums[i] >= nums[j] {
        i--
        j--
    }

    if i == -1 {
        return false
    }

    for nums[i] >= nums[k] {
        k--
    }
    nums[i], nums[k] = nums[k], nums[i]

    for i, j = j, arrLen - 1; i < j; i, j = i + 1, j - 1 {
        nums[i], nums[j] = nums[j], nums[i]
    }

    return true
}