最近在看 《程序員面試金典》，感覺書中的一些算法非常的精妙布卡，所以本人對書中的每一個題目都著手實現(xiàn)了一遍，為了以后能夠方便的重溫這個知識惊来，也為了能夠?qū)⑦@個算法分享給 沒看過這本書的小伙伴攀痊，于是本人決定將這些題目和算法寫下來桐腌，當(dāng)然我也只是寫下題目和解法，不會對解法進(jìn)行分析苟径，想看具體分析可以買一本紙質(zhì)書看一下案站，非常不錯的一本書。
1.1 實現(xiàn)一個算法涩笤，確定一個字符串的所有字符是否全都不同蛾坯。假設(shè)不允許使用額外的數(shù)據(jù)結(jié)構(gòu)匈睁，又該如何處理寸潦？
public class UniqueCharCheck {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
String data = input.nextLine();
boolean result = isUniqueChar(data);
System.out.println(result);
input.close();
}
private static boolean isUniqueChar(String data) {
if (data.length() > 256) // 假設(shè)字符是 ASCII 字符
return false;
boolean[] check = new boolean[256];
for (int i = 0; i < data.length(); i++) {
int v = data.charAt(i);
if (check[v])
return false;
check[v] = true;
}
return true;
}
}
1.2 用 C/C++ 實現(xiàn) void reverse(char* str) 函數(shù)避凝，即翻轉(zhuǎn)一個 null 結(jié)尾的字符串。
#include<iostream>
using namespace std;
void reverse(char *str);
int main()
{
char s[100];
cin>>s;
reverse(s);
cout<<s<<endl;
return 0;
}
void reverse(char *str)
{
char *end = str;
char *start = str;
while(*end)
++end;
--end;
while(start < end)
{
char temp = *start;
*start++ = *end;
*end-- = temp;
}
return;
}
1.3 給定兩個字符串恩沽，請編寫程序誊稚，確定其中一個字符串的字符重新排列后，能否變成另一個字符串罗心。
public class EqualCheck {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
String v = input.nextLine();
String t = input.nextLine();
input.close();
System.out.println(permutation(v, t));
}
public static String sort(String s) {
char[] array = s.toCharArray();
java.util.Arrays.sort(array);
return new String(array);
}
// 這是第一種方法
public static boolean compare(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 check[] = new int[256];
for (int i = 0; i < s.length(); i++) {
int v = s.charAt(i);
check[v]++;
}
for (int i = 0; i < t.length(); i++) {
int v = t.charAt(i);
if (--check[v] < 0)
return false;
}
return true;
}
}
1.4 編寫一個方法里伯，將字符串中的空格全部替換成 “ %20”，假定字符串尾部有足夠的空間存放新增字符渤闷，并且知道字符串的 “ 真實” 長度疾瓮。(注: 用 Java 實現(xiàn)的話，請用字符數(shù)組實現(xiàn)飒箭，以便直接在數(shù)組上進(jìn)行操作)狼电。
public class ReplaceSpace {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
String s = input.nextLine();
s = replace(s);
System.out.println(s);
input.close();
}
public static String replace(String s) {
int count = 0;
for (int i = 0; i < s.length(); i++) {
if (s.charAt(i) == ' ')
count++;
}
int newLength = s.length() + count * 2;
char array[] = new char[newLength];
for (int i = s.length() - 1; i >= 0; i--) {
char t = s.charAt(i);
if (t == ' ') {
array[newLength - 1] = '0';
array[newLength - 2] = '2';
array[newLength - 3] = '%';
newLength -= 3;
} else {
array[newLength - 1] = t;
newLength -= 1;
}
}
return new String(array);
}
}
1.5 利用字符重復(fù)出現(xiàn)的次數(shù)，編寫一個方法弦蹂，實現(xiàn)基本的字符串壓縮功能肩碟。比如，字符串 "aabcccccaaa" 會變?yōu)?“ a2b1c5a3”凸椿，若“壓縮”后的字符串沒有變短削祈，則返回原先的字符串。
public class ZipStringData {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
String s = input.nextLine();
s = zip(s);
System.out.println(s);
input.close();
}
private static String zip(String s) {
int size = check(s); // 壓縮后的字符串長度
if (size >= s.length()) // 如果壓縮后的字符串長度大于等于原來的長度，直接返回原字符串
return s;
StringBuilder builder = new StringBuilder(); // 使用 StringBuilder 進(jìn)行連接髓抑，減小時間開銷
char last = s.charAt(0);
int count = 1;
for (int i = 1; i < s.length(); i++) {
if (last == s.charAt(i))
count++;
else {
builder.append(last + "" + count);
last = s.charAt(i);
count = 1;
}
}
builder.append(last + "" + count);
return builder.toString();
}
// 用于計算壓縮后的字符串長度
private static int check(String s) {
int size = 0;
char last = s.charAt(0);
int count = 1;
for (int i = 1; i < s.length(); i++) {
if (s.charAt(i) == last) {
count++;
} else {
size += 1 + String.valueOf(count).length();
last = s.charAt(i);
count = 1;
}
}
size += 1 + String.valueOf(count).length();
return size;
}
}
1.6 給定一副由 N×N 矩陣表示的圖像咙崎，其中每個像素的大小為 4 字節(jié)，編寫一個方法启昧，將圖形旋轉(zhuǎn) 90 度叙凡。不占用額外內(nèi)存空間能否做到？
public class MatrixRotate {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int[][] matrix;
int n = input.nextInt();
matrix = new int[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = input.nextInt();
}
}
show(matrix);
rotate(matrix, n);
show(matrix);
input.close();
}
public static void show(int[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
public static void rotate(int[][] matrix, int n) {
for (int layer = 0; layer < n / 2; layer++) { // 因為每次旋轉(zhuǎn)會旋轉(zhuǎn)兩行兩列密末，所以上限為 n/2
int first = layer;
int last = n - layer - 1;
for (int i = first; i < last; i++) {
int offset = i - first;
int top = matrix[first][i]; //保存上邊元素值
matrix[first][i] = matrix[last - offset][first]; // 左邊覆蓋上邊
matrix[last - offset][first] = matrix[last][last - offset]; //下邊覆蓋左邊
matrix[last][last - offset] = matrix[offset][last]; // 右邊覆蓋下邊
matrix[offset][last] = top; // 將保存的值覆蓋到下邊
}
}
}
}
1.7 編寫一個算法，若 M × N 矩陣中的某個元素為 0 跛璧，則將其所在的行與列置為 0严里。
public class ResetMatrix {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
int m = input.nextInt();
int n = input.nextInt();
int[][] matrix = new int[m][n];
boolean[] row = new boolean[matrix.length];
boolean[] column = new boolean[(matrix[0].length)];
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
matrix[i][j] = input.nextInt();
if (matrix[i][j] == 0) {
row[i] = true;
column[j] = true;
}
}
}
show(matrix);
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (row[i] || column[j]) {
matrix[i][j] = 0;
}
}
}
show(matrix);
}
public static void show(int[][] matrix) {
for (int i = 0; i < matrix.length; i++) {
for (int j = 0; j < matrix[0].length; j++) {
System.out.print(matrix[i][j] + " ");
}
System.out.println();
}
}
}
1.8 假定有一個方法 isSubstring ， 可檢查一個單詞是否為其他字符串的子串追城。給定兩個兩個字符串 s1 和 s2刹碾，請編寫代碼檢查 s2 是否為 s1 旋轉(zhuǎn)而成，要求只能調(diào)用 一次 isSubstring座柱。（比如迷帜，waterbottle 是 erbottlewat 旋轉(zhuǎn)后的字符串）。
public boolean isRotation(String s1,String s2){
int length = s1.length();
if(length == s2.length() && length > 0){
String s1s1 = s1+s1; // 若s2 是由 s1 旋轉(zhuǎn)而成色洞，那么 s2 必然是 s1s1 的子串
return isSubstring(s1s1,s2);
}
return false;
}
再次聲明戏锹，以上題目和算法均來自 《程序員面試金典》。
