剑指OFFER学习总结！

月伴飞鱼2025-09-102025-09-10

3数组中重复的数字

找出数组中重复的数字。

在一个长度为 n 的数组 nums 里的所有数字都在 0～n-1 的范围内。

数组中某些数字是重复的，但不知道有几个数字重复了，也不知道每个数字重复了几次。

请找出数组中任意一个重复的数字。

示例 1：

1
2
3

输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

class Solution {
    public int findRepeatNumber(int[] nums) {
        int i = 0;
        while(i < nums.length) {
            if(nums[i] == i) {
                i++;
                continue;
            }
            if(nums[nums[i]] == nums[i]) {
              return nums[i];
            }
            int tmp = nums[i];
            nums[i] = nums[tmp];
            nums[tmp] = tmp;
        }
        return -1;
    }
}

4二维数组中的查找

class Solution {
    private boolean flag = false; // 如果flag等于false则没有该证书，如果等于true则有
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        // 从右上角开始，路径只有左和下
        // 所以如果target大于当前值，就往左，如果小于，就往下

        // 数组问题记得判空
        if (matrix.length == 0 || matrix[0].length == 0) {
            return false;
        }
        int row = 0, column = matrix[0].length - 1;

        while (row < matrix.length && column >= 0) {
            if (matrix[row][column] == target) {
                return true;
            } else if (matrix[row][column] > target) {
                column--;
            } else {
                row++;
            }
        }
        return false;
    }
}

6从尾到头打印链表

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    ArrayList<Integer> tmp = new ArrayList<Integer>();
    public int[] reversePrint(ListNode head) {
        recur(head);
        int[] res = new int[tmp.size()];
        for(int i = 0; i < res.length; i++) {
            res[i] = tmp.get(i);
        }
        return res;
    }
    void recur(ListNode head) {
        if(head == null) {
            return;
        }
        recur(head.next);
        tmp.add(head.val);
    }
}

时间复杂度 O(N)：遍历链表，递归 N 次。

空间复杂度 O(N)：系统递归需要使用 O(N) 的栈空间。

9用两个栈实现队列

class CQueue {
    //两个栈
    Stack<Integer> input,output;
    public CQueue() {
        input = new Stack<Integer>();
        output = new Stack<Integer>();
    }
    
    public void appendTail(int value) {
        input.push(value);
    }
    public int deleteHead() {
        //转移操作
        if(output.empty()){
            if(input.empty()){
                return -1;
            }
            while(!input.empty()){
                output.push(input.pop());
            }
        }
        return output.pop();
    }
}

15二进制中1的个数

public class Solution {
    public int hammingWeight(int n) {
        int count = 0;
        while(n!=0) {
            n = n&(n-1);
            count++;
        }
        return count;
    }
}

18删除链表的节点

给定单向链表的头指针和一个要删除的节点的值，定义一个函数删除该节点。

返回删除后的链表的头节点。

class Solution {
    public ListNode deleteNode(ListNode head, int val) {
        if (head == null) {
            return null;
        }
        if (head.val == val) {
            return head.next;
        }
        
        ListNode pre = head, cur = head.next;
        while (cur!=null&&cur.val!=val) {
            pre=cur;
            cur=cur.next;
        }
        if (cur!=null) {
            pre.next=cur.next;
        }
        return head;
    }
}

21调整数组顺序使奇数位于偶数前面

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有奇数位于数组的前半部分，所有偶数位于数组的后半部分。

示例：

输入：nums = [1,2,3,4]

输出：[1,3,2,4]

class Solution {
    public int[] exchange(int[] nums) {
        int i = 0, j = nums.length - 1, tmp;
        while(i < j) {
            while(i < j && (nums[i] & 1) == 1) {
                i++;
            }
            while(i < j && (nums[j] & 1) == 0) {
                j--;
            }
            tmp = nums[i];
            nums[i] = nums[j];
            nums[j] = tmp;
        }
        return nums;
    }
}

22链表中倒数第K个节点

输入一个链表，输出该链表中倒数第K个结点。

