当前位置：首页 > news >正文

电子商务网站开发与设计报告手机百度搜索

news 2025/8/11 18:37:19

电子商务网站开发与设计报告,手机百度搜索,做电影网站不放国内主机,临朐网站建设经典题目选讲（5） 题目一：两个有序数组间相加和的TOP K问题题目描述：给定两个有序数组arr1和arr2，再给定一个整数k，返回来自arr1和arr2的两个数相加和最大的前k个，两个数必须分别来自两个数组。…

经典题目选讲（5）

题目一：两个有序数组间相加和的TOP K问题

题目描述：给定两个有序数组arr1和arr2，再给定一个整数k，返回来自arr1和arr2的两个数相加和最大的前k个，两个数必须分别来自两个数组。按照降序输出。

要求：时间复杂度达到O(klogk)。

输入描述：

第一行三个整数N, K分别表示数组arr1, arr2的大小，以及需要询问的数
接下来一行N个整数，表示arr1内的元素
再接下来一行N个整数，表示arr2内的元素

输出描述：

输出K个整数表示答案

示例：输入

5 4
1 2 3 4 5
3 5 7 9 11

输出：16 15 14 14

解题思路：一般涉及到 TopK 问题，首先应该想到使用堆。

我们可以知道 a[n-1] + b[n-1] 是整体的最大值，那么在这个最大值之后应该是哪个元素呢，应该是 $max\{a[n-1] + b[n-2], a[n-2] + b[n-1]\}$ ，它俩就是下一个可能最大值，绝不会出现比它们更大的元素。

我们可以使用一个大根堆，每个节点保存三个元素 $\{sum,idx1,idx2\}$ ，且 $a[idx1]+b[idx2]=sum$ ，两个下标用来表明该元素由两个数组中哪两个元素凑成的。

选择堆顶元素，其就是整体的最大值，将其删除，然后把两个可能的最大元素插入到堆中去：

$\{a[idx1-1]+b[idx2], idx1-1, idx2\}$

$\{a[idx1] + b[idx2-1], idx1, idx2-1\}$

这样进行 k 次操作后，就可以得到整体的 TopK 了。

注意：
1. 需要判重，因为两个节点的下标有可能相等
2. 测试数据出现无序的情况
代码如下：

