高频算法题冒险之旅精讲(一)之LeetCode小牛试刀五道题

这篇具有很好参考价值的文章主要介绍了高频算法题冒险之旅精讲(一)之LeetCode小牛试刀五道题。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

📢 导读:
本篇博文是LeetCode算法题讲解篇,对高频算法题进行详细而深入的讲解,解题语言选择的是Java。
更多算法专栏如下:
⛳️ 排序算法
⛳️ 分治法
⛳️ LeetCode高频算法题讲解
⛳️ 数据结构

前言:
本次算法冒险之旅将围绕LeetCode上面的算法面试题汇总进行讲解,该部分的题型在面试或笔试中出现的频率很高。
如下是本次冒险之旅的目录:
冒险算法,# LeetCode,LeetCode,高频算法题,动态规划,分治法,摩尔投票
本篇文章讲解冒险之旅开始前的五道题,让大家感受一下算法的魅力,之后笔者会逐一进行讲解如下的每一章节,每一个大标题都会写一篇文章,算是对其进行剖析和详细汇总。

在进入正题之前,不妨先让我们回顾几个有意思的经典互联网公司的面试题目,热热身。



⛳️ 1.只出现一次的数字(第136题)

1.1题目:

冒险算法,# LeetCode,LeetCode,高频算法题,动态规划,分治法,摩尔投票

1.2解题思路及完整Java代码

根据题目所给出的信息,我想到的map或者set去解决,因为题目中很明确说明了有且只有一个元素会出现一次,其他的都是两次。

  1. 用map,我们可以在第一次的时候把元素的值作为key,下标为value存进map中,然后在进行判断下一个元素是否在map中,用key去判断,containsKey方法的时间复杂度很低,原因是key被存储到hash表中,查找时是在hash表上进行查找,其时间复杂度为:最好情况便是O(1),最坏情况是O(lgn)。如果存在就从map中移除,因为重复的话只会出现两次,题目中已经明确说明了,那么最后map中所剩的最后一个元素就是唯一出现一次的元素。
  2. 不重复的话,我们也会考虑到用set去解决,这个我们也很容易想到,只要是添加失败的情况,就证明之前已经向set集合中添加过该元素了,我们把之前的也删掉即可,最后剩下的哪一个也是唯一出现一次的元素。
  3. 用位运算中的异或,如果a、b两个值不相同,则异或结果为1。如果a、b两个值相同,异或结果为0,把所有的数字都进行异或操作就能得到结果了。
1.2.1用map

用map,我们可以在第一次的时候把元素的值作为key,下标为value存进map中,然后在进行判断下一个元素是否在map中,用key去判断,containsKey方法的时间复杂度很低,原因是key被存储到hash表中,查找时是在hash表上进行查找,其时间复杂度为:最好情况便是O(1),最坏情况是O(lgn)。如果存在就从map中移除,因为重复的话只会出现两次,题目中已经明确说明了,那么最后map中所剩的最后一个元素就是唯一出现一次的元素。
代码:

public class SingleNumber01 {
    public int singleNumber(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for(int i =0;i<nums.length;i++){
            if(map.containsKey(nums[i])){
                map.remove(nums[i]);
            }else {
                map.put(nums[i],i);
            }
        }
        Object[] arr = map.keySet().toArray();
        return (int) arr[0];
    }

    public static void main(String[] args) {
        System.out.println(new SingleNumber01().singleNumber(new int[]{4, 1, 2, 1, 2}));
    }
}

这种花费的时间太长了:
冒险算法,# LeetCode,LeetCode,高频算法题,动态规划,分治法,摩尔投票
下面我们用set。

1.2.2用set

不重复的话,我们也会考虑到用set去解决,这个我们也很容易想到,只要是添加失败的情况,就证明之前已经向set集合中添加过该元素了,我们把之前的也删掉即可,最后剩下的哪一个也是唯一出现一次的元素。

代码:

public class SingleNumber02 {
    public int singleNumber(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int num : nums) {
            if(!set.add(num))
                set.remove(num);
        }
        Object[] arr = set.toArray();
        return (int) arr[0];
    }

    public static void main(String[] args) {
        System.out.println(new SingleNumber02().singleNumber(new int[]{4, 1, 2, 1, 2}));
    }
}

