Interview-Question-20: String Pyramids with Transition Matrix

原文链接:

http://www.1point3acres.com/bbs/thread-146537-1-1.html

题目描述:

给你一个字符对的转换matrix,表示这个字符对会转化成一个字符(但是有的字符对可能有多个能够转化成的字符,原文是nondeterministic)。以及若干个合法的终点(最顶上那一个点)状态,多次询问,判断一个字符串是否有一个方法能够走到合法状态。

解析:

 

 

Interview-Question-19: WaterLand

原文链接:
http://www.1point3acres.com/bbs/forum.php?mod=viewthread&tid=218383

题目描述:

Skype: 往一个int array 代表海拔的格子里倒水,打印出倒水后的图, 输入:int[] 海拔, int 水数量, int 倒的位置。
Example:
int[] 海拔 {5,4,2,1,2,3,2,1,0,1,2,4}
+           
++      +
++  +   ++
+++ +++  ++ 
++++++++ +++
++++++++++++水数量8, 倒在位置5 ->
+      
++      +
++www+   ++
+++w+++www++
++++++++w+++
++++++++++++

解析:

 

Leetcode-Question-212: Word Search II

原文链接:

https://leetcode.com/problems/word-search-ii/

解析:

Trie + DFS

 

Leetcode-Question-269: Alien Dictionary

原文链接:

https://leetcode.com/problems/alien-dictionary/

题目描述:

There is a new alien language which uses the latin alphabet. However, the order among letters are unknown to you. You receive a list of non-empty words from the dictionary, where words are sorted lexicographically by the rules of this new language. Derive the order of letters in this language.

Example 1:
Given the following words in dictionary,

The correct order is: "wertf".

Example 2:
Given the following words in dictionary,

The correct order is: "zx".

Example 3:
Given the following words in dictionary,

The order is invalid, so return "".

Note:

  1. You may assume all letters are in lowercase.
  2. You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
  3. If the order is invalid, return an empty string.
  4. There may be multiple valid order of letters, return any one of them is fine.

解析:

BFS

第二遍:

 

Interview-Question-03: Flattern 2D Vector with Remove

原文链接:

参考https://leetcode.com/problems/flatten-2d-vector/

题目描述:

实现二维数组的迭代器,加上remove操作。

解析:

 

Interview-Question-18: Menu Order

原文链接:

https://instant.1point3acres.com/thread/191262

描述:

点菜,菜价格为double,问如何正好花完手里的钱

Given a menu (list of items prices), find all possible combinations of items that sum a particular value K. (A variation of the typical 2sum/Nsum questions).

解析:

假设同一个菜可以重复点。。。

参考:https://leetcode.com/problems/combination-sum-ii/

 

Leetcode-Question-336: Palindrome Pairs

原文链接:

https://leetcode.com/problems/palindrome-pairs/

解析:

更直观的解法:

【面试考察的解法】

再写一遍:

 

Leetcode-Question-15: Find Median from Large File of Integers

原文链接:

https://instant.1point3acres.com/thread/159344

题目描述:

给定一特别大的文件,每行包含一Integer,如何快速找出其中位数。

解法:

Binary Search

 

Leetcode-Question-14: Wizards

原文链接:

http://www.1point3acres.com/bbs/thread-296093-1-1.html

题目描述:

比如说有五个魔法师,求0到4认识的最少距离
0号认识 1号和 2号
1号认识 3号.
2号认识 3号,4号.
3号认识4号

那么0号到4号的三条路径有: 0->1->3->4, 0->2->3->4, 0->2->4
最小权重和的路径是 0->2->3->4.

/There are 10 people at a wizard meetup. Each wizard has levels 0 – 9 (the index of the input) and  knows a few other wizards there.  Your job is to find the cheapest way for wizard 0 to meet wizard 9. Introductions have a cost that equals the square of the difference in levels.
Goal: Level 0 wizard wants to meet level 9 using the fewest possible magic points. 
Cost: square of difference of levels
The index of the array represents the level (0-9)
the value is an array with the index of the other people each person knows.
Note that relationships are one directional (e.g. 2 can introduce you to 3 but not vice versa)
e.g. Min cost: 23 Min path: [0, 1, 4, 6, 9]. /

graph like this
vector<vector<int>> wizards = {
  {1, 2, 3},   // wizard 0
  {8, 6, 4},   // wizard 1
  {7, 8, 3},   // wizard 2
  {8, 1},      // …
  {6},
  {8, 7},
  {9, 4},
  {4, 6},
  {1},
  {1, 4},
};

解析:

 

Interview-Question-14: Host Crowding

原文链接及题目描述请自行Google.

解析: