LeetCode刷题记录贴（一）

1.两数之和

#哈希表
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        other = dict()
        for i in range(len(nums)):
            if other.get(target - nums[i]) != None:
                return [other.get(target - nums[i]),i]
            other[nums[i]] = i
        return None

#暴力版
class Solution(object):
    def twoSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[int]
        """
        if nums == []:
            return []
        sum = 0
        for i in range(len(nums)):
            for j in range(i+1,len(nums)):
                sum = nums[i] + nums[j]
                if sum == target:
                    return [i,j]

2.两数相加

class Solution(object):
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        list1 = []
        list2 = []
        while l1:
            list1.append(str(l1.val))
            l1 = l1.next
        while l2:
            list2.append(str(l2.val))
            l2 = l2.next
        a = int(''.join(list1[::-1]))
        b = int(''.join(list2[::-1]))
        sum = list(map(int,str(a+b)))[::-1]
        sroot = ListNode(sum[0])
        s = sroot
        for i in range(1,len(sum)):
            s.next = ListNode(sum[i])
            s = s.next
        return sroot

3.无重复字符的最长子串

可变滑动窗口

class Solution(object):
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """
        if s == []:
            return 0
        left = 0
        cur_len = 0
        max_len = 0
        domin = set()
        for i in range(len(s)):
            cur_len = cur_len + 1
            while s[i] in domin:
                domin.remove(s[left])
                left = left + 1
                cur_len = cur_len - 1
            if cur_len > max_len:
                max_len = cur_len
            domin.add(s[i])
        return max_len

4.寻找两个正序数组的中位数

python2和python3的除法不同，
python2： int除int，结果为int，除数被除数中有float类型，结果float类型
python3：除法结果都为float类型