class Solution {
    public ListNode getKthFromEnd(ListNode head, int k) {
        if (head == null) {
            return null;
        }
        //1->2->3->4->5
        ListNode pre = head, after = head;
        for (int i = 0; i < k;i++) {
            pre = pre.next;
        }
        while (pre != null) {
            pre = pre.next;
            after = after.next;
        }
        return after;
    }
}

24反转链表

迭代

class Solution {
    public ListNode reverseList(ListNode head) {
        ListNode pre = null;
        ListNode cur = head;
        while(cur!=null) {
            //记录当前节点的下一个节点
            ListNode tmp = cur.next;
            //然后将当前节点指向pre
            cur.next = pre;
            //pre和cur节点都前进一位
            pre = cur;
            cur = tmp;
        }
        return pre;
    }
}

递归

class Solution {
    public ListNode reverseList(ListNode head) {
        //递归终止条件是当前为空，或者下一个节点为空
        if(head==null || head.next==null) {
            return head;
        }
        //这里的cur就是最后一个节点
        ListNode cur = reverseList(head.next);
        //如果链表是 1->2->3->4->5，那么此时的cur就是5
        //而head是4，head的下一个是5，下下一个是空
        //所以head.next.next 就是5->4
        head.next.next = head;
        //防止链表循环，需要将head.next设置为空
        head.next = null;
        //每层递归函数都返回cur，也就是最后一个节点
        return cur;
    }
}

25合并两个排序的链表

迭代

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null || l2 == null) {
            return l1 == null ? l2 : l1;
        }

        ListNode head = new ListNode(-1);//新增头节点
        ListNode cur = head;//指向已合并部分链表的最后一个节点

        while(l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                cur.next = l1;
                l1 = l1.next;
            } else {
                cur.next = l2;
                l2 = l2.next;
            }
            cur = cur.next;
        }
        //不为空的那条链表的剩余部分接在合并链表的末尾
        cur.next = (l1 == null ? l2 : l1);
        return head.next;
    }
}

递归

class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        }
        if (l2 == null) {
            return l1;
        }
        if (l1.val <= l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

26树的子结构

class Solution {
    public boolean isSubStructure(TreeNode A, TreeNode B) {
        if (A == null || B == null) {
            return false;
        }
        //先从根节点判断B是不是A的子结构，如果不是在分别从左右两个子树判断
        //只要有一个为true，就说明B是A的子结构
        return isSub(A, B) || isSubStructure(A.left, B) || isSubStructure(A.right, B);
    }

    boolean isSub(TreeNode A, TreeNode B) {
        //这里如果B为空，说明B已经访问完了，确定是A的子结构
        if (B == null) {
            return true;
        }
        //如果B不为空A为空，或者这两个节点值不同，说明B树不是A的子结构，直接返回false
        if (A == null || A.val != B.val) {
            return false;
        }
        //当前节点比较完之后还要继续判断左右子节点
        return isSub(A.left, B.left) && isSub(A.right, B.right);
    }
}

时间复杂度 O(MN) ：

其中 M,N 分别为树 A 和树 B 的节点数量，先序遍历树 A 占用 O(M) ，每次调用 isSub(A, B) 判断占用 O(N) 。

空间复杂度 O(M)

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;
        }
        TreeNode left = root.left;
        TreeNode right = root.right;
        root.left = right;
        root.right = left;
        mirrorTree(root.left);
        mirrorTree(root.right);
        return root;
    }
}

时间复杂度：O(n)，其中 n 是二叉树的结点数，每个结点都被访问一次，对于每个结点交换左右子树的时间都是 O(1)。

空间复杂度：O(n)，其中 n 是二叉树的结点数。

空间复杂度主要是递归调用的栈空间，取决于二叉树的高度，最坏情况下二叉树的高度是 O(n)。

迭代

class Solution {
    public TreeNode mirrorTree(TreeNode root) {
        if (root == null) {
            return null;
        }
        Queue<TreeNode> queue = new ArrayDeque<TreeNode>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            TreeNode left = node.left, 
          	right = node.right;
            node.left = right;
            node.right = left;
            if (right != null) {
                queue.offer(right);
            }
            if (left != null) {
                queue.offer(left);
            }
        }
        return root;
    }
}

31栈的压入、弹出序列

输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。