执行时间:
冒险算法,# LeetCode,LeetCode,高频算法题,动态规划,分治法,摩尔投票
可以看到相比于第一个用map只提高了1ms,那么我们是否有更快的方法呢,此时我们i想到了用位运算。

1.2.3用位运算

用位运算中的异或,如果a、b两个值不相同,则异或结果为1。如果a、b两个值相同,异或结果为0(按位bit进行异或运算),把所有的数字都进行异或操作就能得到结果了。
代码:

public class SingleNumber03 {
    public int singleNumber(int[] nums) {
        int result = nums[0];
        for (int i =1;i<nums.length;i++){
            result=result ^ nums[i];
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(new SingleNumber03().singleNumber(new int[]{4, 1, 2, 1, 2}));
    }
}

执行时间:
冒险算法,# LeetCode,LeetCode,高频算法题,动态规划,分治法,摩尔投票
可以看到只需要1ms就执行完了,相比与前两种方法,这种方法有质的提升。



⛳️ 2.多数元素(第169题)

2.1题目:

冒险算法,# LeetCode,LeetCode,高频算法题,动态规划,分治法,摩尔投票

2.2解题思路及完整Java代码

2.2.1使用map去存储元素出现的次数
  • 题目中已经说明了我们可以假设数组是非空的,并且数组中总是存在多数元素,所以数组为空或者不存在多数元素的情况我们不考虑。
  • 题目中对于多数元素的定义为出现次数大于n/2的元素,在元素为n的数组中,大于n/2的情况肯定只有一个数,所以我们可以断定多数元素只有一个。
  • 分析到这里我们就很容易想到利用map中的key去存储元素的值,利用value进行存储元素出现的次数。
  • 由于只存在一个大于n/2的数,所以我们可以在循环的过程中对map的value进行判断,如果存在大于n/2的数字那么我们把它返回即可。

代码:

public class MostElements {
    public int majorityElement(int[] nums) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            int count = map.containsKey(num) ? map.get(num) : 0;
            map.put(num,++count);
            if(count>nums.length/2){
                return num;
            }
        }
        throw new RuntimeException("传入数组不符合要求!");
    }

    public static void main(String[] args) {
        System.out.println(new MostElements().majorityElement(new int[]{2,2,1,1,1,2,2}));
    }
}

执行时间:
冒险算法,# LeetCode,LeetCode,高频算法题,动态规划,分治法,摩尔投票
可以看到时间还是挺长的,下面我们用另外一种方法。

2.2.2排序后直接输出

我们要善于根据题意解答问题,根据题意,多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素,出现次数大于n/2,不论这个数字是最大还是最小,经过排序后,数组中间的那个元素一定是多数元素。

代码:

public class MostElements01 {
    public int majorityElement(int []nums){
        Arrays.parallelSort(nums);
        return nums[nums.length/2];
    }

    public static void main(String[] args) {
        System.out.println(new MostElements01().majorityElement(new int[]{2,2,1,1,1,2,2}));
    }
}

执行时间:
冒险算法,# LeetCode,LeetCode,高频算法题,动态规划,分治法,摩尔投票
可以看到相较于之前用map进行统计,该方法所需的时间又得到了提升。那么还有其他方法使之得到进一步的提升嘛,答案是有的,我们接着看。

2.2.3摩尔投票法

理解:随机选取两个不同的数进行相消,最坏情况是,所有非多数元素于多数元素相消,因为多数元素是大于n/2的数,所以最后留下的绝对也是多数元素。

  1. 题目中已经说到了,数组中存在大于n/2的数;
  2. 定义count=0,我们可以采取刚开始选择数组中的第一个元素,count赋值等于1,然后判断数组中接下来的数是否与其相同,相同count加1,不同count减1;
  3. 当count等于0时,我们就选择数组中的下一个数,count赋值等于1,重复2的操作。
  4. 数组遍历一遍后,最后剩下的数就是多数元素了。

Java代码:

public class MostElements02 {
    public int majorityElement(int[] nums) {
        int major = nums[0];
        for (int i = 1, count = 1; i < nums.length; i++) {
            if (count == 0) {
                major = nums[i];
                count++;
            } else if (nums[i] == major)
                count++;
            else
                count--;
        }
        return major;
    }

