头像

记着别人的好




离线:8小时前


最近来访(292)
用户头像
wuog
用户头像
呀哈喽
用户头像
Fatin
用户头像
Juicy
用户头像
zhaohongrui
用户头像
xiezere
用户头像
一只特立独行的Cat7
用户头像
violet_garden
用户头像
baijing
用户头像
托马斯成
用户头像
天道酬勤_58
用户头像
xunqian
用户头像
1357649762
用户头像
不一定回来
用户头像
种花家的市长
用户头像
专注等于效率翻倍
用户头像
ROKANARBITER
用户头像
sweet_tea
用户头像
普罗米修斯零号机
用户头像
jahshwhs


思路:数论

图像理解:

120dac15f393013de6ec09524843a57.jpg
4a1fdb817364728cd769b587e115676.jpg

因式分解 5 的个数肯定比 2 的个数少,min(a, b) = b (因为 5 > 2,所以少)

代码实现:

class Solution {
public:
    int trailingZeroes(int n) 
    {
        int ans = 0;
        while(n)
        {
            ans += n / 5;
            n /= 5;
        }

        return ans;
    }
};


活动打卡代码 LeetCode 172. 阶乘后的零

class Solution {
public:
    int trailingZeroes(int n) 
    {
        int ans = 0;
        while(n)
        {
            ans += n / 5;
            n /= 5;
        }

        return ans;
    }
};


活动打卡代码 LeetCode 166. 分数到小数

string get(int x, int y)
{
    typedef long long LL;
    LL a = x, b = y;
    if(a % b == 0) return to_string(a / b);

    string ans;
    if(a < 0 && b > 0 || b < 0 && a > 0) ans += '-';
    a = abs(a);
    b = abs(b);
    ans += to_string(a / b);
    a %= b;
    while(a)
    {
        hash[a] = ans.size();
        a *= 10;
        ans += to_string(a / b);
        a %= b;
        if(hash.count(a) >= 1) 
        {
            ans = ans.substr(0, hash[a]) + "(" + ans.substr(hash[a]) + ")";
            break;
        }
    }

    return ans;
}



思路:模拟高精度除法 + unordered_map[HTML_REMOVED] hash

时间复杂度:O(n == size(y))

x % y 的范围是 0 — y - 1, length = size(y)
  1. 模拟一下除法过程,可以清楚的知道 unordered_map[HTML_REMOVED] hash 是用来求循环节的哦
  2. hash[x] 到 res.end() 就是循环节了

图像理解:

4aa0cac160cffc2fb1ac1b10aaa6dce.jpg
685e81dddd7a87c2fedc1a8aa5f23e7.jpg
bc3164318203aff0027fb22bbe3ac61.jpg

代码实现:

class Solution {
public:
    string fractionToDecimal(int x, int y) 
    {
        typedef long long LL;       // -1     -2147483648 是答案会爆 int
        LL a = x, b = y;
        if(a % b == 0) return to_string(a / b);

        string ans;
        if(a < 0 && b > 0 || b < 0 && a > 0) ans += '-';
        a = abs(a);
        b = abs(b);
        ans += to_string(a / b) + ".";
        a %= b;
        unordered_map<LL, int> hash;  // 根据除法的过程,求循环节用的哦
        while(a)
        {
            hash[a] = ans.size();
            a *= 10;
            ans += to_string(a / b);
            a %= b;
            if(hash.count(a) >= 1)    // 找到循环节了
            {
                ans = ans.substr(0, hash[a]) + "(" + ans.substr(hash[a]) + ")";
                break;
            }
        }

        return ans;
    }
};


活动打卡代码 LeetCode 279. 完全平方数

bool is(int x)
{
    int t = sqrt(x);
    return t * t == x;
}

int get(int n)
{
    if(is(n)) return 1;

    for(int i = 1; i <= n / i; i++)
        if(is(n - i * i)) return 2;

    while(n % 4 == 0) n /= 4;
    if(n % 8 != 7) return 3;

    return 4;
}



