精华内容
下载资源
问答
  • 小于N 的所有质数

    2017-11-10 17:44:00
    笔试题目当中,素数出现的几率有点大。昨天就做了一个,感觉不是很难,但可以考查程序员的数学和编码功底。 用嵌套循环来实现是很理想的,怎样减少循环的次数?怎样求出小于N的所有质数? 不可能将一个数除与...

      笔试题目当中,找素数出现的几率有点大。昨天就做了一个,感觉不是很难,但可以考查程序员的数学和编码功底。

         用嵌套循环来实现是很理想的,怎样减少循环的次数?怎样求出小于N的所有质数?

         不可能将一个数除与所有小于它的数字,只要检查到N的平方根就好了。但直接开根号还有个精度的问题。这个可能会产生误差。

         索性将判断条件写成 i*i<=N ,道理也是很简单的 i 大于N 的平方根,在检查 第一个 i 除数 N 之前可以先检查 小于第二个 i 是否可以 整除 N。

        下面自己敲的求素数:

         

    复制代码
    import java.util.ArrayList;
    
    public class Prime {
    
        public static int[] findPrime(final int max) {
            int[] prime = new int[max + 1];
            ArrayList list = new ArrayList();
        
            // 两个嵌套循环 ,赋值不是质数
            for (int j = 2; j * j <= max; j++) {
                for (int k = 2*j; k <= max; k++) {
                    if (k % j == 0) {
                        //不是质数 数组对应赋值为1
                        prime[k] = 1;
                    }
                }
            }
            for (int i = 2; i < max; i++) {
                //因为JAVA数组默认赋值为整数“0”,所以所有是质数的经过上面的嵌套循环数组所对应的值是没有发生的
                if (prime[i] == 0) {
                    list.add(new Integer(i));
                }
            }
        //将list 转换为数组返回
            int[] p = new int[list.size()];
            for (int i = 0; i < list.size(); i++) {
                p[i] = (Integer) list.get(i);
            }
            return p;
    
        }
    
        public static void main(String[] args) {
            int[] prime = Prime.findPrime(1000);
            for (int i = 0; i < prime.length; i++) {
                System.out.print(prime[i] + " ");
            }
        }
    
    }
    复制代码

     本文转自Orson博客园博客,原文链接:http://www.cnblogs.com/java-class/archive/2013/05/26/3099994.html,如需转载请自行联系原作者

    展开全文
  • 请编写代码出那个缺失的整数。你有办法在O(n)时间内完成吗? int missingNumber(int* nums, int numsSize){ int num = 0; for(int i = 0; i < numsSize; i++) { num = num ^ i; num = num ^ nums[i]; } ...

    数组nums包含从0到n的所有整数,但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗?

    int missingNumber(int* nums, int numsSize){
        int num = 0;
        for(int i = 0; i < numsSize; i++)
        {
            num = num ^ i;
            num = num ^ nums[i];
        }
        num ^= numsSize;
        return num;
    }
    

    一个整型数组 nums 里除两个数字之外,其他数字都出现了两次。请写程序找出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。

    int* singleNumbers(int* nums, int numsSize, int* returnSize){
        int sum = 0;
        for(int i = 0; i < numsSize; i++)
        {
            sum ^= nums[i];
        }
    
        int flag = sum & (-sum);
        int* ans = (int *)malloc(sizeof(int)*2);
    
        ans[0] = ans[1] = 0;
    
        for(int i = 0; i < numsSize; i++)
        {
            if((flag & nums[i]) == 0)
                ans[0] ^= nums[i];
            else
                ans[1] ^= nums[i];
        }
    
        *returnSize = 2;
        return ans;
    }
    

    总结:
    0 ^ a = a
    a ^ (b ^ c) = (a ^ b) ^c
    a ^ a = 0
    a & -a 只保留a的二进制数的最低位的1

    展开全文
  • 编敲代码出这个两个仅仅出现一次的数字。要求时间复杂度O(n),空间复杂度O(1). 如 {2,4,3,6,3,2,5,5},输出{4,6} 解析: 空间复杂度为O(1)断绝了用hash-table的思路,时间复杂度O(n)断绝排序的思路。 怎样...

    题目描写叙述:
    一个整型数组里除了两个数字之外,其它的数字都出现了两次。

    编敲代码找出这个两个仅仅出现一次的数字。要求时间复杂度O(n),空间复杂度O(1).
    {2,4,3,6,3,2,5,5},输出{4,6}


    解析:
    空间复杂度为O(1)断绝了用hash-table的思路,时间复杂度O(n)断绝排序的思路。

    怎样推断一个数字出现2次呢?

    • 计数
    • 异或:假设出现2次。随意数字和自己异或都为0

    异或的性质:
    不论什么数字和 0 异或。都为它本身。
    随意数字和自己异或都为0。

    由于成对出现的元素异或结果为 0,那么整个数组的异或结果为仅仅出现 一次 的元素的异或结果

    由于存在2个出现一次的元素。所以终于结果是2者的异或结果。那么怎样分离出这2个元素?
    这2个出现一次的元素。不相等,那么异或的结果不等0。即2进制表示肯定有1位是不为 0 的(都为0,说明相等),等价于这2个元素的此位是不相等的,我们依据该位,能够将整个数组分为2部分,该位为 1 的分为 1部分,为 0 的一部分。

    此时,2个仅仅出现一次的元素被分离开,而成对出现的元素每一位都相等,因此它们也是成对的分布在2个部分数组中。然后我们分别对这2部分计算异或的结果,就可以得到 2 个仅仅出现一次的数字。

    注意: &, |, ~ 的优先级小于 ==,>, < ,注意加括号。

    #include <iostream>
    using namespace std;
    int FindBitIndexofOne(int number) {
        unsigned int index = 0;
        // 如 0x0010 返回 1, 注意 & 的优先级小于 ==,必须有()
        while ((number & 0x01) == 0 && index < 8 * sizeof(int)) {
            number = number >> 1;
            index++;
        }
        return index;
    }
    bool IsOneBit(int number, unsigned int index) {
        while (index) {
            number = number >> 1;
            index--;
        }
        if (number & 0x01)
            return true;
        else
            return false;
    }
    bool FindNumApperOnce(int nums[], int length, int &result1, int &result2) {
        if (nums == NULL || length < 2)
            return false;
        int XORResult = 0;
        for (int i = 0; i < length; i++)
            XORResult ^= nums[i];
        unsigned int oneBitIndex = FindBitIndexofOne(XORResult);
        result1 = 0, result2 = 0;
        for (int i = 0; i < length; i++) {
            if (IsOneBit(nums[i], oneBitIndex))
                result1 ^= nums[i]; // 标志位是 1 的数组
            else
                result2 ^= nums[i];// 标志位是 0 的数组
        }
        return true;
    }
    
    int main() {
        int nums[] = { 1,3,2,4,6,42,4,42,1,3 };
        int result1, result2;
        if (FindNumApperOnce(nums, sizeof(nums) / sizeof(nums[0]), result1, result2))
            cout << result1 << " " << result2 << endl;
    }
    

    转载于:https://www.cnblogs.com/mfmdaoyou/p/7120016.html

    展开全文
  • //采用位图的方法,如果是在一个1000万大的数组中,其中只有两个数是相同的,可以在O(n)时间复杂度内出相同的数 //数组b是一块连续内存区域,用数组中的每一bit表示一个数是否存在,1表示存在,0不存在,比如,...
    //采用位图的方法,如果是在一个1000万大的数组中,其中只有两个数是相同的,可以在O(n)时间复杂度内找出相同的数
    //数组b是一块连续内存区域,用数组中的每一bit表示一个数是否存在,1表示存在,0不存在,比如,给定一个数字1025,
    //那么,就把b数组的第1025bit置为1,基本思想就是用数组内存的一个bit所在的下标值作为数据数值,而不用真正去储存这个值,用下标作为值,节省空间。
    //因为操作系统内存最小操作单位是字节,所以不能直接操作bit,因此,首先,必须找到第1025bit所在的字节,就是1025/8(因为下标是从0开始,整除截断的无关紧要,下步用到),
    //然后再找出1025在该字节的哪一bit,就是1025%8=1,整个意思就是,1025在b数组的第1025/8个字节的第1 bit中,然后用&操作访问该bit是否为1,为1则表明1025存在了.
    #include <stdio.h>
    int a[3]={1,10000000,10000000};
    //char类型为8位,共需要10000000/8个char
    static unsigned char b[10000000/8+1];
    int i;
    void main() {
        for (i=0;i<3;i++) {
    		//1<<(a[i]%8)表示1左移余数的位数即为a[i]在b中对应的位,例如1024%8=0,然后1<<0=1(二进制止:00000001),所以1024在b数组的第1024/8个字节的第1 bit中;
    		//1025%8=1,然后1<<1=2(二进制:00000010),所以1025在b数组的第1025/8个字节的第2 bit中;1026%8=2,然后1<<2=4(二进制:00000100),所以1026在b数组的第1026/8个字节的第3 bit中;以次类推
            if (b[a[i]/8]&(1<<(a[i]%8))) break;
            else b[a[i]/8]|=(1<<(a[i]%8));
        }
        if (i<3) printf("%d\n",a[i]);
        else     printf("Can not find.\n");
    	printf("%d\n",1<<(1024%8));
    	printf("%d",5);
    }


    展开全文
  • 将数字正序输出

    千次阅读 2018-05-30 17:10:52
    判断数字的位数和将数字逆输出都已经讲过了,今天讲讲怎样将数字正序输出:例如1234,我们需要分别输出1 2 3 4,现在就有一个难题了,我们怎样找到一个数字的最高位呢?我们会发现要想找到最高位首先得知道一个数字...
  • 出一个N自守数,N-自守数满足的要求如题目所示。输出N-自守数的N值和该数字,用空格间隔开。 题目分析 由于N<10,所以我们完全可以通过遍历N的方式找到正确的N值。但我们要怎样得到NK^2后面的几个数字呢? 我们...
  • 自幂数是指一个 n 位数,它的每个位上的数字的 n 次幂之和等于它本身。(例如:当n为3时,有1^3 +...下面分析怎样找出自幂数的算法: 1:首先要能判断一个自幂数 (这里面可以分为几个函数 1.找出数字的位数 2.给一个...
  • 求写程序出这两个只出现一次的数字。要求时间复杂度是O(n),空间复杂度是O(1)。 边界条件及异常: 数组为空,没有只出现一次的数,只有一个只出现一次的数。 思路: 这题好难! 首先我们考虑如果数组中只有...
  • 点击蓝关注我们Contents1 出两个链表的交点 (160)2 链表反转 (206)3 归并两个有序的链表 (21)4 从有序链表中删除重复节点(83)5 删除链表的倒数第 n 个节点(19)6 交换链表中的相邻结点 (24)7 链表求和(445)8 回文...
  • 拳王昨天想一款音频转文字软件, 我分别在3个渠道去搜索了一下: 淘宝搜索结果: 可以看到这个软件在N多的公众号里都是免费分享的!并且都是很知名的语音转换软件,安装既是VIP用户;不用花费一分钱; 微店结果 ...
  • 由于我只是个业余编程爱好者,加上文化底蕴差,只要涉及算法和编程理论方面的东西,我就无能为力了,所以直到目前,我也不知道具体的描边算法是怎样的(网上搜索过N次,也没找到答案,可能这方面的东西是要卖钱的)...
  • *怎样找出那个维一出现一次的元素。 *要求的复杂度:时间:O(n),空间:O(1) *将数组中的数字进行异或运算,两个数进行异或,相同为0,不同为1,则出现两次的数全部抵消了。 *扫描一遍数组复杂度为o(n),另外存储...
  • n个元素的全排列(非递归+去重)

    千次阅读 2016-06-16 19:39:20
    非递归采用的方法是:字典排序后继;该方法自带去重的效果,并且效率高、顺序自然。 以3个数字的全排列为例,共有 3! = 6 种排列,这6种排列是有大小的,如果按从小到大排列,示意如下: 123 132 213 231 312 ...
  • %最大值和下标 stem(lambda(ix)*1e6,mx,'--','filled') %画直杆图 text(lambda(ix)*1e6,mx,[num2str(lambda(ix)'*1e6)],'fontsize',fs)%显示峰值波长 t=1300:2020; %较密的温度向量 lambda=b./t; %波长向量 ...
  • 怎样通过只读遍历一次数组,出数字a和b。 由于只能遍历一次,在遍历数组arr时,算出 a和b的差值,以及a和b的平方差,通过解方程,即可求得a和b。具体做法为: 设: s1 = 1 + 2 + ... + n (= n * ...
  • 怎样通过只读遍历一次数组,出数字a和b; 只能遍历一次: 方法1:首先想到的是列方程组,直接求解a,b; (1)等式1 :s1为1…n的和 s1=n(n+1)/2; 而s2是给定数组的和 这样的话,根据题意有,s1=s2+a-b; (2)等式2...
  • 求a,b两种方法

    2013-08-15 21:30:00
    怎样通过只读遍历一次数组,出数字a和b; 只能遍历一次: 方法1:首先想到的是列方程组,直接求解a,b; (1)等式1 :s1为1…n的和 s1=n(n+1)/2; 而s2是给定数组的和 这样的话,根据题意有,s1=s2+a-b; (2)等式2: ...
  •  n个互不相同的数字,每个数字有两个,共2*n个数字,每次操作能够交换两个相邻数字的位置,要求最少的操作次数,使得任意相等的数字都相邻。 题解:  遇到相邻两个不相等的就到后面这个数字然后交换。  因为...
  • 贪心算法

    2015-09-04 11:36:25
    题意:  给定一个数字串,按奇偶顺序挑选几个数字,+奇选的数字-偶选的数字,问怎样顺序...O(N)去遍历,先出最大值,然后出最小值,就算完成一个子段。 至于最后的子段肯定是只有最大值,所以只需在读取的
  • 题意:  给定一个数字串,按奇偶顺序挑选几个数字,+奇选的数字-偶...O(N)去遍历,先出最大值,然后出最小值,就算完成一个子段。 至于最后的子段肯定是只有最大值,所以只需在读取的串最后面加一个数字0即可。
  • 多重部分和

    2020-07-22 18:30:07
    这道题最难的还是在于怎样找递推关系,因为涉及到每个数都有多个,所以我们可以将dp[i+1][j]抽象为用前i种数字加和得到j时第i种数最多能剩余多少个(如果不能加和得到j就为-1) dp[i+1][j]= (1)mi

空空如也

空空如也

1 2 3 4 5
收藏数 83
精华内容 33
关键字:

怎样找n字