智能算法 | 刷题的方法真的找到正确思路了嘛

亦凉 2024-04-22 22:08 5阅读 0赞

## 前言 ##

![在这里插入图片描述][0422b4369a3549b3a39da19588ab88f4.png]  
「作者主页」：[雪碧有白泡泡][Link 1]  
「个人网站」：[雪碧的个人网站][Link 2]  
![请添加图片描述][ff5fcbac70f843ebb3ef9cf9ebf68fef.gif]

大家在学习编程、算法，刷题的时候，真正的苦恼在于没有一套行之有效的刷题顺序。

![请添加图片描述][c7f3e6b8a7624a9eabbea77dbcbca119.jpeg]

#### 文章目录 ####

*  前言
 *  引言
 *  华为2023最新面试题
 *   *  对称二叉树
     *  两个数组的交集
 *  数据结构小结
 *  推荐书籍

## 引言 ##

从何学起，先学什么，再学什么。力扣（Leetcode）上两千道题目，怎么刷，很多人刷题的效率低，主要体现在如下三点：

*  找题
 *  找到了不合适现阶段做的题
 *  没有全套的优质题解可以参考  
    **而市面上基本找不到真正能解决以上痛点的算法书籍。**

> 一些书籍是每个知识点蜻蜓点水，然后就叫大家举一反三。
> 
> 一些书籍是一堆题解堆在一起，让大家学起来感受不到知识的连贯性和系统性。

**断片式的学习，效率怎么能高呢？**

在学习算法的时候，就深感其中的艰难，当的题量达到一定数量时候，随着反复的琢磨和深入的思考，我再去回顾这些算法题目，发现如果要是按照合理的顺序来刷题，那效果一定是 事半功倍！

每一个专题中的题目按照由易到难的顺序进行编排，每一道题目所涉及的知识，前面都会有相应的题目做知识铺垫，做到环环相扣。

建议大家按照章节顺序阅读本书，在阅读的过程中会发现在题目编排上的良苦用心！  
![在这里插入图片描述][a3bf294ee712452bbc426e5cadaee033.png]

本书不仅在题目编排上精心设计，而且在针对读者最头痛的算法问题上做了详细且深入的讲解。

> 关于动态规划，都知道递推公式的重要性，但dp数组的含义、dp数组的初始化、遍历顺序以及如何打印dp数组来排查Bug，这些都很重要。例如，解决背包问题的时候，遍历顺序才是最关键的，也是最难理解的。
> 
> 关于回溯算法，题目要求集合之间不可重复，那么就需要去重，各种资料都说要去重，但没有说清楚是“树层去重”还是“树枝去重”——这是我为了说明去重的过程而创造的两个词汇。
> 
> 关于KMP算法，都知道使用前缀表进行回退，可什么是前缀表，为什么一定要用前缀表，根据前缀表回退有几种方式，这些却没有说清楚，导致最后大家看的一头雾水。
> 
> 关于二叉树，不同的遍历顺序其递归函数究竟如何安排，递归函数什么时候需要返回值，什么时候不用返回值，什么情况下分别使用前、中、后序遍历，迭代法又要如何实现，这些都决定了对二叉树的理解是否到位。

![在这里插入图片描述][2abced8b9f9b48a4bdb2336f058cec51.png]

## 华为2023最新面试题 ##

> 以下题为最新的leetcode会员付费华为面试题

![在这里插入图片描述][26bf9c13015e4f07b9c0d893f185b118.png]  
让我们一起开始吧！

由于篇幅限制，我们将题目使用引用的方式大家可以直接跳转去先尝试一下，并只介绍其开头部分简单题，获取完整题目可以点击文章底部微信进行私聊

### 对称二叉树 ###

题目地址：[点击这里跳转即可][Link 3]

1.  数据结构：**二叉树**

二叉树常用于搜索，父节点有两个左右节点，有可能会退化为链表

