程序员面试——数组与字符串韧还

importjava.util.*;publicclassDifferent{publicbooleancheckDifferent(StringiniString){for(inti=0;i

boolean[]index=newboolean[256];for(inti=0;i

1.2字符反转

无额外开销和无新数据结构；

stringbuffer的反转可以直接做，或者直接赋值就好；

importjava.util.*;publicclassReverse{publicStringreverseString(StringiniString){if(iniString.length()<=1)returniniString;StringBufferrev=newStringBuffer();for(inti=iniString.length()-1;i>=0;i--){rev.append(iniString.charAt(i));}returnrev.toString();//StringBuffershit=newStringBuffer(iniString);//returnshit.reverse().toString();}}

1.3乱序同构

给定两个字符串，请编写程序，确定其中一个字符串的字符重新排列后，能否变成另一个字符串。这里规定大小写为不同字符，且考虑字符串重点空格。

给定一个stringstringA和一个stringstringB，请返回一个bool，代表两串是否重新排列后可相同。保证两串的长度都小于等于5000。

"Thisisnowcoder","isThisnowcoder"返回：true"Hereyouare","Areyouhere"返回：false思路一：双循环，就把两个读到数组中，然后把2排列成1一模一样的情况

importjava.util.*;publicclassSame{publicbooleancheckSam(StringstringA,StringstringB){if(stringA.length()!=stringB.length())returnfalse;char[]dataA=stringA.toCharArray();char[]dataB=stringB.toCharArray();for(inti=0;i

思路二：ASCII码，记录每个字符出现次数；

细节：依然是输入控制，看长度是否相等；

1.4空格替换

"MrJohnSmith”,13返回："Mr%20John%20Smith"”HelloWorld”,12返回：”Hello%20%20World”直接做吧，或者讲究一点的就先算出有多少个空格，然后规定好长度；

importjava.util.*;publicclassReplacement{publicStringreplaceSpace(StringiniString,intlength){char[]data=iniString.toCharArray();char[]rt=newchar[length*3];intrtIndex=0;for(inti=0;i

细节：Stringsb=newString(rt);数组与字符串；字符串长度截取；

1.5基本字符串压缩

利用字符重复出现的次数，编写一个方法，实现基本的字符串压缩功能。比如，字符串“aabcccccaaa”经压缩会变成“a2b1c5a3”。若压缩后的字符串没有变短，则返回原先的字符串。

给定一个stringiniString为待压缩的串(长度小于等于10000)，保证串内字符均由大小写英文字母组成，返回一个string，为所求的压缩后或未变化的串。

"aabcccccaaa"返回："a2b1c5a3""welcometonowcoderrrrr"返回："welcometonowcoderrrrr"基本思路：快慢指针

importjava.util.*;publicclassZipper{publicStringzipString(StringiniString){StringBufferres=newStringBuffer();res.append(iniString.charAt(0));//res.append(1);intindex=0;intcount=1;intlen=iniString.length();charc=iniString.charAt(0);for(inti=1;i=iniString.length()){//returniniString;}else{res.append(count);res.append(iniString.charAt(i));count=1;c=iniString.charAt(i);index=index+2;}}res.append(count);return(index

不用count的写法

importjava.util.*;publicclassZipper{publicStringzipString(StringiniString){if(iniString.length()<=2)returniniString;StringBufferzip=newStringBuffer();intslow=0;//intcount=0;for(inti=1;i

细节：还是输入控制；另外注意所有情况；

1.6旋转矩阵

不用额外空间

找好对应关系，列式子

importjava.util.*;publicclassTransform{publicint[][]transformImage(int[][]mat,intn){intcenter=n/2;for(inti=0;i

1.7清楚行列

注意一点就可以，全部确定了再清楚，负责可能发生覆盖

类似1.1的方法，用boolean做标记

importjava.util.*;publicclassClearer{publicint[][]clearZero(int[][]mat,intn){boolean[]line=newboolean[n];boolean[]row=newboolean[n];//intlineIndex=0;//introwIndex=0;for(inti=0;i

1.8翻转子串

假定我们都知道非常高效的算法来检查一个单词是否为其他字符串的子串。请将这个算法编写成一个函数，给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成，要求只能调用一次检查子串的函数。

给定两个字符串s1,s2,请返回bool值代表s2是否由s1旋转而成。字符串中字符为英文字母和空格，区分大小写，字符串长度小于等于1000。

"Helloworld","worldhello"返回：false"waterbottle","erbottlewat"返回：true很巧妙地思路：合并两个，然后看是否包含

importjava.util.*;publicclassReverseEqual{publicbooleancheckReverseEqual(Strings1,Strings2){if(s1==null||s2==null||s1.length()!=s2.length())returnfalse;return(s1+s1).contains(s2);}}

---------------拓展-------------------

17.7数字发音(废物)

有一个非负整数，请编写一个算法，打印该整数的英文描述。

给定一个intx，请返回一个string，为该整数的英文描述。

1234返回："OneThousand,TwoHundredThirtyFour"就三位三位的取，所以没三位做成一个函数来做；

然后注意各个单词放在String[]中

17.8最大连续数列和

对于一个有正有负的整数数组，请找出总和最大的连续数列。

给定一个int数组A和数组大小n，请返回最大的连续数列的和。保证n的大小小于等于3000。

[1,2,3,-6,1]返回：6我的思路：找每一个正数当作起点，然后求和，得到max就好了！！

importjava.util.*;publicclassMaxSum{publicintgetMaxSum(int[]A,intn){if(n<=1)returnn;intqidian=0;intmax=0;for(inti=0;i0){qidian=i;inttmp=A[i];if(tmp>max){max=tmp;}//max=tmp;for(intj=qidian+1;jmax){max=tmp;}}}}returnmax;}}

书上的逻辑没懂，不过第一句话记住了：这题的难度不小（偷笑中）

11.6矩阵元素查找

有一个NxM的整数矩阵，矩阵的行和列都是从小到大有序的。请设计一个高效的查找算法，查找矩阵中元素x的位置。

给定一个int有序矩阵mat，同时给定矩阵的大小n和m以及需要查找的元素x，请返回一个二元数组，代表该元素的行号和列号(均从零开始)。保证元素互异。

[[1,2,3],[4,5,6]],2,3,6返回：[1,2]思路：实现一种折现查找，然后想到的用while

importjava.util.*;publicclassFinder{publicint[]findElement(int[][]mat,intn,intm,intx){int[]ret=newint[2];//if(n==1&&m==1)return[0,0];//intline=0;intlie=0;for(intline=0;line

当然书上的还要巧妙一些：

while(row=0){if(mat[row][col]==x){returntrue;}elseif(mat[row][col]>n){col--;}else{row++;}}returnfalse;

思路是差不多的，只是个人思路是直观一些，书上这个更加抽象~