package com.jz.day1119;import java.util.Arrays;
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Scanner;class HeapNode {int idx1; // arr1中的位置int idx2; // arr2中的位置int sum; // arr1[index1]+arr2[index2]public HeapNode(int idx1, int idx2, int sum) {this.idx1 = idx1;this.idx2 = idx2;this.sum = sum;}
}public class TwoArrayTopK {public static void main(String[] args) {Scanner sc = new Scanner(System.in);String[] param = sc.nextLine().split(" ");int N = Integer.parseInt(param[0]);int K = Integer.parseInt(param[1]);String[] arr1 = sc.nextLine().split(" ");String[] arr2 = sc.nextLine().split(" ");int[] res = solution(N, K, arr1, arr2);for (int i : res) {System.out.print(i + " ");}}private static int[] solution(int n, int k, String[] arr1, String[] arr2) {if (arr1 == null || arr2 == null || k < 1) {return null;}int[] nums1 = Arrays.stream(arr1).mapToInt(Integer::parseInt).sorted().toArray();int[] nums2 = Arrays.stream(arr2).mapToInt(Integer::parseInt).sorted().toArray();k = Math.min(k, n * n); // 数组求和最多有n*n种组合，如果k较大，则所有组合都会输出int[] res = new int[k];int resIndex = 0;//自定义比较器，实现大根堆PriorityQueue<HeapNode> maxHeap = new PriorityQueue<>((N1, N2) -> N2.sum - N1.sum);HashSet<String> positionSet = new HashSet<>(); //使用hashset解决超内存问题// 从右下角开始int index1 = nums1.length - 1;int index2 = nums2.length - 1;maxHeap.add(new HeapNode(index1, index2, nums1[index1] + nums2[index2]));positionSet.add(index1 + "_" + index2);while (resIndex < k) {HeapNode curr = maxHeap.poll();res[resIndex++] = curr.sum;index1 = curr.idx1;index2 = curr.idx2;if (index1 - 1 >= 0 && !positionSet.contains((index1 - 1) + "_" + index2)) {positionSet.add(index1 - 1 + "_" + index2);maxHeap.add(new HeapNode(index1 - 1, index2, nums1[index1 - 1] + nums2[index2]));}if (index2 - 1 >= 0 && !positionSet.contains(index1 + "_" + (index2 - 1))) {positionSet.add(index1 + "_" + (index2 - 1));maxHeap.add(new HeapNode(index1, index2 - 1, nums1[index1] + nums2[index2 - 1]));}}return res;}
}

题目二：子数组的最大累加和问题

题目描述：给定一个数组arr，返回子数组的最大累加和。例如，arr=[1,-2,3,5,-2,6,-1]，所有的子数组中，[3,5,-2,6]
可以累加出最大的和12，所以返回12。

要求：如果arr长度为N，要求时间复杂度为O(N)，额外空间复杂度为O(1)。

解题思路：看到这样的题目，首先想到的就是利用动态规划。这里，我们直接列出状态转移方程。

设置一个动态数组dp[i]：表示在下标i处之前的最大累加和（可能包括自己（例如起始位置），也可能不包括自己），以下是状态转移方程：

初始化：dp[0] = arr[0]

对于dp[i]:

如果在i-1的位置上dp[i-1]>0，则dp[i] = dp[i-1]+arr[i]。因为对于当前位置来说，加上一个正数可以让自己变大；

如果在i-1的位置上dp[i-1]<=0, 则dp[i] = arr[i]。如果当前位置之前是个负数或零，则当前最大累加和就是当前的值本身。

代码如下：

    private static int solution1(int[] arr) {if (arr == null || arr.length == 0) {return 0;}int[] dp = new int[arr.length];dp[0] = arr[0];int maxValue = dp[0];for (int i = 1; i < arr.length; i++) {if (dp[i - 1] > 0) {dp[i] = dp[i - 1] + arr[i];} else {dp[i] = arr[i];}maxValue = Math.max(maxValue, dp[i]);}return maxValue;}

然后，我们发现，其实没有必要使用动态规划数组。因为只需要两个变量来存储前后变化的值。因此，声明一个变量maxValue存储全局最大值，一个变量curr存储当前的累加和；初始化的时候curr等于arr[0]，则maxValue等于curr；遍历数组，如果curr小于等于0，则curr等于当前位置的值，否则curr等于curr加上当前位置的值。然后将curr和maxValue的值赋给maxValue。代码如下：

    private static int solution2(int[] arr) {if (arr == null || arr.length == 0) {return 0;}int curr = arr[0]; //记录当前累加和int maxValue = curr;for (int i = 1; i < arr.length; i++) {curr = curr > 0 ? curr + arr[i] : arr[i];maxValue = Math.max(curr, maxValue);}return maxValue;}

题目三：边界都是1的最大正方形大小

题目描述：给定一个NN的矩阵matrix，在这个矩阵中，只有0和1两种值，返回边框全是1的最大正方形的边长长度。

举例：

0 1 1 1 1
0 1 0 0 1
0 1 0 0 1
0 1 1 1 1
0 1 0 1 1
其中，边框全是1的最大正方形的大小为4*4，所以返回4。

输入描述：

第一行一个整数N。表示矩阵的长宽。
接下来N行，每行N个整数表示矩阵内的元素

输出描述：

输出一个整数表示答案

示例：

输入：

输出：

解题思路：

首先最先想到的方法便是美剧一个N*M的矩阵中的所有子矩阵，但是如果枚举矩阵中所有的子矩阵，则时间复杂度为O(NM)*O(NM)，这是因为一个矩形可由左上角与右下角决定，枚举左上角为O(NM)，枚举右下角为O(NM)。因此，这种方法效率不高。

那么如果枚举这个矩阵中所有的正方形呢？一个正方形可由左上角的点及其边长所决定，那么时间复杂度为O(NM)*min(N, M)，因为边长最多有min(N,M)种情况。

所以对于该题，有两种解法：

方法1：枚举所有的正方形，然后检查四个边，所以当M=N时，这是O(N^4)时间复杂度
方法2：采用预处理矩阵的方法，同样也是枚举所有的正方形，但是判断该正方形是否符合规则是，是O(1)的时间复杂度，所以当M=N时，这是O(N^3)时间复杂度。

这是以空间换时间的做法。

那么，如何预处理矩阵呢？用与原矩阵同样大小的两个矩阵，一个为right，一个为down。right[i][j]表示mat[i][j]的右边有多少个连续的1，包括自身；down[i][j]表示mat[i][j]的下边有多少个连续的1，包括自身。从右到左，从下到上依次填充两个矩阵。

对于以[row,col]为左上角，length作为边长的正方形，要想四个边全为1，只有满足如下条件：
- [row,col]代表左上方的位置，要求在该位置的下边最少有连续的length个1，该位置的右边最少有连续的length个1；
- [row + length - 1][col]代表左下角，要求该位置右边最少有连续的length个1；
- [row][col + length - 1]代表右上角，要求该位置下边最少有连续的length个1；

这样便构成了四个边都符合题目规则的正方形。

代码如下：

package com.jz.day1120;import java.util.Arrays;
import java.util.Scanner;/*** 边界都是1的最大正方形大小*/
public class MaxTangleSize {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int N = Integer.parseInt(sc.nextLine().trim());int[][] mat = new int[N][N];for (int i = 0; i < N; i++) {mat[i] = Arrays.stream(sc.nextLine().split(" ")).mapToInt(Integer::parseInt).toArray();}int res = solution(mat);System.out.println(res);}private static int solution(int[][] mat) {if (mat == null || mat.length == 0 || mat[0].length == 0) {return 0;}// right[i][j]表示m[i][j]的右边有多少个连续的1，包括自身int[][] right = new int[mat.length][mat[0].length];// down[i][j]表示m[i][j]的下边有多少个连续的1，包括自身int[][] down = new int[mat.length][mat[0].length];int nrow = mat.length;int ncol = mat[0].length;// 初始化右下角的位置right[nrow - 1][ncol - 1] = mat[nrow - 1][ncol - 1];down[nrow - 1][ncol - 1] = mat[nrow - 1][ncol - 1];// 初始化最后一行, 对列从右到左遍历for (int i = ncol - 2; i >= 0; i--) {if (mat[nrow - 1][i] == 1) {right[nrow - 1][i] = right[nrow - 1][i + 1] + 1;down[nrow - 1][i] = 1;}}// 初始化最后一列，对行从下到上遍历for (int i = nrow - 2; i >= 0; i--) {if (mat[i][ncol - 1] == 1) {right[i][ncol - 1] = 1;down[i][ncol - 1] = down[i + 1][ncol - 1] + 1;}}// 对于其他位置，从右向左，从下到上填充for (int i = nrow - 2; i >= 0; i--) {for (int j = ncol - 2; j >= 0; j--) {if (mat[i][j] == 1) {right[i][j] = right[i][j + 1] + 1;down[i][j] = down[i + 1][j] + 1;}}}// 以正方形边长为索引，从大到小依此遍历for (int length = Math.min(nrow, ncol); length >= 1; length--) {// 对于每个大小的边长，看是否存在以该值为边长的矩阵，满足四周都是1, 那么如果边长为length，则// (irow,icol)表示矩阵的左上角，要想满足正方形的条件，则要求在该点的右边(right矩阵)最少有连续的length个1，在该点的下边(down矩阵)最少有连续的length个1// (irow+length-1,icol) 表示矩阵的左下角， 要求在该点的右边(right矩阵)最少有连续的length个1// (irow, icol+length-1) 表示矩阵的右上角，要求在该点的下边(down矩阵)最少有连续的length个1// 因此，上述四个条件都满足，则构成一个正方形，返回for (int irow = 0; irow + length - 1 <= right.length - 1; irow++) {for (int icol = 0; icol + length - 1 <= down[0].length - 1; icol++) {if (right[irow][icol] >= length && down[irow][icol] >= length && right[irow + length - 1][icol] >= length && down[irow][icol + length - 1] >= length) {return length;}}}}return 0;}
}

题目四：找到字符串的最长无重复字符子串

题目描述：给定一个字符串str，返回str的最长无重复字符子串的长度。

举例：

str="abcd"，返回4
str="aabcb"，最长无重复字符子串为"abc"，返回3。
要求：如果str的长度为N，请实现时间复杂度为O(N)的方法。

输入描述：

一行一个字符串，长度不超过1000

输出描述：

输出一个数字表示最长子串的长度

示例：

输入：

abcabcbb

输出：

解题思路：对于求解字符子串的问题，可以考虑采用滑动窗口的策略。首先，创建一个集合windows，表示窗口内的子串无重复字符，窗口大小表示无重复子串的长度；然后声明两个变量，分别表示窗口的左边界L和右边界R。如果当前字符不在窗口中，则集合中添加该元素，同时窗口向右扩展；如果窗口中存在当前字符，则删除当前字符，并将左边界向右移动，直到不存在该字符为止。

代码如下：

package com.jz.day1120;import java.util.*;/*** 找出字符串的最长无重复字符子串*/
public class LongestUniqueStr {public static void main(String[] args) {Scanner sc = new Scanner(System.in);while (sc.hasNextLine()) {String str = sc.nextLine();int res = solution(str);System.out.println(res);}sc.close();}private static int solution(String str) {if (str == null || str.length() == 0) {return 0;}if (str.length() == 1) return 1;Set<Character> windows = new HashSet<>();int L = 0, R = 0, maxValue = 0;while (R < str.length()) {char chr = str.charAt(R++);while (windows.contains(chr)) {//移动左边界，缩小窗口windows.remove(str.charAt(L++));}windows.add(chr);maxValue = Math.max(maxValue, windows.size());}return maxValue;}
}

题目五：认识完美洗牌问题

问题1：给定一个长度为偶数的数组arr，长度记为2*N。前n个为左部分，后n个为右部分。arr可以表示为 $\{L_1,L_2...L_{n-1},L_n,R_1,R_2...R_{n-1},R_n \}$ ,请将数组调整成 $\{ R_1,L_1,R_2,L_2,...R_n,L_n \}$ 。

输入描述：

输入有包含两行，第一行包含一个整数n（ $1 \leq n \leq 10^5$ ，保证n为偶数），代表arr长度。第二行包含n个整数，代表数组arr（ $1 \leq arr_i \leq 10^8$ ）。

输出描述：

输出一行n个整数，代表调整后的数组arr。

示例：

输入：

6
1 2 3 4 5 6

输出：

4 1 5 2 6 3

要求：

时间复杂度O（N），额外空间复杂度O（1）。

解题思路：

先读取整个序列，然后直接按洗牌后的顺序打印就行，右边的牌索引号为 n/2 + i，左边的牌索引号为 i，其中0 <= i < n/2

代码如下：

package com.jz.day1120;import java.util.Scanner;public class CardShift_I {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = Integer.parseInt(sc.nextLine());String[] strs = sc.nextLine().split(" ");sc.close();for (int i = 0; i < n / 2; i++) {System.out.print(strs[n / 2 + i] + " " + strs[i] + " ");}}
}

问题2：给定一个数组arr，请将数组调整为依次相邻的数字，总是先<=、再>=的关系，并交替下去。比如数组中有五个数字，调整成[a,b,c,d,e],使之满足a<=b>=c<=d>=e。

示例：

输入：

6
1 2 3 4 5 6

输出：

1 3 2 5 4 6

解题思路：观察规律就是如果是有序的数组，那么只要每隔两个数进行交换，那就可以了。如果数组长度<=2,那么就不改变。

代码如下：

package com.jz.day1120;import java.util.Arrays;
import java.util.Scanner;/*** 完美洗牌问题（2）*/
public class CardShift_II {public static void main(String[] args) {Scanner sc = new Scanner(System.in);int n = Integer.parseInt(sc.nextLine());String[] arr = sc.nextLine().split(" ");sc.close();int[] nums = Arrays.stream(arr).mapToInt(Integer::parseInt).toArray();solution(n, nums);for (int i = 0; i < n; i++) {System.out.print(nums[i] + " ");}}private static void solution(int n, int[] nums) {if (nums.length <= 2) return;Arrays.sort(nums);for (int i = 1; i < n - 1; i += 2) {int temp = nums[i];nums[i] = nums[i + 1];nums[i + 1] = temp;}}
}

查看全文

http://www.lbrq.cn/news/2663425.html