【面试经典150】day 9

目录

1.Z 字形变换 

2.找出字符串中第一个匹配项的下标

3.文本左右对齐

1.Z 字形变换 

class Solution {public String convert(String s, int numRows) {//明明是N字形变换if(numRows<2) return s;//rows是可扩展的字符串数组List<StringBuilder>rows=new ArrayList<StringBuilder>();for(int i=0;i<numRows;i++) rows.add(new StringBuilder());int i=0,flag=-1;for(char c:s.toCharArray()){rows.get(i).append(c);if(i==0||i==numRows-1) flag=-flag;i+=flag;}StringBuilder ret=new StringBuilder();for(StringBuilder row:rows) ret.append(row);return ret.toString();}
}

2.找出字符串中第一个匹配项的下标

KMP匹配算法 

我爱卡尔

class Solution {public int strStr(String haystack, String needle) {//KMP算法int m=needle.length();//当needle是空字符串时返回0if(m==0){return 0;}int n=haystack.length();if(n<m){return -1;}int i=0;int j=0;while(i<n-m+1){//找到首字母相等while(i<n&&haystack.charAt(i)!=needle.charAt(j)){i++;}if(i==n){//没有首字母相等的return -1;}//遍历后续字符，判断是否相等i++;j++;while(i<n&&j<m&&haystack.charAt(i)==needle.charAt(j)){i++;j++;}if(j==m){//找到return i-j;}else{//未找到i-=j-1;j=0;}}return -1;}
}

3.文本左右对齐

class Solution {//答案列表List<String> ret=new ArrayList<>();//记录每个单词的长度，方便后续补齐空格操作int [] lens;//替代maxWidth,减少函数传参int maxRowLen;public List<String> fullJustify(String[] words, int maxWidth) {maxRowLen=maxWidth;int n=words.length;//1.记录每个单词的长度lens=new int[n];for(int i=0;i<n;i++){lens[i]=words[i].length();}//2.单词分组，确定哪写单词在哪行int rowLen=0;for(int i=0;i<n;i++){int start=i;while(i<n&&rowLen+lens[i]<=maxRowLen){rowLen+=(lens[i]+1);i++;}int end=--i;//[start,end]对应的单词组成一行，加入答案addAns(words,start,end);rowLen=0;}return ret;}private void addAns(String[] words,int start,int end){StringBuilder sb=new StringBuilder();//情况一：一行只有一个单词，直接空格补齐if(start==end){sb.append(words[start]);int space=maxRowLen-lens[start];for(int j=1;j<=space;j++){sb.append(" ");}ret.add(sb.toString());return;}//情况二：如果是最后一行，左对齐，即每个单词间一个空格，最后空格补齐if(end==words.length-1){int space=maxRowLen;for(int i=start;i<end;i++){sb.append(words[i]).append(" ");space-=(lens[i]+1);}sb.append(words[end]);space-=lens[end];for(int j=1;j<=space;j++){sb.append(" ");}ret.add(sb.toString());return;}//情况三：一般情况// 思路：统计要插入的总空格数spaceAll //      -> 计算单词间能够平分的空格数spaceMean//      -> 计算剩余空格数spaceLast，并从前往后分配// 总空格数int spaceAll=maxRowLen;for(int i=start;i<=end;i++){spaceAll-=lens[i];}  //平均空格数int spaceMean=spaceAll/(end-start);//剩余空格数int spaceLast=spaceAll-spaceMean* (end - start);for (int i = start; i < end; i++) {sb.append(words[i]);// 在每个单词后面插入平均空格数for (int j = 1; j <= spaceMean; j++) {sb.append(" ");}// 如果有剩余空格数，插一个if (spaceLast > 0) {sb.append(" ");spaceLast--;}}sb.append(words[end]);ret.add(sb.toString());}
}