请听第一道算法题:爱健身的小王

夏天的风_495e · · 4792 次点击 · · 开始浏览    
这是一个创建于 的文章,其中的信息可能已经有所发展或是发生改变。

刚参加工作的小伙伴可能觉得算法没什么用处,会工程开发就行,会写业务就行。但是当你达到一定的水平以后,你会发现系统的瓶颈可能在于算法,一个好的算法和一个差的算法在系统性能上的表现有云泥之别。不止于此,学习和练习算法也能锻炼人的思维能力,不管你做什么事都会有潜移默化的影响。所以,总之一句话,让我们现在就开始学习算法吧!

今年实习生招聘差不多也接近尾声了,各大厂的笔试题目在网上都能找到。今天我们看一道美团的笔试题,比较容易。

题目如下图所示:

image.png

这种题目切忌一上来就暴力求解。首先要分析一下题目的规律。我们假设小王从正方形的左上角(记为原点)开始走起。

首先分析一下小王会在哪里停下来。小王从起点走n+1步后打了第一个标记,我们记为A点,再走n+1步又打一个标记,记为B点,以此类推。假设小王打了若干次标记后不是在A点停下来,比如是在B点停下来,那么往回退n+1步,小王上一次一定是在A点重复打了一个标记,这就有矛盾了,所以,小王一定是在A点停下来的。

这个结论一旦成立,说明小王在A点重复打标记之前的一次就是在原点打标记。我们记小王一共标记了m次,那么在原点打标记就是第m-1次打标记,而每打一次标记要走n+1步,所以到第m-1次打标记为止一共走了(n+1)(m-1)步,这(n+1)(m-1)步刚好等于周长的若干倍,即

(n+1)(m-1)=4n*k

从这个式子中可以看出,(n+1)(m-1)既是n+1的倍数,也是4n的倍数,又因为我们要找的m是让上式第一次成立的m,所以我们只要找出n+1和4n的最小公倍数,然后除以n+1即可得到答案。

所以m=[n+1, 4n] / (n+1) + 1

而最小公倍数[n+1, 4n] = (n+1)*4n / (n+1, 4n)

所以m = 4n / (n+1, 4n) + 1

到这里我们发现这道题的本质变成了求最大公约数问题(gcd)。最大公约数问题的代码网上到处都是。

最后附上golang版的代码:

package main

import (
  "fmt"
  "strconv"
  "bufio"
  "os"
  "strings"
)

func main() {
  var ts string
  var ns string
  fmt.Scanln(&ts)
  t, _ := strconv.Atoi(ts)
  
  inputReader := bufio.NewReader(os.Stdin)
  ns, _ = inputReader.ReadString('\n')
  ns = strings.Trim(ns, "\r\n")
  n_slice := strings.Split(ns, " ")
  for i := 0; i < t; i++ {
    n, _ := strconv.Atoi(n_slice[i])
    fmt.Println(4*n/gcd(n+1, 4*n)+1)
  }
}

func gcd(a, b int) int {
  if b == 0 {
    return a
  } else {
    return gcd(b, a%b)
  }
}

大家想看更详细的视频解答的话,可以上b站或者斗鱼等网站上搜“大雪菜”(这个up主是北大的大神级人物),能找到相关的视频。

欢迎关注博主个人微信公众号~~~

image

有疑问加站长微信联系(非本文作者)

本文来自:简书

感谢作者:夏天的风_495e

查看原文:请听第一道算法题:爱健身的小王

入群交流(和以上内容无关):加入Go大咖交流群,或添加微信:liuxiaoyan-s 备注:入群;或加QQ群:701969077

4792 次点击  
加入收藏 微博
添加一条新回复 (您需要 登录 后才能回复 没有账号 ?)
  • 请尽量让自己的回复能够对别人有帮助
  • 支持 Markdown 格式, **粗体**、~~删除线~~、`单行代码`
  • 支持 @ 本站用户;支持表情(输入 : 提示),见 Emoji cheat sheet
  • 图片支持拖拽、截图粘贴等方式上传