Weekly #9
@Date : 2019-05-27 10:19:27
@Author : Lewis Tian (taseikyo@gmail.com)
@Link : https://taseikyo.github.io
@Range : 2019/05/27 - 2019/05/31
Photo by Alexander Ramsey on Unsplash
Table of Contents
algorithm
217. Contains Duplicate
Given an array of integers, find if the array contains any duplicates.
Your function should return true if any value appears at least twice in the array, and it should return false if every element is distinct.
Example 1:
Input: [1,2,3,1]
Output: true
Example 2:
Input: [1,2,3,4]
Output: false
Example 3:
Input: [1,1,1,3,3,4,3,2,4,2]
Output: true
solutioin
It's quite easy in Python. Or sort the array first, then we can find if there are any two consecutive duplicate elements.
def containsDuplicate(self, nums: List[int]) -> bool:
'''36 ms 18.6 MB'''
return len(nums) != len(set(nums))
445. Add Two Numbers II
You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Follow up: What if you cannot modify the input lists? In other words, reversing the lists is not allowed.
Example:
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7
solution
I returned head on my first attempt. There was a test case: [0] + [0], so I got a wrong answer error.
def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
'''80 ms 13.2 MB'''
def List2Num(l: ListNode):
num = 0
while l:
num = num*10 + l.val
l = l.next
return num
num = List2Num(l1) + List2Num(l2)
head = ListNode(0)
while num:
val = num % 10
num //= 10
node = ListNode(val)
node.next = head.next
head.next = node
return head.next if head.next else head
171. Excel Sheet Column Number
Given a column title as appear in an Excel sheet, return its corresponding column number.
For example:
A -> 1
B -> 2
C -> 3
https://github.com/taseikyo/arts/blob/master.
Z -> 26
AA -> 27
AB -> 28
https://github.com/taseikyo/arts/blob/master.
Example 1:
Input: "A"
Output: 1
Example 2:
Input: "AB"
Output: 28
Example 3:
Input: "ZY"
Output: 701
solution
similar to hexadecimal/decimal number
230. Kth Smallest Element in a BST
Given a binary search tree, write a function kthSmallest to find the kth smallest element in it.
Note: You may assume k is always valid, 1 ≤ k ≤ BST's total elements.
Example 1:
Input: root = [3,1,4,null,2], k = 1
3
/ \
1 4
\
2
Output: 1
Example 2:
Input: root = [5,3,6,2,4,null,null,1], k = 3
5
/ \
3 6
/ \
2 4
/
1
Output: 3
Follow up:
- What if the BST is modified (insert/delete operations) often and you need to find the kth smallest frequently? How would you optimize the kthSmallest routine?
solution
Perform an inorder traversal to get the sorted values and then return the kth val.
review
- The Huawei Sanction Might Just Pop the Tech Bubble - OwenWilliams - Medium
- [Markdown] The Huawei Sanction Might Just Pop the Tech Bubble - OwenWilliams - Medium
The main content of this article is the trade war (U.S & China), mainly about the US ban on Huawei.
tip
fseek(fp, 0L, SEEK_END);
long int size = ftell(fp);
share
-[Chinese] The most detailed kvm_mmu_page structure and usage analysis in history
This article gives a detailed explanation of kvm_mmu_page structure. A very GOOD article, recommand level ⭐⭐⭐⭐⭐.