阿源的知识库大厂刷题班1
01 第一节
题目一 CordCoverMaxPoint
给定一个有序数组arr，代表坐落在X轴上的点
给定一个正数K，代表绳子的长度
返回绳子最多压中几个点?
即使绳子边缘处盖住点也算盖住
L R 一个窗口不回退java
public static int maxPoint1(int[] arr, int L) {
int res = 1;
for (int i = 0; i < arr.length; i++) {
int nearest = nearestIndex(arr, i, arr[i] - L);
res = Math.max(res, i - nearest + 1);
}
return res;
}
public static int nearestIndex(int[] arr, int R, int value) {
int L = 0;
int index = R;
while (L <= R) {
int mid = L + ((R - L) >> 1);
if (arr[mid] >= value) {
index = mid;
R = mid - 1;
} else {
L = mid + 1;
}
}
return index;
}
public static int maxPoint2(int[] arr, int L) {
int left = 0;
int right = 0;
int N = arr.length;
int max = 0;
while (left < N) {
while (right < N && arr[right] - arr[left] <= L) {
right++;
}
max = Math.max(max, right - (left++));
}
return max;
}题目二 CountFiles
给定一个文件目录的路径,
写一个函数统计这个目录下所有的文件数量并返回
隐藏文件也算，但是文件夹不算
将文件夹放到队列里去，Q内弹出文件夹，遇到文件 count++
用栈也行java
// 注意这个函数也会统计隐藏文件
public static int getFileNumber(String folderPath) {
File root = new File(folderPath);
if (!root.isDirectory() && !root.isFile()) {
return 0;
}
if (root.isFile()) {
return 1;
}
Stack<File> stack = new Stack<>();
stack.add(root);
int files = 0;
while (!stack.isEmpty()) {
File folder = stack.pop();
for (File next : folder.listFiles()) {
if (next.isFile()) {
files++;
}
if (next.isDirectory()) {
stack.push(next);
}
}
}
return files;
}题目三 Near2Power
给定一个非负整数num,
如何不用循环语句,
返回>=num，并且离num最近的，2的某次方
给7 返回8 给14 返回16
先减1是为了避免直接为2的次方，把后面填满 然后+1java
// 已知n是正数
// 返回大于等于，且最接近n的，2的某次方的值
public static final int tableSizeFor(int n) {
n--;
n |= n >>> 1;
n |= n >>> 2;
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
return (n < 0) ? 1 : n + 1;
}题目四 MinSwapStep
一个数组中只有两种字符'G'和'B'
想让所有的G都放在左侧，所有的B都放在右侧
但是只能在相邻字符之间进行交换操作,
返回至少需要交换几次
贪心 第0次出现的G只能放在0位置
L index找到出现的G index-Ljava
public static int minSteps1(String s) {
if (s == null || s.equals("")) {
return 0;
}
char[] str = s.toCharArray();
int step1 = 0;
int gi = 0; // 相当于L
for (int i = 0; i < str.length; i++) {
if (str[i] == 'G') {
step1 += i - (gi++);
}
}
int step2 = 0;
int bi = 0;
for (int i = 0; i < str.length; i++) {
if (str[i] == 'B') {
step2 += i - (bi++);
}
}
return Math.min(step1, step2);
}java
// 可以让G在左，或者在右
public static int minSteps2(String s) {
if (s == null || s.equals("")) {
return 0;
}
char[] str = s.toCharArray();
int step1 = 0;
int step2 = 0;
int gi = 0;
int bi = 0;
for (int i = 0; i < str.length; i++) {
if (str[i] == 'G') { // 当前的G，去左边 方案1
step1 += i - (gi++);
} else {// 当前的B，去左边 方案2
step2 += i - (bi++);
}
}
return Math.min(step1, step2);
}题目五 LongestIncreasingPath
给定一个二维数组matrix,
你可以从任何位置出发，走向上下左右四个方向
返回能走出来的最长的递增链长度java
public static int longestIncreasingPath1(int[][] matrix) {
int ans = 0;
int N = matrix.length;
int M = matrix[0].length;
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
ans = Math.max(ans, process1(matrix, i, j));
}
}
return ans;
}
// 从m[i][j]开始走，走出来的最长递增链，返回！
public static int process1(int[][] m, int i, int j) {
int up = i > 0 && m[i][j] < m[i - 1][j] ? process1(m, i - 1, j) : 0;
int down = i < (m.length - 1) && m[i][j] < m[i + 1][j] ? process1(m, i + 1, j) : 0;
int left = j > 0 && m[i][j] < m[i][j - 1] ? process1(m, i, j - 1) : 0;
int right = j < (m[0].length - 1) && m[i][j] < m[i][j + 1] ? process1(m, i, j + 1) : 0;
return Math.max(Math.max(up, down), Math.max(left, right)) + 1;
}java
public static int longestIncreasingPath2(int[][] matrix) {
int ans = 0;
int N = matrix.length;
int M = matrix[0].length;
int[][] dp = new int[N][M];
for (int i = 0; i < N; i++) {
for (int j = 0; j < M; j++) {
ans = Math.max(ans, process2(matrix, i, j, dp));
}
}
return ans;
}
// 从m[i][j]开始走，走出来的最长递增链，返回！
public static int process2(int[][] m, int i, int j, int[][] dp) {
if (dp[i][j] != 0) {
return dp[i][j];
}
// (i,j)不越界
int up = i > 0 && m[i][j] < m[i - 1][j] ? process2(m, i - 1, j, dp) : 0;
int down = i < (m.length - 1) && m[i][j] < m[i + 1][j] ? process2(m, i + 1, j, dp) : 0;
int left = j > 0 && m[i][j] < m[i][j - 1] ? process2(m, i, j - 1, dp) : 0;
int right = j < (m[0].length - 1) && m[i][j] < m[i][j + 1] ? process2(m, i, j + 1, dp) : 0;
int ans = Math.max(Math.max(up, down), Math.max(left, right)) + 1;
dp[i][j] = ans;
return ans;
}题目六 AOE （线段树）
给定两个非负数组x和hp，长度都是N,再给定-个正数range
x有序，x[门]表示i号怪兽在x轴上的位置; hp[]表示i号怪兽的血量
range表示法师如果站在x位置，用AOE技能打到的范围是:
[x-range,x+range],被打到的每只怪兽损失1点血量
返回要把所有怪兽血量清空，至少需要释放多少次AOE技能?
线段树 一个范围内所有数字减java
题目七 TargetSum
给定一个数组arr,你可以在每个数字之前决定+或者-
但是必须所有数字都参与
再给定一个数target，请问最后算出target的方法数是多少?
// leetcode 494题java
// 暴力尝试
public static int findTargetSumWays1(int[] arr, int s) {
return process1(arr, 0, s);
}
// 可以自由使用arr[index....]所有的数字！
// 搞出rest这个数，方法数是多少？返回
// index == 7 rest = 13
// map "7_13" 256
public static int process1(int[] arr, int index, int rest) {
if (index == arr.length) { // 没数了！如果当前为0 方法+1
return rest == 0 ? 1 : 0;
}
// 还有数！arr[index] arr[index+1 ... ]
return process1(arr, index + 1, rest - arr[index]) + process1(arr, index + 1, rest + arr[index]);
}java
public static int findTargetSumWays2(int[] arr, int s) {
return process2(arr, 0, s, new HashMap<>());
}
// index == 7 rest = 13 256
// 7 : {13 , 256}
public static int process2(int[] arr, int index, int rest, HashMap<Integer, HashMap<Integer, Integer>> dp) {
if (dp.containsKey(index) && dp.get(index).containsKey(rest)) {
return dp.get(index).get(rest);
}
// 否则，没命中！
int ans = 0;
if (index == arr.length) {
ans = rest == 0 ? 1 : 0;
} else {
ans = process2(arr, index + 1, rest - arr[index], dp) + process2(arr, index + 1, rest + arr[index], dp);
}
if (!dp.containsKey(index)) {
dp.put(index, new HashMap<>());
}
dp.get(index).put(rest, ans);
return ans;
}java
// 优化点一 :
// 你可以认为arr中都是非负数
// 因为即便是arr中有负数，比如[3,-4,2]
// 优化点二 :
// 如果arr都是非负数，并且所有数的累加和是sum
// 那么如果target<sum，很明显没有任何方法可以达到target，可以直接返回0
// 优化点三 : 奇偶性
// arr内部的数组，不管怎么+和-，最终的结果都一定不会改变奇偶性
// 所以，如果所有数的累加和是sum，
// 并且与target的奇偶性不一样，没有任何方法可以达到target，可以直接返回0
// 优化点四 :
// 比如说给定一个数组, arr = [1, 2, 3, 4, 5] 并且 target = 3
// 其中一个方案是 : +1 -2 +3 -4 +5 = 3
// 该方案中取了正的集合为P = {1，3，5}
// 该方案中取了负的集合为N = {2，4}
// 所以任何一种方案，都一定有 sum(P) - sum(N) = target
// 现在我们来处理一下这个等式，把左右两边都加上sum(P) + sum(N)，那么就会变成如下：
// sum(P) - sum(N) + sum(P) + sum(N) = target + sum(P) + sum(N)
// 2 * sum(P) = target + 数组所有数的累加和
// sum(P) = (target + 数组所有数的累加和) / 2
// 也就是说，任何一个集合，只要累加和是(target + 数组所有数的累加和) / 2
// 那么就一定对应一种target的方式
// 也就是说，比如非负数组arr，target = 7, 而所有数累加和是11
// 求有多少方法组成7，其实就是求有多少种达到累加和(7+11)/2=9的方法
// 优化点五 :
// 二维动态规划的空间压缩技巧
public static int findTargetSumWays(int[] arr, int target) {
int sum = 0;
for (int n : arr) {
sum += n;
}
return sum < target || ((target & 1) ^ (sum & 1)) != 0 ? 0 : subset2(arr, (target + sum) >> 1);
}
// 求非负数组nums有多少个子集，累加和是s
// 二维动态规划
// 不用空间压缩
public static int subset1(int[] nums, int s) {
if (s < 0) {
return 0;
}
int n = nums.length;
// dp[i][j] : nums前缀长度为i的所有子集，有多少累加和是j？
int[][] dp = new int[n + 1][s + 1];
// nums前缀长度为0的所有子集，有多少累加和是0？一个：空集
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = 0; j <= s; j++) {
dp[i][j] = dp[i - 1][j];
if (j - nums[i - 1] >= 0) {
dp[i][j] += dp[i - 1][j - nums[i - 1]];
}
}
}
return dp[n][s];
}
// 求非负数组nums有多少个子集，累加和是s
// 二维动态规划
// 用空间压缩:
// 核心就是for循环里面的：for (int i = s; i >= n; i--) {
// 为啥不枚举所有可能的累加和？只枚举 n...s 这些累加和？
// 因为如果 i - n < 0，dp[i]怎么更新？和上一步的dp[i]一样！所以不用更新
// 如果 i - n >= 0，dp[i]怎么更新？上一步的dp[i] + 上一步dp[i - n]的值，这才需要更新
public static int subset2(int[] nums, int s) {
if (s < 0) {
return 0;
}
int[] dp = new int[s + 1];
dp[0] = 1;
for (int n : nums) {
for (int i = s; i >= n; i--) {
dp[i] += dp[i - n];
}
}
return dp[s];
}