【算法刷题】Day18

文章目录

1. x 的平方根
- 题干：
- 算法原理：
- 代码：
2. 搜索插入位置
- 题干：
- 算法原理：
- 代码：
3. 珠宝的最高价值
- 题干：
- 算法原理：
- - 1. 状态表示
  - 2. 状态转移方程
  - 3. 初始化
  - 4. 填表顺序
  - 5. 返回值
- 代码：

1. x 的平方根

在这里插入图片描述
原题链接

题干：

给一个 x 计算返回 x 的算数平方根
只保留整数
不能使用指数函数和算符

算法原理：

使用 二分查找

利用“二段性”
在这里插入图片描述

mid * mid <= x : left = mid
mid * mid > x : right = mid + 1

代码：

class Solution {
    public int mySqrt(int x) {
        //细节
        if(x < 1) {
            return 0;
        }
        long left = 1;
        long right = x;
        while(left < right) {
            long mid = left + (right - left + 1) / 2;
            if(mid*mid <= x) {
                left = mid;
            }else {
                right = mid - 1;
            }
        }
        return (int)left;
    }
}

在这里插入图片描述

2. 搜索插入位置

在这里插入图片描述
原题链接

题干：

有一个排序数组和一个目标值
找到目标值返回索引
不存在返回应该插入的位置

要求时间复杂度 O(log n)

算法原理：

使用 二分查找

在这里插入图片描述

x < t : left = mid + 1
x >= t : right = mid

代码：

class Solution {
    public int searchInsert(int[] nums, int target) {
        int left = 0;
        int right = nums.length - 1;
        while(left < right) {
            int mid = left + (right - left) / 2;
            if(nums[mid] < target) {
                left = mid + 1;
            }else {
                right = mid;
            }
        }
        //第三种情况
        if(nums[left] < target) {
            return left + 1;
        }
        return left;
    }
}

在这里插入图片描述

3. 珠宝的最高价值

在这里插入图片描述
原题链接

题干：

在这里插入图片描述
格子中的每个数都是珠宝的价值
求从 △ 到 ☆ 拿的最大价值
注意：只能向右和向下拿

算法原理：

使用 动态规划

1. 状态表示

dp[i][j] 表示：走到 [i, j] 位置处，此时的最大价值

2. 状态转移方程

在这里插入图片描述
对于 dp[i][j] ，我们发现想要到达 [i, j] 位置，有两种方式：

从 [i, j] 位置的上方 [i - 1, j] 位置，向下走⼀步，此时到达 [i, j] 位置能拿到的礼物价值为 dp[i - 1][j] + frame[i][j]
从 [i, j] 位置的左边 [i, j - 1] 位置，向右走⼀步，此时到达 [i, j] 位置能拿到的礼物价值为 dp[i][j - 1] + frame[i][j]

dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + frame[i][j]

3. 初始化

在这里插入图片描述
在表格上面和左边加一行和一列

保证后面的填表是正确的
下标的映射

在本题中，「添加⼀行」，并且「添加⼀列」后，所有的值都为 0 即可

4. 填表顺序

从上往下填写每一行
从左往右填写每一列

5. 返回值

dp[m][n]

代码：

class Solution {
    public int jewelleryValue(int[][] frame) {
        int m = frame.length;
        int n = frame[0].length;
        int[][] dp = new int[m + 1][n + 1];
        for(int i = 1; i <= m; i++) {
            for(int j = 1; j <= n; j++) {
                dp[i][j] = Math.max(dp[i][j - 1],dp[i-1][j]) + frame[i - 1][j -1];
            }
        }
        return dp[m][n];
    }
}