算法-题目汇总-4
2021/8/9 12:35:57
本文主要是介绍算法-题目汇总-4，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！
1. 二叉树的最大子bst树 使用二叉树套路 bst树的特点左边的最大值小于根节点的值 右边的最小值 大于根节点的值
注意判断null值 因为结束条件返回的null
1 public TreeNode node(TreeNode head) {
2 BSTInfo process = process(head);
3 return process.maxSizeHead;
4 }
5
6 public BSTInfo process(TreeNode node) {
7 if (node == null) {
8 return null;
9 }
10 BSTInfo leftRes = process(node.left);
11 BSTInfo rightRes = process(node.right);
12 int maxNode = node.value;
13 int minNode = node.value;
14 int maxSize = 0;
15 TreeNode maxSizeHead = null;
16 boolean isbst = false;
17 if (leftRes != null) {
18 maxNode = Math.max(maxNode, leftRes.maxNode);
19 minNode = Math.min(minNode, leftRes.minNode);
20
21 }
22 if (rightRes != null) {
23 maxNode = Math.max(maxNode, rightRes.maxNode);
24 minNode = Math.min(minNode, rightRes.minNode);
25 }
// 左子树找到的最大bst的头结点
26 if (leftRes != null) {
27 maxSize = leftRes.maxSize;
28 maxSizeHead = leftRes.maxSizeHead;
29 }
// 右树找到的最大bst的头结点
30 if (rightRes != null && rightRes.maxSize > maxSize) {
31 maxSize = rightRes.maxSize;
32 maxSizeHead = rightRes.maxSizeHead;
33 }
34 // 根节点是bst的根节点 左树 和 右树 跟 根节点 可以连起来的判断 连起来肯定比上面的maxsize大
35 if ((leftRes == null || leftRes.isBst) && (rightRes == null || rightRes.isBst)) {
36 if ((leftRes == null || leftRes.maxNode < node.value) && (rightRes == null || rightRes.minNode > node.value)) {
37 isbst = true;
38 maxSize = (leftRes == null ? 0 : leftRes.maxSize) + (rightRes == null ? 0 : rightRes.maxSize) + 1;
39 maxSizeHead = node;
40 }
41 }
42 return new BSTInfo(maxSize, maxSizeHead, maxNode, minNode, isbst);
43 }
1 public class BSTInfo {
2 public Integer maxSize;
3 public TreeNode maxSizeHead;
4 public Integer maxNode;
5 public Integer minNode;
6 public boolean isBst;
7
8 public BSTInfo(Integer maxSize, TreeNode maxSizeHead, Integer maxNode, Integer minNode, boolean isBst) {
9 this.maxSize = maxSize;
10 this.maxSizeHead = maxSizeHead;
11 this.maxNode = maxNode;
12 this.minNode = minNode;
13 this.isBst = isBst;
14 }
15 }
2. 子数组的最大累加和
结果假设法
假设答案是数组中累加和最大并且 数量最多的那一段,所以在这段的开头位置是 前面数组相加是负数的index的下一项, 因为如果是正数就会包含在累加和中,
当出现等于-1的时候说明这段就可能是最大的累加和那段 所以开始相加 如果是结果的话 cur值会超过前面的max 如果超过就说明这段是 当下一次出现cur等于负数的时候
再判断下一段是不是最大累加和
1 public int maxSumArr(int[] arr) {
2 if (arr == null || arr.length == 0) {
3 return 0;
4 }
5 int cur = 0;
6 int max = Integer.MIN_VALUE;
7 for (int i : arr) {
8 cur += i;
9 max = Math.max(cur, max);
10 cur = cur < 0 ? 0 : cur;
11 }
12 return max;
13 }
3. 矩阵的最大累加和
-5 3 6 4
-7 9 -5 3
-10 1 -200 4
先求0行最大累加和
再求 0-1行最大累加和
再求 0-2行最大累加和
再求1-2行最大累加和
再求2行最大累加和
两行或者多行的如何求 以0-1行为例 (-5+-7),(3+9),(6+-5),(4,3) 求最大累加和
4. 路灯问题,在AB组成的数组中,A位置不需要照亮 B位置需要照亮 路灯可以照亮n-1 n n+1的位置,求最少需要多少个路灯
1 public int lessLeight(String str) {
2 if (str == null || str.isEmpty()) {
3 return 0;
4 }
5 char[] chars = str.toCharArray();
6 int leight = 0;
7 int index = 0;
8 while (index < chars.length) {
9 if (chars[index] == 'X') {
10 index++;
11 } else {
12 leight++;
13 if (index + 1 == chars.length) {
14 break;
15 } else {
16 if (chars[index + 1] == 'X') {
17 // index直接跳过这个x
18 index += 2;
19 } else {
20 // index+1 是.
21 index += 3;
22 }
23 }
24 }
25 }
26 return leight;
27 }
5. 给你先序遍历的数组 和 中序遍历的数组 返回后续遍历的数组
1 public int[] getPost(int[] pre, int[] mid) {
2 int length = pre.length;
3 int[] after = new int[length];
4 getPost(pre, mid, after, 0, length - 1, 0, length - 1, 0, length - 1);
5 return after;
6 }
7
8 public void getPost(int[] pre, int[] mid, int[] after, int p1, int p2, int m1, int m2, int a1, int a2) {
9 if (p1 > p2) {
10 return;
11 }
12 if (p1 == p2) {
13 after[a1] = pre[p1];
14 return;
15 }
16 after[a2] = pre[p1];
17 int find = m1;
18 while (mid[find] != pre[p1]) {
19 find++;
20 }
21 getPost(pre, mid, after, p1 + 1, p1 + find - m1, m1, find - 1, a1, a1 + find - m1 - 1);
22 getPost(pre, mid, after, p1 + find - m1 + 1, p2, find + 1, m2, a1 + find - m1, m2 - 1);
23 }
6. 数字转中文读法
1 public String numTo9(int num) {
2 if (num < 0 || num > 9) {
3 return "";
4 }
5 String[] names = {"一", "二", "三", "四", "五", "六", "七", "八", "九"};
6 return names[num - 1];
7 }
8
9 public String numTo99(int num, boolean hasBai) {
10 if (num < 1 || num > 99) {
11 return "";
12 }
13 if (num < 10) {
14 return numTo9(num);
15 }
16 int shi = num / 10;
17 if (shi == 1 && (!hasBai)) {
18 return "十" + numTo9(num % 10);
19 } else {
20 return numTo9(shi) + "十" + numTo9(num % 10);
21 }
22 }
23
24 public String numTo999(int num) {
25 if (num < 1 || num > 999) {
26 return "";
27 }
28 if (num < 100) {
29 return numTo99(num, false);
30 }
31 String res = numTo9(num / 100) + "百";
32 int i = num % 100;
33 if (i == 0) {
34 return res;
35 } else if (i >= 10) {
36 return res + numTo99(i, true);
37 } else {
38 return res + "零" + numTo9(i);
39 }
40 }
41
42 public String numTo9999(int num) {
43 if (num < 1 || num > 9999) {
44 return "";
45 }
46 if (num < 1000) {
47 return numTo999(num);
48 }
49 int i = num / 1000;
50 int j = num % 1000;
51 String res = numTo9(i) + "千";
52 if (j == 0) {
53 return res;
54 } else if (j > 100) {
55 res += numTo999(j);
56 } else {
57 res += "零" + numTo99(j, false);
58 }
59 return res;
60 }
61
62 public String numTo99999(int num) {
63 if (num < 1 || num > 99999999) {
64 return "";
65 }
66 if (num < 10000) {
67 return numTo9999(num);
68 }
69 int i = num / 10000;
70 int j = num % 10000;
71 String res = numTo9999(i) + "万";
72 if (j == 0) {
73 return res;
74 } else if (j > 1000) {
75 res += numTo9999(j);
76 } else {
77 res += "零" + numTo999(j);
78 }
79 return res;
80 }
81
82 public String numTo999999999(int num) {
83 if (num == 0) {
84 return "零";
85 }
86 String res = num < 0 ? "负" : "";
87 int i = Math.abs(num / 100000000);
88 int j = Math.abs(num % 100000000);
89 if (i == 0) {
90 return res + numTo99999(num);
91 }
92 res += numTo9999(i) + "亿";
93 if (j == 0) {
94 return res;
95 } else {
96 if (j < 10000000) {
97 return res + "零" + numTo99999(j);
98 } else {
99 return res + numTo99999(j);
100 }
101 }
102 }
7. 求完全二叉树的节点个数
先看右子树的最左节点有没有到最大的深度
达到了 说明左子树是满二叉树 个数是(2^n)-1
没达到 说明右子树是满二叉树 个数是(2^n)-1
结束条件是当前节点到底最底层的时候 return 1;
1 public int getCount(TreeNode head) {
2 return bs(head, 1, getrLevel(head, 1));
3 }
4
5 public int bs(TreeNode node, int level, int h) {
6 if (level == h) {
7 return 1;
8 }
9 if (getrLevel(node.right, level + 1) == h) {
10 // 右子树的最左节点到底了最大深度
11 return (1 << (h - level)) + bs(node.right, level + 1, h);
12 } else {
13 // h-level-1 右子树是满二叉树 但是比左数少一层
14 return (1 << (h - level - 1)) + bs(node.left, level + 1, h);
15 }
16 }
8. 最长递增子序列
3 1 2 6 3 4 的最长子序列是 1,2,3,4
dp问题,从3开始 找3左边比3小的数没有 所以最长子序列是1个
1左边没有 结果1
2左边有1 ,1的最长子序列是1 所以2结果是2
6左边比他小的是2 2的子序列是2 所以6的结果是3
3 左边比他小的是2 3结果是3
4左边比他小的是3 结果是4
9. 1234 能否被3整除? 转换成1+2+3+4 能否被3整除
这篇关于算法-题目汇总-4的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
- 2024-10-05小米13T Pro系统合集：性能与摄影的极致融合，值得你升级的系统ROM
- 2024-10-01基于Python+Vue开发的医院门诊预约挂号系统
- 2024-10-01基于Python+Vue开发的旅游景区管理系统
- 2024-10-01RestfulAPI入门指南：打造简单易懂的API接口
- 2024-10-01初学者指南：了解和使用Server Action
- 2024-10-01Server Component入门指南：搭建与配置详解
- 2024-10-01React 中使用 useRequest 实现数据请求
- 2024-10-01使用 golang 将ETH账户的资产平均分散到其他账户
- 2024-10-01JWT用户校验课程：从入门到实践
- 2024-10-01Server Component课程入门指南
