Skip to content

Commit 1e657ec

Browse files
author
luzhicheng
committed
有效的括号
有效的括号
1 parent 8a28a5a commit 1e657ec

10 files changed

Lines changed: 253 additions & 25 deletions

File tree

‎README.md‎

Lines changed: 2 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -6,11 +6,10 @@
66
|[Python数据分析](./data_analysis/main.md)|《深入浅出统计学》,numpy,pandas基础概念及练习等......|
77
|[Python爬虫](./spiders/main.md)|python爬虫基础库requests，beautifulsoup，xpath，selenium，代理池，部分网站爬虫等......|
88
|[计算机网络基础](./network_protocol/main.md)|网络基础知识，tcp/ip协议与http协议等......|
9-
|[LeetCode-数组](./leetcode_array/main.md)|leetcode数组类算法练习|
9+
|[LeetCode-数组](./leetcode_array/main.md)|leetcode数组类，字符串类算法练习|
1010
|[LeetCode-链表](./leetcode_linked_list/main.md)|leetcode链表类算法练习|
1111
|[LeetCode-哈希表](./leetcode_hash/main.md)|leetcode哈希表类算法练习|
12-
|[LeetCode-字符串](./leetcode_string/main.md)|leetcode字符串类算法练习|
13-
|[LeetCode-栈](./leetcode_stack/main.md)|leetcode栈类算法练习|
12+
|[LeetCode-栈+队列](./leetcode_stack/main.md)|leetcode栈+队列类算法练习|
1413
|[LeetCode-树](./leetcode_tree/main.md)|leetcode树类算法练习|
1514
|[Django学习](./django_note/main.md)|Django学习笔记。|
1615
|[其他](./others/main.md)|redis，kafka，ZeroMQ等|

‎leetcode_array/main.md‎

Lines changed: 4 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -14,6 +14,10 @@
1414
* [三数之和(左右指针)](三数之和.md)
1515
* [四数之和](四数之和.md)
1616
* [反转字符串(双指针)](反转字符串.md)
17+
* [反转字符串II](反转字符串II.md)
18+
* [替换空格](替换空格.md)
19+
* [翻转字符串里的单词](翻转字符串里的单词.md)
20+
* [左旋转字符串](左旋转字符串.md)
1721

1822
<!--
1923
2. [删除排序数组中的重复项](删除排序数组中的重复项.md)

‎leetcode_array/反转字符串II.md‎

Lines changed: 65 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,65 @@
1+
# 541.反转字符串II
2+
## 题目
3+
给定一个字符串 s 和一个整数 k，你需要对从字符串开头算起的每隔 2k 个字符的前 k 个字符进行反转。
4+
* 如果剩余字符少于 k 个，则将剩余字符全部反转。
5+
* 如果剩余字符小于 2k 但大于或等于 k 个，则反转前 k 个字符，其余字符保持原样。
6+
```python
7+
输入: s = "abcdefg", k = 2
8+
输出: "bacdfeg"
9+
10+
2k = 4
11+
1. 拆分"abcd" "efg"
12+
2. 翻转"bacd" "feg"
13+
3. 还原"bacdfeg"
14+
```
15+
16+
## 分析
17+
与[反转字符串](反转字符串.md)原理一样，这里只是对不同的部位进行翻转操作。
18+
* 把字符串按照2k的长度遍历
19+
* 长度大于等于k就只对前k个字符进行翻转，长度小于k就全部翻转
20+
21+
```python
22+
def reverseStr(s, k):
23+
def reverseS(ss):
24+
ss = list(ss)
25+
L = 0
26+
R = len(ss) - 1
27+
while L < R:
28+
ss[L], ss[R] = ss[R], ss[L]
29+
L += 1
30+
R -= 1
31+
return ''.join(ss)
32+
33+
for i in range(0, len(s), 2*k):
34+
# 按照2k的长度遍历字符串
35+
s1 = s[i:i+2*k]
36+
if len(s1) < k:
37+
# 全部翻转
38+
s1 = reverseS(s1)
39+
else:
40+
# 只反转前k个
41+
s1 = reverseS(s1[:k]) + s1[k:]
42+
s = s[:i] + s1 + s[i+2*k:]
43+
return s
44+
```
45+
46+
**其实分组后无论长度是多少，都是翻转前k个字符串**
47+
```python
48+
def reverseStr(s, k):
49+
def reverseS(ss):
50+
ss = list(ss)
51+
L = 0
52+
R = len(ss) - 1
53+
while L < R:
54+
ss[L], ss[R] = ss[R], ss[L]
55+
L += 1
56+
R -= 1
57+
return ''.join(ss)
58+
59+
for i in range(0, len(s), 2*k):
60+
s1 = s[i:i+2*k]
61+
# 反转前k个字符
62+
s1 = reverseS(s1[:k]) + s1[k:]
63+
s = s[:i] + s1 + s[i+2*k:]
64+
return s
65+
```

