面经题

我会带着你远行 2022-10-01 11:56 268阅读 0赞

**232.Implement Queue Using Stack**

class MyQueue {
    
        /** Initialize your data structure here. */
            Stack<Integer> s1;
            Stack<Integer> s2;
        public MyQueue() {
            s1 = new Stack<>();
            s2 = new Stack<>();
        }
        
        /** Push element x to the back of queue. */
        public void push(int x) {
            s1.push(x);
        }
        
        /** Removes the element from in front of queue and returns that element. */
        public int pop() {
            while (!s2.isEmpty()) {
                return s2.pop();
            }
            while (!s1.isEmpty()) {
                s2.push(s1.pop());
            }
            if (!s2.isEmpty()) {
                return s2.pop();
            }
            return -1;
        }
        
        //优化代码逻辑 先check s2是否为空
        public int pop() {
            if (s2.isEmpty()) {
                while (!s1.isEmpty()) {
                    s2.push(s1.pop());   
                }
            }
            return s2.pop();
        }
        
        /** Get the front element. */
        public int peek() {
            if (!s2.isEmpty()) {
                return s2.peek();
            }
            while (!s1.isEmpty()) {
                s2.push(s1.pop());
            }
            if (s2.isEmpty()) {
                return -1;
            }
            return s2.peek();
        }
        
        /** Returns whether the queue is empty. */
        public boolean empty() {
            return (s2.isEmpty() && s1.isEmpty());
        }
    }
    
    /** * Your MyQueue object will be instantiated and called as such: * MyQueue obj = new MyQueue(); * obj.push(x); * int param_2 = obj.pop(); * int param_3 = obj.peek(); * boolean param_4 = obj.empty(); */
    复制代码

**155.Min Stack**

*  题目: 实现一个包含返回栈中最小元素的方法的栈
 *  思路1: 两个栈来实现 -> 一个栈`s1`来存所有的元素, 另一个栈`s2`记录当前最小元素,
    
     *  push(): `s1`全都压入, `s2`在比较之后压入
     *  pop(): 如果弹出的是最小元素,那么两个栈同时弹出,如果弹出的不是最小元素,那么只有第一个栈弹出,最小栈不做操作
     *  getMin(): 直接返回`s2`的peek即可 最小栈中可能有重复值
 *  思路2: 一个栈来实现,相当于把**最小元素**这个信息记录在了当前栈中
    
     *  push(): 先判断新加入的元素是否比当前的元素小, 如果小的话,将上一个最小值push进栈,则上一个最小值有效的范围是两个值之间 \[-2,0,-3\]的输入会生成一个 \[-3, -2, 0, -2, MAX\] 的栈，-2是在\[-2,0,-2\]范围内有效的

class MinStack {
        int min = Integer.MAX_VALUE;
        private Stack<Integer> stack = new Stack<Integer>();
        
        public void push(int x) {
            // only push the old minimum value when the current 
            // minimum value changes after pushing the new value x
            if(x <= min){          
                this.stack.push(min);
                min=x;
            }
            this.stack.push(x);
        }
    
        public void pop() {
            // if pop operation could result in the changing of the current minimum value, 
            // pop twice and change the current minimum value to the last minimum value.
            if(stack.pop() == min) {
                min = this.stack.pop();
            }
        }
    
        public int top() {
            return this.stack.peek();
        }
    
        public int getMin() {
            return min;
        }
    }
    复制代码

#### Tree ####

**Binary Tree Preorder Traversal**

class Solution {
        public List<Integer> preorderTraversal(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            if (root == null) {
                return res;
            }
            Stack<TreeNode> stack = new Stack<>();
            stack.push(root);
            while (!stack.isEmpty()) {
                TreeNode node = stack.pop();
                res.add(node.val);
                if (node.right != null) {
                    stack.push(node.right);
                }
                if (node.left != null) {
                    stack.push(node.left);
                }
            }
            
            return res;
        }
    }
    复制代码

**Inorder Traversal**

