LeetCode 1211, 55, 76

本文主要是介绍LeetCode 1211, 55, 76，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

1211. 查询结果的质量和占比

题目链接

1211. 查询结果的质量和占比

表

表Queries的字段为query_name，result，position和rating。

要求

将查询结果的质量 quality 定义为：各查询结果的评分与其位置之间比率的平均值。
将劣质查询百分比 poor_query_percentage 定义为：评分小于 3 的查询结果占全部查询结果的百分比。
编写解决方案，找出每次的 query_name 、 quality 和 poor_query_percentage。
quality 和 poor_query_percentage 都应 四舍五入到小数点后两位 。
以 任意顺序 返回结果表。

知识点

round：四舍五入函数。
avg：统计平均值函数。
sum：求和函数。
count：计数函数。
group by：根据某个字段进行分组。
if：对条件进行判断，如果条件成立，则返回第一个值；否则返回第二个值。例如if(num > 3, 1, 0)表示如果num大于3，就返回1，否则返回0。

思路

先定义一个概念：query_name相同的所有记录统称为一类查询。
要想获取各查询结果的评分与其位置之间比率的平均值，需要对表的query_name进行分组，然后使用avg获取每类查询的平均值。
要想获取评分小于 3 的查询结果占全部查询结果的百分比，分别计算出这类查询的劣质次数和总次数，然后用前者除以后者即可。

代码（有问题）

如果提交这样的代码，那么恭喜你，过不了最后一个样例。

selectquery_name,round(avg(rating / position), 2) quality,round(sum(if(rating < 3, 1, 0)) * 100 / count(*), 2) poor_query_percentage
fromQueries
group byquery_name

代码（修正）

因为最后一个样例的query_name有null的情况，所以应该再添加一个条件query_name is not null。

selectquery_name,round(avg(rating / position), 2) quality,round(sum(if(rating < 3, 1, 0)) * 100 / count(*), 2) poor_query_percentage
fromQueries
wherequery_name is not null
group byquery_name

55. 跳跃游戏

题目链接

55. 跳跃游戏

思路

本题可以使用贪心的思想解决，每步都看一下是否能跳到最后一个下标，如果能，那就返回true，否则就继续，直到遍历整个数组。当然还要满足一个前提——能从前面的下标跳到这个下标，否则从这个下标跳到最后一个下标就是一个无稽之谈。

代码

class Solution {public boolean canJump(int[] nums) {int n = nums.length;int far = 0; // 当前能跳到的最远的下标for (int i = 0; i < n; i++) {if (i > far) { // 如果不能从前面的下标跳到这个下标，就不需要再跳了break;}far = Math.max(far,i+ nums[i]); // 更新能跳到的最远距离if (far >= n - 1) { // 如果能跳到最后一个下标，就返回truereturn true;}}return false; // 遍历整个数组还找不到一个解，返回false}
}

76. 最小覆盖子串

题目链接

76. 最小覆盖子串

思路

这道题看起来没有思路，其实可以这样理解这道题：对于一个子串，只要目标字符的个数足够，就可以将这个子串作为答案，然后通过去除这个子串头部的多余部分，让这个子串达到最短。题目中可能有多个这样的子串，但有一个子串的长度是最短的；如果没有这样的子串，就返回空串。
首先，要统计出目标字符的个数；然后，在数组中使用两个指针i, j来指向子串的头部和尾部，并统计子串中字符的个数；接着，与目标字符的个数进行比较，如果对于每个字符都有 子串中字符的个数 >= 目标字符的个数 ，则使用两个变量left, right记录头部和尾部的指针；之后，通过向后移动子串头部的指针i来去除子串头部的多余部分，每次去除时都更新一下记录头部和尾部的指针left, right，直到这个子串不满足要求。
底下这段有点抽象，不太好描述，可以先看代码，理解代码后就理解这段话的含义了。
对于这样的思路还有一个小优化，就是使用一个变量toPass来统计目标字符的种类（也就是需要通过的条件数），并且使用一个变量passed来统计已经比目标字符个数大的个数（也就是通过条件的个数），然后每当 子串中字符的个数 == 目标字符的个数 （也就是通过了一个条件）时，让passed加1；每当 去除子串头部多余部分并且让一个字符的个数小于目标字符的个数 （也就是没有通过这个条件）时，让passed减1。

代码

class Solution {public String minWindow(String s, String t) {// 1. 准备char数组，因为使用char[]的索引比String的.charAt()方法快char[] target = t.toCharArray();char[] source = s.toCharArray();// 2. 统计目标字符的个数int[] targetCount = new int[128];for (char ch : target) {targetCount[ch]++;}// 3. 统计需要通过的条件总数int toPass = 0; // 需要通过的条件总数for (int count : targetCount) {if (count > 0) {toPass++;}}// 4. 使用两个指针指向子串的头、尾，对每个子串进行判断int passed = 0; // 已通过的条件数int[] subCount = new int[128]; // subCount用来统计某子串的字符出现次数int i = 0, j = 0;int left = -1, right = -1; // 如果left和right最后都是-1，则找不到题目要求对子串while (j < source.length) {char tail = source[j]; // tail是子串的最后一个字符subCount[tail]++;// 通过条件后让计数加一，为了避免重复增加，故只能使用==，而不能使用<=if (subCount[tail] == targetCount[tail]) {passed++;}// 如果已满足所有条件，则去除子串头部的无用字符while (passed == toPass && i <= j) {// 如果区间左右端点未赋值或有更优取值，则更新左右端点if (left == -1 || j - i < right - left) {left = i;right = j;}char head = source[i]; // head是子串的第一个字符subCount[head]--;// 由于去除字符导致一个条件没有通过，让passed减一if (subCount[head] < targetCount[head]) {passed--;}i++;}j++;}// 5. 若left == -1，说明没找到符合的答案，返回空串return left == -1 ? "" : new String(source, left, right - left + 1);}
}