小编Jus*_*son的帖子

鉴于 x 是一个集合，以下代码遍历集合 x 的子集：

int b = 0;
do {
// process subset b
} while (b=(b-x)&x);

我读到了有关位操作及其如何用于表示集合的阅读。

表达式b=(bx)&x是什么意思？它是如何工作的？我熟悉==但不熟悉=在 do while 循环中。这是如何运作的？当 (bx)&x 的值变为零时循环是否终止？

代码的用法如下：

#include <iostream>

using namespace std;

void subsets(int x, int b){
    do{
        cout << b<<"\n";
    }while(b = (b-x)&x);
}

int main()
{
    int x = (1<<1)|(1<<3)|(1<<4)|(1<<8);
    int b = 0;
    subsets(x, b);
    return 0;
}

上面代码给出的输出是：

0
2
8
10
16
18
24
26
256
258
264
266
272 …

问题陈述

阿德里安是一名跑步者，每天早上他都会和朋友一起去跑步。每天早上，他们的教练都会给他们一份从左到右到覆盖的检查站清单。每个检查点都有一个特殊的值。现在，教练有一个规则，即跑步者只会去值严格高于前一个检查点的检查点。此外，所有跑步者都应该严格向右移动。您需要找出覆盖所有检查点所需的最少跑步者人数。

输入采用数组的形式，从左到右表示检查点的值。

样本输入

[12, 15, 18, 17, 20, 25, 27, 19, 20, 21]

样本输出

2

案例说明：

第一名将覆盖 [12, 15, 18, 19, 20, 21]，第二名将覆盖 [17, 25, 27]。

我的代码

我的递归算法给出了正确的输出，但效率不够高。

visited = [0] * len(A)
def ans(A, visited):
    n = len(A)
    if visited.count(0) == 0:
        return 0
    num = 0
    ind = visited.index(0)
    visited[ind] = 1
    min_num = A[ind]
    for i in range(ind, n):
        if A[i] > min_num and visited[i] == 0:
            visited[i] = 1
            min_num = A[i]
    return 1 + …

问题：给定两个字符串数组，对于列表（查询）中的每个字符串，确定它在另一个列表（字典）中有多少个字谜。
它应该返回一个整数数组。
示例：
查询 = ["a", "nark", "bs", "hack", "stair"]
字典 = ['hack', 'a', 'rank', 'khac', 'ackh', 'kran ', 'rankhacker', 'a', 'ab', 'ba', 'stairs', 'rais']
答案是 [2, 2, 0, 3, 1]
因为 query[0] = 'a'字典中有 2 个字谜：'a' 和 'a' 等等......
这是我能想出的最有效的代码：

d = {'a': 2, 'b': 3, 'c': 5, 'd': 7, 'e': 11, 'f': 13, 'g': 17, 'h': 19, 'i': 23, 'j': 29, 'k': 31, 'l': 37, 'm': 41, 'n': 43, 'o': 47, 'p': 53, 'q': 59, 'r': 61, 's': …

我在竞争性程序员手册中找到了一个递归代码来执行相同的操作，但我很难理解其背后的逻辑。
\n它指出：

\n

与子集一样，排列可以使用递归生成。下面的函数搜索遍历集合 {0,1,...,n\xc2\xa11} 的排列。该函数\n构建一个包含该排列的向量排列，并且在不带参数调用该函数时\n开始搜索。\n

\n

void search() {\n    if (permutation.size() == n) {\n        // process permutation\n    } else {\n        for (int i = 0; i < n; i++) {\n            if (chosen[i]) continue;\n            chosen[i] = true;\n            permutation.push_back(i);\n            search();\n            chosen[i] = false;\n            permutation.pop_back();\n        }\n    }\n}\n

\n

每个函数调用都会向排列添加一个新元素。所选数组\表示哪些元素已包含在排列中。如果\n排列的大小等于集合的大小，则已生成排列。\n

\n

我似乎无法理解正确的直觉和所使用的概念。
\n有人可以解释一下这段代码在做什么以及它背后的逻辑是什么吗？