class Solution {
        public List<Integer> inorderTraversal(TreeNode root) {
            List<Integer> res = new ArrayList<>();
            if (root == null) {
                return res;
            }
            Stack<TreeNode> stack = new Stack<>();
            while (!stack.isEmpty() || root != null) {
                // 先遍历所有的左子树节点
                while (root != null) {
                    stack.push(root);
                    root = root.left;
                }
                // 到了最左边之后再pop然后将根节点从栈中弹出, 遍历右子节点
                root = stack.pop();
                res.add(root.val);
                root = root.right;
            }
            
            return res;
        }
    }
    复制代码

**Postorder Traversal**

**二叉树的最长路径**

*  [www.cnblogs.com/miloyip/arc…][www.cnblogs.com_miloyip_arc]

**543. Diameter of Binary Tree**

*  题目:找出一个二叉树中的最长路径
 *  思路: 两种情况 1.经过root节点 left深度 + right深度 2.不经过root节点 直接max(left, right) + 1
 *

class Solution {    
        public int diameterOfBinaryTree(TreeNode root) {
            if (root == null) {
                return 0;
            }
            int diameter = 0;
            helper(root, diameter);
            return diameter;
        }
        
        private int helper(TreeNode root, int diameter) {
            if (root == null) {
                return 0;
            }
            int left = helper(root.left, diameter);
            int right = helper(root.right, diameter);
            diameter = Math.max(diameter, left + right);
            return Math.max(left, right) + 1; // 不过root节点
        }
    }
    复制代码

**判断一棵二叉树是否为完全二叉树**

*  思路: 四种节点 1.左右子树都存在 2.只存在左子树 3.只存在右子树 4.左右子树都不存在 如
    
     *  直接放入queue中
     *  可以是最后一层的靠左的节点
     *  不符合要求,如果发现这样的节点直接return false
     *  可以是倒数第二层的叶节点

import java.util.*;
    class TreeNode {
        int val = 0;
        TreeNode left = null;
        TreeNode right = null;
        public TreeNode(int val) {
            this.val = val;
        }
    }
    public class CheckCompletion {
        public boolean checking(TreeNode root) {
            Queue<TreeNode> queue = new LinkedList<TreeNode>();
            boolean leaf = false; // 叶子结点
            TreeNode left;
            TreeNode right;
            queue.add(root);
            while (!queue.isEmpty()) {
                root = queue.poll();
                left = root.left;
                right = root.right;
                if ((leaf&&(left!=null||right!=null)) || (left==null&&right!=null)) {
                    // 如果之前层遍历的结点没有右孩子，且当前的结点有左或右孩子，直接返回false
                    // 如果当前结点有右孩子却没有左孩子，直接返回false
                    return false;
                }
                if (left != null) {
                    queue.offer(root.left);
                }
                if (right != null) {
                    queue.offer(root.right);
                }else {
                    leaf = false; // 如果当前结点没有右孩子，那么之后层遍历到的结点必须为叶子结点
                }
            }
            return true;
        }
    }
    复制代码

**124.Binary Tree Maximum Path Sum** 问题: 返回一个非空二叉树中路径和最大的路径

public class Solution {
        int maxValue;
        
        public int maxPathSum(TreeNode root) {
            maxValue = Integer.MIN_VALUE;
            maxPathDown(root);
            return maxValue;
        }
        
        private int maxPathDown(TreeNode node) {
            if (node == null) return 0;
            int left = Math.max(0, maxPathDown(node.left));
            int right = Math.max(0, maxPathDown(node.right));
            maxValue = Math.max(maxValue, left + right + node.val);
            return Math.max(left, right) + node.val;
        }
    }
    复制代码

#### String ####

**415. Add Strings**

*  题目: 给出两个非负的字符串,求两个字符串向相加之后的结果
 *  思路: 两个字符串从后向前遍历,逐一相加,注意进位和遍历越界的情况

public class Solution {
        public String addStrings(String num1, String num2) {
            StringBuilder sb = new StringBuilder();
            int carry = 0;
            // 从后向前遍历
            for (int i = num1.length() - 1, j = num2.length() - 1; i >= 0 || j >= 0 || carry == 1; i--, j--) {
                int x = i < 0 ? 0 : num1.charAt(i) - '0';
                int y = j < 0 ? 0 : num2.charAt(j) - '0';
                sb.append((x + y + carry) % 10); // 对10取模得到余数
                carry = (x + y + carry) / 10; // 除10得到倍数
            }
            return sb.reverse().toString();
        }
    }
    复制代码