class Solution(object):
    def findMedianSortedArrays(self, nums1, nums2):
        """
        :type nums1: List[int]
        :type nums2: List[int]
        :rtype: float
        """
        num = []
        while nums2 != [] and nums1 != []:
            if nums1[0] <= nums2[0]:
                num.append(nums1.pop(0))
            else:
                num.append(nums2.pop(0))
        if nums1 == []:
            num.extend(nums2)
        elif nums2 == []:
            num.extend(nums1)
        length = len(num)
        if length % 2 == 1:
            mid = float(num[length // 2])
        else:
            mid = (float(num[length // 2] + num[length // 2 - 1])) / 2
        return mid

5.最长回文子串

开始想的可以找到挨着相同的两个作为回文字符的最中心再向两侧查找找到最长回文串，但这种方法只适用于回文字符串为双数的（单数中间一个没有相同的）
之后基于这个想法改进了一下，比较一次i和 i+1，再比较一次i和i+2

class Solution(object):
    def longestPalindrome(self, s):
        """
        :type s: str
        :rtype: str
        """
        if s == "":
            return ""
        max_len = 0
        max_str = s[0]
        start = 0
        end = 1           
        while start<end and end<len(s):
            if s[start] == s[end]:
                print(start,end)
                str = self.max_str(s,start,end)
                if len(str) > max_len:
                    max_len = len(str)
                    max_str = str
            if end<len(s)-1:	
            #不能在while直接写end<len(s)-1，不然会少比较一次最后两个元素
                end += 1
                if s[start] == s[end]:
                    str = self.max_str(s, start, end)
                    if len(str) > max_len:
                        max_len = len(str)
                        max_str = str
            start += 1
        return max_str
        
	#在找到回文中心位置的时候向两侧扩展找到最大子串
    def max_str(self,s,start,end):
        if s[start] == s[end]:
            while start > 0 and end < len(s) - 1:
                start = start - 1
                end = end + 1
                if s[start] != s[end]:
                    return s[start+1:end]
        return s[start:end+1]
if __name__ == '__main__':
    t = Solution()
    s = "bb"
    # print(t.findMedianSortedArrays(nums1,nums2))
    print(t.longestPalindrome(s))

6.z字形变换

想法是创建一个列表，z字形改变列表值，最后输出列表非零值

a = [[0]*列数 for i in range(行数)]				 # 创建二维全零数组
for row in range(numRows-2,0,-1) 			# for循环倒序

class Solution(object):
    def convert(self, s, numRows):
        """
        :type s: str
        :type numRows: int
        :rtype: str
        """
        if s == "":
            return ""
        z = [['']*len(s) for i in range(numRows)]
        col = 0
        index = 0
        while index < len(s):
            for row in range(numRows):
                if index < len(s):
                    z[row][col] = s[index]
                    index += 1
            col = col + 1
            for row in range(numRows-2,0,-1):
                if index < len(s):
                    z[row][col] = s[index]
                    index += 1
                    col = col + 1
        result = []
        for i in range(numRows):
            for j in range(len(s)):
                if z[i][j] != '':
                    result.append(z[i][j])
        return ''.join(result)

if __name__ == '__main__':
    s = "LEETCODEISHIRING"
    numRows = 4
    t = Solution()
    print(t.convert(s,numRows))

7.整数反转

class Solution(object):
    def reverse(self, x):
        """
        :type x: int
        :rtype: int
        """
        s = list(str(x))
        if s[0] == '+' or s[0] == '-':
            s[1:] = s[len(s)-1:0:-1]
        else:
            s = s[::-1]
        s = int(''.join(s))
        if s < 2147483648 and s > -2147483648:
            return s
        else:
            return 0

8.字符串转换整数

一看就会一做就错。。一踩全是坑，细节太多了吧也
大概要考虑：字符串为空，字符串全空格，只有±符号，±符号后不是数字（我还多考虑了一个小数点结果不用又错一次）

class Solution(object):
    def myAtoi(self, str):
        """
        :type str: str
        :rtype: int
        """
        if str == "" or all(str[i]==' ' for i in range(len(str))):
            return 0
        result = []
        str = list(str)
        while str[0] == ' ':
            str.pop(0)
        # str = ''.join(str)
        if str[0].isdigit() or (len(str)>1 and (str[0] == '+' or str[0] == '-') and str[1].isdigit()):
            result.append(str[0])
            # print("str = ",str)
            for i in range(1,len(str)):
                if str[i].isdigit():
                    result.append(str[i])
                else:
                    break
            result = int(''.join(result))
            if result > 2**31:
                result = 2**31
            elif result < -2**31:
                result = -2**31
            return result
        return 0

if __name__ == '__main__':
    str = "     -4245.p134.56789"
    str2 = "4193 with words"
    str3 = " "
    t = Solution()
    print(t.myAtoi(str3))

9.回文数

class Solution(object):
    def isPalindrome(self, x):
        """
        :type x: int
        :rtype: bool
        """
        x = str(x)
        print(x)
        if x == "":
            return True
        start = 0
        end = len(x)-1
        isP = True
        while start <= end:
            if x[start] != x[end]:
                # print(x[start],x[end])
                return False
            # print(x[start],x[end])
            start += 1
            end -= 1
        return True

10.正则表达式匹配 ※

动态规划的题不太会下次单独刷一下

12.整数转罗马数字

自己第一反应的智障写法

class Solution(object):
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """
        result = []
        while num >= 1000:
            result.append('M')
            num = num -1000
        while num >= 900:
            result.append('CM')
            num = num - 900
        while num >= 500:
            result.append('D')
            num = num - 500
        while num >= 400:
            result.append('CD')
            num = num - 400
        while num >= 100:
            result.append('C')
            num = num -100
        while num >= 90:
            result.append('XC')
            num = num - 90
        while num >= 50:
            result.append('L')
            num = num - 50
        while num >= 40:
            result.append('XL')
            num = num - 40
        while num >= 10:
            result.append('X')
            num = num -10
        while num >= 9:
            result.append('IX')
            num = num - 9
        while num >= 5:
            result.append('V')
            num = num - 5
        while num >= 4:
            result.append('IV')
            num = num - 4
        while num >= 1:
            result.append('I')
            num = num - 1
        return ''.join(result)

参考题解优秀的写法，原链接

知识点：商, 余数 = divmod(被除数, 除数)

class Solution(object):
    def intToRoman(self, num):
        """
        :type num: int
        :rtype: str
        """
        digits = [(1000, "M"), (900, "CM"), (500, "D"), (400, "CD"), (100, "C"), (90, "XC"),
          (50, "L"), (40, "XL"), (10, "X"), (9, "IX"), (5, "V"), (4, "IV"), (1, "I")]
        roman_digits = []
        # Loop through each symbol.
        for value, symbol in digits:
            # We don't want to continue looping if we're done.
            if num == 0: break
            count, num = divmod(num, value)
            # Append "count" copies of "symbol" to roman_digits.
            roman_digits.append(symbol * count)
        return "".join(roman_digits)

13.罗马数字转整数

class Solution(object):
    def romanToInt(self, s):
        """
        :type s: str
        :rtype: int
        """
        sum = 0
        num = {'I':1,'IV':4,'V':5,'IX':9,'X':10,'XL':40,'L':50,'XC':90,'C':100,'CD':400,'D':500,'CM':900,'M':1000}
        i = 0
        while i<len(s):
            if s[i] == 'I' or s[i] == 'X' or s[i] == 'C':
                if i != len(s)-1 and (s[i:i+2] == 'IV' or s[i:i+2] == 'IX' or s[i:i+2] == 'XL' or s[i:i+2] == 'XC' or s[i:i+2] == 'CD' or s[i:i+2] == 'CM'):
                    temp = s[i:i+2]
                    i += 2
                else:
                    temp = s[i]
                    i += 1
            else:
                temp = s[i]
                i += 1
            print(num.get(temp))
            sum = sum + num.get(temp)
        return sum

14.最长公共前缀

知识点：map()函数在python2到python3中发生了变化
python2中 map()返回列表，可以直接输出
python3中 map()返回迭代器，输出需要list(map())

class Solution(object):
    def longestCommonPrefix(self, strs):
        """
        :type strs: List[str]
        :rtype: str
        """
        if strs == [] :
            return ""
        elif len(strs)==1:
            return strs[0]
        result = []
        new_strs = list(map(list,strs))
        while new_strs[0]!=[]:
            print(new_strs)
            for i in range(1,len(new_strs)):
                if new_strs[i] == [] or new_strs[i].pop(0) != new_strs[0][0]:
                    return ''.join(result)
            print(new_strs)
            result.append(new_strs[0].pop(0))
        return ''.join(result)

if __name__ == '__main__':
    t = Solution()
    print(t.longestCommonPrefix(["aa","a"]))

15.三数之和

class Solution(object):
    def threeSum(self, nums):
        """
        :type nums: List[int]
        :rtype: List[List[int]]
        """
        result = []
        hush_nums = {}
        nums.sort()
        print(nums)
        i = 0
        for i in range(len(nums)):
            if i != 0 and nums[i] == nums[i-1]:  #保证不取相同的序列
                i += 1
                continue
            j = i + 1
            e = len(nums)-1
            while e > j :
                if nums[j] + nums[e] == 0 - nums[i]:
                    print([nums[i],nums[j],nums[e]])
                    result.append([nums[i],nums[j],nums[e]])
                elif nums[j] + nums[e] > 0 - nums[i]:
                    e = e - 1
                    while e > j + 1 and nums[e+1] == nums[e]:
                        e = e - 1
                    continue
                j = j + 1
                while  j< len(nums)-1 and nums[j - 1] == nums[j]:
                    j = j + 1
        return result

16.最接近的三数之和

直接用上一题代码改的

class Solution(object):
    def threeSumClosest(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: int
        """
        min_abs = float('inf')
        nums.sort()
        print(nums)
        i = 0
        for i in range(len(nums)):
            if i != 0 and nums[i] == nums[i-1]:  #保证不取相同的序列
                i += 1
                continue
            j = i + 1
            e = len(nums)-1
            while e > j :
                sum_num = nums[i] + nums[j] + nums[e]
                if sum_num == target:
                    return sum_num
                elif target < sum_num :
                    e = e - 1
                    while e > j + 1 and nums[e+1] == nums[e]:
                        e = e - 1
                elif target > sum_num:
                    j = j + 1
                    while j < len(nums) - 1 and nums[j - 1] == nums[j]:
                        j = j + 1
                min_abs = target - sum_num if abs(target - sum_num ) < abs(min_abs) else min_abs
        return target - min_abs

if __name__ == '__main__':
    t = Solution()
    print(t.threeSumClosest([-4,-2,1,-5,-4,-4,4,-2,0,4,0,-2,3,1,-5,0],-19))

17.电话号码的字母组合※

回溯思想，循环+迭代，参考

class Solution:
    def letterCombinations(self, digits):
        """
        :type digits: str
        :rtype: List[str]
        """
        phone = {'2': ['a', 'b', 'c'],
                 '3': ['d', 'e', 'f'],
                 '4': ['g', 'h', 'i'],
                 '5': ['j', 'k', 'l'],
                 '6': ['m', 'n', 'o'],
                 '7': ['p', 'q', 'r', 's'],
                 '8': ['t', 'u', 'v'],
                 '9': ['w', 'x', 'y', 'z']}

        def backtrack(combination, next_digits):
            # if there is no more digits to check
            if len(next_digits) == 0:
                # the combination is done
                output.append(combination)
            # if there are still digits to check
            else:
                # iterate over all letters which map 
                # the next available digit
                for letter in phone[next_digits[0]]:
                    # append the current letter to the combination
                    # and proceed to the next digits
                    backtrack(combination + letter , next_digits[1:])


        output = []
        if digits:
            backtrack("", digits)
        return output

if __name__ == '__main__':
    t = Solution()
    print(t.letterCombinations('23'))

18.四数之和

1.三数和+外层循环
2.两数和 + 迭代
3.哈希表

class Solution(object):
    def fourSum(self, nums, target):
        """
        :type nums: List[int]
        :type target: int
        :rtype: List[List[int]]
        """
        if nums == '':
            return []
        n = len(nums)
        nums.sort()
        table = {}
        res = set()
        if n<4:
            return []
        for i in range(n-1):
            for j in range(i+1,n):
                s = nums[i] + nums[j]
                if target-s in table:
                    for temp in table[target-s]:
                        if temp[1]<i: res.add((nums[temp[0]],nums[temp[1]],nums[i],nums[j]))
                if s not in table:
                    table[s] = []
                table[s].append((i,j))
        result = []
        for re in res:
            result.append(list(re))
        return result

19.删除链表倒数第n个节点

链表，双指针，第一个指针先走n-1步，第一个指针到结束的时候删除第二个指针指向的项

20.有效的括号

栈

class Solution(object):
    def isValid(self, s):
        """
        :type s: str
        :rtype: bool
        """
        table = ['(','{','[']
        pop_table = {')':'(','}':'{',']':'['}
        if s == '':
            return True
        stack = []
        s = list(s)
        while s != []:
            temp = s.pop(0)
            if temp in table or stack == []:
                stack.append(temp)
            else:
                if pop_table.get(temp) == stack[len(stack)-1]:
                    stack.pop(len(stack)-1)
                else:
                    return False
        if stack == []:
            return True
        return False

21.合并两个有序列表

递归

76.最小覆盖子串

可变滑动窗口，end指针持续向右滑动，start指针在符合条件时向右滑动，保证lookup内字符串满足条件

all(可迭代类型参数)   # 判断给定的可迭代参数iterable中的所有元素是否都为TRUE，如果是返回True，否则返回 False。
map(函数，可迭代类型参数)   # 对可迭代类型参数中每一项执行函数
lambda 参数:函数    # 对参数执行函数

class Solution(object):
    def minWindow(self, s, t):
        """
        :type s: str
        :type t: str
        :rtype: str
        """
        if s == None:
            return ""
        from collections import Counter
        t = Counter(t)
        lookup = Counter()
        start = 0
        end = 0
        str = ""
        min_len = float("inf")
        while end < len(s):
            lookup[s[end]] += 1
            end = end + 1
            while all(map(lambda x:lookup[x]>=t[x],t.keys())):
                if end-start < min_len:
                    min_len = end-start
                    str = s[start:end]
                lookup[s[start]] -= 1
                start += 1
        return str

if __name__ == '__main__':
    t = Solution()
    nums1 = [1, 2]
    nums2 = []
    nums3 = [1, 2]
    nums4 = [3, 4]
    # print(t.findMedianSortedArrays(nums1,nums2))
    print(t.findMedianSortedArrays([1,2],[3,4]))

最后

以上就是感性电话为你收集整理的LeetCode刷题记录贴（一）的全部内容，希望文章能够帮你解决LeetCode刷题记录贴（一）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。