    public static void main(String[] args) {
        System.out.println(new MostElements02().majorityElement(new int[]{2, 2, 1, 1, 1, 2, 2}));
    }
}

执行时间:
冒险算法,# LeetCode,LeetCode,高频算法题,动态规划,分治法,摩尔投票
可以看到只需要1ms就执行完了,相比与前两种方法,这种方法也有质的提升,且时间复杂度是O(n)。



⛳️ 3.搜索二维矩阵 II(第240题)

3.1题目:

冒险算法,# LeetCode,LeetCode,高频算法题,动态规划,分治法,摩尔投票

3.2解题思路及完整Java代码

3.2.1暴力解法

Java代码:

public boolean searchMatrix(int[][] matrix, int target) {
        for (int i = 0; i < matrix.length; i++) {
            for (int j = 0; j < matrix[0].length; j++) {
                if (matrix[i][j] == target)
                    return true;
            }
        }
        return false;
    }

解题时间:
冒险算法,# LeetCode,LeetCode,高频算法题,动态规划,分治法,摩尔投票

3.2.2一般解题思路

因矩阵有如下特征:

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

固很容易会想到如下解题思路;
可以看到矩阵每行的元素从左到右升序排列,

  1. 我们可以首先取矩阵中的第一行第一列的元素进行判断,如果矩阵当前元素比目标值小,就继续读取矩阵该行的下一个元素,然后继续和目标值作比较。如果读取到该行末尾,就读取下一行的第一个元素,直到出现2中的情况。
  2. 矩阵从按行读取变成按列读取:
    当矩阵当前元素大于目标元素,我们就读取矩阵当前元素所在行的前一列元素,我们称之为X,读取X列的下一个元素,然后与目标值做比较,如果小于目标元素,就继续按照列读取,直到找到相等的,如果没有相等的,就把列再向前移动一位,如此循环,直到找到相等的值,当列的值等于0时,证明矩阵中不存在该元素。

Java代码:

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
       // 第一行先从左到右进行比较
        for (int i = 0; i < matrix.length; i++) {
            // 然后从上到下
            for (int j = 0; j < matrix[i].length; j++) {
                if (target == matrix[i][j])
                    return true;
                if (target < matrix[i][j]) {
                    // 否则列减一,然后固定减一后的列,行累加进行查找,如果找到该列的行尾或者有笔目标值大的元素,就把列再向前移动一位
                    //当列的值等于0时,证明矩阵中不存在该元素
                    j--;
                    for(;j>=0;j--){
                       for (int k = i;++k < matrix.length && matrix[k][j] <= target;) {
                            if (matrix[k][j] == target)
                                return true;
                        }
                    }
                    return false;
                }
            }
        }
        return false;
    }
}

解题时间:

冒险算法,# LeetCode,LeetCode,高频算法题,动态规划,分治法,摩尔投票

3.2.3看成一棵排序二叉树
  1. 从矩阵的左下角开始比较(该二维数组类似于一棵排序二叉树,对于每个数来说,上方的数都小于它,右方的数都大于它,所以把左下角作为根节点开始比较)。
  2. 也可以从矩阵的右上角开始比较,把矩阵的右上角的元素作为二叉树的根节点。

如下以矩阵右上角为排序二叉树的根节点来举例:
Java代码:

class Solution {
        public boolean searchMatrix(int[][] matrix, int target) {
        //从矩阵右上角开始搜索
        int col = matrix[0].length - 1;
        int row = 0;
        while (col >= 0 && row <= matrix.length - 1) {
            if (target == matrix[row][col]) {
                //如果找到就直接返回
                return true;
            } else if (target < matrix[row][col]) {
                //如果查找的值大了,下一步往左找
                col--;
            } else if (target > matrix[row][col]) {
                //如果查找的值小了,下一步往下找
                row++;
            }
        }
        return false;
    }
}

解题时间:
冒险算法,# LeetCode,LeetCode,高频算法题,动态规划,分治法,摩尔投票



⛳️ 4.合并两个有序数组(第88题)

4.1题目:

冒险算法,# LeetCode,LeetCode,高频算法题,动态规划,分治法,摩尔投票

