LeetCode - 宝宝题解

2019/01/25 刷题

箴言

我认为,不论处于什么阶段,什么状态,保持一个A题的习惯,是保证自己在工程技术前进的路上,数据结构和算法知识不会退步的有效办法。

LeetCode题解

LC3 Longest Substring Without Repeating Characters

Given a string, find the length of the longest substring without repeating characters.

Example 1:

Input: "abcabcbb"
Output: 3 
Explanation: The answer is "abc", with the length of 3. 

Example 2:

Input: "bbbbb"
Output: 1
Explanation: The answer is "b", with the length of 1.

Example 3:

Input: "pwwkew"
Output: 3
Explanation: The answer is "wke", with the length of 3. 
            Note that the answer must be a substring, "pwke" is a subsequence and not a substring.

这个题,可以引出字符串类型题目的一个经典套路 —— Sliding Window。

Python3

# Sliding Window
class Solution:
    def lengthOfLongestSubstring(self, s):
        """
        :type s: str
        :rtype: int
        """

        ans = 0

        store_with_index = ""

        for cur in s:
            if cur not in store_with_index:
                store_with_index += cur
                ans = max(ans, len(store_with_index))
            else:
                cut = store_with_index.index(cur)
                store_with_index = store_with_index[cut + 1:] + cur

        return ans

# Runtime: 72 ms

效果为

image

LC2 Add Two Numbers

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Example:

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

很简单的语言基础题目,做好边界处理,type convert,就好。

Python3

# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def addTwoNumbers(self, l1, l2):
        """
        :type l1: ListNode
        :type l2: ListNode
        :rtype: ListNode
        """
        data_1 = ""
        data_2 = ""
        while (l1 != None):
            data_1 += str(l1.val)
            l1 = l1.next

        while (l2 != None):
            data_2 += str(l2.val)
            l2 = l2.next

        data_1 = int(data_1[::-1])
        data_2 = int(data_2[::-1])

        ans = str(data_1 + data_2)[::-1]

        ret = []
        for i in range(len(ans)):
            ret.append(ListNode(int(ans[i])))

        for i in range(len(ret) - 1):
            ret[i].next = ret[i+1]

        return ret[0]
        

# Runtime: 108 ms

Search

    Table of Contents