Long Luo's Life Notes

每一天都是奇迹

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 1.7k 阅读时长 ≈ 2 分钟

By Long Luo

这是 Leetcode 525. 连续数组 的题解。

方法一：暴力

思路与算法：

首先想到的方法是暴力法，遍历数组，计算 \(0\) 和 \(1\) 的数量，如果相等，则更新最大长度 \(\textit{maxLength}\)。

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
public int findMaxLength(int[] nums) {
    if (nums == null || nums.length <= 1) {
        return 0;
    }

    int ans = 0;
    int len = nums.length;
    for (int i = 0; i < len; i++) {
        int zeroCnt = 0;
        int oneCnt = 0;
        for (int j = i; j < len; j++) {
            zeroCnt += nums[j] == 0 ? 1 : 0;
            oneCnt += nums[j] == 1 ? 1 : 0;

            if (zeroCnt == oneCnt) {
                ans = Math.max(ans, 2 * zeroCnt);
            }
        }
    }

    return ans; 
}

复杂度分析：

  • 时间复杂度：\(O(N^2)\)，其中 \(N\) 是数组 \(\textit{nums}\) 的长度。
  • 空间复杂度：\(O(1)\)。
阅读全文 »

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 7.8k 阅读时长 ≈ 7 分钟

By Long Luo

Leetcode 29. 两数相除 题目如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
29. 两数相除

给定两个整数，被除数`dividend`和除数`divisor`。将两数相除，要求不使用乘法、除法和`mod`运算符。

返回被除数`dividend`除以除数`divisor`得到的商。

整数除法的结果应当截去（truncate）其小数部分，例如：truncate(8.345) = 8 以及 truncate(-2.7335) = -2

示例 1:
输入: dividend = 10, divisor = 3
输出: 3
解释: 10/3 = truncate(3.33333..) = truncate(3) = 3

示例 2:
输入: dividend = 7, divisor = -3
输出: -2
解释: 7/-3 = truncate(-2.33333..) = -2
 
提示：
被除数和除数均为$32$位有符号整数。
除数不为$0$。
假设我们的环境只能存储 $32$ 位有符号整数，其数值范围是 [-2^31, 2^31-1]。本题中，如果除法结果溢出，则返回2^31-1。

方法一：暴力法

思路与算法：

因为题目要求不能使用乘法、除法和mod运算符，那么首先想到的是只能使用加减法了。

因为除法就是看被除数能让多少个除数相加，因为被除数和除数均为 \(32\) 位有符号整数，存在溢出的可能，所以我们首先进行类型转换，转换成 \(\textit{Long}\) 型进行处理。

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
public int divide(int dividend, int divisor) {
    if (dividend == 0) {
        return 0;
    }

    long dividendLong = dividend;
    long divisorLong = divisor;

    boolean sign = false;
    if (dividendLong < 0 && divisorLong < 0) {
        dividendLong = -dividendLong;
        divisorLong = -divisorLong;
    } else if (dividendLong < 0 && divisorLong > 0) {
        sign = true;
        dividendLong = -dividendLong;
    } else if (dividendLong > 0 && divisorLong < 0) {
        sign = true;
        divisorLong = -divisorLong;
    }

    long ans = 0;
    while (dividendLong >= divisorLong) {
        dividendLong -= divisorLong;
        ans++;
    }

    ans = sign ? -ans : ans;

    return ans > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) ans;
}

毫无疑问，超时了！

卡在了这个 -2147483648 1 测试用例上，那么我们针对这些边界值进行处理：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
public int divide(int dividend, int divisor) {
    if (divisor == Integer.MIN_VALUE) {
        return dividend == Integer.MIN_VALUE ? 1 : 0;
    }
    
    if (dividend == Integer.MIN_VALUE) {
        if (divisor == 1) {
            return dividend;
        } else if (divisor == -1) {
            return Integer.MAX_VALUE;
        }
    } else if (dividend == Integer.MAX_VALUE) {
        if (divisor == 1) {
            return dividend;
        } else if (divisor == -1) {
            return -dividend;
        }
    }

    long dividendLong = dividend;
    long divisorLong = divisor;

    boolean sign = false;
    if (dividendLong < 0 && divisorLong < 0) {
        dividendLong = -dividendLong;
        divisorLong = -divisorLong;
    } else if (dividendLong < 0 && divisorLong > 0) {
        sign = true;
        dividendLong = -dividendLong;
    } else if (dividendLong > 0 && divisorLong < 0) {
        sign = true;
        divisorLong = -divisorLong;
    }

    long ans = 0;
    while (dividendLong >= divisorLong) {
        dividendLong -= divisorLong;
        ans++;
    }

    ans = sign ? -ans : ans;

    return ans > Integer.MAX_VALUE ? Integer.MAX_VALUE : (int) ans;
}

