剑指 offer 代码+资料 + 具体安排（完结）
PS：为了阅读体验更好，请大家前往这里阅读：《剑指offer最优解》题解
PS：为了阅读体验更好，请大家前往这里阅读：《剑指offer最优解》题解
PS：为了阅读体验更好，请大家前往这里阅读：《剑指offer最优解》题解
这个 PDF 整理了《剑指offer》所有实现代码 + 对应的视频讲解链接以及原题链接，《剑指offer》基本属于面试 必刷，希望这个视频，能够帮助你更好着去理解剑指offer。
本资料已经整理成PDF，可以在帅地的公众号「帅地玩编程」中回复「剑指offer」获取PDF版本哦。
本系列配套视频讲解可以前往帅地的B站看：完美撒花！剑指offer题解合集(完结)｜有字幕+动画+现场手撕代码｜Java实现
提醒：由于网站原因，代码中的一些 = = 或者 < > 会被吃掉，有时候你们就脑补一下了。（看到的我都处理了）
开篇：聊一聊算法面试
这个视频讲解了算法面试相关的一些事情：开篇：聊一聊算法面试
剑指offer 3～15题
剑指 Offer 03. 数组中重复的数字
视频讲解直达：本题视频讲解
public int findRepeatNumber(int[] nums) {
// 遍历数组
for(int i = 0; i < nums.length; i++) {
// 之所以用while，是因为交换之后，该位置的元素任然没有在正确的位置
while(i != nums[i]){
if(nums[i] == nums[nums[i]]){
return nums[i];
}
// nums[i] 正确的位置在 nums[nums[i]]
int k = nums[nums[i]];
nums[nums[i]] = nums[i];
nums[i] = k;
}
}
return -1;
}
剑指 Offer 04. 二维数组中的查找
视频讲解直达： 本题视频讲解
if(matrix == null || matrix.length <= 0 || matrix[0].length <= 0){
return false;
}
// 这里 cols 表示多少行的意思（但是有人说 cols 是表示列，那我可能记错了）
int cols = matrix.length;
// rows 表示多少列的意思
int rows = matrix[0].length;
// 左下角的位置
int col = cols - 1;
int row = 0;
// 向上向右走的过程中不能出界
while(col >= 0 && row < rows){
if(target > matrix[col][row]){
row++;
} else if(target < matrix[col][row]){
col--;
} else {
return true;
}
}
return false;
}
剑指 Offer 05. 替换空格
视频讲解直达： 本题视频讲解
// Java中的常规做法
// public String replaceSpace(String s) {
// // 常规
// StringBuilder builder = new StringBuilder();
// for(int i = 0; i < s.length(); i++){
// if(s.charAt(i) == ' '){
// builder.append("%20");
// } else {
// builder.append(s.charAt(i));
// }
// }
// return builder.toString();
// }
//这个做法是模拟原地扩容的，但是Java并不支持扩容，所以我们只是联系一下代码怎么写
public String replaceSpace(String s) {
// 统计有多少空格
int count = 0;
for(int i = 0; i < s.length(); i++){
if(s.charAt(i) == ' '){
count ++;
}
}
char[] res = new char[s.length() + count * 2];
int k = res.length - 1;
// 从右往左遍历
for(int i = s.length() - 1; i >= 0; i--){
// 从右往左移动字符与替换字符
if(s.charAt(i) == ' '){
res[k--] = '0';
res[k--] = '2';
res[k--] = '%';
} else {
res[k--] = s.charAt(i);
}
}
return new String(res);
}
剑指 Offer 06. 从尾到头打印链表
视频讲解直达： 本题视频讲解
// 从右边=往左填充
public int[] reversePrint(ListNode head) {
if(head == null)
return new int[0];
// 统计链表节点个数，方便创建数组
int count = 0;
ListNode temp = head;
while(temp != null){
count++;
temp = temp.next;
}
int[] res = new int[count];
int k = count - 1;
// 从由往左填充数组
while(head != null){
res[k--] = head.val;
head = head.next;
}
return res;
}
剑指 Offer 07. 重建二叉树
视频讲解直达： 本题视频讲解
Map< Integer, Integer > map = new HashMap();
public TreeNode buildTree(int[] preorder, int[] inorder) {
if(preorder == null || preorder.length <= 0){
return null;
}
// 简历中序遍历数组的映射（就是为了快速求出某个元素的下标）
for(int i = 0; i < inorder.length; i++) {
map.put(inorder[i], i);
}
TreeNode root = f(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);
return root;
}
TreeNode f(int[] preorder, int l1, int r1, int[] inorder, int l2, int r2) {
// 前序遍历或者中序遍历为空时，表示这棵树不存在，直接返回 null
if( l1 > r1 || l2 > r2){
return null;
}
// 根节点
TreeNode root = new TreeNode(preorder[l1]);
// 根节点在中序遍历中的下标
int i = map.get(preorder[l1]);
// 递归求解
root.left = f(preorder, l1 + 1, l1 + (i - l2), inorder, l2, i - 1);
root.right = f(preorder, l1 + (i - l2) + 1, r1, inorder, i + 1, r2);
return root;
}
剑指 Offer 09. 用两个栈实现队列
视频讲解直达： 本题视频讲解
class CQueue {
Stack< Integer > stack1;
Stack< Integer > stack2;
public CQueue() {
stack1 = new Stack<>();
stack2 = new Stack<>();
}
public void appendTail(int value) {
stack1.push(value);
}
public int deleteHead() {
if(!stack2.isEmpty()){
return stack2.pop();
}
if(!stack1.isEmpty()){
while(!stack1.isEmpty()){
stack2.push(stack1.pop());
}
return stack2.pop();
}
return -1;
}
}
剑指 Offer 10- I. 斐波那契数列
视频讲解直达： 本题视频讲解
public int fib(int n) {
if( n <= 1){
return n;
}
int a = 0;
int b = 1;
int c = 0;;
for(int i = 2; i <= n; i++){
c = (a + b) % 1000000007;
// a 原本指向的值不会在用到，所以让 a 保存 b，b 保存 c，之后重新计算 c，如此循环
a = b;
b = c;
}
return c;
}
剑指 Offer 10- II. 青蛙跳台阶问题
视频讲解直达： 本题视频讲解
// 如果看不懂代码为啥这样写，可以参考上一题
public int numWays(int n) {
//递归公示 f(n) = f(n - 1) + f(n - 2);
if( n <= 1)
return 1;
int a = 1;
int b = 1;
int c = 0;
for(int i = 2; i <= n; i++){
c = (a + b) % 1000000007;
a = b;
b = c;
}
return c;
}
剑指 Offer 11. 旋转数组的最小数字
视频讲解直达： 本题视频讲解
public int minArray(int[] numbers) {
// O（n)
// logN O1
int l = 0;
int r = numbers.length - 1;
while(l < r) {
if(numbers[l] < numbers[r]){
return numbers[l];
}
int mid = (r + l) / 2;
if(numbers[mid] > numbers[l]){
l = mid + 1;
} else if(numbers[mid] < numbers[l]){
r = mid;
} else {
l++;
}
}
return numbers[l];
}
剑指 Offer 12. 矩阵中的路径
视频讲解直达： 本题视频讲解
class Solution {
int n;
int m;
int len;
boolean[][] visited;
public boolean exist(char[][] board, String word) {
this.n = board.length;
this.m = board[0].length;
this.len = word.length();
visited = new boolean[n][m];
for(int i = 0; i < n; i++){
for(int j = 0; j < m; j++){
if(dsf(board, i, j, word, 0)){
return true;
}
}
}
return false;
}
boolean dsf(char[][] board, int i, int j, String word, int k){
// 判断是否越界，已经访问过或者不匹配
if(i < 0 || i >= n || j < 0 || j >= m || board[i][j] != word.charAt(k)){
return false;
}
if(k == len - 1){
return true;
}
//visited[i][j] = true;
board[i][j] = '\n';
// 四个方向都搜索一下
boolean res = dsf(board, i, j + 1, word, k + 1) ||
dsf(board, i + 1, j, word, k + 1) ||
dsf(board, i, j - 1, word, k + 1) ||
dsf(board, i - 1, j, word, k + 1);
board[i][j] = word.charAt(k);
return res;
// 时间复杂度：mn * 3^len
}
}
剑指 Offer 13. 机器人的运动范围
视频讲解直达： 本题视频讲解
class Solution {
int m;
int n;
int k;
boolean[][] visited;
public int movingCount(int m, int n, int k) {
this.m = m;
this.n = n;
this.k = k;
visited = new boolean[m][n];
return dfs(0, 0);
}
int dfs(int i, int j){
// 是否在方格之内或者是否访问过或者是否是障碍物
if(i < 0 || j < 0 || i >= m || j >= n || visited[i][j] || k < sum(i) + sum(j)){
return 0;
}
visited[i][j] = true;
return 1 + dfs(i + 1, j) + dfs(i, j + 1);
}
int sum(int x){
int res = 0;
while(x != 0){
res = res + x % 10;
x = x / 10;
}
return res;
}
}
剑指 Offer 14- I. 剪绳子
视频讲解直达： 本题视频讲解
public int cuttingRope(int n) {
if(n <= 2){
return 1;
}
if(n == 3){
return 2;
}
int res = n / 3;
int mod = n % 3;
if(mod == 0){
return pow(3, res);
} else if(mod == 1){
return pow(3, res - 1) * 4;
} else {
return pow(3, res) * 2;
}
}
// 这里多余了，其实直接调用Math.pow就可以了
int pow(int a, int n){
int sum = 1;
for(int i = 1; i <= n; i ++){
sum = sum * a;
}
return sum;
}
剑指 Offer 14- II. 剪绳子 II
视频讲解直达： 本题视频讲解
public int cuttingRope(int n) {
if(n <= 2){
return 1;
}
if(n == 3){
return 2;
}
int res = n / 3;
int mod = n % 3;
int p = 1000000007;
if(mod == 0){
return (int)pow(3, res);
} else if(mod == 1){
return (int)(pow(3, res - 1) * 4 % p);
} else {
return (int)(pow(3, res) * 2 % 1000000007);
}
}
//求 a^n %p
long pow(int a, int n){
long res = 1;
int p = 1000000007;
for(int i= 1; i <= n; i++){
res = (res * a) % p;
}
return res;
}
剑指 Offer 15. 二进制中1的个数
视频讲解直达： 本题视频讲解
public int hammingWeight(int n) {
int sum = 0;
while(n != 0){
// n & (n - 1)可以消除n最右边的一个 1（二进制表示）
n = n & (n - 1);
sum ++;
}
return sum;
}
剑指offer 16～30题
剑指 Offer 16. 数值的整数次方
视频讲解直达： 本题视频讲解
public double myPow(double x, int n) {
double res = 1;
long y = n;// 不能用 int。
if(n < 0){
y = -y;
x = 1 / x;
}
while(y > 0){
if(y % 2 == 1){
res = res * x;
}
x = x * x;
y = y / 2;
}
return res;
}
剑指 Offer 17. 打印从1到最大的n位
视频讲解直达： 本题视频讲解
public int[] printNumbers(int n) {
int sum = (int)Math.pow(10, n);
int[] res = new int[sum - 1];
for(int i = 1; i <= sum - 1; i++){
res[i - 1] = i;
}
return res;
}
剑指 Offer 18. 删除链表的节点
视频讲解直达： 本题视频讲解
public ListNode deleteNode(ListNode head, int val) {
if(head == null){
return null;
}
if(head.val == val){
return head.next;
}
ListNode temp = head.next;
ListNode pre = head;
while(temp != null){
if(temp.val == val){
pre.next = temp.next;
return head;
}
temp = temp.next;
pre = pre.next;
}
return head;
}
剑指 Offer 19. 正则表达式匹配
视频讲解直达： 本题视频讲解
class Solution {
public boolean isMatch(String s, String p) {
if(s == null || p == null){
return true;
}
int n = s.length();
int m = p.length();
boolean[][] dp = new boolean[n+1][m+1];
// 初始化
dp[0][0] = true;
for(int j = 2; j <= m; j++){
if(p.charAt(j - 1) == '*'){
dp[0][j] = dp[0][j - 2];
}
}
for(int i = 1; i <= n; i++){
for(int j = 1; j <= m; j++){
// 当j不为 *
if(p.charAt(j - 1) != '*'){
// 如果不匹配
if(p.charAt(j-1) == '.' || p.charAt(j-1) == s.charAt(i - 1)){
dp[i][j] = dp[i-1][j-1];
}
} else {
// 第j-1个字符不匹配
if(p.charAt(j - 2) != s.charAt(i - 1) && p.charAt(j-2) != '.'){
dp[i][j] = dp[i][j-2];
} else {
dp[i][j] = dp[i][j-2] || dp[i][j-1] || dp[i-1][j];
}
}
}
}
return dp[n][m];
}
}
剑指 Offer 20. 表示数值的字符串
视频讲解直达： 本题视频讲解
class Solution {
public boolean isNumber(String s) {
//有限状态机
// 2.小数点 3.E/e 4. 数字字符 5. -+
if(s == null || s.length() <= 0){
return false;
}
char[] res = s.trim().toCharArray();
if(res.length <= 0) return false;
int n = res.length;
boolean is_dot = false;
boolean is_e_or_E = false;
boolean is_num = false;
for(int i = 0; i < n; i++){
if(res[i] >= '0' && res[i] <= '9'){
is_num = true;
} else if(res[i] == '.'){
//-+ 8. 8.8 .8
// 前面：不能有重复的小数点，也不能出现 e/E
if(is_dot || is_e_or_E){
return false;
}
is_dot = true;
} else if(res[i] == 'e' || res[i] == 'E'){
// 前面必须要有一个数字 || 前面不能出现重复的 e/E
if(is_e_or_E || !is_num){
return false;
}
is_e_or_E = true;
is_num =false;//11E+ 11E
} else if(res[i] == '-' || res[i] == '+'){
if(i!=0 && res[i-1] != 'e' && res[i-1] != 'E'){
return false;
}
} else {
return false;
}
}
return is_num;
}
}
剑指 Offer 21. 调整数组顺序使奇数位于偶数前面
视频讲解直达： 本题视频讲解
class Solution {
public int[] exchange(int[] nums) {
if(nums == null || nums.length == 0){
return nums;
}
int left = 0;
int right = nums.length - 1;
while(left < right){
while(left < right && nums[left] % 2 != 0) left++;
while(left < right && nums[right] % 2 != 1) right--;
int temp = nums[left];
nums[left] = nums[right];
nums[right] = temp;
}
return nums;
}
}
剑指 Offer 22. 链表中倒数第k个节
视频讲解直达： 本题视频讲解
class Solution {
public ListNode getKthFromEnd(ListNode head, int k) {
if(head == null){
return null;
}
ListNode fast = head, slow = head;
for(int i = 0; i < k; i++){
if(fast == null){
return null;
}
fast = fast.next;
}
while(fast != null){
fast = fast.next;
slow = slow.next;
}
return slow;
}
}
剑指 Offer 24. 反转链表
视频讲解直达： 本题视频讲解
class Solution {
// 原地反转
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null){
return head;
}
ListNode cur = head, pre = null;
while(cur != null){
ListNode temp = cur.next;
cur.next = pre;
pre = cur;
cur = temp;
}
return pre;
// 额外空间复杂度=1
}
// 递归
public ListNode reverseList(ListNode head) {
if(head == null || head.next == null){
return head;
}
// 反转子链表
ListNode temp = reverseList(head.next);
head.next.next = head;
head.next = null;
return temp;
}
}
剑指 Offer 25. 合并两个排序的链表
视频讲解直达： 本题视频讲解
class Solution {
public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
ListNode merge = new ListNode(0);
ListNode temp = merge;
while(l1 != null && l2 != null){
if(l1.val < l2.val){
temp.next = l1;
l1 = l1.next;
} else {
temp.next = l2;
l2 = l2.next;
}
temp = temp.next;
}
temp.next = l1 == null ? l2 : l1;
return merge.next;
}
}
剑指 Offer 26. 树的子结构
视频讲解直达： 本题视频讲解
class Solution {
public boolean isSubStructure(TreeNode A, TreeNode B) {
if(A == null || B == null){
return false;
}
if(isSubTree(A, B)){
return true;
}
if(isSubStructure(A.left, B) || isSubStructure(A.right, B)){
return true;
}
return false;
}
public boolean isSubTree(TreeNode Ta, TreeNode Tb){
if(Tb == null){
return true;
}
if(Ta == null){
return false;
}
if(Ta.val != Tb.val){
return false;
}
return isSubTree(Ta.left, Tb.left) &&
isSubTree(Ta.right, Tb.right);
}
}
剑指 Offer 27. 二叉树的镜像
视频讲解直达： 本题视频讲解
class Solution {
public TreeNode mirrorTree(TreeNode root) {
if(root == null || (root.left == null && root.right == null)){
return root;
}
TreeNode left = mirrorTree(root.left);
TreeNode right = mirrorTree(root.right);
root.left = right;
root.right = left;
return root;
}
}
剑指 Offer 28. 对称的二叉树
视频讲解直达： 本题视频讲解
class Solution {
public boolean isSymmetric(TreeNode root) {
if(root == null || (root.left == null && root.right == null)){
return true;
}
return f(root.left, root.right);
}
// 判断B是不是以A阶段为根节点的子树
public boolean f(TreeNode A, TreeNode B){
if(A == null && B == null){
return true;
}
if(A == null || B == null){
return false;
}
if(A.val != B.val){
return false;
}
return f(A.left, B.right) && f(A.right, B.left);
}
}
剑指 Offer 29. 顺时针打印矩阵
视频讲解直达： 本题视频讲解
class Solution {
public int[] spiralOrder(int[][] matrix) {
if(matrix == null || matrix.length == 0 || matrix[0].length == 0){
return new int[0];
}
int l = 0, r = matrix[0].length - 1, t = 0, b = matrix.length - 1;
int[] res = new int[(r+1) * (b+1)];
int k = 0;
while(true){
// 从左到右
for(int i = t,j = l; j <= r; j++){
res[k++] = matrix[i][j];
}
if(++t > b) break;
// 从下往上
for(int i = t, j = r; i <= b; i++){
res[k++] = matrix[i][j];
}
if(l > --r) break;
// 从右往左
for(int i = b, j = r; j >= l; j--){
res[k++] = matrix[i][j];
}
if(t > --b) break;
// 从下往上
for(int i = b, j = l; i >= t; i--){
res[k++] = matrix[i][j];
}
if(++l > r) break;
}
return res;
}
}
剑指 Offer 30. 包含min函数的栈
视频讲解直达： 本题视频讲解
class MinStack {
Stack stack1;
Stack stack2;
/** initialize your data structure here. */
public MinStack() {
this.stack1 = new Stack();
this.stack2 = new Stack();
}
public void push(int x) {
stack1.push(x);
if(stack2.isEmpty() || x <= stack2.peek().intValue()){
stack2.push(x);
}
}
public void pop() {
if(!stack1.isEmpty()){
//Integer, 数值 > 127 I
if(stack1.peek().intValue() == stack2.peek().intValue()){
stack2.pop();
}
stack1.pop();
}
}
public int top() {
return stack1.peek();
}
public int min() {
return stack2.peek();
}
}
剑指offer 31～45题
剑指 Offer 31. 栈的压入、弹出序列
视频讲解直达： 本题视频讲解
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
if(pushed == null || pushed.length <= 0){
return true;
}
int k = 0;
Stack stack = new Stack();
for(int i = 0; i < pushed.length; i++){
stack.push(pushed[i]);
while(!stack.isEmpty() && stack.peek() == popped[k]){
stack.pop();
k++;
}
}
return stack.isEmpty();
}
}
剑指 Offer 32 - I. 从上到下打印二叉树
视频讲解直达： 本题视频讲解
class Solution {
public int[] levelOrder(TreeNode root) {
if(root == null){
return new int[0];
}
Queue queue = new LinkedList<>();
List res = new ArrayList<>();
queue.add(root);
while(!queue.isEmpty()){
TreeNode t = queue.poll();
res.add(t.val);
if(t.left != null) queue.add(t.left);
if(t.right != null) queue.add(t.right);
}
int[] arr = new int[res.size()];
for(int i = 0; i < res.size(); i++){
arr[i] = res.get(i);
}
return arr;
}
}
剑指 Offer 32 - II. 从上到下打印二叉树
视频讲解直达： 本题视频讲解
class Solution {
public List> levelOrder(TreeNode root) {
if(root == null){
return new ArrayList<>();
}
Queue queue = new LinkedList<>();
List> res = new ArrayList<>();
queue.add(root);
while(!queue.isEmpty()){
int k = queue.size();
List tmp = new ArrayList<>();
for(int i = 0; i < k; i++){
TreeNode t = queue.poll();
tmp.add(t.val);
if(t.left != null) queue.add(t.left);
if(t.right != null) queue.add(t.right);
}
res.add(tmp);
}
return res;
}
}
剑指 Offer 32 - III. 从上到下打印二叉树
视频讲解直达： 本题视频讲解
class Solution {
public List> levelOrder(TreeNode root) {
if(root == null){
return new ArrayList<>();
}
Queue queue = new LinkedList<>();
List> res = new ArrayList<>();
int sum = 1;
queue.add(root);
while(!queue.isEmpty()){
int k = queue.size();
LinkedList tmp = new LinkedList<>();
for(int i = 0; i < k; i++){
TreeNode t = queue.poll();
if(sum % 2 == 1){
tmp.add(t.val);
} else {
tmp.addFirst(t.val);
}
if(t.left != null) queue.add(t.left);
if(t.right != null) queue.add(t.right);
}
res.add(tmp);
sum ++;
}
return res;
}
}
剑指 Offer 33. 二叉搜索树的后序遍历序列
视频讲解直达： 本题视频讲解
class Solution {
public boolean verifyPostorder(int[] postorder) {
if(postorder == null){
return true;
}
return f(postorder, 0, postorder.length - 1);
}
boolean f(int[] postorder, int i, int j){
if(i >= j){
return true;
}
int root = postorder[j];
int p = i;
// 获取第一个大于或者等于 root 等元素的位置
while(postorder[p] < root) p++;
// 判断 p ~ j -1 这个范围是否存在小于root的元素
for(int k = p; k < j; k++){
if(postorder[k] < root){
return false;
}
}
return f(postorder, i, p - 1) && f(postorder, p, j - 1);
}
}
剑指 Offer 34. 二叉树中和为某一值的路径
视频讲解直达： 本题视频讲解
class Solution {
List> res;
List tmp;
public List> pathSum(TreeNode root, int target) {
res = new ArrayList<>();
tmp = new ArrayList<>();
dsf(root, target);
return res;
}
void dsf(TreeNode root, int target){
if(root == null){
return;
}
tmp.add(root.val);
target = target - root.val;
if(root.left == null && root.right == null && target == 0){
res.add(new ArrayList<>(tmp));
}
dsf(root.left, target);
dsf(root.right, target);
tmp.remove(tmp.size() - 1);
}
}
剑指 Offer 35. 复杂链表的复制
视频讲解直达： 本题视频讲解
class Solution {
public Node copyRandomList(Node head) {
if(head == null){
return null;
}
// 复制链表节点
Node cur = head;
while(cur != null){
Node next = cur.next;
cur.next = new Node(cur.val);
cur.next.next = next;
cur = next;
}
// 复制随机节点
cur = head;
while(cur != null){
Node curNew = cur.next;
curNew.random = cur.random == null ? null : cur.random.next;
cur = cur.next.next;
}
// 拆分,比如把 A->A1->B->B1->C->C1拆分成 A->B->C和A1->B1->C1
Node headNew = head.next;
cur = head;
Node curNew = head.next;
while(cur != null){
cur.next = cur.next.next;
cur = cur.next;
curNew.next = cur == null ? null : cur.next;
curNew = curNew.next;
}
return headNew;
}
}
剑指 Offer 36. 二叉搜索树与双向链表
视频讲解直达： 本题视频讲解
class Solution {
public Node treeToDoublyList(Node root) {
if(root == null){
return null;
}
Queue queue = new LinkedList<>();
inOrder(root, queue);
Node head = queue.poll();
Node pre = head;
while(!queue.isEmpty()){
Node cur = queue.poll();
pre.right = cur;
cur.left = pre;
pre = cur;
}
pre.right = head;
head.left = pre;
return head;
}
void inOrder(Node root, Queue queue){
if(root == null){
return;
}
inOrder(root.left, queue);
queue.add(root);
inOrder(root.right, queue);
}
}
剑指 Offer 37. 序列化二叉树
视频讲解直达： 本题视频讲解
public class Codec {
// Encodes a tree to a single string.
public String serialize(TreeNode root) {
// 序列化成字符串,1,2,3,null,null,4,5,null...
if(root == null){
return "";
}
StringBuilder build = new StringBuilder();
Queue queue = new LinkedList<>();
queue.add(root);
while(!queue.isEmpty()){
TreeNode t = queue.poll();
if(t != null){
queue.add(t.left);
queue.add(t.right);
build.append(t.val + ",");
}else{
build.append("null,");
}
}
return build.toString();
}
// Decodes your encoded data to tree.
public TreeNode deserialize(String data) {
// 1,2,3,null,null,4,5,null...
if(data == null || data.length() <= 0){
return null;
}
String[] s = data.split(",");
Queue queue = new LinkedList<>();
TreeNode root = new TreeNode(Integer.parseInt(s[0]));
queue.add(root);
int i = 1;
while(!queue.isEmpty()){
TreeNode t = queue.poll();
// 构建做左节点
if(!s[i].equals("null")){
TreeNode left = new TreeNode(Integer.parseInt(s[i]));
t.left = left;
queue.add(left);
}
i++;
// 构建右节点
if(!s[i].equals("null")){
TreeNode right = new TreeNode(Integer.parseInt(s[i]));
t.right = right;
queue.add(right);
}
i++;
}
return root;
}
}
剑指 Offer 38. 字符串的排列
视频讲解直达： 本题视频讲解
class Solution {
List path;
List res;
boolean[] visited;
public String[] permutation(String s) {
this.path = new ArrayList<>();
this.res = new ArrayList<>();
this.visited = new boolean[s.length()];
char[] arr = s.toCharArray();
Arrays.sort(arr);
dfs(arr, 0);
String[] ss = new String[res.size()];
for(int i = 0; i < res.size(); i++){
ss[i] = res.get(i);
}
return ss;
}
// 时间复杂度：O(n*n!) 空间：N,N,递归调用最大深度也是 N，3n,O(n)
void dfs(char[] arr, int k){
if(arr.length == k){
res.add(listToString(path));
return;
}
//进行N叉树搜索
for(int i = 0; i < arr.length; i++){
// 剪枝 aab
if(i > 0 && arr[i] == arr[i - 1] && visited[i - 1] == false){
continue;
}
if(visited[i] == false){
// 递归访问
visited[i] = true;
path.add(arr[i]);
dfs(arr, k + 1);
path.remove(path.size() - 1);
visited[i] = false;
}
}
}
String listToString(List list){
StringBuilder b = new StringBuilder();
for(int i = 0; i < list.size(); i++){
b.append(list.get(i));
}
return b.toString();
}
}
剑指 Offer 39. 数组中出现次数超过一半的数字
视频讲解直达： 本题视频讲解
class Solution {
public int majorityElement(int[] nums) {
if(nums.length <= 2){
return nums[0];
}
int x = nums[0];
int sum = 1;
for(int i = 1; i < nums.length; i++){
if(sum == 0){
x = nums[i];
sum = 1;
} else {
if(x == nums[i]){
sum++;
} else {
sum--;
}
}
}
return x;
}
}
剑指 Offer 40. 最小的k个数
视频讲解直达： 本题视频讲解
class Solution {
public int[] getLeastNumbers(int[] arr, int k) {
if(arr == null || arr.length == 0 || k == 0){
return new int[0];
}
return quickFind(arr, 0, arr.length - 1, k);
}
int[] quickFind(int[] arr, int left, int right, int k){
int i = partition(arr, left, right);
// 之所以需要 i+1，是因为下标从 0 开始，0～i之间一共有 i+1个数
if(i + 1 == k){
return Arrays.copyOf(arr, k);
}
if(i + 1 > k){
return quickFind(arr, 0, i - 1, k);
} else {
return quickFind(arr, i + 1, right, k);
}
}
// 找出pivot的下标以及使小于等于pivot在左边，大于等于的在右边
int partition(int[] arr, int left, int right){
int pivot = arr[left];
int i = left + 1;
int j = right;
while(i < j){
while(i <= j && arr[i] <= pivot) i++;
while(i <= j && arr[j] >= pivot) j--;
if(i >= j){
break;
}
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
arr[left] = arr[j];
arr[j] = pivot;
return j;
}
}
剑指 Offer 41. 数据流中的中位数
视频讲解直达： 本题视频讲解
class MedianFinder {
Queue min, max;
/** initialize your data structure here. */
public MedianFinder() {
min = new PriorityQueue<>(); // 小根，保存较大的
max = new PriorityQueue<>((x, y) -> (y - x));// 大根
}
public void addNum(int num) {
// 如果是偶数
if(min.size() == max.size()){
min.add(num);
max.add(min.poll());
} else {
max.add(num);
min.add(max.poll());
}
}
public double findMedian() {
// 如果是偶数
if(min.size() == max.size()){
return (min.peek() + max.peek()) / 2.0;
} else {
return max.peek() * 1.0;
}
}
}
剑指 Offer 42. 连续子数组的最大和
视频讲解直达： 本题视频讲解
class Solution {
public int maxSubArray(int[] nums) {
int dp = nums[0];
int max = nums[0];
// 刷新dp之前，dp相当于是 dp[i-1],刷新之后，Dp就是dp[i]
for(int i = 1; i < nums.length; i++){
dp = Math.max(dp + nums[i], nums[i]);
max = Math.max(max, dp);
}
return max;
}
}
剑指 Offer 43. 1～n 整数中 1 出现的次数
视频讲解直达： 本题视频讲解
class Solution {
public int countDigitOne(int n) {
// 几个变量计算：cur = (n/bit)%10, low = n % bit, high = n / bit / 10
// 几个公示
// cur > 1 => (high + 1) * bit
// cur == 1 => (high * bit) + (1 + low)
// cur = 0 => high * bit
long bit = 1;
long sum = 0;
while(bit <= n){
long cur = (n/bit)%10;
long low = n % bit;
long high = n / bit / 10;
if(cur > 1){
sum += (high + 1) * bit;
}else if(cur == 1){
sum += (high * bit) + (1 + low);
}else{
sum += high * bit;
}
bit = bit * 10;
}
return (int)sum;
}
}
剑指 Offer 44. 数字序列中某一位的数字
视频讲解直达： 本题视频讲解
class Solution {
public int findNthDigit(int n) {
if(n == 0){
return 0;
}
long bit = 1;
int i = 1;
long count = 9;
while(count < n){
n = (int)(n - count);
bit = bit * 10;
i++;
count = bit * i * 9;
}
// 确定是在这个区间的哪个数
long num = bit + (n - 1) / i;
// 确定在 Num 的那个字符
int index = (n - 1) % i + 1;
int res = (int)(num / Math.pow(10, i - index)) % 10;
return res;
}
}
剑指 Offer 45. 把数组排成最小的数
视频讲解直达： 本题视频讲解
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 sb = new StringBuilder();
for (int i = 0; i < strs.length; i++) {
sb.append(strs[i]);
}
return sb.toString();
}
///时间nlogn，空间 On
// 快速排序模版（和普通快速排序模版一样的，除了比较那里不一样）
private void quickSort(String[] arr, int left, int right) {
if (left > right) {
return;
}
int i = partition(arr, left, right);
quickSort(arr, left, i - 1);
quickSort(arr, i + 1, right);
}
int partition(String[] arr, int left, int right){
String pivot = arr[left]; // 中间值
int i = left;
int j = right;
while (i < j) {
while (i <= j && (arr[i] + pivot).compareTo(pivot + arr[i]) <= 0) {
i++;
}
while (i <= j && (arr[j] + pivot).compareTo(pivot + arr[j]) >= 0) {
j--;
}
if(i >= j){
break;
}
String temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
arr[left] = arr[j];
arr[j] = pivot;
return j;
}
}
剑指offer 46～68题
剑指 Offer 46. 把数字翻译成字符串
视频讲解直达： 本题视频讲解
class Solution {
public int translateNum(int num) {
if(num <= 9){
return 1;
}
char[] arr = String.valueOf(num).toCharArray();
int n = arr.length;
//int[] dp = new int[n + 1];
// f(n) = f(n-1) + f(n-2)
int a = 1;
int b = 1;
int c = 1;
// 优化 a,b,c
for(int i = 2; i <= n; i++){
// 计算第i和第i-1个字符的组合
int tmp = 10 * (arr[i-2] - '0') + (arr[i-1] - '0');
if(tmp >= 10 && tmp <= 25){
c = a + b;
}else{
c = b;
}
//迭代
a = b;
b = c;
}
return c;
}
}
剑指 Offer 47. 礼物的最大价值
视频讲解直达： 本题视频讲解
class Solution {
public int maxValue(int[][] grid) {
//优化版本
int n = grid.length;
int m = grid[0].length;
int[]dp = new int[m];
dp[0] = grid[0][0];
for(int j = 1; j < m; j++){
dp[j] = dp[j-1] + grid[0][j];
}
for(int i = 1; i < n; i++){
//
dp[0] = dp[0] + grid[i][0];
for(int j = 1; j < m; j++){
dp[j] = Math.max(dp[j], dp[j-1]) + grid[i][j];
}
}
return dp[m-1];
}
// 二维版本
public int maxValue(int[][] grid) {
int n = grid.length;
int m = grid[0].length;
int[][] dp = new int[n][m];
dp[0][0] = grid[0][0];
for(int i = 1; i < n; i++){
dp[i][0] = dp[i-1][0] + grid[i][0];
}
for(int j = 1; j < m; j++){
dp[0][j] = dp[0][j -1] + grid[0][j];
}
for(int i = 1; i < n; i++){
for(int j = 1; j < m; j++){
dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]) + grid[i][j];
}
}
return dp[n-1][m-1];
}
}
剑指 Offer 48. 最长不含重复字符的子字符串
视频讲解直达： 本题视频讲解
class Solution {
// public int lengthOfLongestSubstring(String s) {
// if(s == null || s.length() <= 0){
// return 0;
// }
// // 优化 => 单个变量
// Map map = new HashMap<>();
// int[] dp = new int[s.length()];
// dp[0] = 1;
// map.put(s.charAt(0), 0);
// int res = 1;
// for(int i = 1; i < s.length(); i++){
// if(!map.containsKey(s.charAt(i))){
// dp[i] = dp[i-1] + 1;
// }else{
// int k = map.get(s.charAt(i));
// dp[i] = i - k <= dp[i-1] ? i - k : dp[i-1] + 1;
// }
// res = Math.max(res, dp[i]);
// map.put(s.charAt(i), i);
// }
// return res;
// }
// 优化版本
public int lengthOfLongestSubstring(String s) {
if(s == null || s.length() <= 0){
return 0;
}
// 优化 => 单个变量
Map map = new HashMap<>();
//int[] dp = new int[s.length()];
int a = 1;
map.put(s.charAt(0), 0);
int res = 1;
for(int i = 1; i < s.length(); i++){
if(!map.containsKey(s.charAt(i))){
a = a + 1;// 就是没有刷新 a 之前，a表示dp[i-1]
}else{
int k = map.get(s.charAt(i));
a = i - k <= a ? i - k : a + 1;
}
res = Math.max(res, a);
map.put(s.charAt(i), i);
}
return res;
// 时间On,空间On
}
}
剑指 Offer 49. 丑数
视频讲解直达： 本题视频讲解
class Solution {
public int nthUglyNumber(int n) {
int a = 1, b = 1, c = 1;
int[] dp = new int[n+1];
dp[1] = 1;
for(int i = 2; i <= n; i++){
dp[i] = Math.min(Math.min(dp[a] * 2, dp[b] * 3), dp[c] * 5);
if(dp[i] == dp[a] * 2) a++;
if(dp[i] == dp[b] * 3) b++;
if(dp[i] == dp[c] * 5) c++;
}
return dp[n];
}
}
剑指 Offer 50. 第一个只出现一次的字符
视频讲解直达： 本题视频讲解
class Solution {
public char firstUniqChar(String s) {
if(s == null || s.length() <= 0){
return ' ';
}
//一个字母出现的次数大于 1 次就不符合要求了，这个时候使用 Fasle 标记状态相对于 Integer 的不断递增更合理，也更省空间。布尔值可以用来判断，可以简化代码逻辑。
Map map = new LinkedHashMap<>();
for(int i = 0; i < s.length(); i++){
map.put(s.charAt(i), !map.containsKey(s.charAt(i)));
}
for(Map.Entry m : map.entrySet()){
if(m.getValue()){
return m.getKey();
}
}
return ' ';
}
}
剑指 Offer 51. 数组中的逆序对
视频讲解直达： 本题视频讲解
class Solution {
public int reversePairs(int[] nums) {
if(nums == null || nums.length <= 1){
return 0;
}
return mergeSort(nums, 0, nums.length - 1);
}
int mergeSort(int[] nums, int left, int right){
if(left >= right){
return 0;
}
int mid = (right - left) / 2 + left;
int x1 = mergeSort(nums, left, mid);
int x2 = mergeSort(nums, mid + 1, right);
int x3 = merge(nums, left, mid, mid+1, right);
return x1 + x2 + x3;
}
int merge(int[] nums, int l1, int r1, int l2, int r2){
int[] temp = new int[r2 - l1 + 1];
int count = 0;
int i = l1, j = l2, k = 0;
while(i <= r1 && j <= r2){
if(nums[i] > nums[j]){
count = count + (l2 - i);
temp[k++] = nums[j++];
}else{
temp[k++] = nums[i++];
}
}
while(i <= r1) temp[k++] = nums[i++];
while(j <= r2) temp[k++] = nums[j++];
// 把临时数组复制回原数组
k = 0;
for(i = l1; i <= r2; i++){
nums[i] = temp[k++];
}
return count;
}
}
剑指 Offer 52. 两个链表的第一个
视频讲解直达： 本题视频讲解
class Solution {
ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if(headA == null || headB == null) return null;
ListNode A = headA;
ListNode B = headB;
while(A != B){
A = A == null ? headB : A.next;
B = B == null ? headA : B.next;
}
return A;
}
}
剑指 Offer 53 - I. 在排序数组中查找
视频讲解直达： 本题视频讲解
class Solution {
public int search(int[] nums, int target) {
//常见题型：
// 1.寻找第一个大于等于 target 的数 2.寻找第一个等于 target 的数
// 3.寻找最后一个大于等于 target 的数 4.寻找最后一个等于 target 的数
//PS：其实这里是不需要写两个查找函数的，可以把代码优化放在同一个方法里滴
int left = search2(nums, target);
int right = search4(nums, target);
if(left < 0 || right < 0) return 0;
return right - left + 1;
}
//2.寻找第一个等于 target 的数的下标
int search2(int[] nums, int target){
if(nums == null || nums.length <= 0){
return -1;
}
int left = 0, right = nums.length - 1;
while(left < right){
// 向下取整
int mid = (right - left) / 2 + left;
if(nums[mid] >= target){
right = mid;
}else{
left = mid + 1;
}
}
// 判断该数是否存在
if(nums[left] != target) return -1;
return left;
}
//4.寻找最后一个等于 target 的数下标
int search4(int[] nums, int target){
if(nums == null || nums.length <= 0){
return -1;
}
int left = 0, right = nums.length - 1;
while(left < right){
//向上取整
int mid = (right - left + 1) / 2 + left;
if(nums[mid] <= target){
left = mid;
}else{
right = mid - 1;
}
}
// 判断该数是否存在
if(nums[left] != target) return -1;
return left;
}
}
剑指 Offer 53 - II. 0～n-1中缺失的数字
视频讲解直达： 本题视频讲解
class Solution {
public int missingNumber(int[] nums) {
int l = 0, r = nums.length - 1;
while(l < r){
int mid = (r - l) / 2 + l;
if(nums[mid] == mid) l = mid + 1;
else r = mid;
}
return nums[l] == l ? l + 1 : l;
}
}
剑指 Offer 54. 二叉搜索树的第k大节点
视频讲解直达： 本题视频讲解
class Solution {
int k = 0;
int target = 0;
public int kthLargest(TreeNode root, int k) {
// 中序遍历：有序的序列 左 根 右 从小到大排序的
// 右 根 左 从大到小的排序
this.k = k;
right_root_left(root);
return target;
}
void right_root_left(TreeNode root){
if(root == null || k <= 0) return;
right_root_left(root.right);
// 打印当前根节点
k--;
if(k == 0){
target = root.val;
}
right_root_left(root.left);
}
}
剑指 Offer 55 - I. 二叉树的深度
视频讲解直达： 本题视频讲解
class Solution {
public int maxDepth(TreeNode root) {
if(root == null) return 0;
int left = maxDepth(root.left);
int right = maxDepth(root.right);
return Math.max(left, right) + 1;
}
}
剑指 Offer 55 - II. 平衡二叉树
视频讲解直达： 本题视频讲解
class Solution {
// nlogn 空间 On 方法2:时间 On,空间O
public boolean isBalanced(TreeNode root) {
if(root == null) return true;
if(maxDepth(root) == -1) return false;
return true;
}
public int maxDepth(TreeNode root) {
if(root == null) return 0;
int left = maxDepth(root.left);
if(left == -1) return -1;
int right = maxDepth(root.right);
if(right == -1) return -1;
// 返回-1表示不符合条件了
if(Math.abs(left - right) > 1) return -1;
return Math.max(left, right) + 1;
}
}
剑指 Offer 56 - I. 数组中数字出现的次数
视频讲解直达： 本题视频讲解
class Solution {
public int[] singleNumbers(int[] nums) {
int z = 0;
for(int i = 0;i < nums.length; i++){
z = z ^ nums[i];
}
int m = 1;
while((m & z) == 0){
m = m << 1;
}
int x = 0, y = 0;
for(int i = 0;i < nums.length; i++){
if((nums[i] & m) == 0){
//结果为 0 的子数组，一边统计用异或统计x
x = x ^ nums[i];
} else {
//结果为 1 的子数组，一边统计用异或统计y
y = y ^ nums[i];
}
}
return new int[]{x, y};
}
}
剑指 Offer 56 - II. 数组中数字出现的次数 II
视频讲解直达： 本题视频讲解
class Solution {
public int singleNumber(int[] nums) {
int[] res = new int[32];
int m = 1;
int sum = 0;
for(int i = 0; i < 32; i++){
for(int j = 0; j < nums.length; j++){
if((nums[j] & m) != 0){
res[i]++;
}
}
res[i] = res[i] % 3;
sum = sum + res[i] * m;
m = m << 1;
}
return sum;
}
}
剑指 Offer 57. 和为s的两个数字
视频讲解直达： 本题视频讲解
class Solution {
public int[] twoSum(int[] nums, int target) {
if(nums == null || nums.length < 2){
return new int[0];
}
int i = 0, j = nums.length - 1;
while(i < j){
if(nums[i] + nums[j] > target){
j--;
}else if(nums[i] + nums[j] < target){
i++;
}else{
return new int[]{nums[i], nums[j]};
}
}
return new int[0];
}
}
剑指 Offer 57 - II. 和为s的连续正数序列
视频讲解直达： 本题视频讲解
class Solution {
public int[][] findContinuousSequence(int target) {
List res = new ArrayList<>();
int i = 1, j = 1;
int sum = 1;
while(i <= target/2){
if(sum < target){
j++;
sum = sum + j;
} else if(sum > target){
sum = sum - i;
i++;
} else {
int[] temp = new int[j - i + 1];
int index = 0;
for(int k = i; k <= j; k++){
temp[index++] = k;
}
sum = sum - i;
i++;
j++;
sum = sum + j;
res.add(temp);
}
}
return res.toArray(new int[res.size()][]);
}
}
剑指 Offer 58 - I. 翻转单词顺序
视频讲解直达： 本题视频讲解
class Solution {
public String reverseWords(String s) {
// split
if(s == null || s.length() <= 0){
return s;
}
s = s.trim();
StringBuilder build = new StringBuilder();
int i = s.length() - 1, j = i;
while(i >= 0){
while(i >= 0 && s.charAt(i) != ' ') i--;
//[i+1, j];
build.append(s.substring(i+1, j+1) + " ");
while(i >= 0 && s.charAt(i) == ' ') i--;
j = i;
}
return build.toString().trim();
}
}
剑指 Offer 58 - II. 左旋转字符串
视频讲解直达： 本题视频讲解
class Solution {
public String reverseLeftWords(String s, int n) {
StringBuilder build = new StringBuilder();
int len = s.length();
for(int i = n; i < len + n; i++){
build.append(s.charAt(i%len));
}
// for(int i = 0; i < n; i++){
// build.append(s.charAt(i));
// }
return build.toString();
}
}
剑指 Offer 59 - I. 滑动窗口的最大值
视频讲解直达： 本题视频讲解
class Solution {
public int[] maxSlidingWindow(int[] nums, int k) {
if(nums == null || nums.length <= 1){
return nums;
}
LinkedList queue = new LinkedList<>();
int[] res = new int[nums.length - k + 1];
int index = 0;
//K
for(int i = 0; i < nums.length; i++){
while(!queue.isEmpty() && nums[queue.peekLast()] <= nums[i]){
queue.pollLast();
}
queue.add(i);
if(queue.peekLast() - k == queue.peek()){
queue.poll();
}
if(i + 1 >= k){
res[index++] = nums[queue.peek()];
}
}
return res;
}
}
剑指 Offer 60. n个骰子的点数
视频讲解直达： 本题视频讲解
class Solution {
public double[] dicesProbability(int n) {
int[][] dp = new int[n+1][6*n+1];
for(int i = 1; i <= 6; i++){
dp[1][i] = 1;
}
for(int i = 2; i <= n; i++){
for(int j = i; j <= 6 * i; j++){
for(int k = 1; k <= 6; k++){
if(j < k) break;
dp[i][j] += dp[i-1][j-k];
}
}
}
double[] res = new double[5*n + 1];
int index = 0;
double sum = Math.pow(6, n);
for(int i = n; i <= 6 * n; i++){
res[index++] = dp[n][i] / sum;
}
return res;
}
}
剑指 Offer 61. 扑克牌中的顺子
视频讲解直达： 本题视频讲解
class Solution {
public boolean isStraight(int[] nums) {
// 排序法 nlogn
// 集合 n，n
// 如果要成为一个顺子，则需要 满足两个条件
// 1、不存在有重复的数，大小王除外
// 2、最大值 - 最小值 < 5,大小王除外
Set set = new HashSet<>();
int max = -1, min = 20;
for(int i = 0; i < nums.length; i++){
if(nums[i] == 0) continue;
if(set.contains(nums[i]))return false;
set.add(nums[i]);
max = Math.max(nums[i], max);
min = Math.min(nums[i], min);
}
return max - min < 5;
}
}
剑指 Offer 62. 圆圈中最后剩下的数字
视频讲解直达： 本题视频讲解
class Solution {
// 时间n 空间 1
public int lastRemaining(int n, int m) {
if( n == 0) return n;
//return (lastRemaining(n - 1, m) + m) % n;
// 优化
int res = 0;
for(int i = 1; i <= n; i++){
res = (res + m) % i;
}
return res;
}
}
剑指 Offer 63. 股票的最大利润
视频讲解直达： 本题视频讲解
class Solution {
public int maxProfit(int[] prices) {
int min = Integer.MAX_VALUE;
int max = 0;
for(int i = 0; i < prices.length; i++){
if(prices[i] < min){
min = prices[i];
}else{
max = Math.max(max, prices[i] - min);
}
}
return max;
}
}
剑指 Offer 64. 求1+2+…+n
视频讲解直达： 本题视频讲解
class Solution {
int sum = 0;
public int sumNums(int n) {
// 与或门
boolean flag = n >= 1 && sumNums(n - 1) < 1;
sum = sum + n;
return sum;
}
}
剑指 Offer 68 - I. 二叉搜索树的最近公共祖先
视频讲解直达： 本题视频讲解
class Solution {
// On,O1
public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
while(root != null){
if(root.val > p.val && root.val > q.val){
root = root.left;
} else if(root.val < p.val && root.val < q.val){
root = root.right;
} else {
return root;
}
}
return null;
}
}
[/rihide]
评论(2)
打卡
打卡是在 B 站的每个视频下面打卡！！！！！