秋招笔试题—力扣—程序员面试金典（第六版）

seven_ • 2023年2月23日下午1:15 • 后端漫谈 • 阅读 195

一次编辑

字符串有三种编辑操作:插入一个英文字符、删除一个英文字符或者替换一个英文字符。给定两个字符串，编写一个函数判定它们是否只需要一次(或者零次)编辑。

Test :

package com.test3;

public class Test {
    public static void main(String[] args) {
        boolean de=oneEditAway("parse","pars");
        System.out.println("输出结果："+de);
    }

    //定义方法：判断能否进行一次编辑
    public static boolean oneEditAway(String first,String second){
        int m = first.length(),n = second.length();
        if(n - m == 1){
            return oneInsert(first,second);
        }else if( m - n == 1){
            return oneInsert(second,first);
        }else if( m == n ){
            boolean foundDifference = false;
            for (int i = 0; i < m; i++) {
                if(first.charAt(i) != second.charAt(i)){
                    if(!foundDifference){
                        foundDifference = true;
                    }else {
                        return false;
                    }
                }
            }
            return true;
        }else {
            return false;
        }

    }

    //定义方法：用来判断是否满足一次性的删除或插入或修改
    public static boolean oneInsert(String shorter,String longer){
        int length1 = shorter.length(),length2=longer.length();
        int index1 = 0,index2 = 0;
        while ( index1 < length1 && index2 < length2 ){
            if(shorter.charAt(index1) == longer.charAt(index2)){
                index1++;
            }
            index2++;
            if(index2 - index1 > 1){
                return false;
            }
        }
        return  true;
    }
}

运行结果：

盛最多水的容器

Test2 :

package com.test3;

public class Test2 {
    public static void main(String[] args) {
        int[] height={1,8,6,2,5,4,8,3,7};
        int maxAArea=maxArea(height);
        System.out.println("输出结果："+maxAArea);
    }
    public static int maxArea(int[] height) {
        // int maxarea=0;
        // for(int i=0;i<height.length;i++){
        //     for(int j=i+1;j<height.length;j++){
        //         maxarea=Math.max(maxarea,Math.min(height[i],height[j])*(j-i));
        //     }
        // }
        // return maxarea;  //执行时间超时

        int maxarea=0,l=0,r=height.length-1;
        while(l<r){
            maxarea=Math.max(maxarea,Math.min(height[l],height[r])*(r-l));
            if(height[l]<height[r]){
                l++;
            }else{
                r--;
            }
        }
        return maxarea;
    }
}