Hypercube's LeetCode Weekly Contest 48
- Rank: 46 / 2668
- Score: 23 / 23
- Finish Time: 00:50:06
Second Minimum Node In a Binary Tree
Given a non-empty special binary tree consisting of nodes with the non-negative value, where each node in this tree has exactly two or zero sub-node. If the node has two sub-nodes, then this node’s value is the smaller value among its two sub-nodes.
Given such a binary tree, you need to output the second minimum value in the set made of all the nodes’ value in the whole tree.
If no such second minimum value exists, output -1 instead.
Example 1:
Input:
2
/ \
2 5
/ \
5 7
Output: 5
Explanation: The smallest value is 2, the second smallest value is 5.
Example 2:
Input:
2
/ \
2 2
Output: -1
Explanation: The smallest value is 2, but there isn't any second smallest value.
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
def add2set(n, s):
if n:
s.add(n.val)
add2set(n.left, s)
add2set(n.right, s)
class Solution:
def findSecondMinimumValue(self, root):
"""
:type root: TreeNode
:rtype: int
"""
s = set()
add2set(root, s)
try:
s.remove(min(s))
return min(s)
except:
return -1Trim a Binary Search Tree
Given a binary search tree and the lowest and highest boundaries as L and R, trim the tree so that all its elements lies in [L, R] (R >= L). You might need to change the root of the tree, so the result should return the new root of the trimmed binary search tree.
Example 1:
Input:
1
/ \
0 2
L = 1
R = 2
Output:
1
\
2
Example 2:
Input:
3
/ \
0 4
\
2
/
1
L = 1
R = 3
Output:
3
/
2
/
1
# Definition for a binary tree node.
# class TreeNode:
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
def trim(n, l, r):
if not n:
return
if l <= n.val <= r:
n.left = trim(n.left, l, r)
n.right = trim(n.right, l, r)
return n
if n.val < l:
return trim(n.right, l, r)
else:
return trim(n.left, l, r)
class Solution:
def trimBST(self, root, L, R):
"""
:type root: TreeNode
:type L: int
:type R: int
:rtype: TreeNode
"""
return trim(root, L, R)Maximum Swap
Given a non-negative integer, you could swap two digits at most once to get the maximum valued number. Return the maximum valued number you could get.
Example 1:
Input: 2736
Output: 7236
Explanation: Swap the number 2 and the number 7.
Example 2:
Input: 9973
Output: 9973
Explanation: No swap.
Note:
- The given number is in the range [0, 10^8]
def ms(s):
if not s:
return ''
v = max(s)
if s[0] == v:
return s[0] + ms(s[1:])
m = s.rfind(v)
return s[m] + s[1:m] + s[0] + s[m+1:]
class Solution:
def maximumSwap(self, num):
"""
:type num: int
:rtype: int
"""
return int(ms(str(num)))Bulb Switcher II
There is a room with n lights which are turned on initially and 4 buttons on the wall. After performing exactly m unknown operations towards buttons, you need to return how many different kinds of status of the n lights could be.
Suppose n lights are labeled as number [1, 2, 3, …, n], function of these 4 buttons are given below:
- Flip all the lights.
- Flip lights with even numbers.
- Flip lights with odd numbers.
- Flip lights with (3k + 1) numbers, k = 0, 1, 2, …
Example 1:
Input: n = 1, m = 1.
Output: 2
Explanation: Status can be: [on], [off]
Example 2:
Input: n = 2, m = 1.
Output: 3
Explanation: Status can be: [on, off], [off, on], [off, off]
Example 3:
Input: n = 3, m = 1.
Output: 4
Explanation: Status can be: [off, on, off], [on, off, on], [off, off, off], [off, on, on].
Note: n and m both fit in range [0, 1000].
def r1(l):
l = l[:]
try:
l[0] = not l[0]
l[1] = not l[1]
l[2] = not l[2]
l[3] = not l[3]
except:
pass
return l
def r2(l):
l = l[:]
try:
l[1] = not l[1]
l[3] = not l[3]
except:
pass
return l
def r3(l):
l = l[:]
try:
l[0] = not l[0]
l[2] = not l[2]
except:
pass
return l
def r4(l):
l = l[:]
try:
l[0] = not l[0]
l[3] = not l[3]
except:
pass
return l
class Solution:
def flipLights(self, n, m):
"""
:type n: int
:type m: int
:rtype: int
"""
lights = [True, True, True, True][:n]
s = set()
if m%2 == 0:
s.add(tuple(lights))
if m >= 2:
s.add(tuple(r2(r1(lights))))
s.add(tuple(r3(r1(lights))))
s.add(tuple(r4(r1(lights))))
s.add(tuple(r3(r2(lights))))
s.add(tuple(r4(r2(lights))))
s.add(tuple(r4(r3(lights))))
if m >= 4:
s.add(tuple(r4(r3(r2(r1(lights))))))
else:
s.add(tuple(r1(lights)))
s.add(tuple(r2(lights)))
s.add(tuple(r3(lights)))
s.add(tuple(r4(lights)))
if m >= 3:
s.add(tuple(r3(r2(r1(lights)))))
s.add(tuple(r4(r2(r1(lights)))))
s.add(tuple(r4(r3(r1(lights)))))
s.add(tuple(r4(r3(r2(lights)))))
return len(s)