头像

jasonlin


访客:17427

离线:4天前


活动打卡代码 LeetCode 50. Pow(x, n)

jasonlin
17天前

快速幂

n可能很大, 直接一个一个乘,可能会超时

class Solution {
public:
    double myPow(double x, int n) {
        typedef long long LL;
        bool is_minus = n < 0;
        double res = 1;
        for (LL k = abs(LL(n)); k; k >>= 1) {
            if (k & 1) res *= x;
            x *= x;
        }
        if (is_minus) res = 1 / res;
        return res;
    }
};

注意 :n为INT_MIN可能会溢出,所以这里都把n转换到负数域进行计算了,偷懒的话直接开个long long变量就行。



活动打卡代码 LeetCode 44. 通配符匹配

jasonlin
17天前

注意和正则表达式的区别

  • 匹配任意

class Solution {
public:
    bool isMatch(string s, string p) {
        int n = s.size(), m = p.size();
        s = ' ' + s, p = ' ' + p;
        vector<vector<bool>> f(n + 1, vector<bool>(m + 1)); // s的前i个 能否和 p的前j分匹配
        f[0][0] = true;

//星号,它可以匹配任一字符,所以
//f[i][j]=f[i][j−1]||f[i−1][j−1]||f[i−2][j−1]||…||f[0][j−1]f[i][j]=f[i][j−1]||f[i−1][j−1]||f[i−2][j−1]||…||f[0][j−1],
//=> f[i−1][j]=f[i−1][j−1]||f[i−2][j−1]||f[i−3][j−1]||…||f[0][j−1]f[i−1][j]=f[i−1][j−1]||f[i−2][j−1]||f[i−3][j−1]||…||f[0][j−1],
//那递推式就是f[i][j]=f[i−1][j]||f[i][j−1]

        for (int i = 0; i <= n; i ++ )
            for (int j = 1; j <= m; j ++ ) 
                if (p[j] == '*') f[i][j] = f[i][j - 1] || i && f[i - 1][j];
                else  f[i][j] = (s[i] == p[j] || p[j] == '?') && i && f[i - 1][j - 1]; // 末尾匹配看前面

        return f[n][m];
    }
};





jasonlin
17天前

题目描述

给定一个非空字符串,将其编码为具有最短长度的字符串。
编码规则是:k[encoded_string],其中在方括号encoded_string 中的内容重复 k 次。
注:
k为正整数且编码后的字符串不能为空或有额外的空格。
你可以假定输入的字符串只包含小写的英文字母。字符串长度不超过 160。
如果编码的过程不能使字符串缩短,则不要对其进行编码。如果有多种编码方式,返回任意一种即可。

样例

示例 1:
输入: "aaa"
输出: "aaa"
解释: 无法将其编码为更短的字符串,因此不进行编码。

示例 2:
输入: "aaaaa"
输出: "5[a]"
解释: "5[a]" 比 "aaaaa" 短 1 个字符。

示例 3:
输入: "aaaaaaaaaa"
输出: "10[a]"
解释: "a9[a]" 或 "9[a]a" 都是合法的编码,和 "10[a]" 一样长度都为 5。


示例 4:
输入: "aabcaabcd"
输出: "2[aabc]d"
解释: "aabc" 出现两次,因此一种答案可以是 "2[aabc]d"。

示例 5:
输入: "abbbabbbcabbbabbbc"
输出: "2[2[abbb]c]"
解释: "abbbabbbc" 出现两次,但是 "abbbabbbc" 可以编码为 "2[abbb]c",因此一种答案可以是 "2[2[abbb]c]"。


算法1

(区间动态规划) $O(n^3)$

首先得解决这么一个问题 :

给定一个非空的字符串,判断它是否可以由它的一个子串重复多次构成

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        return (s + s).find(s, 1) != s.size();
    }
};

进一步,假如它可以由它的一个子串重复多次构成,那么这个子串是什么,重复了多少次, 返回重复的次数

