LeetCode--Python解答

LeetCode–Python解答

【1】Two Sum:
给定一个整数组和一个目标值，找出数组中和为目标值的两个数，返回这两个数在数组中的index

示例：
给定数组list：num_list=[ 1, 2, 3, 6, 7]
目标值为：5

解答1（最简单的循环方法）：

def TwoSum(num_list,target):
    solution_list = []
    for i in range(len(num_list)-1):
        for j in range(i+1,len(num_list)):
            if num_list[i] + num_list[j] == target:
                solution_list.append(i)
                solution_list.append(j)
                return solution_list

def TwoSum(num_list,target):
    solution_list = []
    for i in range(len(num_list)-1):
        if target - num_list[i] in num_list:
                solution_list.append(num_list.index(target - num_list[i]))
                solution_list.append(i)
                solution_list.sort()
                return solution_list

【2】Reverse Integer:
给定一个整数（可以大于零或者小于零），保留原符号的情况下，反向输出这个整数。

示例：
给定：a=-123
返回结果为：-321
给定：b=123
返回结果为：b=321

解答

def ReverseInt(num):
    if num < 0:
        sign = -1
    else:
        sign = 1
    num2str = str(sign*num)
    num2str = num2str[::-1]
    str2num = sign*int(num2str)
    return str2num

【3】Palindrome（判断是否为回文数）:
给定一个整数组，如果反向输出这个整数，依然得到原整数，那么这个数就叫做回文数：

示例：
给定数a = 12321
反向输出：a_reverse=12321
a = a_reverse，a是回文数

给定数a = 12345
反向输出：a_reverse=54321
a 不等于 a_reverse，a不是回文数

负数不是回文数

解答1：

def isPalindrome(x):
    num = x
    res = 0
    while num>0:
        res = res*10 + num%10
        num = num // 10
    return res == x

【4】无重复最长字符串:
给定一个字符串，找出不含有重复字符的最长子串的长度。

示例：
输入: “abcabc”
输出: 3
解释: 无重复字符的最长子串是
“abc”，其长度为 3。

解答1：

def NoRepeatingAlp(in_str):
    max_length = ''
    for i in range(len(in_str)-1):
        new_str = in_str[i]
        j = i
        while j<(len(in_str)-1):
            if in_str[j+1] not in new_str:
                new_str = new_str + in_str[j+1]
                j += 1
            else:
                break
        if len(new_str) > len(max_length):
            max_length = new_str
    print(max_length)

解答2：

def NoRepeatingAlp(in_str):
    solution_str = ''
    for i in range(len(in_str)-1):
        j = i+1
        while j<=(len(in_str)-1):
            if in_str[j] not in in_str[i:j]:
                j += 1
            else:
                break
        if (j-i)>len(solution_str):
            solution_str = in_str[i:j]
    print(solution_str)

解答1

def CompTwo(num_seta,num_setb):
    new_list = []
    i = 0
    j = 0
    a = 0
    b = 0
    while True:
        if num_seta[i]<num_setb[j]:
            new_list.append(num_seta[i])
            if i < len(num_seta)-1:
                i += 1
            a += 1
            print(i)
        elif num_seta[i]==num_setb[j]:
            new_list.append(num_seta[i])
            new_list.append(num_setb[j])
            if i < len(num_seta)-1:
                i += 1
            if j < len(num_setb)-1:
                j += 1
            a += 1
            b += 1
        if num_seta[i]>num_setb[j]:
            new_list.append(num_setb[j])
            if j < len(num_setb)-1:
                j += 1
            b += 1
            print(j)
            print(b)
        if a == len(num_seta):
            new_list.extend(num_setb[j:])
            print(new_list)
            return new_list
        if b == len(num_setb):
            new_list.extend(num_seta[i:])
            print(new_list)
            return new_list


a = [1,3]
b = [2,4]
CompTwo(a,b)

解答2

def CompTwo(num_seta,num_setb):
    new_list = []
    res_a = num_seta
    res_b = num_setb
    while True:
        if res_a[0] < res_b[0]:
            new_list.append(res_a[0])
            res_a.remove(res_a[0])
        elif res_a[0] == res_b[0]:
            new_list.append(res_a[0])
            new_list.append(res_b[0])
            res_a.remove(res_a[0])
            res_b.remove(res_b[0])
        else:
            new_list.append(res_b[0])
            res_b.remove(res_b[0])
        if len(res_a) == 0:
            new_list.extend(res_b)
            print(new_list)
            return new_list
        if len(res_b) == 0:
            new_list.extend(res_a)
            print(new_list)
            return new_list

a = [1,3]
b = [2,4]
CompTwo(a,b)

解答3（无需建立新数组）：

