LeetCode

由于时效问题，该文某些代码、技术可能已经过期，请注意！！！本文最后更新于：3 年前

力扣笔记

题目描述：

给定一个字符串 s ，其中包含字母顺序打乱的用英文单词表示的若干数字（0-9）。按 升序 返回原始的数字。例如：输入：s = “owoztneoer”，输出：”012”。
原题地址：https://leetcode-cn.com/problems/reconstruct-original-digits-from-english/

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
### 我的方案，使用了递归，，但依然很惨，没通过力扣的检验（超出时间限制）

def originalDigits(s):
    en_num = {'zero':0, 'one':1,'two':2, 'three':3,'four':4,'five':5,'six':6,'seven':7,
    'eight':8,'nine':9}

    ss = []
    for k, v in en_num.items():
        l = len(k)
        c = 0
        for i in k:
            if i in s:
                c += 1

        if c == l:
            ss.append(str(v))
            for j in k:
                s = s.replace(j, '', 1)
    if s:
        ss.append(originalDigits(s))
        ss.sort()
        return ''.join(ss)
    else:
        ss.sort()
        return ''.join(ss)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
## 力扣方案

class Solution:
    def originalDigits(self, s: str) -> str:
        c = Counter(s)

        cnt = [0] * 10
        cnt[0] = c["z"]
        cnt[2] = c["w"]
        cnt[4] = c["u"]
        cnt[6] = c["x"]
        cnt[8] = c["g"]

        cnt[3] = c["h"] - cnt[8]
        cnt[5] = c["f"] - cnt[4]
        cnt[7] = c["s"] - cnt[6]
        
        cnt[1] = c["o"] - cnt[0] - cnt[2] - cnt[4]

        cnt[9] = c["i"] - cnt[5] - cnt[6] - cnt[8]

        return "".join(str(x) * cnt[x] for x in range(10))

如果单看这个代码的话我依然看不懂，还是要看解释，解释在上面的网址里都有。反正这个题确实挺考验智商的吧，我这智商还是洗洗睡了。

题目描述：

无重复字符串的排列组合。编写一种方法，计算某字符串的所有排列组合，字符串每个字符均不相同。
例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。
原题地址：https://leetcode-cn.com/problems/permutation-i-lcci/
python的itertools包中的permutations函数可以实现。

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
### itertools.permutations函数源码如下

def permutation(iterable, r=None):
    #  r:length permutations of elements in the iterable
    # permutations('ABCD', 2) --> AB AC AD BA BC BD CA CB CD DA DB DC
    # permutations(range(3)) --> 012 021 102 120 201 210
    pool = tuple(iterable)
    n = len(pool)
    r = n if r is None else r
    if r > n:
        return
    indices = list(range(n))
    cycles = list(range(n, n-r, -1))
    yield tuple(pool[i] for i in indices[:r])
    while n:
        for i in reversed(range(r)):
            cycles[i] -= 1
            if cycles[i] == 0:
                indices[i:] = indices[i+1:] + indices[i:i+1]
                cycles[i] = n - i
            else:
                j = cycles[i]
                indices[i], indices[-j] = indices[-j], indices[i]
                yield tuple(pool[i] for i in indices[:r])
                break
        else:
            return

源码还是挺复杂的，，，，，

1
2
3
4
5
6
7
8
9
10
11
### 力扣方法，也是递归

def permutation(S):
        if len(S)==1:
            return [S]
        ans=[]
        for i in range(len(S)):
            s=S[:i]+S[i+1:]              
            for string in permutation(s):
                ans.append(S[i]+string)
        return ans
题目描述：

给定两个单词 word1 和 word2，请计算出 word1 与 word2 的最长公共字串长度。

1
2
3
4
5
6
7
8
9
10
11
word1 = 'abcfdg'
word2 = 'bcfdkhi'

def comm_len(word1, word2):
    c = 0
    for i in range(len(word1)):
        if word[i-c:i+1] in word2:
            c += 1

    return c

题目描述：

快速排序

