【面试经典150】day 9

1. 

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.

class Solution {
    public int strStr(String haystack, String needle) {
        //KMP算法
        int m=needle.length();
        //当needle是空字符串时返回0
        if(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());
    }
}