大雪菜 — LeetCode刷题打卡活动第三期——week2 DFS专题（部分代码）

转自   https://www.bilibili.com/video/av34962180?t=1435&p=2

77，给定两个整数 n 和 k，返回 1 ... n 中所有可能的 k 个数的组合。

vector<vector<int> >ans;
    vector<vector<int>> combine(int n, int k) {
        vector<int>way;
        dfs(way,1,n,k);
        return ans;
    }
    void dfs(vector<int>&way,int start,int n,int k)
    {
        if(k==0)
        {
            ans.push_back(way);
            return;
        }

        for(int i=start;i<=n;i++)
        {
            way.push_back(i);
            dfs(way,i+1,n,k-1);
            way.pop_back();
        }
    }

 一，组合和全排列

1，组合：

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<vector>
using namespace std;
vector<int>way;
int n,m;
void show()
{
    for (int i = 0; i < way.size(); i++)   //遍历
    {
        printf("%d ", way[i]);
    }puts("");
}
void dfs(int s, int k)  // 组合数
{
    if (k == 0)
    {
        show();
        return;
    }
    for (int i = s; i <= n; i++)
    {
        way.push_back(i);
        dfs(i + 1, k - 1);
        way.pop_back();
    }
}
int main(void)
{
    scanf("%d%d", &n,&m);
    dfs(m, n);

    system("pause");
    return 0;
}

这种方式不能用于全排列，因为这里得到的数始终是递增的，所以保证了他是按照字典序出现的，所以它不会出现 3 1 2 这种情况，而全排列会。

2，全排列

#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<stdlib.h>
#include<vector>
using namespace std;
vector<int>way;
int n;
void show()
{
    for (int i = 0; i < way.size(); i++)   //遍历
    {
        printf("%d ", way[i]);
    }puts("");
}
int vis[11];
void DFS(int k)
{
    if (k == 0)
    {
        show();
        return;
    }
    for (int i = 1; i <= n; i++)
    {
        if (vis[i] == 0)
        {
            vis[i] = 1;
            way.push_back(i);
            DFS(k - 1);
            vis[i] = 0;
            way.pop_back();
        }
    }
}
int main(void)
{
    scanf("%d", &n);
    DFS(n);

    system("pause");
    return 0;
}

这个也不能用于组合数，因为他会重复求，如出现 123 132  213 之类的

784，给定一个字符串S，通过将字符串S中的每个字母转变大小写，我们可以获得一个新的字符串。返回所有可能得到的字符串集合。

class Solution {
public:
    vector<string> ans;
    vector<string> letterCasePermutation(string S) {
        dfs(S,0);

        return ans;
    }
    void dfs(string S,int u)
    {
        if(u==S.size())
        {
            ans.push_back(S);
            return;
        }
        dfs(S,u+1);

        if(S[u]>='A')
        {
            S[u] ^=32;
            dfs(S , u + 1);
        }
    }
};

这一题 有一个挺秀的操作， S[u] ^=32    ,实现大小写的互换

这两题我觉得还不错，愿能记住！！！

========== ========== ========= ======= ======== ====== ===== ==== == =

求上进的人，不要总想着靠谁，人都是自私的，自己才是最靠得住的人。