- 剑指 Offer 59 - I. 滑动窗口的最大值
- 剑指 Offer 59 - II. 队列的最大值
- 剑指 Offer 37. 序列化二叉树
- 剑指 Offer 38. 字符串的排列
- 剑指 Offer 49. 丑数
- 剑指 Offer 17. 打印从1到最大的n位数
- 剑指 Offer 51. 数组中的逆序对
剑指 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 ≤ 输入数组的大小。
链接：https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/
解法一：优先队列（堆）
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
PriorityQueue<int[]> pq = new PriorityQueue<int[]>(new Comparator<int[]>() {
public int compare(int[] pair1, int[] pair2) {
return pair1[0] != pair2[0] ? pair2[0] - pair1[0] : pair2[1] - pair1[1];
}
});
for (int i = 0; i < k; ++i) {
pq.offer(new int[]{nums[i], i});
}
int[] ans = new int[n - k + 1];
ans[0] = pq.peek()[0];
for (int i = k; i < n; ++i) {
pq.offer(new int[]{nums[i], i});
while (pq.peek()[1] <= i - k) {
pq.poll();
}
ans[i - k + 1] = pq.peek()[0];
}
return ans;
}
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/solution/hua-dong-chuang-kou-de-zui-da-zhi-by-lee-ymyo/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
解法二：单调队列(单调递减的队列)
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
int n = nums.length;
Deque<Integer> deque = new LinkedList<Integer>();
for (int i = 0; i < k; ++i) {
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(i);
}
int[] ans = new int[n - k + 1];
ans[0] = nums[deque.peekFirst()];
for (int i = k; i < n; ++i) {
while (!deque.isEmpty() && nums[i] >= nums[deque.peekLast()]) {
deque.pollLast();
}
deque.offerLast(i);
while (deque.peekFirst() <= i - k) {
deque.pollFirst();
}
ans[i - k + 1] = nums[deque.peekFirst()];
}
return ans;
}
}
作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/hua-dong-chuang-kou-de-zui-da-zhi-lcof/solution/hua-dong-chuang-kou-de-zui-da-zhi-by-lee-ymyo/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
剑指 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 <= 10^5
链接：https://leetcode-cn.com/problems/dui-lie-de-zui-da-zhi-lcof/
解法一：维护一个普通队列和单调队列
class MaxQueue {
Queue<Integer> queue;
Deque<Integer> deque;
public MaxQueue() {
this.queue = new LinkedList<>();
this.deque = new LinkedList<Integer>();
}
public int max_value() {
if (deque.isEmpty()){
return -1;
}
return deque.peekFirst();
}
public void push_back(int value) {
queue.offer(value);
while (!deque.isEmpty()&&deque.peekLast()<value){
deque.pollLast();
}
deque.offerLast(value);
}
public int pop_front() {
if (queue.isEmpty()) {
return -1;
}
int ans = queue.poll();
if (ans == deque.peekFirst()) {
deque.pollFirst();
}
return ans;
}
}
/**
* Your MaxQueue object will be instantiated and called as such:
* MaxQueue obj = new MaxQueue();
* int param_1 = obj.max_value();
* obj.push_back(value);
* int param_3 = obj.pop_front();
*/
剑指 Offer 37. 序列化二叉树
请实现两个函数，分别用来序列化和反序列化二叉树。
你需要设计一个算法来实现二叉树的序列化与反序列化。这里不限定你的序列 / 反序列化算法执行逻辑，你只需要保证一个二叉树可以被序列化为一个字符串并且将这个字符串反序列化为原始的树结构。
提示：输入输出格式与 LeetCode 目前使用的方式一致，详情请参阅 LeetCode 序列化二叉树的格式。你并非必须采取这种方式，你也可以采用其他的方法解决这个问题。
示例：
输入：root = [1,2,3,null,null,4,5]
输出：[1,2,3,null,null,4,5]
链接：https://leetcode-cn.com/problems/xu-lie-hua-er-cha-shu-lcof/
解法一：层序遍历
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
if (root==null){
return "[]";
}
StringBuilder sb = new StringBuilder();
sb.append("[");
Queue<TreeNode> queue = new LinkedList<>();
queue.offer(root);
while (!queue.isEmpty()){
TreeNode node = queue.poll();
if (node!=null){
queue.offer(node.left);
queue.offer(node.right);
sb.append(node.val+",");
}else{
sb.append("null,");
}
}
sb.deleteCharAt(sb.length() - 1);
sb.append("]");
return sb.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
if(data.equals("[]")) return null;
data = data.substring(1,data.length()-1);
String[] strs = data.split(",");
System.out.print(data);
TreeNode root = new TreeNode(Integer.parseInt(strs[0]));
Queue<TreeNode> queue = new LinkedList<>() {{ add(root); }};
int i = 1;
while(!queue.isEmpty()) {
TreeNode node = queue.poll();
if(!strs[i].equals("null")) {
node.left = new TreeNode(Integer.parseInt(strs[i]));
queue.add(node.left);
}
i++;
if(!strs[i].equals("null")) {
node.right = new TreeNode(Integer.parseInt(strs[i]));
queue.add(node.right);
}
i++;
}
return root;
}
}
// Your Codec object will be instantiated and called as such:
// Codec codec = new Codec();
// codec.deserialize(codec.serialize(root));
剑指 Offer 38. 字符串的排列
输入一个字符串，打印出该字符串中字符的所有排列。
你可以以任意顺序返回这个字符串数组，但里面不能有重复元素。
示例:
输入：s = "abc"
输出：["abc","acb","bac","bca","cab","cba"]
限制：
1 <= s 的长度 <= 8
链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/
解法一：回溯
class Solution {
List<String> res = new LinkedList<>();
char[] c;
public String[] permutation(String s) {
c = s.toCharArray();
dfs(0);
return res.toArray(new String[res.size()]);
}
void dfs(int x) {
if(x == c.length - 1) {
res.add(String.valueOf(c)); // 添加排列方案
return;
}
HashSet<Character> set = new HashSet<>();
for(int i = x; i < c.length; i++) {
if(set.contains(c[i])) continue; // 重复，因此剪枝
set.add(c[i]);
swap(i, x); // 交换，将 c[i] 固定在第 x 位
dfs(x + 1); // 开启固定第 x + 1 位字符
swap(i, x); // 恢复交换
}
}
void swap(int a, int b) {
char tmp = c[a];
c[a] = c[b];
c[b] = tmp;
}
}
作者：jyd
链接：https://leetcode-cn.com/problems/zi-fu-chuan-de-pai-lie-lcof/solution/mian-shi-ti-38-zi-fu-chuan-de-pai-lie-hui-su-fa-by/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
解法二：使用Set
class Solution {
public String[] permutation(String s) {
Set<String> lastSet = new HashSet<>();
lastSet.add("");
// 从1个字母到2个字母到n个字母逐步构建
for (int i = 0; i < s.length(); ++i) {
Set<String> curSet = new HashSet<>();
for (String str: lastSet) {
int n = str.length();
// 移动第i个字母的位置得到不同序列
for (int j = 0; j <= n; ++j)
curSet.add(str.substring(0, j) + s.charAt(i) + str.substring(j, n));
}
lastSet = curSet;
}
return lastSet.toArray(new String[0]);
}
}
剑指 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。
链接：https://leetcode-cn.com/problems/chou-shu-lcof/
解法一：动态规划
class Solution {
public int nthUglyNumber(int n) {
int a = 0, b = 0, c = 0;
int[] dp = new int[n];
dp[0] = 1;
for(int i = 1; i < n; i++) {
int n2 = dp[a] * 2, n3 = dp[b] * 3, n5 = dp[c] * 5;
dp[i] = Math.min(Math.min(n2, n3), n5);
if(dp[i] == n2) a++;
if(dp[i] == n3) b++;
if(dp[i] == n5) c++;
}
return dp[n - 1];
}
}
剑指 Offer 17. 打印从1到最大的n位数
输入数字 n，按顺序打印出从 1 到最大的 n 位十进制数。比如输入 3，则打印出 1、2、3 一直到最大的 3 位数 999。
示例 1:
输入: n = 1
输出: [1,2,3,4,5,6,7,8,9]
说明：
- 用返回一个整数列表来代替打印
- n 为正整数
链接：https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/
~~解法一：~~
class Solution {
public int[] printNumbers(int n) {
int len = 0;
for (int i=0;i<n;i++){
len += 9*Math.pow(10,i);
}
int[] res = new int[len];
for (int i=0;i<len;i++){
res[i] = i+1;
}
return res;
}
}
解法二：
实际上这题是要考查大数，因此应该使用字符串输出防止溢出
class Solution {
StringBuilder res;
int nine = 0, count = 0, start, n;
char[] num, loop = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9'};
public String printNumbers(int n) {
this.n = n;
res = new StringBuilder();
num = new char[n];
start = n - 1;
dfs(0);
res.deleteCharAt(res.length() - 1);
return res.toString();
}
void dfs(int x) {
if(x == n) {
String s = String.valueOf(num).substring(start);
if(!s.equals("0")) res.append(s + ",");
if(n - start == nine) start--;
return;
}
for(char i : loop) {
if(i == '9') nine++;
num[x] = i;
dfs(x + 1);
}
nine--;
}
}
作者：jyd
链接：https://leetcode-cn.com/problems/da-yin-cong-1dao-zui-da-de-nwei-shu-lcof/solution/mian-shi-ti-17-da-yin-cong-1-dao-zui-da-de-n-wei-2/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
剑指 Offer 51. 数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
示例 1:
输入: [7,5,6,4]
输出: 5
限制：
0 <= 数组长度 <= 50000
链接：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
解法一：利用归并排序
class Solution {
int res = 0;
public int reversePairs(int[] nums) {
mergeSort(nums);
return res;
}
void mergeSort(int[] nums){
sort(nums,0,nums.length-1);
}
// 分别对左右排序
void sort(int[] nums,int low,int high){
if (low>=high){
return;
}
int mid = low + ( high - low ) / 2;
// 对左边排序
sort(nums,low,mid);
// 对右边排序
sort(nums,mid+1,high);
// 合并有序数组
merge(nums,low,mid,high);
}
// 合并
void merge(int[] nums,int low,int mid,int high){
// 暂时保存数组
int[] temp = new int[high-low+1];
int i = 0;
int l = low;
int m = mid+1;
// 从有序数组中挑选最小的放入temp中
while (l<=mid&&m<=high){
if(nums[l] <= nums[m]){
temp[i++] = nums[l++];
}else{
// 统计逆序数
//当左边数组的大与右边数组的元素时，统计当前元素以及后面的元素的个数
//此时这个数就是逆序数
// 例如：7，5，6，4 划分左右排序为5，7和4，6；5大于4逆序数为3，7大于6，逆序数为2
res += (mid - l + 1);
temp[i++] = nums[m++];
}
}
// 处理未被放入的元素
while (l<=mid){
temp[i++] = nums[l++];
}
while (m<=high){
temp[i++] = nums[m++];
}
// 将排序后的序列放回原序列
System.arraycopy(temp,0,nums,low,temp.length);
}
}
官方题解：https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/solution/shu-zu-zhong-de-ni-xu-dui-by-leetcode-solution/