Q:无序列表，如何去重
ids=[1,2,3,4,3,2,5]
new_ids=list(set(ids))
print(new_ids)
Q:字符串转为数字，比如 str="1234"，变成 int 1234，并测试这个程序。
def stoi(sr):
current = 0
for i in sr:
sum = ord(i) - ord('0')
current = current * 10 + sum
return current
assert type(stoi('1234')) == int
assert stoi('1234') == 1234
Q:99乘法表
for i in range(1, 10):
for j in range(1, i+1):
print('{}x{}={}\t'.format(j, i, i*j), end='')
print()
Q:实现阶乘函数
def factorial(num):
if num <=1:
return 1
else:
return num*factorial(num-1)
Q:leetcode-468. 验证IP地址
IPv4的格式:(1~255).(0~255).(0~255).(0~255)
def legal_ip_2(one_str):
try:
IPy.IP(one_str)
return True
except Exception as e:
return False
def validate_IP4(ip):
nums = ip.split('.')
for x in nums:
if len(x) == 0 or len(x) > 3:
return "Neither"
if x[0] == '0' and len(x) != 1 or not x.isdigit() or int(x) > 255:
return "Neither"
return "IPv4"
def validate_IP6(ip):
nums = ip.split(':')
hexdigits = '0123456789abcdefABCDEF'
for x in nums:
if len(x) == 0 or len(x) > 4 or not all(c in hexdigits for c in x):
return "Neither"
return "IPv6"
def valid(ip):
if ip.count('.')==3:
return validate_IP4(ip)
if ip.count(':')==7:
return validate_IP6(ip)
else:
return False
Q:算出 100-1000 的质数
质数（prime number）又称素数，有无限个。质数定义为在大于1的自然数中，除了1和它本身以外不再有其他因数的数称为质数.
data = []
for i in range(100, 1000):
for j in range(2, i):
if i % j == 0:
break
else:
data.append(i)
Q:字符串反转，如果字符串有多个空格也需要处理
ss = 'SJD EJJF EJEF'
ss = re.sub(r'\s', '', ss)
print(ss[::-1])
ss = 'SJD EJJF EJEF'
ss = re.sub(r'\s', '', ss)
a = ''.join(reversed(ss))
print(a)
def rev(str):
l = list(str)
newstr = ""
while len(l) > 0:
newstr += l.pop()
return newstr
Q: 找出第一个非重复字符在字符串中的位置
举例：‘Google’返回l,4
def first_char(string):
dict1 = {}
for i in string:
# 累计字符的出现次数
if i in dict1:
dict1[i] += 1
# 只出现一次，key对应的value就记1次
else:
dict1[i] = 1
for i in range(len(string)):
if dict1[string[i]] == 1:
return string[i], i
Q:实现斐波那契数列(⽣成器方式)
def fib(n):
if n <= 1:
return n
return fib(n-1)+fib(n-2)
for i in range(1, 20):
print(fib(i), end=',')
Q:leetcode-165. 比较版本号
Python比较两个版本号 v1 和 v2；如果 v1 > 2 返回 1,如果 v1 < v2 返回 -1， 除此之外返回 0。
思路：
根据点分割两个字符串将分割的结果存储到数组中。
遍历较长数组并逐个比较块。如果其中一个数组结束了，实际上可以根据需要添加尽可能多的零，以继续与较长的数组进行比较。
如果两个版本号不同，则返回 1 或 -1。
版本号相同，返回 0。
def compare_version(v1, v2):
nums1 = v1.split('.')
nums2 = v2.split('.')
n1, n2 = len(nums1), len(nums2)
for i in range(max(n1, n2)):
i1 = int(nums1[i])if i < n1 else 0
i2 = int(nums2[i])if i < n2 else 0
if i1 != i2:
return 1 if i1 > i2 else -1
return 0
Q:对列表中的 IP 排序
import socket
iplist = ['192.168.1.33','10.5.1.3','10.5.2.4','202.98.96.68','133.120.1.1','192.168.1.22']
print(sorted(iplist, key=socket.inet_aton))
socket.inet_aton(ip_string) // 依赖于inet_aton的C实现
转换IPV4地址字符串（192.168.10.8）成为32位打包的二进制格式（长度为4个字节的二进制字符串），它不支持IPV6。inet_pton()支持IPV4/IPV6地址格式。
Q:字符串中找出连续最长的数字串。
import re
print(max(re.findall(r"\d*", input()), key=len))
Q:leetcode-409. 最长回文串
给定一个包含大写字母和小写字母的字符串，找到通过这些字母构造成的最长的回文串。
def cront(s):
count = collections.Counter(s).values()
x = sum([item//2*2 for item in count if(item//2>0)])
return x if x==len(s)else x+1
Q:[-1,1,1,-2,3,-5,-6]⽤最少的时间、空间，将负数放在左边、正数放右边。
def sort_li(li):
i = 0
j = len(li) - 1
while i <= j:
if li[i] < 0:
i += 1
elif li[j] > 0:
j -= 1
else:
li[i], li[j] = li[j], li[i]
return li
Q: lintcode-144. 交错正负数
给出一个含有正整数和负整数的数组，重新排列成一个正负数交错的数组。
解题思路：先将负数放在左边，正数放在右边，然后隔一个数进行交换。（需考虑负数多，正数多和正负数一样多的情况）
def rerange(a):
if a is None or len(a) == 0:
return a
start, end = 0, len(a)-1
while start < end:
if a[end] > 0:
end -= 1
elif a[start] < 0:
start += 1
else:
a[start], a[end] = a[end], a[start]
# 计算负数的个数
if a[start] < 0:
start += 1
# 负数更少，两边应是正数
if start < len(a)-start:
start, end = 0, len(a)-2
# 正数更少，两边应是负数
elif start > len(a)-start:
start, end = 1, len(a)-1
# 正数负数相同
else:
start, end = 0, len(a)-1
while start < end:
if a[start] > 0 or a[end] < 0:
break
a[start], a[end] = a[end], a[start]
start += 2
end -= 2
return a
Q:字符串中最小的整数
class Solution(object):
def FindMaxinStr(self, s):
if not s:
return 0
result = []
current = 0
for c in s:
num = ord(c) - ord('0')
if 0 <= num <= 9:
current = current*10+num
result.append(current)
else:
current = 0
return min(result)
Q: 剑指 Offer 50. 第一个只出现一次的字符
在字符串s中找出第一个只出现一次的字符。如果没有，返回一个单空格。 s 只包含小写字母。
def first(s: str):
dic = {}
for c in s:
dic[c] = c not in dic
for c in s:
if dic[c]:
return c
return ''
Q:输⼊一个字符串然后去掉空格，在统计每个字⺟出现的次数
from collections import Counter
a = a.replace(' ', '')
b = Counter(a)
def str_count(a):
a = a.replace(' ', '')
b = {}
i = 0
while i < len(a):
if a[i] in b:
b[a[i]] += 1
else:
b[a[i]] = 1
i += 1
return b
Q：leetcode-88.合并两个有序数组
给你两个有序整数数组 nums1 和 nums2，请你将 nums2 合并到 nums1 中，使 nums1 成为一个有序数组。
def merge(nums1, m, nums2, n):
p1 = m - 1
p2 = n - 1
p = m + n - 1
while p1 >= 0 and p2 >= 0:
if nums1[p1] < nums2[p2]:
nums1[p] = nums2[p2]
p2 -= 1
else:
nums1[p] = nums1[p1]
p1 -= 1
p -= 1
nums1[:p2 + 1] = nums2[:p2 + 1]
Q::leetcode-10. 青蛙跳台阶问题
一只青蛙一次可以跳上1级台阶，也可以跳上2级台阶。求该青蛙跳上一个 n 级的台阶总共有多少种跳法。
def numWays(self, n: int) -> int:
a, b = 1, 1
for _ in range(n):
a, b = b, a + b
return a % 1000000007
Q:leetcode-704. 二分法查找
给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target ，写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
def search(self, nums: List[int], target: int) -> int:
left, right = 0, len(nums) - 1
while left <= right:
pivot = left + (right - left) // 2
if nums[pivot] == target:
return pivot
if target < nums[pivot]:
right = pivot - 1
else:
left = pivot + 1
return -1
Q:leetcode-20. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
def isvalid(self, s):
stack = []
mapping = {")": "(", "}": "{", "]": "["}
for char in s:
if char in mapping:
top_element = stack.pop() if stack else '#'
if mapping[char] != top_element:
return False
else:
stack.append(char)
return not stack
Q: 剑指Offer-40. 最小的k个数
输入整数数组 arr ，找出其中最小的 k 个数。例如，输入4、5、1、6、2、7、3、8这8个数字，则最小的4个数字是1、2、3、4。
def getLeastNumbers(arr: List[int], k: int):
arr.sort()
return arr[:k]
时间复杂度：O(n log n),其中 nn 是数组 arr 的长度.算法的时间复杂度即排序的时间复杂度。
空间复杂度：O(log n),排序所需额外的空间复杂度为O(logn)
def getLeastNumbers1(arr:List[int], k: int):
if k == 0:
return list()
hp = [-x for x in arr[:k]]
heapq.heapify(hp)
for i in range(k,len(arr)):
if -hp[0]>arr[i]:
heapq.heappop(hp)
heapq.heappush(hp, -arr[i])
ans = [-x for x in hp]
return ans
时间复杂度：O(nlogk)，其中 nn 是数组 arr 的长度。由于大根堆实时维护前 k小值，所以插入删除都是 O(logk) 的时间复杂度，最坏情况下数组里 nn 个数都会插入，所以一共需要 O(nlogk) 的时间复杂度。
空间复杂度：O(k)，因为大根堆里最多 kk 个数。
Q: leetcode-347. 前 K 个高频元素
class Solution:
def top(self,nums,k):
lookup = Counter(nums)
return [item[0] for item in lookup.most_common(k)]
Q:leetcode-560.和为K的子数组
class Solution:
def subarraySum(self, nums, k: int):
# num_times 存储某“前缀和”出现的次数，这里用collections.defaultdict来定义它
# 如果某前缀不在此字典中，那么它对应的次数为0
num_times = collections.defaultdict(int)
num_times[0] = 1 # 先给定一个初始值，代表前缀和为0的出现了一次
cur_sum = 0 # 记录到当前位置的前缀和
res = 0
for i in range(len(nums)):
cur_sum += nums[i] # 计算当前前缀和
if cur_sum - k in num_times: # 如果前缀和减去目标值k所得到的值在字典中出现，即当前位置前缀和减去之前某一位的前缀和等于目标值
res += num_times[cur_sum - k]
# 下面一句实际上对应两种情况，一种是某cur_sum之前出现过（直接在原来出现的次数上+1即可），
# 另一种是某cur_sum没出现过（理论上应该设为1，但是因为此处用defaultdict存储，如果cur_sum这个key不存在将返回默认的int，也就是0）
# 返回0加上1和直接将其置为1是一样的效果。所以这里统一用一句话包含上述两种情况
num_times[cur_sum] += 1
return res
Q:leetcode-434. 字符串中的单词数
class Solution:
def countSegments(self, s):
return len(s.split())
Q:字母统计并排序, 其中单词用空格分隔，统计出现最多的3个单词和它们出现的次数
def func(data):
# 按空格对字符串进行切割
data = data.split(' ')
list_most=collections.Counter(data).most_common(3)
print(list_most)
Q:快排
def quick_sort(li,start,end):
if start >= end:
return
left = start
right = end
mid = li[left]
while left < right:
while left < right and li[right] >= mid:
right -= 1
li[left] = li[right]
while left < right and li[left] < mid:
left += 1
li[right] = li[left]
li[left] = mid
quick_sort(li, start, left-1)
quick_sort(li, left+1, end)
Q:冒泡排序
def bubble_sort(arr):
length = len(arr)
while length > 0:
for i in range(length-1):
if arr[i] > arr[i+1]:
current = arr[i]
arr[i] = arr[i+1]
arr[i + 1] = current
length -= 1
网友评论