算法题：
- 数据结构：数组、链表、字符串、树、数学、栈、hash表、图
- 动态规划、中心扩散、回溯算法、递归、迭代、贪心算法、
- 从整体到细节，自顶向下，从抽象到具体的框架思维是通用的，不只是学习数据结构和算法，学习其他任何知识都是高效的。
一、数组：
技巧：
- 双指针
二、链表：
技巧：
- 链表问题一般先定义一个哑结点，将特殊清除处理掉
链表反转
private Node reverse(Node node) {
Node pre = null, cur = node, tem = null;
while (cur != null) {
tem = cur.next;
cur.next = pre;
pre = cur;
cur = tem;
}
return pre;
}
2. 两数相加
难度中等 6174
给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。
请你将两个数相加，并以相同形式返回一个表示和的链表。
你可以假设除了数字 0 之外，这两个数都不会以 0 开头。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { = val; }
* ListNode(int val, ListNode next) { = val; = next; }
* }
*/
class Solution {
public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
// 特判：
if(l1==null)return l2;
if(l2==null)return l1;
int carry=0;
ListNode dummy =new ListNode(0);// 定义个哑结点，便于处理
ListNode pre=dummy; // 指向哑结点的地址、最终返回;
while(l1!=null && l2!=null){
int sum =l1.val+l2.val+carry;
carry =sum/10;
ListNode node =new ListNode(sum%10);
dummy.next=node;
l1=l1.next;
l2=l2.next;
dummy=dummy.next;
}
while(l1!=null){
int sum =l1.val+carry;
carry =sum/10;
ListNode node =new ListNode(sum%10);
dummy.next=node;
l1=l1.next;
dummy=dummy.next;
}
while(l2!=null){
int sum =l2.val+carry;
carry =sum/10;
ListNode node =new ListNode(sum%10);
dummy.next=node;
l2=l2.next;
dummy=dummy.next;
}
if(carry>0){
dummy.next=new ListNode(carry);
}
return pre.next;
}
}
- 看清题意，有时候需要做链表的反转。
19. 删除链表的倒数第 N 个结点
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { = val; }
* ListNode(int val, ListNode next) { = val; = next; }
* }
*/
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
// 方式1： 遍历一遍,统计元素个数总和 ，再遍历
// 方式2： 快慢指针
// 定义一个哑结点，使得链表中所有的结点都有前驱结点
ListNode dummy = new ListNode(0,head);
// 定义快慢指针都指向哑结点
ListNode fast=dummy, slow=dummy;
// 让快指针先往前移动 n+1 步
for(int i=0;i<n+1;i++){
fast=fast.next;
}
// 同时移动快慢指针，直到快指针指向null
while(fast!=null){
fast=fast.next;
slow=slow.next;
}
// 不清理要删除元素所占的空间。
// =;
// 清理待删除元素所占的空间
ListNode delNode =slow.next;
slow.next=delNode.next;
delNode.next=null;
return dummy.next;
}
}
寻找链表的中间结点：
// 快慢指针，慢指针一次走一步，快指针一次走两步。最终慢指针指向就为中间结点
private ListNode endOfFirstHalf(ListNode head) {
ListNode fast = head;
ListNode slow = head;
while (fast.next != null && fast.next.next != null) {
fast = fast.next.next;
slow = slow.next;
}
return slow;
}
141. 环形链表
public class Solution {
public boolean hasCycle(ListNode head) {
Set<ListNode> seen = new HashSet<ListNode>();
while (head != null) {
if (!(head)) {
return true;
}
head = ;
}
return false;
}
}
面试题 02.06. 回文链表
- 其中包括获取中间结点的方法
- 链表反转的方法。
- 最终达到
class Solution {
public boolean isPalindrome(ListNode head) {
// 方式3：反转后半段链表，然后比较前后半段链表的值
// 1、通过快慢指针，找出链表的中间结点，慢指针的next结点为后半部分的开始
ListNode firstTail = getFirstHalf(head);
if(firstTail==null) return true ;
//2、反转后半部分链表
ListNode nextHalf= reversal(firstTail.next);
//3、比较将原链表和后半部分值比较。（不同return false， 相同返回true）
while(nextHalf!=null){
if(head.val!=nextHalf.val){
return false;
} else{
head=head.next;
nextHalf=nextHalf.next;
}
}
return true;
}
// 获取链表中间结点的方法
private ListNode getFirstHalf(ListNode head){
ListNode fast =head,slow =head;
while(fast!=null&&fast.next!=null&& fast.next.next!=null){
fast =fast.next.next;
slow=slow.next;
}
return slow;
}
// 链表反转
private ListNode reversal(ListNode node){
ListNode pre = null, cur=node,tem=null;
while(cur!=null){
tem =cur.next;
cur.next=pre;
pre=cur;
cur=tem;
}
return pre;
}
}
三、字符串：
- 字符串问题一般转换成char数组，去操作数组，省的每次操作字符串的
(i)
1、验证子串是否为回文串
// char[] charArr =();// 字符串转换成char数组
private static boolean validateSubstring(char[] charArr, int left ,int right){
while(left<right){
if(charArr[left]!=charArr[right]){
return false;
}
left++;
right--;
}
return true;
}
5. 最长回文子串
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = “babad”
输出：“bab”
解释：“aba” 同样是符合题意的答案。示例 2：
输入：s = “cbbd”
输出：“bb”
示例 3：输入：s = “a”
输出：“a”
示例 4：输入：s = “ac”
输出：“a”提示：
1 <= <= 1000
s 仅由数字和英文字母（大写和/或小写）组成
class Solution {
public String longestPalindrome(String s) {
// 特判
if(null==s || s.length()<2) return s;
// 中心扩散法
int res =1; //最大长度
int ll=0; //最大回文串的左指针
int rr=0; //最大回文串的右指针
//将字符串转成char数组，不在循环中去使用(i)
char[] chArr =s.toCharArray();
// 开始遍历char数组
for(int i =0; i<chArr.length; i++){
// 以i为中心向两边扩散，寻找最长子串（通俗：回文串为奇数长度i为中心）
int l =i-1;
int r =i+1;
while(l>=0 && r<chArr.length && chArr[l]==chArr[r]){
int len =r-l+1;
if(len>res){
res=len;
ll=l;
rr=r;
}
l--;
r++;
}
// 以i为左指针，i+1为右指针（通俗：回文串为偶数长度）
l=i;
r=i+1;
while(l>=0 && r<chArr.length && chArr[l]==chArr[r]){
int len =r-l+1;
if(len>res){
res=len;
ll=l;
rr=r;
}
l--;
r++;
}
}
return s.substring(ll,rr+1);
}
}
四、树：
技巧：
- 递归最简单，一般树的问题都可以通过递归来解决。（需要再学下迭代，迭代是显示维护一个栈）
- 前序遍历：根左右；
中序遍历：左根右；后序遍历：左右根。
94. 二叉树的中序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* = val;
* = left;
* = right;
* }
* }
*/
class Solution {
public List<Integer> inorderTraversal(TreeNode root) {
// 中序遍历：左 根 右
List<Integer> list = new ArrayList<Integer>();
leftOrder(root,list);
return list;
}
private void leftOrder(TreeNode node, List list){
if(null==node) return;
leftOrder(node.left,list);
list.add(node.val);
leftOrder(node.right,list);
}
}
五、栈：
六、Hash表
七、图
八、动态规划（labuladong）
动态规划的特点：
- 重叠子问题
- 状态转义方程（最关键）
- 最优子结构
题型：
- 求最值
- 核心：穷举：不要小看暴力穷举
解题套路：
- 明确【状态】
- 明确【选择】
- 明确dp函数、数组的定义
- 明确base case。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-RsFw2FXi-1622290180636)(%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E9%A2%/)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EqdphKC2-1622290180639)(%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E9%A2%/)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lMB5LyEx-1622290180641)(%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E9%A2%/)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-iv9SXKeI-1622290180645)(%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E9%A2%/)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-onKZYvFS-1622290180646)(%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E9%A2%/)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4RaL0PV6-1622290180648)(%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E9%A2%/)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-DuZMyq2H-1622290180649)(%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E9%A2%/)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-lSizQQ5a-1622290180649)(%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E9%A2%/)]
-
空间换时间。引入数组备忘录，占用数组大小的空间。
-
自底向上：
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-EtPHrtHP-1622290180650)(%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E9%A2%/)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-QXdBtZBI-1622290180651)(%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E9%A2%/)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-tdIKRMnf-1622290180652)(%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E9%A2%/)]
- 优秀的算法都是慢慢演变来的 ，就像系统架构一样，不是一开始就很优，都是慢慢演变的
509：斐波那契数列
class Solution {
public int fib(int n) {
// 方式1：直接递归 ，但是时间复杂度较高，多了很多重复的计算。
/*// 方式2：带备忘录的递归。将所有计算过的值缓存下来，递归中直接返回。（自顶向下推，然后自底向上回溯）
// 初始化备忘录。
int[] notes =new int[n+1];
// 进行带备忘录的递归。
return helper(notes, n);*/
/* // 方式3：dp数组迭代法 （自底向上）
if(n==0) return 0;
int[] dp =new int[n+1];
// base case
dp[0]=0; dp[1]=1;
// 状态转移
for(int i=2; i<=n;i++){
dp[i]=dp[i-1]+dp[i-2];
}
return dp[n];*/
//方式4： 优化空间复杂度，求第n个数，其实只需要知道他的前两个数就可以了 ，
// 因此可以定义两个变量去表示它的前两个数的值，依次来优化空间复杂度
if(n==0) return 0;
int pre=0,curr=1;
for(int i=2;i<=n;i++){
int sum=pre+curr;
pre =curr;
curr=sum;
}
return curr;
}
private int helper(int[] notes,int n){
if(n==0|| n==1) return n; //base case
if(notes[n]!=0) return notes[n];
notes[n] =helper(notes,n-1)+helper(notes,n-2);
return notes[n];
}
}
322. 零钱兑换
- 动态规划 是用于求最值的问题。
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-l8LPzpXZ-1622290180652)(%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E9%A2%/)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-inO9cJ24-1622290180653)(%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E9%A2%/)]
- 自顶向下的递归（带备忘录）
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-cDrON8qK-1622290180654)(%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E9%A2%/)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-PfYzUeuZ-1622290180655)(%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E9%A2%/)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-byRez0zV-1622290180655)(%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E9%A2%/)]
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4xp2AyzG-1622290180656)(%E5%B8%B8%E8%A7%81%E7%AE%97%E6%B3%95%E9%A2%/)]
动态规划问题的本质：
- 1、如何穷举
- 写出状态转移方程，暴力穷举所有可行解。
- 2、如何聪明的穷举
- 用备忘录消除重叠子问题，写出自动向下解法
- 进一步，可以写出自动向下解法
- 再进一步，可能可以优化空间复杂度