dsapr

刷题

一

1

给定一个有序数组arr，坐落在X轴上给定正整数K为绳子长度返回绳子最多压中几个点？即使绳子边缘处盖住也算

// 滑动窗口
public int maxPoint(int arr[], int K) {
  int left = 0;
  int right = 0;
  int max = 0;
  while (left < arr.length) {
    while (right < arr.length && arr[right] - arr[left] <= K) {
      right++;
    }
    max = Math.max(max, right - (left++));
  }
  
  return max;
}

2

给定一个文件目录的路径写一个函数统计这个目录下所有的文件数量并返回隐藏文件也算，文件夹不算

递归或者队列或者栈

3

给定一个非负整数num，如何不用循环语句，返回>=num，并且离num最近的，2的某次方

二进制填满 +1
1111 + 1

4

一个数组中只有两种字符'G'和'B'，可以让所有的G都放在左侧，所有的B都放在右侧或者可以让所有的G都放在右侧，所有的B都放在左侧，但是只能在相邻字符之间进行交换操作，返回至少需要交换几次

贪心：左右双指针，G全移到左侧B自然到右侧

5

给定一个二维数组matrix，你可以从任何位置出发，走向上、下、左、右四个方向，返回能走出来的最长的递增链长度

6

给定两个非负数组x和hp，长度都是N，再给定一个正数range x有序，x[i]表示i号怪兽在x轴上的位置 hp[i]表示i号怪兽的血量再给定一个正数range，表示如果法师释放技能的范围长度被打到的每只怪兽损失1点血量。返回要把所有怪兽血量清空，至少需要释放多少次AOE技能？

贪心

7

给定一个数组arr，你可以在每个数字之前决定+或者-但是必须所有数字都参与，再给定一个数target 请问最后算出target的方法数

二

1

给定数组hard和money，长度都为N，hard[i]表示i号工作的难度， money[i]表示i号工作的收入给定数组ability，长度都为M，ability[j]表示j号人的能力，每一号工作，都可以提供无数的岗位，难度和收入都一样但是人的能力必须>=这份工作的难度，才能上班。返回一个长度为M的数组ans，ans[j]表示j号人能获得的最好收入

2 数据结构设计题

贩卖机只支持硬币支付，且收退都只支持10 ，50，100三种面额一次购买只能出一瓶可乐，且投钱和找零都遵循优先使用大钱的原则需要购买的可乐数量是m，其中手头拥有的10、50、100的数量分别为a、b、c，可乐的价格是x(x是10的倍数) 请计算出需要投入硬币次数

6

给定一个数组arr，只能对arr中的一个子数组排序，但是想让arr整体都有序，返回满足这一设定的子数组中最短的是多长

1 2 6 5 4 3 8 9 sort

三

2

只由小写字母（a~z）组成的一批字符串，都放在字符类型的数组String[] arr中，如果其中某两个字符串所含有的字符种类完全一样就将两个字符串算作一类，比如baacbba和bac就算作一类，返回arr中有多少类

利用整数存 26 个字母，描黑，存到 hashset 中看有多少个整数

核心代码

int key = 0;
fori
  key |= (1 << (chs[i] - 'a'));

5

给定一个正数数组arr，代表若干人的体重，再给定一个正数limit，表示所有船共同拥有的载重量，每艘船最多坐两人，且不能超过载重想让所有的人同时过河，并且用最好的分配方法让船尽量少，返回最少的船数 Leetcode链接open in new window

找到 <=limit/2 偏左的数字

6

给定整数数组nums和目标值goal，需要从nums中选出一个子序列，使子序列元素总和最接近goal 也就是说如果子序列元素和为sum ，需要最小化绝对差abs(sum - goal)，返回 abs(sum - goal)可能的最小值注意数组的子序列是通过移除原始数组中的某些元素（可能全部或无）而形成的数组。

9

给定三个参数，二叉树的头节点head，树上某个节点target，正数K。从target开始，可以向上走或者向下走，返回与target的距离是K的所有节点

四

1

数组为{3, 2, 2, 3, 1}，查询为(0, 3, 2)，意思是在数组里下标0~3这个范围上，有几个？答案返回2 假设给你一个数组arr，对这个数组的查询非常频繁，且都给了查询组，请返回所有查询的结果

做出预处理结构，降低单次查询代价

