1.相关数据结构
1.1 ArrayList
1.2 String、StringBuffer和StringBuilder
参考String、StringBuffer和StringBuilder
2.编程题
Q1.实现一个算法，确定一个字符串的所有字符是有全都相同。假使不允许使用额外的数据结构，如何处理？
Ans.思路如下：
- step1.是ASCII字符还是Unicode字符，字符不同，存储空间不同。
- step2.优化，若字符串的长度大于字母表中字符个数，则肯定有相同的
- step3.使用boolean数据进行标记该字符是否出现；使用位向量标记
使用位向量：
public static boolean isUniqueChars(String str) {
if (str.length() > 128) {
return false;
}
int checker = 0;
for (int i = 0; i < str.length(); i++) {
int val = str.charAt(i) - 'a';
if ((checker & (1 << val)) > 0) return false;
checker |= (1 << val);
}
return true;
}
使用boolean数组：
public static boolean isUniqueChars2(String str) {
if (str.length() > 128) {
return false;
}
boolean[] char_set = new boolean[128];
for (int i = 0; i < str.length(); i++) {
int val = str.charAt(i);
if (char_set[val]) return false;
char_set[val] = true;
}
return true;
}
Q2.使用C/C++实现void reverse(char* str)函数，反转一个null结尾的字符串。
Ans.思路：
- 找到尾指针，头尾指针交换，并向中间走
void reverse(char *str) {
char* end = str;
char tmp;
if (str) {
while (*end) {
++end;
}
--end;
while (str < end) {
tmp = *str;
*(str++) = *end;
*(end--) = tmp;
}
}
Q3.给定两个字符串，请编写程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。变位词（anagram）
Ans.思路：
- 优化：长度不同，肯定不是变位词
- 一种直接的想法：排序后是否相等 O(nlgn)
- 改进的算法：检查两字符串的各字符数是否相同 O(n)
直接的思路：
public static String sort(String s) {
char[] content = s.toCharArray();
java.util.Arrays.sort(content);
return new String(content);
}
public static boolean permutation(String s, String t) {
return sort(s).equals(sort(t));
}
改进算法：
public static boolean permutation(String s, String t) {
if (s.length() != t.length()) {
return false;
}
int[] letters = new int[128];
char[] s_array = s.toCharArray();
for (char c : s_array) { // count number of each char in s.
letters[c]++;
}
for (int i = 0; i < t.length(); i++) {
int c = (int) t.charAt(i);
if (--letters[c] < 0) {
return false;
}
}
return true;
}
算法分析：
- 1）若相等，则所有letters[c]最后均为0
- 2）若有小于0，则肯定不等
- 3）若最终有大于0的，表明对于字符c，s[c] > t[c]。但是由于s和t总长度相等，则必然有其他某个字符s[d] < t[d]，表明一定有小于0。所以算法是正确的。
Q4.编写一个方法，将字符串中的空格全部替换为"%20"。假定该字符串尾部有足够空间存放新增字符，并且知道字符串的真实长度。
Ans.思路
- 字符串操作的常见做法：从尾部开始编辑，从后往前反向操作。从尾部操作有额外缓冲，移动少，不必担心覆盖。
- 两次遍历：第一次，统计出空格数，计算出最终字符串长度；第二次，反向修改。
public static void replaceSpaces(char[] str, int length) {
int spaceCount = 0, index, i = 0;
for (i = 0; i < length; i++) {
if (str[i] == ' ') {
spaceCount++;
}
}
index = length + spaceCount * 2;
str[index] = '\0';
for (i = length - 1; i >= 0; i--) {
if (str[i] == ' ') {
str[index - 1] = '0';
str[index - 2] = '2';
str[index - 3] = '%';
index = index - 3;
} else {
str[index - 1] = str[i];
index--;
}
}
}
Q5.利用字符重复出现的次数，编写一个方法，实现基本的字符串压缩功能。比如，字符串aabcccccaaa变为a2b1c5a3。若压缩后的字符串没有变短，则返回原先的字符串。
Ans.思路：
- 此题思路比较直接，关键在于String的拼接处理方式：直接使用String +；使用StringBuffer；使用字符数组代替
直接使用String +：
public static int countCompression(String str) {
if (str == null || str.isEmpty()) return 0;
char last = str.charAt(0);
int size = 0;
int count = 1;
for (int i = 1; i < str.length(); i++) {
if (str.charAt(i) == last) {
count++;
} else {
last = str.charAt(i);
size += 1 + String.valueOf(count).length();
count = 1;
}
}
size += 1 + String.valueOf(count).length();
return size;
}
public static String compressBad(String str) {
int size = countCompression(str);
if (size >= str.length()) {
return str;
}
String mystr = "";
char last = str.charAt(0);
int count = 1;
for (int i = 1; i < str.length(); i++) {
if (str.charAt(i) == last) {
count++;
} else {
mystr += last + "" + count;
last = str.charAt(i);
count = 1;
}
}
return mystr + last + count;
}
使用StringBuffer：
public static String compressBetter(String str) {
int size = countCompression(str);
if (size >= str.length()) {
return str;
}
StringBuffer mystr = new StringBuffer();
char last = str.charAt(0);
int count = 1;
for (int i = 1; i < str.length(); i++) {
if (str.charAt(i) == last) {
count++;
} else {
mystr.append(last);
mystr.append(count);
last = str.charAt(i);
count = 1;
}
}
mystr.append(last);
mystr.append(count);
return mystr.toString();
}
使用字符数组
public static String compressAlternate(String str) {
int size = countCompression(str);
if (size >= str.length()) {
return str;
}
char[] array = new char[size];
int index = 0;
char last = str.charAt(0);
int count = 1;
for (int i = 1; i < str.length(); i++) {
if (str.charAt(i) == last) {
count++;
} else {
index = setChar(array, last, index, count);
last = str.charAt(i);
count = 1;
}
}
index = setChar(array, last, index, count);
return String.valueOf(array);
}
Q6.给定一幅由NxN矩阵表示的图像，其中每个像素的大小为4字节，编写一个方法，将图像旋转90度。不占用额外内存空间能否做到？
Ans.思路：
- 逐层处理
- 对于每一层，找到上边的起点和终点。然后从起点开始逐个旋转。
- 旋转方法：记住上边top，左->上，下->左，右->下，top->右
public static void rotate(int[][] matrix, int n) {
for (int layer = 0; layer < n / 2; ++layer) {
int first = layer;
int last = n - 1 - layer;
for(int i = first; i < last; ++i) {
int offset = i - first;
int top = matrix[first][i]; // save top
// left -> top
matrix[first][i] = matrix[last-offset][first];
// bottom -> left
matrix[last-offset][first] = matrix[last][last - offset];
// right -> bottom
matrix[last][last - offset] = matrix[i][last];
// top -> right
matrix[i][last] = top; // right <- saved top
}
}
}
Q7.编写一个算法，若MxN矩阵中某个元素为0，则将其所在的行与列清0.
Ans.思路
- 陷阱：不要直接处理，将某一行清0后，会导致整个矩阵为0
- 改进：遍历一遍矩阵，记住哪些行和哪些列为0；第二遍处理时，对于a[i][j]，只要行i和列j其中有一个为0，则置为0
- 改进：只用遍历一次即可，方法是将哪些行、列为0的标记标记在第一行和第一列中；对于第一行和第一列是否全为0，首先检查出来，做好标记，然后最后进行处理
public static void nullifyRow(int[][] matrix, int row) {
for (int j = 0; j < matrix[0].length; j++) {
matrix[row][j] = 0;
}
}
public static void nullifyColumn(int[][] matrix, int col) {
for (int i = 0; i < matrix.length; i++) {
matrix[i][col] = 0;
}
}
public static void setZeros(int[][] matrix) {
boolean[] row = new boolean[matrix.length];
boolean[] column = new boolean[matrix[0].length];
// Store the row and column index with value 0
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length;j++) {
if (matrix[i][j] == 0) {
row[i] = true;
column[j] = true;
}
}
}
// Nullify rows
for (int i = 0; i < row.length; i++) {
if (row[i]) {
nullifyRow(matrix, i);
}
}
// Nullify columns
for (int j = 0; j < column.length; j++) {
if (column[j]) {
nullifyColumn(matrix, j);
}
}
}
一次遍历即可：
public static void setZeros2(int[][] matrix) {
boolean rowHasZero = false;
boolean colHasZero = false;
// Check if first row has a zero
for (int j = 0; j < matrix[0].length; j++) {
if (matrix[0][j] == 0) {
rowHasZero = true;
break;
}
}
// Check if first column has a zero
for (int i = 0; i < matrix.length; i++) {
if (matrix[i][0] == 0) {
colHasZero = true;
break;
}
}
// Check for zeros in the rest of the array
for (int i = 1; i < matrix.length; i++) {
for (int j = 1; j < matrix[0].length;j++) {
if (matrix[i][j] == 0) {
matrix[i][0] = 0;
matrix[0][j] = 0;
}
}
}
// Nullify rows based on values in first column
for (int i = 1; i < matrix.length; i++) {
if (matrix[i][0] == 0) {
nullifyRow(matrix, i);
}
}
// Nullify columns based on values in first row
for (int j = 1; j < matrix[0].length; j++) {
if (matrix[0][j] == 0) {
nullifyColumn(matrix, j);
}
}
// Nullify first row
if (rowHasZero) {
nullifyRow(matrix, 0);
}
// Nullify first column
if (colHasZero) {
nullifyColumn(matrix, 0);
}
}
Q8.假定有一个方法isSubstring，可检查一个单词是否为其他字符串的子串，给定两个字符串s1和s2，请编写检查s2是否为s1旋转而来，只能调用一次isSubstring。（waterbottler是erbottlewat旋转后的字符串）
Ans.思路
- 在选择点进行切分：比如字符串xy选择后变成了yx。则必然有xyxy包含yx。
public static boolean isSubstring(String big, String small) {
if (big.indexOf(small) >= 0) {
return true;
} else {
return false;
}
}
public static boolean isRotation(String s1, String s2) {
int len = s1.length();
/* check that s1 and s2 are equal length and not empty */
if (len == s2.length() && len > 0) {
/* concatenate s1 and s1 within new buffer */
String s1s1 = s1 + s1;
return isSubstring(s1s1, s2);
}
return false;
}
Q9.打印输入文件的最后K行。
Ans.思路：
- 使用一个K大小的数组，依次存入0K-1行，1K行，...
- 使用循环式数组，每次读入新行，都会替换掉最早读入的元素。
Q10.珠玑妙算游戏。四种颜色。猜对某个槽的颜色，则算一次“猜中”，要是只猜对颜色但是槽位错了，算一次“伪猜中”，猜中不能算入伪猜中。
Ans.思路：
- 猜中要先剔除
public static class Result {
public int hits;
public int pseudoHits;
public Result(int h, int p) {
hits = h;
pseudoHits = p;
}
public Result() {
}
public String toString() {
return "(" + hits + ", " + pseudoHits + ")";
}
};
public static int code(char c) {
switch (c) {
case 'B':
return 0;
case 'G':
return 1;
case 'R':
return 2;
case 'Y':
return 3;
default:
return -1;
}
}
public static int MAX_COLORS = 4;
public static Result estimate(String guess, String solution) {
if (guess.length() != solution.length()) return null;
Result res = new Result();
int[] frequencies = new int[MAX_COLORS];
/* Compute hits and built frequency table */
for (int i = 0; i < guess.length(); i++) {
if (guess.charAt(i) == solution.charAt(i)) {
res.hits++;
} else {
/* Only increment the frequency table (which will be used for pseudo-hits) if
* it's not a hit. If it's a hit, the slot has already been "used." */
int code = code(solution.charAt(i));
if (code >= 0) {
frequencies[code]++;
}
}
}
/* Compute pseudo-hits */
for (int i = 0; i < guess.length(); i++) {
int code = code(guess.charAt(i));
if (code >= 0 && frequencies[code] > 0 && guess.charAt(i) != solution.charAt(i)) {
res.pseudoHits++;
frequencies[code]--;
}
}
return res;
}
Q11.给定一个整数数组，编写一个函数，找出索引m和n，只要将m和n之间的元素排好序，整个数组就是有序的。注意：n-m越小越好，也就是说，找出符号条件的最短序列。
Ans.思路：
- step1.首先找出首尾最长递增子序列
- step2.然后将min取值为 中间+右边最小 中最小者，以此最小值将中间向左推进到<=该最小值的下一位，能保证左边的所有都小于右边
- step3.同理max取值为 中间+左边最大 中最大者，以此最大值将中间向右推进到>=该最大值的上一位，能保证右边的所有都大于左边
- 此题本质上要求left < middle < right
public class Question {
public static int findEndOfLeftSubsequence(int[] array) {
for (int i = 1; i < array.length; i++) {
if (array[i] < array[i - 1]) {
return i - 1;
}
}
return array.length - 1;
}
public static int findStartOfRightSubsequence(int[] array) {
for (int i = array.length - 2; i >= 0; i--) {
if (array[i] > array[i + 1]) {
return i + 1;
}
}
return 0;
}
public static int shrinkLeft(int[] array, int min_index, int start) {
int comp = array[min_index];
for (int i = start - 1; i >= 0; i--) {
if (array[i] <= comp) {
return i + 1;
}
}
return 0;
}
public static int shrinkRight(int[] array, int max_index, int start) {
int comp = array[max_index];
for (int i = start; i < array.length; i++) {
if (array[i] >= comp) {
return i - 1;
}
}
return array.length - 1;
}
public static void findUnsortedSequence(int[] array) {
// find left subsequence
int end_left = findEndOfLeftSubsequence(array);
if (end_left >= array.length - 1) {
//System.out.println("The array is already sorted.");
return; // Already sorted
}
// find right subsequence
int start_right = findStartOfRightSubsequence(array);
int max_index = end_left; // max of left side
int min_index = start_right; // min of right side
for (int i = end_left + 1; i < start_right; i++) {
if (array[i] < array[min_index]) {
min_index = i;
}
if (array[i] > array[max_index]) {
max_index = i;
}
}
// slide left until less than array[min_index]
int left_index = shrinkLeft(array, min_index, end_left);
// slide right until greater than array[max_index]
int right_index = shrinkRight(array, max_index, start_right);
if (validate(array, left_index, right_index)) {
System.out.println("TRUE: " + left_index + " " + right_index);
} else {
System.out.println("FALSE: " + left_index + " " + right_index);
}
}
/* Validate that sorting between these indices will sort the array. Note that this is not a complete
* validation, as it does not check if these are the best possible indices.
*/
public static boolean validate(int[] array, int left_index, int right_index) {
int[] middle = new int[right_index - left_index + 1];
for (int i = left_index; i <= right_index; i++) {
middle[i - left_index] = array[i];
}
java.util.Arrays.sort(middle);
for (int i = left_index; i <= right_index; i++) {
array[i] = middle[i - left_index];
}
for (int i = 1; i < array.length; i++) {
if (array[i-1] > array[i]) {
return false;
}
}
return true;
}
public static void main(String[] args) {
int[] array = {1, 2, 4, 7, 10, 11, 8, 12, 5, 7, 16, 18, 19};
findUnsortedSequence(array);
}
}
Q12.给定一个整数，打印该整数的英文描述。
Ans.思路：
- 分段处理，每三位转换一次，并在适当的时候插入相应的thousand、million、hundred等
public class Question {
public static String[] digits = {"One", "Two", "Three", "Four", "Five", "Six", "Seven", "Eight", "Nine"};
public static String[] teens = {"Eleven", "Twelve", "Thirteen", "Fourteen", "Fifteen", "Sixteen", "Seventeen", "Eighteen", "Nineteen"};
public static String[] tens = {"Ten", "Twenty", "Thirty", "Forty", "Fifty", "Sixty", "Seventy", "Eighty", "Ninety"};
public static String[] bigs = {"", "Thousand", "Million", "Billion"};
public static String numToString(int number) {
if (number == 0) {
return "Zero";
}
if (number < 0) {
return "Negative " + numToString(-1 * number);
}
int count = 0;
String str = "";
while (number > 0) {
if (number % 1000 != 0) {
str = numToString100(number % 1000) + bigs[count] + " " + str;
}
number /= 1000;
count++;
}
return str;
}
public static String numToString100(int number) {
String str = "";
/* Convert hundreds place */
if (number >= 100) {
str += digits[number / 100 - 1] + " Hundred ";
number %= 100;
}
/* Convert tens place */
if (number >= 11 && number <= 19) {
return str + teens[number - 11] + " ";
} else if (number == 10 || number >= 20) {
str += tens[number / 10 - 1] + " ";
number %= 10;
}
/* Convert ones place */
if (number >= 1 && number <= 9) {
str += digits[number - 1] + " ";
}
return str;
}
public static void main(String[] args) {
/* numbers between 100000 and 1000000 */
for (int i = 0; i < 8; i++) {
int value = (int) Math.pow(10, i);
String s = numToString(-1 * value);
System.out.println(value + ": " + s);
}
/* numbers between 0 and 100 */
for (int i = 0; i < 10; i++) {
int value = AssortedMethods.randomIntInRange(0, 100);
String s = numToString(value);
System.out.println(value + ": " + s);
}
/* numbers between 100 and 1000 */
for (int i = 0; i < 10; i++) {
int value = AssortedMethods.randomIntInRange(100, 1000);
String s = numToString(value);
System.out.println(value + ": " + s);
}
/* numbers between 1000 and 100000 */
for (int i = 0; i < 10; i++) {
int value = AssortedMethods.randomIntInRange(1000, 100000);
String s = numToString(value);
System.out.println(value + ": " + s);
}
/* numbers between 100000 and 100000000 */
for (int i = 0; i < 10; i++) {
int value = AssortedMethods.randomIntInRange(100000, 100000000);
String s = numToString(value);
System.out.println(value + ": " + s);
}
/* numbers between 100000000 and 1000000000 */
for (int i = 0; i < 10; i++) {
int value = AssortedMethods.randomIntInRange(100000000, 1000000000);
String s = numToString(value);
System.out.println(value + ": " + s);
}
/* numbers between 1000000000 and Integer.MAX_VALUE */
for (int i = 0; i < 10; i++) {
int value = AssortedMethods.randomIntInRange(1000000000, Integer.MAX_VALUE);
String s = numToString(value);
System.out.println(value + ": " + s);
}
}
}
Q13.给定一个整数数组（有正数、负数），找出总和最大的连续数列，并返回综合。
Ans.思路：
- 只要当前和为正数，就可以连续加下去；若累积为负数，则重新开始，否则会拖累后面的计算，因为去掉前面的负数累赘，后面的求和会更大。
public static int getMaxSum(int[] a) {
int maxSum = 0;
int runningSum = 0;
for (int i = 0; i < a.length; i++) {
runningSum += a[i];
if (maxSum < runningSum) {
maxSum = runningSum;
} else if (runningSum < 0) {
runningSum = 0;
}
}
return maxSum;
}
Q14.设计一个算法，找出数组中两数之和为指定值的所有整数对。
Ans.思路：
- 使用散列表
- 对于排好序的数组，可以使用first和last指向头和尾进行查找
public static void printPairSums(int[] array, int sum) {
Arrays.sort(array);
int first = 0;
int last = array.length - 1;
while (first < last) {
int s = array[first] + array[last];
if (s == sum) {
System.out.println(array[first] + " " + array[last]);
++first;
--last;
} else {
if (s < sum) {
++first;
} else {
--last;
}
}
}
}
Q15.有个内含单词的超大文本文件，给定任意两个单词，找出在这个文件中这两个单词的最短距离。有办法在O(1)时间内完成搜索操作吗？解法的空间复杂度如何？
Ans.思路：
- 普通做法，从前向后遍历，不断更新min
- 对于需要经常调用的，可以生成hash表，记录每个单词及其出现的位置。然后计算两个链表中最短的距离。做法跟普通做法类似。
public static int shortest(String[] words, String word1, String word2) {
int min = Integer.MAX_VALUE;
int lastPosWord1 = -1;
int lastPosWord2 = -1;
for (int i = 0; i < words.length; i++) {
String currentWord = words[i];
if (currentWord.equals(word1)) {
lastPosWord1 = i;
// Comment following 3 lines if word order matters
int distance = lastPosWord1 - lastPosWord2;
if (lastPosWord2 >= 0 && min > distance) {
min = distance;
}
} else if (currentWord.equals(word2)) {
lastPosWord2 = i;
int distance = lastPosWord2 - lastPosWord1;
if (lastPosWord1 >= 0 && min > distance) {
min = distance;
}
}
}
return min;
}
Q16.给定一组单词，编写一个程序，找出其中的最长单词，且该单词由这组单词中的其他单词组合而成。
Ans.思路：
- 先将单词放入哈希表，然后从最长单词开始，将每个单词分解为可能的两半，然后检查左右两半是否在列表中。
- 若单词可以由任意数量的其他单词组成，又会怎么样？
递归检查右半部分是否由数组其他元素构建出来。
public static String printLongestWord(String arr[]) {
HashMap<String, Boolean> map = new HashMap<String, Boolean>();
for (String str : arr) {
map.put(str, true);
}
Arrays.sort(arr, new LengthComparator()); // Sort by length
for (String s : arr) {
if (canBuildWord(s, true, map)) {
System.out.println(s);
return s;
}
}
return "";
}
public static boolean canBuildWord(String str, boolean isOriginalWord, HashMap<String, Boolean> map) {
if (map.containsKey(str) && !isOriginalWord) {
return map.get(str);
}
for (int i = 1; i < str.length(); i++) {
String left = str.substring(0, i);
String right = str.substring(i);
if (map.containsKey(left) && map.get(left) == true &&
canBuildWord(right, false, map)) {
return true;
}
}
map.put(str, false);
return false;
}
public class LengthComparator implements Comparator<String> {
public int compare(String o1, String o2) {
if (o1.length() < o2.length()) return 1;
if (o1.length() > o2.length()) return -1;
return 0;
}
}
Q17.给定一个字符串s和一个包含较短字符串的数组T，设计一个方法，根据T中的每个较短字符串，对s进行搜索。
Ans.思路：
- 创建s的后缀树，例如bibs
-
注意indexes，indexes表示该后缀分支的起始索引，多个表示有多个起始索引都为该值。
public class SuffixTree {
SuffixTreeNode root = new SuffixTreeNode();
public SuffixTree(String s) {
for (int i = 0; i < s.length(); i++) {
String suffix = s.substring(i);
root.insertString(suffix, i);
}
}
public ArrayList<Integer> search(String s) {
return root.search(s);
}
}
public class SuffixTreeNode {
HashMap<Character, SuffixTreeNode> children = new HashMap<Character, SuffixTreeNode>();
char value;
ArrayList<Integer> indexes = new ArrayList<Integer>();
public SuffixTreeNode() { }
public void insertString(String s, int index) {
indexes.add(index);
if (s != null && s.length() > 0) {
value = s.charAt(0);
SuffixTreeNode child = null;
if (children.containsKey(value)) {
child = children.get(value);
} else {
child = new SuffixTreeNode();
children.put(value, child);
}
String remainder = s.substring(1);
child.insertString(remainder, index);
}
}
public ArrayList<Integer> search(String s) {
if (s == null || s.length() == 0) {
return indexes;
} else {
char first = s.charAt(0);
if (children.containsKey(first)) {
String remainder = s.substring(1);
return children.get(first).search(remainder);
}
}
return null;
}
}
Q18.给定字典里的两个单词，长度相等，编写一个方法，将一个单词变换成另一个单词，一次只改动一个字母。在变换过程中，每一步得到的新单词都必须是字典里存在的。
Ans.思路：
- 可以使用广度优先搜索，每次相差一个字符。
public static LinkedList<String> transform(String startWord, String stopWord, Set<String> dictionary) {
startWord = startWord.toUpperCase();
stopWord = stopWord.toUpperCase();
Queue<String> actionQueue = new LinkedList<String>();
Set<String> visitedSet = new HashSet<String>();
Map<String, String> backtrackMap = new TreeMap<String, String>();
actionQueue.add(startWord);
visitedSet.add(startWord);
while (!actionQueue.isEmpty()) {
String w = actionQueue.poll();
// For each possible word v from w with one edit operation
for (String v : getOneEditWords(w)) {
if (v.equals(stopWord)) {
// Found our word! Now, back track.
LinkedList<String> list = new LinkedList<String>();
// Append v to list
list.add(v);
while (w != null) {
list.add(0, w);
w = backtrackMap.get(w);
}
return list;
}
// If v is a dictionary word
if (dictionary.contains(v)) {
if (!visitedSet.contains(v)) {
actionQueue.add(v);
visitedSet.add(v); // mark visited
backtrackMap.put(v, w);
}
}
}
}
return null;
}
private static Set<String> getOneEditWords(String word) {
Set<String> words = new TreeSet<String>();
// for every letter
for (int i = 0; i < word.length(); i++) {
char[] wordArray = word.toCharArray();
// change that letter to something else
for (char c = 'A'; c <= 'Z'; c++) {
if (c != word.charAt(i)) {
wordArray[i] = c;
words.add(new String(wordArray));
}
}
}
return words;
}
public static HashSet<String> setupDictionary(String[] words) {
HashSet<String> hash = new HashSet<String>();
for (String word : words) {
hash.add(word.toUpperCase());
}
return hash;
}
Q19.给定一个方阵，其中每个单元非黑即白。设计一个算法，找出四条边皆为黑色像素的最大子方阵。
Ans.思路：
- 一种简单思路，穷举法——从NxN逐渐递减查找 (N-1)x(N-1) ...，时间复杂度为O(N^4)，大范围要遍历N次，小范围，例如N/2 x N/2，有N/2 x N/2种可能性，检查N/2 x 4周长才能确定，所以O(N3)，总共为O(N4)
- 预处理：穷举每次检查一个方阵是否符合要求，都需要O(N)时间，经过预处理，可以将其降为O(1)。
处理的方法：记住每一个点右边最长黑边和下边最长的黑边。
穷举法：
public static Subsquare findSquare(int[][] matrix){
assert(matrix.length > 0);
for (int row = 0; row < matrix.length; row++){
assert(matrix[row].length == matrix.length);
}
int N = matrix.length;
for (int i = N; i >= 1; i--) {
Subsquare square = findSquareWithSize(matrix, i);
if (square != null) {
return square;
}
}
return null;
}
public static Subsquare findSquareWithSize(int[][] matrix, int squareSize) {
// On an edge of length N, there are (N - sz + 1) squares of length sz.
int count = matrix.length - squareSize + 1;
// Iterate through all squares with side length square_size.
for (int row = 0; row < count; row++) {
for (int col = 0; col < count; col++) {
if (isSquare(matrix, row, col, squareSize)) {
return new Subsquare(row, col, squareSize);
}
}
}
return null;
}
private static boolean isSquare(int[][] matrix, int row, int col, int size) {
// Check top and bottom border.
for (int j = 0; j < size; j++){
if (matrix[row][col+j] == 1) {
return false;
}
if (matrix[row+size-1][col+j] == 1) {
return false;
}
}
// Check left and right border.
for (int i = 1; i < size - 1; i++) {
if (matrix[row+i][col] == 1){
return false;
}
if (matrix[row+i][col+size-1] == 1) {
return false;
}
}
return true;
}
public class Subsquare {
public int row, column, size;
public Subsquare(int r, int c, int sz) {
row = r;
column = c;
size = sz;
}
public void print() {
System.out.println("(" + row + ", " + column + ", " + size + ")");
}
}
预处理法：
public static Subsquare findSquare(int[][] matrix){
assert(matrix.length > 0);
for (int row = 0; row < matrix.length; row++){
assert(matrix[row].length == matrix.length);
}
SquareCell[][] processed = processSquare(matrix);
int N = matrix.length;
for (int i = N; i >= 1; i--) {
Subsquare square = findSquareWithSize(processed, i);
if (square != null) {
return square;
}
}
return null;
}
public static Subsquare findSquareWithSize(SquareCell[][] processed, int square_size) {
// On an edge of length N, there are (N - sz + 1) squares of length sz.
int count = processed.length - square_size + 1;
// Iterate through all squares with side length square_size.
for (int row = 0; row < count; row++) {
for (int col = 0; col < count; col++) {
if (isSquare(processed, row, col, square_size)) {
return new Subsquare(row, col, square_size);
}
}
}
return null;
}
private static boolean isSquare(SquareCell[][] matrix, int row, int col, int size) {
SquareCell topLeft = matrix[row][col];
SquareCell topRight = matrix[row][col + size - 1];
SquareCell bottomRight = matrix[row + size - 1][col];
if (topLeft.zerosRight < size) { // Check top edge
return false;
}
if (topLeft.zerosBelow < size) { // Check left edge
return false;
}
if (topRight.zerosBelow < size) { // Check right edge
return false;
}
if (bottomRight.zerosRight < size) { // Check bottom edge
return false;
}
return true;
}
public static SquareCell[][] processSquare(int[][] matrix) {
SquareCell[][] processed = new SquareCell[matrix.length][matrix.length];
for (int r = matrix.length - 1; r >= 0; r--) {
for (int c = matrix.length - 1; c >= 0; c--) {
int rightZeros = 0;
int belowZeros = 0;
if (matrix[r][c] == 0) { // only need to process if it's a black cell
rightZeros++;
belowZeros++;
if (c + 1 < matrix.length) { // next column over is on same row
SquareCell previous = processed[r][c + 1];
rightZeros += previous.zerosRight;
}
if (r + 1 < matrix.length) {
SquareCell previous = processed[r + 1][c];
belowZeros += previous.zerosBelow;
}
}
processed[r][c] = new SquareCell(rightZeros, belowZeros);
}
}
return processed;
}
public class SquareCell {
public int zerosRight = 0;
public int zerosBelow = 0;
public SquareCell(int right, int below) {
zerosRight = right;
zerosBelow = below;
}
public void setZerosRight(int right) {
zerosRight = right;
}
public void setZerosBelow(int below) {
zerosBelow = below;
}
}
Q20.给定一个正整数和负整数组成的NxN矩阵，编写代码找出元素总和最大的子矩阵。
Ans.思路：
- 暴力法：迭代O(N^4)个子矩阵，然后计算每个子矩阵的总和用时O(N^2)，总时间复杂度为O(N^6)。
- 将每个矩阵和计算的时间降为O(1)，可以预先处理好这些值O(N^4)
- 给定一个整数数组，找出元素总和最大的子数组。可以在O(N)时间内找到和最大的子数组。O(N^3)
预处理：
public static int getMaxMatrix(int[][] original) {
int maxArea = Integer.MIN_VALUE; // Important! Max could be < 0
int rowCount = original.length;
int columnCount = original[0].length;
int[][] matrix = precomputeMatrix(original);
for (int row1 = 0; row1 < rowCount; row1++) {
for (int row2 = row1; row2 < rowCount; row2++) {
for (int col1 = 0; col1 < columnCount; col1++) {
for (int col2 = col1; col2 < columnCount; col2++) {
int sum = computeSum(matrix, row1, row2, col1, col2);
if (sum > maxArea) {
System.out.println("New Max of " + sum + ": (rows " + row1 + " to " + row2 + ") and (columns " + col1 + " to " + col2 + ")");
maxArea = sum;
}
}
}
}
}
return maxArea;
}
private static int[][] precomputeMatrix(int[][] matrix) {
int[][] sumMatrix = new int[matrix.length][matrix[0].length];
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
if (i == 0 && j == 0) { // first cell
sumMatrix[i][j] = matrix[i][j];
} else if (j == 0) { // cell in first column
sumMatrix[i][j] = sumMatrix[i - 1][j] + matrix[i][j];
} else if (i == 0) { // cell in first row
sumMatrix[i][j] = sumMatrix[i][j - 1] + matrix[i][j];
} else {
sumMatrix[i][j] = sumMatrix[i - 1][j] +
sumMatrix[i][j - 1] - sumMatrix[i - 1][j - 1] +
matrix[i][j];
}
}
}
return sumMatrix;
}
private static int computeSum(int[][] sumMatrix, int i1, int i2,
int j1, int j2) {
if (i1 == 0 && j1 == 0) { // starts at row 0, column 0
return sumMatrix[i2][j2];
} else if (i1 == 0) { // starts at row 0
return sumMatrix[i2][j2] - sumMatrix[i2][j1 - 1];
} else if (j1 == 0) { // starts at column 0
return sumMatrix[i2][j2] - sumMatrix[i1 - 1][j2];
} else {
return sumMatrix[i2][j2] - sumMatrix[i2][j1 - 1] - sumMatrix[i1 - 1][j2] + sumMatrix[i1 - 1][j1 - 1];
}
}
使用O(n)计算最大子数组和：
public static void clearArray(int[] array) {
for (int i = 0; i < array.length; i++) {
array[i] = 0;
}
}
public static int maxSubMatrix(int[][] matrix) {
int rowCount = matrix.length;
int colCount = matrix[0].length;
int[] partialSum = new int[colCount];
int maxSum = 0; // Max sum is an empty matrix
for (int rowStart = 0; rowStart < rowCount; rowStart++) {
clearArray(partialSum);
for (int rowEnd = rowStart; rowEnd < rowCount; rowEnd++) {
for (int i = 0; i < colCount; i++) {
partialSum[i] += matrix[rowEnd][i];
}
int tempMaxSum = maxSubArray(partialSum, colCount);
// if you want to track the coordinates, add code here to do that
maxSum = Math.max(maxSum, tempMaxSum);
}
}
return maxSum;
}
public static int maxSubArray(int array[], int N) {
int maxSum = 0;
int runningSum = 0;
for (int i = 0; i < N; i++) {
runningSum += array[i];
maxSum = Math.max(maxSum, runningSum);
/* If running_sum is < 0 no point in trying to continue the
* series. Reset. */
if (runningSum < 0) {
runningSum = 0;
}
}
return maxSum;
}
Q21.给定一份几百万个单词的清单，设计一个算法，创建由字母组成的最大矩形，其中每一行组成一个单词（自左向右），每一列组成一个单词（自上向下）。不要求这些单词在清单里连续出现，但要求所有行等长，所有列等高。
Ans.思路：
- 预处理：将字典按单词长短进行分组。
- 对于查找，可以用trie树
- 典型的回溯法，穷举某个长度的情况，然后借助trie树检查高度是否符合
step1.将单词按长度分组
public class Question {
private int maxWordLength;
private WordGroup[] groupList ;
private Trie trieList[];
public Question(String[] list) {
groupList = WordGroup.createWordGroups(list);
maxWordLength = groupList.length;
// Initialize trieList to store trie of groupList[i] at ith position.
trieList = new Trie[maxWordLength];
}
step2.从可能最大面积矩形开始，然后面积依次减一，第一个成功构建的必定是最大的
public Rectangle maxRectangle() {
// The dimensions of the largest possible rectangle.
int maxSize = maxWordLength * maxWordLength;
for (int z = maxSize; z > 0; z--) {
// Find out all pairs i,j less than maxWordLength
// such that i * j = z
for (int i = 1; i <= maxWordLength; i ++ ) {
if (z % i == 0) {
int j = z / i;
if (j <= maxWordLength) {
// Check if a Rectangle of length i and height
// j can be created.
Rectangle rectangle = makeRectangle(i,j);
if (rectangle != null) {
return rectangle;
}
}
}
}
}
return null;
}
step3.构造指定长度和高度的矩形
private Rectangle makeRectangle(int length, int height) {
if (groupList[length - 1] == null || groupList[height - 1] == null) {
return null;
}
if (trieList[height - 1] == null) {
ArrayList<String> words = groupList[height - 1].getWords();
trieList[height - 1] = new Trie(words);
}
return makePartialRectangle(length, height, new Rectangle(length));
}
step4.深度优先遍历解空间，分支为该长度所有可能性
private Rectangle makePartialRectangle(int l, int h, Rectangle rectangle) {
// Check if we have formed a complete rectangle by seeing if each column
// is in the dictionary
if (rectangle.height == h) {
if (rectangle.isComplete(l, h, groupList[h - 1])) {
return rectangle;
} else {
return null;
}
}
// If the rectangle is not empty, validate that each column is a
// substring of a word of length h in the dictionary using the
// trie of words of length h.
if (!rectangle.isPartialOK(l, trieList[h - 1])) {
return null;
}
// For each word of length l, try to make a new rectangle by adding
// the word to the existing rectangle.
for (int i = 0; i < groupList[l-1].length(); i++) {
Rectangle orgPlus = rectangle.append(groupList[l-1].getWord(i));
Rectangle rect = makePartialRectangle(l, h, orgPlus);
if (rect != null) {
return rect;
}
}
return null;
}
参考
- Cracking the coidng interview. 5th
