剑指 Offer 66. 构建乘积数组image.png

  1. class Solution {
  2.     public int[] constructArr(int[] a) {
  3.         int len = a.length;
  4.         int[] arr = new int[len];
  5.         if(len==0)
  6.             return arr;
  7.         arr[0] = 1;
  8.         int t = a[0];
  9.         for(int i = 1; i < len; i++) {
  10.             arr[i] = t;
  11.             t*=a[i];
  12.         }
  13.         System.out.println(Arrays.toString(arr));
  14.         t = a[len-1];
  15.         for(int i = len-2;i>=0;i--) {
  16.             arr[i] *= t;
  17.             t *= a[i];
  18.         }
  19.         System.out.println(Arrays.toString(arr));
  20.         return arr;
  21.     }
  22. }

剑指 Offer 68 - I. 二叉搜索树的最近公共祖先

image.png

  1. class Solution {
  2.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  3.         if(root==null)
  4.             return null;
  5.         int min = Math.min(p.val,q.val);
  6.         int max = Math.max(p.val,q.val);
  7.         if(root.val==min || root.val==max)
  8.             return root;
  9.         if(root.val >min && root.val < max )
  10.             return root;
  11.         if(root.val > min && root.val > max)
  12.             return lowestCommonAncestor(root.left,p,q);
  13.         if(root.val<max && root.val<min)
  14.             return lowestCommonAncestor(root.right,p,q);
  15.         return null;
  16.     }
  17. }

剑指 Offer 68 - II. 二叉树的最近公共祖先

image.png

  1. /**
  2.  * Definition for a binary tree node.
  3.  * public class TreeNode {
  4.  *     int val;
  5.  *     TreeNode left;
  6.  *     TreeNode right;
  7.  *     TreeNode(int x) { val = x; }
  8.  * }
  9.  */
  10. class Solution {
  11.     public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
  12.         return find(p,q,root);
  13.     }
  15.     TreeNode find(TreeNode p,TreeNode q,TreeNode root) {
  16.         if(root==null)
  17.             return null;
  19.         TreeNode l = find(p,q,root.left);
  20.         TreeNode r = find(p,q,root.right);
  21.         if(l!=null &&  r!=null){
  22.             return root;
  23.         }
  24.         if(root==q || root==p) {
  25.             if(l!=null || r!=null)
  26.                 return root;
  27.             return root;
  28.         }
  30.         if(l!=null)
  31.             return l;
  32.         if(r!=null)
  33.             return r;
  35.         return null;
  37.     }
  38. }

剑指 Offer 60. n个骰子的点数

image.png

dp[i][j] 表示一共i个筛子，掷出j点数的次数
第i个筛子可以是1，2，3，4，5，6 ，所以dp[i][j] = dp[i-1][j-1] + dp[i-1][j-2] + dp[i-1][j-3] + dp[i-1][j-4] + ..dp[i-1][j-6] 

  1. class Solution {
  2.     public double[] dicesProbability(int n) {
  3.         int[][] dp = new int[n+1][6*n+1];
  4.         for(int i = 1; i <= 6; i++) {
  5.             dp[1][i]=1;
  6.         }
  8.         for(int i = 2; i <= n ;i++) {
  9.             for(int j = i;j<=6*i;j++) {
  10.                 for(int k = 1; k <= 6 && k<j ;k++) {
  11.                     dp[i][j] += dp[i-1][j-k];
  12.                 }
  13.             }
  14.         }
  16.         double count = 0;
  17.         for(int i = n;i<=6*n;i++) {
  18.             count+=dp[n][i];
  19.         }
  21.         double[] res = new double[6*n-n+1];
  22.         for(int i = 0 ; i < res.length; i++) {
  23.             res[i] = dp[n][i+n]/count;
  24.         }
  25.         return res;
  26.     }
  27. }

剑指 Offer 62. 圆圈中最后剩下的数字

image.png

  1. class Solution {
  2.     public int lastRemaining(int n, int m) {
  3.         int f = 0;
  4.         for(int i = 2; i <= n; i++) {
  5.             f = (m+f)%i;
  6.         }
  7.         return f;
  8.     }
  9. }