数据结构和算法是编程路上永远无法避开的两个核心知识点，本系列【算法题】旨在记录刷题过程中的一些心得体会，将会挑出LeetCode等最具代表性的题目进行解析，题解基本都来自于LeetCode官网（https://leetcode-cn.com/），本文是第一篇。
1.两数之和（原第1题）
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
（1）知识点
哈希表：保存数组中的每个元素与其索引相互对应的最好方法。
（2）解题方法
方法转自：https://leetcode-cn.com/problems/two-sum/solution/liang-shu-zhi-he-by-leetcode-2/
方法一：暴力法
暴力法很简单，遍历每个元素 x，并查找是否存在一个值与 target?x 相等的目标元素。
- 时间复杂度：O(n^2)，对于每个元素，我们试图通过遍历数组的其余部分来寻找它所对应的目标元素，这将耗费 O(n) 的时间。因此时间复杂度为 O(n^2)。
- 空间复杂度：O(1)。
方法二：两遍Hash表
通过以空间换取速度的方式，我们可以将查找时间从 O(n) 降低到 O(1)。哈希表正是为此目的而构建的，它支持以 近似 恒定的时间进行快速查找。我用“近似”来描述，是因为一旦出现冲突，查找用时可能会退化到 O(n)。但只要你仔细地挑选哈希函数，在哈希表中进行查找的用时应当被摊销为 O(1)。
一个简单的实现使用了两次迭代。在第一次迭代中，我们将每个元素的值和它的索引添加到表中。然后，在第二次迭代中，我们将检查每个元素所对应的目标元素（target - nums[i]）是否存在于表中。注意，该目标元素不能是 nums[i] 本身！
- 时间复杂度：O(n)，我们把包含有 n 个元素的列表遍历两次。由于哈希表将查找时间缩短到 O(1) ，所以时间复杂度为 O(n)。
- 空间复杂度：O(n)，所需的额外空间取决于哈希表中存储的元素数量，该表中存储了 n 个元素。
方法三：一遍Hash表
事实证明，我们可以一次完成。在进行迭代并将元素插入到表中的同时，我们还会回过头来检查表中是否已经存在当前元素所对应的目标元素。如果它存在，那我们已经找到了对应解，并立即将其返回。
- 时间复杂度：O(n)，我们只遍历了包含有 n 个元素的列表一次。在表中进行的每次查找只花费 O(1) 的时间。
- 空间复杂度：O(n)，所需的额外空间取决于哈希表中存储的元素数量，该表最多需要存储 n 个元素。
（3）伪代码
函数头：int[] twoSum(int[] nums, int target)
方法二：两遍Hash表
- 定义一个HashMap
- 第一次遍历数组
- 将数组值存为key，数组下标存为value
- 第二次遍历数组
- 记录r为目标值减去当前的值
- 判断map是否已经存在r这个key，并且这个key的value不等于当前遍历到的位置（i），为true则返回i和r对应的value。
方法三：一遍Hash表
- 定义一个HashMap
- 遍历数组
- 记录r为目标值减去当前的值
- 判断map是否已经存在r这个key，为true则返回i和r对应的value。
- 数组值存为key，数组下标存为value
（4）代码示例
public int[] twoSum(int[] nums, int target) {
int res = 0;
HashMap<Integer, Integer> map = new HashMap<>();
for(int i = 0; i < nums.length; ++i){
res = target - nums[i];
if(map.containsKey(res)){
return new int[]{map.get(res), i};
}
map.put(nums[i], i);
}
return new int[0];
}
2.两数相加（原第2题）
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
示例:
输入：(2 -> 4 -> 3) + (5 -> 6 -> 4)
输出：7 -> 0 -> 8
原因：342 + 465 = 807
（1）知识点
链表
（2）解题方法
方法转自：：https://leetcode-cn.com/problems/add-two-numbers/solution/liang-shu-xiang-jia-by-leetcode/
方法：初等数学
我们使用变量来跟踪进位，并从包含最低有效位的表头开始模拟逐位相加的过程。
- 时间复杂度：O(max(m, n))，假设 m 和 n 分别表示 l1 和 l2 的长度，上面的算法最多重复 max(m, n) 次。
- 空间复杂度：O(max(m, n))，新列表的长度最多为 max(m,n)+1。
（3）伪代码
函数头：ListNode addTwoNumbers(ListNode l1, ListNode l2)
方法：初等数学
- 定义一个用于返回最后结果的节点res，和一个指向它用于移动的节点curr=res
- 定义用于记录进位的数t=0
- 定义p，q分别指向l1和l2的头部
- 遍历两个链表（p或q不为空）
- 如果p不为空x=p.val，否则x=0。y也一样
- sum=x+y+t
- 更新进位t=sum/10
- res=new ListNode(sum%10)
- 移动res指针和p与q指针（pq要判空）
（4）代码示例
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int carry = 0;
ListNode dummy = new ListNode(-1);
ListNode tmp = dummy;
while(l1 != null || l2 != null){
int sum = 0;
if(l1 != null) {
sum += l1.val;
l1 = l1.next;
}
if(l2 != null) {
sum += l2.val;
l2 = l2.next;
}
sum += carry;
carry = sum / 10;
sum %= 10;
tmp.next = new ListNode(sum);
tmp = tmp.next;
}
if(carry != 0) tmp.next = new ListNode(carry);
return dummy.next;
}
3.无重复字符的最长子串（原第3题）
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
示例:
输入: "abcabcbb"
输出: 3
解释: 因为无重复字符的最长子串是 "abc"，所以其长度为 3。
（1）知识点
哈希集合：主要利用HashSet来判断以某个字符开始的子串中有无重复字符。
（2）解题方法
方法转自：https://leetcode-cn.com/problems/longest-substring-without-repeating-characters/solution/wu-zhong-fu-zi-fu-de-zui-chang-zi-chuan-by-leetc-2/
方法：滑动窗口
我们不妨以示例一中的字符串 abcabcbb 为例，找出 从每一个字符开始的，不包含重复字符的最长子串，那么其中最长的那个字符串即为答案。对于示例一中的字符串，我们列举出这些结果，其中括号中表示选中的字符以及最长的字符串：
以 (a)bcabcbb 开始的最长字符串为 (abc)abcbb；
以 a(b)cabcbb 开始的最长字符串为 a(bca)bcbb；
以 ab(c)abcbb 开始的最长字符串为 ab(cab)cbb；
以 abc(a)bcbb 开始的最长字符串为 abc(abc)bb；
以 abca(b)cbb 开始的最长字符串为 abca(bc)bb；
以 abcab(c)bb 开始的最长字符串为 abcab(cb)b；
以 abcabc(b)b 开始的最长字符串为 abcabc(b)b；
以 abcabcb(b) 开始的最长字符串为 abcabcb(b)。
发现了什么？如果我们依次递增地枚举子串的起始位置，那么子串的结束位置也是递增的！这里的原因在于，假设我们选择字符串中的第 k 个字符作为起始位置，并且得到了不包含重复字符的最长子串的结束位置为 rk。那么当我们选择第 k+1 个字符作为起始位置时，首先从 k+1 到 rk 的字符显然是不重复的，并且由于少了原本的第 k 个字符，我们可以尝试继续增大 rk ，直到右侧出现了重复字符为止。
- 时间复杂度：O(N)，其中 N 是字符串的长度。左指针和右指针分别会遍历整个字符串一次。
- 空间复杂度：O(∣Σ∣)，其中 Σ 表示字符集（即字符串中可以出现的字符），∣Σ∣ 表示字符集的大小。在本题中没有明确说明字符集，因此可以默认为所有 ASCII 码在 [0,128) 内的字符，即 ∣Σ∣=128|。我们需要用到哈希集合来存储出现过的字符，而字符最多有 ∣Σ∣ 个，因此空间复杂度为 O(∣Σ∣)。
（3）伪代码
函数头：int lengthOfLongestSubstring(String s)
方法：滑动窗口
- 定义HashSet用于记录每一个字符开头的字符集
- 定义一个动指针rk和要返回的结果res（最大长度）
- 从第一个字符开始遍历字符串
+ 不为第一个字符时，集合每循环一次移除掉头一个字符（如上例中 a(b)cabcbb 的时候，就需要把第一个字母a移除掉，确保第二重循环开始时集合都是以当前字母开始的
+ 第二重循环（使用while，当rk不大于n且集合不包含rk位置的字符执行）
+ 集合添加rk位置的字符串，rk++
+ 用max函数比较一下最大的长度
（4）代码示例
public int lengthOfLongestSubstring(String s) {
int max = 0;
HashSet<Character> set = new HashSet<>();
int start = 0, next = 0;
char startChar, nextChar;
for(start = 0; start < s.length(); ++start){
startChar = s.charAt(start);
set.add(startChar);
next = start + set.size();
while(next < s.length()){
nextChar = s.charAt(next);
if(set.contains(nextChar)) break;
set.add(nextChar);
++next;
}
max = Math.max(max, set.size());
set.remove(startChar);
}
return max;
}
4.最长回文子串（原第5题）
给定一个字符串 s，找到 s 中最长的回文子串。你可以假设 s 的最大长度为 1000。
示例 1：
输入: "babad"
输出: "bab"
注意: "aba" 也是一个有效答案。
（1）知识点
动态规划：每一个回文串首尾添加一个字符后都需要重新判断是否回文。
（2）解题方法
方法转自：https://leetcode-cn.com/problems/longest-palindromic-substring/solution/zui-chang-hui-wen-zi-chuan-by-leetcode-solution/
方法一：动态规划
动态规划最重要的是状态转移方程，找出每种状态之间的关系。动态规划的本质是填一个二维表格，通过已知位置的数据来得到未知的数据，从而将整个表填满。
对于一个子串而言，如果它是回文串，并且长度大于 2，那么将它首尾的两个字母去除之后，它仍然是个回文串。例如对于字符串 “ababa”，如果我们已经知道 “bab” 是回文串，那么 “ababa” 一定是回文串，这是因为它的首尾两个字母都是 “a”。
带上边界条件（考虑长度为1的字符串）：
- 时间复杂度：O(n^2)，其中 n 是字符串的长度。动态规划的状态总数为 O(n^2)，对于每个状态，我们需要转移的时间为 O(1)。
- 空间复杂度：O(n^2)，即存储动态规划状态需要的空间。
方法二：中心扩展算法
中心扩展算法实质上是逆向思考动态规划，动态规划是通过状态转移方程，找出每一个状态和前一个状态的关系，直到某个确定的边界（子串为1个字符或2个字符的情况）。那么我们可以先枚举出所有的边界，开始扩展，如果扩展两边的字符相同，则继续，否则从下一个边界开始扩展。
- 时间复杂度：O(n^2)，其中 n 是字符串的长度。长度为 1 和 2 的回文中心分别有 n 和 n?1 个，每个回文中心最多会向外扩展 O(n)次。
- 空间复杂度：O(1)。
方法三：Manacher 算法（先不考虑，它的时间复杂度是O(n)）
（3）伪代码
函数头：string longestPalindrome(string s)
方法一：动态规划
- 定义一个二维数组boolean[][] arr，用于记录i到j是否为回文串
- 声明返回的字符串res
- 进行预处理，将对角线的值全设定为true，对角线实质上就是字符串的每个位置的单个字符
- 第一重循环，j从1->len-1（一列一列来）
- 第二重循环，i从0->j-1（表填一半就好，因为是对称的）
- 判断i和j的字符是否想等，不相等则arr[i][j]=false；相等则判断j-i是否小于3（这是因为aa和aba这种必为回文），否则判断arr[i+1][j-1]的值
- 如果arr[i][j]为true，则更新最大长度和起始位置
- 第二重循环，i从0->j-1（表填一半就好，因为是对称的）
方法二：中心扩展算法
- 定义一个start，一个end用于记录返回的回文串的起始和终止位置
- 第一层循环（i=0->len-1）
- len1=以i为中心扩展的最长回文子串长度（func）
- len2=以i和i+1为中心扩展的最常回文子串长度（func）
- 比较len1和len2取大者
- 如果max(len1,len2)>end-start，更新start和end的值（注意这里如何通过i和len来得到start和end）
func：计算回文子串这个函数其实很简单，为了同时考虑一个和两个字符为边界的情况，只需要把一个字符的输入参数设为i和i就可以了，两个字符的则为i和i+1。
（4）代码示例
public String longestPalindrome(String s) {
int len = s.length();
if(len == 0 || len == 1) return s;
String res;
boolean [][] arr = new boolean[len][len];
for(int i = 0; i < len; ++i){
arr[i][i] = true;
}
int start = 0, maxLength = 1;
for(int j = 1; j < len; ++j){
for(int i = 0; i < j; ++i){
if(j == i + 1) {
arr[i][j] = s.charAt(i) == s.charAt(j);
}else{
arr[i][j] = arr[i+1][j-1] && s.charAt(i) == s.charAt(j);
}
if(arr[i][j] && (j - i + 1) > maxLength){
start = i;
maxLength = j - i + 1;
}
}
}
return s.substring(start, start + maxLength);
}
5.整数反转（原第7题）
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
示例 1:
输入: 123
输出: 321
示例 2:
输入: -123
输出: -321
注意:
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [?2^31, 2^31 ? 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
（1）知识点
除法和取余，以及边界条件
（2）解题方法
方法转自：https://leetcode-cn.com/problems/reverse-integer/solution/zheng-shu-fan-zhuan-by-leetcode/
方法：弹出和推入数字 & 溢出前进行检查
我们可以一次构建反转整数的一位数字。在这样做的时候，我们可以预先检查向原整数附加另一位数字是否会导致溢出。（变构建边检查）
先考虑一下如何取到每一位的数字和重构数字
//取数:
pop = x % 10;
x /= 10;
//重构:
tmp = rev * 10 + pop;
rev = tmp;
现在问题来了，tmp = rev * 10 + pop可能会溢出，那么判断一下就好了：（假设这里的rev是正数）
（3）伪代码
函数头：int reverse(int x)
方法：弹出和推入数字 & 溢出前进行检查
- 定义rev（返回的值）
- while循环（x!=0）
- 取数：pop = x % 10，x /= 10
- 判断如果rev>int的最大值或者（rev=int的最大值/10并且pop>7）——x为正
- 判断如果rev<int的最小值或者（rev=int的最大值/10并且pop<-8）——x为负
- 重构：rev = rev*10 + pop
（4）代码示例
public int reverse(int x) {
int y = 0;
int tmp = 0;
int MAX_VALUE = Integer.MAX_VALUE;
int MIN_VALUE = Integer.MIN_VALUE;
while(x != 0){
tmp = x % 10;
if(MAX_VALUE / 10 < y || (MAX_VALUE / 10 == y && tmp > 7)) return 0;
if(MIN_VALUE / 10 > y || (MIN_VALUE / 10 == y && tmp < -8)) return 0;
y = y * 10 + tmp;
x /= 10;
}
return y;
}
本文暂时没有评论，来添加一个吧(●'◡'●)