头像

腾杨天下

腾杨集团




离线:6天前


最近来访(363)
用户头像
hiccgoal
用户头像
用户头像
ZZMQ
用户头像
吃相略难看
用户头像
chim
用户头像
无产阶级万岁
用户头像
太阳下山了吗
用户头像
君故
用户头像
shengshu_
用户头像
不要不听话
用户头像
pio
用户头像
hncsxzx
用户头像
不能AK的猫猫虫
用户头像
cony
用户头像
acw_s4n
用户头像
perfectionist
用户头像
小桑要读研
用户头像
我不爱玩游戏
用户头像
2ist
用户头像
我是好人


腾杨天下
10个月前

思路

跟n皇后很相似,都是检验状态是否合法,合法就填进去然后进行下一步的dfs,在n皇后中,我们使用了check()函数,在每下一步棋之前都检查是否下了之后横竖斜对四条线上是否有其他皇后来判断是否合法,我们这一道题也可以用同样的方法,但是在这一道题我们进行进阶,将check()的时间复杂度由O(n)降到O(1),具体来说,原本要检查27个格子,现在只需要3次判断就可以了。这就是————状态压缩。
我们可以用一个数组来记录某行/某列/某块中某个数字是否出现过,这就将复杂度又降低了n倍,由于本题n恒为9,所以就是降低了9倍,具体的,st1[x][i],st2[y][i],st3[x/3][y/3][i]分别表示第x行中、第y列中、xy对应的九宫格中是否出现过数字i。

未优化check()版

class Solution {
public:
    char ans[9][9];
    bool check(vector<vector<char>>& a,int x,int y,int v)
    {
        int mx=x/3*3,my=y/3*3;
        for(int i=0;i<9;i++)
        {
            if(a[i][y]==v+'0')return false;
            if(a[x][i]==v+'0')return false;
            if(a[mx+i/3][my+i%3]==v+'0')return false;
        }
        return 1;
    }
    bool dfs(vector<vector<char>>& a,int x,int y)
    {
        if(y==9)x+=1,y=0;
        if(x==9)return true;
        if(a[x][y]!='.')return dfs(a,x,y+1);
        for(int i=1;i<=9;i++)
        {
            if(check(a,x,y,i))
            {
                a[x][y]=i+'0';
                if(dfs(a,x,y+1))return true;
                a[x][y]='.';
            }
        }
        return false;
    }
    void solveSudoku(vector<vector<char>>& a) {
        dfs(a,0,0);
    }
};

状态压缩版

class Solution {
public:
    char ans[9][9];
    bool st1[15][15],st2[15][15],st3[5][5][15];
    bool dfs(vector<vector<char>>& a,int x,int y)
    {
        if(y==9)x+=1,y=0;
        if(x==9)return true;
        if(a[x][y]!='.')return dfs(a,x,y+1);
        for(int i=1;i<=9;i++)
        {
            if(!st1[x][i]&&!st2[y][i]&&!st3[x/3][y/3][i])
            {
                a[x][y]=i+'0';
                st1[x][i]=true,st2[y][i]=true,st3[x/3][y/3][i]=true;
                if(dfs(a,x,y+1))return true;
                a[x][y]='.';
                st1[x][i]=false,st2[y][i]=false,st3[x/3][y/3][i]=false;
            }
        }
        return false;
    }
    void solveSudoku(vector<vector<char>>& a) {
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                if(a[i][j]!='.')
                {
                    int val=a[i][j]-'0';
                    st1[i][val]=true;
                    st2[j][val]=true;
                    st3[i/3][j/3][val]=true;
                }
            }
        }
        dfs(a,0,0);
    }
};


活动打卡代码 LeetCode 37. 解数独

腾杨天下
10个月前

思路

