3的冪

題目:給定一個整數(shù)，寫一個函數(shù)來判斷它是否是 3 的冪次方。

示例 1:
輸入: 27
輸出: true
示例 2:
輸入: 0
輸出: false
示例 3:
輸入: 9
輸出: true
示例 4:
輸入: 45
輸出: false
進階：
你能不使用循環(huán)或者遞歸來完成本題嗎？

思路：單純這個題就是程序入門就會的，但是這個進階條件不適用循環(huán)或者遞歸才讓這個題有點意思。我懷疑如果不用循環(huán)或者遞歸說明有一個常量計算是不是3的冪次方的方法。我去找找規(guī)律。
規(guī)律算是找完了吧，這個題怎么說呢，3的冪次方則說明只有有3或者3的次方的因數(shù)，剩下什么2，5，7，11之類的都不能有。本來我是想一個個列出來的，但是因為發(fā)現(xiàn)往后太多了，有點懶得算了，所以直接看了答案?？戳舜鸢刚嫘挠悬c覺得這個題出的有毛病，沒有這么很直接的規(guī)律，就是生算：
解法只有一種，3的冪次方：int范圍內(nèi)只支持到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;
    }
}

還有一種方法：就是在上面的基礎上改進的版本，因為是三個冪，所以一個個數(shù)是關系就是上一個*3等于這個。所以直接把最大值取出來，除以n如果能整除說明是3的冪。不是說明不是。如下圖;

class Solution {
    public boolean isPowerOfThree(int n) {
         return n > 0 && 1162261467 % n == 0;
    }
}

4的冪

題目：給定一個整數(shù) (32 位有符號整數(shù))，請編寫一個函數(shù)來判斷它是否是 4 的冪次方。

示例 1:
輸入: 16
輸出: true
示例 2:
輸入: 5
輸出: false
進階：
你能不使用循環(huán)或者遞歸來完成本題嗎？

思路：對于進階要求我想說一句：我不能。這幾道題真的是惡心他媽給惡心開門，惡心到家了！我是真的有點反感這幾道題。我也懶得看什么思路了，直接暴力列舉法

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;
    }
}

下一題。

反轉字符串

題目：編寫一個函數(shù)，其作用是將輸入的字符串反轉過來。輸入字符串以字符數(shù)組 char[] 的形式給出。不要給另外的數(shù)組分配額外的空間，你必須原地修改輸入數(shù)組、使用 O(1) 的額外空間解決這一問題。你可以假設數(shù)組中的所有字符都是 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"]

這道題乍一看好像很簡單啊。不就是數(shù)組第一個字符和最后一個字符交換，第二個和倒數(shù)第二個么？我先去擼代碼看看坑在哪里。
!!!一直到運行完成通過我也沒看出坑在哪里，很詫異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;
        }
    }
}

下一題。

反轉字符串中的元音字母

題目：編寫一個函數(shù)，以字符串作為輸入，反轉該字符串中的元音字母。

示例 1:
輸入: "hello"
輸出: "holle"
示例 2:
輸入: "leetcode"
輸出: "leotcede"
說明:
元音字母不包含字母"y"。

思路：這個題怎么說呢，上道題的進化版。然后因為沒有什么時間復雜度空間復雜度的要求，我就是第一直覺做的，用到了list，先轉化char數(shù)組，然后元音提出來下標存list（根據(jù)list是有序的），最后根據(jù)list把第一個和最后一個下標的元素呼喚，第二個和倒數(shù)第二個互換，以此類推。直接貼代碼：

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

題解提到了用棧，或者雙指針，但是雙指針就要一層一層的循環(huán)，感覺直接 的感官度還不如我這個呢。這道題就算了，下一題。

兩個數(shù)組的交集

題目：給定兩個數(shù)組，編寫一個函數(shù)來計算它們的交集。

示例 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數(shù)組。

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

反正這道題就這樣吧，下一題。

兩個數(shù)的交集2

題目：給定兩個數(shù)組，編寫一個函數(shù)來計算它們的交集。

示例 1:
輸入: nums1 = [1,2,2,1], nums2 = [2,2]
輸出: [2,2]
示例 2:
輸入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
輸出: [4,9]
說明：
輸出結果中每個元素出現(xiàn)的次數(shù)，應與元素在兩個數(shù)組中出現(xiàn)的次數(shù)一致。
我們可以不考慮輸出結果的順序。
進階:
如果給定的數(shù)組已經(jīng)排好序呢？你將如何優(yōu)化你的算法？
如果 nums1 的大小比 nums2 小很多，哪種方法更優(yōu)？
如果 nums2 的元素存儲在磁盤上，磁盤內(nèi)存是有限的，并且你不能一次加載所有的元素到內(nèi)存中，你該怎么辦？

思路：這道題就是上一道題的進化版，先說單純的實現(xiàn),就是把上一個用set換成list就可以解決這個可以有重復的問題（我就不寫代碼了，沒必要）。這個題的亮點應該是進階的幾個要求
一點點說這個進階要求：
1.如果已經(jīng)排好序了，可以兩個數(shù)組比較了，每次小的那個往前挪動，直到相等或者小的那個挪的比另一個大了。然后相等的存起來。存list，因為允許重復。
因為這個沒有測試案例，所以腦補吧，我就不敲代碼了。
2.nums1比2小。則1作為存map的數(shù)組，這樣每次判斷key是否存在消耗小。
3.這就到了我知識盲區(qū)了，完全不懂。
接下來我去看看題解了：
好吧，前兩頁看來，沒有第三個硬盤的問題的解決辦法。至于第一個第二個我因為是分別的問題，但是沒想到是和的關系。
在有序的前提下，1比2數(shù)組長度小，可以用什么二分法或者雙指針。
今天太晚了，就記錄到這里。
如果稍微幫到你了記得點個喜歡點個關注，明天周一，祝大家新的一周工作順順利利~！