LeetCode刷题笔记 LeetCode刷题笔记

2019/4/16 subject：771. Jewels and Stones
solution：

class Solution: def numJewelsInStones(self, J, S): """ :type J: str :type S: str :rtype: int """ return sum(S.count(i) for i in J)

tips：
python中，count() 方法用于统计某个元素在列表中出现的次数。
subject: 1021. Remove Outermost Parentheses
solution:

class Solution: def removeOuterParentheses(self, S: str) -> str: count = 0 prev = None res = [] left_n = 0 right_n = 0 j = 0 for i in range(len(S)): if S[i] == "(": left_n += 1# add 1 when left parenthesis else: right_n += 1# add 1 when right if left_n == right_n: res.append(S[j + 1:i])# add part when left_n = right_n j = i + 1# because next first item will be cut, i + 1 gives j += 2 total return ''.join(res)

2019/4/17 subject: 709. To Lower Case
solution1 :

class Solution: def toLowerCase(self, str: str) -> str: for i in str: if ord(i) in range(65,91): new = ord(i) + 32 n = chr(new) str = str.replace(i,n) return str

solution 2:

class Solution(object): def toLowerCase(self, str): """ :type str: str :rtype: str """ stack = [ord(x) for x in str] for i in range(len(stack)): if stack[i] > 64 and stack[i] < 91: stack[i] += 32 asw=[chr(x) for x in stack]return ''.join(asw)

tips：
Python join() 方法用于将序列中的元素以指定的字符连接生成一个新的字符串。
附：ASCII码表
2019/4/22 subject: 2.Add two numbers
solution:

# # @lc app=leetcode id=2 lang=python3 # # [2] Add Two Numbers # # https://leetcode.com/problems/add-two-numbers/description/ # # algorithms # Medium (30.92%) # Total Accepted:831.3K # Total Submissions: 2.7M # Testcase Example:'[2,4,3]\n[5,6,4]' # # 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. # # # # Definition for singly-linked list. # class ListNode: #def __init__(self, x): #self.val = x #self.next = Noneclass Solution: def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode: carry = 0 root = n = ListNode(0) while l1 or l2 or carry: v1 = v2 = 0 if l1: v1 = l1.val l1 = l1.next if l2: v2 = l2.val l2 = l2.next carry, val = divmod(v1+v2+carry, 10) n.next = ListNode(val) n = n.next return root.next

【LeetCode刷题笔记】tips:
这道题涉及到Python数据结构之链表（linked list）

root的作用：
文章图片

2019/4/23 subject: [5] Longest Palindromic Substring
solution:

# # @lc app=leetcode id=5 lang=python3 # # [5] Longest Palindromic Substring # # https://leetcode.com/problems/longest-palindromic-substring/description/ # # algorithms # Medium (27.00%) # Total Accepted:528.9K # Total Submissions: 2M # Testcase Example:'"babad"' # # Given a string s, find the longest palindromic substring in s. You may assume # that the maximum length of s is 1000. # # Example 1: # # # Input: "babad" # Output: "bab" # Note: "aba" is also a valid answer. # # # Example 2: # # # Input: "cbbd" # Output: "bb" # # #class Solution: def longestPalindrome(self, s): res = "" for i in range(len(s)): # odd case, like "aba" tmp = self.helper(s, i, i) if len(tmp) > len(res): res = tmp # even case, like "abba" tmp = self.helper(s, i, i+1) if len(tmp) > len(res): res = tmp return res# get the longest palindrome, l, r are the middle indexes # from inner to outerdef helper(self, s, l, r): while l >= 0 and r < len(s) and s[l] == s[r]: l -= 1 r += 1 return s[l+1:r]

tips:
这道题主要是需要理解palindromic的格式，即共有“a" "aa" "aba" 三种形式。另外可以学习到的是在solution类中再编写辅助函数调用的思想。
helper中的思想也值得注意，l -= 1 r += 1的操作是为了让扫描区域向str两边扩散。