当前位置: 首页 > article >正文

【面试经典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是空字符串时返回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());
    }
}

 


http://www.kler.cn/a/372267.html

相关文章:

  • 使用 Mermaid 语言描述 AGI 系统架构图
  • spring容器的启动流程
  • 怎么理解ES6 Proxy
  • 将多个commit合并成一个commit并提交
  • 【每日刷题】Day145
  • 基于uniapp微信小程序的校园二手书交易系统
  • PostgreSQL 清理 WAL 文件
  • 2024“源鲁杯“高校网络安全技能大赛-Misc-WP
  • 逆变器竞品分析--绿联150W方案【2024/10/30】
  • Docker搭建官方私有仓库registry及相关配置
  • 基于树莓派的安保巡逻机器人--(一、快速人脸录入与精准人脸识别)
  • DGUS屏使用方法
  • 易至狂欢购车季火热开启,EV3青春版打造年轻一代出行新选择
  • 【MMIN】缺失模态想象网络用于不确定缺失模态的情绪识别
  • 相关矩阵图——Python实现
  • 【Android】Kotlin教程(4)
  • Ubuntu20.04安装VM tools并实现主机和虚拟机之间文件夹共享
  • 基于微信小程序的小区管理系统设计与实现(lw+演示+源码+运行)
  • uniapp跨域问题,在开发环境中配置
  • Unity(四十八):Unity与Web双向交互
  • Spring Cloud 微服务全面概述
  • 【系统面试篇】简述进程调度算法
  • CTF-PWN: 虚表(vtable)
  • Vue学习记录之二十二 Vue3+vite+electron 构建项目实例
  • 别被忽悠了 Lua 数组真的也可以从 0 开始索引?
  • 10 最长回文子串、买卖股票的最好时机(一)、[NOIP2002 普及组] 过河卒24_10_30