常见算法面试题_工小商给你一个长度为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