‎leetcode_array/左旋转字符串.md‎

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,43 @@
1+
# 58.2.左旋转字符串
2+
## 题目
3+
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串"abcdefg"和数字2，该函数将返回左旋转两位得到的结果"cdefgab"。
4+
```python
5+
输入: s = "lrloseumgh", k = 6
6+
输出: "umghlrlose"
7+
```
8+
9+
## 分析
10+
通过三次反转实现
11+
* 反转前n个字符： abcdefg -> bacdefg
12+
* 反转后n个字符： bacdefg -> bagfedc
13+
* 反转整个字符串: bagfedc -> cdefgab
14+
15+
```python
16+
def reverseLeftWords(s, n):
17+
def reverse(s):
18+
s = list(s)
19+
L = 0
20+
R = len(s) - 1
21+
while L < R:
22+
s[L], s[R] = s[R], s[L]
23+
L += 1
24+
R -= 1
25+
return ''.join(s)
26+
27+
s_1 = reverse(s[:n])
28+
s_2 = reverse(s[n:])
29+
return reverse(s_1 + s_2)
30+
```
31+
32+
如果不能使用切片，就用列表,时间复杂度O(n),空间复杂度O(n)
33+
```python
34+
class Solution:
35+
def reverseLeftWords(self, s: str, n: int) -> str:
36+
ans = []
37+
for i in range(n, len(s)):
38+
ans.append(s[i])
39+
40+
for i in range(n):
41+
ans.append(s[i])
42+
return ''.join(ans)
43+
```

‎leetcode_array/替换空格.md‎

Lines changed: 35 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,35 @@
1+
# 05.替换空格
2+
## 题目
3+
请实现一个函数，把字符串 s 中的每个空格替换成"%20"。
4+
```python
5+
输入：s = "We are happy."
6+
输出："We%20are%20happy."
7+
```
8+
9+
## 分析
10+
* 初始化一个长度数组，长度为字符串长度的3倍
11+
* 指针指向初始化数组的头部
12+
* 遍历字符串，如果字符是空，就填充"%", "2", "0"，指针前进三步，如果不是空，填充字符，指针前进一步
13+
14+
```python
15+
def replaceSpace(s):
16+
ans = ['' for _ in range(len(s)*3)]
17+
size = 0
18+
for char in s:
19+
if char == ' ':
20+
ans[size], ans[size+1], ans[size+2] = "%", "2", "0"
21+
size += 3
22+
else:
23+
ans[size] = char
24+
size += 1
25+
return ''.join(ans[:size])
26+
```
27+
28+
![](../pic/leetcode_array/05_1.gif)
29+
```python
30+
def replaceSpace(s):
31+
ans = []
32+
for char in s:
33+
ans.append(char) if char != ' ' else ans.append("%20")
34+
return ''.join(ans)
35+
```

‎leetcode_array/翻转字符串里的单词.md‎

