哎，今天参加了次leetcode的周赛。。感觉自己太年轻，一共四道题只做出了两道，有点丧。。。不过还是要安慰安慰自己，非科班而且只刷算法两个月，做出两道不错了~~~但是讲真的，还是丧啊，看完第四题感觉再学两个月也不一定能会，烦死了都。。。算了，换个心情，继续刷简单的题目来找找信心！
比较字符串最小字母出现频次
题目:我们来定义一个函数 f(s)，其中传入参数 s 是一个非空字符串；该函数的功能是统计 s 中（按字典序比较）最小字母的出现频次。例如，若 s = "dcce"，那么 f(s) = 2，因为最小的字母是 "c"，它出现了 2 次。现在，给你两个字符串数组待查表 queries 和词汇表 words，请你返回一个整数数组 answer 作为答案，其中每个 answer[i] 是满足 f(queries[i]) < f(W) 的词的数目，W 是词汇表 words 中的词。
示例 1：
输入：queries = ["cbd"], words = ["zaaaz"]
输出：[1]
解释：查询 f("cbd") = 1，而 f("zaaaz") = 3 所以 f("cbd") < f("zaaaz")。
示例 2：
输入：queries = ["bbb","cc"], words = ["a","aa","aaa","aaaa"]
输出：[1,2]
解释：第一个查询 f("bbb") < f("aaaa")，第二个查询 f("aaa") 和 f("aaaa") 都 > f("cc")。
提示：
1 <= queries.length <= 2000
1 <= words.length <= 2000
1 <= queries[i].length, words[i].length <= 10
queries[i][j], words[i][j] 都是小写英文字母
思路：审了好几遍题总算是看明白了。感觉应该不难，首先最小字母出现次数应该是依次遍历数组代替下表就可以做到。其次就暴力的解法就是双循环暴力解。但是具体怎么做能不能优化我再看看吧，先去写代码了。
改了两遍性能也才超过百分之八十五的人，先贴上代码吧：
class Solution {
public int[] numSmallerByFrequency(String[] queries, String[] words) {
int max = 0;
int[] d = new int[11];
for(String s : words){
d[getN(s)]++;
}
int[] res = new int[queries.length];
int idx = 0;
for(int i = 0;i<queries.length;i++){
int sum = 0;
for(int j = 1;j<11;j++ ){
if(d[j]>0 && getN(queries[i])<j){
sum += d[j];
}
}
res[idx] = sum;
idx++;
}
return res;
}
public int getN(String s){
int[] d = new int[26];
for(char i : s.toCharArray()){
d[i-'a']++;
}
for(int i : d){
if(i>0) return i;
}
return -1;
}
}
其实还有一个直接存储结果的想法，就是下标0存的是大于1的所有数，下标1 存的是大于2的所有数。。依次类推。但是我是真的懒得写了，心烦意乱的。直接看性能排行第一的代码吧。
没啥说的，思路是对的，直接贴代码：
class Solution {
public int[] numSmallerByFrequency(String[] queries, String[] words) {
// 统计
int [] counter = new int[12];
for (int i = 0; i < words.length; i++)
counter[getN(words[i])]++;
// 累和
for (int i = 9; i >= 0; i--)
counter[i] += counter[i + 1];
// 拿值
int[] ret = new int[queries.length];
for (int i = 0; i < queries.length; i++)
ret[i] = counter[getN(queries[i]) + 1];
return ret;
}
public int getN(String s){
int[] d = new int[26];
for(char i : s.toCharArray()){
d[i-'a']++;
}
for(int i : d){
if(i>0) return i;
}
return -1;
}
}
公交站间的距离
题目：环形公交路线上有 n 个站，按次序从 0 到 n - 1 进行编号。我们已知每一对相邻公交站之间的距离，distance[i] 表示编号为 i 的车站和编号为 (i + 1) % n 的车站之间的距离。环线上的公交车都可以按顺时针和逆时针的方向行驶。返回乘客从出发点 start 到目的地 destination 之间的最短距离。
示例 1：
输入：distance = [1,2,3,4], start = 0, destination = 1
输出：1
解释：公交站 0 和 1 之间的距离是 1 或 9，最小值是 1。
示例 2：
输入：distance = [1,2,3,4], start = 0, destination = 2
输出：3
解释：公交站 0 和 2 之间的距离是 3 或 7，最小值是 3。
示例 3：
输入：distance = [1,2,3,4], start = 0, destination = 3
输出：4
解释：公交站 0 和 3 之间的距离是 6 或 4，最小值是 4。
提示：
1 <= n <= 10^4
distance.length == n
0 <= start, destination < n
0 <= distance[i] <= 10^4
题目截图
题目截图
题目截图
思路：这个题反正乍一看是送分题，具体怎么样我先去做了，指不定是又审题不清呢。
class Solution {
public int distanceBetweenBusStops(int[] distance, int start, int destination) {
int s = 0;
int n = 0;
for(int i = 0; i<distance.length;i++){
s += distance[i];
if((start<=i && destination>i) || (start>i && destination<=i)){
n += distance[i];
}
}
return s-n>n?n:s-n;
}
}
百分百性能，这个题简直简单的无脑了，直接下一题吧。
一周中的第几天
题目：给你一个日期，请你设计一个算法来判断它是对应一周中的哪一天。输入为三个整数：day、month 和 year，分别表示日、月、年。您返回的结果必须是这几个值中的一个 {"Sunday", "Monday", "Tuesday", "Wednesday", "Thursday", "Friday", "Saturday"}。
示例 1：
输入：day = 31, month = 8, year = 2019
输出："Saturday"
示例 2：
输入：day = 18, month = 7, year = 1999
输出："Sunday"
示例 3：
输入：day = 15, month = 8, year = 1993
输出："Sunday"
提示：
给出的日期一定是在 1971 到 2100 年之间的有效日期。
思路：这个题怎么说呢，昨天还是前天做过一个类似的，判断年中某天，这道题可以借用一下。直接判断除1971年1月1日是哪天就行了。因为1月1日是周五，所以从周五开始算就行了，另外判断当前日期到1971.1.1除7余了几天就行，反正自己看代码吧
class Solution {
public String dayOfTheWeek(int day, int month, int year) {
int y=1971,d=0,m=0,res=0;
int[] monday ={31,28,31,30,31,30,31,31,30,31,30,31};
for(;y<year;y++){
if((y%4==0&&y%100!=0)||y%400==0) res +=366;
else res +=365;
}
if((y%4==0&&y%100!=0)||y%400==0) monday[1] =29;
for(;d<month-1;d++){
res += monday[d];
}
res +=day;
res = (res-1)%7;
switch(res){
case 0:
return "Friday";
case 1:
return "Saturday";
case 2:
return "Sunday";
case 3:
return "Monday";
case 4:
return "Tuesday";
case 5:
return "Wednesday";
case 6:
return "Thursday";
default: break;
}
return "";
}
}
这道题其实我觉得是麻烦有余技巧不足，反正我不是很喜欢这种。完全不知道考点是什么。
今天的笔记就到这里了，三道题拿低保~~然后今天比较丧，希望明天能调整好。也祝大家工作顺顺利利！
网友评论