class Solution {
    public boolean validateStackSequences(int[] pushed, int[] popped) {
        Stack<Integer> stack = new Stack<>();
        int popIndex = 0;
        for (int i = 0; i < pushed.length; i++){
            stack.push(pushed[i]);
            while(!stack.isEmpty()&&stack.peek()==popped[popIndex]) {
                stack.pop();
                popIndex++;
            }
        }
        return stack.isEmpty();
    }
}

32II从上到下打印二叉树II

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        List<List<Integer>> result = new ArrayList<>();
        if (root==null) {
            return result;
        }

        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()) {
            int size = queue.size();
            List<Integer> temp = new ArrayList<>();
            for (int i = 0;i<size;i++) {
                TreeNode node = queue.poll();
                temp.add(node.val);
                if (node.left!=null) {
                    queue.add(node.left);
                }
                if (node.right!=null) {
                    queue.add(node.right);
                }
            }
            result.add(temp);
        }
        return result;
    }
}

32III从上到下打印二叉树III

class Solution {
    public List<List<Integer>> levelOrder(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> res = new ArrayList<>();
        if(root != null) {
            queue.add(root);
        }
        while(!queue.isEmpty()) {
            List<Integer> tmp = new ArrayList<>();
            for(int i = queue.size(); i > 0; i--) {
                TreeNode node = queue.poll();
                tmp.add(node.val);
                if(node.left != null) {
                    queue.add(node.left);
                }
                if(node.right != null) {
                    queue.add(node.right);
                }
            }
            if((res.size() & 1) == 1) {
                Collections.reverse(tmp);
            }
            res.add(tmp);
        }
        return res;
    }
}

33二叉搜索树的后序遍历序列

请实现一个函数来判断整数数组 postorder 是否为二叉搜索树的后序遍历结果。

class Solution {
    public boolean verifyPostorder(int[] postorder) {
        return helper(postorder, 0, postorder.length - 1);
    }

    boolean helper(int[] postorder, int left, int right) {
        if (left >= right) {
            return true;
        }

        //因为数组中最后一个值postorder[right]是根节点，这里从左往右找出第一个比
        //根节点大的值，他后面的都是根节点的右子节点（包含当前值，不包含最后一个值
        //因为最后一个是根节点），他前面的都是根节点的左子节点
        int mid = left;
        int root = postorder[right];
        while (postorder[mid] < root) {
            mid++;
        }
        int temp = mid;
        //因为postorder[mid]前面的值都是比根节点root小的
        //我们还需要确定postorder[mid]后面的值都要比根节点root大
        //如果后面有比根节点小的直接返回false
        while (temp < right) {
            if (postorder[temp++] < root) {
                return false;
            }
        }
        //然后对左右子节点进行递归调用
        return helper(postorder, left, mid - 1) && helper(postorder, mid, right - 1);
    }
}

34二叉树中和为某一值的路径

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
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();
    }
}

39数组中出现次数超过一半的数字

class Solution {
    public int majorityElement(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int result = nums[0], count = 1;
        for (int num : nums) {
            if (num == result) {
                count++;
            } else {
                count--;
            }
            if (count == 0) {
                count = 1;
                result = num;
            }
        }
        return result;
    }
}

42连续子数组的最大和

class Solution {
    public int maxSubArray(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int result = nums[0];
        int current = nums[0];
        for (int i = 1; i<nums.length;i++) {
            current = Math.max(current + nums[i], nums[i]);
            result = Math.max(result, current);
        }
        return result;
    }
}

52两个链表的第一个公共节点

使用两个指针 node1，node2 分别指向两个链表 headA，headB 的头结点，然后同时分别逐结点遍历。

当 node1 到达链表 headA 的末尾时，重新定位到链表 headB 的头结点。

当 node2 到达链表 headB 的末尾时，重新定位到链表 headA 的头结点。

这样，当它们相遇时，所指向的结点就是第一个公共结点。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */
class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        if (headA == null || headB == null) {
            return null;
        }

        ListNode node1 = headA, node2 = headB;
        while (node1 != node2) {
            //当node1为空，则从headB遍历
            node1 = (node1 == null ? headB : node1.next);
            //当node2为空，则从headA遍历
            node2 = (node2 == null ? headA : node2.next);
        }
        return node1;
    }
}