1
2
3
4
5
6
7
8
9
10
11
arr = [1, 4, 5, 12, 32, 198, 2, 3, 15, 112, 132]

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    tmp = arr[0]
    left = [i for i in arr[1:] if i < tmp]
    right = [i for i in arr[1:] if i > tmp]
    return quick_sort(left) + [tmp] + quick_sort(right)

print(quick_sort(arr))
题目描述：

归并排序应用

  • 1、将两个有序数组合并成一个有序数组

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    a = [1,3,5,7]
    b = [2,6,8,9]

    def merge(left, right):
        '''合并操作，将两个有序数组left[]和right[]合并成一个大的有序数组'''
        #left与right的下标指针
        l, r = 0, 0
        result = []
        while l<len(left) and r<len(right):
            if left[l] < right[r]:
                result.append(left[l])
                l += 1
            else:
                result.append(right[r])
                r += 1
        result += left[l:]
        result += right[r:]
        return result

    print(merge(a, b))
    1. 每个 SNP 位点用一个长度为 2 的 list 表示，第一个元素为染色体编号（chr，范围为
      1~22），第二个元素为染色体上的位置（pos）。写一个 python 函数，输入两个正序（按
      chr 和 pos 排序）的 SNP 位点 list，输出一个合并且去重的正序 SNP 位点 list。不能使用
      sorted 函数、pandas 库，要求时间复杂度尽可能低。
      例如：
      1
      2
      Input: list1 = [[1,230], [1,4000], [2,500]], list2 = [[2,320], [6,70]]
      Output: [[1,230], [1,4000], [2,320], [2,500], [6,70]]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
list1 = [[1,230], [1,4000], [2,500]]
list2 = [[2,320], [6,70]]

def merge(list1, list2):
    l, r = 0, 0
    result = []
    while l<len(list1) and r<len(list2):
        if list1[l][0] < list2[r][0]:
            if list1[l] not in result:
                result.append(list1[l])
            l += 1
        else:
            if list2[r] not in result:
                result.append(list2[r])
            r += 1

    result += list1[l:]
    result += list2[r:]
    return result

print(merge(list1, list2))
题目描述：

输出单向链表中倒数第k个结点

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Node(object):

    def __init__(self, val=0):
        self.val = val
        self.next = None


while True:
    try:
        l, s, k, head = int(input()), list(map(int, input().split())), int(input()), Node()
        while k:
            head.next = Node(s.pop())
            head = head.next
            k -= 1
        print(head.val)
    except:
        break
题目描述：

给定两个单词 word1 和 word2，请计算出将 word1 转换成 word2 所使用的最少操作数。
参考：https://www.jianshu.com/p/9a53f32cf62b

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
def editDistance(str1, str2):
    '''
    计算字符串str1和str2的编辑距离
    '''
    edit = [[i+j for j in range(len(str2)+1)] for i in range(len(str1)+1)]
    print(edit)
    for i in range(1,len(str1)+1):
        for j in range(1,len(str2)+1):
            if str1[i-1] == str2[j-1]:
                d = 0
            else:
                d = 1
            edit[i][j] = min(edit[i-1][j]+1,edit[i][j-1]+1,edit[i-1][j-1]+d)
    return edit[len(str1)][len(str2)]

editDistance('python', 'pyton')
题目描述：

  • 最长回文字串

    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    s = input()
    win_len = 2
    s_list = []
    for i in range(len(s)):
        for j in range(i+1, len(s) + 1):
            ss = s[i:j]
            if ss == ss[::-1]:
                s_list.append(len(ss))
                
    print(max(s_list))

  • 输入两个 DNA 序列，输出它们的最长公共序列。

    1
    2
    Input: seq1 = “AGGCT”, seq2 = “GGCA”
    Output: “GGC”
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
seq1 = 'AGGCT'
seq2 = 'GGCA'

def comm_len(seq1, seq2):
    c = 0
    seq_list = []
    for i in range(len(seq1)):
        tmp = seq1[i-c:i+1]
        if tmp in seq2:
            c += 1
            seq_list.append(tmp)

          
    return seq_list[-1]

print(comm_len(seq1, seq2))
leetcode
Python

本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！