1. Beautiful String
簡單來說就是對一個string，依照字母的出現頻率給予 26 ~ 1的權重 (從低到高)。把出現次數乘上權重再加總算總分。
2. Balanced Smileys
要想一下的字串parse題。從s[0]開始一個一個字串作。字元a~z和空白不重要，直接skip。由於左括( 與右括 ) 要匹配，所以要持續紀錄目前還單身的左括號。冒號的話要看緊接在後的是否有) 或 (，有的話要branch成兩重情況，一種是笑/哭臉，另一種是單純的冒號。我很懶就用recursive實作了。
3. Finding the min
被我莽夫地解了。
前k (m_0 ~ m_k-1) 個就模擬了，反正頂多10萬個，注意一下10^9 * 10^9要用long long 去接(C/C++)，不然會暴。算完前k個就完成一半了。
另一半就是算之後的k+1個數(m_k ~ m_2k)。由於要不斷的挑前k個數沒出現過的最小非負整數，用個好的data structure還是有用的，比如說BST。我又懶了所以這裡就bucket count了，非常暴力。聰明的人觀察到 m_k~ m_2k 剛好是 0 ~ k+1的permutation, 所以m_2k+1 之後會從m_k開始重復。所以m_k = m_2k+1 = m_3k+2 = m_4k+3 。總之就是有k+1的週期，如此週而復始屎而復粥。最後小心的把n mapping一下即可。
沒有留言:
張貼留言