Java面试笔记-算法
二叉树的先序、中序和后序遍历 (Easy)
分别按照二叉树先序，中序和后序打印所有的节点。
示例1
输入：{1,2,3}
输出：[[1,2,3],[2,1,3],[2,3,1]]二叉树遍历
- 先序：root -> left -> right
- 中序：left -> root -> right
- 后序：left -> right-> root
import java.util.*;
/*
* public class TreeNode {
* int val = 0;
* TreeNode left = null;
* TreeNode right = null;
* }
*/
public class Solution {
/**
*
* @param root TreeNode类 the root of binary tree
* @return int整型二维数组
*/
public int[][] threeOrders (TreeNode root) {
// write code here
int[][] res = new int[3][getSize(root)];
order(res, root);
return res;
}
int i1 = 0;
int i2 = 0;
int i3 = 0;
public void order(int[][] res, TreeNode root) {
if (root == null) return;
res[0][i1++] = root.val;
order(res, root.left);
res[1][i2++] = root.val;
order(res, root.right);
res[2][i3++] = root.val;
}
public int getSize(TreeNode root) {
if (root == null) return 0;
return 1 + getSize(root.left) + getSize(root.right);
}
}二叉树的层序遍历 (Medium)
给你一个二叉树，请你返回其按 层序遍历 得到的节点值。 （即逐层地，从左到右访问所有节点）。
示例：
二叉树：[3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7 返回其层序遍历结果：
[
[3],
[9,20],
[15,7]
]解题思路
I. 按层打印： 题目要求的二叉树的 从上至下 打印（即按层打印），又称为二叉树的 广度优先搜索（BFS）。BFS 通常借助 队列 的先入先出特性来实现。
II. 每层打印到一行： 将本层全部节点打印到一行，并将下一层全部节点加入队列，以此类推，即可分为多行打印。
算法流程
- 特例处理： 当根节点为空，则返回空列表
[]； - 初始化： 打印结果列表
res = []，包含根节点的队列queue = [root]； - BFS 循环： 当队列
queue为空时跳出；- 新建一个临时列表
tmp，用于存储当前层打印结果； - 当前层打印循环： 循环次数为当前层节点数（即队列
queue长度）；- 出队： 队首元素出队，记为
node； - 打印： 将
node.val添加至tmp尾部； - 添加子节点： 若
node的左（右）子节点不为空，则将左（右）子节点加入队列queue；
- 出队： 队首元素出队，记为
- 将当前层结果
tmp添加入res。
- 新建一个临时列表
- 返回值： 返回打印结果列表
res即可。
复杂度分析
- 时间复杂度 O(N) ： N 为二叉树的节点数量，即 BFS 需循环 N 次。
- 空间复杂度 O(N) ： 最差情况下，即当树为平衡二叉树时，最多有 N/2 个树节点同时在 queue 中，使用
O(N)大小的额外空间。
代码
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> res = new ArrayList<>();
if(root != null) queue.add(root);
while(!queue.isEmpty()) {
List<Integer> tmp = new ArrayList<>();
for(int i = queue.size(); i > 0; i--) {
TreeNode node = queue.poll();
tmp.add(node.val);
if(node.left != null) queue.add(node.left);
if(node.right != null) queue.add(node.right);
}
res.add(tmp);
}
return res;
}
}重建二叉树 (Medium)
输入某二叉树的前序遍历和中序遍历的结果，请重建该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。
例如，给出
前序遍历 preorder = [3,9,20,15,7
中序遍历 inorder = [9,3,15,20,7]返回如下的二叉树：
3
/ \
9 20
/ \
15 7解题思路
前序遍历性质： 节点按照 [ 根节点 | 左子树 | 右子树 ] 排序。
中序遍历性质： 节点按照 [ 左子树 | 根节点 | 右子树 ] 排序。
以题目示例为例：
- 前序遍历划分 [ 3 | 9 | 20 15 7 ]
- 中序遍历划分 [ 9 | 3 | 15 20 7 ]
根据以上性质，可得出以下推论：
- 前序遍历的首元素 为 树的根节点
node的值。 - 在中序遍历中搜索根节点
node的索引 ，可将 中序遍历 划分为[ 左子树 | 根节点 | 右子树 ]。 - 根据中序遍历中的左 / 右子树的节点数量，可将 前序遍历 划分为
[ 根节点 | 左子树 | 右子树 ]。
通过以上三步，可确定 三个节点 ：1.树的根节点、2.左子树根节点、3.右子树根节点。
对于树的左、右子树，仍可使用以上步骤划分子树的左右子树。
以上子树的递推性质是 分治算法 的体现，考虑通过递归对所有子树进行划分。
分治算法解析
递推参数： 根节点在前序遍历的索引
root、子树在中序遍历的左边界left、子树在中序遍历的右边界right；终止条件： 当
left > right，代表已经越过叶节点，此时返回 null ；递推工作：
建立根节点
node： 节点值为preorder[root]；划分左右子树： 查找根节点在中序遍历
inorder中的索引i；
为了提升效率，本文使用哈希表dic存储中序遍历的值与索引的映射，查找操作的时间复杂度为 O(1)构建左右子树： 开启左右子树递归；
根节点索引 中序遍历左边界 中序遍历右边界 左子树 root + 1 left i - 1 右子树 i - left + root + 1 i + 1 right
*`i - left + root + 1`含义为 `根节点索引 + 左子树长度 + 1`*- 返回值： 回溯返回
node，作为上一层递归中根节点的左 / 右子节点；
复杂度分析：
- 时间复杂度 O(N) ： 其中 N 为树的节点数量。初始化 HashMap 需遍历 inorder ，占用O(N) 。递归共建立 N 个节点，每层递归中的节点建立、搜索操作占用 O(1) ，因此使用 O(N) 时间。
- 空间复杂度 O(N) ： HashMap 使用 O(N) 额外空间。最差情况下，树退化为链表，递归深度达到 N ，占用 O(N) 额外空间；最好情况下，树为满二叉树，递归深度为NlogN ，占用O(logN) 额外空间。
代码
注意：本文方法只适用于 “无重复节点值” 的二叉树。
class Solution {
int[] preorder;
HashMap<Integer, Integer> dic = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
this.preorder = preorder;
for(int i = 0; i < inorder.length; i++)
dic.put(inorder[i], i);
return recur(0, 0, inorder.length - 1);
}
TreeNode recur(int root, int left, int right) {
if(left > right) return null; // 递归终止
TreeNode node = new TreeNode(preorder[root]); // 建立根节点
int i = dic.get(preorder[root]); // 划分根节点、左子树、右子树
node.left = recur(root + 1, left, i - 1); // 开启左子树递归
node.right = recur(root + i - left + 1, i + 1, right); // 开启右子树递归
return node; // 回溯返回根节点
}
}二叉树转双向链表 (Medium)
输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的循环双向链表。要求不能创建任何新的节点，只能调整树中节点指针的指向。
为了让您更好地理解问题，以下面的二叉搜索树为例：
我们希望将这个二叉搜索树转化为双向循环链表。链表中的每个节点都有一个前驱和后继指针。对于双向循环链表，第一个节点的前驱是最后一个节点，最后一个节点的后继是第一个节点。
下图展示了上面的二叉搜索树转化成的链表。“head” 表示指向链表中有最小元素的节点。
特别地，我们希望可以就地完成转换操作。当转化完成以后，树中节点的左指针需要指向前驱，树中节点的右指针需要指向后继。还需要返回链表中的第一个节点的指针。
解题思路
本文解法基于性质：二叉搜索树的中序遍历为 递增序列 。
将 二叉搜索树 转换成一个 “排序的循环双向链表” ，其中包含三个要素：
- 排序链表： 节点应从小到大排序，因此应使用 中序遍历 “从小到大”访问树的节点。
- 双向链表： 在构建相邻节点的引用关系时，设前驱节点
pre和当前节点cur，不仅应构建pre.right = cur，也应构建cur.left = pre。 - 循环链表： 设链表头节点
head和尾节点tail，则应构建head.left = tail和tail.right = head。
中序遍历 为对二叉树作 “左、根、右” 顺序遍历，递归实现如下：
// 打印中序遍历
void dfs(Node root) {
if(root == null) return;
dfs(root.left); // 左
System.out.println(root.val); // 根
dfs(root.right); // 右
}根据以上分析，考虑使用中序遍历访问树的各节点 cur ；并在访问每个节点时构建 cur 和前驱节点 pre 的引用指向；中序遍历完成后，最后构建头节点和尾节点的引用指向即可。
算法流程
dfs(cur): 递归法中序遍历；
终止条件： 当节点
cur为空，代表越过叶节点，直接返回；递归左子树，即
dfs(cur.left)；构建链表：
- 当
pre为空时： 代表正在访问链表头节点，记为head； - 当
pre不为空时： 修改双向节点引用，即pre.right = cur，cur.left = pre； - 保存
cur： 更新pre = cur，即节点cur是后继节点的pre；
- 当
递归右子树，即
dfs(cur.right)；
treeToDoublyList(root)：
- 特例处理： 若节点
root为空，则直接返回； - 初始化： 空节点
pre； - 转化为双向链表： 调用
dfs(root)； - 构建循环链表： 中序遍历完成后，
head指向头节点，pre指向尾节点，因此修改head和pre的双向节点引用即可； - 返回值： 返回链表的头节点
head即可；
复杂度分析：
- 时间复杂度 O(N) ： N 为二叉树的节点数，中序遍历需要访问所有节点。
- 空间复杂度 O(N) ： 最差情况下，即树退化为链表时，递归深度达到 N，系统使用 O(N) 栈空间。
class Solution {
Node pre, head;
public Node treeToDoublyList(Node root) {
if(root == null) return null;
dfs(root);
head.left = pre;
pre.right = head;
return head;
}
void dfs(Node cur) {
if(cur == null) return;
dfs(cur.left);
if(pre != null) pre.right = cur;
else head = cur;
cur.left = pre;
pre = cur;
dfs(cur.right);
}
}反转链表 (Easy)
定义一个函数，输入一个链表的头节点，反转该链表并输出反转后链表的头节点。
示例:
输入: 1->2->3->4->5->NULL
输出: 5->4->3->2->1->NULL限制：
0 <= 节点个数 <= 5000解法一 栈
最简单的一种方式就是使用栈，因为栈是先进后出的。实现原理就是把链表节点一个个入栈，当全部入栈完之后再一个个出栈，出栈的时候在把出栈的结点串成一个新的链表。原理如下
class Solution {
public ListNode reverseList(ListNode head) {
Stack<ListNode> stack = new Stack<>();
//把链表节点全部摘掉放到栈中
while (head != null) {
stack.push(head);
head = head.next;
}
if (stack.isEmpty())
return null;
ListNode node = stack.pop();
ListNode dummy = node;
//栈中的结点全部出栈，然后重新连成一个新的链表
while (!stack.isEmpty()) {
ListNode tempNode = stack.pop();
node.next = tempNode;
node = node.next;
}
//最后一个结点就是反转前的头结点，一定要让他的next
//等于空，否则会构成环
node.next = null;
return dummy;
}
}解法二 双指针迭代
我们可以申请两个指针，第一个指针叫 pre，最初是指向 null 的。
第二个指针 cur 指向 head，然后不断遍历 cur。
每次迭代到 cur，都将 cur 的 next 指向 pre，然后 pre 和 cur 前进一位。
都迭代完了(cur 变成 null 了)，pre 就是最后一个节点了。
动画演示如下：
class Solution {
public ListNode reverseList(ListNode head) {
//申请节点，pre和 cur，pre指向null
ListNode pre = null;
ListNode cur = head;
ListNode tmp = null;
while(cur!=null) {
//记录当前节点的下一个节点
tmp = cur.next;
//然后将当前节点指向pre
cur.next = pre;
//pre和cur节点都前进一位
pre = cur;
cur = tmp;
}
return pre;
}
}解法三 递归
递归的两个条件：
终止条件是当前节点或者下一个节点==null
在函数内部，改变节点的指向，也就是 head 的下一个节点指向 head 递归函数那句
head.next.next = head
很不好理解，其实就是 head 的下一个节点指向head。
递归函数中每次返回的 cur 其实只最后一个节点，在递归函数内部，改变的是当前节点的指向。
动画演示如下：
class Solution {
public ListNode reverseList(ListNode head) {
//递归终止条件是当前为空，或者下一个节点为空
if(head==null || head.next==null) {
return head;
}
//这里的cur就是最后一个节点
ListNode cur = reverseList(head.next);
//这里请配合动画演示理解
//如果链表是 1->2->3->4->5，那么此时的cur就是5
//而head是4，head的下一个是5，下下一个是空
//所以head.next.next 就是5->4
head.next.next = head;
//防止链表循环，需要将head.next设置为空
head.next = null;
//每层递归函数都返回cur，也就是最后一个节点
return cur;
}
}合并两个有序的链表 (Easy)
输入两个递增排序的链表，合并这两个链表并使新链表中的节点仍然是递增排序的。
示例1：
输入：1->2->4, 1->3->4
输出：1->1->2->3->4->4解题思路
根据题目描述， 链表 l1 , l2 是
递增的，因此容易想到使用双指针 l1 和 l2 遍历两链表，根据 l1 .val 和 l2 .val 的大小关系确定节点添加顺序，两节点指针交替前进，直至遍历完毕。引入伪头节点： 由于初始状态合并链表中无节点，因此循环第一轮时无法将节点添加到合并链表中。
解决方案：初始化一个辅助节点
dum作为合并链表的伪头节点，将各节点添加至dum之后。
算法流程
- 初始化： 伪头节点
dum，节点cur指向dum。 - 循环合并： 当 l1 或 l2 为空时跳出；
- 当
l1.val<l2.val时：cur的后继节点指定为 l1，并 l1 向前走一步； - 当
l1.val≥l2.val时：cur的后继节点指定为 l2 ，并 l2 向前走一步 ； - 节点
cur向前走一步，即cur = cur.next。
- 当
- 合并剩余尾部： 跳出时有两种情况，即 l1 为空 或 l2 为空。
- 若 l1$\neq$null ： 将 l1 添加至节点
cur之后 - 否则： 将 l2 添加至节点
cur之后。
- 若 l1$\neq$null ： 将 l1 添加至节点
- 返回值： 合并链表在伪头节点
dum之后，因此返回dum.next即可。
复杂度分析
- 时间复杂度 O(M+N) ： M, N 分别为链表 l1 , l2 的长度，合并操作需遍历两链表。
- 空间复杂度 O(1) ： 节点引用 dum , cur 使用常数大小的额外空间。
代码
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode dum = new ListNode(0), cur = dum;
while(l1 != null && l2 != null) {
if(l1.val < l2.val) {
cur.next = l1;
l1 = l1.next;
}
else {
cur.next = l2;
l2 = l2.next;
}
cur = cur.next;
}
cur.next = l1 != null ? l1 : l2;
return dum.next;
}
}#
最长回文子串 (Medium)
给你一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入：s = "babad"
输出："bab"
解释："aba" 同样是符合题意的答案。示例 2：
输入：s = "cbbd"
输出："bb"示例 3：
输入：s = "a"
输出："a"示例 4：
输入：s = "ac"
输出："a"提示：
1 <= s.length <= 1000s仅由数字和英文字母（大写和/或小写）组成
方法一：暴力匹配 （Brute Force）
- 根据回文子串的定义，枚举所有长度大于等于 22 的子串，依次判断它们是否是回文；
- 在具体实现时，可以只针对大于“当前得到的最长回文子串长度”的子串进行“回文验证”；
- 在记录最长回文子串的时候，可以只记录“当前子串的起始位置”和“子串长度”，不必做截取。这一步我们放在后面的方法中实现。
说明：暴力解法时间复杂度高，但是思路清晰、编写简单。由于编写正确性的可能性很大，可以使用暴力匹配算法检验我们编写的其它算法是否正确。优化的解法在很多时候，是基于“暴力解法”，以空间换时间得到的，因此思考清楚暴力解法，分析其缺点，很多时候能为我们打开思路。
public class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2) {
return s;
}
int maxLen = 1;
int begin = 0;
// s.charAt(i) 每次都会检查数组下标越界，因此先转换成字符数组
char[] charArray = s.toCharArray();
// 枚举所有长度大于 1 的子串 charArray[i..j]
for (int i = 0; i < len - 1; i++) {
for (int j = i + 1; j < len; j++) {
if (j - i + 1 > maxLen && validPalindromic(charArray, i, j)) {
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substring(begin, begin + maxLen);
}
/**
* 验证子串 s[left..right] 是否为回文串
*/
private boolean validPalindromic(char[] charArray, int left, int right) {
while (left < right) {
if (charArray[left] != charArray[right]) {
return false;
}
left++;
right--;
}
return true;
}
}复杂度分析：
- 时间复杂度：O(N3)，这里 N 是字符串的长度，枚举字符串的左边界、右边界，然后继续验证子串是否是回文子串，这三种操作都与 N 相关；
- 空间复杂度：O(1)，只使用到常数个临时变量，与字符串长度无关。
方法二：动态规划
事实上，「回文」天然具有「状态转移」性质。
- 一个回文去掉两头以后，剩下的部分依然是回文（这里暂不讨论边界情况）；
依然从回文串的定义展开讨论：
- 如果一个字符串的头尾两个字符都不相等，那么这个字符串一定不是回文串；
- 如果一个字符串的头尾两个字符相等，才有必要继续判断下去。
- 如果里面的子串是回文，整体就是回文串；
- 如果里面的子串不是回文串，整体就不是回文串。
即：在头尾字符相等的情况下，里面子串的回文性质据定了整个子串的回文性质，这就是状态转移。因此可以把「状态」定义为原字符串的一个子串是否为回文子串。
第 1 步：定义状态
dp[i][j] 表示子串 s[i..j] 是否为回文子串，这里子串 s[i..j] 定义为左闭右闭区间，可以取到 s[i] 和 s[j]。
第 2 步：思考状态转移方程
在这一步分类讨论（根据头尾字符是否相等），根据上面的分析得到：
dp[i][j] = (s[i] == s[j]) and dp[i + 1][j - 1]
说明：
- 「动态规划」事实上是在填一张二维表格，由于构成子串，因此
i和j的关系是i <= j，因此，只需要填这张表格对角线以上的部分。 - 看到
dp[i + 1][j - 1]就得考虑边界情况。
边界条件是：表达式 [i + 1, j - 1] 不构成区间，即长度严格小于 2，即 j - 1 - (i + 1) + 1 < 2 ，整理得 j - i < 3。
这个结论很显然：j - i < 3 等价于 j - i + 1 < 4，即当子串 s[i..j] 的长度等于 2 或者等于 3 的时候，其实只需要判断一下头尾两个字符是否相等就可以直接下结论了。
- 如果子串
s[i + 1..j - 1]只有 1 个字符，即去掉两头，剩下中间部分只有 1 个字符，显然是回文； - 如果子串
s[i + 1..j - 1]为空串，那么子串s[i, j]一定是回文子串。
因此，在 s[i] == s[j] 成立和 j - i < 3 的前提下，直接可以下结论，dp[i][j] = true，否则才执行状态转移。
第 3 步：考虑初始化
初始化的时候，单个字符一定是回文串，因此把对角线先初始化为 true，即 dp[i][i] = true 。
事实上，初始化的部分都可以省去。因为只有一个字符的时候一定是回文，dp[i][i] 根本不会被其它状态值所参考。
第 4 步：考虑输出
只要一得到 dp[i][j] = true，就记录子串的长度和起始位置，没有必要截取，这是因为截取字符串也要消耗性能，记录此时的回文子串的「起始位置」和「回文长度」即可。
第 5 步：考虑优化空间
因为在填表的过程中，只参考了左下方的数值。事实上可以优化，但是增加了代码编写和理解的难度，丢失可读和可解释性。在这里不优化空间。
注意事项：总是先得到小子串的回文判定，然后大子串才能参考小子串的判断结果，即填表顺序很重要。
public class Solution {
public String longestPalindrome(String s) {
// 特判
int len = s.length();
if (len < 2) {
return s;
}
int maxLen = 1;
int begin = 0;
// dp[i][j] 表示 s[i, j] 是否是回文串
boolean[][] dp = new boolean[len][len];
char[] charArray = s.toCharArray();
for (int i = 0; i < len; i++) {
dp[i][i] = true;
}
for (int j = 1; j < len; j++) {
for (int i = 0; i < j; i++) {
if (charArray[i] != charArray[j]) {
dp[i][j] = false;
} else {
if (j - i < 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
}
// 只要 dp[i][j] == true 成立，就表示子串 s[i..j] 是回文，此时记录回文长度和起始位置
if (dp[i][j] && j - i + 1 > maxLen) {
maxLen = j - i + 1;
begin = i;
}
}
}
return s.substring(begin, begin + maxLen);
}
}复杂度分析：
时间复杂度：O(N2)。
空间复杂度：O(N2)，二维 dp 问题，一个状态得用二维有序数对表示，因此空间复杂度是 O(N2)。
下面分别展示了错误的填表顺序和正确的填表顺序，以便大家理解动态规划要满足「无后效性」的意思。
说明：表格中的数字表示「填表顺序」，从 1 开始。表格外的箭头和数字也表示「填表顺序」，与表格中的数字含义一致。
下面这段代码只有内层循环和上文代码1.0不同，已经标注在注释中。
import java.util.Arrays;
public class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2) {
return s;
}
boolean[][] dp = new boolean[len][len];
for (int i = 0; i < len; i++) {
Arrays.fill(dp[i], false);
}
// 初始化
for (int i = 0; i < len; i++) {
dp[i][i] = true;
}
char[] charArray = s.toCharArray();
int maxLen = 1;
int start = 0;
for (int j = 1; j < len; j++) {
// 只有下面这一行和代码1.0不同，i 正着写、倒过来写都行，因为子串都有参考值
for (int i = j - 1; i >= 0; i--) {
if (charArray[i] == charArray[j]) {
if (j - i < 3) {
dp[i][j] = true;
} else {
dp[i][j] = dp[i + 1][j - 1];
}
} else {
dp[i][j] = false;
}
// 只要 dp[i][j] == true 成立，就表示子串 s[i, j] 是回文，此时记录回文长度和起始位置
if (dp[i][j]) {
int curLen = j - i + 1;
if (curLen > maxLen) {
maxLen = curLen;
start = i;
}
}
}
}
return s.substring(start, start + maxLen);
}
}总结：
- 我们看到，用「动态规划」方法解决问题，有的时候并不是直接面向问题的。
- 「动态规划」依然是「空间换时间」思想的体现，并且本身「动态规划」作为一种打表格法，就是在用「空间」换「时间」。
关于「动态规划」方法执行时间慢的说明：
- 动态规划本质上还是「暴力解法」，因为需要枚举左右边界，有 O(N2)这么多；
- 以下提供的「中心扩散法」枚举了所有可能的回文子串的中心，有 O(2N)这么多，不在一个级别上。
上面采用了时间复杂度估算的表示，O(N2)表示最高项是 aN2的多项式。
从这个问题我们也可以看出，虽然时间复杂度一样，但是实际执行时间有可能是有差距的，并且时间复杂度是一个估算，没有必要计算得很清楚，这是因为真正的运行时间还和很多因素有关：例如所运行机器的环境，测试用例等。
方法三： 中心扩散
暴力法采用双指针两边夹，验证是否是回文子串。
除了枚举字符串的左右边界以外，比较容易想到的是枚举可能出现的回文子串的“中心位置”，从“中心位置”尝试尽可能扩散出去，得到一个回文串。
因此中心扩散法的思路是：遍历每一个索引，以这个索引为中心，利用“回文串”中心对称的特点，往两边扩散，看最多能扩散多远。
枚举“中心位置”时间复杂度为 O(N)，从“中心位置”扩散得到“回文子串”的时间复杂度为 O(N)，因此时间复杂度可以降到 O(N2)。
在这里要注意一个细节：回文串在长度为奇数和偶数的时候，“回文中心”的形式是不一样的。
- 奇数回文串的“中心”是一个具体的字符，例如：回文串
"aba"的中心是字符"b"； - 偶数回文串的“中心”是位于中间的两个字符的“空隙”，例如：回文串串
"abba"的中心是两个"b"中间的那个“空隙”。
我们看一下一个字符串可能的回文子串的中心在哪里？
我们可以设计一个方法，兼容以上两种情况：
- 如果传入重合的索引编码，进行中心扩散，此时得到的回文子串的长度是奇数；
- 如果传入相邻的索引编码，进行中心扩散，此时得到的回文子串的长度是偶数。
具体编码细节在以下的代码的注释中体现。
public class Solution {
public String longestPalindrome(String s) {
int len = s.length();
if (len < 2) {
return s;
}
int maxLen = 1;
String res = s.substring(0, 1);
// 中心位置枚举到 len - 2 即可
for (int i = 0; i < len - 1; i++) {
String oddStr = centerSpread(s, i, i);
String evenStr = centerSpread(s, i, i + 1);
String maxLenStr = oddStr.length() > evenStr.length() ? oddStr : evenStr;
if (maxLenStr.length() > maxLen) {
maxLen = maxLenStr.length();
res = maxLenStr;
}
}
return res;
}
private String centerSpread(String s, int left, int right) {
// left = right 的时候，此时回文中心是一个字符，回文串的长度是奇数
// right = left + 1 的时候，此时回文中心是一个空隙，回文串的长度是偶数
int len = s.length();
int i = left;
int j = right;
while (i >= 0 && j < len) {
if (s.charAt(i) == s.charAt(j)) {
i--;
j++;
} else {
break;
}
}
// 这里要小心，跳出 while 循环时，恰好满足 s.charAt(i) != s.charAt(j)，因此不能取 i，不能取 j
return s.substring(i + 1, j);
}
}复杂度分析：
- 时间复杂度：O(N2)，理由已经叙述。
- 空间复杂度：O(1)，只使用到常数个临时变量，与字符串长度无关。
事实上，还有时间复杂度更优的算法，是由计算机科学家 Manacher 发明的。
排序 (Medium)
给定一个数组，请你编写一个函数，返回该数组排序后的形式。
示例1
输入：[5,2,3,1,4]
输出：[1,2,3,4,5]示例2
输入：[5,1,6,2,5]
输出：[1,2,5,5,6]解法1：调用库函数Arrays.sort
import java.util.Arrays;
public class Solution {
public int[] MySort (int[] arr) {
//调用库函数sort；
Arrays.sort(arr);
return arr;
}
}解法2：冒泡排序BubbleSort
以升序排列为例：将第一个元素和第二个元素比较，若前者大于后者，则交换两者的位置，再将第二个元素与第三个元素比较，若前者大于后者则交换两者位置，以此类推直到倒数第二个元素与最后一个元素比较，若前者大于后者，则交换两者位置。这样一轮比较下来将会把序列中最大的元素移至序列末尾，这样就安排好了最大数的位置，接下来只需对剩下的（n-1）个元素，重复上述操作即可。
时间复杂度：
若原数组本身就是有序的（这是最好情况），仅需n-1次比较就可完成，时间复杂度依然为O(n）；
若是倒序，比较次数为 n-1+n-2+…+1=n(n-1)/2，交换次数和比较次数等值。所以，其时间复杂度依然为O(n2）
空间复杂度：
使用常数个辅助单元：O(1）
public int[] MySort (int[] arr) {
if(arr.length<2){
return arr;
}
// for(int end=arr.length-1; end>0; end--){//每次选出最大的放到最后，重复；
// for(int i=0;i<end;i++){
// if(arr[i]>arr[i+1]){
// swap(arr,i,i+1);
// }
// }
// }
for(int i=0;i<arr.length-1;i++){
for(int j=0;j<arr.length-i-1;j++){
if(arr[j]>arr[j+1]){
swap(arr,j,j+1);
}
}
}
return arr;
}
public void swap(int[]arr,int i, int j){
int tmp;
tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}
/* public static void swap(int[] arr, int i, int j) {
arr[i] = arr[i] ^ arr[j];
arr[j] = arr[i] ^ arr[j];
arr[i] = arr[i] ^ arr[j];
}
*/解法3：快速排序Quicksort
**快速排序(Quick Sort)**：是对冒泡排序的一种改进方法，在冒泡排序中，进行元素的比较和交换是在相邻元素之间进行的，元素每次交换只能移动一个位置，所以比较次数和移动次数较多，效率相对较低。而在快速排序中，元素的比较和交换是从两端向中间进行的，较大的元素一轮就能够交换到后面的位置，而较小的元素一轮就能交换到前面的位置，元素每次移动的距离较远，所以比较次数和移动次数较少，y速度较快，故称为“快速排序”。
快速排序的基本思想是：
- 在待排序的元素任取一个元素作为基准(通常选第一个元素，但最的选择方法是从待排序元素中随机选取一个作为基准)，称为基准元素；
- 将待排序的元素进行分区，比基准元素大的元素放在它的右边，比其小的放在它的左边；
- 对左右两个分区重复以上步骤直到所有元素都是有序的
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 将给定数组排序
* @param arr int整型一维数组 待排序的数组
* @return int整型一维数组
*/
public int[] MySort (int[] arr) {
quickSort(arr , 0 , arr.length-1);
return arr;
}
public void quickSort(int[] list, int left, int right) {
if (left < right) {
// 分割数组，找到分割点
int point = partition(list, left, right);
// 递归调用，对左子数组进行快速排序
quickSort(list, left, point - 1);
// 递归调用，对右子数组进行快速排序
quickSort(list, point + 1, right);
}
}
/**
* 分割数组，找到分割点
*/
public int partition(int[] list, int left, int right) {
// 用数组的第一个元素作为基准数
int first = list[left];
while (left < right) {
while (left < right && list[right] >= first) {
right--;
}
// 交换
swap(list, left, right);
while (left < right && list[left] <= first) {
left++;
}
// 交换
swap(list, left, right);
}
// 返回分割点所在的位置
return left;
}
private void swap(int[] arr, int i, int j) {
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
}public static void quickSort(int[] arr,int L,int R){
if(L<R){
swap(arr,L+(int)(Math.random()*(R-L+1)),R);//加上就是随机快排, Math.random返回>=0，小于R-L+1的数
int [] p= paration(arr,L,R);
quickSort(arr,L,p[0]-1);
quickSort(arr,p[0]+1,R);
}
}
public static int[] paration(int[] arr,int L,int R){
int less=L-1;
int more=R;
int current=L;//current作为遍历数组的下标
while(current<more){
if(arr[current]<arr[R]){
swap(arr,++less,current++);
}
else if(arr[current]==arr[R]){
current++;
}
else{
swap(arr,--more,current);
}
}
swap(arr,more,R);
return new int[]{less+1,more};
}解法4：归并排序MergeSort
- 归并排序（MERGE-SORT）是利用归并的思想实现的排序方法，该算法采用经典的分治（divide-and-conquer）策略（分治法将问题分(divide)成一些小的问题然后递归求解，而治(conquer)的阶段则将分的阶段得到的各答案”修补”在一起，即分而治之)。
- 归并排序是稳定排序，它也是一种十分高效的排序，能利用完全二叉树特性的排序一般性能都不会太差。java中Arrays.sort()采用了一种名为TimSort的排序算法，就是归并排序的优化版本。从上文的图中可看出，每次合并操作的平均时间复杂度为O(n)，而完全二叉树的深度为|log2n|。总的平均时间复杂度为O(nlogn)。而且，归并排序的最好，最坏，平均时间复杂度均为O(nlogn)。
import java.util.*;
public class Solution {
/**
* 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
* 将给定数组排序
* @param arr int整型一维数组 待排序的数组
* @return int整型一维数组
*/
public int[] MySort (int[] arr) {
mergeSort(arr,0,arr.length-1);
return arr;
}
public void mergeSort(int[] arr,int l,int r){
if(l==r){
return;
}
int mid = l+((r-l)>>1); //中点位置，即(l+r)/2
mergeSort(arr,l,mid);
mergeSort(arr,mid+1,r);
merge(arr,l,mid,r);
}
public void merge(int[] arr,int l,int mid,int r){
int [] help= new int[r-l+1]; //辅助数组
int i=0;
int p1=l; //左半数组的下标
int p2=mid+1; //右半数组的下标
//判断是否越界
while(p1<=mid && p2<=r){
help[i++]=arr[p1]<arr[p2] ? arr[p1++] : arr[p2++];
}
//p1没有越界，说明p2越界了，将左边剩余元素拷贝到辅助数组
while(p1<=mid){
help[i++]=arr[p1++];
}
//p2没有越界，说明p1越界了
while(p2<=r){
help[i++]=arr[p2++];
}
//将辅助数组元素拷贝会原数组
for(i=0;i<help.length;i++){
arr[l+i]=help[i];
}
}
}解法5：堆排序HeapSort
堆结构就是将一颗完全二叉树映射到数组中的一种存储方式
- heapInsert和heapify
大根堆最重要的两个操作就是heapInsert和happify，前者是当一个元素加入到大根堆时应该自底向上与其父结点比较，若大于父结点则交换；后者是当堆中某个结点的数值发生变化时，应不断向下与其孩子结点中的最大值比较，若小于则交换。下面是对应的代码：
//判断该结点与父结点的大小，大结点一直往，建立大根堆
public static void heapInsert(int[] arr,int index){
while(arr[index]>arr[(index-1)/2]){
swap(arr,index,(index-1)/2);
index=(index-1)/2;
}
}
//一个值变小往下沉的过程
public static void heapify(int[] arr,int index,int size){
int left=index*2+1;
while(left<size){
int largest = left + 1 < size && arr[left+1] > arr[left] ? left+1 : left;
largest = arr[largest] > arr[index] ? largest :index;
if(largest==index){
break;
}
swap(arr,largest,index);
index=largest;
left=index*2 +1;
}
}- 利用heapify排序
public int[] MySort (int[] arr) {
heapSort(arr);
return arr;
}
public static void heapSort(int[] arr){
if(arr == null || arr.length<2){
return;
}
for(int i=0;i<arr.length;i++){
heapInsert(arr,i); //构造完全二叉树
}
int size = arr.length;
swap(arr,0,--size);
while(size>0){
heapify(arr,0,size);// 最后一个数与根交换
swap(arr,0,--size);
}
}
//判断该结点与父结点的大小，大结点一直往，建立大根堆
public static void heapInsert(int[] arr,int index){
while(arr[index]>arr[(index-1)/2]){
swap(arr,index,(index-1)/2);
index=(index-1)/2;
}
}
//一个值变小往下沉的过程
public static void heapify(int[] arr,int index,int size){
int left=index*2+1;
while(left<size){
int largest = left + 1 < size && arr[left+1] > arr[left] ? left+1 : left;
largest = arr[largest] > arr[index] ? largest :index;
if(largest==index){
break;
}
swap(arr,largest,index);
index=largest;
left=index*2 +1;
}
}
//交换函数
public static void swap(int[] arr, int i, int j){
int tmp;
tmp=arr[i];
arr[i]=arr[j];
arr[j]=tmp;
}解法6：优先级队列PriorityQueue
优先队列不再遵循先入先出的原则，而是分为两种情况：
- 最大优先队列，无论入队顺序，当前最大的元素优先出队；
- 最小优先队列，无论入队顺序，当前最小的元素优先出队；
比如有一个最大优先队列，它的最大元素是8，那么虽然元素8并不是队首元素，但出队的时候仍然让元素8首先出队：
优先级队列，也叫二叉堆、堆（不要和内存中的堆区搞混了，一个是内存区域，一个是数据结构）。
堆的本质上是一种完全二叉树，分为：
- 小根堆：树中每个非叶子结点都不大于其左右孩子结点的值，也就是根节点最小的堆，图a
- 大根堆：树中每个非叶子结点都不小于其左右孩子结点的值，也就是根节点最大的堆，图b
public int[] MySort (int[] arr) {
// PriorityQueue<Integer> queue=new PriorityQueue<Integer>();
PriorityQueue<Integer> queue=new PriorityQueue<>(new Comparator<Integer>(){
public int compare(Integer a,Integer b){
return a.compareTo(b);
}
});
for(int i=0;i<arr.length;i++){
queue.add(arr[i]);
}
int[] newarr=new int[arr.length];
for(int i=0;i<arr.length;i++){
newarr[i]=queue.poll();
}
return newarr;
}LRU 缓存机制 (Medium)
运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制 。
实现 LRUCache 类：
LRUCache(int capacity) 以正整数作为容量 capacity 初始化 LRU 缓存int get(int key) 如果关键字 key 存在于缓存中，则返回关键字的值，否则返回 -1 。void put(int key, int value) 如果关键字已经存在，则变更其数据值；如果关键字不存在，则插入该组「关键字-值」。当缓存容量达到上限时，它应该在写入新数据之前删除最久未使用的数据值，从而为新的数据值留出空间。
进阶：你是否可以在 O(1) 时间复杂度内完成这两种操作？
示例：
["LRUCache", "put", "put", "get", "put", "get", "put", "get", "get", "get"]
[[2], [1, 1], [2, 2], [1], [3, 3], [2], [4, 4], [1], [3], [4]]
输出
[null, null, null, 1, null, -1, null, -1, 3, 4]
解释
LRUCache lRUCache = new LRUCache(2);
lRUCache.put(1, 1); // 缓存是 {1=1}
lRUCache.put(2, 2); // 缓存是 {1=1, 2=2}
lRUCache.get(1); // 返回 1
lRUCache.put(3, 3); // 该操作会使得关键字 2 作废，缓存是 {1=1, 3=3}
lRUCache.get(2); // 返回 -1 (未找到)
lRUCache.put(4, 4); // 该操作会使得关键字 1 作废，缓存是 {4=4, 3=3}
lRUCache.get(1); // 返回 -1 (未找到)
lRUCache.get(3); // 返回 3
lRUCache.get(4); // 返回 4算法
LRU 缓存机制可以通过哈希表辅以双向链表实现，我们用一个哈希表和一个双向链表维护所有在缓存中的键值对。
- 双向链表按照被使用的顺序存储了这些键值对，靠近头部的键值对是最近使用的，而靠近尾部的键值对是最久未使用的。
- 哈希表即为普通的哈希映射（HashMap），通过缓存数据的键映射到其在双向链表中的位置。
这样以来，我们首先使用哈希表进行定位，找出缓存项在双向链表中的位置，随后将其移动到双向链表的头部，即可在 O(1) 的时间内完成 get 或者 put 操作。具体的方法如下：
对于
get操作，首先判断key是否存在：- 如果
key不存在，则返回 -1−1； - 如果
key存在，则key对应的节点是最近被使用的节点。通过哈希表定位到该节点在双向链表中的位置，并将其移动到双向链表的头部，最后返回该节点的值。
- 如果
对于
put操作，首先判断key是否存在：- 如果
key不存在，使用key和value创建一个新的节点，在双向链表的头部添加该节点，并将key和该节点添加进哈希表中。然后判断双向链表的节点数是否超出容量，如果超出容量，则删除双向链表的尾部节点，并删除哈希表中对应的项； - 如果
key存在，则与get操作类似，先通过哈希表定位，再将对应的节点的值更新为value，并将该节点移到双向链表的头部。
- 如果
上述各项操作中，访问哈希表的时间复杂度为 O(1)，在双向链表的头部添加节点、在双向链表的尾部删除节点的复杂度也为 O(1)。而将一个节点移到双向链表的头部，可以分成「删除该节点」和「在双向链表的头部添加节点」两步操作，都可以在 O(1) 时间内完成。
小贴士
在双向链表的实现中，使用一个伪头部（dummy head）和伪尾部（dummy tail）标记界限，这样在添加节点和删除节点的时候就不需要检查相邻的节点是否存在。
public class LRUCache {
class DLinkedNode {
int key;
int value;
DLinkedNode prev;
DLinkedNode next;
public DLinkedNode() {}
public DLinkedNode(int _key, int _value) {key = _key; value = _value;}
}
private Map<Integer, DLinkedNode> cache = new HashMap<Integer, DLinkedNode>();
private int size;
private int capacity;
private DLinkedNode head, tail;
public LRUCache(int capacity) {
this.size = 0;
this.capacity = capacity;
// 使用伪头部和伪尾部节点
head = new DLinkedNode();
tail = new DLinkedNode();
head.next = tail;
tail.prev = head;
}
public int get(int key) {
DLinkedNode node = cache.get(key);
if (node == null) {
return -1;
}
// 如果 key 存在，先通过哈希表定位，再移到头部
moveToHead(node);
return node.value;
}
public void put(int key, int value) {
DLinkedNode node = cache.get(key);
if (node == null) {
// 如果 key 不存在，创建一个新的节点
DLinkedNode newNode = new DLinkedNode(key, value);
// 添加进哈希表
cache.put(key, newNode);
// 添加至双向链表的头部
addToHead(newNode);
++size;
if (size > capacity) {
// 如果超出容量，删除双向链表的尾部节点
DLinkedNode tail = removeTail();
// 删除哈希表中对应的项
cache.remove(tail.key);
--size;
}
}
else {
// 如果 key 存在，先通过哈希表定位，再修改 value，并移到头部
node.value = value;
moveToHead(node);
}
}
private void addToHead(DLinkedNode node) {
node.prev = head;
node.next = head.next;
head.next.prev = node;
head.next = node;
}
private void removeNode(DLinkedNode node) {
node.prev.next = node.next;
node.next.prev = node.prev;
}
private void moveToHead(DLinkedNode node) {
removeNode(node);
addToHead(node);
}
private DLinkedNode removeTail() {
DLinkedNode res = tail.prev;
removeNode(res);
return res;
}
}复杂度分析
- 时间复杂度：对于
put和get都是 O(1)。 - 空间复杂度：*O(capacity)*，因为哈希表和双向链表最多存储 capacity+1 个元素。
最小K个数 (Easy)
设计一个算法，找出数组中最小的k个数。以任意顺序返回这k个数均可。
示例：
输出： [1,2,3,4]
输入： arr = [1,3,5,7,2,4,6,8], k = 4方法一：排序
思路和算法
对原数组从小到大排序后取出前 k 个数即可。
class Solution {
public int[] smallestK(int[] arr, int k) {
int[] vec = new int[k];
Arrays.sort(arr);
for (int i = 0; i < k; ++i) {
vec[i] = arr[i];
}
return vec;
}
}复杂度分析
- 时间复杂度：O(nlogn)，其中 n 是数组 arr 的长度。算法的时间复杂度即排序的时间复杂度。
- 空间复杂度：O(logn)，排序所需额外的空间复杂度为 O(logn)。
方法二：堆
思路和算法
我们用一个大根堆实时维护数组的前 k 小值。首先将前 k 个数插入大根堆中，随后从第 k+1 个数开始遍历，如果当前遍历到的数比大根堆的堆顶的数要小，就把堆顶的数弹出，再插入当前遍历到的数。最后将大根堆里的数存入数组返回即可。
class Solution {
public int[] smallestK(int[] arr, int k) {
int[] vec = new int[k];
if (k == 0) { // 排除 0 的情况
return vec;
}
PriorityQueue<Integer> queue = new PriorityQueue<Integer>(new Comparator<Integer>() {
public int compare(Integer num1, Integer num2) {
return num2 - num1;
}
});
for (int i = 0; i < k; ++i) {
queue.offer(arr[i]);
}
for (int i = k; i < arr.length; ++i) {
if (queue.peek() > arr[i]) {
queue.poll();
queue.offer(arr[i]);
}
}
for (int i = 0; i < k; ++i) {
vec[i] = queue.poll();
}
return vec;
}
}复杂度分析
- 时间复杂度：O(nlogk)，其中 n 是数组 arr 的长度。由于大根堆实时维护前 kk 小值，所以插入删除都是 O(logk) 的时间复杂度，最坏情况下数组里 n 个数都会插入，所以一共需要 O(nlogk) 的时间复杂度。
- 空间复杂度：O(k)，因为大根堆里最多 k 个数。
方法三：快排思想
思路和算法
我们可以借鉴快速排序的思想。我们知道快排的划分函数每次执行完后都能将数组分成两个部分，小于等于分界值 pivot 的元素的都会被放到数组的左边，大于的都会被放到数组的右边，然后返回分界值的下标。与快速排序不同的是，快速排序会根据分界值的下标递归处理划分的两侧，而这里我们只处理划分的一边。
我们定义函数 randomized_selected(arr, l, r, k) 表示划分数组 arr 的 [l,r] 部分，使前 k 小的数在数组的左侧，在函数里我们调用快排的划分函数，假设划分函数返回的下标是 pos（表示分界值 pivot 最终在数组中的位置），即 pivot 是数组中第 pos - l + 1 小的数，那么一共会有三种情况：
- 如果
pos - l + 1 == k，表示pivot就是第 k 小的数，直接返回即可； - 如果
pos - l + 1 < k，表示第 k 小的数在pivot的右侧，因此递归调用randomized_selected(arr, pos + 1, r, k - (pos - l + 1))； - 如果
pos - l + 1 > k，表示第 kk 小的数在 pivot 的左侧，递归调用randomized_selected(arr, l, pos - 1, k)。
函数递归入口为 randomized_selected(arr, 0, arr.length - 1, k)。在函数返回后，将前 k 个数放入答案数组返回即可。
class Solution {
public int[] smallestK(int[] arr, int k) {
randomizedSelected(arr, 0, arr.length - 1, k);
int[] vec = new int[k];
for (int i = 0; i < k; ++i) {
vec[i] = arr[i];
}
return vec;
}
private void randomizedSelected(int[] arr, int l, int r, int k) {
if (l >= r) {
return;
}
int pos = randomizedPartition(arr, l, r);
int num = pos - l + 1;
if (k == num) {
return;
} else if (k < num) {
randomizedSelected(arr, l, pos - 1, k);
} else {
randomizedSelected(arr, pos + 1, r, k - num);
}
}
// 基于随机的划分
private int randomizedPartition(int[] nums, int l, int r) {
int i = new Random().nextInt(r - l + 1) + l;
swap(nums, r, i);
return partition(nums, l, r);
}
private int partition(int[] nums, int l, int r) {
int pivot = nums[r];
int i = l - 1;
for (int j = l; j <= r - 1; ++j) {
if (nums[j] <= pivot) {
i = i + 1;
swap(nums, i, j);
}
}
swap(nums, i + 1, r);
return i + 1;
}
private void swap(int[] nums, int i, int j) {
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}复杂度分析
时间复杂度：期望为 O(n) ，由于证明过程很繁琐，所以不再这里展开讲。具体证明可以参考《算法导论》第 9 章第 2 小节。
最坏情况下的时间复杂度为 O(n^2^ )。情况最差时，每次的划分点都是最大值或最小值，一共需要划分 n - 1 次，而一次划分需要线性的时间复杂度，所以最坏情况下时间复杂度为 O(n^2^ )。
空间复杂度：期望为 O(logn)，递归调用的期望深度为 O(logn)，每层需要的空间为 O(1)，只有常数个变量。
最坏情况下的空间复杂度为 O(n)。最坏情况下需要划分 n 次，即
randomized_selected函数递归调用最深 n - 1 层，而每层由于需要 O(1) 的空间，所以一共需要 O(n) 的空间复杂度。
用两个栈实现队列 (Easy)
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 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]解题思路
- 栈无法实现队列功能： 栈底元素（对应队首元素）无法直接删除，需要将上方所有元素出栈。
- 双栈可实现列表倒序： 设有含三个元素的栈 A = [1,2,3] 和空栈 B = []。若循环执行 A 元素出栈并添加入栈 B ，直到栈 A 为空，则 A = [] , B = [3,2,1] ，即 栈 B 元素实现栈 A 元素倒序 。
- 利用栈 B 删除队首元素： 倒序后，B 执行出栈则相当于删除了 A 的栈底元素，即对应队首元素。
函数设计
题目只要求实现 加入队尾
appendTail()和 删除队首deleteHead()两个函数的正常工作，因此我们可以设计栈A用于加入队尾操作，栈B用于将元素倒序，从而实现删除队首元素。
- 加入队尾
appendTail()函数： 将数字val加入栈A即可。 - 删除队首
deleteHead()函数： 有以下三种情况。- 当栈
B不为空：B中仍有已完成倒序的元素，因此直接返回B的栈顶元素。 - 否则，当
A为空： 即两个栈都为空，无元素，因此返回 −1 。 - 否则： 将栈
A元素全部转移至栈B中，实现元素倒序，并返回栈B的栈顶元素。
- 当栈
复杂度分析
由于问题特殊，以下分析仅满足添加 N 个元素并删除 N 个元素，即栈初始和结束状态下都为空的情况。
- 时间复杂度：
appendTail()函数为 O(1) ；deleteHead()函数在 N 次队首元素删除操作中总共需完成 N 个元素的倒序。 - 空间复杂度 O(N) ： 最差情况下，栈
A和B共保存 N 个元素。
代码
class CQueue {
LinkedList<Integer> A, B;
public CQueue() {
A = new LinkedList<Integer>();
B = new LinkedList<Integer>();
}
public void appendTail(int value) {
A.addLast(value);
}
public int deleteHead() {
if(!B.isEmpty()) return B.removeLast();
if(A.isEmpty()) return -1;
while(!A.isEmpty())
B.addLast(A.removeLast());
return B.removeLast();
}
}制作 m 束花所需的最少天数 (Medium)
给你一个整数数组 bloomDay，以及两个整数 m 和 k 。
现需要制作 m 束花。制作花束时，需要使用花园中 相邻的 k 朵花 。
花园中有 n 朵花，第 i 朵花会在 bloomDay[i] 时盛开，恰好 可以用于 一束 花中。
请你返回从花园中摘 m 束花需要等待的最少的天数。如果不能摘到 m 束花则返回 -1 。
示例 1：
输入：bloomDay = [1,10,3,10,2], m = 3, k = 1
输出：3
解释：让我们一起观察这三天的花开过程，x 表示花开，而 _ 表示花还未开。
现在需要制作 3 束花，每束只需要 1 朵。
1 天后：[x, _, _, _, _] // 只能制作 1 束花
2 天后：[x, _, _, _, x] // 只能制作 2 束花
3 天后：[x, _, x, _, x] // 可以制作 3 束花，答案为 3示例 2：
输入：bloomDay = [1,10,3,10,2], m = 3, k = 2
输出：-1
解释：要制作 3 束花，每束需要 2 朵花，也就是一共需要 6 朵花。而花园中只有 5 朵花，无法满足制作要求，返回 -1 。示例 3：
输入：bloomDay = [7,7,7,7,12,7,7], m = 2, k = 3
输出：12
解释：要制作 2 束花，每束需要 3 朵。
花园在 7 天后和 12 天后的情况如下：
7 天后：[x, x, x, x, _, x, x]
可以用前 3 朵盛开的花制作第一束花。但不能使用后 3 朵盛开的花，因为它们不相邻。
12 天后：[x, x, x, x, x, x, x]
显然，我们可以用不同的方式制作两束花。示例 4：
输入：bloomDay = [1000000000,1000000000], m = 1, k = 1
输出：1000000000
解释：需要等 1000000000 天才能采到花来制作花束示例 5：
输入：bloomDay = [1,10,2,9,3,8,4,7,5,6], m = 4, k = 2
输出：9解题思路
- 制作花朵最少的时间必然是 bloomDay 数组中开花所用天数最少的那朵花
min(bloomDay) - 制作花朵最多的时间也只能是 bloomDay 数组中开花所需天数最多的那朵花
max(bloomDay) - 寻找制作花束的最少天数必然落在上面所说的区间里 [min(bloomDay), max(bloomDay)], 连续的一个正整数区间, 因此可以通过二分查找来提升查找效率!
结合题目
- 数组中的花朵不够用来制作花束的, 直接返回
-1 - 必须是连续的花朵, 这个可以通过变量
flower来计数是否连续, 一旦不连续就重置为 0 - 每满足一次连续的 k 朵花, 就可以制作一束花,
flower计数重新为 0 开始计数
代码
class Solution {
public int minDays(int[] bloomDay, int m, int k) {
// 数组中的花朵不够用来制作花束的, 直接返回 -1
if (m * k > bloomDay.length) {
return -1;
}
int right = 0;
for (int num : bloomDay) {
right = Math.max(right, num);
}
int left = 0;
while (left < right) {
int mid = left + (right - left) / 2;
int count = helper(bloomDay, mid, k);
if (count >= m) {
right = mid ;
} else {
left = mid + 1;
}
}
return left;
}
private int helper(int[] nums, int day, int k) {
int res = 0;
int count = 0;
for (int i = 0; i < nums.length; i++) {
if (nums[i] <= day) {
count++;
}
// 必须是连续的花朵, 这个可以通过变量 count 来计数是否连续, 一旦不连续就重置为 0
else {
count = 0;
}
// 满足一次连续的 k 朵花, 就可以制作一束花, count 计数重新为 0 开始计数
if (count == k) {
count = 0;
res++;
}
}
return res;
}
}本博客所有文章除特别声明外，均采用 CC BY-SA 4.0 协议 ，转载请注明出处！