Long Luo's Life Notes

每一天都是奇迹

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\)
阅读全文 »

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

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)\)
阅读全文 »

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\)

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

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

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

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

阅读全文 »

By Long Luo

Leetcode 4. 寻找两个正序数组的中位数 ,这是一道很经典的题目,非常考察算法功底和逻辑思维能力,下面我们就通过几种解法来吃透这道题吧!

方法一:暴力法(合并数组)

思路与算法:

很直观的解法,先将两个数组按照元素大小合并为一个数组,然后根据新数组长度来决定返回值。

注意在合并数组时,要注意指针边界情况,不要越过数组边界。

代码如下所示:

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
public double findMedianSortedArrays(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;

if (m == 0) {
if (n % 2 == 0) {
return (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0;
} else {
return nums2[n / 2];
}
} else if (n == 0) {
if (m % 2 == 0) {
return (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0;
} else {
return nums1[m / 2];
}
}

int[] nums = new int[m + n];
int total = m + n;
for (int i = 0, j = 0, cnt = 0; cnt < total; ) {
if (i == m && j < n) {
nums[cnt++] = nums2[j++];
} else if (j == n && i < m) {
nums[cnt++] = nums1[i++];
} else if (i < m && nums1[i] <= nums2[j]) {
nums[cnt++] = nums1[i++];
} else if (i < m && nums1[i] > nums2[j]) {
nums[cnt++] = nums2[j++];
}
}

if (total % 2 == 0) {
return (nums[total / 2 - 1] + nums[total / 2]) / 2.0;
} else {
return nums[total / 2];
}
}

其实,在合并数组时,实际上只需要合并到 \(cnt=total/2\) 即可,优化之后如下所示:

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
public double findMedianSortedArrays_bf_opt(int[] nums1, int[] nums2) {
int m = nums1.length;
int n = nums2.length;

if (m == 0) {
if (n % 2 == 0) {
return (nums2[n / 2 - 1] + nums2[n / 2]) / 2.0;
} else {
return nums2[n / 2];
}
} else if (n == 0) {
if (m % 2 == 0) {
return (nums1[m / 2 - 1] + nums1[m / 2]) / 2.0;
} else {
return nums1[m / 2];
}
}

int[] nums = new int[m + n];
int total = m + n;
for (int i = 0, j = 0, cnt = 0; cnt <= total / 2; ) {
if (i == m && j < n) {
nums[cnt++] = nums2[j++];
} else if (j == n && i < m) {
nums[cnt++] = nums1[i++];
} else if (i < m && nums1[i] <= nums2[j]) {
nums[cnt++] = nums1[i++];
} else if (i < m && nums1[i] > nums2[j]) {
nums[cnt++] = nums2[j++];
}
}

if (total % 2 == 0) {
return (nums[total / 2 - 1] + nums[total / 2]) / 2.0;
} else {
return nums[total / 2];
}
}

复杂度分析:

  • 时间复杂度:\(O(m+n)\),需要遍历 \(2\) 个数组。
  • 空间复杂度:\(O(m+n)\),开辟了一个新数组,长度为 \(m+n\)
阅读全文 »
0%