Jiaming Zhang's Blog
0%

算法-线性表

发表于 更新于 分类于

线性表相关算法题

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public int maxCoveredPoint(int[] arr, int K) {
    int maxValue = Integer.MIN_VALUE;
    int r = 0;
    // 滑动窗口：坐指针从左到右，右指针找到距离左指针最远的点
    for (int l = 0; l < arr.length; l++) {
        while (r < arr.length) {
            if (arr[r] - arr[l] > K) {
                break;
            }
            maxValue = Math.max(r - l + 1, maxValue);
            r ++;
        }
    }
    return maxValue;
}

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

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
public int getFileNumber(String path) {
    File root = new File(path);
    if (!root.exists()) {
       return 0;
    }
    if (!root.isDirectory() && !root.isFile()) {
        return 0;
    }
    if (root.isFile()) {
        return 1;
    }
    Stack<File> stack = new Stack<>();
    stack.add(root);
    int fileNum = 0;
    while (!stack.isEmpty()) {
        File top = stack.pop();
        for (File next : Objects.requireNonNull(top.listFiles())) {
            if (next.isFile()) {
                fileNum ++;
            }
            if (next.isDirectory()) {
                stack.push(next);
            }
        }
    }
    return fileNum;
}

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

有序表

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
45
46
47
48
public int[] bestJob(int[] hard, int[] money, int[] ability) {
    Job[] jobList = new Job[hard.length];
    for (int i = 0; i < hard.length; i++) {
        jobList[i] = new Job(hard[i], money[i]);
    }
    // 先按难度升序排序，再按工资降序排序
    Arrays.sort(jobList);
    // 构建有序表
    TreeMap<Integer, Integer> treeMap = new TreeMap<>();
    treeMap.put(jobList[0].hard, jobList[0].money);
    Job base = jobList[0];
    // 获取：1.相同难度工资高的工作；2.难度增大工资高的工作
    for (int i = 1; i < jobList.length; i++) {
        if (jobList[i].hard > base.hard && jobList[i].money > base.money) {
            treeMap.put(jobList[i].hard, jobList[i].money);
            base = jobList[i];
        }
    }
    // 取能力<=hard[i]且离hard[i]最近的工作
    int[] ans = new int[ability.length];
    for (int i = 0; i < ability.length; i++) {
        Integer key = treeMap.floorKey(ability[i]);
        ans[i] = key != null ? treeMap.get(key) : 0;
    }
    return ans;
}

static class Job implements Comparable<Job> {
    public int hard;
    public int money;
    public Job(int hard, int money) {
        this.hard = hard;
        this.money = money;
    }

    @Override
    public int compareTo(Job o) {
        return this.hard - o.hard != 0 ? this.hard - o.hard : - this.money + o.money;
    }

    @Override
    public String toString() {
        return "Job{" +
                "hard=" + hard +
                ", money=" + money +
                '}';
    }
}

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

https://leetcode-cn.com/problems/shortest-unsorted-continuous-subarray/

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
public int minSortLength(int[] arr) {
    if (arr == null || arr.length < 2) {
        return 0;
    }
    int left = 0;
    int right = arr.length - 1;
    int max = Integer.MIN_VALUE;
    // 从左向右找必须要排序的右端点
    for (int i = 0; i < arr.length; i++) {
        // 如何找：如果arr[i]小于已经发现的最大值，则arr[i]必须得调整位置
        if (arr[i] < max) {
            left = i;
        }
        max = Math.max(max, arr[i]);
    }
    int min = Integer.MAX_VALUE;
    // 从右向左找必须要排序的左端点
    for (int i = arr.length-1; i >= 0 ; i--) {
        // 如何找：如果arr[i]大于已经发现的最小值，则arr[i]必须得调整位置
        if (arr[i] > min) {
            right = i;
        }
        min = Math.min(min, arr[i]);
    }
    return Math.max(0, left - right + 1);
}

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

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
public int longestIncreasingPath(int[][] arr) {
        int ans = 0;
        int N = arr.length;
        int M = arr[0].length;
        int[][] cache = new int[N][M];
    	// 遍历每个位置，求最长递增链长度的位置
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                ans = Math.max(ans, process(arr, i, j, cache));
            }
        }
        return ans;
    }

	// 求从位置i, j出发的最长递增链的长度
    private int process(int[][] arr, int i, int j, int[][] cache) {
        if (cache[i][j] != 0) {
            return cache[i][j];
        }
        int up = 0, down = 0, left = 0, right = 0;
        if (i > 0 && arr[i][j] < arr[i-1][j]) {
            up = process(arr, i - 1, j, cache);
        }
        if (i + 1 < arr.length && arr[i][j] < arr[i+1][j]) {
            down = process(arr, i + 1, j, cache);
        }
        if (j > 0 && arr[i][j] < arr[i][j-1]) {
            left = process(arr, i, j - 1, cache);
        }
        if (j + 1 < arr[0].length && arr[i][j] < arr[i][j+1]) {
            right = process(arr, i, j + 1, cache);
        }
        cache[i][j] = Math.max(Math.max(up, down), Math.max(left, right)) + 1;
        return cache[i][j];
    }

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

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
public int AOEGreedy(int[] x, int[] hp, int range) {
        int ans = 0;
        int n = x.length;
        // 元素i为AOE攻击最左侧点时，能否覆盖的最右侧元素位置
        int[] cover = new int[n];
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (x[j] - x[i] <= range) {
                    cover[i] = j;
                }
            }
        }
        for (int i = 0; i < n; i++) {
            if (hp[i] <= 0) {
                continue;
            }
            int hitTime = hp[i];
            // 将距离x[i] range 范围内的 hp 值减 hitTime
            for (int j = i; j <= cover[i]; j++) {
                hp[j] -= hitTime;
            }
            ans += hitTime;
        }
        return ans;
    }

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

https://leetcode-cn.com/problems/target-sum/

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
class Solution {
    public int findTargetSumWays(int[] nums, int target) {
        Map<Integer, Map<Integer, Integer>> cache = new HashMap<>();
        return process(nums, 0, target, cache);
    }
    
    public int process(int[] arr, int index, int rest, Map<Integer, Map<Integer, Integer>> cache) {
        // 读缓存判断是否命中
        if (cache.containsKey(index) && cache.get(index).containsKey(rest)) {
            return cache.get(index).get(rest);
        }
        // 最后，如果rest为0，说明正好算出target
        if (index == arr.length) {
            return rest == 0 ? 1 : 0;
        }
        int ans = process(arr, index + 1, rest - arr[index], cache) + 
                process(arr, index + 1, rest + arr[index], cache);
        // 更新缓存
        if (!cache.containsKey(index)) {
            cache.put(index, new HashMap<>());
        }
        cache.get(index).put(rest, ans);
        return ans;
    }
}

优化：转化为01背包

微信图片_20220419023158 
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
class Solution {
    public int findTargetNum(int[] arr, int target) {
        int sum = 0;
        // 都转为正数
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] < 0) {
                arr[i] = -arr[i];
            }
            sum += arr[i];
        }
        // 所有数字和小于target返回0
        // 所有数字和与target奇偶性不一致返回0
        // 转为01背包问题
        return sum < target || ((target & 1) ^ (sum & 1)) != 0 ? 0 : subset(arr, (target + sum) >> 1);
    }

    public int subset(int[] arr, int s) {
        if (s < 0) {
            return 0;
        }
        int n = arr.length;
        int[][] dp = new int[n + 1][s + 1];
        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 - arr[i - 1] >= 0) {
                    dp[i][j] += dp[i - 1][j - arr[i - 1]];
                }
            }
        }
        return dp[n][s];
    }
}

优化：动态规划的空间压缩（递推公式只与上一行有关，可用一维数组代替二维数组）

1
2
3
4
5
6
7
8
9
10
11
12
13
public int subset(int[] arr, int s) {
	if (s < 0) {
		return 0;
	}
	int[] dp = new int[s + 1];
	dp[0] = 1;
	for (int n : arr) {
		for (int i = s; i >= n; i--) {
			dp[i] += dp[i - n];
		}
	}
	return dp[s];
}

返回一个数组中子数组最大累加和

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public int maxSubArraySum(int[] arr) {
    int[] dp = new int[arr.length];
    dp[0] = arr[0];
    int maxSum = dp[0];
    for (int i = 1; i < arr.length; i++) {
        dp[i] = Math.max(dp[i-1] + arr[i], arr[i]);
        maxSum = Math.max(maxSum, dp[i]);
    }
    return maxSum;
}

// 优化：空间压缩（只用到其左侧位置）
public int maxSubArraySum2(int[] arr) {
    int dp = arr[0];
    int maxSum = dp;
    for (int i = 1; i < arr.length; i++) {
        dp = Math.max(dp + arr[i], arr[i]);
        maxSum = Math.max(maxSum, dp);
    }
    return maxSum;
}

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
public class solution {
    public int subArrMaxSumNotAdjacent(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        if (arr.length == 1) {
            return arr[0];
        }
        if (arr.length == 2) {
            return Math.max(arr[0], arr[1]);
        }
        // dp[i]表示0-i范围内的最大不相邻子序列累加和
        int[] dp = new int[arr.length];
        dp[0] = arr[0];
        dp[1] = arr[1];
        for (int i = 2; i < arr.length; i++) {
            dp[i] = Math.max(Math.max(dp[i-2] + arr[i], arr[i]), dp[i-1]);
        }
        return dp[arr.length - 1];
    }
}

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

微信图片_20220428014442

分治思路：将n个数字分为2份，每份分别计算所有可能的组合情况的序列和，求第一份中最接近的，第二份中最接近的，两份中取两个相加最接近的（先取左侧一个数字a，计算goal-a，在右侧二分查找），再比较三者哪个最接近

Think：分3，4，5...份行不行

1

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

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
45
46
47
48
49
50
public class Solution {
    /**
     * 给定一个有序数组arr，其中值可能为正、负、0。返回arr中每个数都平方之后不同的结果有多少种？
     * @param arr
     * @return
     */
    public int power2Diff1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        Set<Integer> powers = new HashSet<>();
        for (int i = 0; i < arr.length; i++) {
            powers.add(Math.abs(arr[i]));
        }
        return powers.size();
    }

    public int power2Diff2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int L = 0;
        int R = arr.length - 1;
        int ans = 0;
        int LAbs = 0;
        int RAbs = 0;
        while (L <= R) {
            LAbs = Math.abs(arr[L]);
            RAbs = Math.abs(arr[R]);
            if (LAbs < RAbs) {
                while (R >= 0 && Math.abs(arr[R]) == RAbs) {
                    R--;
                }
            } else if (LAbs > RAbs) {
                while (L < arr.length && Math.abs(arr[L]) == LAbs) {
                    L++;
                }
            } else {
                while (L < arr.length && Math.abs(arr[L]) == LAbs) {
                    L++;
                }
                while (R >= 0 && Math.abs(arr[R]) == RAbs) {
                    R--;
                }
            }
            ans++;
        }
        return ans;
    }
}

给定一个数组arr，先递减然后递增，返回arr中有多少个不同的数字？

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
public class Solution {
    public int diffNum(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int N = arr.length;
        int L = 0;
        int R = N-1;
        int diffNum = 0;
        while (L <= R) {
            int lvalue = arr[L];
            int rvalue = arr[R];
            if (lvalue < rvalue) {
                while (R >= 0 && arr[R] == rvalue) {
                    R--;
                }
            } else if (lvalue > rvalue) {
                while (L < N && arr[L] == lvalue) {
                    L++;
                }
            } else {
                while (L < N && arr[L] == lvalue) {
                    L++;
                }
                while (R >= 0 && arr[R] == rvalue) {
                    R--;
                }
            }
            diffNum++;
        }
        return diffNum;
    }
}