很久没发博客文章了,最近想重新捡起来,因为觉得自己总是输入不输出不是一个很好的学习习惯,祝大家虎年快乐。最近总算是读完了 Happy Money 这本书,这本书是之前在 Madison 短租房子的时候前租户留下的,作者是 Elizabeth Dunn 和 Michael Norton。正好当时也有些迷失,但是有开始了自己的全职工作,就想好好思考一下如何花钱让自己最开心。现在看完了这本书,也算是有所共鸣有所学习,在这里记录分享一下。
In this post I will mainly talk about some enrollment tips for future new Chinese students to UW-Madison. Some tips also are also applicable to students to other U.S. Universities. 本文主要介绍一些入学前准备工作给一些未来可能来麦屯的中国同学,其中一些 Tips 可能也适用于其他美国学校。
In this post I will give some algorithm problem from Google OA as well as Leetcode and my thoughts on them. Our main problem here will be the OA problem appeared in the OA practice of Google Intern 2020 Online Assesment.
Problem Description
Problem Removed due to DMCA issue.
Thoughts
Original Problem
Patience. Deal cards $c_1, c_2, …, c_n$ into piles according to two rules:
Can’t place a higher-valued card onto a lowered-valued card.
Can form a new pile and put a card onto it. Goal. Form as few piles as possible.
Dual Problem
The dual problem for this is Longest increasing subsequence. And the Problem is defined as: Given a sequence of elements $c_1, c_2, …, c_n$ from a totally-ordered universe, find the longest increasing subsequence.
Duality Proof
Greedy Algorithm
Place each card on leftmost pile that fits.
Observation. At any stage during greedy algorithm, top cards of piles increase from left to right.
Weak duality.
In any legal game of patience, the number of piles ≥ length of any increasing subsequence.
Proof.
Cards within a pile form a decreasing subsequence.
Any increasing sequence can use at most one card from each pile.
Strong duality
[Hammersley 1972]Min number of piles = max length of an IS; moreover greedy algorithm finds both.
Proof. Each card maintains a pointer to top card in previous pile at time of insertion.
Follow pointers to obtain IS whose length equals the number of piles.
By weak duality, both are optimal.
Conclusion The length of longest increasing subsequence is equal to the smallest number of decresing subsequences.
defget_min_row_num(student_height_arr: List[int]) -> int: # greedy and binary search tail_list = [0] * len(student_height_arr) size = 0 for height in student_height_arr: # i: start index of rows # j: end index of rows i, j = 0, size while i != j: m = int((i + j)/2) # note here we need <= to ensure in each row is strictly decreasing # according to the problem description if tail_list[m] <= height: i = m + 1 else: j = m tail_list[i] = height size = max([i+1, size]) return size
#!/usr/bin/env python3 # view it as a LNDS problem from typing importList
defget_min_row_num(student_height_arr: List[int]) -> int: # DP, convert to Longest Non-decreasing Subsequence Problem (LNDS) # memo[i] LNDS including ending with arr[i] n = len(student_height_arr) if n == 0: return0 memo = [1]*n for i inrange(1, n): for j inrange(i): if student_height_arr[i] >= student_height_arr[j]: memo[i] = max([memo[i], memo[j]+1]) returnmax(memo)
There are many public face datasets available on the Internet for reseach purposes at present. In this post, I collect most of them and give each of them a small desciption so that people can select the proper one quickly. Selecting and preprocessing the datasets properly can be critical to the performance and reliability of the results.