剣指Offer-文字列
スペースを置換
テーマの説明
関数を実行して、文字列の空白を「%20」に置き換えてください。例えば、文字列がWe Aree Happyである場合、置換された文字列はWe%20 Aree%20 Happyである。時間制限：1秒 空間制限：32768 K コード
剣指のOfferの本の中のテーマは入参のフォーマットが異なっていることを求めて、そのため実現の方法も異なっています。
《剣の指Offer》-コード
テーマの説明
''''と'*'を含む正規表現にマッチする関数を実装してください。モード中の文字'''は任意の文字を表し、'*'はその前の文字が任意の回数(0回を含む)であることを示します。本題では、マッチングとは文字列のすべての文字がモードにマッチすることです。例えば、文字列「a a」はモード「a.a」と「ab＊ac＊a」と整合しているが、「aa.a」と「ab＊a」は一致していない。時間制限：1秒 空間制限：32768 K コード
テーマの説明
1つの関数を使用して、1回だけの文字が流れているものを探してください。例えば、前の2文字「go」だけが文字ストリームから読み出されると、最初の1回だけ出現する文字は「g」となります。前の6文字の「google」をこの文字の流れから読み出すと、最初の1回だけ出てくる文字は「l」です。時間制限：1秒 空間制限：32768 K ここの256は「剣指Offer」の8位のcharタイプです。
コード
テーマの説明
文字列が数値（整数と小数を含む）を示すかどうかを判定する関数を実装してください。例えば、文字列「+100」、「5 e 2」、「-123」、「3.1416」、「-1 E-16」は数値を表します。しかし、「12 e」、「1 a 3.14」、「1.2.3」、「+-5」、「12 e+4.3」は全部違います。時間制限：1秒 空間制限：32768 K コード
列挙の方式、多くのifネスティング、感じはあまり良くありません。冗長です。でも、確かに問題を解くことができます。
コード2
「コンパイル原理の自動機」を使って実現できるという話があります。筋道がはっきりしていていいです。
結び目
上記のいくつかの問題の境界問題の処理方法に注意してください。null、空の文字列、要求に符合しない、要求に符合する、複数がテーマの要求に符合する場合、自分で相応の文字列を書いてテストを行うことができ、プログラムに異常が発生して崩壊することを防止する。
タイトルがシンプルであることはコードが簡単であることを意味しない。
テーマの説明
関数を実行して、文字列の空白を「%20」に置き換えてください。例えば、文字列がWe Aree Happyである場合、置換された文字列はWe%20 Aree%20 Happyである。
/**
* @author Think
* @since 2016-12-19 11:18:00
*/
public class Solution {
public String replaceSpace(StringBuffer str) {
int tar = 32;
String des = "%20";
StringBuffer reStr = new StringBuffer();
for (int i=0;ichar c = str.charAt(i);
if (tar == c){
reStr.append(des);
}else {
reStr.append(c);
}
}
return reStr.toString();
}
public static void main(String[] args) {
StringBuffer in = new StringBuffer("We Are Happy");
System.out.println(new Solution().replaceSpace(in));
}
} 剣指のOfferの本の中のテーマは入参のフォーマットが異なっていることを求めて、そのため実現の方法も異なっています。
void ReplaceBlank(char string[], int length){
//TODO
}《剣の指Offer》-コード
public class Solution {
public static void main(String[] args) {
int length = 20;
char[] string = new char[length];
String str = "We are happy";
for (int i = 0; i < str.length(); i++) {
string[i] = str.charAt(i);
}
int pos = 0;
while (string[pos]!='\0'){
System.out.print(string[pos++]);
}
System.out.println();
Solution solution = new Solution();
solution.ReplaceBlank(string, length);
pos = 0;
while (string[pos]!='\0'){
System.out.print(string[pos++]);
}
}
public void ReplaceBlank(char[] string, int length) {
if (string == null || length <= 0) {
return;
}
int originalLength = 0;
int numberOfBlank = 0;
int i = 0;
while (string[i] != '\0') {
originalLength++;
if (string[i] == ' ') {
numberOfBlank++;
}
i++;
}
int newLength = originalLength + 2 * numberOfBlank;
// length ， newLength length， 。
if (newLength > length) {
return;
}
int indexOdOriginal = originalLength;
int indexOfNew = newLength;
while (indexOdOriginal >= 0 && indexOfNew > indexOdOriginal) {
if (string[indexOdOriginal] == ' ') {
string[indexOfNew--] = '0';
string[indexOfNew--] = '2';
string[indexOfNew--] = '%';
} else {
string[indexOfNew--] = string[indexOdOriginal];
}
indexOdOriginal--;
}
}
}テーマの説明
''''と'*'を含む正規表現にマッチする関数を実装してください。モード中の文字'''は任意の文字を表し、'*'はその前の文字が任意の回数(0回を含む)であることを示します。本題では、マッチングとは文字列のすべての文字がモードにマッチすることです。例えば、文字列「a a」はモード「a.a」と「ab＊ac＊a」と整合しているが、「aa.a」と「ab＊a」は一致していない。
public class Solution {
public static void main(String[] args) {
char[] s = "aa".toCharArray();
char[] patten = "a*".toCharArray();
Solution solution = new Solution();
boolean result = solution.match(s, patten);
System.out.println(result);
}
public boolean match(char[] str, char[] pattern) {
if (str == null || pattern == null) {
return false;
}
int i = 0, j = 0;
return matchTwo(str, i, pattern, j);
}
// ""/"."/"*"/".*"/a*a ， 。
boolean matchTwo(char[] str, int i, char[] pattern, int j) {
int len1 = str.length;
int len2 = pattern.length;
// Str pattern ， 。
if (i == len1 && j == len2) {
return true;
}
// str ， pattern ， 。
// ， str ， pattern ， 。
// ：pattern * ， 0 。
if (i < len1 && j == len2) {
return false;
}
// pattern *：* pattern 。
// - *， 。
// 1 0 ， pattern 2 。
// 2 1 ， ，pattern * ，j ；
// 3 1 ，pattern 2 。
// ，2 3 。 2 3，
// true， || ， 。
// ， 。
// (j+1)
if ((j + 1) < len2 && pattern[j + 1] == '*') {
if ((i < len1 && pattern[j] == '.') || (i < len1 && str[i] == pattern[j])) {
return matchTwo(str, i, pattern, j + 2) ||
matchTwo(str, i + 1, pattern, j) ||
matchTwo(str, i + 1, pattern, j + 2);
} else {
return matchTwo(str, i, pattern, j + 2);
}
} else {
if ((i < len1 && pattern[j] == '.') || (i < len1 && str[i] == pattern[j])) {
return matchTwo(str, i + 1, pattern, j + 1);
} else {
return false;
}
}
}
} テーマの説明
1つの関数を使用して、1回だけの文字が流れているものを探してください。例えば、前の2文字「go」だけが文字ストリームから読み出されると、最初の1回だけ出現する文字は「g」となります。前の6文字の「google」をこの文字の流れから読み出すと、最初の1回だけ出てくる文字は「l」です。
コード
public class Solution {
public static void main(String[] args) {
Solution solution = new Solution();
// String str = "google";
// String str = "";
// String str = "aabbcc";
String str = "think";
for (int i=0;iint charTable[] = new int[256];
StringBuffer sb = new StringBuffer();
//Insert one char from stringstream
public void Insert(char ch) {
sb.append(ch);
if (ch >= 256) {
return;
}
charTable[ch]+=1;
}
//return the first appearence once char in current stringstream
public char FirstAppearingOnce() {
char defaultCh = '#';
char charStr[] = sb.toString().toCharArray();
for (int i=0;iif (charTable[charStr[i]]==1){
return charStr[i];
}
}
return defaultCh;
}
} テーマの説明
文字列が数値（整数と小数を含む）を示すかどうかを判定する関数を実装してください。例えば、文字列「+100」、「5 e 2」、「-123」、「3.1416」、「-1 E-16」は数値を表します。しかし、「12 e」、「1 a 3.14」、「1.2.3」、「+-5」、「12 e+4.3」は全部違います。
列挙の方式、多くのifネスティング、感じはあまり良くありません。冗長です。でも、確かに問題を解くことができます。
public class Solution {
public static void main(String[] args) {
Solution solution = new Solution();
// True for: "+100","5e2","-123","3.1416" and "-1E-16"
// False for: "12e","1a3.14","1.2.3","+-5" and "12e+4.3"
// Other test case: +.123, 1+23,
char[] str = "1+23".toCharArray();
System.out.println(solution.isNumeric(str));
}
public boolean isNumeric(char[] str) {
int numOfPoint = 0;
if (str == null) {
return false;
}
int index = 0;
if (str[index] == '+' || str[index] == '-') {
index = 1;
if (!isNumber(str[index]) && str[index] != '.') {
return false;
}
}
for (int i = index; i < str.length; i++) {
if (str[i] == 'e' || str[i] == 'E') {
if ((i + 1) < str.length && (str[i + 1] == '+' || str[i + 1] == '-') && (i + 2) < str.length && isNumber(str[i + 2])) {
index = i + 3;
break;
} else if ((i + 1) < str.length && isNumber(str[i + 1])) {
index = i + 2;
break;
} else {
return false;
}
} else if (str[i] == '.') {
numOfPoint++;
if (numOfPoint > 1) {
return false;
}
} else {
if (!isNumber(str[i])) {
return false;
}
}
index = i;
}
for (int i = index; i < str.length; i++) {
if (!isNumber(str[i])) {
return false;
}
}
if (numOfPoint > 1) {
return false;
}
return true;
}
public boolean isNumber(char ch) {
if (ch < '0' || ch > '9') {
return false;
} else {
return true;
}
}
}コード2
public class Solution {
public boolean isNumeric(char[] str) {
String s=String.valueOf(str);
//return s.matches("[+-]?[0-9]*(.[0-9]*)?([eE][+-]?[0-9]+)?");
return s.matches("[+-]?[0-9]*(\\.[0-9]*)?([eE][+-]?[0-9]+)?");
}
}「コンパイル原理の自動機」を使って実現できるという話があります。筋道がはっきりしていていいです。
結び目
上記のいくつかの問題の境界問題の処理方法に注意してください。null、空の文字列、要求に符合しない、要求に符合する、複数がテーマの要求に符合する場合、自分で相応の文字列を書いてテストを行うことができ、プログラムに異常が発生して崩壊することを防止する。
タイトルがシンプルであることはコードが簡単であることを意味しない。