【墨鳌】【经典问题】【约瑟夫环~记忆化搜索】

解题思路

  • 经典约瑟夫环 plus 经典记忆化搜索技巧
  • \(f(n,m)=\begin{cases}0 & (n=0)\\ [f(n-1,m)+m]\%n&(n>0)\end{cases}\)

代码

class Solution {
public:
    struct pair_hash {
        inline size_t operator()(const pair<int,int>&p)const{
            return (((unsigned)p.first<<17)+p.second);
        }
    };

    unordered_map<pair<int,int>,int,pair_hash>josephus;
    int lastRemaining(int n, int m) {
        auto state=make_pair(n,m);
        if(josephus[state])return josephus[state];
        return josephus[state]=(n?(lastRemaining(n-1,m)+m)%n:1);
    }
};

~~Jason_liu O(∩_∩)O

推荐这些文章:

【墨鳌】【LCP 22. 黑白方格画】

组合数学
\(O(N\cdot M)\)
class Solution {
public:
int f[10][10];

int C(int n, int m) {
if (n == m || m == 0) return 1;
return f[n][m] = C(n - 1, m - 1) + C(n - 1, m);
}

int paintingPlan(int n, int k) {
if (k == 0 || k == n * n) return 1;
int ans = 0;
...

【墨鳌】【面试题19. 正则表达式匹配】

class Solution {
public:
bool isMatch(string s, string p) {
int m = s.size();
int n = p.size();

auto matches = [&](int i, int j) {
if (i == 0) {
return false;
}
if (p[j - 1] == '.') {
return true;
...

【墨鳌】【798. 得分最高的最小轮调】

class Solution {
public:
int bestRotation(vector<int>& A) {
int N = A.size();
vector<int> mark(N, 0);
for (int i = 0; i < N; ++i) {
int L = (i + 1) % N; // 得分区间入口
int R = (N + i + 1 - A[i]) % N; // 得分区间出口
mark[L]++;
...

【墨鳌】【卡特兰数】

题目链接
题解链接
解题思路

卡特兰数

代码
// 1 2 5 14 卡特兰数从第二项开始
class Solution {
public:
unordered_map<int,int>C;
int Catalan(int n,int mod){
if(n<=1)return C[n]=1;
if(C[n])return C[n];
int ans=0;
for(int i=1;i<n;i++)
ans=(ans+1LL*Catalan(i,mod)*Catal...

【墨鳌】【简单题~鸡兔同笼】【或者冒泡排序】

题目链接
题解链接
方法一:冒泡排序

思路,略

复杂度

空间复杂度: \(O(1)\)
时间复杂度: \(O(N^2)\)

代码
class Solution {
public:
void sortColors(vector<int>& nums) {
for(auto x=begin(nums);x!=end(nums);x++)
for(auto y=x+1;y!=end(nums);y++)
if(*x>*y)swap(*x,*y);
}
};

方法二:鸡兔同笼
...

【每日一题】【直接循环&二分查找】2022年2月10日-NC32 求平方根

描述实现函数 int sqrt(int x).计算并返回 x 的平方根(向下取整)

 
方法1:直接循环

import java.util.*;

public class Solution {
/**
*
* @param x int整型
* @return int整型
*/
public int sqrt (int x) {
for (int i = 1; i <= x; i++) {
if(i * i == x) {
return i...

字符串双哈希+自定义unordered_map pair<int,int>当key 1923. 最长公共子路径

1 class Solution {
2 public:
3 typedef pair<int,int> pii;
4 const int k1=1331;
5 const int k2=13331;
6 const int mod1=1e9+7;
7 const int mod2=1e9+9;
8 int p1[100005],p2[100005];
9 struct pairhash {
10 size_t operator() (const pair<int, int>...

leetcode357 统计各位数字都不同的数字个数

思路:
排列组合。
实现:

1 class Solution {
2 public:
3 int A(int n,int m){
4 int res=1;
5 for(int i=1;i<=m;i++){
6 res*=n;
7 n--;
8 }
9 return res;
10 }
11 int countNumbersWithUniqueDigits(int n) {
12 int res=1;
13 ...

面试经典题:TOP-K问题(附快排+堆排C++实现)

数组中的第K个最大元素 [TOP-k问题]
// 1、采用快选
class Solution {
public:
int quick_sort(vector<int>& nums,int l,int r,int k){
if(l>=r) return nums[k];
int a = l-1, b = r+1; int x = nums[a+b>>1];
while(a<b){
do a++; while(nums[a] > x);
do ...

leetcode 785 染色法判断二分图

1 class Solution {
2 public:
3 bool isBipartite(vector<vector<int>>& graph) {
4 int n=graph.size();
5 vector<int>G[n],f(n,0);
6 for(int i=0;i<n;i++)
7 for(auto &p:graph[i])G[i].push_back(p);
8 function<int(int,int)...

文章标题:【墨鳌】【经典问题】【约瑟夫环~记忆化搜索】
文章链接:https://www.dianjilingqu.com/51493.html
本文章来源于网络,版权归原作者所有,如果本站文章侵犯了您的权益,请联系我们删除,联系邮箱:saisai#email.cn,感谢支持理解。
THE END
< <上一篇
下一篇>>