层序遍历，记录每层最后一个节点

• Time：O(n)
• Space：O(n)

class Solution {
    public List<Integer> rightSideView(TreeNode root) {
        if (root == null) {
            return new ArrayList<>();
        }
        Queue<TreeNode> queue = new LinkedList<>();
        List<Integer> res = new ArrayList<>();

        queue.add(root);
        while (!queue.isEmpty()) {
            int size = queue.size();
            for (int i = 0; i < size; i ++) {
                TreeNode temp = queue.poll();
                if (temp.left != null) {
                    queue.add(temp.left);
                }
                if (temp.right != null) {
                    queue.add(temp.right);
                }
                if (i == size - 1) { //将当前层的最后一个节点放入结果列表
                    res.add(temp.val);
                }
            }
        }
        return res;
    }
}

以下是代码

public int mySqrt(int x) {
        int l = 0, r = x;
        while (l <= r) {
            int m = l + (r - l) / 2;
            long t = (long) m * m;
            if ((long) m * m == x) {
                return m;
            }
            if (t < x) {
                l = m + 1;
            }
            if (t > x) {
                r = m - 1;
            }
        }
        return l;
    }

打卡

打卡

打卡

打卡

打卡

class Solution {
public:
bool checkSymmetricTree(TreeNode* root) {
if(root NULL || (root->right NULL && root->left NULL))
{
return true;
}
return function(root->right, root->left);
}
bool function(TreeNode* rootright, TreeNode* rootleft)
{
if(rootright NULL && rootleft NULL)
{
return true;
}
if(rootright NULL || rootleft NULL)
{
return false;
}
if(rootright->val != rootleft->val)
{
return false;
}
return (function(rootright->right, rootleft->left) && function(rootright->left, rootleft->right));
}

};
时间复杂度：O(n)，空间复杂度：O(n)。

为什么二者调换顺序就是错误的呢？

if(stack.isEmpty() || s.charAt(i) != stack.pop()) 
if(s.charAt(i) != stack.pop() || stack.isEmpty()) 

class Solution {
    public boolean isValid(String s) {
        if(s.length() % 2 != 0) {
            return false;
        }
        Stack<Character> stack = new Stack();

        for(int i = 0; i < s.length(); i++) {
            if(s.charAt(i) == '[') {
                stack.push(']');
            }
            else if(s.charAt(i) == '{') {
                stack.push('}');
            }
            else if(s.charAt(i) == '(') {
                stack.push(')');
            }
            else {
                if(stack.isEmpty() || s.charAt(i) != stack.pop()) {
                // if(s.charAt(i) != stack.pop() || stack.isEmpty()) {
                    return false;
                }
            }
        }
        return stack.isEmpty();
    }
}

// 【思路】一个队列
// 时间复杂度：除了入栈是O(n)，其余操作是O(1)
// 空间复杂度：O(n)
class MyStack {
    Queue<Integer> queue;

    public MyStack() {
        queue = new LinkedList();
    }

    public void push(int x) {
        queue.offer(x);
        for(int i = 0; i < queue.size() - 1; i++) {
            queue.offer(queue.poll());
        }
    }

    public int pop() {
        return queue.poll();
    }

    public int top() {
        return queue.peek();
    }

    public boolean empty() {
        return queue.isEmpty();
    }
}

// 【思路】两个队列
// 时间复杂度：除了入栈是O(n)，其余操作是O(1)
// 空间复杂度：O(n)
// class MyStack {
//     Queue<Integer> queue1;
//     Queue<Integer> queue2;

//     public MyStack() {
//         queue1 = new LinkedList();
//         queue2 = new LinkedList();
//     }

//     public void push(int x) {
//         //队列1接受新入栈的元素
//         queue1.offer(x);
//         while(!queue2.isEmpty()) {
//             queue1.offer(queue2.poll());
//         }
//         //交换队列，使得队列1始终为空
//         Queue temp = queue1;
//         queue1 = queue2;
//         queue2 = temp;
//     }

//     public int pop() {
//         return queue2.poll();
//     }

//     public int top() {
//         return queue2.peek();
//     }

//     public boolean empty() {
//         return queue2.isEmpty();
//     }
// }

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

class Solution {
    public boolean isSymmetric(TreeNode root) {
        if (root == null || (root.left == null && root.right == null)) {
            return true;
        }
        // 调用递归函数，比较左节点，右节点
        return f(root.left, root.right);
    }

