最近在看 《程序员面试金典》，感觉书中的一些算法非常的精妙，所以本人对书中的每一个题目都着手实现了一遍，为了以后能够方便的重温这个知识，也为了能够将这个算法分享给 没看过这本书的小伙伴，于是本人决定将这些题目和算法写下来，当然我也只是写下题目和解法，不会对解法进行分析，想看具体分析可以买一本纸质书看一下，非常不错的一本书。
1.1 实现一个算法，确定一个字符串的所有字符是否全都不同。假设不允许使用额外的数据结构，又该如何处理？
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) // 假设字符是 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++ 实现 void reverse(char* str) 函数，即翻转一个 null 结尾的字符串。
#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 实现的话，请用字符数组实现，以便直接在数组上进行操作)。
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 利用字符重复出现的次数，编写一个方法，实现基本的字符串压缩功能。比如，字符串 "aabcccccaaa" 会变为 “ 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 进行连接，减小时间开销
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 字节，编写一个方法，将图形旋转 90 度。不占用额外内存空间能否做到？
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++) { // 因为每次旋转会旋转两行两列，所以上限为 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 旋转而成，要求只能调用 一次 isSubstring。（比如，waterbottle 是 erbottlewat 旋转后的字符串）。
public boolean isRotation(String s1,String s2){
int length = s1.length();
if(length == s2.length() && length > 0){
String s1s1 = s1+s1; // 若s2 是由 s1 旋转而成，那么 s2 必然是 s1s1 的子串
return isSubstring(s1s1,s2);
}
return false;
}
再次声明，以上题目和算法均来自 《程序员面试金典》。
