中级提升二
- 题目一：二叉树个数
- 题目二：完整括号字符串
- 题目三：去重数字对
- 题目四：两集合平均值问题
- 题目五：括号深度
- 题目六：最长有效括号字符字串
- 题目七：顺序栈
- 题目八：数字与字符的转化问题
- 题目九：二叉树权值和最大问题
- 题目十：部分有效二维数组查找数字
题目一：二叉树个数
- 题目：
- 暴力递归：
（1）总节点个数为n，若此时分为左子树 i 个节点，右子树就是n - i - 1，那么该种情况的情况个数为：process(i) * process(n - i - 1)
（2）将所有情况相加就是process(n)
（3）basecase：n < 0，return 0；n = 0，return 1；
public static int process(int n){ if (n < 0){ return 0; } if (n == 0){ return 1; } int res = 0; for (int left = 0; left < n; left++){ int leftWays = process(left); int rightWays = process(n - left - 1); res += leftWays * rightWays; } return res; }
- dp思路：
（1）递归函数只有一个可变参数，只需要一个一维的dp表进行填写
（2）初始化的时候dp[0] = 1；从dp[1]开始找寻规律
（3）根据递归函数可知：dp[ i ] += dp[ j ] * dp[ i - j - 1 ]
public static int process(int n){ int[] dp = new int[n + 1]; dp[0] = 1; for (int i = 1; i <= n; i ++){ //从dp[3]开始进行计算 for (int j = 0; j < i; j++){ dp[i] += dp[j] * dp[i - j - 1]; } } return dp[n]; }
题目二：完整括号字符串
- 题目：
- 问题一：如何判断括号的完整性
（1）使用count计数，初始值为0
（2） “ ( ”：左括号count++；“ ) ”：右括号count- -
（3）要求：整个过程中，count的值 >= 0
（4）结束后count的值 == 0
public static boolean test(String s){ char[] chs = s.toCharArray(); int count = 0; for (char ch : chs){ if (count < 0){ return false; } if (ch == '('){ count++; } if (ch == ')'){ count--; } } return count == 0; }
- 问题二：需要添加多少个括号
（1）使用问题一中count计数的方法
（2）若过程中count为0时，碰到一个 “ ) ”右括号，说明缺少一个左括号，num++
（3）若结束遍历后count > 0，那么就说明缺少 count 个右括号，num += count
public static int needParentheses(String s){ char[] chs = s.toCharArray(); int count = 0; int num = 0; for (char ch : chs){ if (ch == '('){ count++; } if (ch == ')'){ if (count == 0){ num++; }else { count--; } } } return num + count; }
题目三：去重数字对
- 题目：
- 例arr = [3，2，5，7，0，0] ; k = 2
结果：(0，2），（3，5），（5，7） - 思路：
（1）将所有数字加入一个哈希表
（2）遍历到一个数字后，寻找该数字 + k得到的数字是否在哈希表中
（3）若在将该数字对加入一个HashSet，若不存在遍历下一个数字
public static List<List<Integer>> allPair(int[] arr, int k){ HashSet<Integer> set = new HashSet<>(); for (int x : arr){ set.add(x); } List<List<Integer>> res = new ArrayList<>(); for (Integer x : set){ if (set.contains(x + k)){ res.add(Arrays.asList(x, x + k)); } } return res; }
题目四：两集合平均值问题
- 题目：
- 问题分析：
（1）当a，b集合的平均值相同的时候，magic无法操作，因为此时取数字，不可能做到a，b集合的平均值同时增大
（2）当a，b集合的平均值不相同的时候，magic不能从平均值较小的集合中取数字到较大的集合中，只可能从较大的集合中取数字到较小的集合中
（3）magic选取的数字一定是：较小的平均值< x < 较大的平均值
（4）在满足要求的数字中，为了实现magic的多次操作，每次选取都要选择数值最小的
public static int maxMagic(int[] arr1, int[] arr2){ double sum1 = 0; double sum2 = 0; for (int i : arr1){ sum1 += (double) i; } for (int i : arr2){ sum2 += (double) i; } if (avg(sum1, arr1.length) == avg(sum2, arr2.length)){ return 0; } //重定位 int[] arrMore = null; int[] arrLess = null; double sumMore = 0; double sumLess = 0; if (avg(sum1, arr1.length) > avg(sum2, arr2.length)){ arrMore = arr1; sumMore = sum1; arrLess = arr2; sumLess = sum2; }else { arrMore = arr2; sumMore = sum2; arrLess = arr1; sumLess = sum1; } //平均值大的排序方便操作 Arrays.sort(arrMore); //记录移动的数字，防止重复 HashSet<Integer> setLess = new HashSet<>(); //计数 int sizeMore = arrMore.length; int sizeLess = arrLess.length; int num = 0; for (int i : arrMore){ if (i < avg(sumMore, sizeMore) && i > avg(sumLess, sizeLess) && !setLess.contains(i)){ sumMore -= i; sumLess += i; sizeMore--; sizeLess++; setLess.add(i); num++; } } return num; } public static double avg(double sum, int size){ return sum / (double) size; }
题目五：括号深度
- 题目：
- 思路
（1）与题目二类似，使用count计数
（2）最大深度就是count能达到的最大值
public static int maxDepth(String s){ char[] chs = s.toCharArray(); int count = 0; int max = 0; for (char ch : chs){ if (ch == '('){ count++; max = Math.max(max, count); } if (ch == ')'){ count--; } } return max; }
题目六：最长有效括号字符字串
- 题目
给定一个只包含 ‘(’ 和 ‘)’ 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: “(()”
输出: 2
解释: 最长有效括号子串为 “()”
示例 2:
输入: “)()())”
输出: 4
解释: 最长有效括号子串为 “()()”
- 思路：
（1）创建字符串等大的数组dp[]，每个位置与字符串位置对应
（2）求以每一个位置的字符作为结尾，对应最长有效括号的长度
（3）若为左括号，一定不能以其结尾，结果为0
（4）若 i 位置为右括号，分析 i - 1 位置，考虑pre位置是否为左括号（pre：处 i - 1位置有效的括号后的前一个括号：i - dp[i -1] - 1 ），若不是左括号，则 i 位置为0，若是左括号，就是：i - 1位置的值加2再加上dp[pre - 1]位置的值
public static int maxLength(String s){ if (s == null || s.equals("")){ return 0; } char[] chs = s.toCharArray(); int[] dp = new int[chs.length]; int pre; int max = 0; for (int i = 0; i < chs.length; i++){ if (chs[i] == ')'){ //左括号均为0，只考虑右括号 pre = i - dp[i - 1] - 1; if (pre >= 0 && chs[pre] == '('){ //pre位置的检查 dp[i] = dp[i - 1] + 2 + (pre > 0 ? dp[pre - 1] : 0); } } max = Math.max(max, dp[i]); } return max; }
题目七：顺序栈
- 题目：
- 思路：
（1）目标：将栈中元素从栈顶最大到栈底最小的排序
（2）辅助栈：将辅助栈设计成栈顶最小到栈底最大的排序
（3）原栈中每次弹出一个元素，加入辅助栈之前判断目前的辅助栈顶的元素是否比该元素小，若小：则弹出辅助栈的元素到原栈中，直至栈顶比该元素大；若大直接加入
（4）当将原栈中元素全部移入辅助栈后，再将辅助栈的元素依次从栈顶到栈底加入原栈
public static void sortStack(Stack<Integer> stack){ Stack<Integer> temp = new Stack<>(); while (!stack.isEmpty()){ int x = stack.pop(); if (!temp.isEmpty() && x > temp.peek()){ //将不满足条件的元素从temp移动到stack stack.push(temp.pop()); } temp.push(x); } while (!temp.isEmpty()){ stack.push(temp.pop()); } }
题目八：数字与字符的转化问题
- 题目：
- 暴力递归：
（1）从左往右的尝试，在数组中index为当前遍历到的位置，尝试index位置的所有可能出现的情况后，index继续移动，直至数组结束即可
（2）若index位置出现0，说明前面转化出错，返回0
（3）若index位置为 1 或 2，可以考虑与 index + 1位置结合转化，也可以单独转化，产生两种递归的方式：直接到下一个位置，或者跳过下一个位置
（4）若index位置为3 ~ 9，就直接单独转化，没有产生多余的情况，直接递归到下一个位置
（5）若index等于数组长度，说明此次转化结束返回 1
public static int number(String str){ if (str == null || str.length() == 0){ return 0; } return process(str.toCharArray(), 0); } public static int process(char[] chs, int index){ //遍历数组 if (index == chs.length){ //index到最后一个说明此次递归得到了一种情况 return 1; } if (chs[index] == '0'){ //index位置出现0，说明此次递归出错 return 0; } if (chs[index] == '1'){ //index位置出现1 //单独转化index位置 int result = process(chs, index + 1); if (index + 1 < chs.length){ //结合index + 1位置转化 result += process(chs, index + 2); } return result; } if (chs[index] == '2') { //index位置出现2 //单独转化index位置 int result = process(chs, index + 1); if (index + 1 < chs.length && (chs[index + 1] <= '6')){ //结合index位置转化 //该转化时，数字小于等于26 result += process(chs, index + 2); } return result; } //index位置为 3 ~ 9 return process(chs, index + 1); }
- 动态规划：
（1）递归过程中，只有index一个参数只需要创建一维的dp数组
（2）根据递归函数：dp[chs.length] = 1
（3）dp[i]通过chs[i]考虑，若chs[i] =‘0’，那么dp[i] = 0；若chs[i] =‘1’，并且i + 2不越界dp[i] = dp[i + 1] +dp[i + 2]，越界则dp[i] = dp[i + 1]；同理考虑chs[i] =‘2’，只需要多一步判断chs[i + 1]是否小与’6‘，其余情况dp[i] = dp[i + 1]
（4）最终结果为dp[0]位置
public static int dpWays(String str){ if (str == null || str.length() == 0){ return 0; } char[] chs = str.toCharArray(); int[] dp = new int[chs.length + 1]; dp[chs.length] = 1; for (int i = chs.length - 1; i >= 0; i--){ if (chs[i] == '0'){ dp[i] = 0; }else if (chs[i] == '1'){ dp[i] = dp[i + 1]; if ((i + 2) < chs.length){ dp[i] += dp[i + 2]; } }else if (chs[i] == '2'){ dp[i] = dp[i + 1]; if ((i + 2) < chs.length && chs[i + 1] <= '6'){ dp[i] += dp[i + 2]; } }else { dp[i] = dp[i + 1]; } } return dp[0]; }
题目九：二叉树权值和最大问题
- 题目：
- 思路：
（1）设置最大权值，只有在叶子节点处更新
（2）递归方法遍历树，若不是叶子节点，移动当前节点位置，并记录路径权值，若是叶子节点停止移动，与最大权值比较
//maxSum，全局遍历，表示最大权值路径，只有到达叶节点时才更新 public static int maxSum = Integer.MIN_VALUE; public static int maxPath(Node head){ process(head, 0); return maxSum; } public static void process(Node p, int pre){ //p当前节点，pre当前节点以上的权值路径和 if (p.left == null && p.right == null){ maxSum = Math.max(maxSum, pre + p.value); } if (p.left != null){ process(p.left, pre + p.value); } if (p.right != null){ process(p.right, pre + p.value); } }
题目十：部分有效二维数组查找数字
- 题目：
- 思路：
例：如图为二维数组matrix，从该数组中寻找7是否存在
（1）遍历的时间复杂度为O(N * M)，N行数，M列数
（2）快捷方法：从右上角，10的位置开始遍历
（3）10 > 7，那么10下方的数组全部不能使用，移动到9
（4）9 > 7，继续移动到5
（5）5 < 7，向下移动到6，然后9
（6）最后通过9找到7
（7）这样时间复杂度为O(N + M)
public static boolean checkAim(int[][] matrix, int aim){ for (int i = matrix.length - 1; i >= 0;){ for (int j = 0; j < matrix[0].length;){ if (matrix[i][j] == aim){ return true; } if (matrix[i][j] < aim){ i--; if (i == -1){ //数组越界就没有找到 return false; } } if (matrix[i][j] > aim){ j++; if (j == matrix[0].length){ return false; } } } } return false; }
