《林老师带你学编程》知识星球是由多个工作10年以上的一线大厂开发人员联合创建,希望通过我们的分享,帮助大家少走弯路,可以在技术的领域不断突破和发展。
🔥 具体的加入方式:
- 直接访问链接:https://t.zsxq.com/14F2uGap7
- 微信扫码下图:
1.字符串交换位置
时间复杂度O(n) 空间复杂度O(1)输入 \”abcde\” 输出 \”edcba\”
def jiaohuan(str1):
s1 = list(str1)
tmp = 0
for i in range(0, int(len(s1) / 2)):
tmp = s1[i]
s1[i] = s1[len(s1) - i - 1]
s1[len(s1) - i - 1] = tmp
return s1
list1 = jiaohuan(\"abcde\")
print(\"\".join(list1)) # edcba
2.数组找最大值、最小值定义了一个数组a = [1,3,4,55,29] 查找数组中最大值
定义一个for循环对数组所有元素遍历一遍时间复杂度为O(n)
def max_value(l1):
min = -1
max = -1
for i in range(len(l1)):
if l1[i] > max:
max = l1[i]
min = i
print(max)
max_value([1, 2, 333, 4, 5, -1])
3.降低复杂度案例、 输入数组a = [1,2,3,4,5,6,4,4,4,2] 中查找出现次数最多的数值
def max_count(l1):
d1 = {}
for i in l1:
d1[i] = d1.get(i, 0) + 1
print(d1)
max_key = -1
count_num = -1
for i, v in d1.items():
if v > count_num:
count_num = v
max_key = i
print(max_key, count_num)
max_count([1, 2, 3, 4, 5, 6, 4, 4, 4, 4])
4.栈:后进先出 给定一个只包括 \'(\’,\’)\’,\'{\’,\’}\’,\'[\’,\’]\’ 的字符串,判断字符串是否有效。
class Solution:
def isValid(self, s: str) -> bool:
len_s = len(s)
if len_s % 2 != 0:
return False
if len_s == 0:
return True
# 利用进栈出栈的思想
str_dict = {\'(\': \')\', \'[\': \']\', \'{\': \'}\'}
stacked = []
for i in range(len_s):
# 如果符号为左括号进行压栈
if s[i] in str_dict.keys():
stacked.append(s[i])
# 如果栈不为空且符号在右括号内且左符号和最后一个元素相等
if stacked and s[i] in str_dict.values() and s[i] == str_dict[stacked[-1]]:
stacked.pop()
if stacked == []:
return True
else:
return False
solution = Solution()
print(solution.isValid(\"{[]}\")) # True
print(solution.isValid(\"{[[}\")) # False
5.为支持浏览器前进和后退功能,利用栈记录历史访问信息 后进先出
first_list = []
last_list = []
def chrome_a(url):
if url not in last_list and url not in first_list: # 当用户访问一个新页面
last_list.append(url)
elif url in last_list: # 当用户后退一个页面
last_list.pop()
first_list.append(url)
else: # 用户前进一个页面
first_list.pop()
last_list.append(url)
for url in [1, 2, 3, 4, 5, 5, 4, 3, 4]:
chrome_a(url)
print(first_list)
print(last_list)
6.队列 先进先出
def josephus2(num, k, m):
alist = list(range(1, num + 1))
index, step = k - 1, m # 从1号开始报数,数到3的那个人出列
for i in range(num - 1):
index = (index + step - 1) % len(alist)
print(\'出去的数:\', alist.pop(index))
return \'最后的一个数:%s\' % alist[0]
print(josephus2(13, 1, 3))
7.数组 数组在内存中是连续存放的,数组内的数据,可以通过索引值直接取出得到
数组 [1,4,3,5,2] 去掉一个最大值和最小值求平均数 要求不允许开辟O(n)空间复杂度的数据结构
def score_avge(l1):
max_num = -1
max_number = -1
min_num = -1
min_number = 99
for index, value in enumerate(l1):
if value > max_number:
max_number = value
max_num = index
if min_number > value:
min_number = value
min_num = index
print(min_num, max_num)
del l1[max_num]
del l1[min_num]
scores = 0
for i, v in enumerate(l1):
scores += v
print(\"平均分:{}\".format(scores / len(l1)))
score_avge([1, 4, 3, 5, 2])
8.字符串 操作都是On
字符串替换将a替换为1aa替换为2 abaabccdaab==>1b2bccd2b
for i in s1:
if i == \"a\":
count += 1
else:
if count != 0:
s2 += str(count)
count = 0
s2 += i
print(s2)
9. 字符串 s = \”goodgoogle\”,判断字符串 t = \”google\” 在 s 中是否存在
s = \"goodgoogle1ccc\"
t = \"google\"
status = True
num = 0
for i, v in enumerate(s):
if v == t[num]:
status = True
num += 1
if len(t) == num:
break
else:
status = False
num = 0
if status:
print(\"t字符串在s中\")
else:
print(\"t字符串不在s中\")
10.设置有且有两个字符串a = \”1345239\” b = \”12345\” 由于\”345\”同时出现在a和b中因此输出345