1.  动图帮助理解  
    ![请添加图片描述][ef9353fd1bb14cf1bb27d8b067831981.gif]
2.  规律

> 左子树的左孩子 == 右子树 的右孩子  
> 左子树的右孩子 == 右子树 的左孩子

1.  终止条件

//递归的终止条件是两个节点都为空
    		//或者两个节点中有一个为空
    		//或者两个节点的值不相等
    		if(left==null && right==null) {
        
    			return true;
    		}
    		if(left==null || right==null) {
        
    			return false;
    		}
    		if(left.val!=right.val) {
        
    			return false;
    		}

### 两个数组的交集 ###

题目地址：[点击这里跳转即可][Link 4]

1.  数据结构 ： 数组  
    一组连续的内存空间存储一组具有相同类型的数据的集合，需要额外注意的是扩容操作，刚开始默认容量为10，然后1.5倍进行扩容，最后copyof复制进去
2.  暴力思路  
    双重循环去比较，注意唯一，把重复的去掉统统暴力
3.  我的错误思路  
    我用的ArrayList和HashMap，他一直不能保证唯一  
    下面第一个代码是错的

import java.util.ArrayList;
    import java.util.HashMap;
    import java.util.List;
    import java.util.Map;
    
    class Solution {
        
        public int[] intersection(int[] nums1, int[] nums2) {
        
            Map<Integer, Integer> numFreqMap = new HashMap<>();
            List<Integer> intersection = new ArrayList<>();
    
            // 统计 nums1 中每个数字的出现频率
            for (int num : nums1) {
        
                numFreqMap.put(num, numFreqMap.getOrDefault(num, 0) + 1);
            }
    
            // 遍历 nums2，寻找和 nums1 重复的数字
            for (int num : nums2) {
        
                if (numFreqMap.containsKey(num) && numFreqMap.get(num) > 0) {
        
                    intersection.add(num);
                    numFreqMap.put(num, numFreqMap.get(num) - 1);
                }
            }
    
            // 将结果转换为数组
            int[] result = new int[intersection.size()];
            for (int i = 0; i < intersection.size(); i++) {
        
                result[i] = intersection.get(i);
            }
    
            return result;
        }
    }

应该用set

import java.util.ArrayList;
    import java.util.HashSet;
    import java.util.List;
    import java.util.Set;
    
    class Solution {
        
        public int[] intersection(int[] nums1, int[] nums2) {
        
            Set<Integer> set1 = new HashSet<>();
            Set<Integer> set2 = new HashSet<>();
            List<Integer> intersection = new ArrayList<>();
    
            // 将 nums1 中的元素添加到 set1
            for (int num : nums1) {
        
                set1.add(num);
            }
    
            // 在 set1 中查找和 nums2 重复的元素
            for (int num : nums2) {
        
                if (set1.contains(num) && !set2.contains(num)) {
        
                    intersection.add(num);
                    set2.add(num);
                }
            }
    
            // 将结果转换为数组
            int[] result = new int[intersection.size()];
            for (int i = 0; i < intersection.size(); i++) {
        
                result[i] = intersection.get(i);
            }
    
            return result;
        }
    }

总之就是数据结构犯了错误  
使用`Set`和`Map`都可以找到两个数组的交集，但是它们有不同的适用情况和功能。

> `Set`是一种集合数据结构，它存储唯一元素并提供高效的成员查询。在找到数组交集的情况下，我们可以利用`Set`的唯一性来避免重复元素的出现。首先，我们可以将一个数组中的元素添加到一个`Set`中。然后，遍历第二个数组，判断元素是否在`Set`中存在，如果存在，则这个元素是交集的一部分。`Set`的实现在内部使用哈希表，这样可以快速进行元素查找和插入操作，因此执行效率较高。

