头像

啊要刷够题目




离线:8小时前


最近来访(11)
用户头像
星冈山月
用户头像
ailyanlu
用户头像
Tingting
用户头像
Ouou
用户头像
喵喵喵喵子
用户头像
拾光010
用户头像
老人与海
用户头像
瞳星结
用户头像
诺亚方舟.


数学

class Solution {
public:

    //一般来说就声明为main函数外面的全局函数,在力扣中就声明为static,和对象无关的。
    //sort中的比较函数compare要声明为静态成员函数或全局函数,不能作为普通成员函数
    //非静态成员(non-static)函数是依赖于具体对象的,
    //而std::sort这类函数是全局的,因此无法再sort中调用非静态成员函数。
    //静态成员函数或者全局函数是不依赖于具体对象的, 可以独立访问,无须创建任何对象实例就可以访问。
    static bool cmp(int a, int b)
    {
        string as = to_string(a), bs = to_string(b);
        return as + bs < bs + as;
    }

    string printMinNumber(vector<int>& nums) {
        sort(nums.begin(), nums.end(), cmp);
        string res;
        for(auto x : nums) res += to_string(x);
        return res;
    }
};



哈希

class Solution {
public:
    char firstNotRepeatingChar(string s) {
        unordered_map<char, int> count;
        for(auto x : s) count[x] ++;
        char res = '#';
        for(auto x : s)
        {
            if(count[x] == 1) 
            {
                res = x;
                break;
            }
        }
        return res;
    }
};



两次二分 不同的判断条件 确定左右边界

class Solution {
public:
    int getNumberOfK(vector<int>& nums , int k) {
        if(nums.empty()) return 0;
        int l = 0, r = nums.size() - 1;

        while(l < r)
        {
            int mid = l + r >> 1;
            if(nums[mid] < k) l = mid + 1;
            else r = mid;
        }
        if(nums[l] != k) return 0;
        int left = l;

        l = 0, r = nums.size() - 1;

        while(l < r)
        {
            int mid = l + r + 1 >> 1;
            if(nums[mid] <= k) l = mid;
            else r = mid - 1;
        }
        return r - left + 1;
    }
};



共同走L1 + L2 + c 步

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *findFirstCommonNode(ListNode *headA, ListNode *headB) {
        if(!headA || !headB) return nullptr;
        ListNode* a = headA, *b = headB;
        while(a != b)
        {
            a = a == nullptr ? headB : a -> next;
            b = b == nullptr ? headA : b -> next;
        }
        return a;
    }
};


活动打卡代码 AcWing 25. 剪绳子

1 动态规划

f[i]表示长度为i的绳子剪成m端后长度的最大乘积(m>1)

class Solution {
public:
    int cuttingRope(int n) {
        vector<int> f(n + 1, 0);
        for(int i = 2; i <= n; i ++)
        {
            for(int j = 1; j <= i/2; j ++)
            {
                f[i] = max(f[i], max(j * (i - j), j * f[i - j]));
            }
        }
        return f[n];
    }
};

2 贪心

发现尽可能多出现3

class Solution {
public:
    int cuttingRope(int n) {
        if(n <= 3) return n -1;
        int res = 1;
        if(n % 3 == 1) res = 4, n -= 4;
        else if(n % 3 == 2) res = 2, n -= 2;
        while(n) res *= 3, n -= 3;
        return res;
    }
};



模拟

class Solution {
public:
    int strToInt(string str) {
        long long number = 0;
        int k = 0;
        bool flag = 0;
        while(k < str.size() && str[k] == ' ') k ++;
        if(str[k] == '+') k ++;
        else if(str[k] == '-') flag = -1, k ++;

        while(k < str.size() && str[k] >= '0' && str[k] <= '9')
        {
            number = number * 10 + str[k] - '0';
            if(flag && number * -1 < INT_MIN)
            {
                return INT_MIN;
                break;
            }
            if(!flag && number > INT_MAX)
            {
                return INT_MAX;
                break;
            }
            k ++;
        }
        if(flag) number *= -1;
        return (int)number;
    }
};



动态规划

class Solution {
public:
    int getTranslationCount(string s) {
        int n = s.size();
        vector<int> f(n + 1);
        f[0] = 1;
        for(int i = 1; i <= n; i ++)
        {
            f[i] = f[i - 1];
            if(i >= 2)
            {
                int t = (s[i - 2] - '0') * 10 + (s[i - 1] - '0');
                if(t >= 10 && t <= 25) f[i] += f[i - 2];

            }
        }
        return f[n];
    }
};



双指针

时间复杂度O(n)
空间O(1):字符的 ASCII 码范围为 0 ~ 127 ,哈希表 dic 最多使用 O(128) = O(1) 大小的额外空间。

class Solution {
public:
    int longestSubstringWithoutDuplication(string s) {
        unordered_map<char, int> map;
        int ans = 0;
        for(int i = 0, j = 0; j < s.size(); j ++)
        {
            map[s[j]] ++;
            while(map[s[j]] > 1 && j > i)
            {
                map[s[i]] --;
                i ++;
                if(map[s[j]] == 1) break;
            }
            ans = max(ans, j - i + 1);
        }
        return ans;
    }
};



双指针

时间复杂度O(n)
空间O(1):字符的 ASCII 码范围为 0 ~ 127 ,哈希表 dic 最多使用 O(128) = O(1) 大小的额外空间。

class Solution {
public:
    int longestSubstringWithoutDuplication(string s) {
        unordered_map<char, int> map;
        int ans = 0;
        for(int i = 0, j = 0; j < s.size(); j ++)
        {
            map[s[j]] ++;
            while(map[s[j]] > 1 && j > i)
            {
                map[s[i]] --;
                i ++;
                if(map[s[j]] == 1) break;
            }
            ans = max(ans, j - i + 1);
        }
        return ans;
    }
};



二分
发现nums[i] - i的结果是单调增的
所以可以以 0 来二分

class Solution {
public:
    int getNumberSameAsIndex(vector<int>& nums) {
        int l = 0, r = nums.size() - 1;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(nums[mid] - mid >= 0) r = mid;
            else l = mid + 1;
        }
        if(nums[l] - l == 0) return l;
        else return -1;
    }
};