Hi,
My solution is very trivial (almost too trivial that it makes me wonder if I got it right)
return len(s.split())
which is Accepted, but only beats < 2% of other AC submission. I wonder how I can make my code run faster.
Thank you.
Software Engineer @ Amazon
Hi,
My solution is very trivial (almost too trivial that it makes me wonder if I got it right)
return len(s.split())
which is Accepted, but only beats < 2% of other AC submission. I wonder how I can make my code run faster.
Thank you.
@jeantimex said in AC Java Union-Find solution:
int find(int nums[], int i) { if (nums[i] == -1) return i; return find(nums, nums[i]); }
Nice solution, though it is O(n^2) in the worst case. If the find function updates the nums array while looking for the value at the same time, it would be O(n)
def getMinimumDifference(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def visit(node):
if node is None: return
visit(node.left)
if visit.prev is not None:
if visit.diff is None or node.val - visit.prev.val < visit.diff:
visit.diff = node.val - visit.prev.val
visit.prev = node
visit(node.right)
visit.prev = None
visit.diff = None
visit(root)
return visit.diff
w = int(sqrt(area))
while area % w != 0:
w -= 1
return [area / w, w]
The trick is to decrease from the sqrt.
rows = ['qwertyuiopQWERTYUIOP', 'asdfghjklASDFGHJKL', 'zxcvbnmZXCVBNM']
return [word for word in words if any([all([ch in row for ch in word]) for row in rows])]
Following Stefan's style :D
Instead of doing BFS, do recursive call tossing x and y position. I like this because it only take O(log n) space whereas BFS takes O(n) space.
class Solution(object):
def findBottomLeftValue(self, root):
"""
:type root: TreeNode
:rtype: int
"""
def visit(node, x, y):
if node == None: return
if y > visit.y or (y == visit.y and x < visit.x):
visit.x, visit.y, visit.bl = x, y, node.val
visit(node.left, x-1, y+1)
visit(node.right, x+1, y+1)
visit.x, visit.y, visit.bl = 0, 0, root.val
visit(root, 0, 0)
return visit.bl
Hi Stefan,
Thank you for a nice solution.
I am always surprised how you write the most concise solution.
Reading your solution is becoming an art form for me :D
Thank you.
thank you for the nice idea. I learn something new every day :D
@WKVictor nice solution, I tried a similar idea in python but python's heap does not have remove function.
The idea is to mark the beg. / end of consecutive 1's to record the length.
In the second iteration, look for 0's and see if it can bridge 1's at left / right of it.
class Solution(object):
def findMaxConsecutiveOnes(self, nums):
"""
:type nums: List[int]
:rtype: int
"""
longest = 0
i, n = 0, len(nums)
while i < n:
if nums[i] == 1:
l = i
while i < n and nums[i] == 1:
i = i + 1
nums[l], nums[i-1], longest = i - l, i - l, max(longest, i - l)
else:
i += 1
for i in range(n):
if nums[i] == 0:
longest = max(longest, 1 + (nums[i-1] if i > 0 else 0) + (nums[i+1] if i < n-1 else 0))
return longest