3

返回一个二维数组中子矩阵最大累加和

动态规划升级版99乘法表基于2题

时间复杂度 O(N^2 * M)

优化：N过大则与M转换

4

返回一个数组中所选数字不能相邻的情况下最大子序列累加和

美团面试

动态规划从左往右要不要当前项

arr[i]
arr[i - 1]
arr[i] + arr[i-2]

原问题open in new window 老师想给孩子们分发糖果，有N个孩子站成了一条直线，老师会根据每个孩子的表现，预先给他们评分你需要按照以下要求，帮助老师给这些孩子分发糖果：每个孩子至少分配到 1 个糖果。评分更高的孩子必须比他两侧的邻位孩子获得更多的糖果。那么这样下来，返回老师至少需要准备多少颗糖果进阶：在原来要求的基础上，增加一个要求，相邻的孩子间如果分数一样，分的糖果数必须一样，返回至少需要准备多少颗糖果

阿里面试

贪心+预结构左右遍历取峰值

进阶：如果两数一样，则继承左边（右边）值小则归 1，大则加 1

6

生成长度为size的达标数组，什么叫达标？对于任意的i<k<j，满足[i]+[j]!=[k]*2。给定一个正数size，返回长度为size的达标数组

左 + 右 != 中 * 2

a + c != 2b 2(a + c) + 2 != 2*(2b) + 2 ==> 2a+1 + 2c+1 != 2*(2b + 1) # 满足条件

[2a, 2b, 2c, 2a + 1, 2b + 1, 2c + 1]

7

给定三个字符串s1、s2、s3，请你帮忙验证s3是否是由s1和s2交错组成的 Leetcode题目open in new window 97

动态规划样本对应模型

8

大楼轮廓线问题 Leetcode题目open in new window

七

1

给定一个非负数组成的数组，长度一定大于1，想知道数组中哪两个数&的结果最大，返回这个最大结果。要求时间复杂度O(N)，额外空间复杂度O(1)

贪心从整数最大位开始&1，一共三十位进行淘汰，剩下的就是可以&出的最大值

2 相机最小覆盖

Leetcode 968 hard

给定一个二叉树，我们在树的节点上安装摄像头，节点上的每个摄影头都可以监视其父对象、自身及其直接子对象，计算监控树的所有节点所需的最小摄像头数量

3

给定一个数组arr，返回如果排序之后（注意是如果排序），相邻两数的最大差值。要求时间复杂度O(N)，不能使用非基于比较的排序

经典题型

假设答案法

鸽笼原理找出平凡解排除

4

给定一个有序数组arr，其中值可能为正、负、0。返回arr中每个数都平方之后不同的结果有多少种？给定一个数组arr，先递减然后递增，返回arr中有多少个不同的数字？

双指针

5

假设所有字符都是小写字母，大字符串是str，arr是去重的单词表, 每个单词都不是空字符串且可以使用任意次。使用arr中的单词有多少种拼接str的方式，返回方法数。

从左往右模型一维动态规划表

前缀树优化

6

String str, int K, String[] parts, int[] record Parts和records的长度一样长，str一定要分割成k个部分，分割出来的每部分在parts里必须得有，那一部分的得分在record里，请问str切成k个部分，返回最大得分

同 5，计算累加和

九

1

给定一个数组arr，长度为N，arr中的值不是0就是1。arr[i]表示第i栈灯的状态，0代表灭灯，1代表亮灯每一栈灯都有开关，但是按下i号灯的开关，会同时改变i-1、i、i+1栈灯的状态问题一：如果N栈灯排成一条直线,请问最少按下多少次开关？ i为中间位置时，i号灯的开关能影响i-1、i和i+1 0号灯的开关只能影响0和1位置的灯 N-1号灯的开关只能影响N-2和N-1位置的灯问题二：如果N栈灯排成一个圈,请问最少按下多少次开关,能让灯都亮起来 i为中间位置时，i号灯的开关能影响i-1、i和i+1 0号灯的开关能影响N-1、0和1位置的灯 N-1号灯的开关能影响N-2、N-1和0位置的灯

6

定义何为step sum？比如680，680 + 68 + 6 = 754，680的step sum叫754。给定一个正数num，判断它是不是某个数的step sum

十一回文专题（dp技巧）

添加字符形成回文