def CheckPair(in_str):
    a = [in_str[0],]
    i = 1
    while i < len(in_str):
        a.append(in_str[i])
        if (a[-2] == '(' and a[-1] == ')') \
                or (a[-2] == '[' and a[-1] == ']') \
                or (a[-2] == '{' and a[-1] == '}'):
            a.pop()
            a.pop()
        i = i +1
    print(a)

def CheckPair(in_str):
    while '{}' in in_str or '()' in in_str or '[]' in in_str:
        in_str = in_str.replace('{}','').replace('()','').replace('[]','')
        print(in_str)
    return len(in_str)==0

[21]

def CombTwo(num_list1,num_list2):
    new_list = []
    old_list1 = num_list1
    old_list2 = num_list2
    while True:
        if old_list1[0]<old_list2[0]:
            new_list.append(old_list1[0])
            old_list1.pop(0)
        elif old_list1[0] == old_list2[0]:
            new_list.append(old_list1[0])
            new_list.append(old_list2[0])
            old_list1.pop(0)
            old_list2.pop(0)
        else:
            new_list.append(old_list2[0])
            old_list2.pop(0)
        if len(old_list1) == 0:
            new_list.extend(old_list2)
            print(new_list)
            return new_list
        if len(old_list2) == 0:
            new_list.extend(old_list1)
            print(new_list)
            return new_list

[26]

def NonRepeating(num_list):
    for i in range(len(num_list)-1):
        while num_list[i] in num_list[i+1:]:
            num_list.pop(i)
            print(num_list)

def NonRepeating(num_list):
    lenn = len(num_list)
    for i in range(len(num_list)-1):
        if num_list[i] in num_list[i+1:]:
            lenn = lenn -1
    return lenn

[53]

def MaxSubSum(num_list):
    lenn = len(num_list)
    new_list = []
    maxsubsum = 0
    for i in range(len(num_list)-1):
        for j in range(i+1,len(num_list)):
            print(j)
            if sum(num_list[i:j+1]) > maxsubsum:
                maxsubsum = sum(num_list[i:j+1])
                new_list.clear()
                new_list.extend(num_list[i:j+1])
    if num_list[-1] > maxsubsum:
        maxsubsum = 1
        new_list.clear()
        new_list.append(num_list[-1])

    return new_list

def MaxSubSum(num_list):
    maxlocal = 0
    globalmax = 0
    for i in range(len(num_list)):
        maxlocal = max(maxlocal+num_list[i],num_list[i])
        globalmax = max(globalmax, maxlocal)
    return globalmax

[88]

def CombTwoList(num_list1, num_list2):
    while len(num_list2)>0:
        if num_list2[0]<num_list1[0]:
            num_list1.append(num_list2[0])
            num_list2.pop(0)
        elif num_list2[0] == num_list1[0]:
            num_list1.append(num_list2[0])
            num_list1.append(num_list1[0])
            num_list1.pop(0)
            num_list2.pop(0)
        else:
            num_list1.append(num_list1[0])
            num_list1.pop(0)
            if len(num_list2) == 1:
                num_list1.append(num_list2[0])
                num_list2.pop()

    return num_list1

[101] 对称二叉树

def BinaryTree(num_list):
    length = len(num_list)
    new_list = []
    depth = 0
    j = 0
    while length>0:
        length = length - 2**depth
        depth += 1
    if depth == 1:
        print('True')
        return True
    if length < 0:
        print('False')
        return False
    index_start = 0
    for k in range(2,depth+1):
        index_start += 2**(k-2)
        sublength = 2**(k-1)
        sublength_half = 2**(k-2)
        if num_list[index_start:index_start+sublength_half] != num_list[index_start+sublength-1:index_start+sublength_half-1:-1]:
            print('False')
            return False
    else:
        print('True')
        return True

[136] Single Number

def SingleNumber(num_list):
    for i in range(0,len(num_list)-1):
        if num_list[i] not in num_list[i+1:]:
           a = num_list.pop(i)
           print(num_list)
           return a

[172]

def SingleNumber(num):
    count = 0
    n = num
    while n > 4:
        n = n//5
        count += n
    return count

print(SingleNumber(25))

[283]

def MoveZeros2End(num_list):
    count = 0
    while 0 in num_list:
            num_list.remove(0)
            count += 1
    num_list.extend([0,]*count)
    return num_list

[342]

def MoveZeros2End(num):
    while num > 3:
        num = num//4
    if num == 1:
        print('True')
    else:
        print('False')

[349]

def MoveZeros2End(num_list1,num_list2):
    new_list =[]
    for i in range(len(num_list1)):
        if num_list1[i] in num_list2:
            new_list.append(num_list1[i])
        while num_list1[i] in num_list2:
            num_list2.remove(num_list1[i])
    print(new_list)

[371] Sum of two integers

def MoveZeros2End(a,b):
    list = ['a']*a
    list.extend(['b']*b)
    print(len(list))
    return len(list)