因为针对性处理了，所以上述代码 AC 了！

因为题目规定了“只能存储 \(32\) 位整数”，所以代码中都不能使用任何 \(64\) 位整数。

如果除法结果溢出，那么我们需要返回 \(2^{31}-1\) 作为答案。因此我们可以首先对于溢出或者容易出错的边界情况进行讨论：

  • 当被除数为 \(32\) 位有符号整数的最小值 \(-2^{31}\) 时：
    • 如果除数为 \(1\)，那么我们可以直接返回答案 \(-2^{31}\)；
    • 如果除数为 \(-1\)，那么答案为 \(2^{31}\)，产生了溢出。此时我们需要返回 \(2^{31}-1\)。
  • 当除数为 \(32\) 位有符号整数的最小值 \(-2^{31}\) 时：
    • 如果被除数同样为 \(-2^{31}\)，那么我们可以直接返回答案 \(1\)；
    • 对于其余的情况，我们返回答案 \(0\)。
  • 当被除数为 \(0\) 时，我们可以直接返回答案 \(0\)。
阅读全文 »

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 988 阅读时长 ≈ 1 分钟

By Long Luo

VSCode

Everything

NodeJS

cmake

MikeX

CTex

GNU Octave

Octave 下载地址

Matlab

TexStudio

Qt

Keil

Python

conda

anaconda

https://mirrors.tuna.tsinghua.edu.cn/help/anaconda/

https://mirrors.tuna.tsinghua.edu.cn/anaconda/archive/

https://blog.csdn.net/qq_42681787/article/details/144693871

Python 2.7 及以上版本中，Python 自带了一个名为 ensurepip 的模块，可以用来安装 pip。在命令行中运行以下命令：

python -m ensurepip –upgrade

pip –version

pip install requests

#=====新建python2.7环境

conda create -n my_name python=2.7 # 创建conda环境 source activate my_name # 激活conda环境

#=====python2.7环境安装jupyter notebook

which jupyter # 默认jupyter路径，通常是主conda环境下的

新版的ipython只支持python3.4以上版本，python2.7的jupyter需配置如下版本

pip install ipython==5.5.0 pip install ipykernel==4.8.2 which jupyter # my_name环境下的jupyter

#=====保证my_name环境下的package在python可以引用到 import sys sys.path # 如果没有my_name下site-packages路径，则手动加入 sys.path.append(‘/root/anaconda3/envs/my_name/lib/python2.7/site-packages’) #=====启动jupyter nohup jupyter notebook –no-browser –port=3434 –ip=192.168.1.230 –allow-root –notebook-dir=‘/’

Python

Android

Android Studio

Gradle

Java

语音

Praat

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 5.4k 阅读时长 ≈ 5 分钟

By Long Luo

Leetcode 209. 长度最小的子数组 题目如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
209. 长度最小的子数组

给定一个含有$n$个正整数的数组和一个正整数$\textit{target}$。

找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回$0$。

示例 1：
输入：target = 7, nums = [2,3,1,2,4,3]
输出：2
解释：子数组 [4,3] 是该条件下的长度最小的子数组。

示例 2：
输入：target = 4, nums = [1,4,4]
输出：1

示例 3：
输入：target = 11, nums = [1,1,1,1,1,1,1,1]
输出：0
 
提示：
1 <= target <= 10^9
1 <= nums.length <= 10^5
1 <= nums[i] <= 10^5
 
进阶：
如果你已经实现 $O(n)$ 时间复杂度的解法, 请尝试设计一个 $O(n\log n)$ 时间复杂度的解法。

方法一：暴力法

思路与算法：

很容易想到，使用 \(2\) 个循环，枚举 \(\textit{nums}\) 中的每个下标作为子数组的开始下标，对于每个子数组 \(i\)，满足 \(i \le x \le j\)，使得：

\[ sum=\sum_{x=i}^{j}\textit{nums}[x] \ge $\textit{target} \]

，并更新子数组的最小长度 \(j-i+1\)。

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
public int minSubArrayLen_bf(int target, int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    int len = nums.length;
    int ans = Integer.MAX_VALUE;
    for (int i = 0; i < len; i++) {
        int sum = 0;
        for (int j = i; j < len; j++) {
            sum += nums[j];
            if (sum >= target) {
                ans = Math.min(ans, j - i + 1);
                break;
            }
        }
    }

    return ans == Integer.MAX_VALUE ? 0 : ans;
}

复杂度分析：

  • 时间复杂度：\(O(N^2)\)，其中 \(N\) 是数组 \(\textit{nums}\) 的长度。
  • 空间复杂度：\(O(1)\)。

方法二：双指针 + 滑动窗口

