算法刷题记录

算法刷题记录

希望能够有所改变！

1、数位递增的数

题目链接

1
2
3
4
5
6
7
8
9
10
11
# 解法一
n = int(input())
ans = 0
for i in range(1, n):
    x = str(i)
    for j in range(len(x)-1):
        if x[j] > x[j+1]:
            break
    else:
        ans += 1
print(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
# 解法二
import sys

num = 0
n = int(input())
for i in range(1, n+1):
    c = i
    b = sys.maxsize  # 获取最大整数值sys.maxsize
    while c > 0:
        a = c % 10
        if a > b:
            break
        b = a
        c //= 10  # 使用整数除法
    if c == 0:
        num += 1
print(num)

2、凯撒加密

题目链接

1
2
3
4
5
6
7
8
9
c = input()  # 直接读取输入
new_c = ""

for char in c:
    # 计算下一个字符的ASCII值，并确保在有效的ASCII字符范围内
    new_char = chr((ord(char)-97+3)%26+97)
    new_c += new_char

print(new_c)

3、最大距离

题目链接

1
2
3
4
5
6
7
8
9
10
import os
import sys

n = int(input())
s = list(map(int,input().split()))
max_num = 0
for i in range(n-1):
    for j in range(i+1,n):
        max_num = max(max_num,abs(j-i) + abs(s[j]-s[i]))
print(max_num)

4、反倍数

题目链接

1
2
3
4
5
6
7
8
9
10
11
import os
import sys

n = int(input())
s = list(map(int,input().split()))
ans = 0

for i in range(1,n+1):
    if i%s[0]!=0 and i%s[1]!=0 and i%s[2]!=0:
        ans += 1
print(ans)

5、洁净数

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
# 不太聪明的版本,这里会运行超时
import os
import sys

n= int(input())
ans=0
for i in range(1,n+1):
    i_str = str(i)
    while len(i_str)>0:
        if len(i_str) == 1 and int(i_str) != 2:
            ans += 1

        a=int(i_str[-1])  # 取个位数
        if a == 2:
            break
        else:
            i_str = i_str[:-1]  # 去掉最后一位数
print(ans)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
# 参考别人的版本，使用到了判断字符或字符串是否在目标中
import os
import sys

n=int(input())
count=1

for i in range(1,n):
      if "2" in str(i):
          continue
      else:
          count=count+1

print(count)

6、确定字符串是否包含唯一字符

题目链接 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
# 解法一：使用字典来计算各个字符出现的次数，再单独使用一个循环来判断是否有不唯一的字符出现
c = input().strip()
n = len(c)
count = {}  # 初始化计数器字典
for i in range(n):
    if c[i] in count:
        count[c[i]] += 1
    else:
        count[c[i]] = 1

# 检查是否有重复的字符
if any(value > 1 for value in count.values()):
    print("NO")
else:
    print("YES")

1
2
3
4
5
6
# 解法二：set(s) 将字符串 s 转换成一个集合，集合中的元素是唯一的，这意味着所有重复的字符都会被移除
s=input()
if len(set(s))==len(s):
  print('YES')
else:
  print('NO') 
1
2
3
4
5
6
7
8
9
10
11
12
# 解法三：类似解法一，换了一种表达方式，使用列表来存储数据
s = input()
s = s.upper()
d = []
for i in s:
    if i not in d:
        d.append(i)
    else:
        print("NO")
        break
else:
    print("YES") 
1
2
3
4
5
6
7
8
9
# 解法四：从第一个字符开始判断字符串中有几个该字符出现
# 使用到了str.count(sub)方法来计算子字符串sub在字符串s中出现的次数
s = input()
for word in s:
    if s.count(word) != 1:
        print("NO")
        break
    if word == s[-1]:
        print("YES")

7、确定字符串是否是另一个的排列

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
# 解法一：使用字段来统计字符出现的次数，字典的键是字符，值是出现的次数
s1 = input()
s2 = input()

count1 = {}
count2 = {}
for i in s1:
    if i not in count1:
        count1[i]=1
    else:
        count1[i]+=1

for j in s2:
    if j not in count2:
        count2[j]=1
    else:
        count2[j]+=1
        
if count1==count2:
    print("YES")
else:
    print("NO")
1
2
3
4
5
6
7
8
9
10
11
12
# 解法二：将输入转换为列表，并使用sort()方法进行排序，确保列表中的字符按照升序排列，然后比较两个列表是否完全相同即可
import os
import sys

s1 = list(input())
s2 = list(input())
s1.sort()
s2.sort()
if s1 == s2:
    print("YES")
else:
    print("NO")
1
2
3
4
5
6
7
8
9
10
11
12
13
# 解法三：确保两个字符串的长度一定相同，并且每个字符出现的次数也相同，同样可以保证两个字符串是一致的
import os
import sys

a=input()
b=input()
for i in a:
    if a.count(i)!=b.count(i) or len(a)!=len(b): 
        s='NO'
        break
    else:
        s='YES'
print(s)

8、压缩字符串

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import os
import sys

s=input()
count={}
for i in s:
    if i not in count:
        count[i] = 1
    else:
        count[i]+=1

ss=""
for i in count:
    if count[i]>1:  # 如果字符出现次数大于1
        ss += i + str(count[i])
    else:
        ss += i   # 若只出现一次，那么数字1可以省略

if len(ss)<len(s):  # 如果输入的字符串可以压缩，输出压缩的字符串
    print(ss)
else:
    print("NO")   # 否则输出NO

但是上述解法不具备普遍性，比如：
测试 AAABBWWWWFFAAAAAAAVVQQQQER 输出是 A10B2W4F2V2Q4ER 但是正确答案是 A3B2W4F2A7V2Q4ER

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
# 优化版
import os
import sys

s = input()
compressed = ""
count = 1

for i in range(len(s)):
    # 如果当前字符与下一个字符相同，则增加计数----使用这种思路就可以解决上面提到的问题了
    if i < len(s) - 1 and s[i] == s[i + 1]:
        count += 1
    else:
        # 否则，将字符和计数添加到压缩字符串中
        if count > 1:
            compressed += s[i] + str(count)
        else:
            compressed += s[i]
        count = 1  # 重置计数
if len(compressed) < len(s):  
    print(compressed)
else:
    print("NO")

9、Fizz Buzz经典问题

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
import os
import sys

n = int(input())
if n % 3==0:
    if n % 5==0:
        print("FizzBuzz")
    else:
        print("Fizz")
elif n % 5==0:
        print("Buzz")
else:
    print(n)

10、反转字符串中的字符

题目链接

1
2
3
4
5
6
7
8
9
10
# 我的解
import os
import sys

s = input()
ss=''
n=len(s)
for i in range(n):
    ss+=s[n-1-i]
print(ss)
1
2
# 参考解1
print("".join(reversed(input())))
  • input()：用于获取用户输入的内容
  • reversed()：这是一个内置函数，它会返回输入内容的反转迭代器
  • "".join()：它将可迭代对象（这里就是反转后的内容）中的元素用空字符串连接起来，形成一个新的字符串并输出
1
2
3
4
5
6
s= 'abcde'
print((reversed(s)))
print("".join(reversed(s)))

# <reversed object at 0x00000150B401DC10>
# edcba

不得不说，这个方法太牛了！

提问：什么是迭代器？

迭代器是一种可以遍历一个集合（如列表、字符串等）的对象。

它具有以下特点： 1. 它提供了一种按顺序访问集合中元素的方式。 2. 可以逐个获取元素，而无需一次性获取所有元素。 3. 通常通过特定的方法（如 next() ）来获取下一个元素。

迭代器使得可以高效地遍历大型集合，而无需将所有元素一次性加载到内存中。在 Python 中，很多内置的数据结构都可以返回迭代器，比如列表、元组、字典等。

1
2
3
4
# 参考解2
x=input()
y=x[::-1]
print(y)

y=x[::-1]：这里使用了切片操作，[::-1] 表示以步长为 -1 对 x 进行切片，也就是将 x 中的字符顺序反转，得到反转后的字符串并赋值给 y

其实可以在此基础上进一步优化： 

1
print(input()[::-1])
不愧是python

11、找到给定字符串中的不同字符

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
a=input()
b=input()
c=0
for i in a:
  if a.count(i)==b.count(i):
      continue
  else:
      print(i)
      c=1
      break
for i in b:
   if c==1:
       break
   else:
       if b.count(i)==a.count(i):
        continue
       else:
        print(i)

12、查找两个总和为特定值的索引

题目链接

1
2
3
4
5
6
7
n = int(input())  # 给定数组的长度
s = list(map(int,input().split()))
k = int(input())
for i in s:
    if k-i in s:
        print(s.index(i),s.index(k-i))
        break

13、实现选择排序

题目链接

  • 解1 
    1
    2
    3
    4
    n=input()
    s=list(map(int,input().split()))
    s.sort()
    print(' '.join(map(str,s)))

这样写其实没有用到选择排序，有点取巧了，要是老实按照题目的意思应该是下面的做法

选择排序的工作原理是每一次从需要排序的数据元素中选出最小的一个元素，存放在序列的起始位置，直到全部待排序的数据元素排列完毕

  • 解2 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    def selection_sort(arr):
        n = len(arr)
        for i in range(n):
            min_idx = i
            for j in range(i + 1, n):
                if arr[j] < arr[min_idx]:
                    min_idx = j
            arr[i], arr[min_idx] = arr[min_idx], arr[i]
        return arr

    n = int(input())
    arr = list(map(int, input().split()))
    sorted_arr = selection_sort(arr)
    print(" ".join(map(str, sorted_arr)))

这行代码 arr[i], arr[min_idx] = arr[min_idx], arr[i] 是 Python 中的一种特殊的赋值方式，称为“多元赋值”或“并行赋值”。

它的作用是将数组 arr 中索引为 i 的元素和索引为 min_idx 的元素的值进行交换。

比如说，如果 arr[i] 的值是 5 ，arr[min_idx] 的值是 3 ，那么执行这行代码后，arr[i] 的值会变成 3 ，arr[min_idx] 的值会变成 5 。

这种赋值方式可以在一行代码中简洁地完成两个变量值的交换，而无需使用临时变量来辅助。例如，如果使用传统的方式交换两个变量的值，可能会这样写：

1
2
3
temp = arr[i]
arr[i] = arr[min_idx]
arr[min_idx] = temp

但使用多元赋值就可以直接一步完成交换，使代码更加简洁和高效。

  • 解3 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    def select_sort_simple(li):      # 复杂度是 O(n**2)
        li_new=[]
        for i in range(len(li)):
            min_val=min(li)           #找最小值则需要遍历一遍  O(n)
            li_new.append(min_val)
            li.remove(min_val)          # 删除的时候还需要遍历一遍 O(n)
        return li_new
    n=int(input())
    li=list(map(int,input().split()))
    for i in select_sort_simple(li):
        print(i,end=' ')

这种实现方式虽然能达到排序的目的，但由于频繁使用了查找最小值和删除元素的操作，导致时间复杂度较高，不是一种高效的选择排序实现方式。

14、K倍区间

题目链接

暴力解法如下，使用双重循环遍历，但是会超时

  • 解1 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    import os
    import sys

    N,K = list(map(int,input().split()))
    a = [0] * N
    for i in range(N):
        a[i] = int(input())

    ans = 0
    for i in range(N):
        temp = 0
        for j in range(i,N):
            temp += a[j]
            if temp % K == 0:
                ans += 1
    print(ans)
  • 解2

使用了前缀和的思想来解决，参考代码如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
'''
[1 2 3 4 5]
前缀和[1 3 6 10 15]
对2(k)取余数[1 1 0 0 1]会发现余数为0>>说明该位置的前缀和能被k整除；余数相减为0的，两两组合C（3，2）。c(n,2)等于（n-1）*n/2
'''
n,k=map(int,input().split())
ls=[0]*k        #创建一个长度为k的0列表存储对前缀和取余后余数的种类个数
ans=0           #接收结果
for i in range(n):
  ans+=int(input())    #计算前缀和
  ls[ans%k]+=1    #前缀和余数为0的个数有多少，余数为1的有多少...
ans=ls[0]     #先得出余数为0的个数
for i in range(len(ls)):
  if ls[i]>0:    #说明该余数出现过
    ans+=ls[i]*(ls[i]-1)//2
print(ans)

15、实现插入排序

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import os
import sys

n = int(input())

s = list(map(int,input().split()))

for i in range(1, n):
    key = s[i]
    j = i - 1
    while j >= 0 and s[j] > key:
        s[j + 1] = s[j]
        j -= 1
    s[j + 1] = key

output_str = ' '.join(map(str, s))
print(output_str)

对于未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入

16、实现快速排序

题目链接

1
2
3
4
5
6
7
8
9
10
11
12
13
14
n = int(input())
arr = list(map(int, input().split()))

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

sorted_arr = quick_sort(arr)
print(' '.join(map(str,sorted_arr)))

在这个快速排序的实现中，首先选择一个枢轴元素（这里选择中间元素），然后将列表分为小于枢轴、等于枢轴和大于枢轴的三部分，接着对小于和大于枢轴的部分递归地进行快速排序，最后将它们组合起来。

17、实现归并排序

题目链接

alt text 
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
import os
import sys

n = int(input())
arr = list(map(int,input().split()))

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    # 将数组分为两部分
    mid = len(arr) // 2
    left_half = arr[:mid]
    right_half = arr[mid:]

    # 递归地对两部分进行分解
    left_half = merge_sort(left_half)
    right_half = merge_sort(right_half)

    # 合并并排序两个子数组
    return merge(left_half, right_half)

def merge(left, right):
    result = []
    i = j = 0

    # 比较左右两部分的元素，将较小的元素添加到结果中
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1

    # 将剩余的元素添加到结果中
    result.extend(left[i:])
    result.extend(right[j:])
    return result

sorted_arr=merge_sort(arr)
print(' '.join(map(str,sorted_arr)))

18、实现基数排序

题目链接

实现基数排序算法。基数排序的介绍如下：

1、将整数按位数切割,然后将数值统一为同样的数位长度，数位较短的数前面补零。

2、从最低位开始，依次进行一次排序。

3、从最低位排序一直到最高位排序完成以后, 数列就变成一个有序序列。

1
2
3
4
5
6
7
8
9
10
11
12
13
# 法1
n=int(input())
L=list(map(int,input().split()))
buts=[[] for _ in range( len(str(max(L))))]#决定最大桶子数量

for i in range(n):
  buts[len(str(L[i]))-1].append(L[i])
for i in buts:
  i.sort()
ook=[]
for i in buts:
  ook+=i
print(*ook)

方法2：

以下是 Python 实现的基数排序代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def radix_sort(arr):
    max_value = max(arr)
    exp = 1

    while max_value // exp > 0:
        # 初始化 10 个桶（每个桶代表一个数位 0-9）
        buckets = [[] for _ in range(10)]

        # 将元素放入相应的桶中
        for num in arr:
            digit = (num // exp) % 10
            buckets[digit].append(num)

        # 从桶中取出元素，按顺序重新排列数组
        arr = [item for bucket in buckets for item in bucket]

        # 移动到下一个数位
        exp *= 10

    return arr

以下是对代码的解释：

  1. 首先找到数组中的最大值 max_value，这是为了确定排序的位数。
  2. 进入一个循环，循环的条件是 max_value // exp > 0。exp 初始为 1，每次循环后乘以 10，用于依次处理个位、十位、百位等。
  3. 在每次循环中：
    • 创建 10 个空桶，用于存储不同数位的值。
    • 遍历数组中的每个元素，计算当前数位的值（通过 (num // exp) % 10），并将元素放入相应的桶中。
    • 然后从桶中依次取出元素，重新排列数组。
    • 最后更新 exp 到下一个数位。

示例用法：

1
2
3
arr = [170, 45, 75, 90, 802, 24, 2, 66]
sorted_arr = radix_sort(arr)
print(sorted_arr)

基数排序是一种非比较型整数排序算法，它的时间复杂度为 \(O(d(n + k))\)，其中 \(n\) 是待排序元素个数，\(k\) 是进制数（通常是 10），\(d\) 是最大数的位数。

python
算法刷题记录
http://jrhu0048.github.io/2024/07/08/python/suan-fa-shua-ti-ji-lu/
作者
JR.HU
发布于
2024年7月8日
更新于
2024年10月15日
许可协议