diko
BAN USERAt index i, we have to choose to extend the subarray or drop it.
When we drop it, the new subarray doesn't start from i but i-k+1,
and to make a decision (extend/drop) we have to compare between
- current_max_subarray_sum_ends_at_i (current_max + nums[i])
- and last_k_sum(from i-k+1 to i)
To achieve O(N), we should keep track of last_k_sum values (current_ksum)
and we can compute new current_ksum by: current_ksum - nums[i-k] + nums[i]
def find_max_subarray(nums, k):
if not nums: return
len_nums = len(nums)
if len_nums < k: return
if len_nums == k: return sum(nums), 0, len_nums-1
current_max = sum(nums[:k])
current_ksum = sum(nums[:k])
current_start = 0
max_sum = current_max
max_start = 0
max_end = 1
for i in range(k, len_nums):
current_ksum = current_ksum - nums[i-k] + nums[i]
if current_max + nums[i] > current_ksum: # extends
current_max = current_max + nums[i]
else: # drop, but we have to maintain the window size k
current_max = current_ksum
current_start = i-k+1
if current_max > max_sum:
max_sum = current_max
max_start = current_start
max_end = i
return max_sum, max_start, max_end
if __name__ == '__main__':
nums1 = [-4, -2, 1, -3]
nums2 = [1, 1, 1, 1, 1, 1]
print(find_max_subarray(nums1, 2))
print(find_max_subarray(nums2, 3))
I think we can use the ‘negation’ technique here, because the elements in the list are all value of 0 to n-1,
we can use the element value as the ‘index or key’ of some other meaning (by inverting the value of the index into negative).
But usually we can use the negation when the value is more than 0 (because there is no +0 or -0).
So, I’m going to modify the list value by +1. (and we should do it in one pass.) when I invert the value.
The time would be O(n) and it ends in one pass.
The code (Python) will be as follows:
def find_repeat(nums):
if not nums: return
for i in range(len(nums)):
index = -1
if nums[i] >= 0:
index = nums[i]
else:
index = abs(nums[i]) -1
if nums[index] >= 0:
nums[index] = -1*(nums[index] +1)
else:
# duplicates!
print(index, end=" ")
print("")
if __name__ == '__main__':
nums1 = [4, 2, 0, 5, 2, 0, 1]
nums2 = [1, 2, 3, 0, 0, 1, 3, 6, 6, 6]
find_repeat(nums1) # 0 2
find_repeat(nums2) # 0 1 3 6 6
Consider string s consists of 'character-command’ pairs:
For example, ‘a?b:c’ -> a,b,c are characters and ?,: are commands
and the sequences are ‘a?’, ‘b:’,’c:’ (the end of string is assumed as ‘:’ to make the process consistent)
we maintain two stacks: node_stack and leaf_stack.
- For command ‘?’: make a node and push to the node_stack
- For command ‘:’ : it differs whether it is the first(odd) or the second(even)
- if it is the first: make a node and push to the leaf_stack
- if it is the second:
pop a node from the node_stack and,
node.right = new node from the current character
node.left = a leaf node popped from the leaf_stack
push back the node to the leaf_stack
- After the end of the string expression clean up the residuals (if any in node_stack)
- pop a node from the node_stack
- set node.left and node.right from leaf_stack
- push back the node to the leaf_stack
- Finally, the (only one) first node of the leaf_stack is the result tree.
My code is as follows
- build is the main logic
- print_level is for testing: to print the tree by level-order
- diko June 05, 2017