class Solution {
public:
    vector<vector<int>> shiftGrid(vector<vector<int>>& nums, int k) 
    {
        int n = nums.size(), m = nums[0].size();
        while(k--)
        {
            vector<int> ans_m_1;
            for(int i = 0; i < n; i++) ans_m_1.push_back(nums[i][m - 1]);

            for(int i = 0; i < n; i++)
            {
                // int a = nums[i][m - 1];
                // for(int j = 0; j + 1 < m; j++) nums[i][j + 1] = nums[i][j];
                for(int j = m - 1; j - 1 >= 0; j--) nums[i][j] = nums[i][j - 1];
                // nums[i][0] = a;
            }
            // for(int i = 0; i < n; i++)
            //     if(i + 1 < n)
            //     {
            //         int temp = nums[i][m - 1];
            //         nums[i][m - 1] = nums[i + 1][0];
            //         nums[i + 1][0] = temp;
            //     }

            for(int i = 0; i + 1 < n; i++)
                nums[i + 1][0] = ans_m_1[i];

            nums[0][0] = ans_m_1[n - 1];
        }

        return nums;
    }
};



/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    unordered_map<int, int> hash;
    vector<int> ans;
    void bfs(TreeNode* root)
    {
        queue<TreeNode*> q;
        q.push(root);
        while(q.empty() == false)
        {
            int n = q.size();
            for(int i = 0; i < n; i++)
            {
                auto t = q.front();
                q.pop();

                ans.push_back(t->val);
                hash[t->val]++;

                if(t->left) q.push(t->left);
                if(t->right) q.push(t->right);
            }
        }
    }

    bool findTarget(TreeNode* root, int k) 
    {
        bfs(root);
        for(auto x: ans)
            if(hash.count(k - x) >= 1 && k - x != x) return true;

        return false;
    }
};


活动打卡代码 LeetCode 867. 转置矩阵

class Solution {
public:
    vector<vector<int>> transpose(vector<vector<int>>& nums) 
    {
        int n = nums.size(), m = nums[0].size();
        int ans[1000][1000];

        for(int i = 0; i < n; i++)
            for(int j = 0; j < m; j++)
                ans[i][j] = nums[i][j];

        vector<vector<int>> res(m, vector<int>(n));
        for(int j = 0; j < m; j++)
        {
            for(int i = 0; i < n; i++) 
                res[j][i] = ans[i][j];
        }
                //nums[i][j] = ans[i][j];   // 这样是不对的哦

        return res;
    }
};


活动打卡代码 LeetCode 866. 回文素数

// // 遍历所有数字,检查是不是回文串。如果是,检查是不是素数,如果当前数字长度为 8,可以跳过检查,因为不存在 8 长度的素数。

// class Solution {
// public:
//     int is(int n)
//     {
//         for(int i = 2; i <= n / i; i++)
//             if(n % i == 0)
//                 return false;
//         return true;
//     }

//     int isis(int x)
//     {
//         // int num = n, sum = 0;
//         // while(n > 0)
//         // {
//         //     int t = n % 10;
//         //     sum = sum * 10 + t;
//         //     n /= 10;
//         // }
//         // if(num == sum) return true;

//         // return false;

//         string a = to_string(x);
//         string b = a;
//         reverse(b.begin(), b.end());
//         return stoi(a + b.substr(1));
//     }

//     int primePalindrome(int n) 
//     {
//         if(n == 1) return 2;
//         if(n == 2 || n == 3 || n == 5 || n == 7) return n;

//         for(int i = n; ; i++)
//         {
//             int x = isis(i);
//             if(x >= n && is(i)) return x;
//         }   

//         return 0;
//     }
// };



class Solution {
public:
    int get(int x) {
        string a = to_string(x);
        string b = a;
        reverse(b.begin(), b.end());
        return stoi(a + b.substr(1));
    }

    int is_prime(int x) {
        if (x < 2) return false;
        for (int i = 2; i * i <= x; i ++ )
            if (x % i == 0)
                return false;
        return true;
    }

    int primePalindrome(int n) {
        if (n > 7 && n <= 11) return 11;
        for (int i = 1; ;i ++ ) {
            int x = get(i);
            if (x >= n && is_prime(x))
                return x;
        }
        return -1;
    }
};


活动打卡代码 LeetCode 49. Group Anagrams

string 映射到 unordered_map<string, vector<string>> hash;