问题一：一个字符串至少需要添加多少个字符能整体变成回文串 [leetcode 1312] hard 问题二：返回问题一的其中一种添加结果问题三：返回问题一的所有添加结果

双指针

// i 到 j 范围上需要添几个数字可以形成回文
// 初始化可以判断出 dp[i][i+1] 两个字符的时候需要添加几个形成回文
1. 开头添加	dp[i][j] = 1 + dp[i-1][j]
2. 末尾添加 dp[i][j] = dp[i][j-1] + 1
3. 如果 arr[i] == arr[j] 中间添加 dp[i+1][j-1]
// 从下往上 从右往左
dp[i][j]

如何得到一种结果
回溯一路dp表
返回问题一的所有添加结果
深度优先遍历

切几刀全为回文

问题一：一个字符串至少要切几刀能让切出来的子串都是回文串问题二：返回问题一的其中一种划分结果问题三：返回问题一的所有划分结果

* 十二

1 leetcode[567]

给定长度为m的字符串aim，以及一个长度为n的字符串str，问能否在str中找到一个长度为m的连续子串，使得这个子串刚好由aim的m个字符组成，顺序无所谓，返回任意满足条件的一个子串的起始位置，未找到返回-1

窗口 + hashmap

2 并查集

3 动态规划 leetcode[4] 找正序数组中位数

给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的中位数进阶：在两个都有序的数组中找整体第K小的数，可以做到O(log(Min(M,N)))

4 leetcode[10] hard

样本对应模型（行列模型）

dp[i][j]
str[i...] 能否被 exp[j...] 匹配

5 leetcode[128] 找出数组中可以组合出的最长连续子序列

给定一个未排序的整数数组 nums ，找出数字连续的最长序列（不要求序列元素在原数组中连续）的长度。请你设计并实现时间复杂度为 O(n) 的算法解决此问题。

一张哈希表两张哈希表均可解利用区间粘合求解

十三

1

谷歌面试题扩展版，面值为1~N的牌组成一组，每次你从组里等概率的抽出1~N中的一张，下次抽会换一个新的组，有无限组当累加和<a时，你将一直抽牌；当累加和>=a且<b时，你将获胜；当累加和>=b时，你将失败返回获胜的概率，给定的参数为N，a，b

十四

1

给定一个只由左括号和右括号的字符串，返回最长的有效括号子串的长度

2

arr中求子数组的累加和是<=K的并且是最大的，返回这个最大的累加和

十五股票系列

https://leetcode.com/problems/best-time-to-buy-and-sell-stock/

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-ii/

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iii/

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-iv/

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-cooldown/

https://leetcode.com/problems/best-time-to-buy-and-sell-stock-with-transaction-fee/

十六

2

给定一个正数数组arr，返回arr的子集不能累加出的最小正数 1）正常怎么做？ 2）如果arr中肯定有1这个值，怎么做？

3

给定一个已排序的正整数数组 nums，和一个正整数 n 。从 [1, n] 区间内选取任意个数字补充到 nums 中，使得 [1, n] 区间内的任何数字都可以用 nums 中某几个数字的和来表示，请输出满足上述要求的最少需要补充的数字个数

十七

1

给定一个每一行有序、每一列也有序，整体可能无序的二维数组，再给定一个数num，返回二维数组中有没有num这个数

时间复杂度O(N + M)

2

给定一个每一行有序、每一列也有序，整体可能无序的二维数组，再给定一个正数k，返回二维数组中第k小的数 Leetcode题目378：https://leetcode.com/problems/kth-smallest-element-in-a-sorted-matrix/

二分思想时间复杂度：O((M+N) * log(max-min))

二十二

1 so hard

给定数组 nums 由正整数组成，找到三个互不重叠的子数组的最大和。每个子数组的长度为k，我们要使这3*k个项的和最大化。返回每个区间起始索引的列表（索引从 0 开始）。如果有多个结果，返回字典序最小的一个。 Leetcode题目：https://leetcode.com/problems/maximum-sum-of-3-non-overlapping-subarrays/

2 接雨水 hard

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水 Leetcode题目42：https://leetcode.com/problems/trapping-rain-water/

Dp[i] = Max(Min(左max，右max)-arr[i],0)

哪边max小看哪边