4.2解题思路及完整Java代码

4.2.1 归并排序思想,一个新数组,两个指针,简单明了

Java代码:

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        // 题目中已说,nums1 的初始长度为 m + n,其中前 m 个元素表示应合并的元素,后 n 个元素为 0 ,应忽略。nums2 的长度为 n 。
        // 所以nums1足够长了
        int [] arr = nums1.clone();
        int index1 = 0, index2 = 0;
        while (index1 + index2 < m + n) {
            if(index1>=m){
                nums1[index1+index2] = nums2[index2];
                index2++;
            }else if(index2>=n){
                nums1[index1+index2] = arr[index1];
                index1++;
            }else if (arr[index1] <= nums2[index2]) {
                nums1[index1+index2] = arr[index1];
                index1++;
            }else {
                nums1[index1+index2] = nums2[index2];
                index2++;
            }
        }
    }
}

执行时间:
冒险算法,# LeetCode,LeetCode,高频算法题,动态规划,分治法,摩尔投票
第一次就0s,就很行,哈哈哈,虽然世界效率达到了,O(m+n),但是我们还是要说一下归并排序的思路。

具体的归并排序思想可以参考笔者该篇博文:归并排序 (分而治之算法) java代码实现(java完整代码)java递归实现(分而治之)MergeSort(分治法)



⛳️ 5.鸡蛋掉落(第887题)

5.1题目

冒险算法,# LeetCode,LeetCode,高频算法题,动态规划,分治法,摩尔投票

5.2解题思路及完整Java代码

这道题有点难,我们慢慢分析,
先看一个鸡蛋的时候:

  • 如果你手上只有一个鸡蛋,只能从一楼开始,逐层往上试,
  • 比如总共10层楼。1楼试了没碎,试2楼,直到第5层碎了,那 F=5。如果第10层还没碎,那 F=10。
  • 如果非要从第7层开始试,扔下去碎了,这时只能知道 F<= 6,具体是几,因为没鸡蛋,没法试了。
  • 所有一个鸡蛋的情况下,要确认F是第几层,10次一定可以试出来。即一个鸡蛋的情况下,最小次数=楼层数。
  • 也就是说要考虑最坏情况
5.2.1动态规划(二维背包)

Java代码:

class Solution {
    /**
        01背包问题
     */
    public int superEggDrop(int k, int n) {
        if(n==1){
            return 1;
        }
        //背包:鸡蛋数(k个); 物品:操作数(n个);价值:确定楼层
        int[][] dp = new int[k+1][n+1];

        // 有人问了,为什么不是鸡蛋作为物品,操作数作为背包?
        // 背包问题往往物品与价值有正相关关系。
        // 鸡蛋有k个,但实际不一定全都用上,限制一定的最小操作数,鸡蛋增加,确定楼层(价值)不一定增加
        // 而取一定的鸡蛋,操作数每增加1,确定楼层(价值)就会一定增加
        int count=0;

        // 先遍历物品,再遍历背包
        for(;dp[k][count]<n;){ // 遍历物品,这里直到价值为n就结束
             count++;
            for (int i = k; i >=1; i--) { // 遍历背包,二维数组可以正序或倒叙
                //当前价值 = 鸡蛋碎了的价值 + 鸡蛋没碎的价值 + 确定当前层的价值1
                dp[i][count] = dp[i-1][count-1]+dp[i][count-1]+1;
            }
        }

        return count;
    }
}

执行时间:
冒险算法,# LeetCode,LeetCode,高频算法题,动态规划,分治法,摩尔投票文章来源地址https://www.toymoban.com/news/detail-788280.html

