leecode算法解析和笔记(1)

古城微笑少年丶 2024-03-30 06:32 35阅读 0赞

## leecode算法解析和笔记 ##

## 2022/12/09 ##

[文章][Link 1]

### 1.Two Sum 两数之和解法 ###

#### 问题： ####

> 给定一个整数数组 nums 和一个整数目标，返回两个数字的索引，使它们加起来等于目标。
> 
> 您可能会假设每个输入都只有一个解决方案，并且您可能不会两次使用相同的元素。
> 
> 您可以按任何顺序返回答案。
> 
> Input: nums = \[3,2,4\], target = 6 Output: \[1,2\]

#### 解决问题思路： ####

> 1.  创建一个新的map表
> 2.  在数组中遍历，用目标值-数组中遍历的元素=差值
> 3.  如果在map中，差值在map中，将差值和值的下标存入到map中。注意是值为key，下标为value。之后输出的下标的值
> 4.  如果不存在，插值不存在就插入到map中，将数组的值和下标存入。注意：map(数组\[元素小标\]，元素下标)
> 5.  在for循环遍历数组元素之后，找不到两个组成目标整数的元素，数组返回空值

### 2.Palindrome Number 回文数 ###

#### 问题： ####

> 给定一个整数 x，如果 x 是回文整数，则返回 true。
> 
> 当一个整数向后读和向前读一样时，它就是一个回文数。
> 
> 例如，121 是回文，而 123 不是。

#### 解决问题思路： ####

> 1.  条件进行判断，如果输入的int整数<0,返回false；
> 2.  如果不是，将整数转换成字符串类型，并计算长度。
> 3.  用for循环遍历，从两端向中间逼近，
> 4.  如果最左端不等于最右端的字符串的值，返回false
> 5.  否则说明是回文数，返回true

### 3.Roman to Integer 罗马字转整数 ###

#### 问题： ####

> 用罗马数字输出整数
> 
>     SymbolValue
>     I             1
>     V             5
>     X             10
>     L             50
>     C             100
>     D             500
>     M             1000
>     
>     I can be placed before V (5) and X (10) to make 4 and 9.
>     X can be placed before L (50) and C (100) to make 40 and 90.
>     C can be placed before D (500) and M (1000) to make 400 and 900.
>     
>     Input: s = "III"
>     Output: 3
>     Explanation: III = 3.
>     
>     Input: s = "LVIII"
>     Output: 58
>     Explanation: L = 50, V= 5, III = 3.
>     
>     Input: s = "MCMXCIV"
>     Output: 1994
>     Explanation: M = 1000, CM = 900, XC = 90 and IV = 4.

#### 解决问题思路： ####

> 1.  新建一个hashmap，存储罗马数字对应的整数
> 2.  初始化 int结果为0；
> 3.  从左到右遍历罗马数字
> 4.  取出当前罗马数字并定义一个int变量
> 5.  如果当前的值比右边的值小，则加入到结果中，结果=结果-int变量
> 6.  否则当前的值比右边的值大，结果=结果+int变量
> 7.  循环遍历结果后的结果返回

### 4.Longest Common Prefix最长公共前缀 ###

#### 问题： ####

> 编写一个函数来查找字符串数组中最长的公共前缀字符串。  
> 如果没有公共前缀，则返回一个空字符串“”。
> 
> Input: strs = \[“flower”,“flow”,“flight”\]  
> Output: “fl”
> 
> Input: strs = \[“flower”,“flow”,“flight”\]  
> Output: “fl”

#### 解决问题思路： ####

> 1.  String的数组中，如果为空或长度为0，返回”“空值
> 2.  如果有值
> 3.  初始化第一个数组下标为0的字符串，定义变量为prefix
> 4.  for循环遍历，从第二个字符串开始，逐个和最长公共前缀比较
>     
>     1.  当最长公共前缀不是当前字符串前缀，不断缩小最长公共前缀的长度，直到它成为当前字符串的前缀
>         
>         1.  公共前缀的的值不能为0，进行循环
>         2.  让最长公共前缀缩小，取其中的值
>         3.  如果缩小到空串，返回空串

### 5.Valid Parentheses有效括号 ###

#### 问题： ####

> 给定一个仅包含字符 ‘(’, ‘)’, ‘\{’, ‘\}’, ‘\[’ 和 ‘\]’ 的字符串 s，确定输入字符串是否有效。
> 
> 输入字符串在以下情况下有效：
> 
> 开括号必须用相同类型的括号闭合。 开括号必须以正确的顺序闭合。
> 
> Input: s = “()\[\]\{\}”  
> Output: true
> 
> Input: s = “(\]”  
> Output: false

#### 解决问题思路： ####

## 2022/12/10 ##

[文章][Link 2]

### 1.Merge Two Sorted Lists合并两个排序列表 ###

#### 问题： ####

> 给你两个排序的链表list1 和list2 的头。  
> 将两个列表合并到一个排序列表中。  
> 返回合并链表的头部。
> 
> Input: list1 = \[1,2,4\], list2 = \[1,3,4\]  
> Output: \[1,1,2,3,4,4\]

#### 解决问题思路： ####

