2021-10-22刷題總結

目錄

今日刷題總結

單值二叉樹(easy)

相同的樹(easy)

二進制表示中質數個計算置位(easy)

只出現一次的數(mid)II

補充

今日刷題總結

單值二叉樹(easy)

題目鏈接 ：965. 單值二叉樹 - 力扣（LeetCode） (leetcode-cn.com)

題目描述

如果二叉樹每個節點都具有相同的值，那么該二叉樹就是單值二叉樹，

只有給定的樹是單值二叉樹時，才回傳 true；否則回傳 false，

示例

解題思路

遞回遍歷：用一個布爾型別的輔助函式來完成遞回遍歷，在主函式中把根節點的值 root.val與根節點root傳入輔助函式，讓輔助函式完成遞回 比較，

變數：輔助函式引數 一個整數val 一個節點TreeNode，

代碼

class Solution {
    
    public boolean isUnivalTree(TreeNode root) {
?
        if(root.left == null && root.right == null){
?
            return true;
        }
?
        int val = root.val;
?
        return singleNumber(val,root);
    }
    public boolean singleNumberTree( int val, TreeNode root){
?
        if(root == null){
?
            return true;
        }
?
        if(root.val != val){
            
            return false;
        }
?
        return singleNumber(val,root.left) && singleNumber(val,root.right);
    }
}

相同的樹(easy)

題目鏈接：100. 相同的樹 - 力扣（LeetCode） (leetcode-cn.com)

題目描述

給你兩棵二叉樹的根節點 p 和 q ，撰寫一個函式來檢驗這兩棵樹是否相同，

如果兩個樹在結構上相同，并且節點具有相同的值，則認為它們是相同的，

示例

解題思路

遞回比較：思路很簡單啊這道題，遍歷兩棵樹的每一個節點比較值即可，要注意的地方就是某一個節點為空時，另一個是否為空，

萬能的遞回，哈哈哈哈哈哈又來水題了，

代碼

class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
?
        if(p == null){
?
            return q == null;
?
        }
        if(q == null){
?
            return p == null;
            
        }
        if(p.val != q.val ){
?
            return false;
?
        }
?
        return isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
}

二進制表示中質數個計算置位(easy)

題目鏈接：二進制表示中質數個計算置位

題目描述

給定兩個整數 L和 R，找到閉區間 [L, R] 范圍內，計算置位位數為質數的整數個數，

（注意，計算置位代表二進制表示中1的個數，例如 21 的二進制表示 10101 有 3 個計算置位，還有，1 不是質數，）

示例

輸入: L = 10, R = 15

輸出: 5

解釋:

10 -> 1010 (2 個計算置位, 2 是質數)

11 -> 1011 (3 個計算置位, 3 是質數)

12 -> 1100 (2 個計算置位, 2 是質數)

13 -> 1101 (3 個計算置位, 3 是質數)

14 -> 1110 (3 個計算置位, 3 是質數)

15 -> 1111 (4 個計算置位, 4 不是質數)

注意

1. L, R 是 L <= R 且在 [1, 10^6] 中的整數，

2. R - L 的最大值為 10000，

   ---

解題思路

列舉+位運算：

• 列舉：因為本題L與R范圍在 10 ^ 6 內，故而R的二進制整數表示不超過20位( 2 的 20 次為 1048576 )，故位數中最大大的質數為 19，資料量較少，便可以考慮列舉出 2 - 20 內的質數，

• 位運算：昨天發的文章妙用位運算中便有快速求解一個數中二進制位為1的個數，即 lowbit，

  不知道的小伙伴我可以去看看哦，鏈接放在這里了，

  妙用位運算_

代碼

class Solution {
    public int countPrimeSetBits( int left, int right) {
        int count = 0;
        while( left <= right ) {
            int sum = 0;
            int m = left;
            while(m != 0){
                int c = m & ( -m);
                m -= c;
                sum ++;
                
            }
            left ++;
            count = check(sum) ? count + 1 : count;
        }
        return count;
    }
    public boolean check(int num){
        return num == 2 || num == 3 || num == 5 || num == 7 || num == 11 ||num == 13||num == 17||num == 19;
    }
}

只出現一次的數(mid)II

題目鏈接：只出現一次的數字 II - 提交記錄 - 力扣（LeetCode） (leetcode-cn.com)

題目描述

給你一個整數陣列 nums ，除某個元素僅出現 一次 外，其余每個元素都恰出現 三次 ，請你找出并回傳那個只出現了一次的元素，

示例

?
輸入：nums = [2,2,3,2]
輸出：3
?
輸入：nums = [0,1,0,1,0,1,99]
輸出：99
?

解題思路

哈希表：遍歷該陣列，通過創建哈希表記錄每個數字出現的次數，回傳出現次數為1元素的即可，

位運算：我們知道，如果兩個數不相等，那么他們一定有某幾位二進制數是不相同的，所以我們可以通過記錄陣列中所有數第k位二進制數中1出現的次數count，如果該數在陣列中出現了三次，那么count一定可以被3整除，反之，出現一次的那個數在第k位一定為1，我們只需記錄每一個這樣的k位，把得到的每一個 1 << k 相加即可，

位運算文章：妙用位運算_

代碼

class Solution {
    public int singleNumber(int[] nums) {
        if(nums.length == 1){
            return nums[0];
        }
        int res = 0;
        for(int i =0;i < 32 ;i ++){
            int count = 0;
            for(int item : nums){
                if(( item & 1 << i) == 1<<i){
                    count ++;
                }
            }
            if(count %3 == 1){
                res |= (1 << i);
            }
        }
        return res;
    }
}

補充

今天看了N皇后及其優化問題，果真是初學者的噩夢，不過看完也算是理解了一些遞回特性，長芝士長芝士！！！

好了，今天就先到這里吧（又是水題的一天），明天繼續加油鴨，