分享字节面试经常出现的算法题和解法。

1、反转链表

牛客 78 反转链表：

https://www.nowcoder.com/practice/75e878df47f24fdc9dc3e400ec6058ca

 //遍历解法
 public static ListNode reverseList(ListNode head) {

        if(head == null) return null;

        ListNode cur = head,pre = null;
        while(cur != null){

            //记录 cur.next 用于更新 pre
            ListNode next = cur.next;

            //反转当前节点和前一个节点的指针方向
            cur.next = pre;
            pre = cur;
            cur = next;

        }
        return pre;

    }

    //递归解法
    public ListNode reverseList(ListNode head) {

        if(head == null || head.next == null) return head;

        ListNode last = reverseList(head.next);
        head.next.next = head;
        head.next = null;

        return last;

    }

2、丑数

力扣 263 丑数：

https://leetcode.cn/problems/ugly-number/description/

思路：

循环分解 2、3、5，直到因子只剩 1 或其他。

public boolean isUgly(int n) {

    if (n <= 0) return false;
    // 如果 n 是丑数，分解因子应该只有 2, 3, 5
    while (n % 2 == 0) n = n / 2;
    while (n % 3 == 0)n = n / 3;
    while (n % 5 == 0) n = n / 5;
    return n == 1;

}

3、设计 LRU 缓存结构

力扣 146/牛客 93 设计 LRU 缓存结构：

https://leetcode.cn/problems/lru-cache/description/
https://www.nowcoder.com/practice/5dfded165916435d9defb053c63f1e84?tpId=196

思路：

哈希表+链表
- 借助链表的有序性使得链表元素维持插入顺序，
- 同时借助哈希映射的快速访问能力使得我们可以在 O(1) 时间访问链表的任意元素。
- 提取 makeRecently 公共方法

    private LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();

    private int capacity;


    public Solution(int capacity) {
        this.capacity = capacity;
    }

    //不在缓存中返回-1，在的话返回之前要把此key设置为最近使用
    public int get(int key) {

        if(!cache.containsKey(key)) return -1;

        // 将 key 变为最近使用
        makeRecently(key);
        return cache.get(key);


    }

    public void set(int key, int value) {
        //key在 cache 里，更新 key 为最近使用
        if(cache.containsKey(key)){
            //修改 key 的值
            cache.put(key,value);
            //更新key为最近使用
            makeRecently(key);
            return;
        }

        //缓存大小达到了容量上限，删除最近的
        if(cache.size() >= capacity){
            //链表头部就是最近未使用的
            int oldestKey = cache.keySet().iterator().next();
            cache.remove(oldestKey);
        }
        //将新key添加到链表结尾
        cache.put(key,value);

    }

    public void makeRecently(int key){
        int val = cache.get(key);
        // 删除 key，重新插入到队尾
        cache.remove(key);
        cache.put(key,val);
    }

4、二叉树先中后遍历打印

牛客 45 二叉树先中后打印：

https://www.nowcoder.com/practice/a9fec6c46a684ad5a3abd4e365a9d362?tpId=117

思路：

前中后位置追加节点值

private ArrayList<Integer> pre = new ArrayList<>();
private ArrayList<Integer> in = new ArrayList<>();
private ArrayList<Integer> post = new ArrayList<>();


public int[][] threeOrders (TreeNode root) {

    traverse(root);
    int nodeSize = pre.size();
    int [][] res = new int[3][nodeSize];

    for (int i = 0; i < nodeSize; i++) {
        res[0][i] = pre.get(i);
        res[1][i] = in.get(i);
        res[2][i] = post.get(i);
    }

    return res;

}


private void traverse(TreeNode root) {

    if (root == null) return ;

    //前序位置为前序结果集追加结果
    pre.add(root.val);
    traverse((root.left));
    //中序位置为中序结果集追加结果
    in.add(root.val);
    traverse((root.right));
    //后序位置为中序结果集追加结果
    post.add(root.val);
}

