lc69. x的平方根（EZ）

给你一个非负整数 x ，计算并返回 x 的 算术平方根 。

由于返回类型是整数，结果只保留 整数部分 ，小数部分将被 舍去 。

**注意：**不允许使用任何内置指数函数和算符，例如 pow(x, 0.5) 或者 x ** 0.5 。

示例 1：

输入：x = 4
输出：2

示例 2：

输入：x = 8
输出：2
解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。

提示：

  • 0 <= x <= 2^31 - 1

既然不能使用内置的pow函数，而且不要求精度，那么可以考虑用二分法

为啥可以用二分法呢？回想一下以前高中数学的时候，老师有讲过一种东西叫做零点法（如果忘了就回去翻一下高中数学必修3和选修2-3，有讲过一种粗略计算零点的方法，就是这个零点法）——所以我们在对一个数做粗略的平方根计算的时候就可以考虑用零点法，也就是计算机科学里的二分法

class Solution {
    public int mySqrt(int x) {
        int l = 0, r = x, ans = -1;
        while (l <= r) {
            int mid = (l + r) / 2;
            if ((long) mid * mid > x) {
                r = mid - 1;
            } else if ((long) mid * mid < x) {
                l = mid + 1;
                ans = mid;
            } else {
                return mid;
            }
        }
        return ans;
    }
}

lc50. Pow(x, n) （MD）

实现 pow(x, n) ，即计算 x 的整数 n 次幂函数（即，xn ）。

示例 1：

输入：x = 2.00000, n = 10
输出：1024.00000

示例 2：

输入：x = 2.10000, n = 3
输出：9.26100

示例 3：

输入：x = 2.00000, n = -2
输出：0.25000
解释：2-2 = 1/22 = 1/4 = 0.25

提示：

  • -100.0 < x < 100.0
  • -2^31 <= n <= 2^31-1
  • n 是一个整数
  • 要么 x 不为零，要么 n > 0 。
  • -10^4 <= xn <= 10^4

快速幂板子题

想了解快速幂的直接看这个 快速幂 - OI Wiki

但是不要盲目抄板子，这道题的n是有负值的，快速幂板子一般n不考虑负值

class Solution {
    public double myPow(double x, int n) {
        long N = n;
        return n >= 0 ? quickMul(x, N) : 1 / quickMul(x, -N);
    }

    private double quickMul(double x, long n) {
        double res = 1.0;
        while (n > 0) {
            if ((n & 1) != 0) {
                res = res * x;
            }
            x = x * x;
            n >>= 1;
        }
        return res;
    }
}

lc70. 爬楼梯（EZ）

假设你正在爬楼梯。需要 n 阶你才能到达楼顶。

每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢？

示例 1：

输入：n = 2
输出：2
解释：有两种方法可以爬到楼顶。
1. 1 阶 + 1 阶
2. 2 阶

示例 2：

输入：n = 3
输出：3
解释：有三种方法可以爬到楼顶。
1. 1 阶 + 1 阶 + 1 阶
2. 1 阶 + 2 阶
3. 2 阶 + 1 阶

提示：

  • 1 <= n <= 45

很经典的dp题，也是最简单的dp题……

直接给题解

class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        } else if (n == 2) {
            return 2;
        }
        int a = 1, b = 2;
        for (int i = 3; i <= n; i++) {
            int tmp = b;
            b = b + a;
            a = tmp;
        }
        return b;
    }
}

lc198. 打家劫舍（MD）

你是一个专业的小偷，计划偷窃沿街的房屋。每间房内都藏有一定的现金，影响你偷窃的唯一制约因素就是相邻的房屋装有相互连通的防盗系统，如果两间相邻的房屋在同一晚上被小偷闯入，系统会自动报警。

给定一个代表每个房屋存放金额的非负整数数组，计算你 不触动警报装置的情况下 ，一夜之内能够偷窃到的最高金额。

示例 1：

输入：[1,2,3,1]
输出：4
解释：偷窃 1 号房屋 (金额 = 1) ，然后偷窃 3 号房屋 (金额 = 3)。
     偷窃到的最高金额 = 1 + 3 = 4 。

示例 2：

输入：[2,7,9,3,1]
输出：12
解释：偷窃 1 号房屋 (金额 = 2), 偷窃 3 号房屋 (金额 = 9)，接着偷窃 5 号房屋 (金额 = 1)。
     偷窃到的最高金额 = 2 + 9 + 1 = 12 。

提示：

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 400

在我看来，dp问题的关键在于怎么确定子问题和怎么确定子问题之间的“递推关系”（也就是状态转移方程），这两个虽然看着简单，但实际上一点也不简单

这道题的大问题是 “偷窃所有的房屋能够获得的最高金额”，那么根据大问题我们可以先定义一个子问题 “偷窃 k 间房屋之后，获得的最高金额”，将这个值记录在 dp[k] 中

根据题意要求——我们只能偷窃不相邻的房屋。那么对于 k，我们有两个选择——偷和不偷，对应的 dp[k] 就分别是 dp[k - 2] + nums[k - 1] 和 [dp - 1]

那么就能得到一个转移方程dp[k]=max(dp[k−2]+nums[k−1],dp[k−1])dp[k] = max(dp[k - 2] + nums[k - 1], dp[k - 1])

然后针对数组长度为0做特判即可

class Solution {
    public int rob(int[] nums) {
        int len = nums.length;
        if (len == 0) {
            return 0;
        }
        int a = 0, b = nums[0];
        for (int i = 2; i <= len; i++) {
            int tmp = b;
            b = Math.max(b, a + nums[i - 1]);
            a = tmp;
        }
        return b;
    }
}