Weekly #4
@Date : 2019-04-15 09:43:10
@Author : Lewis Tian (taseikyo@gmail.com)
@Link : https://taseikyo.github.io
@Range : 2019/04/15 - 2019/04/21
Photo by sanjiv nayak on Unsplash
Table of Contents
algorithm
28. Implement strStr
Implement strStr().
Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.
Example 1:
Input: haystack = "hello", needle = "ll"
Output: 2
Example 2:
Input: haystack = "aaaaa", needle = "bba"
Output: -1
Clarification:
What should we return when needle is an empty string? This is a great question to ask during an interview.
For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().
Solution
One line in Python using find method, but I don't think it a good solution.
537. Complex Number Multiplication
Given two strings representing two complex numbers.
You need to return a string representing their multiplication. Note i2 = -1 according to the definition.
Example 1:
Input: "1+1i", "1+1i"
Output: "0+2i"
Explanation: (1 + i) * (1 + i) = 1 + i2 + 2 * i = 2i, and you need convert it to the form of 0+2i.
Example 2:
Input: "1+-1i", "1+-1i"
Output: "0+-2i"
Explanation: (1 - i) * (1 - i) = 1 + i2 - 2 * i = -2i, and you need convert it to the form of 0+-2i.
Note:
- The input strings will not have extra blank.
- The input strings will be given in the form of a+bi, where the integer a and b will both belong to the range of [-100, 100]. And the output should be also in this form
Solution
x1, y1 = a[:-1].split('+')
951. Flip Equivalent Binary Trees
For a binary tree T, we can define a flip operation as follows: choose any node, and swap the left and right child subtrees.
A binary tree X is flip equivalent to a binary tree Y if and only if we can make X equal to Y after some number of flip operations.
Write a function that determines whether two binary trees are flip equivalent. The trees are given by root nodes root1 and root2.
Example 1:
Input: root1 = [1,2,3,4,5,6,null,null,null,7,8], root2 = [1,3,2,null,6,4,5,null,null,null,null,8,7]
Output: true
Explanation: We flipped at nodes with values 1, 3, and 5.
Note:
- Each tree will have at most 100 nodes.
- Each value in each tree will be a unique integer in the range [0, 99].
Solution
Recursion:
if root1 is root2:
return True
if not root1 or not root2 or root1.val != root2.val:
return False
return (self.flipEquiv(root1.left, root2.left) and
self.flipEquiv(root1.right, root2.right) or
self.flipEquiv(root1.left, root2.right) and
self.flipEquiv(root1.right, root2.left))
938. Range Sum of BST
Given the root node of a binary search tree, return the sum of values of all nodes with value between L and R (inclusive).
The binary search tree is guaranteed to have unique values.
Example 1:
Input: root = [10,5,15,3,7,null,18], L = 7, R = 15
Output: 32
Example 2:
Input: root = [10,5,15,3,7,13,18,1,null,6], L = 6, R = 10
Output: 23
Note:
- The number of nodes in the tree is at most
10000. - The final answer is guaranteed to be less than
2^31.
Solution
It's quite easy to use recursion:
if not root: return 0
ans = 0
if L <= root.val <= R:
ans += root.val
ans += self.rangeSumBST(root.left, L, R)
ans += self.rangeSumBST(root.right, L, R)
elif root.val < L:
ans += self.rangeSumBST(root.right, L, R)
else:
ans += self.rangeSumBST(root.left, L, R)
return ans
1021. Remove Outermost Parentheses
A valid parentheses string is either empty (""), "(" + A + ")", or A + B, where A and B are valid parentheses strings, and + represents string concatenation. For example, "", "()", "(())()", and "(()(()))" are all valid parentheses strings.
A valid parentheses string S is primitive if it is nonempty, and there does not exist a way to split it into S = A+B, with A and B nonempty valid parentheses strings.
Given a valid parentheses string S, consider its primitive decomposition: S = P_1 + P_2 + https://github.com/taseikyo/arts/blob/master. + P_k, where P_i are primitive valid parentheses strings.
Return S after removing the outermost parentheses of every primitive string in the primitive decomposition of S.
Example 1:
Input: "(()())(())"
Output: "()()()"
Explanation:
The input string is "(()())(())", with primitive decomposition "(()())" + "(())".
After removing outer parentheses of each part, this is "()()" + "()" = "()()()".
Example 2:
Input: "(()())(())(()(()))"
Output: "()()()()(())"
Explanation:
The input string is "(()())(())(()(()))", with primitive decomposition "(()())" + "(())" + "(()(()))".
After removing outer parentheses of each part, this is "()()" + "()" + "()(())" = "()()()()(())".
Example 3:
Input: "()()"
Output: ""
Explanation:
The input string is "()()", with primitive decomposition "()" + "()".
After removing outer parentheses of each part, this is "" + "" = "".
Note:
- S.length <= 10000
- S[i] is "(" or ")"
- S is a valid parentheses string
Solution
I use variable count to determine whether a primitive composition is formed. When count equals 0, the variable j represents current position and i indicates previous position.
count = 0
i = 0
for j, x in enumerate(S):
if x == '(':
count += -1
else:
count += 1
if count == 0:
ret += S[i+1:j]
i = j + 1
return ret
review
- Lambda Functions in C++11 - the Definitive Guide - Alex Allain - cprogramming
- [Markdown] Lambda Functions in C++11 - the Definitive Guide - Alex Allain - cprogramming
The author gave a detailed introduction to the Lambda function. Or say, this is a guide to the anonymous function.
tip
share
- [MACRO'15] Large pages and lightweight memory management in virtualized environments: Can you have it both ways?
This paper observes the fundamental conflict between the address translation benefits of large pages versus the desire for finer-grained monitoring and agile memory management.
This paper proposes a interpolation-based TLB speculation architecture GLUE, boosting hypervisor-based virtualization and containers.
Splintering is a problem and can cause significant performance problems, the proposed GLUE architecture can largely mitigate these issues, thereby making virtualized systems more attractive to deploy.