Naomi and Ken sometimes play games together. Before they play, each of them gets N identical-looking blocks of wood with masses between 0.0kg and 1.0kg (exclusive). All of the blocks have different weights. There are lots of games they could play with those blocks, but they usually play something they call War. Here is how War works:
- Each player weighs each of his or her own blocks, so each player knows the weights of all of his or her own blocks, but not the weights of the other player’s blocks.
- They repeat the following process N times:
- Naomi chooses one of her own blocks, with mass
- Naomi tells Ken the mass of the block she chose.
- Ken chooses one of his own blocks, with mass
- They each put their block on one side of a balance scale, and the person whose block is heavier gets one point.
- Both blocks are destroyed in a fire. Continue reading “Google Code Jam Qualification Round 2014 Problem D. Deceitful War 题解”
In this problem, you start with 0 cookies. You gain cookies at a rate of 2 cookies per second, by clicking on a giant cookie. Any time you have at least C cookies, you can buy a cookie farm. Every time you buy a cookie farm, it costs you C cookies and gives you an extra F cookies per second.
Once you have X cookies that you haven’t spent on farms, you win! Figure out how long it will take you to win if you use the best possible strategy. Continue reading “Google Code Jam Qualification Round 2014 Problem B. Cookie Clicker Alpha 题解”
Recently you went to a magic show. You were very impressed by one of the tricks, so you decided to try to figure out the secret behind it!
The magician starts by arranging 16 cards in a square grid: 4 rows of cards, with 4 cards in each row. Each card has a different number from 1 to 16 written on the side that is showing. Next, the magician asks a volunteer to choose a card, and to tell him which row that card is in.
Finally, the magician arranges the 16 cards in a square grid again, possibly in a different order. Once again, he asks the volunteer which row her card is in. With only the answers to these two questions, the magician then correctly determines which card the volunteer chose. Amazing, right?
You decide to write a program to help you understand the magician’s technique. The program will be given the two arrangements of the cards, and the volunteer’s answers to the two questions: the row number of the selected card in the first arrangement, and the row number of the selected card in the second arrangement. The rows are numbered 1 to 4 from top to bottom.
Your program should determine which card the volunteer chose; or if there is more than one card the volunteer might have chosen (the magician did a bad job); or if there’s no card consistent with the volunteer’s answers (the volunteer cheated). Continue reading “Google Code Jam Qualification Round 2014 Problem A. Magic Trick 题解”
以下从Java的角度总结了面试常见的算法和数据结构：字符串，链表，树，图，排序，递归 vs. 迭代，动态规划，位操作，概率问题，排列组合，以及一些需要寻找规律的题目。
首先需要注意的是和C++不同，Java字符串不是char数组。没有IDE代码自动补全功能，应该记住下面这些常用的方法。 Continue reading “[转载+整理]面试10大算法汇总+常见题目解答（Java）”