53缺失的数字

一个长度为n-1的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0到n-1之内。

在范围0到n-1的n个数字中有且只有一个数字不在该数组中，请找出这个数字。

由于是排序数组，考虑使用二分查找算法：

当中间数字等于其下标时，在后半部分查找

当中间数字不等于其下标时

如果中间数字的前一个数字也不等于其下标，则在前半部分查找

如果中间数字的前一个数字等于其下标，则说明中间数字的下标即为我们所要找的数字

class Solution {
    public int missingNumber(int[] nums) {
        int i = 0, j = nums.length - 1;
        while(i <= j) {
            int m = (i + j) / 2;
            if(nums[m] == m) {
                i = m + 1;
            } else {
                j = m - 1;
            }
        }
        return i;
    }
}

54二叉搜索树的第K大节点

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    int res, k;
    public int kthLargest(TreeNode root, int k) {
        this.k = k;
        dfs(root);
        return res;
    }
    void dfs(TreeNode root) {
        if(root == null) {
            return;
        }
        dfs(root.right);
        if(k == 0) {
            return;
        }
        if(--k == 0) {
            res = root.val;
        }
        dfs(root.left);
    }
}

55二叉树的深度

DFS

class Solution {
    public int maxDepth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int leftLen = maxDepth(root.left);
        int rightLen = maxDepth(root.right);
        return Math.max(leftLen, rightLen) + 1;
    }
}

时间复杂度 O(N) ： N 为树的节点数量，计算树的深度需要遍历所有节点。

BFS

class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int res = 0;
        while(!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0;i<size;i++) {
                TreeNode node = queue.poll();
                if(node.left != null) {
                    queue.offer(node.left);
                }
                if(node.right != null) {
                    queue.offer(node.right);
                }
            }
            res++;
        }
        return res;
    }
}

63股票的最大利润

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) {
            return 0;
        }
        int minPrice = Integer.MAX_VALUE;
        int profit = 0;
        for (int price : prices) {
            minPrice = Math.min(minPrice, price);
            profit = Math.max(profit, price - minPrice);
        }
        return profit;
    }
}

65不用加减乘除做加法

class Solution {
    public int add(int a, int b) {
        while(b != 0) { // 当进位为 0 时跳出
            int c = (a & b) << 1;  // c = 进位
            a ^= b; // a = 非进位和
            b = c; // b = 进位
        }
        return a;
    }
}

68I二叉搜索树的最近公共祖先

从根结点开始搜索，如果根结点的值大于节点p 和节点 q，证明这两个节点都在当前节点的左子树上。

于是可以继续沿着左子树向下搜索

如果根结点的值小于节点p 和节点 q，证明这两个节点都在当前节点的右子树上，可以继续沿着右子树向下搜索

如果当前节点大于一个节点且小于另一个节点，则证明两个节点分别处于当前节点的左右两侧。

则该节点就是这两个节点的公共祖先

若都不满足则返回空

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || p == null || q == null) {
            return null;
        }
        if (root.val < p.val && root.val < q.val && root.right != null) {
            return lowestCommonAncestor(root.right, p, q);
        }
        if (root.val > p.val && root.val > q.val && root.left != null) {
            return lowestCommonAncestor(root.left, p, q);
        }
        return root;
    }
}

68II二叉树的最近公共祖先

左右子树分别进行递归，即查找左右子树上是否有p结点或者q结点，就一共有4种情况：

第一种情况：左子树和右子树均找没有p结点或者q结点

第二种情况：左子树上能找到，但是右子树上找不到，此时就应当直接返回左子树的查找结果

第三种情况：右子树上能找到，但是左子树上找不到，此时就应当直接返回右子树的查找结果

第四种情况：左右子树上均能找到，说明此时的p结点和q结点分居root结点两侧，此时就应当直接返回root结点了

class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        if (root == null || root == p || root == q) {
            return root;
        }
        TreeNode left = lowestCommonAncestor(root.left, p, q);
        TreeNode right = lowestCommonAncestor(root.right, p, q);
        if (left == null) {
            return right;
        }
        if (right == null) {
            return left;
        }
        return root;
    }
}