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 {
// 思路1:优先考虑饼干,小饼干先喂饱小胃口(遍历饼干)
public int findContentChildren(int[] g, int[] s) {
// 先将饼干和胃口排序(从小到大)
Arrays.sort(g);
Arrays.sort(s);
int n = g.length; // 孩子的数量
int m = s.length; // 饼干的数量
int res = 0; // 存放结果
// 遍历饼干
for (int i = 0; i < m; i ++) {
// 从胃口小的开始喂
if (res < n && g[res] <= s[i]) {
res ++;
}
}
return res;
}
}
class Solution {
// 思路2:优先考虑胃口,先喂饱大胃口(遍历孩子)
public int findContentChildren(int[] g, int[] s) {
// 先将饼干和胃口排序(从小到大)
Arrays.sort(g);
Arrays.sort(s);
int n = g.length - 1; // 孩子的数量
int m = s.length - 1; // 饼干的数量
int res = 0; // 存放结果
// 遍历孩子
for (int i = n; i >= 0; i --) {
// 从胃口大的开始喂
if (m >= 0 && s[m] >= g[i]) {
res ++;
m --;
}
}
return res;
}
}
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 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 {
ArrayList val = new ArrayList();
public Solution(ListNode head) {
ListNode cnt = head;
int i = 0;
while(cnt != null) {
val.add(i, cnt.val);
i++;
cnt = cnt.next;
}
}
public int getRandom() {
Random r = new Random();
int m = r.nextInt(val.size());
int ans = Integer.parseInt(String.valueOf(val.get(m)));
return ans;
}
}
/**
* Your Solution object will be instantiated and called as such:
* Solution obj = new Solution(head);
* int param_1 = obj.getRandom();
*/
class Solution {
public List<List<Integer>> decorateRecord(TreeNode root) {
if (root == null) {
return new ArrayList<>();
}
Queue<TreeNode> queue = new LinkedList<>();
List<List<Integer>> res = new LinkedList<>();
int sum = 1;
queue.offer(root);
while (!queue.isEmpty()) {
int size = queue.size();
LinkedList<Integer> level = new LinkedList<>();
for (int i = 0; i < size; i ++) {
TreeNode temp = queue.poll();
// 奇数行从左到右打印
if (sum % 2 == 1) {
level.add(temp.val);
} else {
// 偶数行从右到左打印
level.addFirst(temp.val);
}
if (temp.left != null) {
queue.offer(temp.left);
}
if (temp.right != null) {
queue.offer(temp.right);
}
}
res.add(level);
sum ++;
}
return res;
}
}
class Solution {
//滑动窗口
public int minSubArrayLen(int target, int[] nums) {
if(nums == null || nums.length < 1) {
return 0;
}
int sum = 0;
int l = 0;
int r = 0;
int min = nums.length + 1;
while(r < nums.length) {
sum += nums[r];
while(sum >= target) {
min = Math.min(min, r - l + 1);
sum -= nums[l];
l++;
}
r++;
}
return min == nums.length + 1 ? 0 : min;
}
}
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;
}
}
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);
}
});
/**> res; tmp; > pathTarget(TreeNode root, int target) {
* 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 {
List<List
List
public List<List
res = new ArrayList<>();
tmp = new ArrayList<>();
dfs(root,target);
return res;
}
void dfs(TreeNode root, int target){
if(rootnull){
return;
}
tmp.add(root.val);
target = target-root.val;
if(root.rightnull&&root.leftnull&&target0){
res.add(new ArrayList<>(tmp));
}
dfs(root.left,target);
dfs(root.right,target);
tmp.remove(tmp.size()-1);
}
}
时间复杂度O(n)
空间复杂度O(n)
层序遍历,记录每层最后一个节点
打卡
以下是代码
“`python代码
class Solution:
def fileCombination(self, target: int) -> List[List[int]]:
if target<=0: return -1
“`
打卡
打卡
打卡
打卡
打卡
打卡
//给出四种变形二分查找的模板代码
//有序数组 arr = [1,2,3,3,3,4,5,5,7]
//target = 3
//给出四种变形二分查找的模板代码
//有序数组 arr = [1,2,3,3,3,4,5,5,7]
//target = 3
//寻找第一个大于target 的元素的下标,本案例中 4就是第一个大于target 的元素,下标 = 5
int upper(int[] arr, int target) {
//如果都不存在,则返回-1
if(arr[arr.length-1] <= target) return -1;
}
//如果数组中存在元素等于target,则返回最后一个等于target的元素的下标,
//如果不存在,则返回第一个大于target的元素的下标。本案例中最后一个等于target的下标 = 4
int floor_upper(int[] arr, int target) {
//如果都不存在,则返回-1
if(arr[arr.length-1] < target) return -1;
if(arr[arr.length-1] target) return arr.length-1;
}
//寻找最后一个小于target的元素的下标,本案例中2则是最后一个小于target的,下标1
int lower(int[] arr, int target) {
//如果都不存在,则返回-1
if(arr[0] >= target) return -1;
}
//如果数组中存在元素等于target,则返回第一个等于target的下标,
//如果不存在,则返回最后一个小于target的元素的下标
int floor_lower(int[] arr, int target) {
//如果都不存在,则返回-1
if(arr[0] > target) return -1;
if(arr[0] target) return 0;
}
//简单记录一下寻找
//第一个大于target的元素的下标为什么向下取整(除法默认的)
//最后一个小于target的元素的下标为什么向上取整?mid = (l + r + 1) / 2;
第一个大于target的元素,第一次使用二分查找时,如果Mid对应的元素正好是最后一个等于target的元素,那么下一个寻找区间是[Mid+1, right]。区间里都是大于target的元素
即mid+1就是第一个大于target的元素。mid = (l + r) / 2可以取到左边界。
第一个大于target的元素 这个要求就是 左边界的值
最后一个小于target的元素的下标,第一次使用二分查找时,如果Mid对应的元素正好是第一个等于target的元素, 那么下一个寻找区间是[left, mid-1],区间里都是小于target的元素
即mid-1就是第一个大于target的元素。mid = (l + r) / 2永远只能取到左边界的值, 而mid = (l + r + 1) / 2才可以取到右边界。
最后一个小于target的元素 这个要求就是 右边界的值,所以需要向上取整
打卡
打卡!
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)。
class Solution {
public:
TreeNode* mirrorTree(TreeNode* root) {
if(root NULL)
{
return NULL;
}
TreeNode* left = mirrorTree(root->left);
TreeNode* right = mirrorTree(root->right);
root->right = left;
root->left = right;
return root;
}
};
时间复杂度:O(n),空间复杂度:O(n)
为什么二者调换顺序就是错误的呢?
先序遍历 + 判断深度 (从顶至底)
后序遍历 + 剪枝 (从底至顶)
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,那么说明使用了索引下推的优化
看到题目结果返回的是数组,就想用数组求解,可是时空复杂度均不理想。
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、刚才说到了模糊匹配失效,为什么使用模糊匹配会失效,你能给我解释一下底层原理吗?
思路和视频一样,但是reverseKGroup的递归关系式写地很乱写不出来
双端队列中存下标值,队首的值是目标值
void printBinaryTree(TreeNode* root, int layer) {
if (root nullptr) {
return;
}
if (layer 1) {
cout << root->val << ” “;
} else if (layer % 2 1) {
printBinaryTree(root->right, layer – 1);
cout << root->val << ” “;
} else {
printBinaryTree(root->left, layer – 1);
cout << root->val << ” “;
}
}//时间复杂度是 O(n),空间复杂度是 O(n)
// 后序遍历二叉搜索树
void postorderTraversal(TreeNode* root) {
if (root NULL) {
return;
}
postorderTraversal(root->left);
postorderTraversal(root->right);
printf(“%d “, root->val);
}//时间负载O(n),空间复杂度O(n)
finally后面的语句分几种情况
异常被捕获:finally代码正常执行并且finally后面正常的代码还是可以继续执行
异常未被捕获:finally代码正常执行,并将异常向上一层调用方抛出,但是finally后面正常的代码不再执行
String类为啥要设计成不可变的?补充:在String类中有个成员变量hash表示该串的哈希值,在第一次调用hashCode方法时字符串的哈希值被计算并赋值给hash,之后调用hashCode方法便可以直接取hash字段返回。
优先队列
法二:
定义优先队列的排序规则
/**
* 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;
}
}