到了这里,关于高频算法题冒险之旅精讲(一)之LeetCode小牛试刀五道题的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 【LeetCode】347.前K个高频元素

    给你一个整数数组  nums  和一个整数  k  ,请你返回其中出现频率前  k  高的元素。你可以按  任意顺序  返回答案。 示例 1: 示例 2: 提示: 1 = nums.length = 10^5 k  的取值范围是  [1, 数组中不相同的元素的个数] 题目数据保证答案唯一,换句话说,数组中前  k  个高频元素

    2024年02月10日
    浏览(30)
  • LeetCode-高频 SQL 50 题:连接 篇

    目录 1378. 使用唯一标识码替换员工ID 题目描述: SQL语句: 1068. 产品销售分析 I 题目描述: SQL语句: 1581. 进店却未进行过交易的顾客 题目描述: SQL语句: 197. 上升的温度 题目描述: SQL语句: 1661. 每台机器的进程平均运行时间 题目描述: SQL语句: 577. 员工奖金 题目描述:

    2024年02月07日
    浏览(32)
  • 【LeetCode】692. 前K个高频单词

    给定一个单词列表 words 和一个整数 k ,返回前 k 个出现次数最多的单词。 返回的答案应该按单词出现频率由高到低排序。如果不同的单词有相同出现频率, 按 字典顺序 排序 示例1 输入 : words = [“i”, “love”, “leetcode”, “i”, “love”, “coding”], k = 2 输出 : [“i”, “lo

    2024年02月04日
    浏览(32)
  • 【LeetCode高频100题-3】冲冲冲(持续更新23.2.1)

    一道数学题,排列组合/小学奥赛题。 动态规划不是一般来解决最值问题的吗,这道题为什么会想到dp? 从左上角到右下角,一共要走m+n-2步,其中向右n-1步,向下m-1步,因此路径的总数,相当于从m+n-2中选择m-1个向下的步数,即排列组合。 但是,需要注意的是,题目只保证最

    2023年04月19日
    浏览(34)
  • 聚类算法:Kmeans和Kmeans++算法精讲

    其实Kmeans聚类算法在YOLOv2(【YOLO系列】YOLOv2论文超详细解读(翻译 +学习笔记))中我们就见到了,那时候只是简单地了解了一下。后来在这学期的数据挖掘课程的期末汇报中,我又抽中了这个算法,于是又重新学习了一遍。另外最近在看一些改进的论文,很多摘要中也都

    2024年02月05日
    浏览(43)
  • 汉诺塔递归算法精讲

    递归算法是计算机算法中的基础算法,也是非常重要的算法,从某种程度上讲,它有一点儿AI的影子。人脑是可以完成递归思路的,但是对不起,残酷的现实是,一般人脑在精力集中的情况下,能递归个三五层就就基本晕菜了。反正我是这样,你或者您可能深度多一些。当然

    2024年02月03日
    浏览(49)
  • 【面试高频算法解析】算法练习3 双指针

    本专栏旨在通过分类学习算法,使您能够牢固掌握不同算法的理论要点。通过策略性地练习精选的经典题目,帮助您深度理解每种算法,避免出现刷了很多算法题,还是一知半解的状态 二分查找 回溯(Backtracking) 双指针 滑动窗口 深度优先搜索 广度优先搜索 贪心算法 单调

    2024年01月23日
    浏览(46)
  • MATLAB算法实战应用案例精讲-【智能优化算法】多目标算法性能评价指标

    在评估多目标优化算法的效果时,我们通常使用五个主要指标:GD(Generational Distance)、IGD(Inverted Generational Distance)、Hypervolume、Spacing和Spread。 GD 和 IGD 是用于测量算法生成的解集合与真实前沿解之间的距离的指标。具体而言,GD测量了所有生成解与真实前沿解之间的平均欧

    2024年02月15日
    浏览(58)
  • 字符串相关高频面试题算法

    一、字符串 java:String内置类型,不可更改。(如需更改可考虑:StringBuffer, StringBuilder,char[]等) 二、归类 字符串涉及到的相关题型通常会是以下几个方面: 概念理解:字典序 简单操作:插入删除字符、旋转 规则判断(罗马数字转换 是否是合法的整数、浮点数) 数字运算(

    2024年02月09日
    浏览(74)
  • 【蓝桥杯】高频算法考点及真题详解小结

    🙊🙊 作者主页 :🔗求不脱发的博客 📔📔 精选专栏 :🔗数据结构与算法 📋📋 精彩摘要 : 考前看一看,AC手拿软。蓝桥杯高频算法考点小结,包括各大算法、排序算法及图的优先遍历原则知识点小结。预祝大家取得优异成绩。 💞💞 觉得文章还不错的话欢迎大家点赞

    2023年04月11日
    浏览(38)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包