views 1437 words

# Diffculty: Medium

## 334. Increasing Triplet Subsequence

Topic:

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Note: Your algorithm should run in O(n) time complexity and O(1) space complexity.

Example 1:

Input: [1,2,3,4,5]
Output: true

Example 2:

Input: [5,4,3,2,1]
Output: false

### Approach1

def increasingTriplet(nums: List[int]) -> bool:
r1, r2 = sys.maxsize, sys.maxsize
for n in nums :
if n <= r1 : r1 = n
elif n <= r2 : r2 = n
else : return True
return False

# ============= 不同写法 ===============

min_num,sec_num = float('inf'),float('inf')  # 初始化最小值，次小值

for i in nums:
min_num = min(i,min_num)                 # 维护min_num为最小值
if i > min_num:                          # 找到了次小值
sec_num = min(i,sec_num)
if i > sec_num:                          # 找到了第三大的数
return True

return False

## 341. Flatten Nested List Iterator

Topic: Stack, Design

Given a nested list of integers, implement an iterator to flatten it.

Each element is either an integer, or a list – whose elements may also be integers or other lists.

Example 1:

Input: [[1,1],2,[1,1]]
Output: [1,1,2,1,1]
Explanation: By calling next repeatedly until hasNext returns false,
the order of elements returned by next should be: [1,1,2,1,1].

Example 2:

Input: [1,[4,[6]]]
Output: [1,4,6]
Explanation: By calling next repeatedly until hasNext returns false,
the order of elements returned by next should be: [1,4,6].

### Approach1

# """
# This is the interface that allows for creating nested lists.
# You should not implement it, or speculate about its implementation
# """
#class NestedInteger:
#    def isInteger(self) -> bool:
#        """
#        @return True if this NestedInteger holds a single integer, rather than a nested list.
#        """
#
#    def getInteger(self) -> int:
#        """
#        @return the single integer that this NestedInteger holds, if it holds a single integer
#        Return None if this NestedInteger holds a nested list
#        """
#
#    def getList(self) -> [NestedInteger]:
#        """
#        @return the nested list that this NestedInteger holds, if it holds a nested list
#        Return None if this NestedInteger holds a single integer
#        """

class NestedIterator:
def __init__(nestedList: [NestedInteger]):
### 栈结构是从右到左, 但是遍历是从左到右, 所以需要反转再压栈
self.stack = nestedList[::-1]

def next(self) -> int:
### 由于hasNext()已经确保在栈顶的一定是integer, 所以可以直接出栈
return self.stack.pop().getInteger()

def hasNext(self) -> bool:
### 当栈的长度大于0和栈的下一个为List时, 就把该list添加到栈中 (同样需要反转才能入栈)
while len(self.stack)>0 and not self.stack[-1].isInteger():
self.stack += self.stack.pop().getList()[::-1]
return len(self.stack) > 0  # 栈长度大于0说明有下一个

# Your NestedIterator object will be instantiated and called as such:
# i, v = NestedIterator(nestedList), []
# while i.hasNext(): v.append(i.next())

### Approach2

class NestedIterator(object):
def __init__(self, nestedList):
"""
:type nestedList: List[NestedInteger]
"""
def build_generator(nestedList):
for i in nestedList:
if i.isInteger():
yield i.getInteger()
else:
i = i.getList()
for j in build_generator(i):
yield j
self.g = build_generator(nestedList)

def next(self):
"""
:rtype: int
"""
#print(self.v)
return self.v

def hasNext(self):
"""
:rtype: bool
"""
try:
self.v = next(self.g)
#print(self.v)
return True
except:
return False

## 347. Top K Frequent Elements

Topic: Heap, Hash Table

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

Note:

• You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
• Your algorithm’s time complexity must be better than O(n log n), where n is the array’s size.
• It’s guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique.
• You can return the answer in any order.

### Approach1

def topKFrequent(nums: List[int], k: int) -> List[int]:
import random
from collections import Counter

lookup = Counter(nums)
nums = [(freq, num) for num, freq in lookup.items()]
random.seed(42)
# 返回的是最大的前k个元组
kths =  self.findKth(nums, k, 0, len(nums)-1)
# print(kths)
return [num for (freq, num) in kths]

# 找到第k大的数所在的位置，返回nums中k及其前面全部的元素；时间复杂度O(n)
def findKth(self, nums, k, low, high) :
import random
if low >= high : return nums[:low+1]
pivot = random.randint(low, high)
nums[low], nums[pivot] = nums[pivot], nums[low]
base = nums[low][0]
i = low
for j in range(low+1, high+1) :
if nums[j][0] > base :
nums[j], nums[i+1] = nums[i+1], nums[j]
i += 1
nums[low], nums[i] = nums[i], nums[low]
if i == k-1 :
return nums[:i+1]
elif i > k - 1 :
return self.findKth(nums, k, low, i-1)
else :
return self.findKth(nums, k, i+1, high)