class Solution {
    public int trap(int[] height) {
        if (height == null && height.length == 0) return 0;
        
        int N = height.length;
        int res = 0;

        int leftMaxHeight = height[0];
        int rightMaxHeight = height[N - 1];
        int leftIndex = 1;
        int rightIndex = (N - 1) - 1;

        while (rightIndex < N && leftIndex > 0 && rightIndex >= leftIndex) {
            // 当前格子雨水量
            int cur;

            if (leftMaxHeight > rightMaxHeight) {
                cur = Math.max((rightMaxHeight - height[rightIndex]), 0);
                rightMaxHeight = Math.max(rightMaxHeight, height[rightIndex]);
                rightIndex--;
            } else {
                cur = Math.max((leftMaxHeight - height[leftIndex]), 0);
                leftMaxHeight = Math.max(leftMaxHeight, height[leftIndex]);
                leftIndex++;
            }

            res += cur;
        }

        return res;
    }
}

4

一个不含有负数的数组可以代表一圈环形山，每个位置的值代表山的高度比如， {3,1,2,4,5}、{4,5,3,1,2}或{1,2,4,5,3}都代表同样结构的环形山山峰A和山峰B能够相互看见的条件为: 1.如果A和B是同一座山，认为不能相互看见 2.如果A和B是不同的山，并且在环中相邻，认为可以相互看见 3.如果A和B是不同的山，并且在环中不相邻，假设两座山高度的最小值为min 1)如果A通过顺时针方向到B的途中没有高度比min大的山峰，认为A和B可以相互看见 2)如果A通过逆时针方向到B的途中没有高度比min大的山峰，认为A和B可以相互看见两个方向只要有一个能看见，就算A和B可以相互看见给定一个不含有负数且没有重复值的数组 arr，请返回有多少对山峰能够相互看见进阶，给定一个不含有负数但可能含有重复值的数组arr，返回有多少对山峰能够相互看见

如果所有数字不一样可以找到 2(N - 2) + 1 对

利用单调栈求解由小到大

5 hard

你正在安装一个广告牌，并希望它高度最大。这块广告牌将有两个钢制支架，两边各一个。每个钢支架的高度必须相等。你有一堆可以焊接在一起的钢筋 rods。举个例子，如果钢筋的长度为 1、2 和 3，则可以将它们焊接在一起形成长度为 6 的支架。返回广告牌的最大可能安装高度。如果没法安装广告牌，请返回 0。 Leetcode题目 956 ：https://leetcode.com/problems/tallest-billboard/

利用栈

二十七

1

每一个项目都有三个数，[a,b,c]表示这个项目a和b乐队参演，花费为c 每一个乐队可能在多个项目里都出现了，但是只能被挑一次 nums是可以挑选的项目数量，所以一定会有nums*2只乐队被挑选出来返回一共挑nums轮(也就意味着一定请到所有的乐队)，最少花费是多少？如果怎么都无法在nums轮请到nums2只乐队且每只乐队只能被挑一次，返回-1 nums<9，programs长度小于500，每组测试乐队的全部数量一定是nums*2，且标号一定是0 ~ nums2-1

三十

dp 参考资料

https://blog.csdn.net/qq_40963043/article/details/100765212

# 刷题

# 一

# 1

# 2

# 3

# 4

# 5

# 6

# 7

# 二

# 1

# 2 数据结构设计题

# 6

# 三

# 1

# 2

# 3

# 5

# 6

# 9

# 四

# 1

# 2

# 3

# 4

# 5

# 6

# 7

# 8

# 七

# 1

# 2 相机最小覆盖

# 3

# 4

# 5

# 6

# 九

# 1

# 6

# 十一 回文专题（dp技巧）

# 添加字符形成回文

# 切几刀全为回文

# * 十二

# 1 leetcode[567]

# 2 并查集

# 3 动态规划 leetcode[4] 找正序数组中位数

# 4 leetcode[10] hard

# 5 leetcode[128] 找出数组中可以组合出的最长连续子序列

# 十三

# 1

# 十四

# 1

# 2

# 十五 股票系列

# 十六

# 2

# 3

# 十七

# 1

# 2

# 二十二

# 1 so hard

# 2 接雨水 hard

# 4

# 5 hard

# 二十七

# 1

# 三十

# dp 参考资料

刷题

一

1

2

3

4

5

6

7

二

1