思路与算法：

因为求连续子数组的和大于某个值，那么很容易想到使用滑动窗口，使用双指针 \(left\) 和 \(right\) 表示一个窗口：

  1. \(right\) 向右移增大窗口，直到窗口内的数字和大于等于了 \(target\);
  2. 记录此时的长度，\(left\) 向右移动，开始减少长度，每减少一次，就更新最小长度，直到当前窗口内的数字和 \(< target\)，回到第 \(1\) 步。

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public int minSubArrayLen_sw(int target, int[] nums) {
    if (nums == null || nums.length == 0) {
        return 0;
    }

    int len = nums.length;
    int ans = Integer.MAX_VALUE;
    int sum = 0;
    int left = 0;
    int right = 0;
    while (right < len) {
        sum += nums[right];
        while (sum >= target) {
            ans = Math.min(ans, right - left + 1);
            sum -= nums[left];
            left++;
        }

        right++;
    }

    return ans == Integer.MAX_VALUE ? 0 : ans;
}

复杂度分析：

  • 时间复杂度：\(O(N)\)，其中 \(N\) 是数组 \(\textit{nums}\) 的长度，指针 \(\textit{start}\) 和 \(\textit{end}\) 最多各移动 \(n\) 次。
  • 空间复杂度：\(O(1)\)。
阅读全文 »

发表于 更新于 分类于 Waline： 阅读次数： 本文字数： 3.8k 阅读时长 ≈ 3 分钟

By Long Luo

Leetcode 155. 最小栈 题目如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
155. 最小栈

设计一个支持push，pop，top操作，并能在常数时间内检索到最小元素的栈。

push(x) —— 将元素 x 推入栈中。
pop() —— 删除栈顶的元素。
top() —— 获取栈顶元素。
getMin() —— 检索栈中的最小元素。
 
示例:

输入：
["MinStack","push","push","push","getMin","pop","top","getMin"]
[[],[-2],[0],[-3],[],[],[],[]]

输出：
[null,null,null,null,-3,null,0,-2]

解释：
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin();   --> 返回 -3.
minStack.pop();
minStack.top();      --> 返回 0.
minStack.getMin();   --> 返回 -2.
 
提示：
pop、top和getMin操作总是在 非空栈 上调用。

这道题有很多方法可以做，其实也就分为额外 \(O(n)\) 和 \(O(1)\) 空间，如果 \(O(n)\) 的话，有非常多方法。如果只能使用一个栈的话，需要思考如何处理当前 \(\texttt{push()}\) 更小的数如何处理。

方法一：栈 + List

思路与算法：

最开始想到的方法就是用一个链表存储数据，这样排序之后获取最小值的就直接读取链表的第一个元素即可。

代码如下所示：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class MinStack {
    Deque<Integer> stack;
    List<Integer> numList;

    public MinStack() {
        stack = new ArrayDeque<>();
        numList = new ArrayList<>();
    }

    // time: O(nlogn)
    public void push(int val) {
        stack.push(val);
        numList.add(val);
        Collections.sort(numList);
    }

    // time: O(n)
    public void pop() {
        int val = stack.pop();
        for (int i = 0; i < numList.size(); i++) {
            if (numList.get(i) == val) {
                numList.remove(i);
                break;
            }
        }

        Collections.sort(numList);
    }

    // time: O(1)
    public int top() {
        return stack.peek();
    }

    // time: O(1)
    public int getMin() {
        return numList.get(0);
    }
}

复杂度分析

  • 时间复杂度：
    • \(\texttt{push()}\): \(O(n \log n)\)，需要进行排序。
    • \(\texttt{pop()}\): \(O(n \log n)\)。
    • \(\texttt{top()}\): \(O(1)\)。
    • \(\texttt{getMin()}\): \(O(1)\)。
  • 空间复杂度：\(O(N)\)，其中 \(N\) 为总操作数。

方法二：辅助栈

思路与算法：

方法一时间复杂度太高，其实排序也是不必要的，占用空间也不小。

因为栈是先进后出的，所以可以在每个元素 \(x\) 入栈时把当前栈的最小值 \(min\) 存储起来。

在这之后无论何时，如果栈顶元素是 \(x\)，我们就可以直接返回存储的最小值 \(min\)。

因此我们可以使用一个辅助栈，与元素栈同步插入与删除，用于存储与每个元素对应的最小值。

  • 当要入栈一个元素时，获取当前辅助栈的栈顶存储的最小值，与当前元素比较得出最小值，将这个最小值插入辅助栈中；

  • 当一个元素要出栈时，我们把辅助栈的栈顶元素也一并弹出；

  • 在任意一个时刻，栈内元素的最小值就存储在辅助栈的栈顶元素中。

阅读全文 »
0%