【算法】二刷lc记录1
1. 两数之和
给定一个整数数组 nums 和一个整数目标值 target，请你在该数组中找出 和为目标值 target 的那 两个 整数，并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。 你可以按任意顺序返回答案。
- 思路:
遍历数组，先判断map中是否有值加上当前数等于target，如符合则是答案，反之再将该数放入map中继续遍历。 - 注意点：
Map的key是数组元素，value 是下标；
如果先把数存入map中，则可能查到本身数两次比如 target = 2，nums[i] = 1。
code
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer,Integer> map = new HashMap<>();
int[] res = new int[2];
for(int i = 0;i < nums.length; i ++){
if(map.containsKey(target - nums[i])){
res[0] = map.get(target - nums[i]);
res[1] = i;
}
map.put(nums[i],i);
}
return res;
}
}2. 两数相加
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。 请你将两个数相加，并以相同形式返回一个表示和的链表。 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
- 思路
这种涉及到头节点的操作需要新建一个dummy节点，返回dummy.next;
利用一个w数，w = 两链表的两个节点相加的值 w % 10 为当前位的大小，w / 10为是否进位。 - 注意点
终止条件是l1 l2 都不等于空 或者w 也不等于空，w不等于空则说明还需继续进位操作。
code
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
int w = 0;
ListNode dummy = new ListNode(-1);
ListNode cur = dummy;
while(l1 != null || l2 != null || w != 0){//w不等于零就可能还存在进位，容易忽视
if(l1 != null){
w += l1.val;
l1 = l1.next;
}
if(l2 != null){
w += l2.val;
l2 = l2.next;
}
cur.next = new ListNode(w % 10);
cur = cur.next;
w /= 10;
}
return dummy.next;
}3. 无重复字符的最长子串
给定一个字符串 s ，请你找出其中不含有重复字符的 最长子串 的长度
- 思路：双指针模板题，一前一后指针，开一个map记录 i 到 j 这段区间每个值出现的次数。前面的指针疯狂试探最远的不重复子串能到什么位置，如果重复了，则缩小区间，并将对应重复元素出现的值--。再去试探。
code
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character,Integer> map = new HashMap<>();
int res = 0;
for(int i = 0,j = 0; i < s.length(); i ++){
map.put(s.charAt(i),map.getOrDefault(s.charAt(i),0) + 1);
while(map.get(s.charAt(i)) > 1){
map.put(s.charAt(j),map.get(s.charAt(j)) - 1);
j ++;
}
res = Math.max(res,i - j + 1);
}
return res;
}
}5. 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
- 思路
枚举每个中心点，分奇数情况和偶数情况去更新最大值，注意更新时的下标处理。
code
class Solution {
public String longestPalindrome(String s) {
String res = "";
int n = s.length();
for(int m = 0; m < n; m++){
//偶数情况
int l = m, r = m + 1;
while(l >= 0 && r < n && s.charAt(l) == s.charAt(r)){
r ++;
l --;
}
if(r - l -1 > res.length())res = s.substring(l + 1,r);
//奇数情况
l = m - 1;
r = m + 1;
while(l >= 0 && r < n && s.charAt(l) == s.charAt(r)){
r ++;
l --;
}
if(r - l - 1 > res.length())res = s.substring(l + 1,r);
}
return res;
}
}7. 整数反转
给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。 如果反转后整数超过 32 位的有符号整数的范围 [−231, 231 − 1] ，就返回 0。 假设环境不允许存储 64 位整数（有符号或无符号）。
- 思路:
模拟
逐位模拟，正数和负数的溢出分别处理即可
code
class Solution {
public int reverse(int x) {
int res = 0;
while(x != 0){
if(res < 0 && res < (Integer.MIN_VALUE - x % 10) / 10)return 0;
if(res > 0 && res > (Integer.MAX_VALUE - x % 10) / 10)return 0;
res = res * 10 + x % 10;
x /= 10;
}
return res;
}
}9. 回文数
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。 回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。
- 思路
模拟
因为不让转化成字符串，可以借助<整数反转>的思想，将其反转后再判断两数是否相等。
- 注意点
BaseCase是0 为true, x < 0 或者 x 个位为0也都不是回文数
code
class Solution {
public boolean isPalindrome(int x) {
if(x == 0)return true;
if(x < 0 || x % 10 == 0)return false;
int rev = 0;
int t = x;
while(t != 0){
rev = rev * 10 + t % 10;
t /= 10;
}
return rev == x;
}
}14. 最长公共前缀
给你一个整数 x ，如果 x 是一个回文整数，返回 true ；否则，返回 false 。 回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。例如，121 是回文，而 123 不是。
- 思路
以第一个数为模板，去和每一个串对比，如果该串不是以模板开头，则让模板删除最后一个字符继续做对比，
这样每个ch都会startswith(res)了
code
class Solution {
public String longestCommonPrefix(String[] strs) {
String tmp = strs[0];
for(int i = 1; i < strs.length; i ++){
while(!strs[i].startsWith(tmp)){
tmp = tmp.substring(0,tmp.length() - 1);
}
}
return tmp;
}
}15. 三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有和为 0 且不重复的三元组。 注意：答案中不可以包含重复的三元组。
- 思路
排序＋双指针：
在数组有序之后，利用i j k三个指针，ij确定位置后k从最后位置开始尝试，当j向右走，k只可能往左走，因为
是有序的还要满足和为0；至于去重，当ij开始循环时判断和各自上一个数 i - 1,j - 1是否相等，如果相等，则说明此类情况已经枚举过了，从而达到去重效果。
注意点
双指针在判断循环时，判断的时k下一个数nums[k - 1]是否满足性质，如果nums[i,j,k-1]三个数的和小于0，则说明nums[k] 是这冲循环最后一个可能满足条件的数。class Solution { public List<List<Integer>> threeSum(int[] nums) { List<List<Integer>> res = new ArrayList<>(); Arrays.sort(nums); for(int i = 0; i < nums.length; i ++){ if(i > 0 && nums[i] == nums[i - 1])continue; for(int j = i + 1,k = nums.length - 1;j < k; j ++){ if(j > i + 1 && nums[j - 1] == nums[j])continue; while(j < k - 1 && nums[i] + nums[j] + nums[k] >= 0)k --;//判断下一个数是否小于0 if(nums[i] +nums[k] + nums[j] == 0){ res.add(Arrays.asList(nums[i],nums[j],nums[k])); } } } return res; } }17. 电话号码的字母组合
思路
回溯 + 模拟哈希
将2-9数字对应字符串对应到string数组中，dfs时计数已搜索的个数
注意点
回溯时stirngbuffer的subtirng返回的是string,需要转成stirngbuffer;
用stringbuffer.deleteCharAt(int index)则可以不用转class Solution { String[] strs ={ "", "", "abc","def","ghi","jkl","mno","pqrs","tuv","wxyz" }; List<String> res = new ArrayList<>(); StringBuffer path = new StringBuffer(""); public List<String> letterCombinations(String digits) { if(digits.length() == 0)return res; dfs(digits,0); return res; } public void dfs(String digits,int u){ if(path.length() == digits.length()){ res.add(path.toString()); return; } String str = strs[digits.charAt(u) - '0']; for(int i = 0; i < str.length();i ++){ path.append(str.charAt(i)); dfs(digits,u + 1); path.deleteCharAt(path.length() - 1); // path = new StirngBuffer(path.substring(0,path.length() - 1)); } } }
19. 删除链表的倒数第 N 个结点
给你一个链表，删除链表的倒数第 n 个结点，并且返回链表的头结点。 进阶：你能尝试使用一趟扫描实现吗？
思路
快慢双指针
- 让快指针先走n步，然后快慢指针一起走，当快指针的下一个节点为空时，慢指针即走到倒数第N个节点的前一个节点，删除即可。
- 简单证明：设链表长 要想删除倒数k个节点，走的步数是l - n ，我们需要找到其l - n - 1位置以便删除；
当快指针先走n步，则快指针来到n + 1的位置，之后快慢以前走，当快的next等于空时，慢指针就走了 l - (n + 1)步即慢指针走到所需位置
- 注意点如果快指针在走n步时其走到了最后一个节点，则删除的时第一个节点，直接返回head.next即可
code
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode fast = head;
ListNode slow = head;
while(n -- > 0){
fast = fast.next;
}
if(fast == null)return head.next;//特判删除的是否为头节点
while(fast.next != null){
slow = slow.next;
fast = fast.next;
}
slow.next = slow.next.next;
return head;
}
}20. 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。- 思路
栈模拟
因为要求配对括号必须是挨着一起的，所以可以利用一个栈，遇到左括号则入栈，如遇右括号，则判断其和栈顶元素ascll码绝对值是否差2，如是，则说明是配对括号，就弹出栈顶元素。反之直接返回false。最后判断栈空即可
符ascii码表
