20200501
Plan
leetcode 每日一题
Notes
最近比较忙，都没什么时间打卡，趁着五一，每天多做几道。 今日题目：1071/912/面试题62，每道题目都有一个可以学习的点，下面依次记录：
- 字符串的最大公因子 对于字符串 S 和 T，只有在 S = T + ... + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。 返回最长字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。
示例 1： 输入：str1 = "ABCABC", str2 = "ABC" 输出："ABC"
示例 2： 输入：str1 = "ABABAB", str2 = "ABAB" 输出："AB"
示例 3： 输入：str1 = "LEET", str2 = "CODE" 输出：""
一、这道题刚开始用的是暴力法，假设str1为较长的字符串，则从长度length为len(str2)开始，取str2长度为length的所有子串，判断该子串是否为str1和str2的最大公因子。设m=len(str1),n=len(str2),时间复杂度为O(n^2*(m+n))。
二、想记录的是辗转相除法，太久没用，已经不太记得。
辗转相除法公式为：
gcd(a,b) = gcd(b,a mod b)
用go语言实现如下：（x>y）
func gcd(x,y int) int{
for y != 0 {
x, y = y, x%y
}
return x
}
可以将x,y分别换为str1,str2.
可定义str1%str2为：str1删去从前往后整数个str2的剩余部分。
912.排序数组 给你一个整数数组 nums，请你将该数组升序排列。 这道题没啥太多可说的，主要是太久不写快排，有点忘记，重新温习了下快排。
面试题62. 圆圈中最后剩下的数字 0,1,,n-1这n个数字排成一个圆圈，从数字0开始，每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。 例如，0、1、2、3、4这5个数字组成一个圆圈，从数字0开始每次删除第3个数字，则删除的前4个数字依次是2、0、4、1，因此最后剩下的数字是3。
示例 1： 输入: n = 5, m = 3 输出: 3
示例 2： 输入: n = 10, m = 17 输出: 2
这个题就是比较经典的约瑟夫环问题，刚开始想用一个循环链表，模拟约瑟夫环，每次都超时。这里想记录下数学解法： 假设n=5,m=3 把原来的数组想象成如下的扩展： 0 1 (2) 3 4 0 1 2 3 4 3 4 (0) 1 3 4 0 1 1 3 (4) 1 3 4 1 3 (1) 3 3 其中括号中的数字表示每一次要删除的数字。 则可以从前往后推导最后剩下的数字在原来的数组中的位置。 设当前位置为index,则上一轮的位置应该为(index+m)%上一轮数组长度,可参考如下过程： 最后一轮的位置为0，则倒数第二轮的位置为(0+3)%2=1 倒数第二轮的位置为1，则倒数第三轮的位置为(1+3)%3=1 倒数第三轮的位置为1,则倒数第四轮的位置为(1+3)%4=0 倒数第四轮的位置为0，则倒数第五轮（也就是刚开始）的位置为(0+3)%5=3 则返回nums[3]即可。