常见算法题

import java.util.*;class TreeNode {int val;TreeNode left;TreeNode right;TreeNode() {}TreeNode(int val) { this.val = val; }TreeNode(int val, TreeNode left, TreeNode right) {this.val = val;this.left = left;this.right = right;}
}public class test_04_16 {//获取二叉树的最大深度public int maxDepth(TreeNode root) {if (root==null){return 0;}int left = maxDepth(root.left);int right = maxDepth(root.right);return Math.max(left,right)+1;}//二叉树的前序遍历//   1// 2//4 5 6 7public static List<Integer> preorderTraversal(TreeNode root) {Stack<TreeNode> stack = new Stack<>();List<Integer> ls = new ArrayList<>();if (root==null){return ls;}stack.push(root);while (!stack.isEmpty()){TreeNode node = stack.pop();ls.add(node.val);if (node.right!=null){stack.push(node.right);}if (node.left!=null){stack.push(node.left);}}return ls;}//   1// 2   3//4 5 6 7//中序遍历public List<Integer> inorderTraversal(TreeNode root) {List<Integer> res = new ArrayList<>();if (root==null){return res;}Stack<TreeNode> stack = new Stack<>();TreeNode p = root;while (p!=null||!stack.isEmpty()){if (p!=null){stack.push(p);p=p.left;}else{TreeNode node = stack.pop();res.add(node.val);if (node.right!=null){p=node.right;}}}return res;}//   1// 2   3//4 5 6 7//后序遍历public List<Integer> postorderTraversal(TreeNode root) {Stack<TreeNode> stack = new Stack<>();List<Integer> res = new ArrayList<>();TreeNode r = root;TreeNode p = root;while (p!=null||!stack.isEmpty()){if (p!=null){stack.push(p);p=p.left;}else{TreeNode node = stack.peek();if (node.right!=null&&node.right!=r){p=node.right;}else{TreeNode pNode = stack.pop();r=pNode;res.add(pNode.val);}}}return res;}//二叉树的层序遍历public List<List<Integer>> levelOrder(TreeNode root) {List<List<Integer>> res = new ArrayList<>();LinkedList<TreeNode> linkedList = new LinkedList<>();linkedList.offer(root);while (!linkedList.isEmpty()){List<Integer> ls = new ArrayList<>();int m = linkedList.size();for (int i=0;i<m;i++){TreeNode node = linkedList.poll();ls.add(node.val);if (node.left!=null){linkedList.offer(node.left);}if (node.right!=null){linkedList.offer(node.right);}}res.add(ls);}return res;}//二叉树的右视图public static List<Integer> rightSideView(TreeNode root) {List<Integer> res = new ArrayList<>();if(root==null){return res;}LinkedList<TreeNode> linkedList = new LinkedList<>();linkedList.offer(root);while (!linkedList.isEmpty()){int m = linkedList.size();for (int i=0;i<m;i++){if (i==m-1){TreeNode pNode = linkedList.poll();res.add(pNode.val);if (pNode.left!=null){linkedList.offer(pNode.left);}if (pNode.right!=null){linkedList.offer(pNode.right);}}}}return res;}//  4//9//二叉树求根节点到叶子结点数字之和public int sumNumbers(TreeNode root) {return dfs(root,0);}// 1private int dfs(TreeNode root, int prevSum) {if (root==null){return 0;}int sum = prevSum*10+root.val;if (root.left==null&&root.right==null){return sum;}else{int leftSum = dfs(root.left,sum);int rightSum = dfs(root.right,sum);return leftSum+rightSum;}}// 1//2 3public TreeNode invertTree(TreeNode root) {if (root==null){return null;}TreeNode leftRoot = invertTree(root.left);TreeNode rightRoot = invertTree(root.right);root.left=rightRoot;root.right=leftRoot;return root;}//二叉树的最近公共祖先//  1//2public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {if (root==null||root==p||root==q){return root;}TreeNode leftNode = lowestCommonAncestor(root.left, p, q);TreeNode rightNode = lowestCommonAncestor(root.right, p, q);if (leftNode!=null&&rightNode!=null){return root;}return leftNode!=null?leftNode:rightNode;}//二叉树展开为链表public void flatten(TreeNode root) {TreeNode cur = root;while (cur!=null){if (cur.left!=null){TreeNode next=cur.left;TreeNode pre = cur.left;while (pre.right!=null){pre=pre.right;}pre.right=cur.right;cur.left=null;cur.right=next;}cur=cur.right;}}//对称二叉树public boolean isSymmetric(TreeNode root) {return checkNode(root.left,root.right);}private boolean checkNode(TreeNode left, TreeNode right) {if (left==null&&right==null){return true;}if (left==null){return false;}if (right==null){return false;}if (left.val!=right.val){return false;}boolean leftB = checkNode(left.left, right.right);boolean rightB = checkNode(left.right, right.left);return leftB && rightB;}//完全二叉树的节点个数public int countNodes(TreeNode root) {if (root==null){return 0;}return countNodes(root.left)+countNodes(root.right)+1;}//二叉搜索数的众数public int[] findMode(TreeNode root) {HashMap<Integer, Integer> hashMap = new HashMap<>();Stack<TreeNode> stack = new Stack<>();TreeNode p = root;int max=1;while (p!=null||!stack.isEmpty()){if (p!=null){stack.push(p);p=p.left;}else{TreeNode node = stack.pop();if (hashMap.containsKey(node.val)){hashMap.put(node.val,hashMap.get(node.val)+1);}else{hashMap.put(node.val,1);}max=Math.max(hashMap.get(node.val),max);if (node.right!=null){p=node.right;}}}List<Integer> res = new ArrayList<>();for (Map.Entry<Integer, Integer> entry:hashMap.entrySet()){if (entry.getValue()==max){res.add(entry.getKey());}}return res.stream().mapToInt(Integer::intValue).toArray();}//合并二叉树public TreeNode mergeTrees(TreeNode root1, TreeNode root2) {if (root1==null){return root2;}if (root2==null){return root1;}TreeNode node = new TreeNode(root1.val + root2.val);node.left=mergeTrees(root1.left,root2.left);node.right=mergeTrees(root1.right,root2.right);return node;}// 路径总和public boolean hasPathSum(TreeNode root, int targetSum) {// 基本情况：如果当前节点为空，返回 falseif (root == null) {return false;}// 如果是叶子节点，并且 targetSum 等于当前节点的值，返回 trueif (root.left == null && root.right == null && targetSum == root.val) {return true;}// 递归检查左右子树，更新剩余的 targetSumreturn hasPathSum(root.left, targetSum - root.val) || hasPathSum(root.right, targetSum - root.val);}//验证二叉树public boolean isValidBST(TreeNode root) {return isValidBSTHelper(root,Long.MIN_VALUE,Long.MAX_VALUE);}public boolean isValidBSTHelper(TreeNode root, Long min, Long max){if (root==null){return true;}if (root.val>min&&root.val<max){boolean left = isValidBSTHelper(root.left, min, (long)root.val);boolean right = isValidBSTHelper(root.right, (long)root.val, max);return left&&right;}return false;}//二叉搜索树中的众数public static int[] getTest1(TreeNode root){HashMap<Integer, Integer> hashMap = new HashMap<>();int max = 1;TreeNode p = root;Stack<TreeNode> stack = new Stack<>();while (p!=null||!stack.isEmpty()){if (p!=null){stack.push(p);p=p.left;}else{TreeNode node = stack.pop();if (hashMap.containsKey(node.val)){hashMap.put(node.val,hashMap.get(node.val)+1);}else{hashMap.put(node.val,1);}max=Math.max(max,hashMap.get(node.val));if (node.right!=null){p=node.right;}}}List<Integer> res = new ArrayList<>();for (Map.Entry<Integer,Integer> entry:hashMap.entrySet()){if (entry.getValue()==max){res.add(entry.getKey());}}return res.stream().mapToInt(Integer::intValue).toArray();}public static String longestCommonPrefix(String[] strs){int minLen = Integer.MAX_VALUE;for (String str : strs) {if (str.length() < minLen) {minLen = str.length();}}int res =0;for (int i=0;i<minLen;i++){char c = strs[0].charAt(i);boolean flag = true;for (int j=1;j<strs.length;j++){if (strs[j].charAt(i)!=c){flag=false;break;}}if (flag){res++;}else{break;}}System.out.println(res);return strs[0].substring(0,res);}//多数元素//[3,2,3]public static int majorityElement(int[] nums){int x = nums[0];int n = 1;for (int i=1;i<nums.length;i++){if (nums[i]==x){n++;}else{if (n==0){x=nums[i];n=1;}else{n--;}}}return x;}//[3,2,2,3], val = 3//[2,3,2,3]//[2.2.3.3]//public static int removeElement(int[] nums, int val) {int i=0;int j=0;int count = 0;for (int k=0;k<nums.length;k++){if (nums[k]!=val){count++;}}while (i<count){if (nums[i]!=val){i++;}else{j=i;while (j<nums.length){if (nums[j]==val){j++;}else{int temp = nums[i];nums[i]=nums[j];nums[j]=temp;break;}}}}return i;}//反转字符串中的单词public static String reverseWords(String s){List<String> res = new ArrayList<>();int i=0;int j;//h ewhile (i<s.length()){//移除开头的空格i=removeSpace(s,i);if (i>=s.length()){break;}j=i;while (j<s.length()&&s.charAt(j)!=' '){j++;}res.add(s.substring(i,j));i=j;}Collections.reverse(res);StringBuilder rs = new StringBuilder();for (int m=0;m<res.size();m++){if (m==res.size()-1){rs.append(res.get(m));}else{rs.append(res.get(m)).append(" ");}}return rs.toString();}public static int removeSpace(String s,int i){while (i<s.length()&&s.charAt(i)==' '){i++;}return i;}//[1,2,3,4,5,6,7][1,2,3,4,5,6,7]//轮转数组public static void rotate(int[] nums, int k) {int[] newNums = new int[nums.length*2];for (int i=0;i<nums.length;i++){newNums[i]=nums[i];newNums[i+nums.length]=nums[i];}for (int i=0;i<nums.length;i++){nums[i]=newNums[nums.length-k%nums.length];}}public static void totateATimes(int[] nums){int temp = nums[nums.length-1];for (int i=nums.length-1;i>0;i--){nums[i]=nums[i-1];}nums[0]=temp;}//找出字符串中第一个匹配项的下标public int strStr(String haystack, String needle) {return haystack.indexOf(needle);}//[1,0,2]//[2,1,2]public static int candy(int[] ratings) {int[] nums = new int[ratings.length];Arrays.fill(nums,1);for (int i=1;i<nums.length;i++){if (ratings[i]>ratings[i-1]){nums[i]=nums[i-1]+1;}}for (int i = nums.length - 2; i >= 0; i--) {if (ratings[i] > ratings[i + 1]) {nums[i] = Math.max(nums[i], nums[i + 1] + 1);}}return Arrays.stream(nums).sum();}public static void main(String[] args) {candy(new int[]{1,0,2});}
}