1.打印如下分形图:
输入1：
O
O O
输入2：
O
O O
O O
O O O O
代码：
Character[][] map;
public void draw(int n) {
int m = (int)Math.pow(2, n);
map = new Character[m][2 * m - 1];
for (int i = 0; i < m; i++) {
for (int j = 0; j < map[0].length; j++) {
map[i][j] = '\0';
}
}
print(n, 0, 0);
for (int i = 0; i < m; i++) {
for (int j = 0; j < map[0].length; j++) {
System.out.print(map[i][j]);
}
System.out.println();
}
}
private void print(int n, int x, int y) {
if (n == 0) {
map[x][y] = 'O';
return;
}
int m = (int)Math.pow(2, n - 1);
print(n - 1, x, y + m);
print(n - 1, x + m, y);
print(n - 1, x + m, y + m * 2);
}
2.Pour Water
We are given an elevation map, heights[i] representing the height of the terrain at that index. The width at each index is 1. After V units of water fall at index K , how much water is at each index?
Water first drops at index K and rests on top of the highest terrain or water at that index. Then, it flows according to the following rules:
If the droplet would eventually fall by moving left, then move left.
Otherwise, if the droplet would eventually fall by moving right, then move right.
Otherwise, rise at it’s current position.
Here, “eventually fall” means that the droplet will eventually be at a lower level if it moves in that direction. Also, “level” means the height of the terrain plus any water in that column.
We can assume there’s infinitely high terrain on the two sides out of bounds of the array. Also, there could not be partial water being spread out evenly on more than 1 grid block - each unit of water has to be in exactly one block.
Note:
heights will have length in [1, 100] and contain integers in [0, 99] .
V will be in range [0, 2000] .
K will be in range [0, heights.length - 1] .
private void pour(int[] heights, int v, int p) {
int[] waters = new int[heights.length];
while(v-- > 0) {
int cur = p;
int pos = -1;
while(cur > 0 && heights[cur - 1] + waters[cur - 1] <= heights[cur] + waters[cur]) {
if (heights[cur - 1] + waters[cur - 1] < heights[cur] + waters[cur]) {
pos = cur - 1;
}
cur--;
}
cur = p;
while(pos == -1 && cur < heights.length - 1 && heights[cur + 1] + waters[cur + 1] <= heights[cur] + waters[cur]) {
if (heights[cur + 1] + waters[cur + 1] < heights[cur] + waters[cur]) {
pos = cur + 1;
}
cur++;
}
pos = pos == -1 ? p : pos;
waters[pos]++;
}
//print
int max = heights[0];
for (int h : heights) {
if (h > max) {
max = h;
}
}
for (int i = max; i > 0; i--) {
for (int j = 0; j < heights.length; j++) {
if (heights[j] + waters[j] < i) {
System.out.printf(" ");
} else if (heights[j] < i) {
System.out.printf("W");
} else {
System.out.printf("#");
}
}
System.out.println();
}
}
3.Sliding Puzzle
On a 2x3 board , there are 5 tiles represented by the integers 1 through 5, and an empty square represented by 0.
A move consists of choosing 0 and a 4-directionally adjacent number and swapping it.
The state of the board is solved if and only if the board is [[1,2,3],[4,5,0]].
Given a puzzle board, return the least number of moves required so that the state of the board is solved. If it is impossible for the state of the board to be solved, return -1.
Note:
heights will have length in [1, 100] and contain integers in [0, 99] .
V will be in range [0, 2000] .
K will be in range [0, heights.length - 1] .
bfs
public int slidePuzzle(int[][] board) {
String from = "";
for (int[] row : board) {
for (int k : row) {
from += k;
}
}
String to = "123450";
int[][] next = new int[][]{{1, 3}, {0, 2, 4}, {1, 5}, {0, 4}, {1, 3, 5}, {2, 4}};
Queue<String> q = new LinkedList<>();
Set<String> used = new HashSet<>();
q.offer(from);
used.add(from);
int steps = 0;
while (!q.isEmpty()) {
int n = q.size();
while (n-- > 0) {
String cur = q.poll();
if (cur.equals(to)) {
return steps;
}
int ind = cur.indexOf("0");
for (int move : next[ind]) {
char[] chars = cur.toCharArray();
char tmp = chars[move];
chars[move] = '0';
chars[ind] = tmp;
String s = String.valueOf(chars);
if (!used.contains(s)) {
used.add(s);
q.add(s);
}
}
}
steps++;
}
return -1;
}
4.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:
Input:
[
"wrt",
"wrf",
"er",
"ett",
"rftt"
]
Output: "wertf"
Example 2:
Input:
[
"z",
"x"
]
Output: "zx"
Example 3:
Input:
[
"z",
"x",
"z"
]
Output: ""
Explanation: The order is invalid, so return "".
Note:
You may assume all letters are in lowercase.
You may assume that if a is a prefix of b, then a must appear before b in the given dictionary.
If the order is invalid, return an empty string.
There may be multiple valid order of letters, return any one of them is fine.
入度为0的点，说明没有前置节点，可以加入输出。
public String alienOrder(String[] words) {
Map<Character, Set<Character>> graph = constructGraph(words);
Map<Character, Integer> inDegreeSet = getInDegree(graph);
String result = "";
Queue<Character> q = new LinkedList<>();
for (Character c : inDegreeSet.keySet()) {
if (inDegreeSet.get(c) == 0) {
q.offer(c);
}
}
while (!q.isEmpty()) {
Character c = q.poll();
result += c;
for (Character neighbour : graph.get(c)) {
inDegreeSet.put(neighbour, inDegreeSet.get(neighbour) - 1);
if (inDegreeSet.get(neighbour) == 0) {
q.offer(neighbour);
}
}
}
if (result.length() != graph.keySet().size()) {
return "";
}
return result;
}
private Map<Character, Integer> getInDegree(Map<Character, Set<Character>> graph) {
Map<Character, Integer> inDegreeMap = new HashMap<>();
for (Character key : graph.keySet()) {
inDegreeMap.put(key, 0);
}
for (Character key : graph.keySet()) {
for (Character c : graph.get(key)) {
inDegreeMap.put(c, inDegreeMap.get(c) + 1);
}
}
return inDegreeMap;
}
private Map<Character, Set<Character>> constructGraph(String[] words) {
Map<Character, Set<Character>> graph = new HashMap<>();
for (String word : words) {
for (Character c : word.toCharArray()) {
if (!graph.containsKey(c)) {
graph.put(c, new HashSet<>());
}
}
}
for (int i = 0; i < words.length - 1; i++) {
int ind = 0;
while (ind < words[i].length() && ind < words[i + 1].length()) {
if (words[i].charAt(ind) != words[i + 1].charAt(ind)) {
graph.get(words[i].charAt(ind)).add(words[i + 1].charAt(ind));
break;
}
ind++;
}
}
return graph;
}
5.Palindrome Pairs
Given a list of unique words, find all pairs of distinct indices (i, j) in the given list, so that the concatenation of the two words, i.e. words[i] + words[j] is a palindrome.
Example 1:
Input: ["abcd","dcba","lls","s","sssll"]
Output: [[0,1],[1,0],[3,2],[2,4]]
Explanation: The palindromes are ["dcbaabcd","abcddcba","slls","llssssll"]
Example 2:
Input: ["bat","tab","cat"]
Output: [[0,1],[1,0]]
Explanation: The palindromes are ["battab","tabbat"]
public List<List<Integer>> palindromePairs(String[] words) {
List<List<Integer>> result = new ArrayList<>();
Map<String, Integer> m = new HashMap<>();
for (int i = 0; i < words.length; i++) {
m.put(words[i], i);
}
for (int i = 0; i < words.length; i++) {
for (int j = 0; j <= words[i].length(); j++) {
String s1 = words[i].substring(0, j);
String s2 = words[i].substring(j);
if (isPalind(s1)) {
String re = new StringBuffer(s2).reverse().toString();
if (m.containsKey(re) && m.get(re) != i) {
List<Integer> tmp = new ArrayList<>();
tmp.add(m.get(re));
tmp.add(i);
result.add(tmp);
}
}
if (isPalind(s2)) {
String re = new StringBuffer(s1).reverse().toString();
if (m.containsKey(re) && m.get(re) != i && s2.length() != 0) {
List<Integer> tmp = new ArrayList<>();
tmp.add(i);
tmp.add(m.get(re));
result.add(tmp);
}
}
}
}
return result;
}
private boolean isPalind(String word) {
int a = 0;
int b = word.length() - 1;
while (a < b) {
if (word.charAt(a) != word.charAt(b)) {
return false;
}
a++;
b--;
}
return true;
}
6.Flatten 2D Vector
Implement an iterator to flatten a 2d vector.
For example,
Given 2d vector =
[
[1,2],
[3],
[4,5,6]
]
By calling next repeatedly until hasNext returns false, the order of elements returned by next should be: [1,2,3,4,5,6].
Hint:
- How many variables do you need to keep track?
- Two variables is all you need. Try with
xandy. - Beware of empty rows. It could be the first few rows.
- To write correct code, think about the invariant to maintain. What is it?
- The invariant is
xandymust always point to a valid point in the 2d vector. Should you maintain your invariant ahead of time or right when you need it? - Not sure? Think about how you would implement
hasNext(). Which is more complex? - Common logic in two different places should be refactored into a common method.
Follow up:
As an added challenge, try to code it using only iterators in C++ or iterators in Java.
public class Vector2D implements Iterator<Integer> {
int indexList, indexElement;
List<List<Integer>> list;
public Vector2D(List<List<Integer>> vec2d) {
indexList = 0;
indexElement = 0;
list = vec2d;
}
@Override
public Integer next() {
return list.get(indexList).get(indexElement++);
}
@Override
public boolean hasNext() {
while(indexList<list.size()) {
if(indexElement<list.get(indexList).size()){
return true;
} else {
indexList++;
indexElement = 0;
}
}
return false;
}
}
7.menu order
类似于Combination Sum II
给定每个菜的价格，可用的总金额。
List<List<Integer>> result;
public List<List<Integer>> combinationSum2(int[] candidates, int target) {
Arrays.sort(candidates);
result = new ArrayList<>();
combine(candidates, 0, candidates.length - 1, target, new ArrayList<>());
return result;
}
private void combine(int[] candidates, int l, int r, int target, List<Integer> last) {
int pre = -1;
for (int i = l; i <= r; i++) {
if (candidates[i] == pre) {
continue;
}
pre = candidates[i];
if (candidates[i] == target) {
List<Integer> tmp = new ArrayList<>(last);
tmp.add(candidates[i]);
result.add(tmp);
} else if (candidates[i] < target) {
last.add(candidates[i]);
combine(candidates, i + 1, r, target - candidates[i], last);
last.remove(last.size() - 1);
}
}
}
8.flight ticket list
每一项包括departure, arrival, cost，然后给一个整数k, 表示最多允许k次中转。给定起始地点A，到达地点B, 要求输出从A到B的最小花费，最多k次中转。
public int findCheapestPrice(int n, int[][] flights, int src, int dst, int K) {
Map<Integer, Map<Integer, Integer>> m = new HashMap<>();
for (int i = 0; i < flights.length; i++) {
if (!m.containsKey(flights[i][0])) {
m.put(flights[i][0], new HashMap<>());
}
m.get(flights[i][0]).put(flights[i][1], flights[i][2]);
}
Queue<int[]> q = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
q.add(new int[]{0, src, K + 1});
while (!q.isEmpty()) {
int[] tmp = q.remove();
if (tmp[1] == dst) {
return tmp[0];
}
if (tmp[2] == 0) {
continue;
}
Map<Integer, Integer> edges = m.getOrDefault(tmp[1], new HashMap<>());
for (int city : edges.keySet()) {
q.add(new int[]{tmp[0] + edges.get(city), city, tmp[2] - 1});
}
}
return -1;
}
9.数转换步数计算
输入两棵树A，B，B是A经过如下操作后得到的：
改变A中某节点的符号，并改变它的孙子，孙子的孙子的符号；
问，需要对几个节点进行上述操作。
public int countSteps(TreeNode a, TreeNode b) {
return count(a, b, new boolean[2]);
}
public int count(TreeNode a, TreeNode b, boolean[] flag) {
if (a == null) {
return 0;
}
boolean[] f = new boolean[2];
a.val = flag[0] ? -a.val : a.val;
f[0] = flag[1];
int cnt = 0;
if (a.val != b.val) {
f[1] = true;
cnt++;
}
return count(a.left, b.left, f) + count(a.right, b.right, f) + cnt;
}
9. string multiply
字符串相乘，可能有负数
public String multiply(String a, String b) {
boolean flag = true;
if (a.charAt(0) == '+' || a.charAt(0) == '-') {
flag = a.charAt(0) == '-' ? false : true;
a = a.substring(1);
}
if (b.charAt(0) == '+' || b.charAt(0) == '-') {
flag = b.charAt(0) == '-' ? !flag : flag;
b = b.substring(1);
}
int[] x = new int[a.length()];
int[] y = new int[b.length()];
for (int i = 0; i < a.length(); i++) {
x[i] = a.charAt(a.length() - i - 1) - '0';
}
for (int i = 0; i < b.length(); i++) {
y[i] = b.charAt(b.length() - i - 1) - '0';
}
int[] res = new int[a.length() + b.length()];
for (int i = 0; i < x.length; i++) {
for (int j = 0; j < y.length; j++) {
res[i + j] += x[i] * y[j];
res[i + j + 1] += res[i + j] / 10;
res[i + j] = res[i + j] % 10;
}
}
String s = "";
int ind = res.length - 1;
while (ind >= 0 && res[ind] == 0) {
ind--;
}
for (int i = ind; i >= 0; i--) {
s += res[i];
}
String result = (ind == -1) ? "0" : s;
return result == "0" ? "0" : flag ? s : "-" + s;
}
10.Pyramid Transition Matrix
public boolean pyramidTransition(String bottom, List<String> allowed) {
Map<String, Set<String>> m = new HashMap<>();
for (String s : allowed) {
if (!m.containsKey(s.substring(0, 2))) {
m.put(s.substring(0, 2), new HashSet<>());
}
m.get(s.substring(0, 2)).add(s.substring(2));
}
return dfs(bottom, m, 0, "");
}
private boolean dfs(String bottom, Map<String, Set<String>> m, int i, String next) {
if (bottom.length() == 1) {
return true;
}
if (i == bottom.length() - 1) {
return dfs(next, m, 0, "");
}
if (m.containsKey(bottom.substring(i, i + 2))) {
for (String s : m.get(bottom.substring(i, i + 2))) {
if (dfs(bottom, m, i + 1, next + s)) {
return true;
}
}
}
return false;
}
