剑指offer_Part7

2019-04-13 / 算法

剑指offer_Part7

友情提示: 代码在这里
本文参照该仓库学习,大家可以star

60 n 个骰子的点数

把 n 个骰子仍在地上，求点数和为 s 的概率。
使用一个二维数组 dp 存储点数出现的次数，其中 dp[i][j] 表示前 i 个骰子产生点数 j 的次数。

动态规划解法
空间复杂度：O(N2)

动态规划解法 + 旋转数组
空间复杂度：O(N)

61 扑克牌顺子

五张牌，其中大小鬼牌面大小为 0,可变换成任意数字。判断这五张牌是否能组成顺子。

62 圆圈中最后剩下的数

题目描述
让小朋友们围成一个大圈。然后，随机指定一个数 m，让编号为 0 的小朋友开始报数。每次喊到 m-1 的那个小朋友要出列唱首歌，然后可以在礼品箱中任意的挑选礼物，并且不再回到圈中，从他的下一个小朋友开始，继续 0...m-1 报数 .... 这样下去 .... 直到剩下最后一个小朋友，可以不用表演。

解题思路
约瑟夫环，圆圈长度为 n 的解可以看成长度为 n-1 的解再加上报数的长度 m。因为是圆圈，所以最后需要对 n 取余。

记公式吧...

另外的一种方法

public int LastRemaining_Solution(int n, int m) {
       LinkedList<Integer> list = new LinkedList<>();
       for(int i = 0;i<n;i++)
       {
           list.add(i);
       }
       int bt = 0;
       while(list.size()>1)
       {
           bt = (bt + m-1)%list.size();
           list.remove(bt);
       }
       return list.size()==1?list.get(0):-1;
   }

63 股票的最大利润

可以有一次买入和一次卖出，那么买入必须在前。求最大收益。
使用贪心策略，假设第 i 轮进行卖出操作，买入操作价格应该在 i 之前并且价格最低。

64 求 1+2+3+...+n

题目描述
要求不能使用乘除法、for、while、if、else、switch、case 等关键字及条件判断语句 A ? B : C。

解题思路
使用递归解法最重要的是指定返回条件，但是本题无法直接使用 if 语句来指定返回条件。

条件与 && 具有短路原则，即在第一个条件语句为 false 的情况下不会去执行第二个条件语句。利用这一特性，将递归的返回条件取非然后作为 && 的第一个条件语句，递归的主体转换为第二个条件语句，那么当递归的返回条件为 true 的情况下就不会执行递归的主体部分，递归返回。

本题的递归返回条件为 n <= 0，取非后就是 n > 0；递归的主体部分为 sum += Sum_Solution(n - 1)，转换为条件语句后就是 (sum += Sum_Solution(n - 1)) > 0。

65 不用加减乘除做加法

写一个函数，求两个整数之和，要求不得使用 +、-、* 、/ 四则运算符号。

66 构建乘积数组

给定一个数组 A[0, 1,..., n-1]，请构建一个数组 B[0, 1,..., n-1]，其中 B 中的元素 B[i]=A[0]* A[1]* ...* A[i-1]* A[i+1]* ...* A[n-1]。要求不能使用除法。

67 把字符串转换成整数

将一个字符串转换成一个整数，字符串不是一个合法的数值则返回 0，要求不能使用字符串转换整数的库函数。
Iuput:
+2147483647
1a33

Output:
2147483647
0

68 树中两个节点的最低公共祖先

二叉查找树

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root==null)
        {
            return root;
        }
        if(root.val > p.val&&root.val<q.val)
        {
            return lowestCommonAncestor(root.left,p,q);
        }
        if(root.val <p.val && root.val > q.val)
        {
            return lowestCommonAncestor(root.right,p,q);
        }

        return root;
    }

普通二叉树

注意p,q必然存在树内, 且所有节点的值唯一!!!
递归思想, 对以root为根的(子)树进行查找p和q, 如果root == null || p || q 直接返回root
表示对于当前树的查找已经完毕, 否则对左右子树进行查找, 根据左右子树的返回值判断:

左右子树的返回值都不为null, 由于值唯一左右子树的返回值就是p和q, 此时root为LCA
如果左右子树返回值只有一个不为null, 说明只有p和q存在与左或右子树中, 最先找到的那个节点为LCA
左右子树返回值均为null, p和q均不在树中, 返回null

public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if(root == null||root == p||root == q)
        {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left,p,q);
        TreeNode right = lowestCommonAncestor(root.right,p,q);
        return left==null?right:right==null?left:root;

    }

标题：剑指offer_Part7
作者：ellenbboe
地址：https://ellenbboe.github.io/articles/2019/04/13/1561009678358.html

Kosmos

---我们总得选择一条路去前行---