大厂算法与数据结构刷题(一)
题目1
给定一个有序数组arr，代表坐落在X轴上的点
给定一个正数K，代表绳子的长度.
返回绳子最多压中几个点?
即使绳子边缘处盖住点也算盖住
image-20210510174212358
解法思路：
滑动窗口LR
找到单调性
image-20210510175446981
image-20210510175915320
image-20210510180134886
image-20210510180300741
public class Code01_CordCoverMaxPoint {
//贪心，右侧压中一个，2分查找左侧 时间复杂度O(N*logN)
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;
}
//单调性解法 left right 一次计算往右 事件复杂度O(n)
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;
}
// for test
public static int test(int[] arr, int L) {
int max = 0;
for (int i = 0; i < arr.length; i++) {
int pre = i - 1;
while (pre >= 0 && arr[i] - arr[pre] <= L) {
pre--;
}
max = Math.max(max, i - pre);
}
return max;
}
// for test
public static int[] generateArray(int len, int max) {
int[] ans = new int[(int) (Math.random() * len) + 1];
for (int i = 0; i < ans.length; i++) {
ans[i] = (int) (Math.random() * max);
}
Arrays.sort(ans);
return ans;
}
public static void main(String[] args) {
int len = 100;
int max = 1000;
int testTime = 100000;
System.out.println("测试开始");
for (int i = 0; i < testTime; i++) {
int L = (int) (Math.random() * max);
int[] arr = generateArray(len, max);
int ans1 = maxPoint1(arr, L);
int ans2 = maxPoint2(arr, L);
int ans3 = test(arr, L);
if (ans1 != ans2 || ans2 != ans3) {
System.out.println("oops!");
break;
}
}
}
}
题目2
给定一个文件目录的路径, 写一个函数统计这个目录下所有的文件数量并返回 ，隐藏文件也算，但是文件夹不算。
思路
树的宽度优先遍历，使用队列辅助
根文件夹放入队列，然后队列不为空，从队列弹出。
弹出的文件夹的下层，获取文件类型，是文件的的count++ 如果是文件夹类型，入队。
public class CountFiles {
// 注意这个函数也会统计隐藏文件
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;
}
}
题目3
给定一个非负整数num,如何不用循环语句，返回>=num，并且离num最近的，2的某次方
public class Code03_Near2Power {
// 已知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;
}
public static void main(String[] args) {
int cap = 120;
System.out.println(tableSizeFor(cap));
}
}
题目4
一个数组中只有两种字符'G'和'B',可以让所有的G都放在左侧，所有的B都放在右侧 或者可以让所有的G都放在右侧，所有的B都放在左侧
但是只能在相邻字符之间进行交换操作,返回至少需要交换几次
public class Code04_MinSwapStep {
// 一个数组中只有两种字符'G'和'B'，
// 可以让所有的G都放在左侧，所有的B都放在右侧
// 或者可以让所有的G都放在右侧，所有的B都放在左侧
// 但是只能在相邻字符之间进行交换操作，请问请问至少需要交换几次，
public static int minSteps1(String s) {
if (s == null || s.equals("")) {
return 0;
}
char[] str = s.toCharArray();
int step1 = 0;
int gi = 0;
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);
}
// 可以让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);
}
}
题目5
给定一个二维数组matrix,你可以从任何位置出发，走向. 上下左右四个方向
返回能走出来的最长的递增链长度
public class Code05_LongestIncreasingPath {
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;
}
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;
}
}
题目6
给定两个非负数组x和hp,长度都是N，再给定一个正数range
x有序 x[]表示i1号怪兽在x轴上的位置; hp[i]表示i号怪兽的血量
range表示法师如果站在x位置，用AOE技能打到的范围是:
[x-range,x+range]，被打到的每只怪兽损失1点血量
返回要把所有怪兽血量清空，至少需要释放多少次AOE技能?
// 贪心策略：永远让最左边缘以最优的方式(AOE尽可能往右扩，最让最左边缘盖住目前怪的最左)变成0，也就是选择：
// 一定能覆盖到最左边缘, 但是尽量靠右的中心点
// 等到最左边缘变成0之后，再去找下一个最左边缘...
public static int minAoe2(int[] x, int[] hp, int range) {
int N = x.length;
int ans = 0;
for (int i = 0; i < N; i++) {
if (hp[i] > 0) {
int triggerPost = i;
while (triggerPost < N && x[triggerPost] - x[i] <= range) {
triggerPost++;
}
ans += hp[i];
aoe(x, hp, i, triggerPost - 1, range);
}
}
return ans;
}
public static void aoe(int[] x, int[] hp, int L, int trigger, int range) {
int N = x.length;
int RPost = trigger;
while (RPost < N && x[RPost] - x[trigger] <= range) {
RPost++;
}
int minus = hp[L];
for (int i = L; i < RPost; i++) {
hp[i] = Math.max(0, hp[i] - minus);
}
}
题目7
给定一个数组arr，你可以在每个数字之前决定+或者- 但是必须所有数字都参与
再给定一个数target，请问最后算出target的方法数是多少?
- 暴力递归
public static int findTargetSumWays1(int[] arr, int s) {
return process1(arr, 0, s);
}
// 可以自由使用arr[index....]所有的数字！
// 搞出rest这个数，方法数是多少？返回
public static int process1(int[] arr, int index, int rest) {
if (index == arr.length) { // 没数了！
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]);
}
- 暴力递归改动态规划 记忆化搜索
public static int findTargetSumWays2(int[] arr, int s) {
return process2(arr, 0, s, new HashMap<>());
}
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;
}
// 优化点一 :
// 你可以认为arr中都是非负数
// 因为即便是arr中有负数，比如[3,-4,2]
// 因为你能在每个数前面用+或者-号
// 所以[3,-4,2]其实和[3,4,2]达成一样的效果
// 那么我们就全把arr变成非负数，不会影响结果的
// 优化点二 :
// 如果arr都是非负数，并且所有数的累加和是sum
// 那么如果target<sum，很明显没有任何方法可以达到target，可以直接返回0
// 优化点三 :
// 因为题目要求一定要使用所有数字去拼target，
// 所以不管这些数字怎么用+和-折腾，最终的结果都一定不会改变奇偶性
// 所以，如果所有数的累加和是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？
// 其实就是求有多少个子集的累加和是9 -> (7 + 11) / 2
// 优化点五 :
// 二维动态规划的空间压缩技巧
public static int findTargetSumWays3(int[] arr, int target) {
int sum = 0;
for (int n : arr) {
sum += n;
}
return sum < target || ((target & 1) ^ (sum & 1)) != 0 ? 0 : subset(arr, (target + sum) >> 1);
}
public static int subset(int[] nums, int s) {
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];
}