> 1.  如果list1为空，返回list2
> 2.  如果list2为空，返回list1
> 3.  如果list1的元素比list2的元素小，那么list1的next指向list2中的元素，返回list1，用递归方法
> 4.  如果list1的元素大于list2的元素值，那么list2的next指向list1中的元素，返回list2，用递归方法

### 2.Remove Duplicates from Sorted Array从排序数组中删除重复项 ###

#### 问题： ####

> 给定一个按非递减顺序排序的整数数组 nums，就地删除重复项，使每个唯一元素只出现一次。元素的相对顺序应保持不变。  
> 由于在某些语言中无法更改数组的长度，因此您必须将结果放在数组 nums 的第一部分。更正式地说，如果删除重复项后有 k 个元素，则 nums 的前 k 个元素应该保存最终结果。在前 k 个元素之外留下什么并不重要。  
> 将最终结果放入 nums 的前 k 个槽后返回 k。  
> 不要为另一个数组分配额外的空间。您必须通过使用 O(1) 额外内存就地修改输入数组来做到这一点。
> 
> Input: nums = \[0,0,1,1,1,2,2,3,3,4\]  
> Output: 5, nums = \[0,1,2,3,4,*,*,*,*,\_\]  
> Explanation: Your function should return k = 5, with the first five elements of nums being 0, 1, 2, 3, and 4 respectively.  
> It does not matter what you leave beyond the returned k (hence they are underscores).

#### 解决问题思路： ####

> 1.  如果数组为空或者数组长度长度1，则无需处理，直接返回数组长度
> 2.  初始化int i为0，从第1个元素开始
> 3.  for循环，从第2个元素开始如果当前元素与上一个元素不同，将当前元素复制到第i位置，并将i后移1
> 4.  返回不重复的元素的长度+1；

### 3.Remove Element移除元素 ###

#### 问题： ####

> 给定一个整数数组 nums 和一个整数 val，就地删除 nums 中所有出现的 val。元素的相对顺序可能会改变。  
> 由于在某些语言中无法更改数组的长度，因此您必须将结果放在数组 nums 的第一部分。更正式地说，如果删除重复项后有 k 个元素，则 nums 的前 k 个元素应该保存最终结果。在前 k 个元素之外留下什么并不重要。
> 
> Input: nums = \[0,1,2,2,3,0,4,2\], val = 2  
> Output: 5, nums = \[0,1,4,0,3,*,*,\_\]  
> Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.  
> Note that the five elements can be returned in any order.  
> It does not matter what you leave beyond the returned k (hence they are underscores).

#### 解决问题思路： ####

> 1.  定义一个方法，接受一个整数数组和要移除的整数值，返回一个整数
> 2.  如果数组为空或长度为0，返回0；
> 3.  定义变量i，表示当前可插入的位置为
> 4.  for循环数组到末尾，如果索引j的值不等于目标值，则将数组i的值=数组j的值，i的索引位置向后移动
> 5.  最后返回数组的长度

#### 4.Implement strStr()实现 strStr() ####

#### 问题： ####

> 给定两个字符串 needle 和 haystack，返回 haystack 中第一次出现 needle 的索引，如果 needle 不是 haystack 的一部分，则返回 -1。  
> 当 needle 为空字符串时，我们应该返回什么？  
> 针对这个问题，当needle为空字符串时，我们将返回0，这与C的strstr()和Java的indexOf()是一致的

#### 解决问题思路： ####

> 1.  int strStr（String haystack,String needle)
> 2.  如果needle为空，或者等于haystack，返回0
> 3.  取出两个字符串长度
> 4.  如果needle的长度大于haystack的长度，返回-1
> 5.  for循环从0开始到haystack的末尾
> 6.  如果haystack的i到i+nLen的子串等于needle，则返回i 注意：用substring分割数据，（a,b)取值是a~b-1
> 7.  否则返回-1

#### 5.Search Insert Position搜索插入位置 ####

#### 问题： ####

> 给定一个由不同整数组成的排序数组和一个目标值，如果找到目标，则返回索引。  
> 如果不是，则返回按顺序插入的索引。  
> 您必须编写一个具有 O(log n) 运行时复杂度的算法。
> 
> Input: nums = \[1,3,5,6\], target = 5  
> Output: 2
> 
> Input: nums = \[1,3,5,6\], target = 2  
> Output: 1
> 
> Input: nums = \[1,3,5,6\], target = 7  
> Output: 4

#### 解决问题思路： ####

> 1.  serchInsert(int\[\] nums,int target)
> 2.  如果nums为null或长度为0 ，返回-1
> 3.  定义索引区间的左端点和右端点
> 4.  当左端点《右端点，继续循环
> 5.  计算中间位置
> 6.  如果中间值=target， 返回之间值
> 7.  如果小于，缩小到mid+1否者mid-1；
> 8.  如过没有找到，返回应该插入的位置

[Link 1]: https://blog.csdn.net/weixin_45428910/article/details/128261022?csdn_share_tail=%7B%22type%22%3A%22blog%22%2C%22rType%22%3A%22article%22%2C%22rId%22%3A%22128261022%22%2C%22source%22%3A%22weixin_45428910%22%7D
[Link 2]: https://blog.csdn.net/weixin_45428910/article/details/128271154?spm=1001.2014.3001.5501