**43. Multiply Strings**

*  题目: 给出两个非负的字符串,求两个字符串相乘的结果
 *  思路: 乘法变加法？ 乘数拆解 num \* 121 = num \* 100 + num \* 20 + num 竖位计算,先将所有的乘法计算的结果保留，然后与之前的结果进行加和,分别保留进位和余位

class Solution {
        public String multiply(String num1, String num2) {
            if (num1.equals("0") || num2.equals("0")) {
                return "0";
            }
            
            int n1 = num1.length();
            int n2 = num2.length();
            int[] res = new int[n1 + n2];
            for (int i = n1 - 1; i >= 0; i--) {
                for (int j = n2 - 1; j >= 0; j--) {
                    // num1[i] * num2[j] 的结果一定是一个两位数，分别对应res中的第i + j 和 第i + j + 1位
                    int mul = (num1.charAt(i) - '0') * (num2.charAt(j) - '0');
                    int sum = mul + res[i + j + 1];
                    // [i + j] 是高位 [i + j + 1]是低位
                    res[i + j] += sum / 10; 
                    res[i + j + 1] = sum % 10;
                }
            }
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < res.length; i++) {
                if (i == 0 && res[i] == 0) {
                    continue;
                }
                sb.append(res[i]);
            }
            
            return sb.toString();
        }
    }
    复制代码

#### Linked List ####

**328. Odd Even Linked List**

*  问题: 将奇偶链表分开 要求O(1)空间复杂度
 *  思路: 快慢指针

复制代码

**奇偶链表排序**

**329. Longest Increasing Path in a Matrix**

class Solution {
        private final int[] dx = {
        1, -1, 0, 0};
        private final int[] dy = {
        0, 0, 1, -1};
        
        public int longestIncreasingPath(int[][] matrix) {
            if (matrix == null || matrix.length == 0) {
                return 0;
            }
            int longest = 0;
            int rows = matrix.length;
            int cols = matrix[0].length;
            int[][] memo = new int[rows][cols];
            for (int i = 0; i < rows; i++) {
                for (int j = 0; j < cols; j++) {
                    int curr = dfs(matrix, i, j, rows, cols, memo);
                    if (curr > longest) {
                        longest = curr;
                    }
                }
            }
            return longest;
        }
        
        public int dfs(int[][] matrix, int x, int y, int rows, int cols, int[][] memo) {
            if (memo[x][y] != 0) {
                return memo[x][y];
            }
            int max = 1;
            for (int i = 0 ; i < 4; i++) {
                int nx = x + dx[i];
                int ny = y + dy[i];
                if (nx < 0 || nx >= rows || ny < 0 || ny >= cols || matrix[nx][ny] <= matrix[x][y]) continue;
                int len = 1 + dfs(matrix, nx, ny, rows, cols, memo);
                max = Math.max(max, len);
            }
            memo[x][y] = max;
            return max;
        }
    }
    复制代码

**Remove Duplicates From Sorted List**

class Solution {
        public ListNode deleteDuplicates(ListNode head) {
            if (head == null) {
                return null;
            }
            ListNode prev = head;
            ListNode curr = head.next;
    
            while (curr != null) {
                if (prev.val == curr.val) {
                    prev.next = curr.next;
                } else {
                    prev = prev.next;
                }
                curr = curr.next;
            }
            
            return head;
        }
    }
    复制代码

**82. Remove Duplicates from Sorted List II**

*  问题: 重复元素不保留,直接全部删除
 *  思路: 需要设定一个dummy指针作为上一个元素的起点,去比较下一个指针和下下个指针的值是否相等,如果不相等,直接前进,如果相等,前进下下个,直到不相等的时候直接跳过

#### Array ####

**295. Find Median from Data Stream**

*  问题: 找到一个数据流中的中位数
 *  思路1: Brute Force维持一个sorted array， 每次将新值插入到特定的顺序 O(n^2)时间复杂度
 *  思路2: 直接
 *

class MedianFinder {
        private PriorityQueue<Integer> lowers;
        PriorityQueue<Integer> highers;
        private boolean even;
        /** initialize your data structure here. */
        public MedianFinder() {
            lowers = new PriorityQueue<>(new Comparator<Integer> () {
                public int compare(Integer a, Integer b) {
                    return -1 * a.compareTo(b);
                }
            });
            highers = new PriorityQueue<Integer>();
            even = true;
        }
        
