我是靠谱客的博主 俭朴短靴，最近开发中收集的这篇文章主要介绍剑指offer30天重刷剑指OFFER 二刷Day1：栈与队列（简单）Day2：链表（简单）Day3：字符串（简单）Day4：查找算法（简单）Day5：查找算法（中等）Day6：搜索与回溯算法（简单）Day7：搜索与回溯算法（简单）Day8：动态规划（简单）Day9：动态规划（中等）Day10：动态规划（中等）Day11：双指针（简单）Day 12：双指针（简单）Day 13：双指针（简单）Day 14：搜索与回溯算法（中等）Day 15：搜索与回溯算法（中等）Day 16：排序（简单）Day ，觉得挺不错的，现在分享给大家，希望可以做个参考。
概述
剑指OFFER 二刷
分类：桶排序
题号：【46】
Day1：栈与队列（简单）
【09】用两个栈实现队列
剑指 Offer 09. 用两个栈实现队列
// 栈本质上就是队列，遇到栈通通用Deque来
class CQueue {
Deque<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();
}
}
【30】包含min函数的栈
剑指 Offer 30. 包含min函数的栈
class MinStack {
Deque<Integer> stack;
Deque<Integer> help;
/** initialize your data structure here. */
public MinStack() {
stack = new LinkedList<>();
help = new LinkedList<>();
}
// public void push(int x) {
// stack.addLast(x);
// if(help.isEmpty()) {
// help.addLast(x);
// } else {
// int tmp = help.peekLast();
// if(x <= tmp) {
// help.addLast(x);
// } else {
// help.addLast(tmp);
// }
// }
// }
// 对上面逻辑的整合
public void push(int x) {
stack.addLast(x);
if(help.isEmpty() || x <= help.peekLast()) {
help.addLast(x);
} else {
help.addLast(help.peekLast());
}
}
public void pop() {
stack.removeLast();
help.removeLast();
}
public int top() {
return stack.peekLast();
}
public int min() {
return help.peekLast();
}
}
Day2：链表（简单）
【06】从尾到头打印链表
剑指 Offer 06. 从尾到头打印链表
// 1. 递归法
class Solution {
List<Integer> list = new ArrayList<>();
public int[] reversePrint(ListNode head) {
if(head == null) return new int[]{};
search(head,list);
int[] arr = new int[list.size()];
for(int i = 0; i < list.size(); i++){
arr[i] = list.get(i);
}
return arr;
}
public void search(ListNode cur, List<Integer> List) {
if(cur == null) return;
// 开始下一次
search(cur.next,list);
// 回到本体
list.add(cur.val);
}
}
// 2. 栈
class Solution {
public int[] reversePrint(ListNode head) {
Deque<Integer> stack = new LinkedList<>();
while(head != null) {
stack.addLast(head.val);
head = head.next;
}
int[] arr = new int[stack.size()];
for(int i = 0; i < arr.length; i++) {
arr[i] = stack.removeLast();
}
return arr;
}
}
【24】反转链表
剑指 Offer 24. 反转链表
class Solution {
ListNode newHead;
public ListNode reverseList(ListNode head) {
if(head == null) return null;
reverse(head);
return newHead;
}
public ListNode reverse(ListNode head) {
if(head.next == null) {
newHead = head;
return head;
}
ListNode nextNode = head.next;
ListNode newPre = reverse(nextNode);
newPre.next = head;
head.next = null;
return head;
}
}
【35】复杂链表的复制
剑指 Offer 35. 复杂链表的复制
/*
// Definition for a Node.
class Node {
int val;
Node next;
Node random;
public Node(int val) {
this.val = val;
this.next = null;
this.random = null;
}
}
*/
// 方法一：构建A-A'-B-B'-C-C'
class Solution {
public Node copyRandomList(Node head) {
if(head == null) return null;
// 1. 构建A-A'-B-B'-C-C'，初始化新节点的val
Node p = head;
while(p != null) {
Node node = new Node(p.val);
node.next = p.next;
p.next = node;
p = node.next;
}
// 2. 构建random
p = head;
while(p != null) {
if(p.random != null){
p.next.random = p.random.next;
}
p = p.next.next;
}
// 3. 拆分，构建next
p = head.next;
Node pre = head;
Node res = head.next;
while(p.next!=null) {
pre.next = pre.next.next;
p.next = p.next.next;
pre=pre.next;
p=p.next;
}
pre.next = null;
return res;
}
}
// 方法二：HashMap先存好新节点的地址。
class Solution {
public Node copyRandomList(Node head) {
if(head == null) return null;
Node cur = head;
Map<Node, Node> map = new HashMap<>();
// 3. 复制各节点，并建立 “原节点 -> 新节点” 的 Map 映射
while(cur != null) {
map.put(cur, new Node(cur.val));
cur = cur.next;
}
cur = head;
// 4. 构建新链表的 next 和 random 指向
while(cur != null) {
// map.get(cur) 是我们 复制完的链表中的Node结构
map.get(cur).next = map.get(cur.next);
map.get(cur).random = map.get(cur.random);
cur = cur.next;
}
// 5. 返回新链表的头节点
return map.get(head);
}
}
Day3：字符串（简单）
【05】替换空格
剑指 Offer 05. 替换空格
class Solution {
public String replaceSpace(String s) {
// 如果是连续的空格“ ”，split后的长度也是0
int len = s.length();
StringBuffer ans = new StringBuffer();
// 1. 处理每一个空格
for(int i = 0; i < len; i++) {
if(s.charAt(i) == ' ') {
ans.append('%');
ans.append('2');
ans.append('0');
} else {
ans.append(s.charAt(i));
}
}
return new String(ans);
}
}
【58】左旋转字符串
class Solution {
public String reverseLeftWords(String s, int n) {
// 1. 原字符串分成2个部分
// 子串part1：索引[n~length-1];
// 子串part2: 索引[0~n-1]
StringBuffer ans = new StringBuffer();
ans.append(s.substring(n,s.length()));
ans.append(s.substring(0,n)); //[0~n-1], substring()是左开右闭的，因此是substring(0,n)
return ans.toString();
}
}
Day4：查找算法（简单）
【03】数组中重复的数字
剑指 Offer 03. 数组中重复的数字
Method1：归位法==【优解】==
// 时间复杂度：O(n); 空间复杂度:O(1)；原数组：修改
/**
题目条件：在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内
一个数 X=nums[i] 一定有一个索引位置 X 是 nums[i] 对应的
*/
class Solution {
public int findRepeatNumber(int[] nums) {
int i = 0;
while(i < nums.length) {
if(nums[i] == i) {
i++;
continue;
}
// 一直换索引i，直到换到一个该索引应该存在的值
if(nums[nums[i]] == nums[i]) return nums[i];
int tmp = nums[i];
nums[i] = nums[tmp];
nums[tmp] = tmp;
}
return -1;
}
}
Method2：二分搜索+遍历【看下剑指OFFER原书】
此方法跟本题题目条件有些不一样
// 时间复杂度O(n), 空间复杂度O(1), 原数组：修改
class Solution {
//方法5：对0到n-1进行二分查找，时间O(nlogn)，空间O(1)，不修改原数据，用时间换空间
//该方法需要数字一定有重复的才行，因此如果题目修改在长度为n，数字在1到n-1的情况下，此时数组中至少有一个数字是重复的，该方法可以通过。
public int findRepeatNumber(int[] nums) {
//统计nums中元素位于0到m的数量，如果数量大于这个值，那么重复的元素肯定是位于0到m的
int min = 0 ;
int max = nums.length-1;
while(min<max){
int mid = (max+min)>>1;
int count = countRange(nums,min,mid);
if(count > mid-min+1) {
max = mid;
}else{
min = mid+1;
}
}
//最后min=max
return min;
}
//统计范围内元素数量,时间O(n)
private int countRange(int[] nums,int min,int max){
int count = 0 ;
for(int num:nums){
if(num>=min && num<=max){
count++;
}
}
return count;
}
}
Method3：哈希表+遍历
// 时间复杂度：O(n); 空间复杂度:O(n)；原数组：不修改
class Solution {
public int findRepeatNumber(int[] nums) {
Set<Integer> dic = new HashSet<>();
for(int num : nums) {
if(dic.contains(num)) return num;
dic.add(num);
}
return -1;
}
}
Method4：排序+指针遍历
// 时间：O(nlogn)；空间：O(1)：原数组：修改
class Solution {
public int findRepeatNumber(int[] nums) {
Arrays.sort(nums);
int slow = 0;
int fast = 1;
while(fast != nums.length){
if(nums[slow] == nums[fast]){
return nums[slow];
}
slow++;
fast++;
}
return -1;
}
}
【53-I】在排序数组中查找数字 I
剑指 Offer 53 - I. 在排序数组中查找数字 I
class Solution {
public int search(int[] nums, int target) {
if(nums.length == 0) return 0;
// 二分查找，<=7 的范围, return r
int l = -1;
int r = nums.length;
while(l+1!=r) {
int mid = (l+r) >> 1;
if(nums[mid] <= target-1) {
l = mid;
} else {
r = mid;
}
}
// 特殊边界值处理：因为最终用的是指针r，故处理r就好。
// r一直没动在右边 或 r停下来不是target，即原来就没有target
// 直接return 0
// 情况1.没有target
if(r == nums.length || nums[r] != target) return 0;
// 情况2. 有target
int ans = 0;
while(r < nums.length) {
if(nums[r] == target){
ans++;
}
r++;
}
return ans;
}
}
【53-II】在排序数组中查找数字 II
剑指 Offer 53 - II. 0～n-1中缺失的数字
class Solution {
public int missingNumber(int[] nums) {
// 合法情况：nums[mid] == mid
// 不合法情况：nums[mid] != mid
int l = -1;
int r = nums.length;
while(l+1!=r) {
int mid = (l + r) >> 1;
if(nums[mid] == mid) {
l = mid;
} else {
r = mid;
}
}
return r;
}
}
Day5：查找算法（中等）
【04】二维数组中查找
剑指 Offer 04. 二维数组中的查找
// 线性查找：从左下角or右上角开始
// 特点：搜索方向只有两个：direction 1：小于自己 ; direction 2：大于自己; 等于就直接返回
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
return false;
}
int rows = matrix.length, columns = matrix[0].length;
// 从右上角出发。
int row = 0, column = columns - 1;
while (row < rows && column >= 0) {
int num = matrix[row][column];
if (num == target) {
return true;
} else if (num > target) {
column--;
} else {
row++;
}
}
return false;
}
}
class Solution {
public boolean findNumberIn2DArray(int[][] matrix, int target) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0) return false;
int row = matrix.length;
int col = matrix[0].length;
if(matrix[0][0] > target) return false;
// 1. 二分查找[0][j]; [i][0]
// 1.1目标：<= target - 1; 返回:l
int l = -1;
int r = col;
while(l+1 != r) {
int mid = (l + r) >> 1;
if(matrix[0][mid] <= target) {
l = mid;
} else {
r = mid;
}
}
// return l, l 一定有
if(matrix[0][l] == target) return true;
// 记录最终搜索的最大 列索引
int n = l;
l = -1;
r = row;
while(l+1 != r) {
int mid = (l + r) >> 1;
if(matrix[mid][0] <= target) {
l = mid;
} else {
r = mid;
}
}
// return l
if(matrix[l][0] == target) return true;
// 记录最终搜索的最大 行索引
int m = l;
for(int i = 0; i <= m; i++) {
for(int j = 0; j <= n; j++) {
if(matrix[i][j] == target) {
return true;
}
}
}
return false;
}
}
【11】旋转数组的最小数字
剑指 Offer 11. 旋转数组的最小数字
// O(n)
class Solution {
public int minArray(int[] numbers) {
if(numbers.length == 1) return numbers[0];
int slow = 0, fast = 1;
while(fast < numbers.length) {
if( numbers[slow] > numbers[fast]) {
return numbers[fast];
}
slow++;
fast++;
}
return numbers[0];
}
}
【50】第一个只出现一次的字符
剑指 Offer 50. 第一个只出现一次的字符
class Solution {
// false：出现多次；true：仅出现一次
Map<Character,Boolean> map = new HashMap<>();
public char firstUniqChar(String s) {
if(s.length() == 0) return ' ';
if(s.length() == 1) return s.charAt(0);
for(int i = 0; i < s.length(); i++) {
char tmp = s.charAt(i);
// if(!map.containsKey(tmp)) {
// map.put(tmp, true);
// } else {
// map.put(tmp, false);
// }
map.put(tmp,!map.containsKey(tmp));
}
for(int i = 0; i < s.length(); i++) {
if(map.get(s.charAt(i)) == true) return s.charAt(i);
}
return ' ';
}
}
Day6：搜索与回溯算法（简单）
【32】从上到下打印二叉树
剑指 Offer 32 - I. 从上到下打印二叉树
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public int[] levelOrder(TreeNode root) {
if(root == null) return new int[]{};
ArrayList<TreeNode> list = new ArrayList<>();
Deque<TreeNode> queue = new ArrayDeque<>();
queue.addLast(root);
while(!queue.isEmpty()) {
int size = queue.size();
for(int i = 0; i < size; i++) {
TreeNode node = queue.removeFirst();
list.add(node);
if(node.left != null) queue.addLast(node.left);
if(node.right != null) queue.addLast(node.right);
}
}
int[] ans = new int[list.size()];
for(int i = 0; i < ans.length; i++) {
// 取出节点，放入节点的值val
ans[i] = list.get(i).val;
}
return ans;
}
}
【32-II】从上到下打印二叉树 II
剑指 Offer 32 - II. 从上到下打印二叉树 II
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if(root == null) return ans;
Deque<TreeNode> queue = new ArrayDeque<>();
queue.addLast(root);
while(!queue.isEmpty()) {
int size = queue.size();
List<Integer> list = new ArrayList<>();
for(int i = 0; i < size; i++) {
TreeNode node = queue.removeFirst();
list.add(node.val);
if(node.left != null) queue.addLast(node.left);
if(node.right != null) queue.addLast(node.right);
}
ans.add(new ArrayList(list));
}
return ans;
}
}
【32-III】从上到下打印二叉树 III
剑指 Offer 32 - III. 从上到下打印二叉树 III
class Solution {
public List<List<Integer>> levelOrder(TreeNode root) {
List<List<Integer>> ans = new ArrayList<>();
if(root == null) return ans;
Deque<TreeNode> queue = new ArrayDeque<>();
queue.addLast(root);
boolean flag = false;
while(!queue.isEmpty()) {
int size = queue.size();
Deque<Integer> list = new ArrayDeque<>();
for(int i = 0; i < size; i++) {
TreeNode node = queue.removeFirst();
// 关键点：改变入队列的方式，
if(flag){ // 从头
list.addFirst(node.val);
} else { // 从尾
list.addLast(node.val);
}
if(node.left != null) queue.addLast(node.left);
if(node.right != null) queue.addLast(node.right);
}
flag = !flag;
ans.add(new ArrayList(list));
}
return ans;
}
}
Day7：搜索与回溯算法（简单）
【26】数的子结构
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
// 自己写的
class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
if(A==null || B==null) return false;
// A中节点对上了，才开始移动 节点B
if(A.val == B.val && help(A,B)) return true;
return isSubStructure(A.left, B) || isSubStructure(A.right,B);
}
public boolean help(TreeNode n1, TreeNode n2) {
if(n1 ==null && n2 == null) return true; // n1、n2 同时为 null
if(n2 == null) return true; // n2 为null，表示先遍历完了
if(n1 == null) return false; // n2 不为null，n1 为null
if(n1.val != n2.val) return false;
return help(n1.left,n2.left) && help(n1.right,n2.right);
}
}
class Solution {
//先序遍历树 A 中的每个节点 n_A
public boolean isSubStructure(TreeNode A, TreeNode B) {
if (B == null || A == null) {
return false;
}
//若，当前两个“根结点”匹配成功
if (A.val == B.val && (recur(A.left, B.left) && recur(A.right, B.right))) {
return true;
}
//此时，当前两个“根结点”没匹配成功，则继续遍历后续结点
//往左右两边的子树再开始寻找
return isSubStructure(A.left, B) || isSubStructure(A.right, B);
}
//判断树 A 中 以 n_A 为根节点的子树 是否包含树 B
private boolean recur(TreeNode root1, TreeNode root2) {
//roo2 == null, 说明搜索roo2所在的子树的某一边已经被遍历完了
if (root2 == null) {
return true;
}
if (root1 == null) {
return false;
}
if (root1.val == root2.val) {
return recur(root1.left, root2.left) && recur(root1.right, root2.right);
} else {
return false;
}
}
}
【27】二叉树的镜像
剑指 Offer 27. 二叉树的镜像
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if(root == null) return null;
help(root);
return root;
}
public void help(TreeNode node) {
// base-case：叶节点
if(node == null) return;
//
if(node.left != null) {
help(node.left);
}
//
TreeNode tmp = node.left;
//
if(node.right != null) {
help(node.right);
}
// 回到本体，改变结构
node.left = node.right;
node.right = tmp;
}
}
【28】对称的二叉树
剑指 Offer 28. 对称的二叉树
/*做递归思考三步：
递归的函数要干什么？
函数的作用是判断传入的两个树是否镜像。
输入：TreeNode left, TreeNode right
输出：是：true，不是：false
递归停止的条件是什么？
左节点和右节点都为空 -> 倒底了都长得一样 ->true
左节点为空的时候右节点不为空，或反之 -> 长得不一样-> false
左右节点值不相等 -> 长得不一样 -> false
从某层到下一层的关系是什么？
要想两棵树镜像，那么一棵树左边的左边要和二棵树右边的右边镜像，一棵树左边的右边要和二棵树右边的左边镜像
调用递归函数传入左左和右右
调用递归函数传入左右和右左
只有左左和右右镜像且左右和右左镜像的时候，我们才能说这两棵树是镜像的
调用递归函数，我们想知道它的左右孩子是否镜像，传入的值是root的左孩子和右孩子。这之前记得判个root==null。
*/
class Solution {
public boolean isSymmetric(TreeNode root) {
return root == null ? true : recur(root.left, root.right);
}
boolean recur(TreeNode L, TreeNode R) {
// 终点判断
if(L == null && R == null) return true;
// 中间过程判断；① 树长得层次不一样；② 节点值不一样
if(L == null || R == null || L.val != R.val) return false;
return recur(L.left, R.right) && recur(L.right, R.left);
}
}
Day8：动态规划（简单）
【10-I】斐波那契数列
剑指 Offer 10- I. 斐波那契数列
class Solution {
static final int MOD = 1000000007;
public int fib(int n) {
if(n == 0) return 0;
if(n == 1) return 1;
int count = 2;
int pre = 0;
int cur = 1;
int sum = 0;
while(count <= n) { // 或者写成for(int i =2;i<=n;i++){}
sum = (pre+cur)%MOD;
pre = cur;
cur = sum;
count++;
}
return sum;
}
}
// 一种数学上的方法
class Solution {
static final int MOD = 1000000007;
public int fib(int n) {
if (n < 2) {
return n;
}
int[][] q = {{1, 1}, {1, 0}};
int[][] res = pow(q, n - 1);
return res[0][0];
}
public int[][] pow(int[][] a, int n) {
int[][] ret = {{1, 0}, {0, 1}};
while (n > 0) {
if ((n & 1) == 1) {
ret = multiply(ret, a); // 保留当前参与平方操作的，底数的内容
}
n >>= 1; // n /= 2;
a = multiply(a, a);
}
return ret;
}
public int[][] multiply(int[][] a, int[][] b) {
int[][] c = new int[2][2];
for (int i = 0; i < 2; i++) {
for (int j = 0; j < 2; j++) {
c[i][j] = (int) (((long) a[i][0] * b[0][j] + (long) a[i][1] * b[1][j]) % MOD);
}
}
return c;
}
}
【10-II】青蛙跳台阶问题
剑指 Offer 10- II. 青蛙跳台阶问题
class Solution {
static final int MOD = 1000000007;
public int numWays(int n) {
if(n==0) return 1;
if(n==1) return 1;
// n 从2开始
// 初始化
int pre = 1; // f(0)
int cur = 1; // f(1)
int sum = 0;
for(int i = 2; i <= n; i++){
sum = (pre+cur)%MOD;
pre = cur;
cur = sum;
}
return sum;
}
}
【63】股票的最大利润
剑指 Offer 63. 股票的最大利润
class Solution {
public int maxProfit(int[] prices) {
if(prices.length == 0) return 0;
// 1. 记录局部最小买入价，初始化为prices[0]
int localMin = prices[0]; // 更新时机：当前买入价 < 局部最小买入价，更新。
// 2. 记录最大利润
int maxProfit = 0; // 更新时机：当前买入价 > 局部最小买入价，可以交易。
for(int i = 1; i<prices.length;i++) {
// if(prices[i] < localMin) {
// localMin = prices[i];
// continue;
// }
// 等效
localMin = Math.min(localMin,prices[i]);
maxProfit = Math.max(maxProfit, prices[i] - localMin);
}
return maxProfit;
}
}
Day9：动态规划（中等）
【42】连续子数组的最大和
剑指 Offer 42. 连续子数组的最大和
class Solution {
public int maxSubArray(int[] nums) {
/**
维护变量：subSum，维护子数组的和
连续子数组 起始位置：start，初始化为 0
更新时机：if subSum < 0，那么更新start为当前nums[i]
同时更新subSum为nums[i]
连续子数组 结束位置：i
*/
// base-case
if(nums.length == 0) return 0;
int finalSum = nums[0];
int subSum = nums[0];
for(int i = 1; i < nums.length; i++) {
// if(subSum < 0) {
// subSum = nums[i];
// finalSum = Math.max(subSum,finalSum);
// continue;
// }
// subSum += nums[i];
// finalSum = Math.max(subSum,finalSum);
// 优化上述代码
subSum = Math.max(subSum, 0);
subSum += nums[i];
finalSum = Math.max(subSum,finalSum);
}
return finalSum;
}
}
【47】礼物的最大价值
剑指 Offer 47. 礼物的最大价值
class Solution {
public int maxValue(int[][] grid) {
if(grid.length == 0) return 0;
int rows = grid.length;
int cols = grid[0].length;
// int ans = grid[0][0];
// 直接修改原数组，节省空间复杂度
// // 1. 初始化第一行
// for(int j = 1; j < cols; j++) {
// grid[0][j] += grid[0][j-1];
// }
// // 2. 初始化第一列
// for(int i = 1; i < rows; i++) {
// grid[i][0] += grid[i-1][0];
// }
// 特殊情况：只有一行或者一列
// if(rows == 1) return grid[0][cols-1];
// if(cols == 1) return grid[rows-1][0];
// 3. 从 grid[1][1] 开始走 i=1;j=1 开始
// 优化了上述代码，把for循环写到了一起
for(int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) {
if(i==0&&j==0) continue;
if(i==0){
grid[i][j] += grid[i][j-1];
} else if (j==0) {
grid[i][j] += grid[i-1][j];
} else {
grid[i][j] += Math.max(grid[i-1][j],grid[i][j-1]);
}
}
}
return grid[rows-1][cols-1];
}
}
Day10：动态规划（中等）
【46】把数字翻译成字符串
剑指 Offer 46. 把数字翻译成字符串
递归法1：需要转成字符串操作
-
String.valueOf();
-
substring();
-
compareTo(“数字”);
class Solution {
public int translateNum(int num) {
//将字符串转化为数字
String str = String.valueOf(num);
//dfs遍历字符串求解
return dfs(str, 0);
}
//表示从index位置开始有好多种翻译方法
public int dfs(String str, int index){
// base-case: 倒数第二个 走一步到 倒数第一个 或者 倒数第二个走两步走到外边儿了
if(index == str.length() - 1 || index ==str.length())
return 1;
int res = dfs(str, index + 1);
//以当前字符的下标为开始，截取两位，判断这位组成的数字是否在10~25之间，防止“06”这样的两位数
//如果在这一次就可以直接翻译两个字符，然后从两个字符后面的位置开始翻译
String temp = str.substring(index, index + 2);
if(temp.compareTo("10") >= 0 && temp.compareTo("25") <= 0)
res += dfs(str, index + 2);
return res;
}
}
递归法2：直接对int进行操作
// 方法2：不用转成字符串
class Solution {
public int translateNum(int num) {
if (num < 10) {
return 1;
}
int re = num % 100; // 天然处理了12208 后面 08 这样的子部分；而在字符串中则需要递归法1的compareTo实现
if (re < 10 || re >25) { // 不能合成2个单个数字
return translateNum(num / 10);
} else { // 10<= 且 <=25 之间，可以合成 2个 单个数字
return translateNum(num / 10) + translateNum(num / 100);
}
}
}
动态规划法
class Solution {
public int translateNum(int num) {
String s = String.valueOf(num);
int[] dp = new int[s.length()+1];
dp[0] = 1;
dp[1] = 1;
for(int i = 2; i <= s.length(); i ++){
String temp = s.substring(i-2, i);
if(temp.compareTo("10") >= 0 && temp.compareTo("25") <= 0)
dp[i] = dp[i-1] + dp[i-2];
else
dp[i] = dp[i-1];
}
return dp[s.length()];
}
}
class Solution {
public int translateNum(int num) {
String s = String.valueOf(num);
int pre = 1;
int cur = 1;
int sum;
for(int i = 2; i <= s.length(); i ++){
String temp = s.substring(i-2, i);
if(temp.compareTo("10") >= 0 && temp.compareTo("25") <= 0) {
sum = pre + cur;
pre = cur;
cur = sum;
} else {
pre = cur;
cur = pre;
}
}
return cur;
}
}
【48】最长不含重复字符的子字符串
本题需要考虑的特殊样例：
“abba"
“dvdfq”
剑指 Offer 48. 最长不含重复字符的子字符串
// 优化后
// space: O(1)；字符的 ASCII 码范围为 0 ~ 127 ，哈希表 dic 最多使用 O(128) = O(1)大小的额外空间。
// time: O(n)
class Solution {
public int lengthOfLongestSubstring(String s) {
/**
HashSet：维护当前子串
更新条件：查询hashset，contains当前元素
更新操作：① 清空hashset；② put 当前元素
maxLen：维护 全局最大 长度
更新条件：hashset被清空的时候
更新操作：Math.max(hashset.size(), maxLen)
subLen：子串的长度，
*/
if(s == null) return 0;
if(s.length() == 0) return 0;
int len = s.length();
int maxLen = 0;
int subStart = 0;
HashMap<Character,Integer> map = new HashMap<>();
for(int i = 0; i < len;i++) {
char tmp = s.charAt(i);
if(map.getOrDefault(tmp, len) < i) { // 不存在返回len（任意一个不存在的索引），是为了解决当hashmap中没有当前元素的情况。
// 更新左边界还要求 比一直记录的subStart要大于等于，不然就不是记录当前真实子串了
if(map.get(tmp) >= subStart) { // 等于是为了第一次subStart=0的时候也能正常执行。
subStart = map.get(tmp) + 1;
}
}
map.put(tmp, i);
maxLen = Math.max(maxLen, i-subStart+1);
}
return maxLen;
}
}
// 毫无优化
class Solution {
public int lengthOfLongestSubstring(String s) {
/**
HashSet：维护当前子串
更新条件：查询hashset，contains当前元素
更新操作：① 清空hashset；② put 当前元素
maxLen：维护 全局最大 长度
更新条件：hashset被清空的时候
更新操作：Math.max(hashset.size(), maxLen)
subLen：子串的长度，
pre：记录重复元素上一次出现的位置
*/
if(s == null) return 0;
if(s.length() == 0) return 0;
int maxLen = 0;
int subLen = 0;
HashMap<Character,Integer> map = new HashMap<>();
for(int i = 0; i < s.length();) {
char tmp = s.charAt(i);
if(map.containsKey(tmp)) {
int lastPostion = map.get(tmp);
map.clear();
subLen = 0;
i = lastPostion + 1;
} else {
map.put(tmp,i);
subLen++;
maxLen = Math.max(subLen, maxLen);
// 循环步长控制
i++;
}
}
return maxLen;
}
}
Day11：双指针（简单）
【18】删除链表的节点
剑指 Offer 18. 删除链表的节点
class Solution {
public ListNode deleteNode(ListNode head, int val) {
if(head == null) return null;
if(head.val == val) return head.next;
ListNode p = head;
while(p.next != null) {
if(p.next.val == val) {
p.next = p.next.next;
break;
}
p = p.next;
}
return head;
}
}
【22】链表中倒数第k个节点
Method1：双指针（优解）
// 双指针，两个指针【间隔 k 步】，当【快指针】到null时，慢指针刚好指到【倒数第k个节点】
// space：O(1)
// time：O(n)
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
ListNode fast = head, slow = head;
for(int i = 1; i <= k; i++) {
fast = fast.next;
}
while(fast != null) {
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
Method：利用栈
// 用一个 栈 倒出来
// space：O(n)
// time：O(n)
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
Deque<ListNode> stack = new ArrayDeque<>();
ListNode p = head;
while(p != null) {
stack.addLast(p);
p = p.next;
}
for(int i = 1; i <= k; i++) {
p = stack.removeLast();
}
return p;
}
}
Day 12：双指针（简单）
【25】合并两个排序的链表
剑指 Offer 25. 合并两个排序的链表
/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode(int x) { val = x; }
* }
*/
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
if(l1 == null && l2 == null) return null;
if(l1 == null && l2 != null) return l2;
if(l1 != null && l2 == null) return l1;
ListNode dummy = new ListNode(0);
ListNode cur = dummy;
// 1. 循环结束时：其中一个遍历完了
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;
}
// 2. 串联剩下的，不用遍历的。
cur.next = l1 == null ? l2 : l1;
return dummy.next;
}
}
【52】两个链表的第一个公共节点
剑指 Offer 52. 两个链表的第一个公共节点
Method 1：优解，非常之漂亮
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) {
return null;
}
ListNode pA = headA, pB = headB;
while (pA != pB) {
pA = pA == null ? headB : pA.next;
pB = pB == null ? headA : pB.next;
}
return pA;
}
}
Method 2：常规想法
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null) return null;
int lenA = 0, lenB = 0;
ListNode pA = headA;
ListNode pB = headB;
// 1. 计算长度
while(pA != null) { pA = pA.next; lenA++;}
while(pB != null) { pB = pB.next; lenB++;}
// 2. 调整到长度一致的位置
int diff = Math.abs(lenA - lenB);
if(lenA < lenB) {
for(int i = 0; i < diff; i++) {
headB = headB.next;
}
} else {
for(int i = 0; i < diff; i++) {
headA = headA.next;
}
}
// 3. 开始寻找
while(headA != null) {
if(headA == headB) return headA;
headA = headA.next;
headB = headB.next;
}
return null;
}
}
Day 13：双指针（简单）
【21】调整数组顺序使奇数位于偶数前面
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
class Solution {
public int[] exchange(int[] nums) {
int l = 0, r = nums.length; // r指向偶数区域
while(l < r) {
// l 遇到奇数 l++；l 遇到偶数，跟(r--)进行交换，l不++
if(nums[l] % 2 == 0) {
swap(nums,l,--r);
} else {
l++;
}
}
return nums;
}
public static void swap(int[] nums, int l, int r) {
if(nums == null) return;
int tmp = nums[l];
nums[l] = nums[r];
nums[r] = tmp;
}
}
【57】和为s的两个数字
剑指 Offer 57. 和为s的两个数字
class Solution {
public int[] twoSum(int[] nums, int target) {
int i = 0, j = nums.length - 1;
while(i < j) {
int s = nums[i] + nums[j];
if(s < target) i++;
else if(s > target) j--;
else return new int[] { nums[i], nums[j] };
}
return new int[0];
}
}
区分另一道题
1. 两数之和
要求返回的是【元素索引】，因为原数组不是有序排列的，因此不能sort，sort之后就改变了索引的对应关系。
Method1：哈希表
class Solution {
public int[] twoSum(int[] nums, int target) {
Map<Integer, Integer> map = new HashMap<>();
for(int i = 0; i< nums.length; i++) {
if(map.containsKey(target - nums[i])) {
return new int[] {map.get(target-nums[i]),i};
}
map.put(nums[i], i);
}
throw new IllegalArgumentException("No two sum solution");
}
}
【58-I】翻转单词顺序
剑指 Offer 58 - I. 翻转单词顺序
class Solution {
public String reverseWords(String s) {
String[] strs = s.trim().split(" "); // 删除首尾空格，分割字符串
StringBuilder res = new StringBuilder();
for(int i = strs.length - 1; i >= 0; i--) { // 倒序遍历单词列表
// 问题 //if(strs[i] == "") continue;
if(strs[i].equals("")) continue; // 遇到空单词则跳过
res.append(strs[i] + " "); // 将单词拼接至 StringBuilder
}
return res.toString().trim(); // 转化为字符串，删除尾部空格，并返回
}
}
一个严肃的问题
if(strs[i] == "") continue;
== 用于基础类型判断值；
此时，右侧""是一个字面量，左侧strs[i]拿到的是一个对象，String 类；不是基础数据类型。
这里 == 比较的是 对象地址
Day 14：搜索与回溯算法（中等）
【12】矩阵中的路径
剑指 Offer 12. 矩阵中的路径
class Solution {
int rows;
int cols;
public boolean exist(char[][] board, String word) {
rows = board.length;
cols = board[0].length;
boolean[][] vis = new boolean[rows][cols];
for(int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) {
if(dfs(board,word,vis,0,i,j)) return true;
}
}
return false;
}
public boolean dfs(char[][] board, String word, boolean[][] vis, int targetIndex, int i, int j) {
// base-case
if(targetIndex == word.length()) return true;
// 越界
if(i<0 || j<0 || i > rows-1 || j > cols-1 || vis[i][j]) return false;
// 目标不符合
if(board[i][j] != word.charAt(targetIndex)) return false;
boolean res = false;
// 合法条件，接下来是符合board[i][j] == word.charAt(targetIndex)
vis[i][j] = true;
res = dfs(board,word,vis,targetIndex+1,i+1,j) || dfs(board,word,vis,targetIndex+1,i-1,j) || dfs(board,word,vis,targetIndex+1,i,j+1) || dfs(board,word,vis,targetIndex+1,i,j-1);
vis[i][j] = false;
return res;
}
}
优化上面的代码
思路：不建立 boolean 二维数组 visited，直接再board原数组上进行修改
区别1：做选择时，用’ ’修改board；撤销选择时，用 当前寻找的字符替代回去。
区别2：原来判断非法要比较vis【i】【j】是不是true（即，被选择过的）
现在if(board[i][j] != word.charAt(targetIndex)) return false; 不仅实现了比较是不是要的开头，而且比较了是不是被选择过的
class Solution {
int rows;
int cols;
public boolean exist(char[][] board, String word) {
rows = board.length;
cols = board[0].length;
for(int i = 0; i < rows; i++) {
for(int j = 0; j < cols; j++) {
if(dfs(board,word,0,i,j)) return true;
}
}
return false;
}
public boolean dfs(char[][] board, String word, int targetIndex, int i, int j) {
// base-case
if(targetIndex == word.length()) return true;
// 越界
if(i<0 || j<0 || i > rows-1 || j > cols-1) return false;
if(board[i][j] != word.charAt(targetIndex)) return false;
// 合法条件，接下来是符合board[i][j] == word.charAt(targetIndex)
board[i][j] = ' ';
boolean res = dfs(board,word,targetIndex+1,i+1,j) || dfs(board,word,targetIndex+1,i-1,j) || dfs(board,word,targetIndex+1,i,j+1) || dfs(board,word,targetIndex+1,i,j-1);
board[i][j] = word.charAt(targetIndex);
return res;
}
}
【13】机器人的运动范围
① DFS
class Solution {
boolean[][] vis;
public int movingCount(int m, int n, int k) {
vis = new boolean[m][n];
return dfs(0,0,m,n,k);
}
public int dfs (int x, int y, int m, int n, int k) {
// base-case
// 越界
if(x<0 || y<0 || x>=m || y >=n || vis[x][y] || !checkSum(x,y,k)) return 0;
vis[x][y] = true;
return 1 + dfs(x+1,y,m,n,k) + dfs(x-1,y,m,n,k) + dfs(x,y+1,m,n,k) + dfs(x,y-1,m,n,k);
}
public boolean checkSum(int i, int j, int k) {
int sum = 0;
while(i != 0) {
sum += (i%10);
i /= 10;
}
while(j != 0) {
sum += (j % 10);
j /= 10;
}
if(sum > k) return false;
else return true;
}
}
② BFS
class Solution {
public int movingCount(int m, int n, int k) {
boolean[][] visited = new boolean[m][n];
int res = 0;
Queue<int[]> queue = new LinkedList<int[]>();
// 1. 初始化起点【】【】
queue.offer(new int[]{0, 0});
while (queue.size() > 0) {
int[] x = queue.poll();
int i = x[0], j = x[1];
//排除非法选择,因为机器人走路的途中（中间过程）受条件控制，他不会去走，因此我们就不统计它。
//这与我们找路径的终点条件判断有所区别
//这里，当queue.size() = 0 时，就表示到终点。
if (i >= m || j >= n || visited[i][j] != false || sum(i, j) > k) continue;
visited[i][j] = true;
res++;
queue.offer(new int[]{i + 1, j});
queue.offer(new int[]{i, j + 1});
}
return res;
}
// 计算两个坐标数字的和
private int sum(int i, int j) {
int sum = 0;
while (i != 0) {
sum += i % 10;
i /= 10;
}
while (j != 0) {
sum += j % 10;
j /= 10;
}
return sum;
}
}
Day 15：搜索与回溯算法（中等）
【34】二叉树中和为某一值的路径
剑指 Offer 34. 二叉树中和为某一值的路径
① 到叶节点，叶节点为剩余和
class Solution {
List<List<Integer>> res = new ArrayList<>();
Deque<Integer> queue = new ArrayDeque<>();
public List<List<Integer>> pathSum(TreeNode root, int target) {
if(root == null) return res;
dfs(root,target);
return res;
}
public void dfs(TreeNode node, int targetSum) {
// base-case：null节点
if(node == null) return;
// 子节点时候，合法性判断
if(node.left == null && node.right == null && targetSum == node.val) {
queue.addLast(node.val);
res.add(new ArrayList(queue));
queue.removeLast();
return;
}
// do
queue.addLast(node.val);
dfs(node.left,targetSum-node.val);
dfs(node.right,targetSum-node.val);
// redo
queue.removeLast();
}
}
② 到叶节点，加入它后，剩余和为0
class Solution {
LinkedList<List<Integer>> res = new LinkedList<>();
LinkedList<Integer> path = new LinkedList<>();
public List<List<Integer>> pathSum(TreeNode root, int sum) {
recur(root, sum);
return res;
}
void recur(TreeNode root, int tar) {
if(root == null) return;
path.add(root.val);
tar -= root.val;
if(tar == 0 && root.left == null && root.right == null)
res.add(new LinkedList(path));
recur(root.left, tar);
recur(root.right, tar);
path.removeLast();
}
}
【36】二叉搜索树与双向链表
剑指 Offer 36. 二叉搜索树与双向链表
-
关键点
用一个pre 节点记录每一个节点的先继节点，
/*
// Definition for a Node.
class Node {
public int val;
public Node left;
public Node right;
public Node() {}
public Node(int _val) {
val = _val;
}
public Node(int _val,Node _left,Node _right) {
val = _val;
left = _left;
right = _right;
}
};
*/
class Solution {
Node head, pre;
public Node treeToDoublyList(Node root) {
if(root==null) return null;
dfs(root);
pre.right = head;
head.left =pre;//进行头节点和尾节点的相互指向，这两句的顺序也是可以颠倒的
return head;
}
public void dfs(Node cur){
if(cur==null) return;
dfs(cur.left);
// pre 记录先继节点
if(pre==null) head = cur;
//反之，pre!=null时，cur左侧存在节点pre，需要进行pre.right=cur的操作。
else pre.right = cur;
cur.left = pre;//pre是否为null对这句没有影响,且这句放在上面两句if else之前也是可以的。
pre = cur;//pre指向当前的cur
dfs(cur.right);//全部迭代完成后，pre指向双向链表中的尾节点
}
}
【54】二叉搜索树的第k大节点
剑指 Offer 54. 二叉搜索树的第k大节点
// space: O(1)
// time: O(k)
class Solution {
int ans = 0;
int count = 0;
public int kthLargest(TreeNode root,int k) {
count = k;
postOrder(root);
return ans;
}
// 右中左，保证递减的顺序访问：后序遍历
public void postOrder(TreeNode node) {
if(node == null) return;
postOrder(node.right);
// 本体
if(--count == 0) {
ans = node.val;
return;
}
postOrder(node.left);
}
}
Day 16：排序（简单）
【45】把数组排成最小的数
剑指 Offer 45. 把数组排成最小的数
-
intchanged toString
① strs[i] = "" + nums[i];
② strs[i] = String.valueOf(nums[i])
-
自定义比较器规则：字典序
① 匿名实现类
Arrays.sort(strs,new Comparator<String>(){
@Override
public int compare(String o1, String o2) {
//字典序列小的放在堆顶
return (o1 + o2).compareTo(o2 + o1);
}
});
② lambda 表达式
Arrays.sort(strs, (o1, o2) -> (o1 + o2).compareTo(o2 + o1));
Arrays.sort(nums, ( Integer a, Integer b) -> { return b-a;});
1) 自定比较规则的Arrays.sort
class Solution {
public String minNumber(int[] nums) {
String[] strs = new String[nums.length];
for(int i = 0; i < nums.length; i++)
// strs[i] = String.valueOf(nums[i]);
strs[i] = "" + nums[i];
// Arrays.sort(strs, (x, y) -> (x + y).compareTo(y + x));
Arrays.sort(strs,new Comparator<String>(){
@Override
public int compare(String o1, String o2) {
//字典序列小的放在堆顶
return (o1 + o2).compareTo(o2 + o1);
}
});
StringBuilder res = new StringBuilder();
for(String s : strs)
res.append(s);
return res.toString();
}
}
2）利用最小堆
class Solution {
public String minNumber(int[] nums) {
Queue<String> queue = new PriorityQueue<>(new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
//字典序列小的放在堆顶
return (o1 + o2).compareTo(o2 + o1);
}
});
for (int num : nums) {
queue.add("" + num);
}
StringBuilder res = new StringBuilder();
while (! queue.isEmpty()){
res.append(queue.poll());
}
return res.toString();
}
}
3）自己实现快排
class Solution {
public String minNumber(int[] nums) {
String[] strs = new String[nums.length];
for(int i = 0; i < nums.length; i++)
strs[i] = String.valueOf(nums[i]);
quickSort(strs, 0, strs.length - 1);
StringBuilder res = new StringBuilder();
for(String s : strs)
res.append(s);
return res.toString();
}
void quickSort(String[] strs, int l, int r) {
if(l >= r) return;
int i = l, j = r;
String tmp = strs[i];
while(i < j) {
while((strs[j] + strs[l]).compareTo(strs[l] + strs[j]) >= 0 && i < j) j--;
while((strs[i] + strs[l]).compareTo(strs[l] + strs[i]) <= 0 && i < j) i++;
tmp = strs[i];
strs[i] = strs[j];
strs[j] = tmp;
}
strs[i] = strs[l];
strs[l] = tmp;
quickSort(strs, l, i - 1);
quickSort(strs, i + 1, r);
}
}
【61】扑克牌中的顺子
剑指 Offer 61. 扑克牌中的顺子
1）排序+遍历
// T: O(nlogn) S: O(1)
class Solution {
public boolean isStraight(int[] nums) {
Arrays.sort(nums);
int count0 = 0; // 统计大小王个数
int compare = 0; // 统计顺子中缺几个
for(int i = 0; i < nums.length - 1; i++) {
if(nums[i] == 0) {count0++;continue;}
int j = nums[i+1] - nums[i];
// 相邻相等比不为顺子，提前返回
if(j==0) return false;
if(j == 1){ // 连上了
continue;
} else {// 有空缺
compare += j-1;
}
}
// 王比空缺多就为true
return count0 >= compare ? true : false;
}
}
2）hashset+遍历
// T: O(n) S:O(n)
class Solution {
public boolean isStraight(int[] nums) {
Set<Integer> repeat = new HashSet<>();
int max = 0, min = 14;
for(int num : nums) {
if(num == 0) continue; // 跳过大小王
max = Math.max(max, num); // 最大牌
min = Math.min(min, num); // 最小牌
if(repeat.contains(num)) return false; // 若有重复，提前返回 false
repeat.add(num); // 添加此牌至 Set
}
return max - min < 5; // 最大牌 - 最小牌 < 5 则可构成顺子
}
}
Day 17：排序（中等）
【40】最小的k个数
剑指 Offer 40. 最小的k个数
① 快排变形【针对 top k 问题】
class Solution {
int compare = 0;
public int[] getLeastNumbers(int[] arr, int k) {
if (k >= arr.length) return arr;
this.compare = k;
quickSort(arr, 0, arr.length - 1);
return Arrays.copyOf(arr, k);
}
public void quickSort(int[] arr, int l, int r) {
if (l < r) {
swap(arr, (l+r)/2, r);
int[] p = partition(arr, l, r);
// p[1] 是等于区的右端索引，因此 最小k个数索引范围 0~p[1] [索引和k是差1的]
// p[1] 这里理解为 小于等于区的右端索引
/**
快排变形，达到最小k个数字就返回。
不要求全部有序，当 小于等于区 小于 k 时， 只需要排序右边的就行，因为只要找到最小k个，不要求这k个继续有序。
*/
if(p[1]+1 == compare) return;
if(p[1]+1 > compare) quickSort(arr, l, p[0] - 1); // 接着换基准值比，让小于等于区右边界往左走
if(p[1]+1 < compare) quickSort(arr, p[1] + 1, r); // 接着换基准值比，让小于等于区右边界往右走
}
}
public int[] partition(int[] arr, int l, int r) {
int less = l - 1;// less是小于区的指针
int more = r;// more是大于区的指针
int i = l; // 数组索引的指针
while (i < more) {
if (arr[i] < arr[r]) {
swap(arr, ++less, i++);
} else if (arr[i] > arr[r]) {
swap(arr, --more, i);
} else {
i++;
}
}
// 调整基准值的位置
swap(arr, more, r);
return new int[] { less + 1, more };
}
public void swap(int[] arr, int i, int j) {
int tmp = arr[i];
arr[i] = arr[j];
arr[j] = tmp;
}
}
② 单纯快排【笨的奥，别看了】
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
Arrays.sort(arr);
int[] res = new int[k];
for(int i = 0; i < k; i++) {
res[i] = arr[i];
}
return res;
}
}
【41】数据流中的中位数
剑指 Offer 41. 数据流中的中位数
/**
原始方法：① 让 initial 无序数组 排序变成有序
② 每 addNum 一个元素，就对其进行一次插入排序 ，插入位置后的所有元素后移一个位置。
关键点：为了每加一个元素就排序一次，所以使用优先队列，优先队列拥有自动排序的功能
*/
class MedianFinder {
Queue<Integer> small, big;
public MedianFinder() {
// 大根堆堆顶 > 小根堆堆顶
small = new PriorityQueue<>(); // 小顶堆，保存较大的一半
big = new PriorityQueue<>((x, y) -> (y - x)); // 大顶堆，保存较小的一半
}
public void addNum(int num) {
if(small.size() != big.size()) {
small.add(num);
big.add(small.poll());
} else {
/**
大小相等时，优先往小根堆放。
① 为什么不直接放？
为保证大根堆堆顶 > 小根堆堆顶，
故先放到大根堆，然后弹出一个最大的，然后这个放入小根堆【成为小根堆的堆顶】
② 为什么优先放小根堆？
为保证，小根堆【存较大一半】，当N为奇数时，小根堆的堆顶就是中位数
*/
big.add(num);
small.add(big.poll());
}
}
public double findMedian() {
return small.size() != big.size() ? small.peek() : (small.peek() + big.peek()) / 2.0;
}
}
Day18：搜索与回溯算法（中等）
【55-I】二叉树的深度
剑指 Offer 55 - I. 二叉树的深度
// BFS
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) return 0;
Deque<TreeNode> queue = new ArrayDeque<>();
queue.addLast(root);
int depth = 0;
while(!queue.isEmpty()) {
depth++;
int size = queue.size();
for(int i = 0; i < size; i++) {
TreeNode tmp = queue.removeFirst();
if(tmp.left != null) {
queue.addLast(tmp.left);
}
if(tmp.right != null) {
queue.addLast(tmp.right);
}
}
}
return depth;
}
}
// dfs
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) return 0;
return 1+Math.max(maxDepth(root.left),maxDepth(root.right));
}
}
【55-II】平衡二叉树
剑指 Offer 55 - II. 平衡二叉树
[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-4zJIoqNb-1645235926737)(C:/Users/50249/Documents/GitHub/%E5%89%91%E6%8C%872%E5%88%B7/%E5%89%91%E6%8C%87OFFER.assets/image-20220128202542446.png)]
class Solution {
public boolean isBalanced(TreeNode root) {
return dfs(root) == -1 ? false : true;
}
public int dfs(TreeNode node) {
if(node == null) return 0;
//往左走
int LDepth = dfs(node.left);
// 回到本地
if(LDepth == -1) return -1;
// 往右走
int RDepth = dfs(node.right);
// 回到本体
if(RDepth == -1) return -1;
int diff = Math.abs(LDepth-RDepth);
if(diff > 1) return -1;
return Math.max(LDepth,RDepth) + 1;
}
}
// dfs
// 此方法容易想到，但会产生大量重复计算，时间复杂度较高。
// 深度的计算是有很多重复计算的部分的
class Solution {
public boolean isBalanced(TreeNode root) {
if(root == null) return true;
int L = depth(root.left);
int R = depth(root.right);
return Math.abs(L-R) <= 1 && isBalanced(root.left) && isBalanced(root.right);
}
public int depth(TreeNode root) {
if(root == null) return 0;
return 1+Math.max(depth(root.left),depth(root.right));
}
}
Day19：搜索与回溯算法（中等）
【64】求1+2+……+n
剑指 Offer 64. 求1+2+…+n
求 1+2+...+n ，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。
class Solution {
public int sumNums(int n) {
// 利用 && 的短路效应，
boolean x = n > 1 && (n += sumNums(n - 1)) > 0;
return n;
}
}
【68-I】 二叉搜索树的最近公共祖先
剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
if(root.val < p.val && root.val < q.val)
return lowestCommonAncestor(root.right, p, q);
if(root.val > p.val && root.val > q.val)
return lowestCommonAncestor(root.left, p, q);
// p <= root <= q
return root;
}
}
【68-II】 二叉搜索树的最近公共祖先
class Solution {
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
return dfs(root,p,q);
}
public TreeNode dfs(TreeNode root, TreeNode p, TreeNode q) {
// base-case
if(root == null) return null;
TreeNode left = dfs(root.left,p,q);
TreeNode right = dfs(root.right,p,q);
// 回到本体节点的时候进行判断
// 1.
if(root == p || root == q) return root;
// 2. 两边都为null
if(left == null && right == null) return null;
// 3. 两边都不为null
if(left != null && right != null) return root;
// 4. 单边为null
return left==null ? right : left;
}
}
Day20：分治算法（中等）
【07】重建二叉树
剑指 Offer 07. 重建二叉树
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode(int x) { val = x; }
* }
*/
class Solution {
// 构建Tree结构
// 返回层序遍历的结果
HashMap<Integer, Integer> dict = new HashMap<>();
public TreeNode buildTree(int[] preorder, int[] inorder) {
for(int i = 0; i < inorder.length; i++){
dict.put(inorder[i], i);
}
return partition(preorder,0,0,inorder.length-1);
}
// l 和 r 确定以当前rootIndex为根节点的树，的所有节点。
public TreeNode partition(int[] preorder,int rootIndex, int l ,int r) {
// base-case
if(l>r) return null;
// 1. 建立根节点
TreeNode head = new TreeNode(preorder[rootIndex]);
// 2. 确定划分点: 根节点在inorder中的索引位置
int i = dict.get(preorder[rootIndex]);
// 3. 划分左子树, 左子树有的话，其头为当前rootIndex的下一个；
head.left = partition(preorder,rootIndex + 1, l, i-1);
// 4. 划分右子树
// (i - l) 左子树个数
// 当前头节点位置 - 左子树个数 + 1 = 右子树的头节点
head.right = partition(preorder,rootIndex + (i - l) + 1, i+1, r);
// 回溯，返回根节点
return head;
}
}
【16】数值的整数次方
剑指 Offer 16. 数值的整数次方
class Solution {
public double myPow(double x, int n) {
// 1. n 是 + 还是 -
return n < 0 ? doPow(1/x, -1*n) : doPow(x,n);
}
public double doPow(double x, int n) {
// base-case
if(n == 0) return 1;
if(n == 1) return x;
double tmp = doPow(x,n/2);
return n % 2 == 0 ? tmp*tmp : x*tmp*tmp;
}
}
【33】二叉搜索树的后序遍历序列
剑指 Offer 33. 二叉搜索树的后序遍历序列
class Solution {
int[] postorder;
public boolean verifyPostorder(int[] postorder) {
this.postorder = postorder;
return check(0,postorder.length-1);
}
public boolean check(int l, int r) {
// BASE-CASE
if(r <= l) return true; // 范围内节点数量 <= 1 合法
// 1. 划分左右子树范围
int m = l;
while(postorder[m] < postorder[r]) { // m 停在第一个比 根节点大 的位置
m++;
}
// 左子树索引范围：l ~ m - 1
// 右子树索引范围：m ~ r - 1
// 当前 l ~ m-1 都小于 根节点值postorder[r], 局部有序合法
// 2. 判断 右子树索引范围是否满足都大于 根节点值postorder[r]
int p = m;
while(postorder[p] > postorder[r]) { // 遍历完停在r，中间有非法则不为r
p++;
}
return p == r && check(l,m-1) && check(m,r-1);
}
}
Day21：位运算（简单）
【15】二进制中1的个数
剑指 Offer 15. 二进制中1的个数
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int count1 = 0;
while(n != 0) {
count1++;
n &= n-1;
}
return count1;
}
}
Day23：
【66】构建乘积数组
剑指 Offer 66. 构建乘积数组
// space:O(1)
// space:O(n)
class Solution {
public int[] constructArr(int[] a) {
int len = a.length;
if(len == 0) return new int[0];
int[] b = new int[len];
b[0] = 1;
int tmp = 1;
for(int i = 1; i < len; i++) { // 从正数第二行开始，正数第一行已经 b[0]=1 初始化过了
b[i] = b[i - 1] * a[i - 1];
}
for(int i = len - 2; i >= 0; i--) { // 从倒数第二行开始，到处第一行 tmp=1 初始化过了
tmp *= a[i + 1];
b[i] *= tmp;
}
return b;
}
}
// space:O(n);
// time:O(n)
// 两个动态数组，分别维护【前缀和】&【后缀和】
class Solution {
public int[] constructArr(int[] a) {
int len = a.length;
int[] ans = new int[len];
int[] backToFront = new int[len];
int[] frontToBack = new int[len];
for(int i = 0; i < len; i++) {
// 初始化
if(i==0){ frontToBack[i] = a[i]; continue;}
frontToBack[i] = frontToBack[i-1] * a[i];
}
for(int i = len - 1; i >= 0; i--) {
// 初始化
if(i == len - 1) { backToFront[i] = a[i]; continue;}
backToFront[i] = backToFront[i+1] * a[i];
}
for(int i = 0; i < len; i++) {
if(i==0){ans[i] = backToFront[i+1];continue;}
if(i==len-1){ans[i] = frontToBack[i-1];continue;}
ans[i] = backToFront[i+1] * frontToBack[i-1];
}
return ans;
}
}
ublic boolean verifyPostorder(int[] postorder) {
this.postorder = postorder;
return check(0,postorder.length-1);
}
public boolean check(int l, int r) {
// BASE-CASE
if(r <= l) return true; // 范围内节点数量 <= 1 合法
// 1. 划分左右子树范围
int m = l;
while(postorder[m] < postorder[r]) { // m 停在第一个比 根节点大 的位置
m++;
}
// 左子树索引范围：l ~ m - 1
// 右子树索引范围：m ~ r - 1
// 当前 l ~ m-1 都小于 根节点值postorder[r], 局部有序合法
// 2. 判断 右子树索引范围是否满足都大于 根节点值postorder[r]
int p = m;
while(postorder[p] > postorder[r]) { // 遍历完停在r，中间有非法则不为r
p++;
}
return p == r && check(l,m-1) && check(m,r-1);
}
}
# Day21：位运算（简单）
## 【15】二进制中1的个数
[剑指 Offer 15. 二进制中1的个数](https://leetcode-cn.com/problems/er-jin-zhi-zhong-1de-ge-shu-lcof/)
```JAVA
public class Solution {
// you need to treat n as an unsigned value
public int hammingWeight(int n) {
int count1 = 0;
while(n != 0) {
count1++;
n &= n-1;
}
return count1;
}
}
Day23：
【66】构建乘积数组
剑指 Offer 66. 构建乘积数组
// space:O(1)
// space:O(n)
class Solution {
public int[] constructArr(int[] a) {
int len = a.length;
if(len == 0) return new int[0];
int[] b = new int[len];
b[0] = 1;
int tmp = 1;
for(int i = 1; i < len; i++) { // 从正数第二行开始，正数第一行已经 b[0]=1 初始化过了
b[i] = b[i - 1] * a[i - 1];
}
for(int i = len - 2; i >= 0; i--) { // 从倒数第二行开始，到处第一行 tmp=1 初始化过了
tmp *= a[i + 1];
b[i] *= tmp;
}
return b;
}
}
// space:O(n);
// time:O(n)
// 两个动态数组，分别维护【前缀和】&【后缀和】
class Solution {
public int[] constructArr(int[] a) {
int len = a.length;
int[] ans = new int[len];
int[] backToFront = new int[len];
int[] frontToBack = new int[len];
for(int i = 0; i < len; i++) {
// 初始化
if(i==0){ frontToBack[i] = a[i]; continue;}
frontToBack[i] = frontToBack[i-1] * a[i];
}
for(int i = len - 1; i >= 0; i--) {
// 初始化
if(i == len - 1) { backToFront[i] = a[i]; continue;}
backToFront[i] = backToFront[i+1] * a[i];
}
for(int i = 0; i < len; i++) {
if(i==0){ans[i] = backToFront[i+1];continue;}
if(i==len-1){ans[i] = frontToBack[i-1];continue;}
ans[i] = backToFront[i+1] * frontToBack[i-1];
}
return ans;
}
}
最后
以上就是俭朴短靴为你收集整理的剑指offer30天重刷剑指OFFER 二刷Day1：栈与队列（简单）Day2：链表（简单）Day3：字符串（简单）Day4：查找算法（简单）Day5：查找算法（中等）Day6：搜索与回溯算法（简单）Day7：搜索与回溯算法（简单）Day8：动态规划（简单）Day9：动态规划（中等）Day10：动态规划（中等）Day11：双指针（简单）Day 12：双指针（简单）Day 13：双指针（简单）Day 14：搜索与回溯算法（中等）Day 15：搜索与回溯算法（中等）Day 16：排序（简单）Day 的全部内容，希望文章能够帮你解决剑指offer30天重刷剑指OFFER 二刷Day1：栈与队列（简单）Day2：链表（简单）Day3：字符串（简单）Day4：查找算法（简单）Day5：查找算法（中等）Day6：搜索与回溯算法（简单）Day7：搜索与回溯算法（简单）Day8：动态规划（简单）Day9：动态规划（中等）Day10：动态规划（中等）Day11：双指针（简单）Day 12：双指针（简单）Day 13：双指针（简单）Day 14：搜索与回溯算法（中等）Day 15：搜索与回溯算法（中等）Day 16：排序（简单）Day 所遇到的程序开发问题。
如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。
本图文内容来源于网友提供，作为学习参考使用，或来自网络收集整理，版权属于原作者所有。
发表评论 取消回复