24届_Spruce.Lau
技术栈测试
1、学Java看的哪个资料：
- 重载，重写，泛型懂吗？
泛型不太懂 - Java集合这块学过了吗？
- HashMap源码，JVM，JUC是否看过：
2、数据结构与算法看的哪个资料：
- 链表，栈，队列，二叉树能自己手写吗：
学过忘了 - AVL树，红黑树，线段树学过吗：
- 冒泡，快速，归并排序能手写吗：
学过忘了 - 递归，二分，贪心，回溯，动规，枚举这几种算法学过哪几种：
- LeetCode 大概刷了多少题：
3、框架与中间件
- servlet，cookie，session学过吗：
- SSM学过了吗：
- redis 学过吗：
- SpringBoot项目做过几个：
4、MySQL看的哪些资料：
- sql 熟练吗：
看过一些MySQL入门视频，了解基础 - 索引底层原理懂吗：
5、计算机基础
- 计算机网络看什么资料：
- 操作系统看什么资料：
- 计算机组成原来看的什么资料：
学习规划（2022.3.22）
你这个的话，在我的课程体系里，相当于是懂一点 Java 基础的小白了，从找工作的层面看，需要学习的东西还挺多的，不过时间也是很充足的吧，加上有学历优势，感觉把基础打扎实，后面就是 offer 收割机，所以我们的前期计划是打基础，学习数据结构、算法 + 深入理解一门语言特性。安排如下
1、学习 数据结构与算法，这门课讲的很详细，学完数据结构各类问题基本搞定，不过老师是使用 Java 来实现的，如果你遇到不大懂的，可以去 Java基础 或者 Java进阶 这里补一下对应的知识。
2、学完之后可以学习 算法面试专题，学这个主要是理解一些常见的算法思想了，学习的过程中，一边刷题吧，比如学习链表，那就刷量链表对应的题，专题分类刷，你可以在 Leetcode 刷，也可以在 算法高频题库 刷。
3、学习数据结构和算法的过程中，如果觉得一直学一门课无聊，那么可以一边学习 Java 的课程，有 Java基础 和 Java进阶 两个推荐视频，你看看哪里还没学过的，就从哪里看吧，如果你觉得自己 Java 学的很不扎实，可以从 23节的对象开始学，这门课老师讲的非常详细和深入，另外学习的过程中，也推荐看下 《Java编程思想》 这本书。
也就是说，「1，2」和「3」可以并行学，看你个人习惯，我们的目标是参加 23 年的春招暑假实习，你的学习重点是算法这块。
所有课程入口看这里：所有课程大纲入口
你先学，我不安排太多，后面看你的学习情况再给你推荐需要学习的东西了，然后你有什么疑惑可以随时找我，也记得每周来跟新下学习进度
每周学习跟进
第一周：3.23-3.27
数据结构与算法：
1.线性查找：最简单的查找方式，通过对数组的遍历来查找目标元素target
2.选择排序：最简单的排序算法，基本思想是对数组中n个数据元素查找出最小的数据元素，将它放到数组的第一个位置，接下来从n-1个数据元素中找出最小的数据元素，将它放到数组的第二个位置，依次类推，直到遍历完整个数组中的元素。
3.插入排序：基本思想是从数组初始索引开始，将当前索引的数据元素依次和之前的数据元素进行比较，当前数据元素小于前面的数据元素，则元素互换位置；直到遍历完整个数组。
插入排序与选择排序比较：两者的循环不变量相同，即前i个数据元素都是排好序的，但对于选择排序来说，前i个排好序的数据元素的位置就是最后整个数组排好序的位置，而对于选择排序来说，每进行一次排序，前i的元素的位置一般都会发生改变。
4.数组：一种基本的线性数据结构，数据集合：data；操作集合：增删改查。针对于动态数组，其本质上还是静态的，是通过resize方法在底层实现对数组的扩容或压缩。
5.栈：也是一种线性数据结构，遵循后进先出（LIFO）的原则，即只能从栈顶插入（push）元素和从栈顶删除（pop）元素。其操作集合为数组的操作集合的一部分。
6.队列：也是一种线性数据结构，遵循先进先出（FIFO）的原则，即从队尾插入元素，从队头删除元素。其操作集合为数组操作集合的一部分。用数组实现队列，会产生假溢出现象（在队尾中添加若干个数据元素，再从队头删除若干元素，此时队头索引不为0，若队尾达到索引最大值，无法再添加元素，但事实上队头之前还有存储空间）。可以通过循环队列解决假溢出的情况。但此时应注意空队列和满队列的判断条件。
7.链表：一种线性数据结构，链表中的元素由一个一个的结点组成，结点又包含数据元素data和指向下一结点的指针next（对象引用）组成。当指向下一结点的指针next=null时，链表结束。链表的插入：新结点newNode，插入位置的前一个结点prev，过程：newNode.next = prev.next，prev.next = newNode。删除：删除结点的前一结点prev，过程：prev.next = prev.next.next。（当然对于特殊结点比如头结点或特殊情况需另外考虑）
链表与递归：链表可以看成是一个结点加上另一个少一个结点的链表，类似于递归，递归的本质的子函数的调用，将一个问题转化为更小的问题。
第二周：3.28-4.3
数据结构与算法：
继续上周的学习，学习了归并排序、插入排序两种分治排序算法，两种排序算法都是基于递归算法来实现的，同时两种算法的时间复杂度为0(nlogn)。接下来还学习了二分查找算法，二分查找是对有序数组进行查找，其时间复杂度为0(logn)级别。由二分查找之后学习了二叉树这种数据结构，并对二叉树进行了增删改查和遍历操作的实现，对于二叉树来说，删除结点稍微困难一些，二叉树的遍历方法分为前序遍历、中序遍历、后序遍历和层序遍历。
Java基础部分：
在学习数据结构与算法的同时，对Java基础进行了查缺补漏，基本上过完了Java基础部分的内容，接下来进行Java进阶部分的学习
第三周：4.4-4.10
这周由于搞了两场活动，然后课程作业也比较多，学习进度受了点影响，这周主要学习了Java进阶部分中的单例模式和包装类的知识，数据结构部分学习了堆和两种排序方法：冒泡排序和希尔排序。
第四周：4.11-4.17
这周学习了Java进阶部分的包装类、String类等的知识，以及异常等重要的知识，
数据结构部分学习了线段树、AVL树、并查集、红黑树和哈希表，将数据结构的第一部分结束了。接下来继续学习Java进阶部分的内容，同时对数据结构进行总结梳理，复习回顾，另外刷一些题来巩固。
第五周：4.18-4.24
这周学习了Java中HashMap等相关的底层源码，关于集合中的框架知识，还有泛型。数据结构这一块没有进行下一步的学习，这周主要在复习学过的数据结构和排序算法，手撕代码实现相关的数据结构和排序算法。
第六周：4.25-4.29
这周没有学习很多东西，主要是学习了Java中多线程的知识点，然后根据地哥在知识星球上的Java虚拟机学习方法看了一章的《深入理解Java虚拟机》这本书。数据结构方面自己实现了一下各种排序算法，然后二叉树和链表这两种数据结构，同时在leetcode上面刷了一些比较简单的算法题
第七周：5.5-5.8
将IO流部分的Java知识点学完了，IO流主要的知识点有File及相关的操作，InputStream、OutputStream、Reader和Writer这四大输入输出流，重要的是他们的子类的特点和应用场合
第八周：5.9-5.15
准备期末考试
第九周：5.16-5.22
准备期末考试
第十周：5.23-5.29
打卡学习《深入理解Java虚拟机》，虚拟机字节码执行引擎和Java虚拟机内存区域和内存溢出。
第十一周：5.30-6.5
61.旋转链表：将链表每个结点向右移动k个位置
解题思路：
向右移动k个结点可看作是将倒数k个结点移动到前面，即最后一个结点的下一个结点指针指向原来的头节点，倒数第k个结点作为新的头节点，倒数第k+1哥结点的下一个结点指针指向空。
但事实上k可能大于链表的长度，因此实际上的倒数k个结点应该是k对链表的长度取模：
k = k % size;//size是链表的长度
为了方便，可以对链表设立一个虚拟头节点
ListNode dummyHead = new ListNode(0);
dummyHead.next = head;
接下来的步骤为：
1.首先遍历链表得到链表的总长度
while (cur.next != null) {
size++;
cur = cur.next;
}
2.再次遍历链表找到倒数第k+1的结点的位置，采用双指针的方式
k = k % size;
ListNode p = dummyHead;
ListNode q = dummyHead;
for (int i = 0; i < k; i++) {
q = q.next;
}
while (q.next != null) {
p = p.next;
q = q.next;
}
3.最后一个结点指向原头节点，倒数第k+1个结点指向空
q.next = head;
ListNode temp = p.next;
p.next = null;
return temp;
237.删除链表中的结点：删除单链表中某个特定的结点
解题思路：
由于不能得到指定结点的上一个结点的位置，故可先将该指定结点的下一个结点的val复制到当前结点，然后转化为删除当前结点的下一个结点。
步骤：
1.复制下一个结点的值
node.val = node.next.val;
2.删除下一个节点
node.next = node.next.next;
143.重排链表：
原始链表：
L0->L1->...->Ln-1->Ln
重新排列后：
L0->Ln->L1->Ln-1->L2->ln-2->...
解题思路：
根据题目的表达，第一个结点和最后一个结点相连，以此类推，可以将原始链表一分为二，前半部分保持不变，后半部分进行链表反转，然后根据规律进行链表的重排，因此关键要找到分割两部分链表的中间结点，而中间结点的位置与链表结点个数的奇偶有关，这时还需要对链表节点个数的奇偶性分情况讨论。中间结点的确定可以采用快慢指针的方式一次遍历链表确定。
步骤：
1.找到链表的中间结点(快慢指针)：
ListNode p = head;//慢指针
ListNode q = head;//快指针
//快指针到达尾部时，慢指针到达链表中间
while (q.next != null || q.next.next != null) {
p = p.next;
q = q.next.next;
}
2.分奇偶讨论
由于q.next null 导致循环结束时：链表节点个数为奇数，循环结束后p指向中间结点，同时也是第一部分链表的最后一个结点；q指向最后一个结点。
//重排链表
if (q.next == null) {
ListNode temp = p.next;
p.next = null;
p = head;
q = reverseListNode(temp);//反转链表
ListNode pnext = p.next;
ListNode qnext = q.next;
while (pnext != null && qnext != null) {
p.next = q;
q.next = pnext;
p = pnext;
q = qnext;
pnext = pnext.next;
qnext = qnext.next;
}
p.next = q;
q.next = pnext;
}
由于q.next.next null 导致循环结束时：链表节点个数为偶数，循环结束后p指向中间结点，同时也是第一部分链表的最后一个结点；q指向倒数第二个结点。
//重排链表
if (q.next == null) {
ListNode temp = p.next;
p.next = null;
p = head;
q = reverseListNode(temp);//反转链表
ListNode pnext = p.next;
ListNode qnext = q.next;
while (pnext != null && qnext != null) {
p.next = q;
q.next = pnext;
p = pnext;
q = qnext;
pnext = pnext.next;
qnext = qnext.next;
}
p.next = q;
}
反转链表：
//反转链表
public static ListNode reverseListNode(ListNode head) {
//当链表为空或者只有一个结点时，不需要进行反转
if (head == null || head.next == null) {
return head;
}
ListNode prev = null;
ListNode curr = head;
ListNode next = curr.next;
while (next != null) {
curr.next = prev;
prev = curr;
curr = next;
next = next.next;
}
curr.next = prev;
return curr;
}
104.二叉树的最大深度：
给定一个二叉树，找出其最大深度。二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
解题思路：
从根结点出发，以root为根的二叉树的最大深度为root的左右子树的最大深度中的最大值加1，因此可以采用递归的方式遍历二叉树。
递归终止条件：
if (root == null) {
return 0;
}
递归过程：
return Math.max(maxDepth(root.left) + 1, maxDepth(root.right) + 1);
111.二叉树的最小深度：
给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
解题思路：
从根结点出发，以root为根的二叉树的最小深度为root的左右子树的最小深度中的最小深度值加1，同样的可以采用递归方式遍历二叉树。
递归终止条件：与最大深度不同，除了结点为空的情况之外，当结点为叶子结点时也需要终止递归。
//结点为空时递归终止
if (root == null) {
return 0;
}
//结点为叶子结点时递归终止
if (root.left == null && root.right == null) {
return 1;
}
递归过程：
//当右子树为空时，递归遍历左子树
if (root.left != null && root.right == null) {
return minDepth(root.left) + 1;
}
//当左子树为空时，递归遍历右子树
if (root.left == null && root.right != null) {
return minDepth(root.right) + 1;
}
//左右子树都不为空时，递归遍历左右子树
return Math.min(minDepth(root.left), minDepth(root.right)) + 1;
226.翻转二叉树：
给你一棵二叉树的根节点 root ，翻转这棵二叉树，并返回其根节点。
解题思路：
从根结点出发，要想翻转整棵二叉树，首先root为根的左右子树进行翻转，因此这又是递归的思想。
递归终止条件：
if (root == null) {
return null;
}
递归过程：
//先定义两个结点，分别代表左子树和右子树
TreeNode leftNode = null;
TreeNode rightNode = null;
//当左子树不为空时，进行翻转
if (root.left != null ) {
leftNode = invertTree(root.left);
}
//当右子树不为空，进行翻转
if (root.right != null) {
rightNode = invertTree(root.right);
}
//交换左右子树
swap(root, leftNode, rightNode);
交换左右孩子函数：
//翻转以root为根结点，leftNode和rightNode为左右孩子的二叉树
private TreeNode swap(TreeNode node, TreeNode leftNode, TreeNode rigthNode) {
node.left = rightNode;
node.right = leftNode;
return node;
}
100.相同的树：
给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
解题思路：
同步遍历两棵二叉树，当p和q都为空时，则他们应该是相同的，当p和q其中有一个不为空时，此时应该他们不相同，当p和q都不为空时，若p的值不等于q的值，则他们也是不相同的。当p和q不为空且他们的值都相同，对他们的左右子树进行判断，当左子树不相同时，直接返回false；左子树相同，判断右子树，不相同返回false，相同则说明遍历完两棵二叉树，没有找到不相同的结点，则返回true。
完整代码：
public boolean isSameTree(TreeNode p, TreeNode q) {
//p和q都为空时，返回true
if (p == null && q == null) {
return true;
}
//当p和q当中有一个不为空，返回false
if (p == null || q == null) {
return false;
}
//当p和q都不为空，且p和q的值不相同时，返回false
if (p != null && q != null && p.val != q.val) {
return false;
}
//判断左子树是否相同
if (!isSameTree(p.left, q.left)) {
return false;
}
//判断右子树是否相同
if (!isSameTree(p.right, q.right)) {
return false;
}
//遍历完两棵二叉树，没有找到不同的结点
return true;
}
150.逆波兰表达式求值：tokens = [“2″,”1″,”+”,”3″,”*”]；该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9。
解题思路：
对tokens字符串数组进行遍历，当数组中的元素为数字字符串时，建立一个栈用来存储这些元素，当遇到运算符时，从栈顶出栈两个元素进行运算符的运算，再将结果入栈，直到将整个字符串数组遍历完毕。
完整代码：
public int evalRPN(String[] tokens) {
Stack<Integer> stack = new Stack<>();//整型栈存储数字字符串
int count = 0;//记录运算结果的中间变量
int j = 0, k = 0;//用来暂存两个栈顶元素
for (int i = 0; i < tokens.length; i++) {
count = 0;
switch(tokens[i]) {
case "+":
k = stack.pop();
j = stack.pop();
count = j + k;
stack.push(count);
break;
case "-":
k = stack.pop();
j = stack.pop();
count = j - k;
stack.push(count);
break;
case "*":
k = stack.pop();
j = stack.pop();
count = j * k;
stack.push(count);
break;
case "/":
k = stack.pop();
j = stack.pop();
count = j / k;
stack.push(count);
break;
default:
stack.push(Integer.parseInt(tokens[i]));
break;
}
}
return stack.peek();//返回最终的栈顶元素，即为运算结果
}
20.有效的括号：左括号必须用相同类型的右括号闭合；左括号必须以正确的顺序闭合。
解题思路：建立一个栈，遍历整个字符串s，当遇到左括号类型就将该括号进行入栈，当遇到右括号时，就从栈中取出栈顶元素，判断是否满足括号匹配的要求，直到遍历完整个字符串s，所有的括号都匹配成功且遍历结束后栈中元素为空时该字符串有效。
完整代码：
public boolean isValid(String s) {
//创建一个辅助栈来存储左括号
Stack<Character> stack = new Stack<>();
//遍历字符串
for (int i = 0; i < s.length(); i++) {
//遇到左括号入栈
if (s.charAt(i) == '(' || s.charAt(i) == '[' || s.cahrAt(i) == '{') {
stack.push(s.charAt(i));
} else if (s.charAt(i) == ')') {//遇到右括号
if (stack.size() == 0 || stack.pop() != '(') {
//字符串的首字符为右括号或者出栈括号不匹配时，括号匹配失败
return false;
}
} else if (s.charAt(i) == ']') {
if (stack.size() == 0 || stack.pop() != '[') {
return false;
}
} else if(s.charAt(i) == '}') {
if (stack.size() == 0 || stack.pop() != '{') {
return false;
}
}
}
//遍历结束后，判断栈是否为空
if (stack.size() != 0) {
return false;
} else {
return true;
}
}
剑指offer 09.用两个栈实现队列:用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
解题思路：
建立两个栈，其中一个栈负责入栈操作，用于存储数据元素，另一个栈负责出栈，出栈的同时满足队列的先进先出的原则。
步骤：
1.栈申明：
Deque<Integer> inStack = new LinkedList<>();//入栈
Deque<Integer> outStack = new LinkedList<>();//出栈
2.入队操作:等同于入栈操作
public void appendTail(int value) {
inStack.push(value);
}
3.出栈操作：将入栈遍历复制到出栈中，然后对出栈进行出栈操作
public int deleteHead() {
//将inStack中的元素复制到outStack中
while (inStack.size() != 0) {
outStack.push(inStack.pop());
}
if (outStack.size() == 0) {
return -1;
} else {
return outStack.pop();
}
}
剑指offer 30.包含min函数的栈：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
解题思路：
其余的操作和普通栈相同，关键是要实现min操作，可以利用辅助栈，将最小值存储在辅助栈中，每次入栈都是对最小值进行入栈。
完整代码：
class MinStack {
Deque<Integer> stack;//主栈，用于存储数据
Deque<Integer> minStack;//辅助栈，用于存储最小值
//初始化
public MinStack() {
stack = new LinkedList<>();
minStack = new LinkedList<>();
}
//入栈操作
public void push(int x) {
if (stack.size() == 0) {//空栈直接入栈
stack.push(x);
minStack.push(x);
} else {//将最小值入栈
stack.push(x);
minStack.push(Math.min(minStack.peek(), x));
}
}
//出栈操作
public void pop() {
stack.pop();
minStack.pop();
}
//取栈顶元素
public int top() {
return stack.peek();
}
//栈中最小值
public int min() {
return minStack.peek();
}
}
剑指offer 35.复杂链表的复制：请实现 copyRandomList 函数，复制一个复杂链表。在复杂链表中，每个节点除了有一个 next 指针指向下一个节点，还有一个 random 指针指向链表中的任意节点或者 null。
解题思路：
方法一：
暴力解法：每个结点含有两个属性，next和random，抛开random来讲就是普通链表的复制，我们可以先对next属性进行复制，从而得到普通的链表，然后根据原始的链表在复制链表中添加random属性，实现想法是从原始链表中获取当前结点random属性的结点的索引，这个索引在复制链表中也是成立的，所以可以在复制链表中找到该结点，所以复制链表中的当前结点的random属性就可以确定。
步骤：
1.复制next：
Node newHead = new Node(head.val);
Node curr = head;
Node newCurr = newHead;
while (curr.next != null) {
curr = curr.next;
Node newNode = new Node(curr.val);
newCurr.next = newNode;
newCurr = newCurr.next;
}
2.复制random：
在原始链表由结点找到索引：
private int nodeToIndex(Node node, Node head) {
int index = 0;
Node curr = head;
while (curr != null) {
if (curr == node) {
return ++index;
}
curr = curr.next;
index++;
}
return index + 1;
}
在复制链表中由索引找到结点：
private Node indexToNode(int index, Node head) {
Node curr = head;
for (int i = 1; i < index; i++) {
curr = curr.next;
}
return curr;
}
复制random
curr = head;
newCurr = newHead;
while (curr != null) {
int index = nodeToIndex(curr.random, head);
Node random = indexToNode(index, newHead);
newCurr.random = random;
}
return newHead;
剑指offer 06.从尾到头打印链表：输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
解题思路：
方法一：
首先遍历一遍链表，得到链表的总长度，然后创建一个相同大小的数组，再次遍历链表，将节点的值从尾到头的存储到数组中。
完整代码：
public int[] reversePrint(ListNode head) {
ListNode curr = head;
int size = 0;//记录链表的大小
while (curr != null) {
size++;
curr = curr.next;
}
//创建相同大小的数组
int[] node = new int[size];
curr = head;
for (int i = size - 1; curr != null; i--) {
node[i] = curr.val;
curr = curr.next;
}
return node;
}
方法二：
建立一个栈，遍历链表，将每个结点的值压入栈中，然后建立一个数组，将出栈的元素一次添加到数组中。
完整代码:
public int[] reversePrint(ListNode head) {
ListNode curr = head;
Deque<Integer> stack = new LinkedList<>();
while (curr != null) {
stack.push(curr.val);
curr = curr.next;
}
int size = stack.size();
int[] node = new int[size];
for (int i = 0; i < size; i++) {
node[i] = stack.pop();
}
return node;
}
剑指offer 11.旋转数组的最小数字
解题思路：
方法一：线性查找
由于数组是有序数组进行旋转得到，设最小值的索引是n，则数组从0到n – 1是递增的，从n到numbers.length – 1是也是递增的，但numbers[n – 1]要大于numbers[n]；根据这个特点我们可以遍历数组，用一个中间变量temp存储上一个数组中的元素，若当前元素的值大于等于temp的值，则将temp的值变换为当前元素的值，否则我们找到一个突变点，该突变点就是最小值，直接返回就可以了，若遍历整个数组都没有找到突变点，则数组中的第一个元素就是最小值。
完整代码：
public int minArray(int[] numbers) {
int temp = numbers[0];
for (int i = 1; i < numbers.length; i++) {
if (numbers[i] >= temp) {
temp = numbers[i];
} else {
return numbers[i];
}
}
return numbers[0];
}
方法二：二分查找
我们考虑数组中的最后一个元素x：在最小值右侧的元素，他们的值一定都小于等于x；而在最小值左侧的元素，他们的值一定都大于等于x。
在二分查找的每一步中，左边界为low，右边界为high，区间的中点为pivot，最小值就在该区间内。我们将中轴元素与右边界元素进行比较，可能得到以下的三种情况：
第一种情况：numbers[pivot] numbers[high]。说明numbers[pivot]是最小值左侧的元素，因此我们可以忽略二分查找区间的左半部分；
第三种情况：numbers[pivot] numbers[high]。由于重复元素的存在，所以不能判断最小值到底位于numbers[pivot]的左侧还是右侧，但是可以将high的下标缩减1得到新的pivot，然后进行判断。
完整代码：
public int minArray(int[] numbers) {
int low = 0;
int high = numbers.length - 1;
while (low < high) {
int pivot = low + (high - low) / 2;
if (numbers[pivot] < numbers[high]) {
high = pivot;
} else if (numbers[pivot] > numbers[high]) {
low = pivot + 1;
} else {
high -= 1;
}
}
return numbers[low];
}
第十二周6.6-6.12
剑指offer 10-1.斐波那契数列
解题思路：
F(0) = 0, F(1) = 1, F(N) = F(N – 1) + F(N – 2)
对两种特例情况进行单独处理，然后利用滚动数组进行循环遍历，得到n时的斐波那契数列值。p和q储存前两个值，r储存当前的斐波那契值。
public int fib(int n) {
//当 n < 2时，返回 n
if (n < 2) {
return n;
}
//p和q储存前两个值，r储存当前的斐波那契值
int p = 0;
int q = 0;
int r = 1;
int MOD = 1000000007;
for (int i = 2; i <= n; i++) {
p = q;
q = r;
r = (p + q) % MOD;
}
return r;
}
剑指offer 10-2.青蛙跳台阶问题
解题思路：
状态定义：numWays(i) 表示到达第i阶台阶的方式总数
状态转移方程：numWays(i) = numWays(i – 1) + numWays(i – 2)
对于i = 0和i = 1两种特例情况单独处理
public int numWays(int n) {
//当 n < 2时，返回 1
if (n < 2) {
return 1;
}
//p和q储存前两个值，r储存当前的斐波那契值
int p = 1;
int q = 1;
int r = 0;
int MOD = 1000000007;
for (int i = 2; i <= n; i++) {
r = (p + q) % MOD;
p = q;
q = r;
}
return r;
}
剑指offer 63.股票的最大利润
解题思路：
状态定义：maxProfit(i)表示从前i天最低价买进，第i天卖出的利润
状态转移方程：maxProfit(i) = max(maxProfit(i), prices[i] – minPoint)
public int maxProfit(int[] prices) {
//当价格数组长度小于1时，不可能有收益，即收益为0
if (prices.length <= 1) {
return 0;
}
int minPoint = prices[0];
int maxProfit = 0;
for (int i = 1; i < prices.length; i++) {
maxProfit = Math.max(maxProfit, prices[i] - minPoint);
minPoint = Math.min(minPoint, prices[i]);
}
return maxProfit;
}
剑指offer 47.连续子数组的最大和
解题思路：
状态定义：maxSubString(i) 表示到达下标i的所有连续子数组的和的最大值
状态转移方程：maxSubString(i) = max(maxSubString(i – 1) + nums[i], nums[i])
public int maxSubString(int[] nums) {
if (nums.length == 0) {
return 0;
}
if (nums.length == 1) {
return nums[0];
}
int pre = nums[0];
int maxSubString = pre;
int result = pre;
for (int i = 1; i < nums.length; i++) {
maxSubString = Math.max(pre + nums[i], nums[i]);
result = Math.max(result, maSubString);
pre = maxSubString;
}
return result;
}
剑指offer 42.礼物的最大价值
解题思路：
状态定义：maxValue[i] [j]表示到达第i行第j列包含礼物的最大值
状态转移方程：maxValue[i] [j] = max(maxValue[i – 1] [j], maxValue[i] [j – 1]) + grid[i] [j]
public int maxValue(int[][] grid) {
//当数组为空时，返回0
if (grid.length == 0 || grid[0].length == 0) {
return 0;
}
int row = grid.length;//数组的行数
int column = grid[0].length;//数组的列数
//由于数组不能越界，故可以先将上边和左边的先确定下来
for (int c = 1; c < column; c++) {
grid[0][c] += grid[0][c - 1];
}
for (int r = 1; r < row; r++) {
grid[r][0] += grid[r - 1][0];
}
//剩下满足状态转移方程
for (int r = 1; r < row; r++) {
for (int c = 1; c < column; c++) {
grid[r][c] = Math.max(grid[r - 1][c], grid[r][c - 1]) + grid[r][c];
}
}
return grid[row - 1][column - 1];
}
7-8-9月
暑假这段时间主要是在公司里面进行学习，熟悉公司项目中的框架和业务逻辑，也做了一些简单的需求，比如说字段的增删改查，需求相对来说比较简单。也利用这段时间接触了部分的实际项目代码，之前系统学习过框架，也在这段时间中了解了Spring Boot、MyBatis框架等，还有包括一些中间件技术：Redis、RabbitMQ和Elasticsearch；但是也只是停留在了解阶段。
暑假结束后，将Spring、Spring MVC和MyBatis框架进行了系统的学习，就是跟着网站里面的视频进行学习，然后利用SSM框架跟着老师做了慕课书评网的项目，做项目时也接触了一下MyBatis-Plus，掌握了其基本使用方法和常用的注解。
接下来学习了Spring Boot的知识，由于网站里面的Spring Boot好像太简单了，所以我是在B站跟着其他老师学习的，Spring Boot里面原理部分中Spring Boot的自动装配原理是核心，这里可以和Spring进行一个比较。对于开发部分就是Spring Boot和一些中间件和插件的整合了，学习了Spring Boot整合druid数据连接池，Thymeleaf模板引擎，MyBatis和Swagger，学习的过程中记录了这些笔记。
好像不知道怎么回事，对登录授权认证比较感兴趣，就是项目的安全方面的管理，找了一些资料学习了Cookie和Session，初步了解Cookie和Session是什么，工作原理，但是Java Web没有学，不知道还有没有其他的一些知识点，然后学习了Shiro安全框架，并利用Spring Boot整合了Shiro框架。
之后就是一些中间件和其他基础知识的学习了，先是将Linux的基础知识学习了一下，包括Linux远程连接、常用的基础命令、文件操作、vim编辑器和安装程序等。之后学习了Redis，刚好学了Linux，在Linux下安装了单机Redis，Redis中主要学习了Redis的数据结构、配置文件、Redis的事务、Redis的客户端jedis；还有Redis的一些底层原理：持久化、发布订阅、主从复制、哨兵、Redis的缓存穿透、缓存雪崩、缓存击穿等。学完Redis后，利用Spring Boot整合Redis。
暑假期间接触的是RabbitMQ，所以选择学习RabbitMQ作为MQ的入门，之后的学习我好像都是跟着其他老师学习的，由于教学中用到了Docker容器技术，学了一下Docker，算是简单入门吧，Docker的操作命令，镜像，容器等基础概念，像Docker的高级技术和原理没学，感觉还用不到，所以就先放一放了。然后使用Docker安装了RabbitMQ。RabbitMQ感觉没怎么学明白，掌握了MQ的基本概念：连接、交换机、信道、队列、绑定，学了MQ的一些工作模式，然后在Spring Boot中整合了RabbitMQ，编写了一些例子和MQ的可视化界面来加深MQ的工作模式，高级部分学习了持久化、发布确认和死信队列；但是感觉有点云里雾里，可能没有具体的例子(项目)，这部分没学好。
接下来学了一下Elasticsearch，在Windows下安装了Elasticsearch，通过kibana对ES进行简单的操作，这部分还没学完，包括在SpringBoot整合ES也还没学习。
第二阶段学习安排（2022.10.15）
你这几个月，接触了不少框架类，中间件类的学习，这些一般都是项目相关，挺好的。不过接下来，你需要多花点时间在八股文这方面，明年暑假找实习的 话，八股文+算法还是比较重要滴。目前你八股文这块，算是刷了 Java进阶 + JVM 的书，不过需要刷的还挺多的，主要是 mysql + redis + 并发 + 计算机网络。具体安排如下：
1、八股文：你先把没刷的过一遍，到时候接近面试的再来复习容易点，把 MySQL原理剖析课程说明刷下，redis 的话，你看书吧，就看《redis设计与实现》，然后也把 Java并发 并发刷一下。具体学习顺序你自己安排吧，没有先后顺序，你应该自己可以安排。
然后你计算机网络还没有学过的话，也是需要刷书的，操作系统则不用。另外你 JVM 倒是好复习的话，只需要看 图解JVM学习指南 就可以了。
2、算法：算法你可以搞个目标，把 算法高频题库 给刷了，如果你要按照某个攻略刷也行，不过刷完记得来刷一刷高频题。
你先把这些过一下，到时候复习在刷 八股文题库(必看)
每周学习跟进
10.15-11.21
这段时间主要是一些理论方面的学习，包括计算机网络方面和redis方面的理论学习。将《图解HTTP》整体学习了一遍，之后通过学习《图解网络》进行计算机网络的系统学习，这部分内容已经过完一大半了，计划是在十一月内将《图解网络》看完一遍，对计算机网络的知识有一个印象和理解。另外这个月同步进行学习《Redis的设计与实现》，将Redis中的对象系统和对象系统的底层实现原理过了一遍，这本书大概看了一半，计划在十一月份将这本书过完一遍。