class Solution {
public:
     int repeatedSubstringPattern(string s) {
        int p = (s + s).find(s, 1);  
        if (p != s.size()) 
            return s.size() / p;
        else 
            return 0;
    }
};

其中p的含义为:

  • s + s下标1开始匹配s,第一次匹配的下标,
  • p != s.szie(), 则s[0, p -1] 为重复子串,长度为p, 重复次数为 s.size() / p

不妨验证一下


#include <iostream>
#include <string>

using namespace std;

int main()
{
    string s1 = "abab";
    string s2 = "aba";
    int p =  (s1 + s1).find(s1, 1);
    printf("%s中%s出现的下标索引为%d\n其中子串为: %s, 重复次数为 : %d\n", 
    (s1 + s1).c_str(), s1.c_str(), p, s1.substr(0, p).c_str(), s1.size() / p);
    cout << endl; 
    printf("%s中%s出现的下标索引为%d \n", (s2 + s2).c_str(), s2.c_str(), (s2 + s2).find(s2, 1));

    return 0;
}

输出

abababab中abab出现的下标索引为2
其中子串为: ab, 重复次数为 : 2

abaaba中aba出现的下标索引为3 

f(i, j) 表示: 字符串从索引i到j处的子串的 最短长度的字符串编码

假如字符串为s, 字符串从索引i到j处的子串为 string t = s.substr(i, j - i + 1)

接下来判断t,能否由它的一个子串重复多次构成,如果可以,则返回”次数 + [子串]“的形式 ,如 4[ab]

其中子串的编码形式为 : f(i, i + p - 1)

枚举区间

  • 枚举长度
    • 枚举区间起点
      • 得到区间[i,j]
        • [i,j]区间自成一派, 由它的一个子串重复多次构成 f(i,j) = cnt + "[" + f(i, i + p -1) + "]"
        • 若[i,j] 可以短的的区间编码连接而成,枚举分割点k得到 [i, k][k + 1, j]
          • f(i, j) = f(i, j).size() > f(i,k) + f(k + 1,j).size() : f(i,k) + f(k + 1,j).size() ? f(i, j)

时间复杂度

  • 时间复杂度 : $0(n^3)$
  • 空间复杂度 : $0(n^2)$

C++ 代码

class Solution {
public:
    vector<vector<string>> f;
    string encode(string s) {
        int n = s.size();
        f = vector<vector<string>> (n, vector<string>(n));

        // 区间dp 枚举长度 枚举起点
        // f(i,j)  字符串子串从索引i到 j处的最短长度的字符串编码
        for(int len = 1; len <= n; len ++)
            for(int i = 0;  i + len - 1 < n; i ++){
                int j = i + len - 1;
                f[i][j] = sub_str(s, i, j); // 要么是子串重复 要么是短子串的连接
                if(len > 4){
                    for(int k = i; k < j; k ++){ // 枚举分割点[i, j] -> [i, k] [k + 1, j]
                        string tmp = f[i][k] + f[k + 1][j];
                        if(f[i][j].size() > tmp.size()) f[i][j] = tmp;
                    }
                }
            }

        return f[0][n - 1];  

    }

    string sub_str(string s, int i, int j){
        s = s.substr(i, j - i + 1);
        if(s.size() < 5) return s ;//  如果编码的过程不能使字符串缩短,则不要对其进行编码。 AAAA -> 4[A] 没有缩短
        int p = (s + s).find(s, 1); // 返回的是下标 前面有p个数 [0, p - 1]为重复字串 重复次数为字符串长度/ p
        if(p != s.size())      
            return to_string(s.size() / p) + "[" + f[i][i + p - 1] + "]";
        else
            return s;
    }
};

其他

另外一种找重复子串的朴素做法 $o(n^2)$

