• 设为首页
  • 点击收藏
  • 手机版
    手机扫一扫访问
    迪恩网络手机版
  • 关注官方公众号
    微信扫一扫关注
    公众号

[Swift]美人征婚问题

原作者: [db:作者] 来自: [db:来源] 收藏 邀请

★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★
➤微信公众号:为敢(WeiGanTechnologies)
➤博客园地址:山青咏芝(https://www.cnblogs.com/strengthen/
➤GitHub地址:https://github.com/strengthen/LeetCode
➤原文地址:https://www.cnblogs.com/strengthen/p/10777313.html 
➤如果链接不是山青咏芝的博客园地址,则可能是爬取作者的文章。
➤原文已修改更新!强烈建议点击原文地址阅读!支持作者!支持原创!
★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★★

热烈欢迎,请直接点击!!!

进入博主App Store主页,下载使用各个作品!!!

注:博主将坚持每月上线一个新app!!!

       公元2019年4月1日,时值西方愚人节,互联网激流暗涌,网络大佬各领风骚。然而从Internet某个小角落,一个征婚热帖撩动了广大单身攻城狮、程序猿、码农的热血激情。而今暗流退下,且让我们重新回味,整理一番。

如你,猜测这是新出炉的高智商诈骗剧本?或者认为是某某互联网HR大佬招兵买马的钓鱼问题?就像你在百度首页按下[F12],映入眼帘的招聘文字。但我们眼中只看到算法问题,微信号是我们是特别不关心的事情。这个征婚正文比较影响你的关注点,我现在马上提炼出具体的问题: 

问题1:求乘积为[7140229933]的两个质数? 

问题2:求乘积为[6541367***]的两个质数?

 

问题1思路历程: 

质数(prime number)定义:在大于1的自然数中,只能被自身或1整除的数即为质数。质数又称素数,质数有无限多个。 

(1)、我们先用埃拉托色尼筛选法求出指定范围的质数集合。 

埃拉托色尼筛选法(the Sieve of Eratosthenes)简称埃氏筛法,是古希腊数学家埃拉托色尼(Eratosthenes 274B.C.~194B.C.)提出的一种筛选法。 是针对自然数列中的自然数而实施的,用于求一定范围内的质数,它的容斥原理之完备性条件是p=H~。

埃氏筛法步骤: 

(a).先把1删除(1既不是质数也不是合数) 

(b).读取队列中当前最小的数2,然后把2的倍数删去 

(c).读取队列中当前最小的数3,然后把3的倍数删去 

(d).读取队列中当前最小的数5,然后把5的倍数删去 

(e).读取队列中当前最小的数7,然后把7的倍数删去 

(f).如上所述直到需求的范围内所有的数均删除或读取

注意:此处的队列并非数据结构队列,如需保留运算结果,处于存储空间的充分利用以及大量删除操作的实施,建议采用链表的数据结构。

(2)、有了质数集合,两数之积这个问题是不是有一点眼熟呢? 

正在美帝田纳西求学的大神级前辈Grandyang告诉我们:平生不识TwoSum,刷尽LeetCode也枉然。。。。。 

因为7140229933是10位数,每个因数平均是5位。所以我们可以选择筛选出十万范围内的质数,只需一次通过哈希表,尝试求出这两个质数(理工女同学的微信号)。并且我们把求质数的范围作为一个参数,如果十万范围里面求不出结果,我们可以扩大筛选范围。

Talk is cheap.Show me your code.多说无用,看我行动。 

 1 import Foundation
 2 class Solution {
 3     func findBeauty(_ number:Int, _ target: Int) -> String {
 4         var primes = Set(2...number)
 5         //埃拉托色尼筛选法
 6         (2...Int(sqrt(Double(number)))).forEach {
 7             let _ = primes.subtract(stride(from: 2*$0, through: number, by: $0))
 8         }
 9         //转换为Double
10         let nums:[Double] = Array(primes).map{Double($0)}
11         var table:[Double:Double] = [Double:Double]()
12         for (firstIndex, num) in nums.enumerated() {
13             let res: Double = Double(target) / Double(num)
14             //可选链接
15             if table[res] == nil
16             {
17                 table[num] = Double(firstIndex)
18             }
19             else
20             {
21                 //转换为Int
22                 let res:Int = Int(res)
23                 let num:Int = Int(num)
24                 print(res)
25                 print(num)
26                 let str:String = res > num ? (String(num) + String(res)) : String(res) + String(num)
27                 return "Lin" + str
28             }
29         }
30         return String()
31     }
32 }

点击:Playground测试

1 //测试
2 print(Solution().findBeauty(100000, 7140229933))
3 //Print 85229
4 //Print 83777
5 //Print Lin8377785229

注意:已经输出女同学的微信号。但是你搜索之后会发现,这只是个小号。认真看完第2问,文章末尾告诉你常用微信号。

问题2思路历程:

我们同样用埃拉托色尼筛选法求出指定范围的质数集合。积为10位数,每个因数平均是5位。所以我们筛选出十万范围内的质数尝试求出结果。我们把求质数的范围作为一个参数,如果十万范围里面求不出结果,我们可以扩大筛选范围。6541367***最后三位数未知。但是我们可以知道:

最小值:6541367000

最大值:6541367999

遍历筛选的质数集合,满足三个条件:

(a)、同时用最大值和最小值分别除以集合中遍历的元素,所得两个商为一个浮点数,浮点数落在连续的两个整数范围内。因为质数为奇数,所以我们取这两个整数中的奇数。取整的两个奇数判等。

(b)、判等的奇数,也必在筛选的质数集合中。

(c)、判等的奇数和遍历的质数之积,减去与1000求余所得结果为最小值。

Talk is cheap.Show me your code.多说无用,看我行动。

 1 import Foundation
 2 class Solution {
 3     func findBeauty2(_ number:Int, _ target: Int) -> [Int] {
 4         var primes = Set(2...number)
 5         //埃拉托色尼筛选法
 6         (2...Int(sqrt(Double(number)))).forEach {
 7             let _ = primes.subtract(stride(from: 2*$0, through: number, by: $0))
 8         }
 9         let nums:[Int] = Array(primes).sorted()
10         //最小值
11         let minNum:Int = target * 1000
12         //最大值
13         let maxNum:Int = minNum + 999
14         //遍历数组
15         for i in 0..<nums.count - 1
16         {
17             let num1:Int = getOdd(maxNum,nums[i])
18             let num2:Int = getOdd(minNum,nums[i])
19             let num3:Int = num1 * nums[i]
20             //质数必须是奇数
21             if num1 == num2 && nums.contains(num1) && minNum == (num3 - num3 % 1000)
22             {
23                print(num3)
24                return([nums[i],num1])
25             }
26         }
27         return [-1,-1]
28     }
29     
30     //质数必为奇数,获取奇数
31     func getOdd(_ num1:Int,_ num2:Int) -> Int
32     {
33         let number:Int = Int(ceil(Double(num1) / Double(num2)))
34         return number % 2 == 0 ? (number - 1) : number
35     }
36 }

点击:Playground测试

1 //测试
2 print(Solution().findBeauty2(100000, 6541367))
3 //Print 6541367489
4 //Print [67049, 97561]

但是我们还没拿到美人的微信大号呢!经过我夜观天象,掐指一算。获得美女学霸其人真正微信:(点击左上角菜单,扫一扫加博主微信。向博主咨询)


鲜花

握手

雷人

路过

鸡蛋
该文章已有0人参与评论

请发表评论

全部评论

专题导读
上一篇:
Swift统计操作list container、show account结果为0的问题发布时间:2022-07-13
下一篇:
21个高质量的Swift开源iOS App发布时间:2022-07-13
热门推荐
热门话题
阅读排行榜

扫描微信二维码

查看手机版网站

随时了解更新最新资讯

139-2527-9053

在线客服(服务时间 9:00~18:00)

在线QQ客服
地址:深圳市南山区西丽大学城创智工业园
电邮:jeky_zhao#qq.com
移动电话:139-2527-9053

Powered by 互联科技 X3.4© 2001-2213 极客世界.|Sitemap