1.實(shí)現(xiàn)一個(gè)算法，確定一個(gè)字符串的所有字符是否全都不同。假使不允許使用額外的數(shù)據(jù)結(jié)構(gòu)，又該怎么處理？

public class UniqueChars {public static void main(String[] args) {// TODO Auto-generated method stubString string = "abcdefgfedcba";System.out.print(isUniqueChars(string));}public static boolean isUniqueChars(String str) {if (str.length() > 256) {return false;}boolean[] char_set = new boolean[256];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;}} View Code

注意：向面試官確認(rèn)上面的字符串是ASCII字符串還是Unicode字符串。若不是ASCII字符串需擴(kuò)大存儲(chǔ)空間，但其余邏輯不變。

? ? ? ? ? 這里假定是ASCII字符串。首先做一個(gè)優(yōu)化，若字符串長(zhǎng)度大于字母表中的字符個(gè)數(shù)，就直接返回false。畢竟，若字母表只有256個(gè)字符，字符串里就不可能有280個(gè)各不相同的字符。

? ? ? ? ? ?然后構(gòu)建一個(gè)布爾值的數(shù)組，索引值i對(duì)應(yīng)的標(biāo)記指示該字符串是否含有字母表第i個(gè)字符。若這個(gè)字符第二次出現(xiàn)，則立即返回false。時(shí)間復(fù)雜度o(n),空間復(fù)雜度o(1)。

若不允許使用額外的數(shù)據(jù)結(jié)構(gòu)：

（1）將字符串中的每一個(gè)字符與其余字符進(jìn)行比較。時(shí)間復(fù)雜度為o(n2)，空間復(fù)雜度o(1)。

public class UniqueChars {public static void main(String[] args) {// TODO Auto-generated method stubString string = "abcdefgfedcba";System.out.print(isUniqueChars(string));}public static boolean isUniqueChars(String str) {if (str.length() > 256) {return false;}for(int i = 0; i < str.length(); i++) {for(int j = i + 1; j < str.length(); j++) {if(str.charAt(i) == str.charAt(j)) return false;}}return true;} } View Code

（2）若允許修改輸入字符串，可以在o(nlogn)的時(shí)間里對(duì)字符串排序，然后線性檢查其中有無相鄰字符完全相同的情況。

2.用Java實(shí)現(xiàn)void reverse(char* str)函數(shù)，即反轉(zhuǎn)一個(gè)null結(jié)尾的字符串。

package ArrayAndString;public class Reverse {public static void main(String[] args) {// TODO Auto-generated method stubString string = "abcdefg";System.out.println(reverseString2(string));}//最簡(jiǎn)單的方法public static String reverseString(String iniString) {// write code hereStringBuffer tmp = new StringBuffer(iniString);tmp = tmp.reverse();return tmp.toString();}//最常用的方法public static String reverseString2(String iniString) { char[] array = iniString.toCharArray(); String reverse = ""; //注意這是空串，不是nullfor (int i = array.length - 1; i >= 0; i--) { reverse += array[i];}return reverse; } } View Code

3.給定兩個(gè)字符串，請(qǐng)編寫程序，確定其中一個(gè)字符串的字符重新排列后，能否變成另一個(gè)字符串。

解法一：對(duì)字符串排序后進(jìn)行比較，若它們擁有相同順序的字符，即互為變位詞。

import java.util.*;public class IsAnagram {public static void main(String[] args) {// TODO Auto-generated method stubString string1 = "aceg";String string2 = "cega";System.out.println(permutation(string1, string2)); }public static String sort(String s) {char[] content = s.toCharArray();Arrays.sort(content);return new String(content);}public static boolean permutation(String s, String t) {if (s.length() != t.length()) {return false;}return sort(s).equals(sort(t));}} View Code

解法二：利用變位詞的定義--組成兩個(gè)單詞的字符數(shù)相同，遍歷字母表，計(jì)算每個(gè)字符出現(xiàn)的次數(shù)，然后比較這兩個(gè)數(shù)組。

public class IsAnagram {public static void main(String[] args) {// TODO Auto-generated method stubString string1 = "aceg";String string2 = "cega";System.out.println(permutation(string1, string2)); }public static boolean permutation(String s, String t) {if (s.length() != t.length()) {return false;}int[] letters = new int[256];char[] s_array = s.toCharArray();for (char c : s_array) {letters[c]++;}for (int i = 0; i < t.length(); i++) {int c = (int) t.charAt(i);if (--letters[c] < 0) {return false;}}return true;}} View Code

注意：向面試官確認(rèn) 變位詞是否區(qū)分大小寫 以及 是否要考慮空白字符。

? ? ? ? ? 這里假定變位詞比較區(qū)分大小寫，空白也要考慮在內(nèi)，是ASCII字符串。首先做一個(gè)優(yōu)化，比較兩個(gè)字符串的長(zhǎng)度，只要長(zhǎng)度不同就不可能是變位詞。

4.編寫一個(gè)方法，將字符串中的空格全部替換為“%20”。假定該字符串尾部有足夠的空間存放新增字符，并且知道字符串的“真實(shí)”長(zhǎng)度。（注：用Java實(shí)現(xiàn)的話，請(qǐng)使用字符數(shù)組實(shí)現(xiàn)，以便直接在數(shù)組上操作。）

思路：進(jìn)行兩次掃描。第一次掃描先數(shù)出字符串中有多少空格，從而算出最終的字符串有多長(zhǎng)。第二次掃描真正開始反向編輯字符串，檢測(cè)到空格則將%20復(fù)制到下一個(gè)位置，若不是空白，就復(fù)制原先的字符。

public class ReplaceString {public static void main(String[] args) {// TODO Auto-generated method stubString str = "abc d e f";char[] arr = new char[str.length() + 3 * 2 + 1];for (int i = 0; i < str.length(); i++) {arr[i] = str.charAt(i);}replaceSpaces(arr, str.length()); System.out.println("\"" + charArrayToString(arr) + "\"");}public static String charArrayToString(char[] array) {StringBuilder buffer = new StringBuilder(array.length);for (char c : array) {if (c == 0) {break;}buffer.append(c);}return buffer.toString();}public static void replaceSpaces(char[] str, int length) {int spaceCount = 0;int index = 0; int 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--;}}}} View Code

注意：處理字符串操作問題時(shí)，常見做法是從字符串尾部開始編輯，從后往前反向操作。因?yàn)樽址膊坑蓄~外的緩沖，可以直接修改，不必?fù)?dān)心會(huì)復(fù)寫原有數(shù)據(jù)。

5.利用字符重復(fù)出現(xiàn)的次數(shù)，編寫一個(gè)方法，實(shí)現(xiàn)基本的字符串壓縮功能。比如，字符串a(chǎn)abcccccaaa會(huì)變成a2b1c5a3。若“壓縮”后的字符串沒有變短，則返回原先的字符串。

public class StringZipper {public static void main(String[] args) {// TODO Auto-generated method stubString str = "aabccccaaa";System.out.println(compressString(str));}public static String compressString(String str) {if (str.length() == 0) {return str;}int flag = 0;int count = 1;StringBuffer sb = new StringBuffer();char last = str.charAt(0);for (int i = 1; i < str.length(); i++) {if (str.charAt(i) == last) {count++;flag = 1;} else {sb.append(last);sb.append(count);last = str.charAt(i);count = 1;}}sb.append(last);sb.append(count);if (flag == 0 || sb.length() >= str.length()) {return str;} else {return sb.toString();}}} View Code

注意：使用flag變量記錄字符串中是否有重復(fù)字符。若最終flag=0說明字符串中無重復(fù)字符，返回原字符串。時(shí)間復(fù)雜度和空間復(fù)雜度都為o(N)。

6.給定一幅由N*N矩陣表示的圖像，其中每個(gè)像素的大小為4字節(jié)，編寫一個(gè)方法，將圖像旋轉(zhuǎn)90度。不占用額外內(nèi)存空間能否做到？

二維數(shù)組a[n][n]順時(shí)針旋轉(zhuǎn)90度，找規(guī)律如下：

當(dāng)n=1時(shí)，不動(dòng)。當(dāng)n=2時(shí)，有：a[0][0] = a[1][0]? a[1][0] = a[1][1]??a[1][1] = a[0][1]??a[0][1] = a[0][0]??初步總結(jié)規(guī)律為：a[i][j] = a[n-1-j][i]

當(dāng)n=3，4，5,……時(shí)也是滿足的。到這里，如果不考慮空間復(fù)雜度，只需要再構(gòu)建一個(gè)二維數(shù)組b[n][n]，利用公式b[i][j] = a[n-1-j][i]就可以解決。代碼如下：

public void rotate(int[][] matrix) {int n = matrix.length;int[][] m = new int[n][n];for(int row=0;row<n;row++){for(int col=0;col<n;col++){m[row][col] = matrix[n-1-col][row];}}//再賦值回matrix，注意java是形參是引用傳遞for(int row=0;row<n;row++){for(int col=0;col<n;col++){matrix[row][col] = m[row][col];}}} View Code

但是題目要求不占用額外空間，應(yīng)該怎么旋轉(zhuǎn)？接著上面的分析，以n=3為例：把焦點(diǎn)放在一個(gè)元素的旋轉(zhuǎn)上，可以看出要在原數(shù)組中旋轉(zhuǎn)，在不丟失數(shù)據(jù)的情況下，每個(gè)值的旋轉(zhuǎn)會(huì)“波及”4個(gè)數(shù)，以1為例波及到了1,3,7,9，每個(gè)數(shù)旋轉(zhuǎn)要不丟失數(shù)據(jù)就要考慮如何讓這4個(gè)數(shù)都得以保留。前邊總結(jié)了規(guī)律a[i][j] = a[n-1-j][i]，分析每組被波及的數(shù)，我們可以得出這里波及了的4個(gè)數(shù)其實(shí)就是a[i][j]? a[n-1-j][i]??a[n-1-i][n-1-j]??a[n-1-(n-1-j)][n-1-i]=a[j][n-1-i]?所以這里需要引入一個(gè)臨時(shí)變量temp就可以解決這4個(gè)數(shù)的順時(shí)針交換，如：

?int temp = matrix[i][j];

matrix[i][j] = matrix[n-1-j][i];

matrix[n-1-j][i] = matrix[n-1-i][n-1-j];

matrix[n-1-i][n-1-j] = matrix[j][n-1-i];

matrix[j][n-1-i] = temp;

把焦點(diǎn)放在一個(gè)元素上，數(shù)交換的問題解決了。那么現(xiàn)在把焦點(diǎn)回到整個(gè)二維數(shù)組上來，每個(gè)數(shù)的旋轉(zhuǎn)會(huì)波及4個(gè)數(shù)，相當(dāng)于用上面的方法，每旋轉(zhuǎn)一個(gè)數(shù)，就把一組的4個(gè)數(shù)都旋轉(zhuǎn)了，

所以現(xiàn)在的問題就是如何才能完整的把所有的數(shù)都旋轉(zhuǎn)90度且不會(huì)多旋轉(zhuǎn)，繼續(xù)分析：

n=1時(shí)，不需旋轉(zhuǎn)。

n=2時(shí)，只需要完成1（a[0][0]）的旋轉(zhuǎn)，就完成了整個(gè)數(shù)組的旋轉(zhuǎn)。

n=3時(shí)，需要完成1,2（a[0][0],a[0][1]）的旋轉(zhuǎn)，就完成了整個(gè)數(shù)組的旋轉(zhuǎn)。

n=4時(shí)，需要完成1,2,3,6（a[0][0至3]，a[1][1]）的旋轉(zhuǎn)。

n=5時(shí)，需要完成(a[0][0至4]，a[1][1至2])的旋轉(zhuǎn)。

大致可以總結(jié)出這么一個(gè)規(guī)律：對(duì)于要旋轉(zhuǎn)的數(shù)a[i][j]滿足，i<n/2?且?i<=j<n-1-i，至此問題終于解決。

public class Rotate {public static void main(String[] args) {// TODO Auto-generated method stubint[][] arr = {{1,2,3}, {4,5,6}, {7,8,9}};int length = arr.length;int[][] arr1 = transform(arr, length);for(int i = 0; i < length; ++i) {for(int j = 0; j < length; ++j) {System.out.print(arr1[i][j]+" ");}}}public static int[][] transform(int[][]matrix, int n) {int limit = n / 2;for (int i = 0; i < limit; i++) {for(int j = i; j < n - i - 1; j++) {int temp = matrix[i][j];matrix[i][j] = matrix[n-1-j][i];matrix[n-1-j][i] = matrix[n-1-i][n-1-j];matrix[n-1-i][n-1-j] = matrix[j][n-1-i];matrix[j][n-1-i] = temp;}}return matrix;}} View Code

算法的時(shí)間復(fù)雜度為o(N的平方)，已經(jīng)是最優(yōu)做法。

7.編寫一個(gè)算法，若M*N矩陣中某個(gè)元素位0，則將其所在的行與列清零。

public class ClearZeros {public static void main(String[] args) {// TODO Auto-generated method stubint[][] arr = {{1,2,0}, {4,5,6}, {7,8,9}};int[][] arr1 = setZeros(arr);for(int i = 0; i < arr.length; ++i) {for(int j = 0; j < arr[0].length; ++j) {System.out.print(arr1[i][j]+" ");}}}public static int[][] setZeros(int[][] matrix) {boolean[] row = new boolean[matrix.length];boolean[] column = new boolean[matrix[0].length];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;}}}for (int i = 0; i < matrix.length; i++) {for (int j = 0; j < matrix[0].length; j++) {if (row[i] || column[j]) {matrix[i][j] = 0;}}}return matrix;}} View Code

注意：不能在第一次遍歷整個(gè)矩陣時(shí)，發(fā)現(xiàn)值為零的元素就直接將其所在的行與列清零，這樣的話最后整個(gè)矩陣的所有元素都會(huì)變?yōu)榱?。要新建一個(gè)矩陣標(biāo)記零元素的位置，在第二次遍歷矩陣時(shí)將零元素所在的行與列清零。而且只需記錄哪行和哪列有零元素即可，無須記錄零元素的確切位置。

8.假定有一個(gè)方法isSubstring，可檢查一個(gè)單詞是否為其他字符串的子串。給定兩個(gè)字符串s1和s2,請(qǐng)編寫代碼檢查s2是否為s1旋轉(zhuǎn)而成，要求只能調(diào)用一次isSubstring。（比如，waterbottle是erbottlewat旋轉(zhuǎn)后的字符串）。

public class IsRotation {public static void main(String[] args) {// TODO Auto-generated method stubSystem.out.println(isRotation("abc","abc"));}public static boolean isSubstring(String str1,String str2){if(str1.contains(str2) || str2.contains(str1)) {return true;}return false;}public static boolean isRotation(String str1,String str2){if(str1.length() != str2.length()) {return false;}String sum = str1 + str1;return isSubstring(sum, str2);}} View Code

注意：假定s2由s1旋轉(zhuǎn)而成，那么將s1切分成x和y，就會(huì)滿足xy=s1和yx=s2。不論x和y之間的分割點(diǎn)在哪，yx都肯定是xyxy的子串，也即s2總是s1s1的子串。直接調(diào)用isSubstring(s1s1,s2)即可。

轉(zhuǎn)載于:https://www.cnblogs.com/struggleli/p/7815584.html

總結(jié)

以上是生活随笔為你收集整理的ArrayAndString（数组和字符串）的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。