刷leetCode算法题+解析（五十一）

哎，今天参加了次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 "";
    }
}

这道题其实我觉得是麻烦有余技巧不足，反正我不是很喜欢这种。完全不知道考点是什么。
今天的笔记就到这里了，三道题拿低保~~然后今天比较丧，希望明天能调整好。也祝大家工作顺顺利利！