跟n皇后很相似,都是检验状态是否合法,合法就填进去然后进行下一步的dfs,在n皇后中,我们使用了check()函数,在每下一步棋之前都检查是否下了之后横竖斜对四条线上是否有其他皇后来判断是否合法,我们这一道题也可以用同样的方法,但是在这一道题我们进行进阶,将check()的时间复杂度由O(n)降到O(1),具体来说,原本要检查27个格子,现在只需要3次判断就可以了。这就是————状态压缩。
我们可以用一个数组来记录某行/某列/某块中某个数字是否出现过,这就将复杂度又降低了n倍,由于本题n恒为9,所以就是降低了9倍,具体的,st1[x][i],st2[y][i],st3[x/3][y/3][i]分别表示第x行中、第y列中、xy对应的九宫格中是否出现过数字i。

未优化check()版

class Solution {
public:
    char ans[9][9];
    bool check(vector<vector<char>>& a,int x,int y,int v)
    {
        int mx=x/3*3,my=y/3*3;
        for(int i=0;i<9;i++)
        {
            if(a[i][y]==v+'0')return false;
            if(a[x][i]==v+'0')return false;
            if(a[mx+i/3][my+i%3]==v+'0')return false;
        }
        return 1;
    }
    bool dfs(vector<vector<char>>& a,int x,int y)
    {
        if(y==9)x+=1,y=0;
        if(x==9)return true;
        if(a[x][y]!='.')return dfs(a,x,y+1);
        for(int i=1;i<=9;i++)
        {
            if(check(a,x,y,i))
            {
                a[x][y]=i+'0';
                if(dfs(a,x,y+1))return true;
                a[x][y]='.';
            }
        }
        return false;
    }
    void solveSudoku(vector<vector<char>>& a) {
        dfs(a,0,0);
    }
};

状态压缩版

class Solution {
public:
    char ans[9][9];
    bool st1[15][15],st2[15][15],st3[5][5][15];
    bool dfs(vector<vector<char>>& a,int x,int y)
    {
        if(y==9)x+=1,y=0;
        if(x==9)return true;
        if(a[x][y]!='.')return dfs(a,x,y+1);
        for(int i=1;i<=9;i++)
        {
            if(!st1[x][i]&&!st2[y][i]&&!st3[x/3][y/3][i])
            {
                a[x][y]=i+'0';
                st1[x][i]=true,st2[y][i]=true,st3[x/3][y/3][i]=true;
                if(dfs(a,x,y+1))return true;
                a[x][y]='.';
                st1[x][i]=false,st2[y][i]=false,st3[x/3][y/3][i]=false;
            }
        }
        return false;
    }
    void solveSudoku(vector<vector<char>>& a) {
        for(int i=0;i<9;i++)
        {
            for(int j=0;j<9;j++)
            {
                if(a[i][j]!='.')
                {
                    int val=a[i][j]-'0';
                    st1[i][val]=true;
                    st2[j][val]=true;
                    st3[i/3][j/3][val]=true;
                }
            }
        }
        dfs(a,0,0);
    }
};



腾杨天下
10个月前

思路

太他妈难了我草

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        int n=0;
        for(auto p=head;p;p=p->next)n++;
        auto dummy=new ListNode(-1);
        dummy->next=head;
        for(int i=1;i<n;i*=2)
        {
            auto cur=dummy;
            for(int j=1;j+i<=n;j+=i*2)
            {
                auto p=cur->next,q=p;
                for(int k=0;k<i;k++)q=q->next;
                int x=0,y=0;
                while(x<i&&y<i&&p&&q)
                {
                    if(p->val<=q->val)cur=cur->next=p,p=p->next,x++;
                    else cur=cur->next=q,q=q->next,y++;
                }
                while(x<i&&p)cur=cur->next=p,p=p->next,x++;
                while(y<i&&q)cur=cur->next=q,q=q->next,y++;
                cur->next=q;//将cur->next移向新的j循环开始节点,不然的话cur->next只可能指在p段或q段上,不可能指向q段的下一个节点。
            }
        }
        return dummy->next;
    }
};


活动打卡代码 LeetCode 148. 排序链表

腾杨天下
10个月前

思路

