配列と文字列に関するアルゴリズム
最近は『プログラマー面接金典』を読んでいますが、本の中のアルゴリズムはとても素晴らしいと思います.だから、本の中のすべてのテーマに対して一度実現しました.これからも便利にこの知識を復習するために、このアルゴリズムをこの本を見たことがない仲間に共有するために、これらのテーマとアルゴリズムを書いてみます.もちろん私もテーマと解法だけを書いて、解法に対して分析することはできません.具体的な分析を見たいです.紙の本を買ってみてもいいです.
1.1アルゴリズムを実行して、文字列のすべての文字が異なるかどうかを決定する.追加のデータ構造の使用が許されないとしたら、どう処理すればいいですか?
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;
}
}
#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;
}
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;
}
}
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);
}
}
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;
}
}
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; //
}
}
}
}
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();
}
}
}
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;
}