笔试算法题（29）：判断元素范围1到N的数组是否有重复数字 & 计算整数的7倍

 1 bool HasDup(int *array, int length, int cur) {
 2         if(cur==length) return false;
 3 
 4         if(array[cur]==cur)
 5                 /**
 6                  * 注意++cur的特性，如果是cur++则参数值是cur
 7                  * 而不是cur+1
 8                  * */
 9                 return HasDup(array, length, ++cur);
10         else if(array[cur]==array[array[cur］)
11                 return true;
12         else {
13                 int temp;
14                 temp=array[cur];
15                 array[cur]=array[temp];
16                 array[temp]=temp;
17                 return HasDup(array,length,cur);
18         }
19 }
20 int main() {
21         int array[]={6,5,3,1,5,4,0};
22         if(HasDup(array,7,0))
23                 printf("\nthere is duplication");
24         else
25                 printf("\nthere is no duplication");
26         return 0;
27 }

 1 /**
 2  * 小于等于0，直接返回false
 3  * 如果为2的次幂，则二进制表示中
 4  * 有且仅有一位是1，当这个数减去1
 5  * 则原有的1变成0，其右边的所有bit
 6  * 变成1，此时他们的&操作为0
 7  * */
 8 bool If2Power(int n) {
 9         if(n<=0) return false;
10         /**
11          * 注意&的优先级小于=，所以必须加括号
12          * */
13         if((n&(n-1))==0) return true;
14         else return false;
15 }
16 /**
17  * 实现乘法可以转换成移位操作，向左移动移K位
18  * 等于*（2^K），最后再加上或者减去差值
19  * 注意加括号
20  * */
21 int Times7(int n) {
22         int t=n;
23         return (n<<3)-t;
24 }
25 
26 int main() {
27         if(If2Power(4))
28                 printf("\nyes");
29         else
30                 printf("\nno");
31 
32         printf("\n21*7= %d",Times7(21));
33         return 0;
34 }