Google Code Jam Qualification Round 2014 Problem D. Deceitful War 题解

Problem

Naomi and Ken sometimes play games together. Before they play, each of them gets 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:

  1. 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.
  2. They repeat the following process N times:
    1. Naomi chooses one of her own blocks, with mass ChosenNaomi.
    2. Naomi tells Ken the mass of the block she chose.
    3. Ken chooses one of his own blocks, with mass ChosenKen.
    4. They each put their block on one side of a balance scale, and the person whose block is heavier gets one point.
    5. Both blocks are destroyed in a fire. Continue reading “Google Code Jam Qualification Round 2014 Problem D. Deceitful War 题解”

Google Code Jam Qualification Round 2014 Problem B. Cookie Clicker Alpha 题解

Introduction

Cookie Clicker is a Javascript game by Orteil, where players click on a picture of a giant cookie. Clicking on the giant cookie gives them cookies. They can spend those cookies to buy buildings. Those buildings help them get even more cookies. Like this problem, the game is very cookie-focused. This problem has a similar idea, but it does not assume you have played Cookie Clicker. Please don’t go play it now: it might be a long time before you come back.

Problem

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 题解”

Google Code Jam Qualification Round 2014 Problem A. Magic Trick 题解

Problem

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 题解”

[转载+整理]面试10大算法汇总+常见题目解答(Java)

原文地址:英文版:http://www.programcreek.com/2012/11/top-10-algorithms-for-coding-interview/

中文版 (本文综合了中文版和英文版,修改了部分文字及排版)

以下从Java的角度总结了面试常见的算法和数据结构:字符串,链表,树,图,排序,递归 vs. 迭代,动态规划,位操作,概率问题,排列组合,以及一些需要寻找规律的题目。

1. 字符串、数组和矩阵

首先需要注意的是和C++不同,Java字符串不是char数组。没有IDE代码自动补全功能,应该记住下面这些常用的方法。 Continue reading “[转载+整理]面试10大算法汇总+常见题目解答(Java)”

各种排序算法的稳定性和复杂度总结

算法 时间复杂度 辅助空间
数据结构均为数组 最好 平均 最坏
冒泡排序(稳定) O(n) O(n^2) O(n^2) O(1)
直接插入(稳定) O(n) O(n^2) O(n^2) O(1)
简单选择(不稳定) O(n^2) O(n^2) O(n^2) O(1)
快速排序(不稳定) O(n log(n)) O(n log(n)) O(n^2) 平均O(log(n)),最坏O(n)
堆排序(不稳定) O(n log(n)) O(n log(n)) O(n log(n)) O(1)
归并排序(稳定) O(n log(n)) O(n log(n)) O(n log(n)) O(n)
基数排序(稳定)
希尔排序(不稳定) O(n^1.3) O(1)

这里有3个很酷的排序算法演示:

http://jsdo.it/norahiko/oxIy/fullscreen

2 15 Sorting Algorithms in 6 Minutes

http://www.youtube.com/watch?v=kPRA0W1kECg

3 Visualization of Quick sort 快速排序的可视化

http://www.youtube.com/watch?v=vxENKlcs2Tw

感谢阅读!

参考资料:

http://bigocheatsheet.com/

[转载]LeetCode题目难度分布(含面试频率及使用的数据结构与算法)

原文地址:LeetCode Question Difficulty Distribution(墙外)

另见:http://blog.csdn.net/lilong_dream/article/details/23191423(难度/频率用颜色深浅区分)

ID

Question

Diff

Freq

Data Structure

Algorithms

1

Two Sum

2

5

array

sort

set

Two Pointers

2

Add Two Numbers

3

4

linked list

Two Pointers

Math

3

Longest Substring Without Repeating Characters

3

2

string

Two Pointers

hashtable

4

Median of Two Sorted Arrays

5

3

array

Binary Search

5

Longest Palindromic Substring

4

2

string

6

ZigZag Conversion

3

1

string

7