Lines changed: 83 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,83 @@
1+
# 151.翻转字符串里的单词
2+
## 题目
3+
给定一个字符串，逐个翻转字符串中的每个单词。
4+
* 无空格字符构成一个单词
5+
* 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括
6+
* 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个
7+
8+
```python
9+
输入："the sky is blue"
10+
输出："blue is sky the"
11+
12+
输入：" hello world! "
13+
输出："world! hello"
14+
15+
输入："a good example"
16+
输出："example good a"
17+
```
18+
19+
## 分析
20+
* 提取字符串中的单词到列表中
21+
* 反转列表，原理同[反转字符串](反转字符串.md)
22+
23+
#### 如何提取字符串中的单词
24+
方法一：用指针记录单词的起始部位，然后记录单词的长度，碰到空格判定单词结束，更新起始部位
25+
26+
```python
27+
class Solution:
28+
def reverseWords(self, s: str) -> str:
29+
words = []
30+
start = 0
31+
length = 0
32+
for i in range(len(s)):
33+
if s[i] == ' ':
34+
if length > 0:
35+
# 单词尾部
36+
words.append(s[start:start+length])
37+
start = start + length + 1
38+
length = 0
39+
else:
40+
start += 1
41+
else:
42+
# 字符不为空就记录长度
43+
length += 1
44+
if length:
45+
words.append(s[start:start + length])
46+
47+
# 反转words
48+
L = 0
49+
R = len(words) - 1
50+
while L < R:
51+
words[L], words[R] = words[R], words[L]
52+
L += 1
53+
R -= 1
54+
return ' '.join(words)
55+
```
56+
57+
方法二：遍历字符串，字符从空格变为非空格时候判断单词起始位置，从非空格变为空格判断单词结束
58+
59+
```python
60+
def reverseWords(s):
61+
words = []
62+
start = 0
63+
end = 0
64+
for i in range(len(s) - 1):
65+
if s[i] == ' ' and s[i + 1] != ' ':
66+
start = i + 1
67+
68+
if s[i] != ' ' and s[i + 1] == ' ':
69+
end = i + 1
70+
words.append(s[start:end])
71+
72+
if start >= end:
73+
words.append(s[start:])
74+
75+
# 反转words
76+
L = 0
77+
R = len(words) - 1
78+
while L < R:
79+
words[L], words[R] = words[R], words[L]
80+
L += 1
81+
R -= 1
82+
return ' '.join(words)
83+
```

‎leetcode_stack/main.md‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1,6 +1,7 @@
11
## LeetCode栈
2-
1. [有效的括号](有效的括号.md)
2+
* [有效的括号](有效的括号.md)
33

4+
<!--
45
2. [最小栈](最小栈.md)
56
3. [用队列实现栈](用队列实现栈.md)
67
4. [用栈实现队列](用栈实现队列.md)
@@ -12,3 +13,4 @@
1213
10. [用栈操作构建数组](用栈操作构建数组.md)
1314
11. [整理字符串](整理字符串.md)
1415
12. [文件夹操作日志搜集器](文件夹操作日志搜集器.md)
16+
-->

‎leetcode_stack/有效的括号.md‎

Lines changed: 18 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -1,4 +1,5 @@
1-
### 有效的括号
1+
# 20.有效的括号
2+
## 题目
23
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
34

45
有效字符串需满足：
@@ -18,16 +19,15 @@
1819
输出: false
1920
```
2021

22+
## 分析
2123
#### 方法一：
2224
利用字符串替换的方法，如果该字符串是有效字符串，最终总能被替换为空字符串。
2325

2426
```python
2527
def isValid(s):
26-
while '[]' in s or '()' in s or '{}' in s:
27-
s = s.replace('[]', '').replace('{}', '').replace('()', '')
28-
if s == '':
29-
return True
30-
return False
28+
while '()' in s or '[]' in s or '{}' in s:
29+
s = s.replace('()', '').replace('[]', '').replace('{}', '')
30+
return not s
3131
```
3232

3333
#### 方法二：
@@ -37,22 +37,20 @@ def isValid(s):
3737

3838
```python
3939
def isValid(s):
40-
if len(s) % 2 == 1:
41-
return False
42-
43-
pairs = {
44-
')': '(',
45-
']': '[',
46-
'}': '{',
47-
}
48-
49-
stack = list()
50-
for ch in s:
51-
if ch in pairs:
52-
if not stack or stack[-1] != pairs[ch]:
40+
stack = []
41+
for char in s:
42+
if char not in ['(', '{', '[']:
43+
# 碰到右括号就弹栈
44+
if not stack:
5345
return False
46+
47+
if (stack[-1] + char) not in ('()', '{}', '[]'):
48+
return False
49+
5450
stack.pop()
5551
else:
56-
stack.append(ch)
52+
# 碰到左括号就入栈
53+
stack.append(char)
54+
5755
return not stack
5856
```

‎leetcode_string/main.md‎

Lines changed: 0 additions & 1 deletion
This file was deleted.

‎pic/leetcode_array/05_1.gif‎

34.9 KB
Loading

0 commit comments

Comments
 (0)