Code 1
Question
Given a string s, find the first non-repeating character in it and return its index. If it does not exist, return -1.
Example 1
Input: s = "leetcode"
Output: 0
Example 2
Input: s = "loveleetcode"
Output: 2
Example 3
Input: s = "aabb"
Output: -1
Answer
- Hash
class Solution(object):
def firstUniqChar(self, s):
"""
:type s: str
:rtype: int
"""
dict={}
for x in s :
dict[x]=dict.get(x,0)+1
for x in s :
if dict[x]==1 :
return s.find(x)
return -1
在第一次遍历时，我们使用哈希映射统计出字符串中每个字符出现的次数。在第二次遍历时，我们只要遍历到了一个只出现一次的字符，那么就返回它的索引，否则在遍历结束后返回 -1。
- 队列
class Solution :
def firstUniqChar(self, s) :
position={}
q=collections.deque()
n=len(s)
for i,ch in enumerate(s) :
if ch not in position :
position[ch]=i
q.append((s[i],i))
else :
position[ch]=-1 #已经出现过了（重复）就设置成-1
while q and position[q[0][0]]==-1 : #弹出队列前面全部不符合的
q.popleft()
return -1 if not q else q[0][1] #如果队列为空返回-1 否则返回第一个
- 我们使用哈希映射，并且使用一个额外的队列，按照顺序存储每一个字符以及它们第一次出现的位置。
- 当我们对字符串进行遍历时，设当前遍历到的字符为 c，如果 c 不在哈希映射中，我们就将 c 与它的索引作为一个二元组放入队尾，否则我们就需要检查队列中的元素是否都满足「只出现一次」的要求，即我们不断地根据哈希映射中存储的值（是否为 ?1）选择弹出队首的元素，直到队首元素「真的」只出现了一次或者队列为空。
- 在遍历完成后，如果队列为空，说明没有不重复的字符，返回 ?1，否则队首的元素即为第一个不重复的字符以及其索引的二元组。
Code 2
Question
Given two stings ransomNote and magazine, return true if ransomNote can be constructed from magazine and false otherwise.
Each letter in magazine can only be used once in ransomNote.
Example 1
Input: ransomNote = "a", magazine = "b"
Output: false
Example 2
Input: ransomNote = "aa", magazine = "ab"
Output: false
Example 3
Input: ransomNote = "aa", magazine = "aab"
Output: true
Answer
- 自己的解法（哈希表）
class Solution(object):
def canConstruct(self, ransomNote, magazine):
"""
:type ransomNote: str
:type magazine: str
:rtype: bool
"""
dict={}
for x in magazine :
dict[x] = dict.get(x, 0) + 1
for x in ransomNote :
if x in dict and dict[x]>0 :
dict[x]=dict.get(x)-1
else :
return False
return True
Code 3
Question
Given two strings s and t, return true if t is an anagram of s, and false otherwise.
Example 1
Input: s = "anagram", t = "nagaram"
Output: true
Example 2
Input: s = "rat", t = "car"
Output: false
Answer
- 哈希表（比上题就多了一个判断）：
class Solution(object):
def isAnagram(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
dict={}
for x in s :
dict[x] = dict.get(x,0) + 1
for x in t :
if x not in dict :
return False
if dict[x]>0 :
dict[x]=dict.get(x)-1
else :
return False
for x in dict :
if dict[x]!=0 :
return False
return True
- 排序
class Solution(object):
def isAnagram(self, s, t):
"""
:type s: str
:type t: str
:rtype: bool
"""
s = list(s)
s.sort()
t=list(t)
t.sort()
if s==t :
return True
else :
return False
如果排序后相同就是相同。
Code 4
Given head, the head of a linked list, determine if the linked list has a cycle in it.
There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to denote the index of the node that tail’s next pointer is connected to. Note that pos is not passed as a parameter.
Return true if there is a cycle in the linked list. Otherwise, return false.
Example 1
Input: head = [3,2,0,-4], pos = 1
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 1st node (0-indexed).
Example 2
Input: head = [1,2], pos = 0
Output: true
Explanation: There is a cycle in the linked list, where the tail connects to the 0th node.
Example 3
Input: head = [1], pos = -1
Output: false
Explanation: There is no cycle in the linked list.
Answer
- 哈希表
自己的解法
# 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
hash={}
while head.next :
hash[head]=hash.get(head,0)+1
if hash[head]==2 :
return True
head=head.next
return False
标准答案（更简洁）
class Solution:
def hasCycle(self, head):
seen = set()
while head:
if head in seen:
return True
seen.add(head)
head = head.next
return False
- 快慢指针法
class Solution(object):
def hasCycle(self, head):
"""
:type head: ListNode
:rtype: bool
"""
if not head or not head.next :
return False
fast=head.next
slow=head
while fast!=slow :
if not fast.next.next or not fast:
return False
else :
slow=slow.next
fast=fast.next.next
return True
我们定义两个指针，一快一满。慢指针每次只移动一步，而快指针每次移动两步。初始时，慢指针在位置 head，而快指针在位置 head.next。这样一来，如果在移动的过程中，快指针反过来追上慢指针，就说明该链表为环形链表。否则快指针将到达链表尾部，该链表不为环形链表。
简单地说，如果相遇，肯定是环形，如果不相遇但走到末尾，就不是环形。
Code 5
Question
Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.
Example 1
Input: head = [1,2,6,3,4,5,6], val = 6
Output: [1,2,3,4,5]
Example 2
Input: head = [], val = 1
Output: []
Example 3
Input: head = [7,7,7,7], val = 7
Output: []
Answer
- 自己的思路（挺乱的）
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def removeElements(self, head, val):
"""
:type head: ListNode
:type val: int
:rtype: ListNode
"""
if not head :
return head
l=head
while l and l.val==val :
l=l.next
while head.next :
if head.next.val==val :
if head.next.next :
head.next=head.next.next
continue
else :
head.next=None
if head.next :
head=head.next
return l
- 标准答案（同思路但更简洁）
class Solution(object):
def removeElements(self, head, val):
"""
:type head: ListNode
:type val: int
:rtype: ListNode
"""
while head and head.val==val :
head=head.next
if not head :
return head
prev=head
while prev.next :
if prev.next.val==val :
prev.next=prev.next.next
else :
prev=prev.next
return head
注意这种方法删除头结点时要更谨慎
- 创建虚拟头节点
# Definition for singly-linked list.
# class ListNode(object):
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution(object):
def removeElements(self, head, val):
"""
:type head: ListNode
:type val: int
:rtype: ListNode
"""
dummy_head=ListNode(val-1,head)
prev = dummy_head
while prev.next:
if prev.next.val == val:
prev.next = prev.next.next
else:
prev = prev.next
return dummy_head.next
注意最后返回的是虚拟节点的下一个而不是头节点,因为prev的操作可能会把head给删掉
例如，样例是[1,1,1,1]，key是1，应该返回[]，但head返回为[1,1,1,1]，dummy_head.next是[]
- 递归法
class Solution(object):
def removeElements(self, head, val):
"""
:type head: ListNode
:type val: int
:rtype: ListNode
"""
if not head :
return head
head.next=self.removeElements(head.next,val)
if head.val==val :
return head.next
else :
return head
对于给定的链表，首先对除了头节点 head \textit{head} head 以外的节点进行删除操作，然后判断 head \textit{head} head 的节点值是否等于给定的 val \textit{val} val。如果 head \textit{head} head 的节点值等于 val \textit{val} val，则 head \textit{head} head 需要被删除，因此删除操作后的头节点为 head \textit{head} head. next \textit{next} next。如果$ \textit{head}$的节点值不等于 val \textit{val} val，则 head \textit{head} head 保留，因此删除操作后的头节点还是 head \textit{head} head。上述过程是一个递归的过程。
