第 1 天 栈与队列
剑指 Offer 09. 用两个栈实现队列
题目
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
示例 1：
输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]
示例 2：
输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]
解答
成员变量：维护两个栈 stack1 和 stack2，其中 stack1 支持插入操作，stack2 支持删除操作
构造方法：初始化 stack1 和 stack2 为空
插入元素：插入元素对应方法 appendTail，stack1 直接插入元素
删除元素：删除元素对应方法 deleteHead
- 如果 stack2 为空，则将 stack1 里的所有元素弹出插入到 stack2 里
- 如果 stack2 仍为空，则返回 -1，否则从 stack2 弹出一个元素并返回
class CQueue {
//两个栈，一个出栈，一个入栈
Stack<Integer> stack1;
Stack<Integer> stack2;
public CQueue() {
// 初始化栈
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void appendTail(int value) {
stack1.push(value);
}
public int deleteHead() {
if(!stack2.isEmpty()){
return stack2.pop();
}else{
//将s1的所有值放入s2
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
return stack2.isEmpty() ? -1 : stack2.pop();
}
}
}
剑指 Offer 30. 包含min函数的栈
题目
定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的 min 函数在该栈中，调用 min、push 及 pop 的时间复杂度都是 O(1)。
示例:
MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.min(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.min(); --> 返回 -2.
解答
本题难点：将 min() 函数复杂度降为 O(1) ，可通过建立辅助栈实现；设定一个辅助栈，栈顶表示当前数据栈中的最小值，每次有新元素入栈，就将当前最小值入辅助栈。出栈时，辅助栈也要将栈顶元素出栈，这就解决了出栈时的最小值更新问题。
class MinStack {
Stack<Integer> dataStack; // 数据栈
Stack<Integer> minStack; // 辅助栈，记录每次有元素进栈后或者出栈后，元素的最小值
public MinStack() {
// 初始化辅助栈和数据栈
dataStack = new Stack<>();
minStack = new Stack<>();
}
public void push(int x) {
dataStack.push(x);// 数据栈，进栈
// 如果辅助栈为空，或者辅助栈栈顶 > x，则将 x 设置为最小值，即进辅助栈
if(minStack.isEmpty() || minStack.peek() > x){
minStack.push(x);
}else{// 如果辅助栈栈顶 < x, 则继续将上次的最小值再入一次辅助栈
minStack.push(minStack.peek());
}
}
public void pop() {
minStack.pop();// 辅助栈，出栈
dataStack.pop();// 数据栈，出栈
}
public int top() {
return dataStack.peek();
}
public int min() {
return minStack.peek();
}
}
第 2 天 链表
剑指 Offer 06. 从尾到头打印链表
题目
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：
输入：head = [1,3,2]
输出：[2,3,1]
解答
栈的特点是后进先出，考虑到栈的这一特点，使用栈将链表元素顺序倒置。
创建一个栈，将链表的节点都压入该栈，获得栈的大小 size，创建一个数组 out，其大小为 size，从栈内弹出一个节点，将该节点的值存到 out 当中，最后返回 out 。
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public int[] reversePrint(ListNode head) {
Stack<ListNode> stack = new Stack<ListNode>();
while(head != null){
stack.push(head);
head = head.next;
}
int size = stack.size();
int []out = new int[size] ;
for(int i = 0; i < size; i++){
out[i] = stack.pop().val;
}
return out;
}
}
剑指 Offer 24. 反转链表
题目
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL
解答
方法1(迭代)：
定义两个指针 pre 和 cur ，在遍历链表时，将当前节点(cur)的 next 指针改为指向前一个节点(pre)，完成一次局部反转。指向前一个节点后，与后一节点的联系就断了，因此在更改引用之前，还需要存储后一个节点(temp)。然后 pre 和 cur 同时往前移动一个位置。最后返回新的头引用。
class Solution {
public ListNode reverseList(ListNode head) {
ListNode pre = null, cur = head;
while(cur != null) {
ListNode temp = cur.next;// 暂存后继节点 cur.next
cur.next = pre;// 修改 next 引用指向
pre = cur;// pre 暂存 cur，即 pre 移动到下一个节点
cur = temp; // cur 访问下一节点
}
return pre;
}
}
方法2(递归)：这个方法我也没看懂，后面再填坑！！！
class Solution {
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null) {
return head;
}
ListNode rehead = reverseList(head.next);
head.next.next = head;
head.next = null;
return rehead;
}
}
第 3 天 字符串
剑指 Offer 05. 替换空格
题目
请实现一个函数，把字符串 s 中的每个空格替换成”%20”。
示例 1：
输入：s = "We are happy."
输出："We%20are%20happy."
解答
class Solution {
public String replaceSpace(String s) {
StringBuilder res = new StringBuilder();
for(int i = 0 ; i < s.length(); i++){
if(s.charAt(i) == ' '){
res.append("%20");
}else{
res.append(s.charAt(i));
}
}
return res.toString();
}
}
剑指 Offer 58 - II. 左旋转字符串
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。请定义一个函数实现字符串左旋转操作的功能。比如，输入字符串”abcdefg”和数字2，该函数将返回左旋转两位得到的结果”cdefgab”。
示例 1：
输入: s = "abcdefg", k = 2
输出: "cdefgab"
示例 2：
输入: s = "lrloseumgh", k = 6
输出: "umghlrlose"
解答
方法1(切片)：
class Solution {
public String reverseLeftWords(String s, int n) {
return s.substring(n, s.length()) + s.substring(0, n);
}
}
方法2(遍历)：
class Solution {
public String reverseLeftWords(String s, int n) {
StringBuilder res = new StringBuilder();
for(int i = n; i< s.length(); i++){
res.append(s.charAt(i));
}
for(int i = 0; i<n; i++){
res.append(s.charAt(i));
}
return res.toString();
}
}
利用求余运算，简化代码。
class Solution {
public String reverseLeftWords(String s, int n) {
StringBuilder res = new StringBuilder();
for(int i = n; i < n + s.length(); i++)
res.append(s.charAt(i % s.length()));
return res.toString();
}
}
❤️Sponsor
您的支持是我不断前进的动力，如果你觉得本文对你有帮助，你可以请我喝一杯冰可乐！嘻嘻🤭
| 支付宝支付 | 微信支付 |
 |
 |
