小编Gre*_*lin的帖子

你会如何除以3为数字,没有使用*,/,+,-,%,运营商？

号码可以是签名或未签名.

今天我正在阅读关于纯函数,与它的使用混淆:

如果函数为同一组输入返回相同的值集并且没有任何可观察的副作用,则称该函数是纯的.

例如strlen(),纯粹的功能,而不纯的功能rand().

__attribute__ ((pure)) int fun(int i)
{
    return i*i;
}

int main()
{
    int i=10;
    printf("%d",fun(i));//outputs 100
    return 0;
}

http://ideone.com/33XJU

上述程序的行为方式与没有pure声明时相同.

将函数声明为pure[如果输出没有变化]有什么好处？

在微软的采访中已经提出了这个问题.非常好奇地知道为什么这些人会对概率提出如此奇怪的问题？

给定rand(N),一个随机生成器,它产生从0到N-1的随机数.

int A[N]; // An array of size N
for(i = 0; i < N; i++)
{
    int m = rand(N);
    int n = rand(N);
    swap(A[m],A[n]);
}

编辑:请注意种子不固定.

阵列A保持不变的概率是多少？
假设数组包含唯一元素.

考虑以下计划:

class A
{
    public:
    A(int i)
    {
            cout<<"Called"<<endl;
    }
};

int main()
{
    vector<A> v(5,A(1));
    return 0;
}       

我得到了输出:http://ideone.com/81XO6

 Called

为什么即使我们构造5个对象,构造函数也只被调用一次？编译器
如何vector内部处理？

方法1:
C(n,r)= n!/(nr)!r!

方法2:
在wilf的" 组合算法 "一书中,我发现:
C(n,r)可以写成C(n-1,r) + C(n-1,r-1).

例如

C(7,4) = C(6,4) + C(6,3) 
       = C(5,4) + C(5,3) + C(5,3) + C(5,2)
       .   .
       .   .
       .   .
       .   .
       After solving
       = C(4,4) + C(4,1) + 3*C(3,3) + 3*C(3,1) + 6*C(2,1) + 6*C(2,2)

如您所见,最终解决方案不需要任何乘法.在每种形式C(n,r)中,n == r或r == 1.

这是我实现的示例代码:

int foo(int n,int r)
{
     if(n==r) return 1;
     if(r==1) return n;
     return foo(n-1,r) + foo(n-1,r-1);
}

请参见此处的输出

在方法2中,存在重叠的子问题,我们正在调用递归来再次解决相同的子问题.我们可以通过使用动态编程来避免它.

我想知道哪个是计算C(n,r)的更好方法？

我在codeblock版本10.05中编写C代码.

该计划是:

int main(int argc , char *argv[])
{
    printf("Entered number is %s \n", argv[1]);
    return 0;
}

但是,当我编译当前文件,然后运行该程序时,会出现一个终端.但是,终端不等待命令行输入并直接输出

<null>

请注意,在上面的程序中,我省略了处理零数量命令行参数的代码.我如何提供命令行参数？

你如何有效地计算从1到N的整数的十进制表示中0的出现次数？

e.g. The number of 0's from 1 to 105 is 16. How?

10,20,30,40,50,60,70,80,90,100,101,102,103,104,105    

计算0的数量,你会发现它16.

显然,不会赞赏蛮力方法.你必须想出一种方法,它不依赖于"有多少数字落在1到N之间".我们可以通过看到某种模式来做到吗？

我们不能扩展这里编译的逻辑来解决这个问题吗？

今天,我很想在C++中找到结构和类之间的一些差异.所以,我发现了一些不同之处:

1. 在结构中,默认情况下,成员是公共的,而在课堂上是私有的.
2. 结构的情况下的继承在默认情况下是公共的,而在类的情况下是私有的.
3. 类可以参与模板,而结构则不能.

单击此处以查看在模板的情况下不能使用结构代替类. http://ideone.com/p5G57

template<struct T> void fun(T i)
{
    cout<<i<<endl;
}

int main()
{
    int i=10;
    fun<int>(i);
    return 0;
}

它给出了错误:

prog.cpp:4: error: ‘struct T’ is not a valid type for a template constant parameter
prog.cpp: In function ‘void fun(T)’:
prog.cpp:4: error: ‘i’ has incomplete type
prog.cpp:4: error: forward declaration of ‘struct T’
prog.cpp: In function ‘int main()’:
prog.cpp:12: error: no matching function for call to ‘fun(int&)’

但是,如果struct被class …

给定一个数组,其中每个数字的出现次数是奇数,除了一个出现次数是偶数的数字.找到偶数出现的数字.

例如

1, 1, 2, 3, 1, 2, 5, 3, 3

输出应该是:

2

以下是限制:

1. 数字不在范围内.
2. 就地做.
3. 所需的时间复杂度为O(N).
4. 数组可能包含负数.
5. 数组未排序.

由于上述限制,我的所有想法都失败了:基于比较的排序,计数排序,BST,散列,暴力.

我很想知道:XORing会在这里工作吗？如果有,怎么样？

我知道此类问题已经发布过,但我想讨论一些新的事情.所以,我发布了它.

给定未排序的整数数组,找到满足x ^ 2 + y ^ 2 = z ^ 2的所有三元组.

例如,如果给定的数组是 - 1,3,7,5,4,12,13答案应该是 - 5,12,13和3,4,5

我建议下面的算法复杂度为O(n ^ 2) -

• 按降序对数组进行排序. - O(nlogn)
• 每个元素都是方形 - 上)

现在它减少了在排序数组中找到所有三元组(a,b,c)的问题,使得a = b + c.

面试官坚持要求比O(n ^ 2)更好的解决方案.

我已经阅读了维基百科上的3SUM问题,强调问题可以在O(n + ulogu)中解决,如果数字在[-u,u]范围内,假设数组可以表示为位向量.但我无法清楚地了解进一步的解释.

有人可以通过一个很好的例子来帮助我理解发生了什么吗？