### Approach2

def topKFrequent(nums: List[int], k: int) -> List[int]:
from collections import Counter
lookup = Counter(nums)
# return [num for num, freq in lookup.most_common(k)]
print(lookup) # Counter({1: 3, 2: 2, 3: 1})
print(lookup.most_common(1)) # [(1, 3)]
print(lookup.most_common(2)) # [(1, 3), (2, 2)]
return [item[0] for item in lookup.most_common(k)]

### Approach3

def topKFrequent(nums: List[int], k: int) -> List[int]:
from collections import Counter
import heapq
count = Counter(nums)
return heapq.nlargest(k, count.keys(), key=count.get)

## 348. Design Tic-Tac-Toe

Topic:

Design a Tic-tac-toe game that is played between two players on a n x n grid.

You may assume the following rules: 1. A move is guaranteed to be valid and is placed on an empty block. 2. Once a winning condition is reached, no more moves is allowed. 3. A player who succeeds in placing n of their marks in a horizontal, vertical, or diagonal row wins the game.

Example:

Given n = 3, assume that player 1 is "X" and player 2 is "O" in the board.

TicTacToe toe = new TicTacToe(3);

toe.move(0, 0, 1); -> Returns 0 (no one wins)
|X| | |
| | | |    // Player 1 makes a move at (0, 0).
| | | |

toe.move(0, 2, 2); -> Returns 0 (no one wins)
|X| |O|
| | | |    // Player 2 makes a move at (0, 2).
| | | |

toe.move(2, 2, 1); -> Returns 0 (no one wins)
|X| |O|
| | | |    // Player 1 makes a move at (2, 2).
| | |X|

toe.move(1, 1, 2); -> Returns 0 (no one wins)
|X| |O|
| |O| |    // Player 2 makes a move at (1, 1).
| | |X|

toe.move(2, 0, 1); -> Returns 0 (no one wins)
|X| |O|
| |O| |    // Player 1 makes a move at (2, 0).
|X| |X|

toe.move(1, 0, 2); -> Returns 0 (no one wins)
|X| |O|
|O|O| |    // Player 2 makes a move at (1, 0).
|X| |X|

toe.move(2, 1, 1); -> Returns 1 (player 1 wins)
|X| |O|
|O|O| |    // Player 1 makes a move at (2, 1).
|X|X|X|

Follow up: Could you do better than O(n2) permove()operation?

### Approach1

class TicTacToe(object):
def __init__(self, n):
"""
:type n: int
"""
self.n = n
self.rowMoveCount1 = [0] * n # maps k to how many pos in row k are occupied by player 1
self.rowMoveCount2 = [0] * n # maps k to how many pos in row k are occupied by player 2
self.colMoveCount1 = [0] * n # maps k to how many pos in col k are occupied by player 1
self.colMoveCount2 = [0] * n # maps k to how many pos in col k are occupied by player 2
self.mainDiagMoveCount1 = [0] # how many pos in main diag (row==col) are occupied by player 1
self.mainDiagMoveCount2 = [0] # how many pos in main diag (row==col) are occupied by player 2
self.antiDiagMoveCount1 = [0] # how many pos in anti diag (row+col==n-1) are occupied by player 1
self.antiDiagMoveCount2 = [0] # how many pos in anti diag (row+col==n-1) are occupied by player 2

def move(self, row, col, player):
"""
Player {player} makes a move at ({row}, {col}).
@param row The row of the board.
@param col The column of the board.
@param player The player, can be either 1 or 2.
@return The current winning condition, can be either:
0: No one wins.
1: Player 1 wins.
2: Player 2 wins.
:type row: int
:type col: int
:type player: int
:rtype: int
"""
assert player==1 or player==2

rowCountList = self.rowMoveCount1 if player==1 else self.rowMoveCount2
colCountList = self.colMoveCount1 if player==1 else self.colMoveCount2
mainDiagCountList = self.mainDiagMoveCount1 if player==1 else self.mainDiagMoveCount2
antiDiagCountList = self.antiDiagMoveCount1 if player==1 else self.antiDiagMoveCount2

rowCountList[row] += 1
colCountList[col] += 1
if row == col:
mainDiagCountList[0] += 1
if row + col == self.n - 1:
antiDiagCountList[0] += 1

if self.n in [ rowCountList[row], colCountList[col], mainDiagCountList[0], antiDiagCountList[0] ]:
return player
else:
return 0

# Your TicTacToe object will be instantiated and called as such:
# obj = TicTacToe(n)
# param_1 = obj.move(row,col,player)