5、二叉搜索树与双向链表

剑指 36 二叉搜索树与双向链表：

https://www.nowcoder.com/practice/947f6eb80d944a84850b0538bf0ec3a5?tpId=13

思路：

二叉搜索树中序遍历升序，中序位置做头节点和前驱指针的初始化以及前驱节点 right 和当前节点 left 的更新

    //返回的第一个指针，即为最小值，先定为null
    TreeNode head = null;
    //中序遍历当前值的上一位，初值为最小值，先定为null
    TreeNode pre = null;
    public TreeNode Convert(TreeNode pRootOfTree) {
        if(pRootOfTree == null) return null;
        //中序遍历为升序，中序位置构建双向链表
        traverse(pRootOfTree);
        return head;
    }

    public void traverse(TreeNode root){
        //中序递归，叶子为空则返回
        if(root == null) return;

        //首先递归到最左最小值 
        traverse(root.left);
        
        //左侧都走完，head 为空，要初始化头节点和前驱指针
        if(head == null){
            head = root;
            pre = root;
        }
        else{
            //连接前驱指针的right和当前指针的left
            pre.right = root;
            root.left = pre;
            //更新前驱指针为当前节点
            pre = root;
        }
        traverse(root.right);
    }

6、数字在升序数组中出现的次数

牛客 74 数字在升序数组中出现的次数：

https://www.nowcoder.com/practice/70610bf967994b22bb1c26f9ae901fa2?tpId=117

思路：

目标值在升序数组最左侧的索引和最右侧的索引可以锁定次数，转换成左边界二分搜索和右边界二分搜索的问题。

   public int GetNumberOfK (int[] nums, int k) {
        // write code here
        int leftIndex = leftBoundSearch(nums,k);
        int rightIndex = rightBoundSearch(nums,k);
        
        if(leftIndex == -1 || rightIndex == -1) return 0;

        return rightIndex - leftIndex + 1;
    }

    private int leftBoundSearch(int[] nums, int target){

        int left = 0,right = nums.length - 1;
        //搜索区间为 [left,right]
        while(left <= right){

            int mid = left + (right - left)/2;
            if(nums[mid] < target){
                //搜索区间变为 [mid + 1,right]
                left = mid + 1;
            }else if(nums[mid] > target){
                //搜索区间变为 [left,mid - 1]
                right = mid - 1;
            }else if(nums[mid] == target){
                //收缩右侧边界
                right = mid - 1;
            }

        }
        //检查出界情况
        if(left >= nums.length || nums[left] != target) return -1;

        return left;
    }


    private int rightBoundSearch(int[] nums, int target){

        int left = 0,right = nums.length - 1;
        while(left <= right){

            int mid = left + (right - left)/2;
            if(nums[mid] < target){
                left = mid + 1;
            }else if(nums[mid] > target){
                right = mid - 1;
            }else if(nums[mid] == target){
                //收缩左侧边界
                left = mid + 1;
            }

        }
        //检查出界情况
        if(right < 0 || nums[right] != target) return -1;

        return right;
    }

7、二叉树的层序遍历

牛客 15 二叉树的层序遍历：

https://www.nowcoder.com/practice/04a5560e43e24e9db4595865dc9c63a3?tpId=117

思路：

构造一个队列存放当前层的节点

public class Solution {

    ArrayList<ArrayList<Integer>> res = new ArrayList<>();

    public ArrayList<ArrayList<Integer>> levelOrder (TreeNode root) {
        // write code here
        traverse(root);
        return res;
    }

    //层序遍历，构造一个队列存放当前层的节点
    private void traverse(TreeNode root){

        if(root == null) return;

        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);

        while(!queue.isEmpty()){

            //当前层队列的大小，用于遍历
            int size = queue.size();
            ArrayList<Integer> curLevelRes = new ArrayList<>();

            for(int i = 0; i <size;i++){
                
                //遍历到的节点出队
                TreeNode node = queue.poll();
                //【逻辑处理位置】添加到当前层结果中
                curLevelRes.add(node.val);
                //如果有子节点，入队，作为下一层处理
                if(node.left != null){
                    queue.offer(node.left);
                }

                if(node.right != null){
                    queue.offer(node.right);
                }
            }

            res.add(curLevelRes);
        }

    }
}

8、两数之和

力扣 1 两数之和/牛客 61 两数之和

https://www.nowcoder.com/practice/20ef0972485e41019e39543e8e895b7f?tpId=117

    public int[] twoSum (int[] numbers, int target) {
        
        // 维护 val -> index 的映射
        HashMap<Integer,Integer> val2Index = new HashMap<>();

        for(int i = 0; i < numbers.length;i++){

            // 查表，看看是否有能和 nums[i] 凑出 target 的元素
            int need = target - numbers[i];

            if(val2Index.containsKey(need)){
                return new int[]{val2Index.get(need) + 1,i + 1};
            }
            // 存入 val -> index 的映射
            val2Index.put(numbers[i],i);
        }

        return null;
    }

9、合并两个排序的链表

牛客 33 合并两个排序链表：

https://www.nowcoder.com/practice/d8b6b4358f774294a89de2a6ac4d9337?tpId=117

思路：

虚拟头节点、结果链表指针、表一指针、表二指针

    public ListNode Merge (ListNode pHead1, ListNode pHead2) {
        // 虚拟头节点
        ListNode dummy = new ListNode(-1),p = dummy;
        ListNode p1 = pHead1, p2 = pHead2;

        
        while (p1 != null && p2 != null) {

             // 比较 p1 和 p2 两个指针，将值较小的节点接到 p 指针
            if (p1.val > p2.val) {
                p.next = p2;
                p2 = p2.next;

            } else {
                p.next = p1;
                p1 = p1.next;
            }
            // p 指针不断前进
            p = p.next;
        }

        // p1 走完，把 p2 剩下的节点接到 p 上
        if (p1 == null) {
            p.next = p2;
        }

        // p2 走完，把 p1 剩下的节点接到 p 上
        if (p2 == null) {
            p.next = p1;
        }
        return dummy.next;
    }

10、用两个栈实现队列s

力扣 232/牛客 76 用两个栈实现队列

https://www.nowcoder.com/practice/54275ddae22f475981afa2244dd448c6?tpId=117

    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

    public void push(int node) {
        stack1.push(node);

    }

    public int pop() {

        if (stack2.isEmpty()) {

            while (!stack1.isEmpty()) {
                int node = stack1.pop();
                stack2.push(node);
            }
        }

        return stack2.isEmpty() ? -1 : stack2.pop();
    }

11、跳台阶

牛客 68 跳台阶：

https://www.nowcoder.com/practice/8c82a5b80378478f9484d87d1c5f12a4?tpId=117

思路：

动态规划。
f(0)=1, f(1)=1,f(2)=2
状态转移方程为：dp[i] = dp[i-1]+dp[i-2]

public int jumpFloor (int number) {
        
        // dp[i] = dp[i-1] + dp[i-2]
        if(number == 0 || number == 1){
            return 1;
        }

        if(number == 2) return 2;

        return jumpFloor((number - 1)) + jumpFloor(number -2);
    }

12、链表中的节点每k个一组翻转

牛客 65 链表中的节点每k个一组翻转：

https://www.nowcoder.com/practice/b49c3dc907814e9bbfa8437c251b028e?tpId=117

思路：

