前端算法

╰+哭是因爲堅強的太久メ 2023-06-17 10:57 9阅读 0赞

### 两数之和 ###

给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。

你可以假设每种输入只会对应一个答案。但是，你不能重复利用这个数组中同样的元素。

示例:

给定 nums = \[2, 7, 11, 15\], target = 9

因为 nums\[0\] + nums\[1\] = 2 + 7 = 9  
所以返回 \[0, 1\]  
**解法一**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMzMyMTg0_size_16_color_FFFFFF_t_70]  
**解答思路**

1.  第一遍过滤 nums 数组，标记为 i。
2.  第二遍再次过滤 nums 数组，标记为 i + 1，因为我们是对数组中的两个数字相加，所以不能重复使用同一个数字。
3.  判断第二次遍历的数字中，它是否等于 target - nums\[i\]，如果成立就返回两个数字的索引。（并不考虑后面还有可成立的答案）。

**解法二**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMzMyMTg0_size_16_color_FFFFFF_t_70 1]  
**解答思路**

1.  首先，我们需要了解 Map 这个对象。
2.  它可以通过 set() 的形式，以 \[key, value\] 的形式保存一组数据。（题目中对应 key 就是存入的 target -  
    nums\[i\] 值，value 就是索引） 它可以通过 get() 的形式，获取到传入 key 值对应的 value。 它可以通过  
    has() 的形式，判断 Map 对象里面是否存储了传入 key 对应的 value。 然后，我们遍历 nums 数组。
3.  最后，我们判断 nums\[i\] 是否存在于 Map 对象中。没有的话，就存入 target - nums\[i\] 到 Map  
    中。有的话，因为上次存入的是 target- nums\[i\]，有点类似于解题的钥匙，既然我们看到 nums\[i\] 存在于 Map中，它是解题的钥匙，所以我们只需要返回 \[map.get(nums\[i\]), i\] 这组值即可。

**解法三**

var twoSum = function (nums,target) { 
           for(let i =0;i<nums.length;i++){ 
               if(nums.indexOf(target-nums[i])!=-1 && nums.indexOf(target-nums[i])!=i){ 
                return [i,nums.indexOf(target-nums[i])]
            }
        }
    }

### 整数反转 ###

> 给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
> 
> 示例 1:
> 
> 输入: 123 输出: 321 示例 2:
> 
> 输入: -123 输出: -321 示例 3:
> 
> 输入: 120 输出: 21 注意:
> 
> 假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 \[−231, 231 −  
> 1\]。请根据这个假设，如果反转后整数溢出那么就返回 0。

**解法一**

**解答思路**

1.  首先，将传入的数字 x 转换成字符串，并分割成数组。
2.  然后，遍历该数组，将最后一个取出来放到 result 中。
3.  最后，判断这个 result 是否超过题目限制，如果超过则变成 0 。

**解法二**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMzMyMTg0_size_16_color_FFFFFF_t_70 2]

### 回文数 ###

判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。  
示例 1:  
输入: 121  
输出: true

示例 2:  
输入: -121  
输出: false  
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。

示例 3:  
输入: 10  
输出: false  
解释: 从右向左读, 为 01 。因此它不是一个回文数。

进阶:  
你能不将整数转为字符串来解决这个问题吗？  
**解法一**

**解答思路**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMzMyMTg0_size_16_color_FFFFFF_t_70 3]  
**解法二**

**解答思路**  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMzMyMTg0_size_16_color_FFFFFF_t_70 4]

1.  首先，我们可以想象：当一个数的长度为偶数，那么它对折过来应该是相等的；当一个数的长度是奇数，那么它对折过来后，有一个的长度需要去掉一位数（除以  
    10 并取整），因为奇数长度的那个数，我们不需要判断它中间的数字。
2.  我们定义传递过来的参数为：x，对折的数字为：z，而 y 为 x 目前的个位数。
3.  然后，我们需要知道如何获取到一个数的个位数：y = x % 10，我们也需要知道如何将单个数字不断添加到一个数的末尾：z = z \*  
    10 + y，例如：z = 1 \* 10 + 2 = 12。
4.  接着，我们只需要判断 x 是不是小于 z 了，毕竟当它小于的时候，说明数字已经对半或者过半了。
5.  最后，我们判断一开始的两种情况，并返回 true 或者 false 即可。

### 最长公共前缀 ###

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 “”。

示例 1:

输入: \[“flower”,“flow”,“flight”\]  
输出: “fl”  
示例 2:

输入: \[“dog”,“racecar”,“car”\]  
输出: “”  
解释: 输入不存在公共前缀。

说明:  
所有输入只包含小写字母 a-z 。