class Solution {
public:
    bool repeatedSubstringPattern(string s) {
        int n = s.size();
        // 枚举子串的长度  且该子串一定是其前缀
        for(int i = 1; i * 2 <=  n ; i ++){
            // 首先长度满足要求
            if(n % i == 0){
                // 再看字符是否相同 [0, i-1] [i, 2*i - 1]
                bool flag = true;
                for(int j = i; j < n; j ++){
                    if(s[j] != s[j - i]){
                        flag = false;
                        break;
                    }
                }

                if(flag) return true;
            }

        }

       return false;

    }
};




jasonlin
18天前

利用之前的做法,把所有数异或,左后的结果是a^b,因为两个数不相同,结果肯定不是0,其二进制表示某一位一定是1,不妨假设为第k位;

以第K位分组,分别求异或

class Solution {
public:
    vector<int> singleNumber(vector<int>& nums) {
        int s = 0;
        for(auto x : nums) s ^= x;
        // 找某一位为1
        int k = 0;
        while((s >> k & 1) == 0) k ++;
        // 根据二进制表示的第k位置是否为1来分组求
        int a = 0, b = 0;
        for(auto x :nums)
            if((x >> k & 1) == 0)  a ^= x;
            else   b ^= x;

        return {a, b};
    }
};



活动打卡代码 LeetCode 268. 缺失数字

jasonlin
18天前

等差数列求和

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        long long sum = 0 ;
        long long  expect_sum = 0;

        int n = nums.size();
        expect_sum = n*(n+1) >> 1;

        for (int x : nums)
            sum += x;
        return (int)(expect_sum - sum); 
    }
};
class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        int res = n * (n + 1) / 2;
        for (auto x: nums) res -= x;
        return res;
    }
};



jasonlin
18天前
class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int a = 0, b = 0;
        for (auto x : nums) {
            b = (b ^ x) & ~a;
            a = (a ^ x) & ~b;
    }
    return b;
    }
};

背过




jasonlin
18天前

哈希表

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        map<int, int> hash;
        for(auto n : nums)  hash[n] ++;

        int res ;
        for(auto &h :hash)
            if(h.second == 1){
                res = h.first;
                break;
            }

        return res;
    }
};

位运算

class Solution {
public:
    int singleNumber(vector<int>& nums) {
        int res = 0;
        for(auto c :nums) res ^= c;
        return res;
    }
};



jasonlin
19天前

yxc老师的解法 上增加了图解,便于理解。

lc_04.png

题目描述

给定两个有序数组 nums1 和 nums2,长度分别为 n,m.请找出它们的中位数,要求时间复杂度在 $O(log(n+m))$

样例

nums1 = [1, 3]
nums2 = [2]

中位数是 2.0
nums1 = [1, 2]
nums2 = [3, 4]

中位数是 (2 + 3) / 2 = 2.5

算法1

(递归) $O(log(n+m))$

首先考虑下如何在两个有序数组,从小到大排序, 第k个数是多少
加入两个数组的长度分别为n, m,那么k = ( m+n) /2 即为所求

  • A[k/2] < B[k/2]
    图片1.png

  • A[k/2] > B[k/2]
    图片2.png

时间复杂度

k=(m+n)/2,且每次递归 k的规模都减少一半,
因此时间复杂度是 $O(log(m+n))$.

参考文献

https://www.acwing.com/solution/content/50/

C++ 代码

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int tot = nums1.size() + nums2.size();
        // 偶数的话就是 2个平均数
        if (tot % 2 == 0){
            int left = findKthNumber(nums1, 0, nums2, 0, tot / 2);
            int right = findKthNumber(nums1, 0, nums2, 0, tot / 2 + 1);
            return (left + right) / 2.0;   // 记得 2.0
        }
        // 奇数的话返回 中间的数
        else
            return findKthNumber(nums1, 0, nums2, 0, tot / 2 + 1);

    }

    // i,j表示寻找的区间的起点下标
    // i 表示第一个数组从第i个数到最后,j表示第二个数组从 j 到最后。
    int findKthNumber(vector<int> &nums1, int i, vector<int> &nums2, int j, int k)
    {  
        // 方便处理 假定第一个数组比较短 个数少   但是也要注意其为空 越界的情况
        if (nums1.size() - i > nums2.size() - j)
            return findKthNumber(nums2, j, nums1, i, k);
        // 边界处理
        if (nums1.size() == i)  // 第一个数组为空
            return nums2[j + k - 1];  // k从1开始的 
        // 边界处理    
        if (k == 1) 
            return min(nums1[i], nums2[j]);

        int si = min(i + k / 2, int(nums1.size()));   // 坐标  第k/2和元素的下一个  所以下面要减1
        int sj = j + k / 2;                           // 坐标
        if (nums1[si - 1] > nums2[sj - 1])  // nums2的前半段没用  
             return findKthNumber(nums1, i, nums2, sj, k - (sj - j)); // 删除的个数 // sj - 1 - j + 1
        else  // // nums1的前半段没用
             return findKthNumber(nums1, si, nums2, j, k - (si - i));

    }
};





jasonlin
19天前

lc_04.png

图片1.png

图片2.png
如何用递归来做

首先来解决一个问题

两个有序数组,从小到大拍, 第k个数是多少
加入两个数组的长度分别为n, m,那么k = ( m+n) /2 即为所求

class Solution {
public:
    double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
        int tot = nums1.size() + nums2.size();
        // 偶数的话就是 2个平均数
        if (tot % 2 == 0){
            int left = findKthNumber(nums1, 0, nums2, 0, tot / 2);
            int right = findKthNumber(nums1, 0, nums2, 0, tot / 2 + 1);
            return (left + right) / 2.0;   // 记得 2.0
        }
        // 奇数的话返回 中间的数
        else
            return findKthNumber(nums1, 0, nums2, 0, tot / 2 + 1);

    }

    // i  表示第一个数组从第i个数到最后,j表示第二个数组从 j 到最后。
    int findKthNumber(vector<int> &nums1, int i, vector<int> &nums2, int j, int k)
    {  
        // 方便处理 假定第一个数组比较短 个数少   但是也要注意其为空 越界的情况
        if (nums1.size() - i > nums2.size() - j)
            return findKthNumber(nums2, j, nums1, i, k);
        // 边界处理
        if (nums1.size() == i)  // 第一个数组为空
            return nums2[j + k - 1];  // k从1开始的 
        // 边界处理    
        if (k == 1) 
            return min(nums1[i], nums2[j]);

        int si = min(i + k / 2, int(nums1.size()));   // 坐标  第k/2和元素的下一个  所以下面要减1
        int sj = j + k / 2;                           // 坐标
        if (nums1[si - 1] > nums2[sj - 1])  // nums2的前半段没用  
             return findKthNumber(nums1, i, nums2, sj, k - (sj - j)); // 删除的个数 // sj - 1 - j + 1
        else  // // nums1的前半段没用
             return findKthNumber(nums1, si, nums2, j, k - (si - i));

    }
};



jasonlin
20天前
class Solution {
public:
    bool containsPattern(vector<int>& arr, int m, int k) {
        if(arr.size() < m * k) return false;

        string s = "";
        for(auto a : arr)  s += to_string(a);


        for(int i = 0; i < s.size(); i++){
            int cnt = 1;
            int j = i + m ;
            while(j + m - 1 < s.size() && s.substr(i, m) == s.substr(j, m)){
                cnt ++;
                j += m;
            }
            if(cnt == k)  return true;     
        }


        return false;

    }
};

Y总

class Solution {
public:
    bool containsPattern(vector<int>& arr, int m, int k) {
        int n = arr.size();
        for (int i = 0; i + m * k <= n; i ++ ) {
            bool flag = true;
            for (int j = i; j < i + m * k; j ++ )
                if (arr[j] != arr[i + (j - i) % m]) {
                    flag = false;
                    break;
                }
            if (flag) return true;
        }
        return false;
    }
};

作者:yxc
链接:https://www.acwing.com/activity/content/code/content/460057/
来源:AcWing
著作权归作者所有。商业转载请联系作者获得授权,非商业转载请注明出处。