Java教程
高频算法和数据结构（四）
本文主要是介绍高频算法和数据结构（四），对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
题目一
数组为{3, 2, 2, 3, 1}，查询为(0, 3, 2)
意思是在数组里下标0~3这个范围上，有几个2？答案返回2。
假设给你一个数组arr，
对这个数组的查询非常频繁，都给出来
请返回所有查询的结果
解题：
预处理结构，生成如下一张表，这样要查1~4中有几个1，在这个表中用二分查就可以
public static class QueryBox2 {
private HashMap<Integer, ArrayList<Integer>> map;
public QueryBox2(int[] arr) {
map = new HashMap<>();
for (int i = 0; i < arr.length; i++) {
if (!map.containsKey(arr[i])) {
map.put(arr[i], new ArrayList<>());
}
map.get(arr[i]).add(i);
}
}
public int query(int L, int R, int value) {
if (!map.containsKey(value)) {
return 0;
}
ArrayList<Integer> indexArr = map.get(value);
// 查询 < L 的下标有几个
int a = countLess(indexArr, L);
// 查询 < R+1 的下标有几个
int b = countLess(indexArr, R + 1);
return b - a;
}
// 在有序数组arr中，用二分的方法数出<limit的数有几个
// 也就是用二分法，找到<limit的数中最右的位置
private int countLess(ArrayList<Integer> arr, int limit) {
int L = 0;
int R = arr.size() - 1;
int mostRight = -1;
while (L <= R) {
int mid = L + ((R - L) >> 1);
if (arr.get(mid) < limit) {
mostRight = mid;
L = mid + 1;
} else {
R = mid - 1;
}
}
return mostRight + 1;
}
}
题目二
https://leetcode.com/problems/maximum-subarray/返回一个数组中，子数组最大累加和
解题：
子数组问题
如果必须以0结尾的子数组，它可以扩展到什么程度，能让累加和最大
如果必须以1结尾的子数组，它可以扩展到什么程度，能让累加和最大..........
public static int maxSubArray(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int max = Integer.MIN_VALUE;
int cur = 0;
for (int i = 0; i < arr.length; i++) {
cur += arr[i];
max = Math.max(max, cur);
cur = cur < 0 ? 0 : cur;
}
return max;
}
public static int maxSubArray2(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
// 上一步，dp的值
// dp[0]
int pre = arr[0];
int max = arr[0];
for (int i = 1; i < arr.length; i++) {
pre = Math.max(arr[i], arr[i] + pre);
max = Math.max(max, pre);
}
return max;
}
题目三
返回一个二维数组中，子矩阵最大累加和
https://leetcode-cn.com/problems/max-submatrix-lcci/
解题：可以将矩阵转化为如题目二的一维数组来求解
先求0行数据，最大累加和多少？
求0,1行最大累加和数据是多少？.....
public static int maxSum(int[][] m) {
if (m == null || m.length == 0 || m[0].length == 0) {
return 0;
}
// O(N^2 * M)
int N = m.length;
int M = m[0].length;
int max = Integer.MIN_VALUE;
for (int i = 0; i < N; i++) {
// i~j
int[] s = new int[M];
for (int j = i; j < N; j++) {
for (int k = 0; k < M; k++) {
s[k] += m[j][k];
}
max = Math.max(max, maxSubArray(s));
}
}
return max;
}
public static int maxSubArray(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int max = Integer.MIN_VALUE;
int cur = 0;
for (int i = 0; i < arr.length; i++) {
cur += arr[i];
max = Math.max(max, cur);
cur = cur < 0 ? 0 : cur;
}
return max;
}
题目四
返回一个数组中，选择的数字不能相邻的情况下，
最大子序列累加和
解题：
动态规划：定义[i]表示0~i范围上在不相邻的情况下，怎么取最大累加和才能得到最好答案
public static int subSqeMaxSumNoNext(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
if (arr.length == 1) {
return arr[0];
}
int[] dp = new int[arr.length];
// dp[i] : arr[0..i]挑选，满足不相邻设定的情况下，随意挑选，最大的累加和
dp[0] = arr[0];
dp[1] = Math.max(arr[0], arr[1]);
for (int i = 2; i < arr.length; i++) {
int p1 = dp[i - 1];
int p2 = arr[i] + Math.max(dp[i - 2], 0);
dp[i] = Math.max(p1, p2);
}
return dp[arr.length - 1];
}
// 给定一个数组arr，在不能取相邻数的情况下，返回所有组合中的最大累加和
// 思路：
// 定义dp[i] : 表示arr[0...i]范围上，在不能取相邻数的情况下，返回所有组合中的最大累加和
// 在arr[0...i]范围上，在不能取相邻数的情况下，得到的最大累加和，可能性分类：
// 可能性 1) 选出的组合，不包含arr[i]。那么dp[i] = dp[i-1]
// 比如，arr[0...i] = {3,4,-4}，最大累加和是不包含i位置数的时候
//
// 可能性 2) 选出的组合，只包含arr[i]。那么dp[i] = arr[i]
// 比如，arr[0...i] = {-3,-4,4}，最大累加和是只包含i位置数的时候
//
// 可能性 3) 选出的组合，包含arr[i], 且包含arr[0...i-2]范围上的累加和。那么dp[i] = arr[i] + dp[i-2]
// 比如，arr[0...i] = {3,1,4}，最大累加和是3和4组成的7，因为相邻不能选，所以i-1位置的数要跳过
//
// 综上所述：dp[i] = Max { dp[i-1], arr[i] , arr[i] + dp[i-2] }
public static int maxSum(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int N = arr.length;
if (N == 1) {
return arr[0];
}
if (N == 2) {
return Math.max(arr[0], arr[1]);
}
int[] dp = new int[N];
dp[0] = arr[0];
dp[1] = Math.max(arr[0], arr[1]);
for (int i = 2; i < N; i++) {
dp[i] = Math.max(Math.max(dp[i - 1], arr[i]), arr[i] + dp[i - 2]);
}
return dp[N - 1];
}
题目五
原问题：Loading...
进阶问题：在原问题的基础上，增加一个原则：
相邻的孩子间如果分数一样，分的糖果数必须一样
返回至少需要分多少糖
解题：
预处理结构+贪心：
左边没东西就为1块糖，比左边大数字++，不再比左边大就返回1，left代表每一个点左边坡度
右边没有东西为1块糖，比右边大数字++，不再比右边大就返回1，right代表每一个点右边坡度
最后每个位置求left和right的最大值，便是最后答案
// 这是原问题的优良解
// 时间复杂度O(N)，额外空间复杂度O(N)
public static int candy1(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int N = arr.length;
int[] left = new int[N];
for (int i = 1; i < N; i++) {
if (arr[i - 1] < arr[i]) {
left[i] = left[i - 1] + 1;
}
}
int[] right = new int[N];
for (int i = N - 2; i >= 0; i--) {
if (arr[i] > arr[i + 1]) {
right[i] = right[i + 1] + 1;
}
}
int ans = 0;
for (int i = 0; i < N; i++) {
ans += Math.max(left[i], right[i]);
}
return ans + N;
}
// 这是原问题空间优化后的解
// 时间复杂度O(N)，额外空间复杂度O(1)
public static int candy2(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int index = nextMinIndex2(arr, 0);
int res = rightCands(arr, 0, index++);
int lbase = 1;
int next = 0;
int rcands = 0;
int rbase = 0;
while (index != arr.length) {
if (arr[index] > arr[index - 1]) {
res += ++lbase;
index++;
} else if (arr[index] < arr[index - 1]) {
next = nextMinIndex2(arr, index - 1);
rcands = rightCands(arr, index - 1, next++);
rbase = next - index + 1;
res += rcands + (rbase > lbase ? -lbase : -rbase);
lbase = 1;
index = next;
} else {
res += 1;
lbase = 1;
index++;
}
}
return res;
}
public static int nextMinIndex2(int[] arr, int start) {
for (int i = start; i != arr.length - 1; i++) {
if (arr[i] <= arr[i + 1]) {
return i;
}
}
return arr.length - 1;
}
public static int rightCands(int[] arr, int left, int right) {
int n = right - left + 1;
return n + n * (n - 1) / 2;
}
// 这是进阶问题的最优解
// 时间复杂度O(N), 额外空间复杂度O(1)
public static int candy3(int[] arr) {
if (arr == null || arr.length == 0) {
return 0;
}
int index = nextMinIndex3(arr, 0);
int[] data = rightCandsAndBase(arr, 0, index++);
int res = data[0];
int lbase = 1;
int same = 1;
int next = 0;
while (index != arr.length) {
if (arr[index] > arr[index - 1]) {
res += ++lbase;
same = 1;
index++;
} else if (arr[index] < arr[index - 1]) {
next = nextMinIndex3(arr, index - 1);
data = rightCandsAndBase(arr, index - 1, next++);
if (data[1] <= lbase) {
res += data[0] - data[1];
} else {
res += -lbase * same + data[0] - data[1] + data[1] * same;
}
index = next;
lbase = 1;
same = 1;
} else {
res += lbase;
same++;
index++;
}
}
return res;
}
public static int nextMinIndex3(int[] arr, int start) {
for (int i = start; i != arr.length - 1; i++) {
if (arr[i] < arr[i + 1]) {
return i;
}
}
return arr.length - 1;
}
public static int[] rightCandsAndBase(int[] arr, int left, int right) {
int base = 1;
int cands = 1;
for (int i = right - 1; i >= left; i--) {
if (arr[i] == arr[i + 1]) {
cands += base;
} else {
cands += ++base;
}
}
return new int[] { cands, base };
}
题目六
生成长度为size的达标数组，什么叫达标？
达标：对于任意的 i<k<j，满足 [i] + [j] != [k] * 2
给定一个正数size，返回长度为size的达标数组
解题：
将数据分为两部分
做变是个偶数域，右边是个奇数域，一个偶数+一个奇数不可能是某个数的两倍
分治思想，当你搞定一半规模的时候，你去想整合逻辑，怎么让它扩展出两倍的N都达标
public static int[] makeNo(int size) {
if (size == 1) {
return new int[] { 1 };
}
// size
// 一半长达标来
// 7 : 4
// 8 : 4
// [4个奇数] [3个偶]
int halfSize = (size + 1) / 2;
int[] base = makeNo(halfSize);
// base -> 等长奇数达标来
// base -> 等长偶数达标来
int[] ans = new int[size];
int index = 0;
for (; index < halfSize; index++) {
ans[index] = base[index] * 2 - 1;
}
for (int i = 0; index < size; index++, i++) {
ans[index] = base[i] * 2;
}
return ans;
}
题目七
字符串交错组成
https://leetcode.com/problems/interleaving-string/
解题：
样本对应模型动态规划
dp[i][j]:表示str1只拿i个字符，和str2只拿j个字符，能否组成str总的只拿i+j个字符？都是前缀，如果这张表可以填好，最右下角就是我们需要的答案。
public static boolean isInterleave(String s1, String s2, String s3) {
if (s1 == null || s2 == null || s3 == null) {
return false;
}
char[] str1 = s1.toCharArray();
char[] str2 = s2.toCharArray();
char[] str3 = s3.toCharArray();
if (str3.length != str1.length + str2.length) {
return false;
}
boolean[][] dp = new boolean[str1.length + 1][str2.length + 1];
dp[0][0] = true;
for (int i = 1; i <= str1.length; i++) {
if (str1[i - 1] != str3[i - 1]) {
break;
}
dp[i][0] = true;
}
for (int j = 1; j <= str2.length; j++) {
if (str2[j - 1] != str3[j - 1]) {
break;
}
dp[0][j] = true;
}
for (int i = 1; i <= str1.length; i++) {
for (int j = 1; j <= str2.length; j++) {
if (
(str1[i - 1] == str3[i + j - 1] && dp[i - 1][j])
||
(str2[j - 1] == str3[i + j - 1] && dp[i][j - 1])
) {
dp[i][j] = true;
}
}
}
return dp[str1.length][str2.length];
}
题目八
大楼轮廓线问题
https://leetcode.com/problems/the-skyline-problem/
解题：
生成一个有序表map
key代表高度，按照有序组织，value代表这个高度加入的次数，加入之后，有序表中拿出最大的key，logN复杂度，我就可以知道最大高度的变化
1位置加了高度4，次数变成2，最大高度没有变化，还是4
2位置加了高度5，次数1，我就知道在2位置最大高度由4变成了5
public static class Node {
public int x;
public boolean isAdd;
public int h;
public Node(int x, boolean isAdd, int h) {
this.x = x;
this.isAdd = isAdd;
this.h = h;
}
}
public static class NodeComparator implements Comparator<Node> {
@Override
public int compare(Node o1, Node o2) {
return o1.x - o2.x;
}
}
public static List<List<Integer>> getSkyline(int[][] matrix) {
Node[] nodes = new Node[matrix.length * 2];
for (int i = 0; i < matrix.length; i++) {
nodes[i * 2] = new Node(matrix[i][0], true, matrix[i][2]);
nodes[i * 2 + 1] = new Node(matrix[i][1], false, matrix[i][2]);
}
Arrays.sort(nodes, new NodeComparator());
// key 高度 value 次数
TreeMap<Integer, Integer> mapHeightTimes = new TreeMap<>();
TreeMap<Integer, Integer> mapXHeight = new TreeMap<>();
for (int i = 0; i < nodes.length; i++) {
if (nodes[i].isAdd) {
if (!mapHeightTimes.containsKey(nodes[i].h)) {
mapHeightTimes.put(nodes[i].h, 1);
} else {
mapHeightTimes.put(nodes[i].h, mapHeightTimes.get(nodes[i].h) + 1);
}
} else {
if (mapHeightTimes.get(nodes[i].h) == 1) {
mapHeightTimes.remove(nodes[i].h);
} else {
mapHeightTimes.put(nodes[i].h, mapHeightTimes.get(nodes[i].h) - 1);
}
}
if (mapHeightTimes.isEmpty()) {
mapXHeight.put(nodes[i].x, 0);
} else {
mapXHeight.put(nodes[i].x, mapHeightTimes.lastKey());
}
}
List<List<Integer>> ans = new ArrayList<>();
for (Entry<Integer, Integer> entry : mapXHeight.entrySet()) {
int curX = entry.getKey();
int curMaxHeight = entry.getValue();
if (ans.isEmpty() || ans.get(ans.size() - 1).get(1) != curMaxHeight) {
ans.add(new ArrayList<>(Arrays.asList(curX, curMaxHeight)));
}
}
return ans;
}
这篇关于高频算法和数据结构（四）的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
JAVA语音识别项目项目实战入门教程11-25
-
JAVA云原生项目实战入门教程11-25
-
Java语音识别项目入门：新手必读指南11-25
-
Java语音识别项目入门：轻松开始你的第一个语音识别项目11-25
-
Java语音识别项目入门详解11-25
-
Java语音识别项目教程：从零开始的详细指南11-25
-
JAVA语音识别项目教程：初学者指南11-25
-
Java语音识别项目教程：初学者指南11-25
-
JAVA云原生入门：新手指南与基础教程11-25
-
Java云原生入门：从零开始的全面指南11-25
-
Java云原生入门：新手必读教程11-25
-
JAVA云原生教程：新手入门及实战指南11-25
-
Java云原生教程：新手入门指南11-25
-
Java云原生教程：入门与实践指南11-25
-
Java对接阿里云智能语音服务项目实战教程11-25
栏目导航
