{ Cracking The Coding Interview: 150 programming QA } --- Arrays and Strings

本文主要是介绍{ Cracking The Coding Interview: 150 programming QA } --- Arrays and Strings，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

Hashtable, ArrayList (Dynamically resizing array, providing O(1) access), StringBuffer (do string concatenation)

1. 判断string是否有重复字符，不允许使用其他数据结构。

Step 1: 问清楚限制，string的编码是ASCII还是Unicode

a. 如果可以用其他数据结构，使用set把字符一个个加进去，add失败的时候即表示有重复。

b. 直接对每个字符，在剩余(substring)字符串中查找(contains)  

//O(1) O(n^n)public boolean hasUniqueChar(String str){if(str == null)return false;int len = str.length();for(int i = 0 ; i < len - 1; i ++){if(str.substring(i + 1).contains(str.subSequence(i, i + 1)))return false;}return true;}

c. 利用字符的有限性，设置bitmap； 如果字符都是 a~z，还可以缩减空间，用int，进行移位和与或操作来判断是否唯一。

//O(1) O(n)public boolean hasUniqueChar1(String str){if(str == null)return false;if(str.length() > 128)return false;//ASCII have 256 chars but only 128 are used widely, and 33 cannot be represented implicitly.boolean[] char_set = new boolean[256];for(int i = 0 ; i < str.length(); i ++){int val = str.charAt(i);if(char_set[val] == true)	//already found in stringreturn false;char_set[val] = true;}return true;}

d. 对字符数组进行排序，看看相邻字符是否相同。 时间复杂度至少 O（n）

2. C语言实现 reverse( char* str)

3. 判断字符串s1是不是s2的排列。

Step1:  ask charset, case sensitive, and whitespace significant.

a. 统计每种字符的个数，看看两个字符串的个数是不是都相同

//O(1) O(n)public boolean isPermu1(String s, String t) {if(s == null || t == null)return false;if(s.length() != t.length() || s.length() == 0 || t.length() == 0)return false;//calculate unique char counts.int[] letters = new int[256];for(int i = 0; i < s.length(); i ++){int val = (int) s.charAt(i); // char --> int ???letters[val] ++;}for(int i = 0 ; i < t.length(); i ++){int val = (int) t.charAt(i);letters[val] --;if(letters[val] < 0){return false;}}return true;}

b. 把字符数组排序，然后比较两个字符串是否相同

//O(n) O(n* log n)public boolean isPermu2(String s, String t) {if(s == null || t == null)return false;if(s.length() != t.length() || s.length() == 0 || t.length() == 0)return false;return sort(s).equals(sort(t));}private String sort(String str){char[] content = str.toCharArray();java.util.Arrays.sort(content);return new String(content);  // charset need be defined if use byte[]}

4. 把字符数组中的空格字符全部用 %20 替换。

a. 创建新的字符串保存原数组，然后扫描该字符串

	//O(n) O(n)public String replaceWhiteSpace(char[] arr, int len) {if(arr == null || len == 0)return null;int j = 0;String string = new String(arr);for(int i = 0; i < len; i ++){char ch = string.charAt(i);if(ch == ' '){arr[j ++] = '%';arr[j ++] = '2';arr[j ++] = '0';}else {arr[j ++] = ch;}}return new String(arr);}

b. 假设原字符数组的空间足够，可以就地扫描得到空白字符的个数，然后从后往前替换原数组。

//O(1) O(n)public String replaceWhiteSpace1(char[] arr, int len) {if(arr == null || len == 0)return null;int whiteSpaceCount = 0;for(int i = 0; i < len; i ++){if(arr[i] == ' ')whiteSpaceCount ++;}if(whiteSpaceCount == 0)return new String(arr);whiteSpaceCount = len + 2 * whiteSpaceCount;arr[whiteSpaceCount] = '\0';while(whiteSpaceCount > 0){char ch = arr[-- len];if(ch == ' '){arr[-- whiteSpaceCount] = '0';arr[-- whiteSpaceCount] = '2';arr[-- whiteSpaceCount] = '%';}else{arr[-- whiteSpaceCount] = ch;}}return new String(arr);}

5. 压缩重复的字符串，如果压缩不成功则返回原字符串。比如 111222， 返回1323