    // 判断 A 和 B 是否互为镜像二叉树
    boolean f(TreeNode A, TreeNode B){
        // 两个节点都为null
        if (A == null && B == null) {
            return true;
        }
        // 一个为 null 一个不为 null
        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);
    }
}

先序遍历 + 判断深度 （从顶至底）

• Time：O(n^2)，最好情况下（为“满二叉树”），每层执行复杂度× 层数复杂度=O(n × logn)。但最坏情况下（退化成链表）,高度为O(n)，时间复杂度为O(n^2)
• Space：最差情况下（当树退化为链表时），递归深度可达到 n

class Solution {
    public boolean isBalanced(TreeNode root) {
        if (root == null) {
            return true;
        }

        // 当前子树、当前子树的左子树、当前子树的右子树 是否是平衡树
        return Math.abs(maxDeaxth(root.left) - maxDeaxth(root.right)) <= 1 && isBalanced(root.left) && isBalanced(root.right);
    }

    int maxDeaxth(TreeNode root) {
        if (root == null) {
            return 0;
        }

        return 1 + Math.max(maxDeaxth(root.left), maxDeaxth(root.right));
    }
}

后序遍历 + 剪枝 （从底至顶）

• Time：O(n)，N 为树的节点数量，计算树的深度需要遍历所有节点
• Space：O(n)，最差情况下（当树退化为链表时），递归深度可达到 n

class Solution {
    public boolean isBalanced(TreeNode root) {
        return maxDeaxth(root) != -1;
    }

    int maxDeaxth(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = maxDeaxth(root.left);
        int right = maxDeaxth(root.right);

        if (left == -1 || right == -1 ||Math.abs(left - right) > 1) {
            return -1;
        }

        return 1 + Math.max(left, right);
    }
}

1、介绍一下索引的分类，以及他们的主要区别是什么？
按数据结构：哈希索引、有序数组、全文索引、B+树索引
按存储特性：聚簇索引（主键索引）、二级索引（辅助索引）
按字段：普通索引、唯一索引、主键索引、前缀索引
按个数：单个索引、联合索引

2、介绍一下什么是复合索引？什么样的情况下我们会使用复合索引？
把多个单个的字段组合起来形成一个索引，(a,b,c)的形式就是联合索引；
联合索引会遵循“最左匹配原则”，
一般需要查询多个列时需要创建联合索引，可以在普通索引的基础上创建联合索引，也就是使用覆盖索引进行优化，可以省去普通索引在查询过程中出现的回表查询插座，

3、唯一索引了解吗？在使用的时候，有什么需要注意的不？
不允许为Null，unique关键字进行修饰，不允许出现重复值，

4、我们有时候会听到索引下推，你知道什么是索引下推吗？那覆盖索引又是什么意思呢？
现在我们知道，对于联合索引（a, b），在执行 select * from table where a > 1 and b = 2 语句的时候，只有 a 字段能用到索引，那在联合索引的 B+Tree 找到第一个满足条件的主键值（ID 为 2）后，还需要判断其他条件是否满足（看 b 是否等于 2），那是在联合索引里判断？还是回主键索引去判断呢？

在 MySQL 5.6 之前，只能从 ID2 （主键值）开始一个个回表，到「主键索引」上找出数据行，再对比 b 字段值。

而 MySQL 5.6 引入的索引下推优化（index condition pushdown)， 可以在联合索引遍历过程中，对联合索引中包含的字段先做判断，直接过滤掉不满足条件的记录，减少回表次数。

当你的查询语句的执行计划里，出现了 Extra 为 Using index condition，那么说明使用了索引下推的优化

/*
// 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;
    }
}
*/

