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的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!