        public void addNum(int num) {
            if (even) {
                highers.offer(num);
                lowers.offer(highers.poll());
            } else {
                lowers.offer(num);
                highers.offer(lowers.poll());
            }
            even = !even;
        }
        
        public double findMedian() {
            if (even) {
                return (lowers.peek() + highers.peek()) / 2.0;
            } else {
                return lowers.peek();
            }
        }
    }
    复制代码

//02.24 九章参考解法
    class MedianFinder {
        public PriorityQueue<Integer> minheap, maxheap;
        public MedianFinder() {
            maxheap = new PriorityQueue<Integer>(Collections.reverseOrder());
            minheap = new PriorityQueue<Integer>();
        }
        
        // Adds a number into the data structure.
        public void addNum(int num) {
            maxheap.add(num);
            minheap.add(maxheap.poll());
            if (maxheap.size() < minheap.size()) {
                maxheap.add(minheap.poll());
            }
        }
    
        // Returns the median of current data stream
        public double findMedian() {
            if (maxheap.size() == minheap.size()) {
                return (maxheap.peek() + minheap.peek()) * 0.5;
            } else {
                return maxheap.peek();
            }
        }
    };
    复制代码

[en.wikipedia.org/wiki/Median…][en.wikipedia.org_wiki_Median] [cs.stackexchange.com/questions/1…][cs.stackexchange.com_questions_1] [www.cnblogs.com/shizhh/p/57…][www.cnblogs.com_shizhh_p_57]

**Design HashMap**

class MyHashMap {
        class ListNode {
            int key, val;
            ListNode next;
            
            ListNode(int key, int val) {
                this.key = key;
                this.val = val;
            }
        }
        final ListNode[] nodes = new ListNode[1000];
    
        /** Initialize your data structure here. */
        public MyHashMap() {
            
        }
        
        /** value will always be non-negative. */
        public void put(int key, int value) {
            int i = idx(key);
            if (nodes[i] == null) {
                nodes[i] = new ListNode(-1, -1);
            }
            ListNode prev = find(nodes[i], key);
            if (prev.next == null) {
                prev.next = new ListNode(key, value);
            } else {
                prev.next.val = value;
            }
        }
        
        /** Returns the value to which the specified key is mapped, or -1 if this map contains no mapping for the key */
        public int get(int key) {
            int i = idx(key);
            if (nodes[i] == null) {
                return -1;
            }
            ListNode node = find(nodes[i], key);
            return node.next == null ? -1 : node.next.val;
        }
        
        /** Removes the mapping of the specified value key if this map contains a mapping for the key */
        public void remove(int key) {
            int i = idx(key);
            if (nodes[i] == null) return;
            ListNode prev = find(nodes[i], key);
            if (prev.next == null) return;
            prev.next = prev.next.next;
        }
        
        int idx(int key) {
            return Integer.hashCode(key) % nodes.length;
        }
        
        // find the value map to the key
        ListNode find(ListNode bucket, int key) {
            ListNode node = bucket;
            ListNode prev = null;
            while (node != null && node.key != key) {
                prev = node;
                node = node.next;
            }
            return prev;
        }
    }
    
    复制代码

转载于:https://juejin.im/post/5c70ad4b518825626911938c

[www.cnblogs.com_miloyip_arc]: https://link.juejin.im?target=http%3A%2F%2Fwww.cnblogs.com%2Fmiloyip%2Farchive%2F2010%2F02%2F25%2F1673114.html
[en.wikipedia.org_wiki_Median]: https://link.juejin.im?target=https%3A%2F%2Fen.wikipedia.org%2Fwiki%2FMedian_of_medians
[cs.stackexchange.com_questions_1]: https://link.juejin.im?target=https%3A%2F%2Fcs.stackexchange.com%2Fquestions%2F1914%2Ffind-median-of-unsorted-array-in-on-time
[www.cnblogs.com_shizhh_p_57]: https://link.juejin.im?target=https%3A%2F%2Fwww.cnblogs.com%2Fshizhh%2Fp%2F5746151.html