// 浅拷贝只复制指向某个对象的指针，而不复制对象本身，新旧对象还是共享同一块内存。
// 但深拷贝会另外创造一个一模一样的对象，新对象跟原对象不共享内存，修改新对象不会改到原对象。
// 时间复杂度：O(n)
// 空间复杂度：O(n)
class Solution {
    public Node copyRandomList(Node head) {
        if(head == null) return null;
        //复制在同一条链上
        Node headsub = head;
        Node headpre = head;
        while(headsub != null) {
            headsub = headsub.next;
            Node temp = new Node(headpre.val);
            temp.next = headsub;;
            headpre.next = temp;
            headpre = headsub;
        }
        headpre = head;
        while(headpre != null) {
            headsub = headpre.next;
            headsub.random = headpre.random == null ? null :headpre.random.next;
            headpre = headsub.next;
        }
        //拆分
        headpre = head;
        headsub = head.next;

        Node newHead = headsub;
        while(headpre != null) {
            headpre.next = headsub.next;
            headpre = headpre.next;
            headsub.next = headpre == null ? null : headpre.next;
            headsub = headsub.next;
        }
        return newHead;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

// 【思路】二路归并 + 有序列表排序
// 时间复杂度：O(n log n)
// 空间复杂度：O(n)
class Solution {
    public ListNode sortList(ListNode head) {
        //函数目的

        //结束条件
        if(head == null || head.next == null) {
            return head;
        }

        //关系式
        ListNode left = head;
        ListNode temp = findMiddle(head);
        ListNode right = temp.next;
        temp.next = null;

        ListNode lHead = sortList(left);
        ListNode rHead = sortList(right);

        return mergeOrdered(lHead, rHead);

    }

    ListNode findMiddle(ListNode head) { //若是偶数则返回前一个
        if(head == null) return head;
        ListNode slow = head;
        ListNode fast = head.next;
        while(fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }

    ListNode mergeOrdered(ListNode head1, ListNode head2) { //合并两个有序链表
        ListNode ans = new ListNode(-1);
        ListNode temp = ans;

        while(head1 != null && head2 != null) {
            if(head1.val < head2.val) {
                temp.next = head1;
                head1 = head1.next;
            }
            else {
                temp.next = head2;
                head2 = head2.next;
            }
            temp = temp.next;
        }

        temp.next = head1 == null ? head2 : head1;
        return ans.next;
    }
}

// 时间复杂度：O(n^2) > O(n log n)
// 空间复杂度：O(n)
// class Solution {
//     public ListNode sortList(ListNode head) {
//         ListNode newhead = new ListNode(-1);
//         ListNode ans = newhead;

//         while(head.next != null) {
//             ListNode head0 = head;
//             ListNode smaller = head;
//             ListNode pre = head;
//             while(head0.next != null) {
//                 if(smaller.val > head0.next.val) {
//                     smaller = head0.next;
//                     pre = head0;
//                 }
//                 head0 = head0.next;
//             }
//             if(smaller != pre) {
//                 pre.next = smaller.next;
//                 smaller.next = null;
//                 newhead.next = smaller;
//             }
//             else {
//                 head = head.next;
//                 newhead.next = smaller;
//             }
//             newhead = newhead.next;
//         }
//         newhead.next = head;
//         return ans.next;
//      }
// }

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */

// 时间复杂度：O(n)
// 空间复杂度：O(1)
class Solution {
    public ListNode mergeTwoLists(ListNode list1, ListNode list2) {
        ListNode head = new ListNode(-1);
        ListNode ans = head;

        while(list1 != null) {
            if(list2 == null) {
                head.next = list1;
                break;
            }
            head.next = list1.val < list2.val ? list1 : list2;
            if(head.next == list1) {
                list1 = list1.next;
            } else if(head.next == list2) {
                list2 = list2.next;
            }
            head = head.next;
        }
        if(list2 != null) {
            head.next = list2;
        }
        return ans.next;
    }
}

1、字段加索引，你是否在自己的项目中用过呢？你觉得什么样的字段适合加索引？（PS：从索引区分度，查找频率真，增删频繁角度考虑）
账户申请表、改期表、操作表
研发人员开通账号：状态字段，频繁查询需要进行加索引；

索引区分度大

频繁查询
不为null
用于条件查询

曾删该不适合创建索引
联合索引
避免创建冗余索引

2、mysql怎么创建索引？（PS：说实话，有些人踢踢而谈，但是还真的不知道怎么给字段加索引）
create index 索引名 on 表（列名）
create unique index 索引名 on 表(列名)
drop index 索引

3、那你觉得，字段加了索引，查找的时候一定会走索引吗？（PS：可以回答索引失效的几个经典因素）
like ‘%**’
or前后列没有加索引
函数计算
发生隐式转换

4、刚才你的索引失效的例子，都是因为人为没有写好 sql 导致的，那如果排除人为的情况，sql 正确书写，那就一定会走索引吗？（PS：走不走索引，是经过优化器权衡预测的，所以这里需要回答系统是如何预测的）
不一定：
优化器、基数（索引区分度）、采样统计、比较全表扫描、扫喵行数、出现预测错误

5、如果我想要强制走某个索引，能实现吗？可以怎么做？
可以，force index

6、如何一条 sql 执行的很慢，我们可以怎么来排查原因？
偶尔慢：写入内存redolog日志刷盘、等待锁释放
一直慢：没有加索引、索引失效、选错了索引

7、刚才说到了模糊匹配失效，为什么使用模糊匹配会失效，你能给我解释一下底层原理吗？

class Solution {
    // 快慢指针
    public int removeElement(int[] nums, int val) {
        if(nums == null || nums.length < 1) {
            return 0;
        }
        int fast = 0;
        int slow = 0;
        while(fast < nums.length) {
            if(nums[fast] != val) {
               nums[slow++] = nums[fast]; 
            }
            fast++;
        }
        return slow;
    }
}

/**
 * Definition for singly-linked list.
 * class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

 // 【思路】用快慢指针，想到了追及问题，最多快的跑多一圈
 // 时间复杂度：O(2n)->O(n)
 // 空间复杂度：O(1)
public class Solution {
    public boolean hasCycle(ListNode head) {
        if(head == null || head.next == null) {
            return false;
        }
        ListNode slow = head;
        ListNode fast = head;


        while(fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
            if(fast == slow) {
                return true;
            }
        }
        return false;
    }
}

由于队列是单调递减的，所以每次窗口变动时，只需要判断队首的值是否还在窗口中就行了。
队列中存放数组下标的值：因为要判断队首的值是否在窗口范围内，由数组下标取值很方便，而由值取数组下标不是很方便。

双端队列中存下标值，队首的值是目标值

• Time：O(n)，线性遍历占用O(n)，每个元素最多仅入队和出队一次，因此单调队列deque占用O(2n)
• Space：O(k)，双端队列deque最多同时存储k个元素(窗口大小）

class Solution {
    public int[] maxSlidingWindow(int[] nums, int k) {
        // 双端队列：保存当前窗口最大值的数组位置，保证队列中数组位置的数值从大到小排序
        Deque<Integer> deque = new LinkedList<>();
        // 结果列表res的窗口个数(n - k + 1)
        int res[] = new int[nums.length - k + 1];
        int index = 0;

        for (int i = 0; i < nums.length; i ++) {
            // 将deque内所有<=nums[i]的元素删除
            while (!deque.isEmpty() && nums[deque.peekLast()] <= nums[i]) {
                deque.pollLast();
            }

            // 添加当前值对应的数组下标
            deque.add(i);

            // 判断当前队列中队首的值是否有效
            if (i - deque.peek() >= k) {
                deque.poll();
            }
            // 当前窗口长度为k时，保存队列最底部的值（最大值）
            if (i + 1 >= k) {
                res[index++] = nums[deque.peek()];
            }
        }
        return res;
    }
}

// 后序遍历二叉搜索树
void postorderTraversal(TreeNode* root) {
if (root NULL) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
printf(“%d “, root->val);
}//时间负载O（n），空间复杂度O（n）

// 【思路】递归
// 时间复杂度：O(n)
// 空间复杂度：O(n)
class Solution {
    public ListNode reverseList(ListNode head) {
        //函数目的：反转栈

        //结束条件
        if(head == null || head.next == null) {
            return head;
        }
        //关系式
        ListNode newHead = reverseList(head.next);

        // 不能用newHead，因为newHead要作为表头返回！！！
        // newHead.next = head;
        // head.next = null;
        // newHead = head;
        // return newHead; 

        head.next.next = head;
        head.next = null;
        return newHead;
    }
}

优先队列

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 设置一个map集合,key存放数字,value存放出现次数
        Map<Integer, Integer> map = new HashMap<>();
        // 统计出现次数
        for (int num : nums) {
            // get的时候有可能key不存在，赋默认值0
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        // 建立一个小根堆,用来存放key值,堆内元素按照key对应的value值从大到小排序
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            public int compare(Integer a, Integer b) {
                return map.get(a) - map.get(b);
            }
        });

        // 将map中的数字，插入到小根堆中
        for (Integer key : map.keySet()) {
            if (queue.size() < k) {
                queue.offer(key);
            } else if (map.get(key) > map.get(queue.peek())) {
                queue.poll();
                queue.offer(key);
            }
        }

        // 将小根堆中的k个数字放到数组中
        int res[] = new int[k];
        int index = 0;
        while (!queue.isEmpty()) {
            res[index++] = queue.poll();
        }
        return res;
    }
}

法二：

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        // 设置一个map集合,key存放数字,value存放出现次数
        Map<Integer, Integer> map = new HashMap<>();
        // 统计出现次数
        for (int num : nums) {
            // get的时候有可能key不存在，赋默认值0
            map.put(num, map.getOrDefault(num, 0) + 1);
        }

        PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((e1, e2) -> {
            return e2.getValue().compareTo(e1.getValue());
        });

        // PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((e1, e2) -> e2.getValue() - e1.getValue());

        // 将map中的数字，插入到小根堆中
        queue.addAll(map.entrySet());

        // 将小根堆中的k个数字放到数组中
        int res[] = new int[k];
        int index = 0;
        while (index < k && !queue.isEmpty()) {
            res[index++] = queue.poll().getKey();
        }
        return res;
    }
}

定义优先队列的排序规则

// 定义优先队列的排序规则1
PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
    public int compare(Integer a, Integer b) {
        return map.get(a) - map.get(b);
    }
});

// 定义优先队列的排序规则2
PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((e1, e2) -> {
    return e2.getValue().compareTo(e1.getValue());
});

// 定义优先队列的排序规则3
PriorityQueue<Map.Entry<Integer, Integer>> queue = new PriorityQueue<>((e1, e2) -> e2.getValue() - e1.getValue());

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) {
 *         val = x;
 *         next = null;
 *     }
 * }
 */

// 以下两种时空复杂度一样
// 时间复杂度：O(n)
// 空间复杂度：O(1)

// 【思路】消去差值
// public class Solution {
//     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        int lena = 0, lenb = 0;
        ListNode a = headA;
        ListNode b = headB;
        while(a != null) {
            lena++;
            a = a.next;
        }
        while(b != null) {
            lenb++;
            b = b.next;
        }
        int diff = Math.abs(lena - lenb);
        Boolean flag = lena > lenb ? true : false;
        a = headA;
        b = headB;
        while(a != null && b != null) {
            if(flag && diff > 0) {
                a = a.next;
                diff--;
                continue;
            }else if(diff > 0) {
                b = b.next;
                diff--;
                continue;
            }
            if(a == b) {
                return  a;
            }
            else {
                a = a.next;
                b = b.next;
            }
        }
        return null;
    }
}

// 【代码优化】
// public class Solution {
//     public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
//         if(headA == null || headB == null) {
//             return null;
//         }
//         ListNode a = headA, b = headB;
//         while(a != b) {
//             a = a == null ? headB : a.next;
//             b = b == null ? headA : b.next;
//         }
//         return a;
//     }
// }

/**
* Definition for singly-linked list.
* public class ListNode {
* int val;
* ListNode next;
* ListNode() {}
* ListNode(int val) { this.val = val; }
* ListNode(int val, ListNode next) { this.val = val; this.next = next; }
* }
*/

// 【思路】单指针
// class Solution {
// public ListNode removeNthFromEnd(ListNode head, int n) {
// ListNode cnt = head;
// int count = 2;
// if(cnt.next null) return null;
// while(cnt.next.next != null) {
// count++;
// cnt = cnt.next;
// }
// if(n 1) {
// cnt.next = null;
// return head;
// }
// int i = count – n;
// if(i 0) {
// return head = head.next;
// }
// cnt = head;
// while(i > 1) {
// cnt = cnt.next;
// i–;
// }
// cnt.next = cnt.next.next;
// return head;
// }
// }

// 【思路】双指针
class Solution {
public ListNode removeNthFromEnd(ListNode head, int n) {
ListNode pre = head;
ListNode sub = head;
if(sub.next null) return null;
while(sub.next != null) {
sub = sub.next;
n–;
if(n > -1) {
continue;
}
pre = pre.next;
}
if(pre head && n 1) {
return head.next;
}
pre.next = pre.next.next;
return head;
}
}