**解法一**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMzMyMTg0_size_16_color_FFFFFF_t_70 5]  
**解法二**

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMzMyMTg0_size_16_color_FFFFFF_t_70 6]

### 去重 ###

给定一个排序数组，你需要在原地删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在原地修改输入数组并在使用 O(1) 额外空间的条件下完成。

示例 1:

给定数组 nums = \[1,1,2\],  
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。  
你不需要考虑数组中超出新长度后面的元素。

示例 2:

给定 nums = \[0,0,1,1,1,2,2,3,3,4\],  
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。  
你不需要考虑数组中超出新长度后面的元素。

**解法一**

**解法二**

var removeDuplicates = function(nums) { 
        var a = [...new Set(nums)];
        for(var i = 0; i < a.length; i++) nums[i] = a[i];
        return a.length;
    }

### 有效的括号 ###

给定一个只包括 ‘(’，’)’，’\{’，’\}’，’\[’，’\]’ 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。  
左括号必须以正确的顺序闭合。  
注意空字符串可被认为是有效字符串。

示例 1:  
输入: “()”  
输出: true

示例 2:  
输入: “()\[\]\{\}”  
输出: true

示例 3:  
输入: “(\]”  
输出: false

示例 4:  
输入: “(\[)\]”  
输出: false

示例 5:  
输入: “\{\[\]\}”  
输出: true

### 最大子串 ###

给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。

示例:  
输入: \[-2,1,-3,4,-1,2,1,-5,4\],  
输出: 6  
解释: 连续子数组 \[4,-1,2,1\] 的和最大，为 6。

进阶:  
如果你已经实现复杂度为 O(n) 的解法，尝试使用更为精妙的分治法求解。  
**解法一**

var maxSubArray = function(nums) { 
        let max = nums[0];
        let val = 0;
        for(let i = 0; i < nums.length; i++){ 
            val+=nums[i];
            max = val > max ? val : max;
            val = 0 > val ? 0 : val;
        }
        return max;
    }

### 寻找比目标字母大的最小字母 ###

给定一个只包含小写字母的有序数组 letters，  
和一个目标字母 target，  
寻找有序数组里面比目标字母大的最小字母。

数组里字母的顺序是循环的。

举个例子，如果目标字母 target = ‘z’，  
并且有序数组为 letters = \[‘a’, ‘b’\]，  
则答案返回 ‘a’。

示例:

输入:  
letters = \[“c”, “f”, “j”\]  
target = “a”  
输出: “c”

输入:  
letters = \[“c”, “f”, “j”\]  
target = “c”  
输出: “f”

输入:  
letters = \[“c”, “f”, “j”\]  
target = “d”  
输出: “f”

输入:  
letters = \[“c”, “f”, “j”\]  
target = “g”  
输出: “j”

输入:  
letters = \[“c”, “f”, “j”\]  
target = “j”  
输出: “c”

输入:  
letters = \[“c”, “f”, “j”\]  
target = “k”  
输出: “c”

注:  
letters长度范围在\[2, 10000\]区间内。  
letters 仅由小写字母组成，最少包含两个不同的字母。  
目标字母target 是一个小写字母。

**解法一**

/** * @name 寻找比目标字母大的最小字母 * @param {character[]} letters * @param {character} target * @return {character} */
    const nextGreatestLetter = (letters, target) => { 
        // 处理数组中的情况
        for(let i = 0; i < letters.length; i++){ 
            if(letters[i] <= target && letters[i+1] > target){ 
                return letters[i+1];
            }
        }
        if(letters[0] > target){ 
            return letters[0];
        }
        if(letters[letters.length - 1] >= target){ 
            return letters[0];
        }
        if(letters.length > 1 && letters[0] == target){ 
            return letters[1];
        }
    }
    console.log(nextGreatestLetter(['c', 'f', 'j'], 'a')); // 'c'

**解法二**

**解法三**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMzMyMTg0_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20191128183530321.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMzMyMTg0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMzMyMTg0_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20191128184718471.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMzMyMTg0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMzMyMTg0_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20191129135827110.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMzMyMTg0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMzMyMTg0_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20191130183649657.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMzMyMTg0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMzMyMTg0_size_16_color_FFFFFF_t_70 4]: https://img-blog.csdnimg.cn/20191130185128197.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMzMyMTg0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMzMyMTg0_size_16_color_FFFFFF_t_70 5]: https://img-blog.csdnimg.cn/20191205112040962.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMzMyMTg0,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMzMyMTg0_size_16_color_FFFFFF_t_70 6]: https://img-blog.csdnimg.cn/20191205113126399.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzMzMzMyMTg0,size_16,color_FFFFFF,t_70