刷题知识回顾《八》完全平方数搜索二维矩阵

前言：由于在公司工作比较繁忙，导致之前刷的算法题忘记了许多，因此最近要大量回顾之前刷过的算法题，旨在有利于自己更好的复习，想跟着学习或复习的小伙伴儿们也可以参考一下🤞🤞
如果有什么需要改进的地方还请大佬斧正😁
小威在此先感谢诸佬了👏👏

🏠个人主页：小威要向诸佬学习呀
🧑个人简介：大家好，我是小威，一个想要与大家共同进步的男人😉😉
目前状况🎉：目前大二，在一家满意的公司实习👏👏

🎁如果大佬在准备面试，找工作，刷算法，可以使用我找实习前用的刷题神器哦刷题神器点这里哟
💕欢迎大家：这里是CSDN，我总结知识的地方，欢迎来到我的博客，我亲爱的大佬😘

牛客部分使用反馈，个人感觉还不错，帮我找到了心仪的公司，希望各位伙伴儿们通过它也能提高不少🥂🥂🥂

以下正文开始

完全平方数

题目:

给你一个整数 n ，返回 和为 n 的完全平方数的最少数量 。

完全平方数 是一个整数，其值等于另一个整数的平方；换句话说，其值等于一个整数自乘的积。例如，1、4、9 和 16 都是完全平方数，而 3 和 11 不是。

示例 1：

输入：n = 12
输出：3
解释：12 = 4 + 4 + 4

示例 2：

输入：n = 13
输出：2
解释：13 = 4 + 9

思路:由于题目要求完全平方数的最少数量,因此至少要将能取到的数全部遍历一遍。那么对于本题而言，返回完全平方数最多的数量是多少呢，无疑是全部由1相加组成，因此最多的数量为n。而在遍历的过程中，如何才能知道是取当前的数，还是取比当前更合适的呢？因此我们需要保存临时的结果，不断地更新结果值。所以我们应该用动态规划的方法来解决这道题。

代码详解：

class Solution {
    public int numSquares(int n) {
        int []dp = new int[n+1]; //定义新数组，数组中的值均默认为0。
        for(int i=1;i<=n;i++){
            dp[i]=i;  //这里表示最差的情况，最差的情况一共有i个。
            for(int j=1;i-j*j>=0;j++){
                dp[i]=Math.min(dp[i],dp[i-j*j]+1);
            }
        }
        return dp[n];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

搜索二维矩阵

编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target 。该矩阵具有以下特性：

每行的元素从左到右升序排列。
每列的元素从上到下升序排列。

示例1

输入：matrix = [[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]],target = 5
输出：true

示例2：

输入：matrix =[[1,4,7,11,15],[2,5,8,12,19],[3,6,9,16,22],[10,13,14,17,24],[18,21,23,26,30]],target = 20
输出：false

思路：此题可以采用暴力解法，进行两次循环找到对应的值，效率比较低一些，也可以使用二分查找来查找对应的值，下面两种代码都展示一下。

代码1+详解：

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        for(int [] row : matrix){ //暴力求解，两次循环
            for(int element:row){
                if(element==target){
                    return true;
                }
            }
        }
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12

代码2+详解：

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        for (int[] row : matrix) {
            int index = search(row, target);
            if (index >= 0) {
                return true;//如果返回的值为正数，即找到了索引，返回真
            }
        }
        return false;
    }
    //进行二分查找代码
    public int search(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            int num = nums[mid];
            if (num == target) {
                return mid;
            } else if (num > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27