Java教程

算法-题目汇总-4

本文主要是介绍算法-题目汇总-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的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!