Thinking in XiaoQiang
世人皆有悲哀,只有你不明白
posts - 56,comments - 150,trackbacks - 0

终于等到google编程赛开始了,可是居然不能登录到arena.急啊!!
晚上好不容易open了一道250分的题,还没看完题呢就掉线了,等我再上去时,时间只剩下不到10分钟了.
可惜啊可惜啊~~~~

好在我也自知水平有限,目标只是为了掺和
------------------------------------------------------------------------------------------------------


250的:
Problem Statement
   
You are given a String input. You are to find the longest substring of input such that the reversal of the substring is also a substring of input. In case of a tie, return the string that occurs earliest in input.
Definition
   
Class:
ReverseSubstring
Method:
findReversed
Parameters:
String
Returns:
String
Method signature:
String findReversed(String input)
(be sure your method is public)
   
Notes
-
The substring and its reversal may overlap partially or completely.
-
The entire original string is itself a valid substring (see example 4).
Constraints
-
input will contain between 1 and 50 characters, inclusive.
-
Each character of input will be an uppercase letter ('A'-'Z').
Examples
0)
   
"XBCDEFYWFEDCBZ"
Returns: "BCDEF"
We see that the reverse of BCDEF is FEDCB, which appears later in the string.
1)
   
"XYZ"
Returns: "X"
The best we can do is find a one character substring, so we implement the tie-breaker rule of taking the earliest one first.
2)
   
"ABCABA"
Returns: "ABA"
The string ABA is a palindrome (it's its own reversal), so it meets the criteria.
3)
   
"FDASJKUREKJFDFASIREYUFDHSAJYIREWQ"
Returns: "FDF"
4)
   
"ABCDCBA"
Returns: "ABCDCBA"
Here, the entire string is its own reversal.

 


750的:
Problem Statement
   
You are given a String[] grid representing a rectangular grid of letters. You are also given a String find, a word you are to find within the grid. The starting point may be anywhere in the grid. The path may move up, down, left, right, or diagonally from one letter to the next, and may use letters in the grid more than once, but you may not stay on the same cell twice in a row (see example 6 for clarification).
You are to return an int indicating the number of ways find can be found within the grid. If the result is more than 1,000,000,000, return -1.
Definition
   
Class:
WordPath
Method:
countPaths
Parameters:
String[], String
Returns:
int
Method signature:
int countPaths(String[] grid, String find)
(be sure your method is public)
   
Constraints
-
grid will contain between 1 and 50 elements, inclusive.
-
Each element of grid will contain between 1 and 50 uppercase ('A'-'Z') letters, inclusive.
-
Each element of grid will contain the same number of characters.
-
find will contain between 1 and 50 uppercase ('A'-'Z') letters, inclusive.
Examples
0)
   
{"ABC",
 "FED",
 "GHI"}
"ABCDEFGHI"
Returns: 1
There is only one way to trace this path. Each letter is used exactly once.
1)
   
{"ABC",
 "FED",
 "GAI"}
"ABCDEA"
Returns: 2
Once we get to the 'E', we can choose one of two directions for the final 'A'.
2)
   
{"ABC",
 "DEF",
 "GHI"}
"ABCD"
Returns: 0
We can trace a path for "ABC", but there's no way to complete a path to the letter 'D'.
3)
   
{"AA",
 "AA"}
"AAAA"
Returns: 108
We can start from any of the four locations. From each location, we can then move in any of the three possible directions for our second letter, and again for the third and fourth letter. 4 * 3 * 3 * 3 = 108.
4)
   
{"ABABA",
 "BABAB",
 "ABABA",
 "BABAB",
 "ABABA"}
"ABABABBA"
Returns: 56448
There are a lot of ways to trace this path.
5)
   
{"AAAAA",
 "AAAAA",
 "AAAAA",
 "AAAAA",
 "AAAAA"}
"AAAAAAAAAAA"
Returns: -1
There are well over 1,000,000,000 paths that can be traced.
6)
   
{"AB",
 "CD"}
"AA"
Returns: 0
Since we can't stay on the same cell, we can't trace the path at all.


在梦想中期待,在掉线中惨败
posted on 2005-12-13 09:48 小强 阅读(408) 评论(0)  编辑  收藏 所属分类: 技术相关

只有注册用户登录后才能发表评论。


网站导航: