今日题解

推荐社区：万人千题

一周中的第几天

思路：使用基姆拉尔森计算公式
w = (day+2month+3(month+1)/5 + year +year/4 - year/100 + year/400) % 7
把一月和二月看成是上一年的十三月和十四月

class Solution {
public:
    string dayOfTheWeek(int day, int month, int year) {
        string res[] = { "Monday" , "Tuesday" , "Wednesday" , "Thursday" , "Friday" , "Saturday" , "Sunday" } ;
        if ( month == 1 || month == 2 )
        {
            month = month + 12 ;
            year -- ;
        }
        int index = 0 ;
        //基姆拉尔森计算公式
        index = ( day + 2 * month + 3 * ( month + 1 ) / 5 + year + year / 4 - year / 100 + year / 400 ) % 7 ;
        return res[index] ;
    }
};

一年中的第几天

思路：主要是判断是否是闰年这个位置，需要把平常的28天改成29天
因为用的是YYYY-MM-DD 格式，所以，年-月-日 那里的字符串转整型，是需要把 - 给过滤掉的，然后用一个数组来代替一年的12个月的对应天数

class Solution {
public:
    int dayOfYear(string date) {
        int cnt = 0;
        int year = stoi(date.substr(0, 4));
        int month = stoi(date.substr(5, 2));
        int day = stoi(date.substr(8, 2));
        int months[12] = {31, 28, 31, 30, 31, 30, 31, 31, 30, 31, 30, 31};

        //判断是否是闰年
        if((year%400) == 0 || (year%4) == 0 && (year/100) != 0) {
            months[1] = 29;
        }
        for(int i=1; i<month; ++i) {
            cnt += months[i-1];
        }
        cnt += day;

        return cnt;
    }
};

判断子序列

思路：匹配成功则 i 和 j 同时右移，匹配 s 的下一个位置，
匹配失败则 j 右移，i 不变，尝试用 t 的下一个字符匹配 s。

class Solution {
public:
    bool isSubsequence(string s, string t) {
        int i=0, j=0;
        while( i< s.size() && j <t.size()) {
            if(s[i] == t[j]) {
                ++i;
            }
            ++j;
        }
        return i == s.size();
    }
};

差的绝对值为k的数对数目

思路：就暴力解决，两层循环，求绝对值是否等于 k 就好
关键点在于 i 和 j 的边界条件

class Solution {
public:
    int countKDifference(vector<int>& nums, int k) {
        int res = 0;
        for(int i=0; i<nums.size()-1; i++)
        {
            for(int j=i+1; j<nums.size(); j++)
            {
                if(abs(nums[i] -nums[j]) == k) res++;//abs：求绝对值
            }
        }
        return res;
    }
};

找不同

思路：相当于 s 是 t 的子集，这样一说，我想你们已经有了思路

class Solution {
public:
    char findTheDifference(string s, string t) {
        int res = 0;
        for(auto &i : t) {
            res += i;
        }
        for(auto &i : s) {
            res -= i;
        }
        return res;
    }
};

拥有糖果最多的孩子

思路：一层循环就好，这次用到了一个新函数（在注释里）
相应的，也有一个输出集合最小元素的函数 *min_element

class Solution {
public:
    vector<bool> kidsWithCandies(vector<int>& candies, int extraCandies) {

        //  *max_element：输出集合最大元素
        int maxCandies = *max_element(candies.begin(), candies.end());
        vector<bool> res;
        for(int i=0; i<candies.size(); ++i) {
            res.push_back(candies[i] + extraCandies >= maxCandies);
        }
        return res;
    }
};

所有奇数长度子数组的和

思路：简单题，没有显示时间，所以我用的是两层循环
这里的关键在于判断当前数组的长度是否是奇数，如果是奇数，就让结果加上当前奇数数组的和，否则res不变

class Solution {
public:
    int sumOddLengthSubarrays(vector<int>& arr) {
        int res = 0;
        for(int i=0; i<arr.size(); i++)
        {
            int sum = 0, len = 0;
            for(int j=i; j<arr.size(); j++)
            {
                sum += arr[j];
                len++;
                if(len%2 == 1) res += sum;
            }
        }
        return res;
    }
};

统计好三元组

思路：根据题目的描述来敲代码就行，没有什么奇奇怪怪的地方，后面我做了部分优化，只有 abs(arr[i] - arr[j]) > a 的时候才继续

class Solution {
public:
    int countGoodTriplets(vector<int>& arr, int a, int b, int c) {
        const int size = arr.size();
        int res = 0;
        for(int i=0; i<size; ++i) {
            for(int j=i+1; j<size; ++j) {
                for(int k=j+1; k<size; ++k) {
                    if(abs(arr[i] - arr[j]) <= a && abs(arr[j] - arr[k]) <= b && abs(arr[i] - arr[k]) <= c) ++res;
                }
            }
        }
        return res;
    }
};

做了部分剪枝的优化代码

class Solution {
public:
    int countGoodTriplets(vector<int>& arr, int a, int b, int c) {
        const int size = arr.size();
        int res = 0;
        for(int i=0; i<size; ++i) {
            for(int j=i+1; j<size; ++j) {
                if(abs(arr[i] - arr[j]) > a) {
                    continue;
                }
                for(int k=j+1; k<size; ++k) {
                    if(abs(arr[j] - arr[k]) <= b && abs(arr[i] - arr[k]) <= c) ++res;
                }
            }
        }
        return res;
    }
};

按既定顺序创建目标数组

思路：我不讲武德，直接使用库函数，啪的一下就过了（大家不要学我哈）

class Solution {
public:
    vector<int> createTargetArray(vector<int>& nums, vector<int>& index) {
        vector<int> res;
        for(int i=0; i<index.size(); ++i) {
            res.insert(res.begin() + index[i], nums[i]);
        }
        return res;
    }
};

统计平方和三元组的数目

思路：注释里面有大致思路

class Solution {
public:
    int countTriples(int n) {
        int res = 0;
        // 枚举 a 与 b
        for (int a = 1; a <= n; a++){
            for (int b = 1; b <= n; b++){
                // 判断是否符合要求
                int c = int(sqrt(a * a + b * b));
                if (c <= n && c * c == a * a + b * b){
                    res++;
                }
            }
        }
        return res;
    }
};

搜索二维矩阵Ⅱ

思路：行从左到右找，列从下往上找，找到就返回true，否则返回false

class Solution {
public:
    bool searchMatrix(vector<vector<int>>& matrix, int target) {
        if(matrix.size() == 0) return false;
        int i=0;
        int j = matrix[0].size()-1;
        while(i<matrix.size() && j >= 0) {
            if(matrix[i][j] == target) {
                return true;
            }
            if(matrix[i][j] < target) {
                ++i;
            }else --j;
        }
        return false;
    }
};

最长公共前缀在我的万人千题计划-29里面
今天的题解就到此为止了，确实难度要比前两天小，能稍微有点时间去休息一下，大家明天见