3的幂
题目:给定一个整数，写一个函数来判断它是否是 3 的幂次方。
示例 1:
输入: 27
输出: true
示例 2:
输入: 0
输出: false
示例 3:
输入: 9
输出: true
示例 4:
输入: 45
输出: false
进阶：
你能不使用循环或者递归来完成本题吗？
思路：单纯这个题就是程序入门就会的，但是这个进阶条件不适用循环或者递归才让这个题有点意思。我怀疑如果不用循环或者递归说明有一个常量计算是不是3的幂次方的方法。我去找找规律。
规律算是找完了吧，这个题怎么说呢，3的幂次方则说明只有有3或者3的次方的因数，剩下什么2，5，7，11之类的都不能有。本来我是想一个个列出来的，但是因为发现往后太多了，有点懒得算了，所以直接看了答案。看了答案真心有点觉得这个题出的有毛病，没有这么很直接的规律，就是生算：
解法只有一种，3的幂次方：int范围内只支持到3的19次方，所以一个个列出来，不是这个里面的就说明不是
class Solution {
public boolean isPowerOfThree(int n) {
if(n==0)
return false;
if(n==Math.pow(3,0)|n==Math.pow(3,2)|n==Math.pow(3,1)|n==Math.pow(3,2)|n==Math.pow(3,3)|n==Math.pow(3,4)|n==Math.pow(3,5)|n==Math.pow(3,6)|n==Math.pow(3,7)|n==Math.pow(3,8)|n==Math.pow(3,9)|n==Math.pow(3,10)|n==Math.pow(3,11)|n==Math.pow(3,12)|n==Math.pow(3,13)|n==Math.pow(3,14)|n==Math.pow(3,15)|n==Math.pow(3,16)|n==Math.pow(3,17)|n==Math.pow(3,18)|n==Math.pow(3,19)|n==Math.pow(3,20))
return true;
return false;
}
}
还有一种方法：就是在上面的基础上改进的版本，因为是三个幂，所以一个个数是关系就是上一个*3等于这个。所以直接把最大值取出来，除以n如果能整除说明是3的幂。不是说明不是。如下图;
class Solution {
public boolean isPowerOfThree(int n) {
return n > 0 && 1162261467 % n == 0;
}
}
4的幂
题目：给定一个整数 (32 位有符号整数)，请编写一个函数来判断它是否是 4 的幂次方。
示例 1:
输入: 16
输出: true
示例 2:
输入: 5
输出: false
进阶：
你能不使用循环或者递归来完成本题吗？
思路：对于进阶要求我想说一句：我不能。这几道题真的是恶心他妈给恶心开门，恶心到家了！我是真的有点反感这几道题。我也懒得看什么思路了，直接暴力列举法
class Solution {
public boolean isPowerOfFour(int num) {
return num == 1 || num == 4 || num ==16 || num == 64 || num == 256 || num == 1024 || num == 4096 || num == 16384 || num == 65536 || num == 262144 || num == 1048576 || num == 4194304 || num == 16777216 || num == 67108864 || num == 268435456 || num == 1073741824;
}
}
下一题。
反转字符串
题目：编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1：
输入：["h","e","l","l","o"]
输出：["o","l","l","e","h"]
示例 2：
输入：["H","a","n","n","a","h"]
输出：["h","a","n","n","a","H"]
这道题乍一看好像很简单啊。不就是数组第一个字符和最后一个字符交换，第二个和倒数第二个么？我先去撸代码看看坑在哪里。
!!!一直到运行完成通过我也没看出坑在哪里，很诧异leetCode里有这么白的题：
class Solution {
public void reverseString(char[] s) {
for(int i=0;i<s.length/2;i++){
char temp = s[i];
s[i] = s[s.length-1-i];
s[s.length-1-i] = temp;
}
}
}
下一题。
反转字符串中的元音字母
题目：编写一个函数，以字符串作为输入，反转该字符串中的元音字母。
示例 1:
输入: "hello"
输出: "holle"
示例 2:
输入: "leetcode"
输出: "leotcede"
说明:
元音字母不包含字母"y"。
思路：这个题怎么说呢，上道题的进化版。然后因为没有什么时间复杂度空间复杂度的要求，我就是第一直觉做的，用到了list，先转化char数组，然后元音提出来下标存list（根据list是有序的），最后根据list把第一个和最后一个下标的元素呼唤，第二个和倒数第二个互换，以此类推。直接贴代码：
class Solution {
public String reverseVowels(String s) {
//元音字母A E I O U
char[] str = s.toCharArray();
List<Integer> list = new ArrayList<Integer>();
for(int i=0;i<s.length();i++){
if(str[i]=='a' ||str[i]=='e'||str[i]=='i'||str[i]=='o'||str[i]=='u'
||str[i]=='A' ||str[i]=='E'||str[i]=='I'||str[i]=='O'||str[i]=='U'){
list.add(i);
}
}
for(int j =0;j<list.size()/2;j++){
char temp = str[list.get(j)];
str[list.get(j)] = str[list.get(list.size()-1-j)];
str[list.get(list.size()-1-j)] = temp;
}
return new String(str);
}
}
就是如图所示，这个代码其实性能还行，超过了百分之七八十的人，但是我总觉得这个aeiou的判断有点low啊，我去看看题解。
image.png
题解提到了用栈，或者双指针，但是双指针就要一层一层的循环，感觉直接 的感官度还不如我这个呢。这道题就算了，下一题。
两个数组的交集
题目：给定两个数组，编写一个函数来计算它们的交集。
示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2]
示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [9,4]
说明:
输出结果中的每个元素一定是唯一的。
我们可以不考虑输出结果的顺序。
思路：这个题，又看起来有点简单啊，没有时间空间要求，那么单纯遍历比较就行了？一个存map，另一个比较map中的key是否存在。我先去做做，看有没有坑
回来了，没啥坑，就是麻烦点，遍历三次，一次存map，一次存set（set有去重性）
最后一个set转换int数组。
class Solution {
public int[] intersection(int[] nums1, int[] nums2) {
Set<Integer> set = new HashSet<>();
Map<Integer, Integer> map = new HashMap<>();
for (int i = 0; i < nums1.length; i++) {
map.put(nums1[i], i);
}
for (int j = 0; j < nums2.length; j++) {
if (map.containsKey(nums2[j])) {
set.add(nums2[j]);
}
}
int[] res = new int[set.size()];
Iterator iterator = set.iterator();
int k = 0;
while (iterator.hasNext()) {
res[k] = (int) iterator.next();
k++;
}
return res;
}
}
其实这个做完我还是很心虚的，因为感觉这么麻烦的做一道题，可能是有什么技巧没想到，但是提交上去性能居然很棒，这个就奇怪了。
image.png
反正这道题就这样吧，下一题。
两个数的交集2
题目：给定两个数组，编写一个函数来计算它们的交集。
示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]
示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]
说明：
输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
我们可以不考虑输出结果的顺序。
进阶:
如果给定的数组已经排好序呢？你将如何优化你的算法？
如果 nums1 的大小比 nums2 小很多，哪种方法更优？
如果 nums2 的元素存储在磁盘上，磁盘内存是有限的，并且你不能一次加载所有的元素到内存中，你该怎么办？
思路：这道题就是上一道题的进化版，先说单纯的实现,就是把上一个用set换成list就可以解决这个可以有重复的问题（我就不写代码了，没必要）。这个题的亮点应该是进阶的几个要求
一点点说这个进阶要求：
1.如果已经排好序了，可以两个数组比较了，每次小的那个往前挪动，直到相等或者小的那个挪的比另一个大了。然后相等的存起来。存list，因为允许重复。
因为这个没有测试案例，所以脑补吧，我就不敲代码了。
2.nums1比2小。则1作为存map的数组，这样每次判断key是否存在消耗小。
3.这就到了我知识盲区了，完全不懂。
接下来我去看看题解了：
好吧，前两页看来，没有第三个硬盘的问题的解决办法。至于第一个第二个我因为是分别的问题，但是没想到是和的关系。
在有序的前提下，1比2数组长度小，可以用什么二分法或者双指针。
今天太晚了，就记录到这里。
如果稍微帮到你了记得点个喜欢点个关注，明天周一，祝大家新的一周工作顺顺利利~！
网友评论