1. 两数之和（难度：简单）
https://leetcode.cn/problems/two-sum/
代码：
class Solution {
public int[] twoSum(int[] nums, int target) {
// 初始化map： 【值:下标】
HashMap<Integer, Integer> tempMap = new HashMap();
int[] res = new int[2];
for(int i=0; i<nums.length; i++) {
Integer another = target - nums[i];
// 如果目标值 存在tempMap中，则说明找到了结果
if(tempMap.containsKey(another)) {
res[0] = i;
res[1] = tempMap.get(another);
return res;
}
// 将【值:下标】 存储在map中 (常规套路，在写代码时进入for后 就可以先写这一步)
tempMap.put(nums[i], i);
}
return res;
}
}
总结注意点：
- 空间换时间的思想，将当前值 以及对应下标信息 存储在map中
核心代码：
// 初始化：存储 某个值 以及 在nums中的位置信息
HashMap<Integer, Integer> tempMap = new HashMap();
// 如果目标值 存在tempMap中，则说明找到了结果
if(tempMap.containsKey(another)) {
res[0] = i;
res[1] = tempMap.get(another);
return res;
}
// 主流程：把当前值 及 对应位置信息存入到map中
tempMap.put(nums[i], i);
2. 两数相加（难度：中等）
https://leetcode.cn/problems/add-two-numbers/
代码：
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
ListNode head1 = l1; // 移动指针1，指向链表1
ListNode head2 = l2; // 移动指针2，指向链表2
// 构建结果链表
ListNode resHead = new ListNode();
ListNode temp = resHead;// 移动指针3，指向链表3
// 进位值， 默认是0 （作用域一定要是外面）
int carry = 0;
while(null != head1 || null != head2) {
// 为空取0， 否则取val（核心思想）
int num1 = null==head1 ? 0 : head1.val;
int num2 = null==head2 ? 0 : head2.val;
int sum = num1 + num2 + carry;
// 求模取余 获取当前节点值
int curVal = sum % 10;
// 整除获取进位值
carry = sum / 10;
// 构建当前节点
ListNode curNode = new ListNode(curVal);
// 尾插法
temp.next = curNode; temp = curNode;
// 节点后移，只需要考虑不为null的链表即可，因为为null的话我们默认取0, 不会有影响
if(null != head1)
head1 = head1.next;
if(null != head2)
head2 = head2.next;
}
// 最后节点遍历完后，判断最后一步运算是否进位了，进位则补1，否则不处理
if(carry == 1) {
ListNode lastNode = new ListNode(1);
temp.next = lastNode;
}
return resHead.next;
}
}
总结注意点：
- 常规链表的移动指针，三个移动指针对应三个链表
while(null != head1 || null != head2)循环条件是 || 不是&&（任意一个链表没走完就执行的逻辑）int num1 = null==head1 ? 0 : head1.val当前节点 为null取0，否则取val- 构建进位变量
carry，作用域一定要放到外面；放里面就没法用了 - 考虑最后一步：最后节点遍历完后，判断最后一步运算是否进位了，进位则补1，否则不处理
3. 无重复字符的最长子串（难度：中等）
https://leetcode.cn/problems/longest-substring-without-repeating-characters/
代码：
class Solution {
public int lengthOfLongestSubstring(String s) {
// 判空处理
if(null == s || s.length() == 0) {
return 0;
}
// 初始化map： 【值:下标】
HashMap<Character, Integer> map = new HashMap();
// 定义滑动窗口最左侧指针
int l = 0;
// 最大长度
int maxLength = 0;
// r可以理解为 滑动窗口最右侧指针
for(int r = 0; r < s.length(); r++) {
char curChar = s.charAt(r);
// 若map中之前存过这个值的下标，则让left指针右移
if(map.containsKey(curChar)) {
// 目的：更新l 为 l、map(curChar)最右侧的下标
// Math.max的好处：我们不需要考虑这个值是否在滑动窗口内
l = Math.max(l, map.get(curChar) + 1);
}
// 更新最大长度
maxLength = Math.max(maxLength, r - l + 1);
// 将【值:下标】 存储在map中 (常规套路，在写代码时进入for后 就可以先写这一步)
map.put(curChar, r);
}
return maxLength;
}
}
解题思路：
该题是一道滑动窗口的问题。
滑动窗口的一般套路：左区间手动改变，有区间for循环累加
B站上视频链接：
https://www.bilibili.com/video/BV1BV411i77g
https://www.bilibili.com/video/BV1w5411E7EP
总结注意点：
- 和第一道题【1. 两数之和】类似点在于，都可以使用 一个map 来记录【值:下标】
- 使用
双指针构建滑动窗口的 经典问题。（套路：左边界手动改变 右边界自动累加） l和r滑动窗口的区间[l,r]表示的就是当前所维护的不重复的字串l = Math.max(l, map.get(curChar) + 1),这里取得是map.get(curChar) + 1，别忘了+1了。如果不+1的话，那么字串可能是abca这种，即第一个字符与后面那个字符重复
4. 寻找两个正序数组的中位数（难度：困难）- 先不做
5. 最长回文子串（困难：中等）
https://leetcode.cn/problems/longest-palindromic-substring/
解法一：暴力 - 遍历所有字串
代码：
class Solution {
public String longestPalindrome(String s) {
String longestPalindrome = "";
// 遍历所有的子串，若长度比longestPalindrome长 且 是回文串，则更新longestPalindrome
for(int i=0; i<s.length(); i++) {
for(int j=i; j<s.length(); j++) {
if(j - i + 1 > longestPalindrome.length()) {
if(isPalindrome(s.substring(i, j+1))) {
longestPalindrome = s.substring(i, j+1);
}
}
}
}
return longestPalindrome;
}
// 判断是否是回文字符串
public Boolean isPalindrome(String s) {
// 双指针
int left = 0;
int right = s.length() - 1;
while (left <= right) {
if(s.charAt(left) != s.charAt(right)) {
return false;
}
left ++;
right --;
}
return true;
}
}
总结注意点：
- 第一步：先写出 判断是否回文 的方法
isPalindrome。 （利用双指针的思想） - 第二步：暴力遍历每个子字符串，判断是否回文，更长的则更新
解法二：动态规划
待完善
解法三：中心扩展算法
待完善
转载：https://blog.csdn.net/qq_45464560/article/details/128427357
查看评论