递归：
- 终止条件：走到最后一个分组；返回值：头节点；本级任务翻转链表
- 翻转后，翻转链表的头节点充当了翻转后的尾节点，直接连接下一段要翻转的链表，即子问题。

    public ListNode reverseKGroup (ListNode head, int k) {
                
        //找到尾节点，锁定翻转范围
        ListNode tail = head;
        //遍历 k 次到尾部
        for(int i = 0; i < k;i++){

            if(tail == null){
                //不足k直接返回，不翻转
                return head;
            }
            tail = tail.next;
        }
        //翻转时需要当前节点和前序节点
        ListNode cur = head,pre = null;
        //在到达当前段尾节点前
        
        while(cur != tail){

            //记录 cur.next 用于更新 pre
            ListNode next = cur.next;
            //反转当前节点和前一个节点的指针方向
            cur.next = pre;
            pre = cur;
            cur = next;
        }
        //head 此时为链表尾部，连接下一段要翻转的链表（子问题）
        head.next = reverseKGroup(tail,k);

        return pre;

    }

13、连续子数组最大和

力扣 53/牛客 19

https://www.nowcoder.com/practice/459bd355da1549fa8a49e350bf3df484?tpId=117

思路：

动态规划。
- dp[i] = Math.max(nums[i], nums[i] + dp[i – 1]);
- 定义dp[i]为以 nums[i] 为结尾的「最大子数组和」。
- 状态转移方程：

    public int maxSubArray(int[] nums) {

        int n = nums.length;
        if (n == 0) return 0;

        //nums[i] 为结尾的「最大子数组和」为 dp[i]
        int[] dp = new int[n];
        //base case，第一个元素前面没有子数组
        dp[0] = nums[0];

        for (int i = 1; i < n; i++) {
            //状态转移方程
            dp[i] = Math.max(nums[i], nums[i] + dp[i - 1]);
        }

        int res = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            res = Math.max(res, dp[i]);
        }

        return res;
    }

14、最长无重复子数组

牛客 41 最长无重复子数组：

https://www.nowcoder.com/practice/b56799ebfd684fb394bd315e89324fb4?tpId=117&tqId=37816

思路：

滑动窗口

    public int maxLength (int[] arr) {
        // write code here

        //窗口值
        Set<Integer> window = new HashSet<>();
        int res = 0;
        int left = 0,right = 0;
        while(right < arr.length){

            //窗口里有值，说明重复，把当前值剔除，收缩左边界
            while(window.contains(arr[right])){
                window.remove(arr[left]);
                left++;
            }
            //窗口加值，扩充右边界
            window.add(arr[right]);
            right++;
            res = Math.max(res,right - left);
        }

        return res;
    }

15、判断链表中是否有环

牛客 4 判断链表中是否有环：

https://www.nowcoder.com/practice/650474f313294468a4ded3ce0f7898b9?tpId=117&tqId=37714

思路：

快慢指针，快指针走两步，慢指针走一步，相遇则有环

    public boolean hasCycle(ListNode head) {

        if (head == null || head.next == null) return false;

        //快慢指针，快指针走两步，慢指针走一步，相遇则有环
        ListNode slow = head, fast = head;

        while (fast != null && fast.next != null) {

            fast = fast.next.next;
            slow = slow.next;

            if (fast == slow) return true;
        }
        return false;

    }

16、合并两个有序的数组

力扣 88/牛客22 合并两个有序数组：

https://leetcode.cn/problems/merge-sorted-array/description/
https://www.nowcoder.com/practice/89865d4375634fc484f3a24b7fe65665?tpId=117

    public void merge(int A[], int m, int B[], int n) {
        
        //两个指针分别初始化数组最后一个元素，结果指针初始化结果数组最后一个元素
        int indexA = m - 1, indexB = n - 1, indexRes = A.length - 1;

        //从后向前生成结果数组，类似合并两个有序链表的逻辑
        while (indexA >= 0 && indexB >= 0 ) {

            if(A[indexA] > B[indexB]){
                A[indexRes] =  A[indexA];
                indexA--;
            }else{
                A[indexRes] =  B[indexB];
                indexB--;
            }

            indexRes--;
        }

        //本身在A数组中放元素，所以只有B数组还在的情况
        while (indexB >= 0) {
            A[indexRes] = B[indexB];
            indexB--;
            indexRes--;
        }

    }