太他妈难了我草

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* sortList(ListNode* head) {
        int n=0;
        for(auto p=head;p;p=p->next)n++;
        auto dummy=new ListNode(-1);
        dummy->next=head;
        for(int i=1;i<n;i*=2)
        {
            auto cur=dummy;
            for(int j=1;j+i<=n;j+=i*2)
            {
                auto p=cur->next,q=p;
                for(int k=0;k<i;k++)q=q->next;
                int x=0,y=0;
                while(x<i&&y<i&&p&&q)
                {
                    if(p->val<=q->val)cur=cur->next=p,p=p->next,x++;
                    else cur=cur->next=q,q=q->next,y++;
                }
                while(x<i&&p)cur=cur->next=p,p=p->next,x++;
                while(y<i&&q)cur=cur->next=q,q=q->next,y++;
                cur->next=q;//将cur->next移向新的j循环开始节点,不然的话cur->next只可能指在p段或q段上,不可能指向q段的下一个节点。
            }
        }
        return dummy->next;
    }
};



腾杨天下
10个月前

思路

首先我们要会写、理解归并排序。归并排序是什么呢?归并排序是先分治再用双指针以比大小的方式从小到大归并左右两段数组为一段排序好的数组的排序算法。
我们这道题就要利用归并排序当中的比大小归并的过程进行逆序对统计,由于分治的作用,在进行归并时,左右两段数组已经被排序过了,它们两者内部已经是从小到大排序,所以左数组种一旦发现第x个数大于右数组中第y个数,那么左数组中下标为[x,mid]的数都大于下标为y的数,也就有mid-x+1个数可以与q[y]组成逆序对,那么我们在进行归并的时候利用这个数据将之统计起来就可以了,代价而已忽略不计。
所以这道题总的时间复杂度就是归并排序的时间复杂度也就是说O(nlogn)。

class Solution {
public:
    int cnt=0;
    void merge_sort(vector<int>& q,int l,int r)
    {
        if(l>=r)return;
        int mid=l+r>>1;
        merge_sort(q,l,mid);
        merge_sort(q,mid+1,r);
        int x=l,y=mid+1,z=0;
        vector<int>temp(r-l+1);
        while(x<=mid&&y<=r)
        {
            if(q[x]<=q[y])temp[z++]=q[x++];
            else
            {
                temp[z++]=q[y++];
                cnt+=mid-x+1;
            }
        }
        while(x<=mid)temp[z++]=q[x++];
        while(y<=r)temp[z++]=q[y++];
        for(int i=0;i<z;i++)q[l+i]=temp[i];
    }
    int reversePairs(vector<int>& nums) {
        merge_sort(nums,0,nums.size()-1);
        return cnt;
    }
};



腾杨天下
10个月前

思路

先算出每种点数有多少种投法。求完了每一个点数之后再除以总点数即可。
f[i][j]表示投完第i个骰子之后点数为j的投法有几种。我们要从f[0][0]算到f[n][6n]。然后需要的点数是f[n][n]~f[n][6n]这5*n种点数。
三重循环计算即可

class Solution {
public:
    double a[15][70];
    vector<double> dicesProbability(int n) {
        vector<double>ans;
        a[0][0]=1;
        for(int i=1;i<=n;i++)
        {
            for(int j=i;j<=i*6;j++)
            {
                for(int k=1;k<=6;k++)
                {
                    if(j-k>=0)a[i][j]+=a[i-1][j-k];
                }
            }
        }
        double cnt=0;
        for(int i=n;i<=6*n;i++)cnt+=a[n][i];
        for(int i=n;i<=6*n;i++)
        {
            a[n][i]/=cnt;
            ans.push_back(a[n][i]);
        }
        return ans;
    }
};



腾杨天下
10个月前

丑数的性质

一个较大的丑数必定是由一个较小的丑数*2/3/5得来的。

思路

我们可以由1这个最初的丑数,*2/3/5得到三个新的丑数,然后再有新的丑数依次*2/3/5得到新的丑数,最后再排序,然后返回当中第n个丑数。这种做法时间复杂度有点高,浪费了一些时间复杂度,它的本质还是打表,而且多了一个nlogn的排序时间,非常的慢。
优化一下,优化掉这个排序的过程,方法就是三指针法,我们直接按照从小到大的顺序求丑数就好了,为此我们需要三个指针,指向a[i]、a[j]、a[k],然后从a[i]2、a[j]3、a[k]*5当中挑出一个最小值,然后判断一下这三个数当中有没有跟这个值相同的,那么把这个指针后移一位,当我们用这种方式从小到大求了n个丑数之后就可以停止了,然后返回第n个丑数。相比于第一种方法,我们这种方法是On的,而且求到第n个丑数就立即停了下来没有多求。当然这种方法也可以直接用来打表的。