Reverse Integer

2

3

Math

8

String to Integer (atoi)

2

5

string

Math

9

Palindrome Number

2

2

Math

10

Regular Expression Matching

5

3

string

Recursion

DP

11

Container With Most Water

3

2

array

Two Pointers

12

Integer to Roman

3

4

Math

13

Roman to Integer

2

4

Math

14

Longest Common Prefix

2

1

string

15

3Sum

3

5

array

Two Pointers

16

3Sum Closest

3

1

array

Two Pointers

17

Letter Combinations of a Phone Number

3

3

string

DFS

18

4Sum

3

2

array

19

Remove Nth Node From End of List

2

3

linked list

Two Pointers

20

Valid Parentheses

2

5

string

Stack Continue reading “[转载]LeetCode题目难度分布(含面试频率及使用的数据结构与算法)”

LeetCode题解汇总(C++ Java Python,含题目翻译)

LeetCode题目(含AC Rates):http://oj.leetcode.com/problems/

题目难度分布、面试频率及使用的数据结构与算法分析:

http://blog.csdn.net/lilong_dream/article/details/23191423

我的github:https://github.com/lilong-dream/

Two Sum

http://blog.csdn.net/lilong_dream/article/details/19298357

Median of Two Sorted Arrays

http://blog.csdn.net/lilong_dream/article/details/19355465

Longest Substring Without Repeating Characters

http://blog.csdn.net/lilong_dream/article/details/19431417

Add Two Numbers

http://blog.csdn.net/lilong_dream/article/details/19544995

Single Number

http://blog.csdn.net/lilong_dream/article/details/19556493

Reverse Integer

http://blog.csdn.net/lilong_dream/article/details/19674929

String to Integer (atoi)

http://blog.csdn.net/lilong_dream/article/details/19677643

Remove Nth Node From End of List

http://blog.csdn.net/lilong_dream/article/details/19753021

Remove Duplicates from Sorted Array

http://blog.csdn.net/lilong_dream/article/details/19757047

10 Remove Element

http://blog.csdn.net/lilong_dream/article/details/19759709 Continue reading “LeetCode题解汇总(C++ Java Python,含题目翻译)”

[翻译]常用的Java库、框架和工具清单

原文地址:http://www.indiageeks.in/list-of-commonly-used-java-libraries-frameworks-and-tools/

Java库和框架:

1.     内核:

    Apache commons

    Guava

2.     日志:

    Log4j

    logback

    SLF4J

3.     日期和时间:

    Joda-time

4.     HTML 和 XML解析器:

    HTMLParser

    JTidy

    JDom

    Simple xml parser Continue reading “[翻译]常用的Java库、框架和工具清单”

CentOS 常用命令及快捷键整理

最近开始学Linux,在VMware Player中安装了CentOS 6.4。为方便自己也方便他人,整理了Linux常用命令及快捷键。

常用命令:

文件和目录:

# cd /home                        进入 ‘/home’ 目录

# cd ..                                返回上一级目录

# cd ../..                             返回上两级目录

# cd –                                 返回上次所在目录

# cp file1 file2                    将file1复制为file2

# cp -a dir1 dir2                 复制一个目录

# cp -a /tmp/dir1 .              复制一个目录到当前工作目录(.代表当前目录)

# ls                                    查看目录中的文件

# ls -a                                显示隐藏文件

# ls -l                                 显示详细信息

# ls -lrt                               按时间显示文件(l表示详细列表,r表示反向排序,t表示按时间排序)

# pwd                                显示工作路径

# mkdir dir1                       创建 ‘dir1’ 目录

# mkdir dir1 dir2                同时创建两个目录

# mkdir -p /tmp/dir1/dir2    创建一个目录树

# mv dir1 dir2                    移动/重命名一个目录

# rm -f file1                        删除 ‘file1’

# rm -rf dir1                       删除 ‘dir1’ 目录及其子目录内容 Continue reading “CentOS 常用命令及快捷键整理”