Java教程
算法-题目汇总-1
本文主要是介绍算法-题目汇总-1，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
1. 给一个数组标识不同距离的点 给一个长度为5的绳子看最多能覆盖多少个点
思路1: 使用二分查找到大于等于当前点-5的最左的点 坐标相减得到结果 logn
思路2: 时间窗口的模式,l在第一个点 r右移 满足条件长度加一 l走完数组结束 左右两个边界都不需要回退 o(n)
1 public int cover(int[] arr, int length) {
2 int l = 0;
3 int r = 1;
4 int max = Integer.MIN_VALUE;
5 while (l <= arr.length - 1 && r <= arr.length - 1) {
6 if (arr[r] - arr[l] <= length) {
7 r++;
8 max = Math.max(max, r - l);
9 } else {
10 l++;
11 }
12 }
13 return max;
14 }
2. 装6个或8个的袋子,如何使用最少的袋子装指定数量的苹果 袋子必须装满
思路1: 奇数肯定不行,先确定8个的袋子最多能用多少 剩下的用6去装 不够8个袋子的减一 当剩余的苹果超过24的时候就可以停止
打表法: 对于输入一个整数 返回一个整数的题,先普通做法做出来 ,再根据输入输出规律 进行优化 40%可以有规律
3. 两只牛吃草,一次只能吃4的幂次方数的草 先手/后手哪个能赢
1 public String process(int n) {
2 if (n < 5) {
3 return (n == 0 || n == 2) ? "后手" : "先手";
4 }
5 int eat = 1;
6 while (eat <= n) {
7 if (process(n - eat).equals("后手")) {
// 子问题的后手是母问题的先手
8 return "先手";
9 }
10 if (eat > n / 4) {
11 break;
12 }
13 eat *= 4;
14 }
15 return "后手";
16 }
17
18 public String winner(int n) {
19 if (n % 5 == 0 || n % 5 == 2) {
20 return "后手";
21 }else {
22 return "先手";
23 }
24 }
4. RRGGR 变成 RRRGG
使用预处理辅助数组,
统计从0-n-1 有几个R
{1,2,2,2,3}
统计0-n-1有几个G
{2,2,2,1,0}
1 public int minPaint(String s) {
2 char[] chars = s.toCharArray();
3 int n = chars.length;
4 // 使用辅助数组统计从0到n-1有多少R
5 // 使用辅助数组统计从0到n-1有多少G
6 for (int i = 0; i < n; i++) {
7 if (i == 0) {
8 // 统计0~n-1有多少个R 需要染成G
9 } else if (i == n) {
10 // 统计0~n-1有多少个G 需要染成R
11 }else {
12 // 统计0~i有多少个R 需要染成G i+1~n-1有多少个G 需要染成R
13 }
14 }
15 return Math.min(1,2);
16 }
5. 给定一个N*N的矩阵 只有0和1两种值,返回边框全是1的最大正方形边长长度
001110
001010
101110
答案3
n*n的矩阵
子长方形规模n^4个 子正方形规模n^3个
从00遍历各个子正方形,使用辅助矩阵判断遍历到的正方形边是否是1
辅助矩阵记录这在当前点往右有多少个连续的1
在当前点往下有多少个连续的1
1 public int maxAllOneBorder(int[][] m) {
2 int c = m.length;
3 int r = m[0].length;
4 // 行
5 for (int row = 0; row < c; row++) {
6 // 列
7 for (int col = 0; col < r; col++) {
8 // 边长
9 for (int border = 0; border <= Math.min(c - row, r - col); border++) {
10 // 判断在某行某列某边长上是否全是1
11 // 使用辅助矩阵记录从左往右有多少连续的1
12 // 使用辅助矩阵记录从上往下有多少连续的1
13 }
14 }
15 }
16 }
6. 给定一个函数 可以等概率返回一个1~5的数字 加工出一个等概率返回1~7的函数
可以等概率返回a~b的一个数,加工出可以返回c~d的函数
p概率返回0 以1-p概率返回1 加工出一个等概率返回0和1的函数 执行两次,当出现10的时候返回0 出现01的时候返回1 因为10的概率是 p* 1-p 10的概率是1-p * p两个概率相等
1 // 等概率返回1-5
2 public int f() {
3 return (int) (Math.random() * 5 + 1);
4 }
5 // 二进制发生器
6 public int binaryTool() {
7 int res = 0;
8 do {
9 res = f();
10 } while (res == 3);
11 return res < 3 ? 0 : 1;
12 }
13 // 等概率返回1-7
14 public int getNum() {
15 int res = 0;
16 do {
17 res = (binaryTool() << 2) + (binaryTool() << 1) + binaryTool();
18 } while (res == 7);
19 return res + 1;
20 }
7. 给定一个非负整数n 代表二叉树的节点数 返回能形成多少种不同结构的二叉树
1 public int process(int n) {
2 if (n == 0) {
3 return 1;
4 }
5 if (n < 0) {
6 return 0;
7 }
8 if (n == 1) {
9 return 1;
10 }
11 if (n == 2) {
12 return 2;
13 }
14 int res = 0;
15 for (int i = 0; i <= n - 1; i++) {
// 左树是0个节点
16 int leftNum = process(i);
// 右树是剩余的节点 -1是要减去一个头结点
17 int rightNum = process(n - i - 1);
18 res += leftNum * rightNum;
19 }
20 return res;
21 }
8. 一个括号字符串,需要在任意位置添加括号,将其转化为一个完整的括号字符串,需要添加多少个括号
1 public int addparentheses(String str) {
2 char[] chars = str.toCharArray();
3 int count = 0;
4 int res = 0;
5 for (int i = 0; i < chars.length; i++) {
6 if (chars[i] == ')') {
7 if (count == 0) {
8 // count等于0的时候直接res++的原因是
9 // 这一步应该count-- 然后res++ , count-- 按照逻辑应该res++ count+1
10 // 最后结果还是count=0 res+1
11 res++;
12 } else {
13 count--;
14 }
15 } else {
16 count++;
17 }
18 }
19 // count代表应该添加的右括号数
20 // res代表应该添加的左括号数
21 return count + res;
22 }
9. 从一个集合中取出一个元素放到另一个集合中,要求移动之后两个集合的平均值要提高 不能把一个集合取空 不能放入集合中已有的值 求最大多能移动几次
两个集合评价值一样返回0 只能平均值大的集合移动到平均值小的集合,先移动小的
1 public int ways(int[] arr) {
2 if (arr == null || arr.length == 0) {
3 return -1;
4 }
5 int sum = 0;
6 for (int i = 0; i < arr.length; i++) {
7 sum += arr[i];
8 }
9 if (sum % arr.length != 0) {
10 return -1;
11 }
12 int avg = sum / arr.length;
13 int leftSum = 0;
14 int max = 0;
15 for (int j = 0; j < arr.length; j++) {
16 // 左边已有数量 左边的桶数 * 平均值
17 int left = leftSum - (j * avg);
18 // 左边已有 当前这个 右边的桶数*平均值
19 int right = sum - leftSum - arr[j] - ((arr.length - 1 - j) * avg);
20 if (left < 0 && right < 0) {
21 // 两边都是负数 说明都不够平均值 取和
22 max = Math.max(max, Math.abs(left) + Math.abs(right));
23 } else {
24 // 一个为负数 一个为正数 或者两个都是正数
25 max = Math.max(max, Math.max(Math.abs(left), Math.abs(right)));
26 }
27 leftSum+=arr[j];
28 }
29 return max;
30 }
10. 求括号字符串最大深度((()))深度是3 左括号count++ 右括号count-- count的最大值就是最大深度
11. 求括号字符串最长子串 dp问题,求对应字符前面的合法子串,''('' 字符直接为0 '')'' 字符求前面符合条件的子串
1 public int maxLength(String str) {
2 char[] chars = str.toCharArray();
3 int[] dp = new int[chars.length];
4 int res = 0;
5 for (int i = 1; i < chars.length; i++) {
6 if (chars[i] == ')') {
7 // 左括号直接是0 不用统计
8 // pre位置是符合条件的前一个位置
9 int pre = i - dp[i - 1] - 1;
10 if (pre >= 0 && chars[pre] == '(') {
11 // (())(()) 适配这种情况
12 dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0);
13 }
14 }
15 res = Math.max(res, dp[i]);
16 }
17 return res;
18 }
12. 返回二叉树每条路径的最大权重
使用二叉树套路解
1 public int process2(TreeNode node) {
2 if (node.left == null && node.right == null) {
3 return node.value;
4 }
5 int next = Integer.MIN_VALUE;
6 int next2 = Integer.MIN_VALUE;
7 if (node.left != null) {
8 next = process2(node.left);
9 }
10 if (node.right != null) {
11 next2 = process2(node.right);
12 }
13 int max = Math.max(next, next2);
14 return node.value + max;
15 }
13. 二维数组 从左到右 从上到下都有序 找某个数
左边都是0 右边都是1 找1最多的数组
1 /** 2 * 1 3 5 10 3 * 2 6 11 13 4 * 7 9 12 17 5 * -------- 6 * 00011 7 * 01111 8 * 01111 9 * 00111 10 */
目标7 从最右开始10大于7左移 小于7下移 大于7左移 小于7下移 大于7左移
从右边开始 左边是1左移 左边是0记录最大值添加list然后下移一次类推
14. 洗衣机问题 n个洗衣机中有衣服 把衣服平均分到各个洗衣机中 每次只能移动一件衣服
1 public int ways(int[] arr) {
2 if (arr == null || arr.length == 0) {
3 return -1;
4 }
5 int sum = 0;
6 for (int i = 0; i < arr.length; i++) {
7 sum += arr[i];
8 }
9 if (sum % arr.length != 0) {
10 return -1;
11 }
12 int avg = sum / arr.length;
13 int leftSum = 0;
14 int max = 0;
15 for (int j = 0; j < arr.length; j++) {
16 // 左边已有数量 左边的桶数 * 平均值
17 int left = leftSum - (j * avg);
18 // 左边已有 当前这个 右边的桶数*平均值
19 int right = sum - leftSum - arr[j] - ((arr.length - 1 - j) * avg);
20 if (left < 0 && right < 0) {
21 // 两边都是负数 说明都不够平均值 取和
22 max = Math.max(max, Math.abs(left) + Math.abs(right));
23 } else {
24 // 一个为负数 一个为正数 或者两个都是正数
25 max = Math.max(max, Math.max(Math.abs(left), Math.abs(right)));
26 }
27 leftSum+=arr[j];
28 }
29 return max;
30 }
15. 顺时针打印矩阵
0 1 2 3
9 10 11 4
8 7 6 5
思路: 先定义两个点0和5 打印 再往里缩 打印
1 public void print(int[][] matrix) {
2 int a = 0, b = 0;
3 int c = matrix.length - 1, d = matrix[0].length - 1;
4 while (a <= c && b <= d) {
5 f(matrix, a++, b++, c--, d--);
6 }
7 }
8
9 public void f(int[][] matrix, int a, int b, int c, int d) {
10 if (a == c) {
11 for (int i = b; i <= d; i++) {
12 System.out.print(matrix[a][i] + " ");
13 }
14 } else if (b == d) {
15 for (int i = a; i <= c; i++) {
16 System.out.print(matrix[i][b] + " ");
17 }
18 } else {
19 int la = a;
20 int lb = b;
21 int rc = c;
22 int rd = d;
23 while (lb != d) {
24 System.out.print(matrix[a][lb++] + " ");
25 }
26 while (la != c) {
27 System.out.print(matrix[la++][d] + " ");
28 }
29 while (rd != b) {
30 System.out.print(matrix[c][rd--] + " ");
31 }
32 while (rc != a) {
33 System.out.print(matrix[rc--][a] + " ");
34 }
35 }
36 }
16. 矩阵顺时针移动数字
0 1 2
7 8 3
6 5 4
-----
6 7 0
5 8 1
4 3 2
思路: 先四个角数子调整 0 2 4 6 再1 3 5 7 调整
1 public void circleRotate(int[][] matrix) {
2 int a = 0, b = 0;
3 int c = matrix.length - 1, d = matrix[0].length - 1;
4 while (a <= c && b <= d) {
5 rotate(matrix, a++, b++, c--, d--);
6 }
7 }
8
9 public void rotate(int[][] maxtrix, int a, int b, int c, int d) {
10 int times = d - b;
11 for (int i = 0; i < times; i++) {
12 int temp = maxtrix[a][b + i];
13 maxtrix[a][b + i] = maxtrix[c - i][b];
14 maxtrix[c - i][b] = maxtrix[c][d - i];
15 maxtrix[c][d - i] = maxtrix[a + i][d];
16 maxtrix[a + i][d] = temp;
17 }
18 }
17. zigzag规则打印矩阵
思路: 刚开始两个点都在左上角,然后a右移 到头的话 往下移 b往下移 到头的话 往右移 当a点移出矩阵的时候结束
1 public void print(int[][] matrix) {
2 int a1 = 0, b1 = 0, c1 = 0, d1 = 0;
3 int endR = matrix.length - 1;
4 int endC = matrix[0].length - 1;
5 boolean flag = false;
// 移出矩阵时结束
6 while (a1 != endR + 1) {
7 print(matrix, a1, b1, c1, d1, flag);
8 a1 = b1 == endC ? a1 + 1 : a1;
9 b1 = b1 == endC ? b1 : b1 + 1;
10 d1 = c1 == endR ? d1 + 1 : d1;
11 c1 = c1 == endR ? c1 : c1 + 1;
12 flag = !flag;
13 }
14 }
15
16
17 public void print(int[][] matrix, int a, int b, int c, int d, boolean flag) {
18 if (flag) {
19 while (a != c + 1) {
20 System.out.print(matrix[a++][b--] + " ");
21 }
22 } else {
23 while (c != a - 1) {
24 System.out.print(matrix[c--][d++] + " ");
25 }
26 }
27
28 }
18. 字符串数组 返回前k个出现次数最多的字符
使用hash统计出现次数,小根堆求前k个
19. 实现一个结构,可以添加add字符串 打印前k个最长的字符串 打印某个字符串个数
建立词频表
堆
记录字符串在堆中的位置index
这篇关于算法-题目汇总-1的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
-
Java中定时任务实现方式及源码剖析11-24
-
Java中定时任务实现方式及源码剖析11-24
-
鸿蒙原生开发手记：03-元服务开发全流程（开发元服务，只需要看这一篇文章）11-24
-
细说敏捷：敏捷四会之每日站会11-24
-
Springboot应用的多环境打包入门11-23
-
Springboot应用的生产发布入门教程11-23
-
Python编程入门指南11-23
-
Java创业入门：从零开始的编程之旅11-23
-
Java创业入门：新手必读的Java编程与创业指南11-23
-
Java对接阿里云智能语音服务入门详解11-23
-
Java对接阿里云智能语音服务入门教程11-23
-
JAVA对接阿里云智能语音服务入门教程11-23
-
Java副业入门：初学者的简单教程11-23
-
JAVA副业入门：初学者的实战指南11-23
-
JAVA项目部署入门：新手必读指南11-23
栏目导航