class Solution {
public:
    int nthUglyNumber(int n) {
        vector<int>a{1};
        int i=0,j=0,k=0;
        while(a.size()<n)
        {
            int temp=min(a[i]*2,min(a[j]*3,a[k]*5));
            if(a[i]*2==temp)i++;
            if(a[j]*3==temp)j++;
            if(a[k]*5==temp)k++;
            a.push_back(temp);
        }
        return a[n-1];
    }
};



腾杨天下
10个月前

DP状态表示

这道题是一个二维状态表示的DP,用f[i][j]表示s前i个字符p前j个字符可以相匹配。

状态转换方程

  1. p[j+1]=='*'时我们跳过这一次判断,因为*只有和前面一个字符连起来的时候才有意义。
  2. p[j]=='*'
  3. X*表示0个字符,那么f[i][j]由f[i][j-2]转换过来
  4. X*表示1个X字符,那么f[i][j]由i&&f[i-1][j]&&s[i]==p[j-1]转换过来
  5. 不需要考虑X*表示2个及以上X字符的情况,因为如果i+1轮情况当中s字符串需要p[j]发力多给一个X字符的话就会从i&&f[i-1][j]&&s[i]==p[j-1]转换过来的
  6. p[j]!='*'时,f[i][j]由i&&f[i-1][j-1]&&(s[i]==p[j]||p[j]==’.’)转换过来
class Solution {
public:
    bool isMatch(string s, string p) {
        int n=s.size(),m=p.size();
        // vector<vector<bool>> f(n+1,vector<bool>(m+1));
        bool f[n+1][m+1];
        memset(f,0,sizeof(f));
        //如果要用数组则必须使用memset初始化,否则就用vector来自动初始化,要么放在全局开数组
        s=' '+s;
        p=' '+p;
        f[0][0]=true;
        for(int i=0;i<=n;i++)
        {
            for(int j=1;j<=m;j++)
            {
                if(j+1<=m&&p[j+1]=='*')continue;
                if(p[j]=='*')
                {
                    f[i][j]=f[i][j-2]||i&&f[i-1][j]&&(s[i]==p[j-1]||p[j-1]=='.');
                }
                else
                {
                    f[i][j]=i&&f[i-1][j-1]&&(s[i]==p[j]||p[j]=='.');
                }
            }
        }
        return f[n][m];
    }
};



腾杨天下
11个月前

思路

先明确f(n,m)表示n个元素的圆圈中最后剩下的元素所在的索引位置
首先是要能想到递归的做法,f(n-1,m)和f(n,m)之间存在关系。
image.png
我们从f(1,m)可以一路递推到f(n,m),f(2,m)=(f(1,m)+m)%2,这就由最后一轮答案所在位置(0)推导到答案在倒数第二轮中所在位置了,然后依次推导到f(n,m),逆推得到答案。
```
class Solution {
public:
int lastRemaining(int n, int m) {
if(n==1)return 0;
return (lastRemaining(n-1,m)+m)%n;
}
};




腾杨天下
11个月前

思路

首先我们需要的时连续正整数序列,我们可以用一前一后双指针来维护一个区间的加和始终大于等于t,如果等于t且区间长度大于等于2,那么将该区间加入答案数组,否则不管它就行,接着将l指针向前移一位,然后重复上述的维护步骤,最后返回答案数组即可。

class Solution {
public:
    vector<vector<int>> findContinuousSequence(int target) {
        vector<vector<int>>ans;
        int sum=1;
        int l=1,r=1;
        while(r<target)
        {
            while(sum<target)sum+=++r;
            if(sum==target&&r-l+1>=2)
            {
                vector<int> temp;
                for(int i=l;i<=r;i++)temp.push_back(i);
                ans.push_back(temp);
            }
            sum-=l;
            l++;
        }
        return ans;
    }
};