- 剑指 Offer 03. 数组中重复的数字
- 题目介绍
- 题目实现
- 剑指 Offer 06. 从尾到头打印链表
- 题目介绍
- 题目实现
- 剑指 Offer 09. 用两个栈实现队列
- 题目介绍
- 题目实现
- 剑指 Offer 15. 二进制中1的个数
- 题目介绍
- 题目实现
- 剑指 Offer 47. 礼物的最大价值
- 题目介绍
- [64. 最小路径和](https://leetcode-cn.com/problems/minimum-path-sum/)
- [62. 不同路径](https://leetcode-cn.com/problems/unique-paths/)
- 题目实现
- 剑指 Offer 49. 丑数
- 题目介绍
- [264. 丑数 II](https://leetcode-cn.com/problems/ugly-number-ii/)
- 题目实现
- 剑指 Offer 59 - I. 滑动窗口的最大值
- 题目介绍
- [239. 滑动窗口最大值](https://leetcode-cn.com/problems/sliding-window-maximum/)
- 题目实现
- 剑指 Offer 59 - II. 队列的最大值
- 题目介绍
- 题目实现
- 剑指 Offer 64. 求1+2+…+n
- 题目介绍
- 题目实现
剑指 Offer 03. 数组中重复的数字 题目介绍
找出数组中重复的数字。
在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。请找出数组中任意一个重复的数字。
示例 1：
输入： [2, 3, 1, 0, 2, 5, 3] 输出：2 或 3
限制：
- 2 <= n <= 100000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/shu-zu-zhong-zhong-fu-de-shu-zi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
我们可以利用 set 集合元素不能重复这一特点，循环遍历数组元素，依次加入到 set 集合中，如果加入失败，就代表该数字重复。
class Solution {
public int findRepeatNumber(int[] nums) {
HashSet hashSet = new HashSet<>();
for (int num : nums) {
if (!hashSet.add(num)) {
return num;
}
}
return -1;
}
}
剑指 Offer 06. 从尾到头打印链表
题目介绍
输入一个链表的头节点，从尾到头反过来返回每个节点的值（用数组返回）。
示例 1：
输入：head = [1,3,2] 输出：[2,3,1]
限制：
- 0 <= 链表长度 <= 10000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
栈的特点是后进先出，即最后压入栈的元素最先弹出。考虑到栈的这一特点，使用栈将链表元素顺序倒置。从链表的头节点开始，依次将每个节点压入栈内，然后依次弹出栈内的元素并存储到数组中。
class Solution {
public int[] reversePrint(ListNode head) {
Stack stack = new Stack<>();
while (head != null) {
stack.push(head);
head = head.next;
}
int size = stack.size();
int[] arr = new int[size];
for (int i = 0; i < size; i++) {
arr[i] = stack.pop().val;
}
return arr;
}
}
剑指 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]
提示：
- 1 <= values <= 10000
- 最多会对 appendTail、deleteHead 进行 10000 次调用
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
队列的特性是 FIFO（先入先出），而栈的特性是 FILO（先入后出）。
知道两者特性之后，我们需要用两个栈来模拟队列的特性，一个栈为入队栈，一个栈为出对栈。
当出队栈存在内容时，出队栈的栈顶，即为第一个出队的元素。
若出队栈无元素，我们的需求又是出队的话，我们就需要将入队栈的内容反序导入出队栈，然后弹出栈顶即可。
注意：根据栈的的特性，我们仅能使用 push 和 pop 操作。
class CQueue {
private Stack inStack;
private Stack outStack;
public CQueue() {
inStack = new Stack<>();
outStack = new Stack<>();
}
public void appendTail(int value) {
inStack.push(value);
}
public int deleteHead() {
if (outStack.isEmpty()) {
while (!inStack.isEmpty()) {
outStack.push(inStack.pop());
}
}
if (outStack.isEmpty()) {
return -1;
} else {
return outStack.pop();
}
}
}
剑指 Offer 15. 二进制中1的个数
题目介绍
请实现一个函数，输入一个整数（以二进制串形式），输出该数二进制表示中 1 的个数。例如，把 9 表示成二进制是 1001，有 2 位是 1。因此，如果输入 9，则该函数输出 2。
示例 1：
输入：00000000000000000000000000001011 输出：3 解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
示例 2：
输入：00000000000000000000000010000000 输出：1 解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
示例 3：
输入：11111111111111111111111111111101 输出：31 解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
提示：
- 输入必须是长度为 32 的 二进制串 。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
- 根据 与运算 定义，设二进制数字 n ，则有：
- 若 n & 1 = 0 ，则 n 二进制 最右一位 为 0 ；
- 若 n & 1 = 1 ，则 n 二进制 最右一位 为 1 。
- 根据以上特点，考虑以下 循环判断 ：
- 判断 n 最右一位是否为 1 ，根据结果计数。
- 将 n 右移一位（本题要求把数字 n 看作无符号数，因此使用 无符号右移 操作）。
public class Solution {
public int hammingWeight(int n) {
int count = 0;
while (n != 0) {
count += n & 1;
n >>>= 1;
}
return count;
}
}
剑指 Offer 47. 礼物的最大价值
题目介绍
在一个 m*n 的棋盘的每一格都放有一个礼物，每个礼物都有一定的价值（价值大于 0）。你可以从棋盘的左上角开始拿格子里的礼物，并每次向右或者向下移动一格、直到到达棋盘的右下角。给定一个棋盘及其上面的礼物的价值，请计算你最多能拿到多少价值的礼物？
示例 1：
输入: [ [1,3,1], [1,5,1], [4,2,1] ] 输出: 12 解释: 路径 1→3→5→2→1 可以拿到最多价值的礼物
提示：
- 0 < grid.length <= 200
- 0 < grid[0].length <= 200
相似题目：
- 64. 最小路径和
- 62. 不同路径
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
从棋盘的左上角开始拿格子里的礼物，并每次 向右 或者 向下 移动一格、直到到达棋盘的右下角。
根据题目说明，易得某单元格只可能从上边单元格或左边单元格到达。
设 f(i, j) 为从棋盘左上角走至单元格 (i ,j) 的礼物最大累计价值，易得到以下递推关系：f(i,j) 等于 f(i,j-1) 和 f(i-1,j) 中的较大值加上当前单元格礼物价值 grid(i,j)。
因此，可用动态规划解决此问题，以上公式便为转移方程。
由于 dp[i][j] 只与 dp[i-1][j] , dp[i][j-1], grid[i][j] 有关系，因此可以将原矩阵 grid 用作 dp 矩阵，即直接在 grid 上修改即可。应用此方法可省去 dp 矩阵使用的额外空间，因此空间复杂度从 O(MN) 降至 O(1) 。
class Solution {
public int maxValue(int[][] grid) {
// 对临界值的判断
int rows = grid.length;
int cols = grid[0].length;
if (grid == null || rows == 0 || cols == 0) return 0;
// 初始化第一列
for (int i = 1; i < rows; i++) {
grid[i][0] = grid[i - 1][0] + grid[i][0];
}
// 初始化第一行
for (int i = 1; i < cols; i++) {
grid[0][i] = grid[0][i - 1] + grid[0][i];
}
// 动态规划核心
for (int i = 1; i < rows; i++) {
for (int j = 1; j < cols; j++) {
grid[i][j] = Math.max(grid[i - 1][j], grid[i][j - 1]) + grid[i][j];
}
}
// 返回最后元素
return grid[rows - 1][cols - 1];
}
}
剑指 Offer 49. 丑数
题目介绍
我们把只包含质因子 2、3 和 5 的数称作丑数（Ugly Number）。求按从小到大的顺序的第 n 个丑数。
示例：
输入: n = 10 输出: 12 解释: 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 是前 10 个丑数。
说明:
- 1 是丑数。
- n 不超过1690。
相同题目：
- 264. 丑数 II
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/chou-shu-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
class Solution {
public int nthUglyNumber(int n) {
int[] dp = new int[n];
dp[0] = 1;
int t2 = 0, t3 = 0, t5 = 0;
for (int i = 1; i < n; i++) {
int next2 = dp[t2] * 2, next3 = dp[t3] * 3, next5 = dp[t5] * 5;
dp[i] = Math.min(Math.min(next2, next3), next5);
if (next2 == dp[i]) t2++;
if (next3 == dp[i]) t3++;
if (next5 == dp[i]) t5++;
}
return dp[n - 1];
}
}
剑指 Offer 59 - I. 滑动窗口的最大值
题目介绍
给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
示例：
输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3 输出: [3,3,5,5,6,7] 解释: 滑动窗口的位置 最大值 --------------- ----- [1 3 -1] -3 5 3 6 7 3 1 [3 -1 -3] 5 3 6 7 3 1 3 [-1 -3 5] 3 6 7 5 1 3 -1 [-3 5 3] 6 7 5 1 3 -1 -3 [5 3 6] 7 6 1 3 -1 -3 5 [3 6 7] 7
提示：
- 你可以假设 k 总是有效的，在输入数组不为空的情况下，1 ≤ k ≤ 输入数组的大小。
相同题目：
- 239. 滑动窗口最大值
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
题目中提到了滑动窗口，我们先以示例为例看下什么是滑动窗口？
在示例中，我们从数组中第一个元素开始遍历，由于窗口的大小是3，因此当遍历到第三个元素时，窗口就形成了。
之后，继续遍历元素时，为了保持窗口的大小为3，左侧元素就需要从窗口中剔除。这样使得窗口一直在向右移动，直到考察到最后一个元素结束，这就是所谓的滑动窗口。
在上述滑动窗口形成及移动的过程中，我们注意到元素是从窗口的右侧进入的，然后由于窗口大小是固定的，因此多余的元素是从窗口左侧移除的。 一端进入，另一端移除，这不就是队列的性质吗？所以，该题目可以借助队列来求解。
题目要求是返回每个窗口中的最大值。那么这个如何解决呢？
我们以数组{5, 3, 4, 1}，窗口大小k=3来进行说明。这里我们规定窗口右侧边界为right，左侧边界为left，其值为元素下标。
然后，开始遍历nums = {5, 3, 4, 1}。当right指向第一个元素5时，此时队列为空，将第一个元素5入队。
继续考察第二个元素3，此时3小于队列末尾的元素5，因此元素3入队，以便看其是否是下一个窗口的最大值。这时队列中元素从队首到队尾是递减的。
接着考察{5, 3, 4, 1}中的第三个元素4，此时4大于队尾元素3，这表明元素3不可能是窗口「5 3 4」中的最大元素，因此需要将其从队列移除。但队首有元素5存在，因此不能将其从队首移除，那怎么办呢？我们可以将其从队尾移除。
对于这种一端既可以有元素入队，又有元素出队的队列，称之为双向队列。
队尾元素3出队之后，由于新的队尾元素5大于当前考察元素4，因此元素4入队，以便看其是否是下一个窗口的最大值。
当元素4入队之后，我们发现这时，队列中元素从队首到队尾依旧是递减的。
我们把从队首到队尾单调递减或递增的队列称之为单调队列。
接着，考察第四个元素1，此时元素1小于队尾元素4，因此元素1入队。
但这时，窗口内有4个元素，而我们这里规定窗口大小是3，因此，需要缩小窗口左边界left。在缩小窗口左边界left后，意味着元素5已经不再窗口内了，因此，队首元素5需要出队。也就是说，当队首元素在原数组中的下标小于窗口左边界时，队首元素就需要移除队列。
至此，该题目的求解思路就清晰了，具体如下：
- 遍历给定数组中的元素，如果队列不为空且当前考察元素大于等于队尾元素，则将队尾元素移除。直到，队列为空或当前考察元素小于新的队尾元素；
- 当队首元素的下标小于滑动窗口左侧边界left时，表示队首元素已经不再滑动窗口内，因此将其从队首移除。
- 由于数组下标从0开始，因此当窗口右边界right+1大于等于窗口大小k时，意味着窗口形成。此时，队首元素就是该窗口内的最大值。
需要说明的一点是，在上述演示中，队列存储的是元素值。而在具体代码实现中，为了方便计算，队列中存储的是元素的下标。
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if (nums == null || nums.length == 0) return new int[0];
// 定义双端队列，用于存储最大值的下标，注意：不是数组元素
Deque deque = new linkedList<>();
// 窗口个数，如何确定？nums.length - (k - 1) = nums.length - k + 1
int[] ans = new int[nums.length - k + 1];
// 遍历数组中元素，right表示滑动窗口右边界
for (int right = 0; right < nums.length; right++) {
// 如果队列不为空且当前考察元素大于等于队尾元素，则将队尾元素移除。
// 直到，队列为空或当前考察元素小于新的队尾元素
while (!deque.isEmpty() && nums[right] >= nums[deque.getLast()]) {
deque.removeLast();
}
// 存储元素下标
deque.addLast(right);
// 计算窗口左侧边界
int left = right - k + 1;
// 当队首元素的下标小于滑动窗口左侧边界left时
// 表示队首元素已经不再滑动窗口内，因此将其从队首移除
if (deque.getFirst() < left) {
deque.removeFirst();
}
// 由于数组下标从0开始，因此当窗口右边界right+1大于等于窗口大小k时
// 意味着窗口形成。此时，队首元素就是该窗口内的最大值
if (right + 1 >= k) {
ans[left] = nums[deque.peekFirst()];
}
}
return ans;
}
}
剑指 Offer 59 - II. 队列的最大值
题目介绍
请定义一个队列并实现函数 max_value 得到队列里的最大值，要求函数max_value、push_back 和 pop_front 的均摊时间复杂度都是O(1)。若队列为空，pop_front 和 max_value 需要返回 -1 。
示例 1：
输入: ["MaxQueue","push_back","push_back","max_value","pop_front","max_value"] [[],[1],[2],[],[],[]] 输出: [null,null,null,2,1,2]
示例 2：
输入: ["MaxQueue","pop_front","max_value"] [[],[],[]] 输出: [null,-1,-1]
限制：
- 1 <= push_back,pop_front,max_value的总操作数 <= 10000
- 1 <= value <= 105
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
直接实现一个普通的队列，查询最大值时遍历计算。
class MaxQueue {
int[] queue = new int[10000];
int begin = 0, end = 0;
public MaxQueue() {}
public int max_value() {
int ans = -1;
for (int i = begin; i != end; i++) {
ans = Math.max(ans, queue[i]);
}
return ans;
}
public void push_back(int value) {
queue[end++] = value;
}
public int pop_front() {
if (begin == end) {
return -1;
}
return queue[begin++];
}
}
剑指 Offer 64. 求1+2+…+n
题目介绍
求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
示例 1：
输入: n = 3 输出: 6
示例 2：
输入: n = 9 输出: 45
限制：
- 1 <= n <= 10000
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/qiu-12n-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
这道题使用高斯求和公式，将乘除法用位运算替换掉即可。
文字表述：和 = (首项 + 末项) x 项数 / 2
数学表达：1+2+……+ n = (n+1) n / 2
class Solution {
public int sumNums(int n) {
return (1 + n) * n >> 1;
}
}
