blic class Main { public static void main(String[] args){ System.out.println(pow(2,2)); } public static double pow(double d,int n){ boolean flag = false; boolean zhisuFlag = false; int e = n; if(n<0){ e = -n; zhisuFlag = true; if(d == 0.0){ return 0; } } if(n%2==1&&d<0){ flag = true;//负数 } double result = power(d, e); if(zhisuFlag){ result = 1/result; } if(flag){ result = -result; } return result; } public static double power(double d,int n){ if(n == 1){ return d; } if(n == 0){ return 1; } double result = d; int k = 1; int pn = n; while (n/2>0) { n = n/2; result = result*result; k = k*2; } result =result * power(pn, n-k); return result; } }
九 Generate Parentheses
题意：给一个整数n，输出n对小括号所能组成的所有正常闭合的组合。如给出整数3，则输出 “((()))”, “(()())”, “(())()”, “()(())”, “()()()”。
思路：用递归实现所有情况，先定义left存左括号的个数，right存右括号数，首先输出一个“（”，如果剩余右括号多于左括号，可以输出右括号，否则只能输出左括号。
代码如下：
public class Main { public static void main(String[] args){ generateParenthesis(1); } public static List
generateParenthesis(int n) { ArrayList
aList = new ArrayList
(); if(n <= 0){ return null; } getList(n,n,"",aList); return aList; } public static void getList(int left,int right,String curStr,List
aList){ if(left > right){ return; } if(left == 0&&right == 0){ aList.add(curStr); } if(left > 0){ getList(left-1, right, curStr+"(", aList); } if(right > 0){ getList(left, right-1, curStr+")", aList); } } }
十、Validate Binary Search Tree
题意：判断一棵树是不是BST树。即判断一棵树的左节点是否全比根节点小，所有右节点是否全比根节点大。
思路一：最直接的方法是用中序遍历，发现不是有序的就不是BST，如果是有序那就是BST。
代码如下：
public static boolean isValidBST(TreeNode root) { if(root == null){ return true; } boolean a = isValidBST(root.left); pre = cur; cur = root; if(pre!=null&&pre.val>=cur.val){//要考虑到与子节点相同的情况 return false; } boolean b = isValidBST(root.right); return a&&b; }
思路二：递归遍历子节点，在遍历过程中分别给左子树和右子树设置左屏障和右屏障，什么意思呢？就是保证左子树的右屏障为根节点，也就是最大值小于等于根节点。右子树左屏障为根节点的值，即最小值大小等于根节点的值。
代码如下：
public static boolean isValidBST(TreeNode root) { int left = Integer.MIN_VALUE; int right = Integer.MAX_VALUE; if(root == null){ return true; } if(root.left == null&&root.right==null){ return true; } return validBinary(root, left, right); } public static boolean validBinary(TreeNode head,int left,int right){ if(head == null){ return true; } if(head.val<=left) { return false; } if(head.val>=right) { return false; } return validBinary(head.left,left,head.val)&&validBinary(head.right,head.val,right); }
就到这吧，整理的好累，其实LeetCode刷了有一些了，但常见的笔试面试题也就那么几类，个人觉得应该不会出太难。