```
Input: intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
Output: Reference of the node with value = 8
Input Explanation: The intersected node's value is 8 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [4,1,8,4,5]. From the head of B, it reads as [5,0,1,8,4,5]. There are 2 nodes before the intersected node in A; There are 3 nodes before the intersected node in B.
```
```
Input: intersectVal = 2, listA = [0,9,1,2,4], listB = [3,2,4], skipA = 3, skipB = 1
Output: Reference of the node with value = 2
Input Explanation: The intersected node's value is 2 (note that this must not be 0 if the two lists intersect). From the head of A, it reads as [0,9,1,2,4]. From the head of B, it reads as [3,2,4]. There are 3 nodes before the intersected node in A; There are 1 node before the intersected node in B.
```
```
Input: intersectVal = 0, listA = [2,6,4], listB = [1,5], skipA = 3, skipB = 2
Output: null
Input Explanation: From the head of A, it reads as [2,6,4]. From the head of B, it reads as [1,5]. Since the two lists do not intersect, intersectVal must be 0, while skipA and skipB can be arbitrary values.
Explanation: The two lists do not intersect, so return null.
```
**Notes:**
- If the two linked lists have no intersection at all, return `null`.
- The linked lists must retain their original structure after the function returns.
- You may assume there are no cycles anywhere in the entire linked structure.
- Your code should preferably run in O(n) time and use only O(1) memory.
```python
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
if not headA or not headB:
return None
a = headA
b = headB
while(headA!=headB):
headA = headA.next if headA.next else b
headB = headB.next if headB.next else a
return headA
```
```python
class Solution:
def getIntersectionNode(self, headA: ListNode, headB: ListNode) -> ListNode:
if not headA or not headB:
return None
a = headA
b = headB
while(headA!=headB):
headA = not headA and b or headA.next
headB = not headB and a or headB.next
return headA
```
Given a char array representing tasks CPU need to do. It contains capital letters A to Z where different letters represent different tasks. Tasks could be done without original order. Each task could be done in one interval. For each interval, CPU could finish one task or just be idle.
However, there is a non-negative cooling interval **n** that means between two **same tasks**, there must be at least n intervals that CPU are doing different tasks or just be idle.
You need to return the **least** number of intervals the CPU will take to finish all the given tasks.
**Example:**
```
Input: tasks = ["A","A","A","B","B","B"], n = 2
Output: 8
Explanation: A -> B -> idle -> A -> B -> idle -> A -> B.
```
**Note:**
1. The number of tasks is in the range [1, 10000].
2. The integer n is in the range [0, 100].
```python
class Solution:
def leastInterval(self, tasks: List[str], n: int) -> int:
if n == 0:
return len(tasks)
hm = {}
t = 0
for task in tasks:
hm[task] = hm.get(task, 0) + 1
t = max(t, hm[task])
print(hm)
counts = sorted(hm.values(), reverse=True)
ret = 0
while counts:
if len(counts) - 1 >= n:
t = counts.pop(-1)
ret += t * (len(counts))
_counts = []
for i in range(len(counts)):
counts[i] -= t
if counts[i] > 0:
_counts.append(counts[i])
counts = _counts
else:
i = 0
while i < len(counts) - 1:
if counts[i] == counts[i + 1]:
i = i + 1
else:
break
ret += (counts[0] - 1) * (n + 1) + i + 1
break
return ret
```
def popTask(self):
while self.pq:
priority, count, task = heapq.heappop(self.pq)
if task is not REMOVED:
self.size -= 1
del self.entryFinder[task]
return task, priority
raise KeyError("pop from an empty priority queue")
def findMin(self):
while self.pq:
if self.pq[0][-1] == REMOVED:
heapq.heappop(self.pq)
else:
return self.pq[0][-1], self.pq[0][0]
raise KeyError("The priority queue is empty")
```
Input: events = [[1,2],[2,3],[3,4]]
Output: 3
Explanation: You can attend all the three events.
One way to attend them all is as shown.
Attend the first event on day 1.
Attend the second event on day 2.
Attend the third event on day 3.
```
Greedy. Intuitively, make events which have ealier endtime to end earlier.
Use priority queue `pq` to store avaliable events in current day `d`. With time proceeding, choose the event with highest priority to attend. Meanwhile, some events in `pq` should be removed out because of unavaliable( `endtime < d`).
1. iterate on days value range
```python
class Solution(object):
def maxEvents(self, events):
"""
:type events: List[List[int]]
:rtype: int
"""
events.sort(key=lambda x: (x[0], x[1]))
heap = []
i, res = 0, 0
for day in range(100005):
while heap and heap[0] < day:
heapq.heappop(heap)
while i < len(events) and events[i][0] == day:
heapq.heappush(heap, events[i][1])
i += 1
if heap:
heapq.heappop(heap)
res += 1
return res
```
2. move to next valid `d`, do add avaliable, attend and at last remove all unavaliable events in one loop. Faster!
```python
def maxEvents(self, events):
events.sort()
pq = []
i, d, res = 0,0,0
while(pq or i<len(events)):
if not pq:
d = events[i][0]
while(i<len(events) and events[i][0]==d):
heapq.heappush(pq,events[i][1])
i+=1
heapq.heappop(pq)
d += 1
res += 1
while(pq and pq[0]<d):
heapq.heappop(pq)
return res
```
Given an array `nums`, write a function to move all `0`'s to the end of it while maintaining the relative order of the non-zero elements.
**Example:**
```
Input: [0,1,0,3,12]
Output: [1,3,12,0,0]
```
**Note**:
1. You must do this **in-place** without making a copy of the array.
2. Minimize the total number of operations.
-----
### Solution
1. brute force
```python
def moveZeroes(self, nums: List[int]) -> None:
"""
Do not return anything, modify nums in-place instead.
"""
n = len(nums)
def helper(i, nums):
if nums[i]!=0:
return
j = i
while(j<n):
if nums[j]!=0:
nums[i], nums[j] = nums[j], nums[i]
return
j = j+1
for i in range(n):
helper(i, nums)
return nums
```
2. two pointers. slow for zero idx. elements between slow and i are all 0.
```python
class Solution:
def moveZeroes(self, nums):
slow = 0
for i in range(len(nums)):
if nums[i]!=0:
nums[i], nums[slow] = nums[slow],nums[i]
slow += 1
return nums
- You may assume that all inputs are consist of lowercase letters `a-z`.
- All inputs are guaranteed to be non-empty strings.
---
### Solution
Easy :-P
```python
class Trie:
def __init__(self):
"""
Initialize your data structure here.
"""
self.root = {}
def insert(self, word: str) -> None:
"""
Inserts a word into the trie.
"""
curr = self.root
for w in word:
if w not in curr:
curr[w] = {}
curr = curr[w]
curr["end"] = True
def search(self, word: str) -> bool:
"""
Returns if the word is in the trie.
"""
curr = self.root
for w in word:
if w not in curr:
return False
curr = curr[w]
return "end" in curr
def startsWith(self, prefix: str) -> bool:
"""
Returns if there is any word in the trie that starts with the given prefix.
"""
curr = self.root
for w in prefix:
if w not in curr:
return False
curr = curr[w]
return True
```
```python
class Solution:
def searchMatrix(self, matrix, target):
"""
:type matrix: List[List[int]]
:type target: int
:rtype: bool
"""
def helper(a, l, r, target):
while(l<r):
mid = (l+r)//2
if a[mid]<target:
l = mid+1
else:
r = mid
return l
m = len(matrix)
# For case: [],0
if m==0:
return False
n = len(matrix[0])
# For case: [[]],1
if n==0:
return False
a = [row[0] for row in matrix]
k = helper(a, 0, m, target)
# For case: [[1]], 1
if k<m and matrix[k][0]==target:
return True
for i in range(k):
row = matrix[i]
if row[-1]<target:
continue
t = helper(row, 0, n, target)
if row[t]==target:
return True
return False
```
```python
def searchMatrix(self, matrix, target ):
if not matrix or not matrix[0]:
return False
m = len(matrix)
n = len(matrix[0])
i,j = m-1, 0
while(i>=0 and j<n):
if matrix[i][j]<target:
j = j+1
elif matrix[i][j]>target:
i = i-1
else:
return True
return False
```
Given a singly linked list, determine if it is a palindrome.
**Example 1:**
```
Input: 1->2
Output: false
```
**Example 2:**
```
Input: 1->2->2->1
Output: true
```
**Follow up:**
Could you do it in O(n) time and O(1) space?
---
### Solution
1. 链表长度为偶数就中间添个dummy，然后翻转后半部分链表，再从首尾开始遍历(Add a dummy node in middle of linked list if its length is even. Reverse the second half of the linked list, and then iterate from tail and head)。这不是easy的解法吧？
```python
class Solution:
def isPalindrome(self, head: ListNode) -> bool:
if not head:
return True
slow, fast = head, head.next
while(fast and fast.next):
slow = slow.next
fast = fast.next.next
if fast:
dummy = ListNode("dummy")
dummy.next = slow.next
slow.next = dummy
mid = dummy
else:
mid = slow
tail = self.reverse(mid)
while(tail!=head):
if tail.val!=head.val:
return False
tail = tail.next
head = head.next
return True
def reverse(self, head):
pre,curr = None,head
while(curr.next):
tmp = curr.next
curr.next = pre
pre = curr
curr = tmp
curr.next = pre
return curr
```
```python
def numSquares(self, n: int) -> int:
m = int(math.sqrt(n))
nums = [i*i for i in range(1, m+1)]
dp = [float("inf") for i in range(n+1)]
dp[0] = 0
for i in range(1, n+1):
for num in nums:
if i>=num:
dp[i] = min(dp[i], dp[i-num]+1)
return dp[-1]
```
2. 看到别人用了静态dp，就是在类里存储了dp结果。有点作弊的感觉...
```python
class Solution(object):
_dp = [0]
def numSquares(self, n):
dp = self._dp
while len(dp) <= n:
dp += min(dp[-i*i] for i in range(1, int(len(dp)**0.5+1))) + 1,
return dp[n]
```
3. bfs。这个要注意限制当前层次的待搜索节点数
```python
def numSquares(self, n):
nums = []
vis = [0 for i in range(n+1)]
# 注意用set，不然会多出很多重复的待搜索节点
q = set([(0,0)])
vis[0] = 1
for i in range(1, int(n**0.5)+1):
nums.append(i*i)
while(q):
_q = set()
for curr, depth in q:
for num in nums:
if curr+num == n:
return depth +1
elif curr+num <n:
_q.add((curr+num, depth+1))
else:
break
q = _q
```
```python
class Solution:
def maxSubArray(self, nums: List[int]) -> int:
n = len(nums)
dp = [0 for i in range(n+1)]
res = nums[0]
for i in range(1, n+1):
dp[i] = max(nums[i-1], dp[i-1]+nums[i-1])
res = max(res, dp[i])
return res
```
楼主: Zheyuuu
狗仔卡
楼主