a. 暴力扫描，构建出压缩后的字符串

//O(n)   > O(n) because of StringBufferpublic String compressStr(String str) {if(str == null || str.length() == 0)return str;int len = str.length();char previous = str.charAt(0);StringBuffer sb = new StringBuffer();int count = 1;for(int i = 1; i < len; i ++){if(previous == str.charAt(i)){count ++;}else{sb.append(previous + "" + count);previous = str.charAt(i);count = 1;}}sb.append(previous + "" + count);if(sb.length() < len)return sb.toString();else return str;}

b. 先扫描一遍，看看需不需要构建压缩的字符串， 再用字符数组来存储压缩后的字符串

private int countCompress(String str){if(str == null || str.isEmpty()) return 0;char last = str.charAt(0);int size = 0;int count = 1;for(int i = 0; i < str.length(); i ++){if(str.charAt(i) == last)count ++;else{last = str.charAt(i);size = size + 1 + String.valueOf(count).length();count = 1;}}size = size + 1 + String.valueOf(count).length();return size;}//O(n)  O(n)public String compressStr2(String str) {int size = countCompress(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);}int setChar(char[] arr, char c, int index, int count){arr[index] = c;index ++;char[] cnt = String.valueOf(count).toCharArray();for(char ch:cnt){arr[index] = ch;index ++;}return index;}

6. 旋转N*N的矩阵

//O(1)   O(n * n)public void rotateRect(int[][] matrix, int N) {for(int layer = 0; layer < N/2; layer ++){//for each layer, rotate [first --> last] elementint first = layer;int last = N - 1 - layer;for(int i = first; i < last; i ++){// shows how index changed.int offset = i - first;int top = matrix[first][i];//left --> topmatrix[first][i] = matrix[last - offset][first];//bottom --> leftmatrix[last - offset][first] = matrix[last][last - offset];//right --> bottommatrix[last][last - offset] = matrix[i][last];//top --> rightmatrix[i][last] = top;}}}

7. 如果某个元素为0，那么设置在矩阵中同行同列所有元素为0.

//O(n)  O(n * m)public void setZeroMatrix(int[][] matrix, int m, int n){ArrayList<Integer> zeroRow = new ArrayList<Integer>();ArrayList<Integer> zeroCol = new ArrayList<Integer>();for(int i = 0; i < m; i ++){for(int j = 0; j < n; j ++){if(matrix[i][j] == 0){zeroRow.add(i);zeroCol.add(j);}}}for(int row : zeroRow){for(int j = 0; j < n; j ++)matrix[row][j] = 0;}for(int col : zeroCol){for(int i = 0; i < m; i ++)matrix[i][col] = 0;}}//Optimize to O(1) space:public void setZeroMatrix2(int[][] matrix, int m, int n){boolean rowHasZero = false;boolean colHasZero = false;//decide whether first row and column have zeros.for(int i = 0; i < m; i ++){if(matrix[i][0] == 0){rowHasZero = true;break;}}for(int i = 0; i < m; i ++){if(matrix[0][i] == 0){colHasZero = true;break;}}//see the rest of matrix and store flag in the first row or column.for(int i = 1; i < m; i ++){for(int j = 1; j < n; j ++){if(matrix[i][j] == 0){matrix[i][0] = 0;matrix[0][j] = 0;}}}for(int row = 0; row < m; row ++){if(matrix[row][0] == 0)for(int j = 0; j < n; j ++)matrix[row][j] = 0;}for(int col = 0; col < n; col ++){if(matrix[0][col] == 0)for(int i = 0; i < m; i ++)matrix[i][col] = 0;}if(rowHasZero == true)for(int j = 0; j < n; j ++)matrix[0][j] = 0;if(colHasZero == true)for(int i = 0; i < m; i ++)matrix[i][0] = 0;}

8. 只用一次isSubStr去判断一个字符串是不是另一个字符串的rotate形式。 比如 terwa 就是 water 的rotate形式。

/** If s2 is a rotation of s1, then* s1 = xy = water * x = wa* t = ter* s2 = yx = terwa* xyxy always contains yx.* so s2 should be a substring of s1s1.*/

这篇关于{ Cracking The Coding Interview: 150 programming QA } --- Arrays and Strings的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---