唔，今天阳光贼好，而且不冷了，感觉这个冬天终于过去了！**然后开始正式刷题啦！（ps：最近工作有变动，可能会暂时放缓刷题进度去看一些别的面试题，但是我精神上与你们同在~献给最近一直互相鼓励刷题的小伙伴们！）
炒鸡丑数
题目：编写一段程序来查找第 n 个超级丑数。超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。
示例:
输入: n = 12, primes = [2,7,13,19]
输出: 32
解释: 给定长度为 4 的质数列表 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。
说明:
1 是任何给定 primes 的超级丑数。
给定 primes 中的数字以升序排列。
0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000 。
第 n 个超级丑数确保在 32 位有符整数范围内。
思路：这道题的思路还是有的啊，上一个丑数是2,3，5为质因数。但是是用系数成质数的方式来实现的。而且当时还不让用额外数组。但是这个质因数本身就是数组，所以我觉得系数相乘的方式也是可以的。我去实现下试试吧。
好了，一次ac。说真的，我觉得我这几天反应贼慢啊，不知道是上了年纪了还是没睡好的原因。。一直隐隐约约有思路但是理不出来。。这个题明明前两天才做过我居然还要从头理思路，我是不是要退休了~~
哎，我直接贴代码：
class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
if(n==1) return 1;
int[] res = new int[n];
res[0] = 1;
//所有最开的是系数都是res[0]，也就是1
int[] x = new int[primes.length];
for(int i = 1;i<n;i++){
int num = Integer.MAX_VALUE;
for(int j = 0;j<primes.length;j++){
num = Math.min(primes[j]*res[x[j]],num);
}
for(int j = 0;j<primes.length;j++) {
if(num/primes[j]==res[x[j]]) {
x[j]++;
}
}
res[i] = num;
}
return res[n-1];
}
}
感觉这个可能是我处理的不太好，两次for循环。一次大循环。性能不是很理想，我去想想怎么优化一下的。至于思路真的是完全抄丑数2的，没啥难度，就是直接判断下一个丑数是多少，然后找到第n个就行了。我记得丑数2是2,3,5三个质数并且不让用额外空间，所以都是字面量来判断，但是这个题中质因数数组不定长，我自己都觉得性能不好是应该的。先去优化试试。
额，我自己放弃优化了，直接看了性能排行第一的代码，只能说思路没问题，就是这个代码的写法上有差别。我直接贴代码：
class Solution {
public int nthSuperUglyNumber(int n, int[] primes) {
int[] uglyNumbers = new int[n];
uglyNumbers[0] = 1;
int primesNumber = primes.length, min = 1, next = 1;
int[] primeIndexes = new int[primesNumber];
int[] tempPrimes = new int[primesNumber];
Arrays.fill(tempPrimes, 1);
for (int i = 0; i < n; i++) {
uglyNumbers[i] = min;
min = Integer.MAX_VALUE;
for (int j = 0; j < tempPrimes.length; j++) {
if (tempPrimes[j] == next) {
tempPrimes[j] = primes[j] * uglyNumbers[primeIndexes[j]];
primeIndexes[j]++;
}
min = Math.min(tempPrimes[j], min);
}
next = min;
}
return uglyNumbers[n - 1];
}
}
其实我之前想过把里面的两个for循环合成一个，但是我又觉得时间复杂度是一样的，所以最终没去实践。。然后看了人家的代码，一看就会，但是自己就是想不到啊。。哎，这个题就这样了，下一题。
最大单词长度乘积
题目：给定一个字符串数组 words，找到 length(word[i]) * length(word[j]) 的最大值，并且这两个单词不含有公共字母。你可以认为每个单词只包含小写字母。如果不存在这样的两个单词，返回 0。
示例 1:
输入: ["abcw","baz","foo","bar","xtfn","abcdef"]
输出: 16
解释: 这两个单词为 "abcw", "xtfn"。
示例 2:
输入: ["a","ab","abc","d","cd","bcd","abcd"]
输出: 4
解释: 这两个单词为 "ab", "cd"。
示例 3:
输入: ["a","aa","aaa","aaaa"]
输出: 0
解释: 不存在这样的两个单词。
思路：大胆的想法，暴力遍历啊。挨个往后匹配找最大值啊，，，虽然百分之九十九会超时。。但是别的好办法也没有，只能去暴力比对了，但是我觉得重点是如何比对两个字符串是不是有重复元素。目前想法有比较char数组，但是我觉得这块是可以优化的，我去想想再写代码了。
如下代码,性能还行。大体思路是因为只含有小写字母，所以用一个26位二进制来表示。如果这个字母出现过，则这个位数是1（不管出现几次），否则是0。其实我觉得就是把下标代替字符，值代表出现次数的数组变为二进制的数的过程（当然不是我想出来的，是我百度出来的方法）。然后反正是没超时而且我觉得性能很不错
class Solution {
public int maxProduct(String[] words) {
int max = 0;
int[] n = new int[words.length];
for(int i = 0;i<n.length;i++){
//把每个字符串转化成26位二进制数，出现的字母是1，不出现的是0
for(char c : words[i].toCharArray()){
n[i] |= 1<<(c-'a');
}
}
for(int i = 0;i<words.length-1;i++){
for(int j = i+1;j<words.length;j++){
if((n[i] & n[j]) == 0){//说明没有重复元素
max = Math.max(words[i].length() * words[j].length(),max);
}
}
}
return max;
}
}
这种表现方式是我百度出来的结果，但是不是性能比较好的那一批，所以我去看看性能排行第一的代码吧：
我看了下性能第一的代码，差不多的思路，只不过我是变为char数组再变成二进制数的，人家是直接字符串处理的，少了一个步骤，我直接贴代码：
class Solution {
public int maxProduct(String[] words) {
if (words == null || words.length == 0) return 0;
int len = words.length;
int[] values = new int[len];
for (int i = 0; i < words.length; i++) {
String temp = words[i];
values[i] = 0;
for (int j = 0; j < temp.length(); j++) {
values[i] |= 1 << (temp.charAt(j) - 'a');
}
}
int maxProduct = 0;
for (int i = 0; i < len; i++) {
for (int j = i + 1; j < len; j++) {
if ((values[i] & values[j]) == 0 && (words[i].length() * words[j].length() > maxProduct)) {
maxProduct = words[i].length() * words[j].length();
}
}
}
return maxProduct;
}
}
这个题怎么说呢，不是很难，重点是超时问题。处理起来麻烦吧。然后这个题就这么过了，我现在觉得做的题多了思路就开拓了，什么时候下意识能用位操作了就是神功大成之日！哈哈。下一题下一题。
灯泡开关
题目：初始时有 n 个灯泡关闭。 第 1 轮，你打开所有的灯泡。 第 2 轮，每两个灯泡你关闭一次。 第 3 轮，每三个灯泡切换一次开关（如果关闭则开启，如果开启则关闭）。第 i 轮，每 i 个灯泡切换一次开关。 对于第 n 轮，你只切换最后一个灯泡的开关。 找出 n 轮后有多少个亮着的灯泡。
示例:
输入: 3
输出: 1
解释:
初始时, 灯泡状态 [关闭, 关闭, 关闭].
第一轮后, 灯泡状态 [开启, 开启, 开启].
第二轮后, 灯泡状态 [开启, 关闭, 开启].
第三轮后, 灯泡状态 [开启, 关闭, 关闭].
你应该返回 1，因为只有一个灯泡还亮着。
思路：看了好久题目。我觉得这个题应该不是代码上的难度，主要是题意上。我打算画一个图好好理解下。题目太狗了，就三个，好多规律都看不出来。下面是我画的图，虽然没画完，但是你看到规律了没？对，你没看错，就是没！有！规！律！我随着往下判断随着觉得这么画好傻的，其实这个规律就是硬性规律。我现在的思路就是n轮n个灯泡。创建一个长度n的数组。最开始都是0.0代表开启（第一轮都开启，我就从第一轮开始往后判断，不想填充1装作最开始了）。然后每走一轮判断一次就行了，需要变的0变1,1变0 。我去代码实现了。应该是很简单的。
很好，第一版本超时了，但是我看了下代码，结果的对的，只能说leetcode不想让我们暴力写呗：
class Solution {
public int bulbSwitch(int n) {
if(n==0) return 0;
if(n==1) return 1;
int[] d = new int[n+1];
d[0] = 1;//正常应该n个元素，但是我嫌下标和数字差1麻烦，所以补了个0，一直关闭状态，不用管。
for(int i = 2;i<=n;i++){
for(int j = i;j<=n;j++){
//整数倍数则翻转。0变1,1变0
if(j%i==0) d[j] = d[j]^1;
}
}
int sum = 0;
for(int i : d){
if(i==0) sum++;
}
return sum;
}
}
以上是我代码的逻辑，超时真的解决不了，刚刚我试着把这个直接当字面量写出来，但是继续提交，还是超时。。所以这是逼着我找规律啊！
但是别说，两次超时结果的获取我还真的找到规律了！
因为其实99999和100000差的只是最后一个灯。前面的应该都是一样的。所以这道题我竟然看出了dp的感觉。哈哈，我执行的结果是100000最后一个灯没亮，所以两个件结果都是316.我就继续接着按照这个思路测试，还真的有点心得，我把我所有的测试结果列出来。
之所以附上这么多截图就是为了找到这个规律。我再画个统计图能更明了的看出来：
好的吧，现在发现了没，这个规律简直简单的不行。就是从平方开始，到下一个平方的前一个数的灯数是平方的向下取整。
这句话我可能说的不是很明白，但是应该一看就能看懂了。所以我也就不多bb了，我去写代码了。
class Solution {
public int bulbSwitch(int n) {
return (int)Math.sqrt(n);
}
}
说真的，这个题是我做过的最简单的题目。没有之一。。甚至说数据库内置函数我都用的理直气壮。毕竟这道题不是考实现平方根的。
哈哈，虽说废了一下时间，但是觉得还是挺好玩的。下一题了。
零钱兑0
题目：给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。
示例 1:
输入: coins = [1, 2, 5], amount = 11
输出: 3
解释: 11 = 5 + 5 + 1
示例 2:
输入: coins = [2], amount = 3
输出: -1
说明:
你可以认为每种硬币的数量是无限的。
思路：这个题我怎么好像是做过呢。回溯递归？啥啥的？反正是先可着最大的用，最大的用不了返回上一步用第二大的。以此类推。我去试下代码吧。
我这个思路有几个问题：首先第一次选择完最大的，第二次还可以选择最大的么？如果选择了，那么也就是第二次还是从最大的开始判断？这就有问题了，所以后来代码改成包含几个最大的就全都用最大的，然后剩下的再去解析。
代码如下：
class Solution {
int res;
public int coinChange(int[] coins, int amount) {
if(amount==0) return 0;
Arrays.sort(coins);
res = Integer.MAX_VALUE;
dfs(coins,amount,0,coins.length-1);
return res==Integer.MAX_VALUE?-1:res;
}
public void dfs(int[] coins,int amount,int n,int idx){
//最小的都大直接pass.
//如果现在能实现的小次数都大于等于res.也直接pass
if(idx<0 || coins[0]>amount || amount/coins[idx]+n>=res) return;
if(amount%coins[idx]==0){
//走到这肯定最小值小于res。所以不用比较直接赋值
res = n+amount/coins[idx];
}else{
for(int i = amount/coins[idx];i>=0;i--){
dfs(coins,amount-i*coins[idx],n+i,idx-1);
}
}
}
}
代码其实比较简单，但是测试案例真的是让我见识了，1,0这种测试，所以我加了最上面那句如果金币是0则直接返回0。还有就是我本来以为零钱就是从小到大排好序的呢，也是我天真了，反正又排了下序。
反正在几次提交，面向测试案例编程后最终ac了，可喜可贺。
我感觉这道题其实不算是很难，就是细节处理比较多。中间递归的for循环关于i的起始值问题我改了好多次，一点点debug才确定这个是最终版。
最开始我就是从idx起，后来发现第一个测试案例就有问题，11-5=6.下一个直接6/2=3、然后答案就是4了。所以说比较纠结。
还有这里如果给定金额是当前可选最大值的倍数就不用往下比较了，因为以后的数只会越来越大， 不会更小。
反正这个代码性能超过百分之九十七，我觉得也是及格了的，所以这道题就这样了啊。
最后一道题。
摆动排序2
题目：给定一个无序的数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]... 的顺序。
示例 1:
输入: nums = [1, 5, 1, 1, 6, 4]
输出: 一个可能的答案是 [1, 4, 1, 5, 1, 6]
示例 2:
输入: nums = [1, 3, 2, 2, 3, 1]
输出: 一个可能的答案是 [2, 3, 1, 3, 1, 2]
说明:
你可以假设所有输入都会得到有效的结果。
进阶:
你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗？
思路：这个题我感觉不提进阶要求的话，简单的不行。排序，从中间节点（如果是奇数则偏后）将数组分成两个，然后小的先放，一个数组一个开始放置元素。思路就是这样。但是既然O(n)时间复杂度或者O（1）空间复杂度，具体要怎么实现就要好好想想了。重新分析下题目。这里说的是或的关系，所以我怀疑O（n）时间复杂和O（1）空间复杂是不能同时实现的。目前为止我觉得空间复杂的还好一点，毕竟快排找到中间节点的数值。然后前后一个一个的插入元素应该就可以了。另外时间复杂度的话，我记得是logN吧？反正目前就这一种想法了，我去试试看。
算了，写来写去快排也没觉得快多好，所以我用了sort（就是偷懒），然后剩下的就是双向插入（对，空间复杂度也没遵守，因为真的是做的没耐心了，我好冷啊）：
class Solution {
public void wiggleSort(int[] nums) {
Arrays.sort(nums);
int t;
int[] newNum = nums.clone();
int len = nums.length / 2;
if (nums.length % 2 == 1) {
nums[0] = newNum[0];
for (int i = 1; i <= len; i++) {
nums[2 * i] = newNum[i];
nums[2 * i -1] = newNum[len + i];
}
} else {
for (int i = 0; i < len; i++) {
nums[2 * i] = newNum[len-1 - i];
nums[2 * i + 1] = newNum[len * 2-1 - i];
}
}
}
}
最后其实这个空间复杂度我觉得其实是可以再做处理的，不过具体怎么处理我觉得如果麻烦点，再原数组上处理也不见得是不行。不过我今天就这样了，毕竟感觉很复杂，而且我是真的手冷。就当是一个思考题吧，明天我还记得的话会补上这个题的更优解的。
今天的笔记就记到这里，如果稍微帮到你了记得点个喜欢点个关注，也祝大家工作顺顺利利！生活健健康康！
