# Weekly #8
@Date : 2019-05-19 16:21:49
@Author : Lewis Tian (taseikyo@gmail.com)
@Link : https://taseikyo.github.io
@Range : 2019/05/20 - 2019/05/26
Table of Contents
algorithm
1046. Last Stone Weight
We have a collection of rocks, each rock has a positive integer weight.
Each turn, we choose the two heaviest rocks and smash them together. Suppose the stones have weights x and y with x <= y. The result of this smash is:
If x == y, both stones are totally destroyed; If x != y, the stone of weight x is totally destroyed, and the stone of weight y has new weight y-x. At the end, there is at most 1 stone left. Return the weight of this stone (or 0 if there are no stones left.)
Example 1:
Input: [2,7,4,1,8,1]
Output: 1
Explanation:
We combine 7 and 8 to get 1 so the array converts to [2,4,1,1,1] then,
we combine 2 and 4 to get 2 so the array converts to [2,1,1,1] then,
we combine 2 and 1 to get 1 so the array converts to [1,1,1] then,
we combine 1 and 1 to get 0 so the array converts to [1] then that's the value of last stone.
Note:
- 1 <= stones.length <= 30
- 1 <= stones[i] <= 1000
solution
When stones[0] is equal to stones[1], sorting the remaining arrays is unnecessary because they are in order. Surprisingly, the time will be longer after deleting the useless sorting step. Why?
class Solution:
def lastStoneWeight(self, stones: List[int]) -> int:
'''36 ms 13.3 MB'''
def func(stones):
if len(stones) < 2:
return stones[0] if len(stones) == 1 else 0
if stones[0] == stones[1]:
return func(stones[2:]) # here
else:
stones[1] = stones[0] - stones[1]
return func(sorted(stones[1:], reverse=True))
return func(sorted(stones, reverse=True))
def lastStoneWeight(self, stones: List[int]) -> int:
'''28 ms 13.2 MB'''
def func(stones):
if len(stones) < 2:
return stones[0] if len(stones) == 1 else 0
if stones[0] == stones[1]:
return func(sorted(stones[2:], reverse=True))
else:
stones[1] = stones[0] - stones[1]
return func(sorted(stones[1:], reverse=True))
return func(sorted(stones, reverse=True))
500. Keyboard Row
Given a List of words, return the words that can be typed using letters of alphabet on only one row's of American keyboard like the image below.
Example:
Input: ["Hello", "Alaska", "Dad", "Peace"]
Output: ["Alaska", "Dad"]
Note:
- You may use one character in the keyboard more than once.
- You may assume the input string will only contain letters of alphabet.
solution
There is a awesome solution:
class Solution:
def findWords(self, words: List[str]) -> List[str]:
'''36 ms 13 MB'''
rows = [set("qwertyuiop"),set("asdfghjkl"),set("zxcvbnm")]
return [w for w in words if any(s&set(w.lower())==set(w.lower()) for s in rows)]
1038. Binary Search Tree to Greater Sum Tree
Given the root of a binary search tree with distinct values, modify it so that every node has a new value equal to the sum of the values of the original tree that are greater than or equal to node.val.
As a reminder, a binary search tree is a tree that satisfies these constraints:
The left subtree of a node contains only nodes with keys less than the node's key. The right subtree of a node contains only nodes with keys greater than the node's key. Both the left and right subtrees must also be binary search trees.
Example 1:
Input: [4,1,6,0,2,5,7,null,null,null,3,null,null,null,8]
Output: [30,36,21,36,35,26,15,null,null,null,33,null,null,null,8]
Note:
- The number of nodes in the tree is between 1 and 100.
- Each node will have value between 0 and 100.
- The given tree is a binary search tree.
solution
This is a variant of the preorder traversal, that is, visiting the right node first.
589. N-ary Tree Preorder Traversal
Given an n-ary tree, return the preorder traversal of its nodes' values.
For example, given a 3-ary tree:
Return its preorder traversal as: [1,3,5,6,2,4].
Note:
- Recursive solution is trivial, could you do it iteratively?
solution
My solution is quite stupid where I use a dict to record the current children index that should be visited.
And there is a more clever solution:
def preorder(self, root: 'Node') -> List[int]:
'''96 ms 17.6 MB'''
stack = [root]
ans = []
while stack:
cur = stack.pop(0)
if cur:
ans.append(cur.val)
if cur.children:
stack = cur.children + stack
return ans
965. Univalued Binary Tree
A binary tree is univalued if every node in the tree has the same value.
Return true if and only if the given tree is univalued.
Example 1:
Input: [1,1,1,1,1,null,1]
Output: true
Example 2:
Input: [2,2,2,5,2]
Output: false
Note:
- The number of nodes in the given tree will be in the range [1, 100].
- Each node's value will be an integer in the range [0, 99].
solution
700. Search in a Binary Search Tree
Given the root node of a binary search tree (BST) and a value. You need to find the node in the BST that the node's value equals the given value. Return the subtree rooted with that node. If such node doesn't exist, you should return NULL.
For example,
Given the tree:
4
/ \
2 7
/ \
1 3
And the value to search: 2
You should return this subtree:
2
/ \
1 3
In the example above, if we want to search the value 5, since there is no node with value 5, we should return NULL.
Note that an empty tree is represented by NULL, therefore you would see the expected output (serialized tree format) as [], not null.
solution
872. Leaf-Similar Trees
Consider all the leaves of a binary tree. From left to right order, the values of those leaves form a leaf value sequence.
For example, in the given tree above, the leaf value sequence is (6, 7, 4, 9, 8).
Two binary trees are considered leaf-similar if their leaf value sequence is the same.
Return true if and only if the two given trees with head nodes root1 and root2 are leaf-similar.
Note:
- Both of the given trees will have between 1 and 100 nodes.
solution
review
This article is quite interesting. There is a response which is what I want to say.
You named this “Don’t use a VPN at home” and then say that you do use one at home, for what… so you can avoid using it? This is more of a confession of buyers remorse/improper configuration.
The take away should be, VPN’s aren’t useful at the device level. If you want privacy, setup a VPN at the network level (Router or firewall) with proper equipment. Home consumer solutions are not yet available.
Privacy takes effort and is not guaranteed by any contract or service in 2019.
tip
This week I read some tutorials about CMake:
share
- [ICS'17] Hardware/Software Cooperative Caching for HybridDRAM/NVM Memory Architectures
This paper proposes a hardware/software cooperative caching mechanism named HSCC, which organizes NVM and DRAM in a flat address space while logically utilizing DRAM as a cache to NVM.
The proposed DRAM/NVM hybrid memory architecture can significantly simplify the hardware design and push DRAM cache management to the software layers.
Authors propose utility-based cache filtering policies to improve the efficiency of DRAM cache. Extensive simulations show that HSCC improves system performance and energy efficiency significantly compared to a hardware-assisted DRAM/NVM memory system , and also achieves higher performance than flat-addressable DRAM/NVM memory systems and a RBLA caching policy.