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, “l(fā)evel” 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的點(diǎn)，說(shuō)明沒(méi)有前置節(jié)點(diǎn)讲仰，可以加入輸出慕趴。
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
給定每個(gè)菜的價(jià)格，可用的總金額。
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
每一項(xiàng)包括departure, arrival, cost冕房，然后給一個(gè)整數(shù)k, 表示最多允許k次中轉(zhuǎn)躏啰。給定起始地點(diǎn)A，到達(dá)地點(diǎn)B, 要求輸出從A到B的最小花費(fèi)耙册，最多k次中轉(zhuǎn)给僵。
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.數(shù)轉(zhuǎn)換步數(shù)計(jì)算
輸入兩棵樹A，B详拙，B是A經(jīng)過(guò)如下操作后得到的：
改變A中某節(jié)點(diǎn)的符號(hào)帝际，并改變它的孫子，孫子的孫子的符號(hào)饶辙；
問(wèn)胡本，需要對(duì)幾個(gè)節(jié)點(diǎn)進(jìn)行上述操作。
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
字符串相乘畸悬，可能有負(fù)數(shù)
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;
}
