当前位置:   article > 正文

常见算法面试题_工小商给你一个长度为n的字符串s,包含若干个左花括号'{',右花括号'}'和小写字母。

工小商给你一个长度为n的字符串s,包含若干个左花括号'{',右花括号'}'和小写字母。

一个数组,求连续最大的和

给定一个数组,求出其中连续的最大的和

问题举例

 数组 {1,-4,10,5,-10,23}, 求出当前数组中最大的和,10+5+ -10 +23 = 28
 数组 {2,-10,4,9,-29,10}, 求出当前数组中最大的和,4+9=13
  • 1
  • 2

问题解析

已知数组,想求出连续最大和,先初始化最大值为数组第一个数字;
然后循环数组一直相加求连续和,每加完一个值,就用连续和  和 最大值进行比较,从新赋值;
求连续和的过程中,如果出现负数,则清0,原因,负数和后一个相加,肯定没有0和后一个相加数字大;
  • 1
  • 2
  • 3

代码

public int getSum(int[] arr){
	if(arr.length == 0)
		return 0;
	//用来记录最大和的值	
	int max = arr[1];
	//用来记录数组连续和
	int sum = 0;
	for(int i : arr){
		//计算 arr[0]+arr[1]+arr[2]+....  出现负数归零
		sum = Math.max(0,sum+i);
		//比较 arr[0]+arr[1]+arr[2]+.... 和当前最大值谁大
		max = Math.max(sum,max);
	}
	return max;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15

整数反转

将一个整数进行反转输出

问题举例

数字 1234,反转后为 4321;
数字 -1230,反转后为 -321;
  • 1
  • 2

问题解析

整数反转,可能会带来一个问题,就是反转后的数字超过了int类型的最大或最小值,代码多加一行判断,这种情况暂时不考虑;
进行反转,符号保留,那就从被反转整数的最后一个数字开始计算,计算方式为取模的方式
  • 1
  • 2

代码

public int reverse(int x){
	//用来记录反转后的整数
	int r = 0;
	while(x != 0){
		//x%10 取出原整数的最后一位数
		//r*10 是为了将反转后的数进位   3变成30    31变成310
		r = (r*10)+(x%10);
		//原整数去掉最后一位数字
		x/=10;
	}
	return r; 
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

回文数

回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数

问题举例

数字 1234,从后向前读4321,不是回文数;
数字 12321,从后向前读也是 12321,这是个回文数;
数字 1221,从后向前读也是 1221,这是个回文数;
数字 -121,从后向前读也是 121-,不是回文数;
  • 1
  • 2
  • 3
  • 4

问题解析

由回文数的本质可知,负数不能成文回文数,10的倍数不能成为回文数(10,40,3000);
判断回文数分为两种,一种是长度为偶数的整数,从中间分开,正好两边长度相同的数字去比较;
还有一种是长度为基数的,中间分开后,最中间的数据去掉,两边的数字去比较;
  • 1
  • 2
  • 3

代码

public boolean isPalindrome(int x) {
	if(x < 0 || (x != 0 && (x % 10) == 0))
		return false;
	//记录反转后的数字
	int r = 0;
	
	while(r < x){
		//x%10 取出原整数的最后一位数
		//r*10 是为了将反转后的数进位   3变成30    31变成310
		r = (r*10)+(x%10);
		//原整数去掉最后一位数字
		x/=10;
	}
	//x==r/10  是因为  121  这种奇数位数据,x最后结果为 12,除10 之后  变为1,在进行判断
	return x==r ? true : false || x==r/10 ? true : false;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

删除排序数组中的重复项

给定一个有序数组,在当前数组中直接删除重复项,使每个元素只出现一次(删除并不准确,应为替换),并返回新数组长度

问题举例

[1,2,2,3,4,4,5]  删除重复项后,原数组变为 [1,2,3,4,5,4,5] ,返回长度为 5(原数组前5个元素为新数组,且元素不重复);   
[1,2,2,5]  删除重复项后,原数组变为 [1,2,5,5] ,返回长度为 3(原数组前3个元素为新数组,且元素不重复);
  • 1
  • 2

问题解析

在原数组上直接做修改,是数组前面的元素不重复,后面的数据就不管了,然后返回前面不重复元素的个数;
数组是排好序的,
  • 1
  • 2

代码

public int removeDuplicates(int[] nums)  {
	if(nums == null || nums.length == 0){
		//数组无元素的情况
		return 0;
	}
	//数组的第一个元素,用于和后面的比较是否元素相等,如果不相等
	int startNum = nums[0];
	//替换后的数组长度,从第二个数组开始循环,所以新数组长度初始为1
	int newLen = 1;
	//循环第一个元素肯定不会涉及重复问题,所以从第二个元素开始循环
	for(int i=1;i<nums.length;i++){
		if(nums[i] != startNum){
			nums[newLen] = nums[i];
			//新数组长度加1
			newLen ++;
			//从新赋值,下一次比较重复元素使用
			startNum = nums[i];
		}
	}
	return newLen;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21

完美数

一个 正整数,如果它和除了它自身以外的所有 正因子 之和相等,我们称它为 完美数。
给定一个 整数 n, 如果是完美数,返回 true,否则返回 false

问题举例

输入6,能被28整除的整数有1、2、4、7、14,1+2+4+7+14=28,与输入数相同,返回true
输入15,能被15整除的整数有1、3、5,1+3+5 与输入数不同,返回false
  • 1
  • 2

问题解析

通过题目可知,整数1的正因子只有它本身,所以输入1的情况直接返回false
所有正整数都可被1整除
一个数除被一个数整除,肯定也能被得出的商整除,6/2 =3,反正 6/3=2,所以整除时商和除数都是因子
整数除以最小的正因子,那么商就是它最大的正因子。
	假设2位最小正因子。输入18,  18/2=9, 那么9就是18的最大因子(题目不包括自身,所以除数是2开始的)
  • 1
  • 2
  • 3
  • 4
  • 5

代码

class Solution {
    public boolean checkPerfectNumber(int num) {
    	//等于1直接返回false
        if(num == 1)
            return false;
        //用来记录正因子之和,因为所有正整数都可被1整除,默认初始值为1
        int total = 1;
        //记录因子的初始值,此处没用1,因为total默认为1了
        int y = 2;
        //临时变量
        int x = num;
        while(y < x){
        	//判断是否整除正因子
            if(num % y == 0){
            	//能被整除的情况,记录当前除数和商的和
                total = (total + y) + (num / y);
                //临时变量记录为当前的商,因为最大的因子只会是这个商
                x = num / y;
            }
            y++;
        }
        return total == num;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24

替换所有的问号

一个仅包含小写英文字母和 ‘?’ 字符的字符串 s,请你将所有的 ‘?’ 转换为若干小写字母,使最终的字符串不包含任何 连续重复 的字符。

问题举例

输入 ?zs,
			返回 azs,该示例共有 25 种解决方案,从 "azs" 到 "yzs" 都是符合题目要求的。
			只有 "z" 是无效的修改,因为字符串 "zzs" 中有连续重复的两个 'z' 。
输入ubv?w
			返回ubvaw,该示例共有 24 种解决方案,只有替换成 "v" 和 "w" 不符合题目要求。
			因为 "ubvvw" 和 "ubvww" 都包含连续重复的字符
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

问题解析

如果输入的s==? ,可以直接返回任意一个字母
如果?在输入字符串的第一个或者最后一个位置,只需要比较前一个或者后一个字符就可,例如 ?a 和 a?
如果?在输入字符串的第一个或者最后一个位置,记录前一个或者后一个字符要判断是否会下标越界
  • 1
  • 2
  • 3

代码

class Solution {
    public static String modifyString(String s) {
        if(s.equals("?"))
        	//输入的是字符串是问号,直接返回字母a
            return "a";
        //将输入的字符串转换为char数组
        char[] ss = s.toCharArray();
        //循环转换的char数组
        for(int index =0; index < ss.length;index++){
            if(ss[index] != '?'){
            	//如果当前不是 ?直接下一次循环
                continue;
            }
            //记录当前 ? 的前一个和后一个字符,默认给一个 *
            char start = '*',end = '*';
            //如果当前 ? 处于第一个字符的位置,只需要比较后一个字符
            if(index == 0 && s.length()-1 != index){
            	//记录后一个字符
                end = ss[index + 1];
            } 
            //如果当前?处于最后一个字符的位置,只需要比较前一个字符
            else if(index == s.length()-1 && index != 0){
            	//记录前一个字符
                start = ss[index - 1];
            }
            //如果当前?在字符串的中间位置,记录前后字符
            else{
            	//记录前一个字符 和 后一个字符
                start = ss[index - 1];
                end = ss[index + 1];
            }
            a:
            for(char ch = 'a';ch < 'z'; ch ++){
            	//循环a-z字母,判断前后字符都不等于当前循环的字母
                if(ch != start && ch != end){
                	//将当前问号替换字母,并跳出当前循环
                    ss[index] = ch;
                    break a;
                }
            }
        }
        return new String(ss);
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44

简化路径

给你一个字符串 path ,表示指向某一文件或目录的 Unix 风格 绝对路径 (以 ‘/’ 开头),请你将其转化为更加简洁的规范路径
在 Unix 风格的文件系统中:一个点(.)表示当前目录本身;两个点 (…) 表示将目录切换到上一级(指向父目录);任意多个连续的斜杠(即,‘//’)都被视为单个斜杠 ‘/’ 。

问题举例

输入/home/,返回 /home
			目录最后的 / 可以省略不展示
输入/home//foo/,返回 /home/foo
			路径中间的双斜杠,可以简化为单斜杠,并将最后的斜杠省略
输入/a/./b/../../c/,返回 /c
			路径/a/.中的 (.),表示当前路径,也就是/a路径,所以路径变为/a/b/../../c/
			路径/a/b/..中的(..)表示上级目录,所以路径变为/a/../c/
			路径/a/..中的(..)表示上级目录,路径变为/c/,最终简化为/c
输入/home/../../..,返回 /
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9

问题解析

可以将路径用/分割成为一个数组,判断每一个元素,是否包括(.)或者(..),分别做不同的处理
创建一个数组(用栈更优),记录原路径数组循环时简化后的路径
	长度为2倍的原路径分割的数组长度,因为原数组分割后的长度是不包含斜杠的了,但是优化的数组是要包含斜杠的
  • 1
  • 2
  • 3

代码

class Solution {
    public static String simplifyPath(String path) {
        //斜杠分割转数组
        String[] arrPath = path.split("\\/");
        //用于记录简化后的数据,长度*2是因为简化后的数据会包含 斜杠
        String[] arr = new String[arrPath.length*2];
        //用于记录记录简化后路径数组的已经使用的数组下标
        int index = -1;
        //循环遍历数组中的元素
        for(String str : arrPath){
            //如果是. 指向当前目录,什么也不用干,进入下次循环;
            //如果是.. 并且下标为-1 虽然指向上一个目录,但是下标为-1说明还没有路径,什么也不用干,进入下次循环
            if(str == null || "".equals(str) || ".".equals(str) || (index == -1 && "..".equals(str))){
                //如果当前元素为空,则进入下次循环
                continue;
            }

            if ("..".equals(str)){
                //如果是..  则指向上一个目录,删除最后一个路径已经路径前的斜杠,并将下标恢复
                arr[index] = "";
                arr[index-1] = "";
                index -=2;
            }else{
                //如果不是.. 不是.  则正常添加路径和路径前的斜杠,下标+2
                arr[index+1] = "/";
                arr[index+2] = str;
                index +=2;
            }

        }
        //记录最终的简化路径
        StringBuilder sb = new StringBuilder();
        for(String str :arr){
            //如果出现一次空,就说明路径已经简化结束,直接退出循环即可
            if(str == null|| "".equals(str)){
                break;
            }
            //记录简化路径
            sb.append(str);
        }
        //如果路径为空,直接返回斜杠
        return sb.toString().equals("") ? "/" : sb.toString();
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44

递增的三元子序列

一个整数数组 nums ,判断这个数组中是否存在长度为 3 的递增子序列。
如果存在这样的三元组下标 (i, j, k) 且满足 i < j < k ,使得 nums[i] < nums[j] < nums[k] ,返回 true ;否则,返回 false
注意:i,j,k 不用必须连续

问题举例

输入[1,2,3,4,5],返回true:下标0,1,2位置的数字是一次递增的
输入[2,1,5,0,3],返回false: 不存在长度为3的递增子序列
输入[1,5,3,4],返回true: 下标0,2,3位置的数字是一次递增的
  • 1
  • 2
  • 3

问题解析

通过题目可知,数组长度如果小于3,那必然是返回false
思路:
	先定位到序列的第一个数,可以让这个数默认等于数组的第一个数
	序列的第二个数默认值为 最大整数,防止循环比较时,直接返回true
	循环数组,判断当前循环的数和第一个数、第二个数的关系:
		如果 第一个数 < 第二个数 < 当前数 ,return true
		如果 第一个数 < 第二个数 &&   第二个数 > 当前数 ,第二个数从新赋值
		如果 第一个数 < 当前数,第一个数从新赋值
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

代码

class Solution {
    public static boolean increasingTriplet(int[] nums) {
    	//获取数组长度
    	int length = nums.length;
        if(length < 3){
        	//如果小于3,直接返回false
            return false;
        }
        //子序列第一个值,默认为数组第一个数字
        int fir = nums[0];
        //子序列第二个值,默认为最大整数
        int sec = Integer.MAX_VALUE;
		//数组循环下标
        int i = 1;
        while(i < length){
        	//循环的当前数值
            int num = nums[i];
            
            if(sec < num){
            	//如果第二个数,小于当前数,返回true. 因为第一个数,小于第二个数
                return true;
            }else if(fir < num){
            	//进入这个条件,说明第一个条件没通过,就是前提条件为 第二个数,小于当前数
            	//第二个数,小于当前数 并且 第一个数小于当前数,就将当前数赋值给第二个数
                sec = num;
            }else{
            	//进入这个条件,说明第一个数肯定是大于当前数的,将第一个数从新复制
                fir = num;
            }
            //进入下一次循环
            i++;
        }
        return false;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35

至少是其他数字两倍的最大数

一个整数数组 nums ,其中总是存在 唯一的 一个最大整数 。
并且这个数 至少是数组中每个其他数字的两倍 。
如果是,则返回 最大元素的下标 ,否则返回 -1

问题举例

输入[3,6,1,0],返回1:下标1位置的数字是最大,并且满足是数组中其他数字最少两倍的条件
输入[1,2,3,4],返回-1: 下标3位置的数字是最大,但是不满足条件,返回-1
输入[9],返回0: 不存在其他数字,默认为其他数字两倍
  • 1
  • 2
  • 3

问题解析

如果输入数组长度为1,那么直接返回0即可
先找出数组中最大的数字,这个最大的数字要和数组中其他数字的二倍进行比较大小,有这个可以得知:
	我们用最大的数字,和第二大的数字的二倍比较大小就可以了
	如果最大的数字比第二大的数字的二倍大,那就一定比其他的数字的二倍大
	第二大的数字的二倍肯定也比其他数字的二倍大
  • 1
  • 2
  • 3
  • 4
  • 5

代码

class Solution {
    public static int dominantIndex(int[] nums) {
        if(nums.length == 1){
            //数组长度为1,直接返回
            return 0;
        }
        //数组前两个数字中,较大数字的下标
        //用于存放最大数字的下标
        int max = nums[0] > nums[1] ? 0 : 1;
        //数组前两个数字中,较小数字的下标
        //用于存放第二大数字的下标
        int prev = max == 0 ? 1 : 0;

        //因为上面已经取出来前两个下标的数,所以循环从第三个开始
        for(int i =2;i<nums.length;i++){

            if(nums[max] < nums[i]){
                //判断最大数字小于当前这个数,那就把大数进行替换
                prev = max;
                max = i;
            }else if(nums[prev] < nums[i]){
                //判断最大数字大于当前这个数,并且第二大的数小于当前这个数,替换第二大的数字
                prev = i;
            }
        }
        //判断最大数字否大于第二大数字的两倍
        return nums[max] >= nums[prev] * 2 ? max : -1;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29

最小时间差

给定一个 24 小时制(小时:分钟 “HH:MM”)的时间列表,找出列表中任意两个时间的最小时间差并以分钟数表示。

问题举例

输入["23:59","00:00"],返回1,相差1分钟
输入["00:00","23:59","00:00"],返回0,有相同时间,相差分钟数为0
  • 1
  • 2

问题解析

如果列表中,有两个相同时间,则直接返回0
如果输入列表的长度为 60分钟*24小时=1440个数据,那就说明必然会有重复数据,直接返回0
数据比较时间时,还要判断最大时间和最小时间的 24 小时差:
	输入["00:00","01:00","23:50"]  ,不止要正着比较 各个时间差,还要倒着比较
	比如:00:00到和23:50,正着比较就是 23小时50分,但是倒着比较却只有10分钟 
  • 1
  • 2
  • 3
  • 4
  • 5

代码

class Solution {
    public static int findMinDifference(List<String> timePoints) {

        //获取输入的集合长度
        int timePointsLen = timePoints.size();
        if (timePointsLen > 1440) {
            //如果长度大于1440,说明肯定会有重复的时间,直接返回
            return 0;
        }
        //新创建一个数组,用于记录传过来的集合的分钟时
        int[] timeMArr = new int[timePointsLen];
        //循环传过来的集合
        for(int i = 0;i < timePointsLen;i++){
            //获取每一时间的值
            String time = timePoints.get(i);
            //将时间换算成从0点到当前的分钟数,时乘60+分  例: 10:15   10*60+15
            timeMArr[i] = Integer.valueOf(time.substring(0,2))*60 + Integer.valueOf(time.substring(3,5));
        }
        //将时间分钟数的集合排序,排序后,分钟从小到大
        Arrays.sort(timeMArr);
        //当前最小的时间,初始化为第二个和第一个分钟数的差
        int min = timeMArr[timePointsLen-1] - timeMArr[timePointsLen-2];
        //循环记录分钟数的数组
        for(int len =1;len < timePointsLen ;len++){
            //判断后一个分钟和前一个分钟的差,和默认的时间差进行比较,取最小
            min = Math.min(timeMArr[len] - timeMArr[len-1],min);
            if(min == 0){
                //如果出现两个时间的差等于0的情况,直接返回0
                return min;
            }
        }
        //倒着比较最小和最大的两个时间的差,加1440就是加24小时的分钟数
        int m = timeMArr[0] + 1440 - timeMArr[timePointsLen-1];
        //输出最小的
        return min > (m) ? m : min;
    }
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37

存在重复元素 II

一个整数数组 nums 和一个整数 k ,判断数组中是否存在两个 不同的索引 i 和 j
满足 nums[i] == nums[j] 且 abs(i - j) <= k 。如果存在,返回 true ;否则,返回 false

问题举例

 nums = {1,2,3,1}, k=3, 返回true。下标0和下标3的数字相同并且abs(0-3)<=k
 nums = [1,0,1,1], k = 1, 返回true。下标2和下标3的数字相同并且abs(2-3)<=k
 nums = [1,2,3,1,2,3], k = 2, 返回false。存在下标相等的数字,但是下标差的绝对值>k
  • 1
  • 2
  • 3

问题解析

可以使用map来记录每个数字出现的下标位置
循环数组,当发现map中已经出现了当前的数字,说明此时已经满足了题目的 nums[i] == nums[j] 条件
发现满足 nums[i] == nums[j] 条件时,只需要在判断 abs(i - j) <= k 条件是否成立
  • 1
  • 2
  • 3

代码

public static boolean containsNearbyDuplicate(int[] nums, int k) {
	//存放每个数据出现位置
    Map<Integer,Integer> map = new HashMap<>();
    //循环数组
    for(int i = 0;i<nums.length;i++){
    	//当前循环出的数字
        Integer num = nums[i];
        //用当前数字,从map中取出出现在位置
        Integer index = map.get(num);

        if(index != null && i - index <= k ){
        	//map中存在当前数字,并且上次记录的下标和这次出现的下标差<=k,直接返回true
            return true;
        }else{
        	//map中不存在当前数字,或者下标已经不符合条件了,添加记录
            map.put(num,i);
        }
    }
    return false;
}
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

写字符串需要的行数

把给定的字符串 S 从左到右写到每一行上,每一行的最大宽度为100个单位,如果在写某个字母的时候会使这行超过了100 个单位,那么应该把这个字母写到下一行。
给定了一个数组 widths ,这个数组 widths[0] 代表 ‘a’ 需要的单位, widths[1] 代表 ‘b’ 需要的单位,…, widths[25] 代表 ‘z’ 需要的单位。

现在回答两个问题:至少多少行能放下S,以及最后一行使用的宽度是多少个单位?将答案作为长度为2的整数列表返回。

问题举例

widths =[90,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,10,40]
S = "azz"
输出: [2, 80]
解释: 
字符串'a'在数组下标第一个位置,也就是长度为90,'z'的长度为40,因为一行的宽度为100,所以‘a’自己在一行,'zz'另起一行,总共2行,第二行为‘zz’宽度为80
  • 1
  • 2
  • 3
  • 4
  • 5

问题解析

字符串从左到右写到每一行上
每一行宽度不能超过100,写字符时如果宽度超过100,当前字符另起一行
字符串中每一个字符的宽度,在数组中有对应,字符‘a’‘b’‘c’‘d’,分别对应数组中0,1,2,3的下标,以此类推,‘z’在数组中最后的一个元素
  • 1
  • 2
  • 3

代码

	public int[] numberOfLines(int[] widths, String S) {
        int[] ans = new int[2];
        int l = 0,r = 1;
        for(int i=0;i<S.length();i++){
            l += widths[S.charAt(i)-'a'];
            if(l > 100){
                r += 1;
                l = widths[S.charAt(i)-'a'];
            }
        }
        ans[0] = r;
        ans[1] = l;
        return ans;
    }
  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

未完待续

还会持续更新一些常见得面试算法
  • 1
声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/2023面试高手/article/detail/653624
推荐阅读
相关标签
  

闽ICP备14008679号