Google Kickstart 2017 Round F题解 | Calvin's Marbles



Google Kickstart 2017 Round F题解 | Calvin's Marbles

Google Kickstart 2017 Round F，当时做了两条就睡觉了，早上把剩下两条也过了。感觉不算是很难，可能也和这场限时24h有关吧。不过提交的时候倒是手忙脚乱，第一条交了三发，第一发是从VS迁移到DevC上是DevC由于之前配了个C++14所以崩了，第二发输出里面是Unicode BOM，WA了，蛋疼。

A. Kicksort

找规律发现每次找的pivot的位置是从原数组的中心点（奇）或中心线靠左（偶）开始，如果小于原数组的中位数，则下一个位置是其轴对称，否则是其左边一个位置。这样从数组的中部交替往外移动，结束条件是pivot到达原数组的最后一个元素。由于这个过程中所有选为的pivot都是最大/小值才返回YES，否则直接返回NO，所以只要迭代继续，我们去掉的就一直是最大/小值。因此使用l和r记录此时所有还没被作为pivot去掉的数中的最大/小值，判断新的pivot是否等于l或r。


Read full article from Google Kickstart 2017 Round F题解 | Calvin's Marbles


No comments:

Post a Comment

Subscribe to: Post Comments (Atom)

Labels

Algorithm (219) Lucene (130) LeetCode (97) Database (36) Data Structure (33) text mining (28) Solr (27) java (27) Mathematical Algorithm (26) Difficult Algorithm (25) Logic Thinking (23) Puzzles (23) Bit Algorithms (22) Math (21) List (20) Dynamic Programming (19) Linux (19) Tree (18) Machine Learning (15) EPI (11) Queue (11) Smart Algorithm (11) Operating System (9) Java Basic (8) Recursive Algorithm (8) Stack (8) Eclipse (7) Scala (7) Tika (7) J2EE (6) Monitoring (6) Trie (6) Concurrency (5) Geometry Algorithm (5) Greedy Algorithm (5) Mahout (5) MySQL (5) xpost (5) C (4) Interview (4) Vi (4) regular expression (4) to-do (4) C++ (3) Chrome (3) Divide and Conquer (3) Graph Algorithm (3) Permutation (3) Powershell (3) Random (3) Segment Tree (3) UIMA (3) Union-Find (3) Video (3) Virtualization (3) Windows (3) XML (3) Advanced Data Structure (2) Android (2) Bash (2) Classic Algorithm (2) Debugging (2) Design Pattern (2) Google (2) Hadoop (2) Java Collections (2) Markov Chains (2) Probabilities (2) Shell (2) Site (2) Web Development (2) Workplace (2) angularjs (2) .Net (1) Amazon Interview (1) Android Studio (1) Array (1) Boilerpipe (1) Book Notes (1) ChromeOS (1) Chromebook (1) Codility (1) Desgin (1) Design (1) Divide and Conqure (1) GAE (1) Google Interview (1) Great Stuff (1) Hash (1) High Tech Companies (1) Improving (1) LifeTips (1) Maven (1) Network (1) Performance (1) Programming (1) Resources (1) Sampling (1) Sed (1) Smart Thinking (1) Sort (1) Spark (1) Stanford NLP (1) System Design (1) Trove (1) VIP (1) tools (1)

Popular Posts