17、两个链表的第一个公共节点

牛客 66 两个链表的第一个公共节点：

https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46?tpId=117

思路：

双指针，链表连起来移动

    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {

        //齐头并进,遍历1把2接起来，遍历2把1接起来，有相等说明有公共节点
        ListNode p1 = pHead1, p2 = pHead2;

        while (p1 != p2) {

            if (p1 == null) p1 = pHead2;
            else p1 = p1.next;

            if (p2 == null) p2 = pHead1;
            else p2 = p2.next;

        }
        return p1 ;
    }

18、链表中环的入口节点

牛客3 链表中环的入口节点：

https://www.nowcoder.com/practice/253d2c59ec3e4bc68da16833f79a38e4?tpId=117

思路：

找到环中相遇节点，然后前指针从头出发，再次相遇即入口节点

    public ListNode EntryNodeOfLoop(ListNode pHead) {

        if (pHead == null || pHead.next == null) return null;

        //找到环中相遇节点，然后前指针从头出发，再次相遇即入口节点
        ListNode slow = pHead, fast = pHead;

        while (fast != null && fast.next != null) {

            fast = fast.next.next;
            slow = slow.next;

            if (fast == slow) {
                break;
            }
        }

        if (fast == null) return null;

        slow = pHead;
        while (slow != fast) {
            slow = slow.next;
            fast = fast.next;
        }
        return slow;
    }

19、括号序列

牛客52 有效括号序列：

https://www.nowcoder.com/practice/37548e94a270412c8b9fb85643c8ccc2?tpId=117

思路：

栈。在有括号入栈是做合法性判断

    public boolean isValid (String s) {

        if(s == null || s.length() % 2 != 0) return false;

     Stack<Character> stack = new Stack<>();
        //遍历字符，左括号入栈，遇到右括号，检查栈顶元素是否和右括号匹配，匹配出栈，不匹配则不合法
        for (char c : s.toCharArray()) {

            if (c == '(' || c == '{' || c == '[')
                stack.push(c);
            else {
                if (!stack.isEmpty()) {
                    char zuoTop = stack.pop();

                    if (!isMatch(zuoTop, c)) {
                        return false;
                    }
                }else{
                    return false;
                }
            }

        }
        return stack.isEmpty();
    }

    private boolean isMatch(char zuo, char you) {
        if (zuo == '(' && you == ')') return true;
        if (zuo == '{' && you == '}') return true;
        if (zuo == '[' && you == ']') return true;
        return false;
    }

20、删除链表的倒数第n个节点

牛客 53 删除链表的倒数第n个节点：

https://www.nowcoder.com/practice/f95dcdafbde44b22a6d741baf71653f6?tpId=117

思路：

快慢指针，快指针先移动 n 步，慢指针开始移动，快指针到头时慢指针移动了 len-n 步，即倒数的节点。

    public ListNode removeNthFromEnd (ListNode head, int n) {

        ListNode dummy = new ListNode(-1);
        dummy.next = head;

        //删除倒数第n个节点，要找到倒数第n+1个节点
        ListNode pre = findFromEnd(dummy,n+1);

        pre.next = pre.next.next;
        return dummy.next;


    }


    //返回链表的倒数第K个节点
    ListNode findFromEnd(ListNode head,int k){
        
        ListNode slow = head,fast = head;
        //fast 先走k步
        for(int i=0; i <k;i++){
            fast = fast.next;
        }

        //同时走 n - k 步   
        while(fast != null){
            fast = fast.next;
            slow = slow.next;

        }
        //slow 指向第 n - k 个节点
        return slow;
    }

我是蜗牛，大厂程序员，专注技术原创和个人成长，正在互联网上摸爬滚打。欢迎关注我，和蜗牛一起成长，我们一起牛~下期见！

推荐阅读：

1120页的Leetcode算法刷题笔记，完整版PDF开放下载！

《Java 工程师成神之路》.pdf

更多内容请收藏：Java for You