> `Map`是一种键值对数据结构，它可以通过键快速查找对应的值。在交集问题中，我们可以将数组中的元素作为键，并将出现的次数作为值存储在`Map`中。遍历第二个数组时，可以在`Map`中查找对应键，如果存在且值大于0，则将该键添加到交集中，并将值减1。这样可以实现统计交集元素及其重复次数的功能。然而，如果我们只关注元素的唯一性而不考虑重复次数，使用`Map`相对于`Set`来说增加了一些额外的复杂性，因为我们需要处理值的递减操作。

## 数据结构小结 ##

我觉得在研究算法之前首先是要拿下数据结构，可以让我们更好的理解题意，在文章的最后带大家梳理一下数据结构的基础内容  
![在这里插入图片描述][c26643f6ff1147dfab2ad42b6c6d341f.png]

> 我们以数组作为底层，它包括了优先队列，双端队列（堆栈），还有不完美哈希，那么先说不完美哈希，在解决哈希冲突的时候，我们使用了开放寻址法，分离法，这些底层都是数组加链表结构，然后双端队列，就是线性结构堆栈，最后说一下优先队列，优先队列是线性数据结构中队列的一种实现队列还有一种实现是延迟队列，它的底层是链表，链表也是一种线性数据结构，底层为双向链表。而优先队列又是树形结构，堆。树形数据结构除了堆之外还有数组作为底层的字典树。还有二叉树，而二叉树为了自平衡出现了AVL自平衡二叉树，还有2-3树和对应的红黑树，这几个树的底层都是指针，同样作为数组为底层的还有并查集和邻接矩阵，这个并查集属于树形数据结构，而邻接矩阵是属于图的一类，图还包括了邻接表，他的数据结构为链表和红黑树，除此之外还有一种数据结构叫做布隆过滤器，他的底层实现为位数组和哈希函数。

## 推荐书籍 ##

>  *  🎁本次送书1~3本【取决于阅读量，阅读量越多，送的越多】👈
>  *  ⌛️活动时间：截止到2023-12月11号
>  *  ✳️参与方式：关注博主+三连（点赞、收藏、评论）  
>     购买链接 ：[https://item.jd.com/13528516.html][https_item.jd.com_13528516.html]![在这里插入图片描述][fa0ecf320f2648df8266383d3a07ca64.png]

[0422b4369a3549b3a39da19588ab88f4.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/ee95a0e7d47b4a63aa890775085ac824.png
[Link 1]: https://blog.csdn.net/Why_does_it_work?spm=1011.2415.3001.5343
[Link 2]: http://47.94.110.103:3000/
[ff5fcbac70f843ebb3ef9cf9ebf68fef.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/75b612e2805349bb86d795bececfb830.gif
[c7f3e6b8a7624a9eabbea77dbcbca119.jpeg]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/963f3c158d3c4fe7b002bc7cd492d7c3.jpeg
[a3bf294ee712452bbc426e5cadaee033.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/169af45cb31d4446908f07f3be1cf4ec.png
[2abced8b9f9b48a4bdb2336f058cec51.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/c9ed200504c74d2196aadb2bfe761d77.png
[26bf9c13015e4f07b9c0d893f185b118.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/1a3716cd9660483f88175ec73081938f.png
[Link 3]: https://leetcode.cn/problems/symmetric-tree/description/?envType=study-plan-v2&envId=huawei-2023-spring-sprint
[ef9353fd1bb14cf1bb27d8b067831981.gif]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/a4a2cce8f3434487b7db7cb01b96caca.gif
[Link 4]: https://leetcode.cn/problems/intersection-of-two-arrays/description/?envType=study-plan-v2&envId=huawei-2023-spring-sprint
[c26643f6ff1147dfab2ad42b6c6d341f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/b05ebb0f5eb54a11bc2839af09e85723.png
[https_item.jd.com_13528516.html]: https://item.jd.com/13528516.html
[fa0ecf320f2648df8266383d3a07ca64.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/22/1fbe1a5c53ce44bda3c2114388086547.png