小米算法
1.题目描述
输入一棵二叉树，判断该二叉树是否是平衡二叉树。
在这里，我们只需要考虑其平衡性，不需要考虑其是不是排序二叉树
2.给顾客找零41分钱，现有25分,20分,10分,5分,1分类型的硬币，怎样找零钱使得顾客收到的硬币个数最少。
动态规划：
public static int coins3(int n){if(n<1) return -1;int[] dp=new int[n+1];//当前所需最小硬币数量dp[0]=0;dp[1]=1; for(int i=1;i<=n;i++){// dp[n]=Math.min(dp[n-25], dp[]);int min=0;if(i>=1)min=Math.min(dp[i-1],min);if(i>=5)min=Math.min(dp[i-5],min);if(i>=20)min=Math.min(dp[i-20],min);if(i>=25)min=Math.min(dp[i-25],min);dp[i]=min+1;}return dp[n];
}
3.判断两棵树是否相等
//定义一颗二叉树
public class TreeNode {int val;TreeNode left;TreeNode right;TreeNode(int x) { val = x; }}
public boolean isSameTree(TreeNode tree1,TreeNode tree2){if (tree1==null&&tree2==null){//若两棵树均为空return true;}else if (tree1==null||tree2==null){//若两棵树有一方为空return false;}if(tree1!=null&&tree2!=null){if(tree1.val!=tree2.val){return false;}else {return isSameTree(tree1.left,tree2.left)&&isSameTree(tree1.right,tree2.right);}}return false; }
4.添加最少的字符让字符串变成回文串
思路：如果能在原串S中找到最长的子序列L，这个子序列是回文，那么我们就能知道要插入多少个字符是的原串成为回文。
ans = (s) - (L)
问题转为求一个字符串的最长回文子序列，这个问题可以使用最长公共子序列的解法，解法如下：
1.求S的逆序串 S’,；
2.那么S和S’的用求最长公共子序列L，L即为S的最长回文子序列(这个规律是在推演中发现的)；
3.那么问题得解：ans = (s) - (L)。
例如： S = abca 那么 S’ = acba ，那么L = aba 那么答案就是1.即 a’c‘bca。其中’c’为插入的字符。
import java.util.Scanner;public class Main {public static void main(String[] args) {Scanner in = new Scanner(System.in); String s = in.nextLine(); StringBuffer sb1 = new StringBuffer(s); for (int i = 0; i < s.length()-1 && !isTrue(sb1.toString()); i++) {sb1.insert(s.length(), s.charAt(i));} System.out.println(sb1); // 输出得到的最短字符串}public static boolean isTrue(String s) { //判断是否回文boolean flag = true;for (int i = 0; i <= s.length() / 2; i++) {if (s.charAt(i) != s.charAt(s.length() - i - 1)) {flag = false;break;}}return flag;}
5.最长连续子序列
class Solution {public int findLengthOfLCIS(int[] nums) {int ans = 0, anchor = 0;for (int i = 0; i < nums.length; ++i) {if (i > 0 && nums[i-1] >= nums[i]) anchor = i;ans = Math.max(ans, i - anchor + 1);}return ans;}
