不想写第二遍的刷题笔记

世界级打野都是rush大龙的

Factorial Trailing Zeroes

LeetCode

Given an integer n, return the number of trailing zeroes in n!.

Example 1:

Input: 3
Output: 0
Explanation: 3! = 6, no trailing zero.

Example 2:

Input: 5
Output: 1
Explanation: 5! = 120, one trailing zero.

Note: Your solution should be in logarithmic time complexity.

Solution

class Solution(object):
def trailingZeroes(self, n):
"""
:type n: int
:rtype: int
"""
res = 0
while n>=5:
res += n/5
n /= 5
return res

3Sum

LeetCode 15

Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.

Note:

The solution set must not contain duplicate triplets.

Example:

Given array nums = [-1, 0, 1, 2, -1, -4],

A solution set is:
[
[-1, 0, 1],
[-1, -1, 2]
]

Solution

class Solution(object):
def threeSum(self, nums):
"""
:type nums: List[int]
:rtype: List[List[int]]
"""
result = []
nums.sort()
for i in range(0, len(nums)-2):
if i>0 and nums[i]==nums[i-1]:
continue
j, k = i+1, len(nums)-1
while j<k:
s = nums[i] + nums[j] + nums[k]
if s<0:
j += 1
elif s>0:
k -= 1
else:
result.append([nums[i], nums[j], nums[k]])
while j<k and nums[j]==nums[j+1]:
j+=1
while j<k and nums[k-1] == nums[k]:
k-=1
j += 1
k -= 1
return result

Valid Palindrome

LeetCode 125

Given a string, determine if it is a palindrome, considering only alphanumeric characters and ignoring cases.

Note: For the purpose of this problem, we define empty string as valid palindrome.

Example 1:

Input: "A man, a plan, a canal: Panama"
Output: true

Example 2:

Input: "race a car"
Output: false

Solution

class Solution(object):
def isPalindrome(self, s):
"""
:type s: str
:rtype: bool
"""
new_s = ""
for i in s:
if i.isalpha() or i.isdigit():
new_s += i
new_s = new_s.lower()
print(new_s)
if new_s[::-1] == new_s:
return True
else:
return False

Duplicate Emails

LeetCode 182

Write a SQL query to find all duplicate emails in a table named Person.

+----+---------+
| Id | Email |
+----+---------+
| 1 | a@b.com |
| 2 | c@d.com |
| 3 | a@b.com |
+----+---------+

For example, your query should return the following for the above table:

+---------+
| Email |
+---------+
| a@b.com |
+---------+

Note: All emails are in lowercase.

Solution

select Email from Person group by Email having count(Email) > 1

Delete Duplicate Emails

LeetCode 196

Write a SQL query to delete all duplicate email entries in a table named Person, keeping only unique emails based on its smallest Id.

+----+------------------+
| Id | Email |
+----+------------------+
| 1 | john@example.com |
| 2 | bob@example.com |
| 3 | john@example.com |
+----+------------------+
Id is the primary key column for this table.

For example, after running your query, the above Person table should have the following rows:

+----+------------------+
| Id | Email |
+----+------------------+
| 1 | john@example.com |
| 2 | bob@example.com |
+----+------------------+

Note:

Your output is the whole Person table after executing your sql. Use delete statement.

Solution

delete from Person
where Email in
(select * from
(select Email from Person group by Email having count(Email) > 1) a)
and Id not in
(select * from
(select min(Id) from Person group by Email having count(Email) > 1) b)

Linked List Cycle

LeetCode 141

Given a linked list, determine if it has a cycle in it.

To represent a cycle in the given linked list, we use an integer pos which represents the position (0-indexed) in the linked list where tail connects to. If pos is -1, then there is no cycle in the linked list.

Example 1:

Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the second node.

Example 2:

Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where tail connects to the first node.

Example 3:

Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.

Follow up:

Can you solve it using O(1) (i.e. constant) memory?

Solution

双指针

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

class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
if not head:
return False
pre = nxt = head
while pre.next and nxt.next and nxt.next.next:
pre = pre.next
nxt = nxt.next.next
if pre==nxt:
return True
return False

Pascal's Triangle II

LeetCode 119

Given a non-negative index k where k ≤ 33, return the kth index row of the Pascal’s triangle.

Note that the row index starts from 0.

In Pascal’s triangle, each number is the sum of the two numbers directly above it.

Example:

Input: 3
Output: [1,3,3,1]

Follow up:

Could you optimize your algorithm to use only O(k) extra space?

Solution

class Solution(object):
def getRow(self, rowIndex):
"""
:type rowIndex: int
:rtype: List[int]
"""
row_p = [1]
row = [1]
for i in range(0, rowIndex):
row = [1]
for j in range(0, i):
row.append(row_p[j] + row_p[j+1])
row.append(1)
row_p = row
return row