【Java】基础算法练习题

爱被打了一巴掌 2024-04-17 10:20 86阅读 0赞

![在这里插入图片描述][8d8e0d8a542946af858489a536162608.gif_pic_center]

> 个人简介：Java领域新星创作者；阿里云技术博主、星级博主、专家博主；正在Java学习的路上摸爬滚打，记录学习的过程~  
> 个人主页：[.29.的博客][.29.]  
> 学习社区：[进去逛一逛~][Link 1]

> [![在这里插入图片描述][c664fe9835bc4e728f15c7539d868c09.png_pic_center]][c664fe9835bc4e728f15c7539d868c09.png_pic_center 1]

#### 目录 ####

*  基础算法练习题
 *   *  ?1. 两数之和
     *  ?13. 罗马数字转整数
     *  ?26. 删除有序数组中的重复项
     *  ?2022. 将一维数组转变成二维数组
     *  ?LCR 158. 库存管理 II
     *  ?88. 合并两个有序数组
     *  ?704. 二分查找
     *  ?69. x 的平方根
     *  ?118. 杨辉三角
     *  ?125. 验证回文串
     *  ?344. 反转字符串
     *  ?191. 位1的个数
     *  ?326. 3 的幂
     *  ?204. 计数质数
     *  ?2427. 公因子的数目
     *  ?1979. 找出数组的最大公约数
     *  ?1984. 学生分数的最小差值

--------------------

## 基础算法练习题 ##

### ?1. 两数之和 ###

⚪[点击跳转：1. 两数之和][1.]

> 给定一个整数数组 `nums` 和一个整数目标值 `target`，请你在该数组中找出 **和为目标值** *`target`* 的那 **两个** 整数，并返回它们的数组下标。
> 
> 你可以假设每种输入只会对应一个答案。但是，数组中同一个元素在答案里不能重复出现。
> 
> 你可以按任意顺序返回答案。
> 
> **示例 1：**
> 
>     输入：nums = [2,7,11,15], target = 9
>     输出：[0,1]
>     解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 。
> 
> **示例 2：**
> 
>     输入：nums = [3,2,4], target = 6
>     输出：[1,2]
> 
> **示例 3：**
> 
>     输入：nums = [3,3], target = 6
>     输出：[0,1]
> 
> **提示：**
> 
>  *  `2 <= nums.length <= 104`
>  *  `-109 <= nums[i] <= 109`
>  *  `-109 <= target <= 109`
>  *  **只会存在一个有效答案**

`通过哈希表实现比较，操作哈希表的开销接近O(1)`：

class Solution {
        
        public int[] twoSum(int[] nums, int target) {
        
            Map<Integer, Integer> map = new HashMap<>();
    
            for(int i = 0;i < nums.length; ++i){
        
                map.put(nums[i], i);
            }
    
            for(int i = 0;i < nums.length; ++i){
        
                int key = target - nums[i];
                if(map.containsKey(key) && map.get(key) != i){
        
                    return new int[]{
        i, map.get(key)};
                }
            }
    
            return null;
        }
    }

--------------------

### ?13. 罗马数字转整数 ###

[⚪点击跳转：13. 罗马数字转整数][13.]

> 罗马数字包含以下七种字符: `I`， `V`， `X`， `L`，`C`，`D` 和 `M`。
> 
>     字符          数值
>     I             1
>     V             5
>     X             10
>     L             50
>     C             100
>     D             500
>     M             1000
> 
> 例如， 罗马数字 `2` 写做 `II` ，即为两个并列的 1 。`12` 写做 `XII` ，即为 `X` \+ `II` 。 `27` 写做 `XXVII`, 即为 `XX` \+ `V` \+ `II` 。
> 
> 通常情况下，罗马数字中小的数字在大的数字的右边。但也存在特例，例如 4 不写做 `IIII`，而是 `IV`。数字 1 在数字 5 的左边，所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地，数字 9 表示为 `IX`。这个特殊的规则只适用于以下六种情况：
> 
>  *  `I` 可以放在 `V` (5) 和 `X` (10) 的左边，来表示 4 和 9。
>  *  `X` 可以放在 `L` (50) 和 `C` (100) 的左边，来表示 40 和 90。
>  *  `C` 可以放在 `D` (500) 和 `M` (1000) 的左边，来表示 400 和 900。
> 
> 给定一个罗马数字，将其转换成整数。
> 
> **示例 1:**
> 
>     输入: s = "III"
>     输出: 3
> 
> **示例 2:**
> 
>     输入: s = "IV"
>     输出: 4
> 
> **示例 3:**
> 
>     输入: s = "IX"
>     输出: 9
> 
> **示例 4:**
> 
>     输入: s = "LVIII"
>     输出: 58
>     解释: L = 50, V= 5, III = 3.
> 
> **示例 5:**
> 
>     输入: s = "MCMXCIV"
>     输出: 1994
>     解释: M = 1000, CM = 900, XC = 90, IV = 4.
> 
> **提示：**
> 
>  *  `1 <= s.length <= 15`
>  *  `s` 仅含字符 `('I', 'V', 'X', 'L', 'C', 'D', 'M')`
>  *  题目数据保证 `s` 是一个有效的罗马数字，且表示整数在范围 `[1, 3999]` 内
>  *  题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
>  *  IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。

`自己想的，菜`：

class Solution {
        
        public int romanToInt(String s) {
        
            Map<Character, Integer> cMap = new HashMap<>();
            Map<String, Integer> sMap = new HashMap<>();
            int ans = 0;
    
            cMap.put('I', 1);
            cMap.put('V', 5);
            cMap.put('X', 10);
            cMap.put('L', 50);
            cMap.put('C', 100);
            cMap.put('D', 500);
            cMap.put('M', 1000);
    
            sMap.put("IV", 4);
            sMap.put("IX", 9);
            sMap.put("XL", 40);
            sMap.put("XC", 90);
            sMap.put("CD", 400);
            sMap.put("CM", 900);
    
            char[] arr = s.toCharArray();
    
            for(int i = 0;i < arr.length; ++i){
        
                if(i + 1 != arr.length && sMap.containsKey("" + arr[i] + arr[i + 1])){
        
                    ans += sMap.get("" + arr[i] + arr[i + 1]);
                    ++i;
                }else{
        
                    ans += cMap.get(arr[i]);
                }
            }
    
            return ans;
    
        }
    }

`优质解答`：

class Solution {
        
        public int romanToInt(String s) {
        
    
            int ans = 0;
            int preNum = getNum(s.charAt(0));
            for(int i = 1;i < s.length(); ++i){
        
                int num = getNum(s.charAt(i));
                if(preNum < num){
        
                    ans -= preNum;
                }else{
        
                    ans += preNum;
                }
                preNum = num;
            }
    
            return ans + preNum;
        }
    
        public int getNum(char c){
        
            switch(c){
        
                case 'I': return 1;
                case 'V': return 5;
                case 'X': return 10;
                case 'L': return 50;
                case 'C': return 100;
                case 'D': return 500;
                case 'M': return 1000;
                default: return 0;
            }
        }
    }

--------------------

### ?26. 删除有序数组中的重复项 ###

[⚪点击跳转：26. 删除有序数组中的重复项][26.]

> 给你一个 **非严格递增排列** 的数组 `nums` ，请你\*\*[ 原地][Link 2]\*\* 删除重复出现的元素，使每个元素 **只出现一次** ，返回删除后数组的新长度。元素的 **相对顺序** 应该保持 **一致** 。然后返回 `nums` 中唯一元素的个数。
> 
> 考虑 `nums` 的唯一元素的数量为 `k` ，你需要做以下事情确保你的题解可以被通过：
> 
>  *  更改数组 `nums` ，使 `nums` 的前 `k` 个元素包含唯一元素，并按照它们最初在 `nums` 中出现的顺序排列。`nums` 的其余元素与 `nums` 的大小不重要。
>  *  返回 `k` 。
> 
> **判题标准:**
> 
> 系统会用下面的代码来测试你的题解:
> 
>     int[] nums = [...]; // 输入数组
>     int[] expectedNums = [...]; // 长度正确的期望答案
>     
>     int k = removeDuplicates(nums); // 调用
>     
>     assert k == expectedNums.length;
>     for (int i = 0; i < k; i++) {
>         assert nums[i] == expectedNums[i];
>     }
> 
> 如果所有断言都通过，那么您的题解将被 **通过**。
> 
> **示例 1：**
> 
>     输入：nums = [1,1,2]
>     输出：2, nums = [1,2,_]
>     解释：函数应该返回新的长度 2 ，并且原数组 nums 的前两个元素被修改为 1, 2 。不需要考虑数组中超出新长度后面的元素。
> 
> **示例 2：**
> 
>     输入：nums = [0,0,1,1,1,2,2,3,3,4]
>     输出：5, nums = [0,1,2,3,4]
>     解释：函数应该返回新的长度 5 ， 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4 。不需要考虑数组中超出新长度后面的元素。
> 
> **提示：**
> 
>  *  `1 <= nums.length <= 3 * 104`
>  *  `-104 <= nums[i] <= 104`
>  *  `nums` 已按 **非严格递增** 排列

`哈希表`

class Solution {
        
        public int removeDuplicates(int[] nums) {
        
            Map<Integer, Integer> map = new HashMap<>();
            int index = 0;
    
            for(int num : nums){
        
                if(!map.containsKey(num)){
        
                    map.put(num, index++);
                }
            }
    
            for(Map.Entry<Integer,Integer> entry : map.entrySet()){
        
                nums[entry.getValue()] = entry.getKey();
            }
    
            return map.size();
        }
    }

`双指针`：

class Solution {
        
        public int removeDuplicates(int[] nums) {
        
            int p = 0;
            int q = 1;
    
            while(q < nums.length){
        
                if(nums[q] != nums[p]){
        
                    if(q - p >= 1){
        
                        nums[p + 1] = nums[q];
                        ++p;
                    }
                }
                ++q;
            }
    
            return p + 1;
        }
    }

--------------------

### ?2022. 将一维数组转变成二维数组 ###

[⚪点击跳转：2022. 将一维数组转变成二维数组][2022.]

> 给你一个下标从 **0** 开始的一维整数数组 `original` 和两个整数 `m` 和 `n` 。你需要使用 `original` 中 **所有** 元素创建一个 `m` 行 `n` 列的二维数组。
> 
> `original` 中下标从 `0` 到 `n - 1` （都 **包含** ）的元素构成二维数组的第一行，下标从 `n` 到 `2 * n - 1` （都 **包含** ）的元素构成二维数组的第二行，依此类推。
> 
> 请你根据上述过程返回一个 `m x n` 的二维数组。如果无法构成这样的二维数组，请你返回一个空的二维数组。
> 
> **示例 1：**
> 
> ![img][]
> 
>     输入：original = [1,2,3,4], m = 2, n = 2
>     输出：[[1,2],[3,4]]
>     解释：
>     构造出的二维数组应该包含 2 行 2 列。
>     original 中第一个 n=2 的部分为 [1,2] ，构成二维数组的第一行。
>     original 中第二个 n=2 的部分为 [3,4] ，构成二维数组的第二行。
> 
> **示例 2：**
> 
>     输入：original = [1,2,3], m = 1, n = 3
>     输出：[[1,2,3]]
>     解释：
>     构造出的二维数组应该包含 1 行 3 列。
>     将 original 中所有三个元素放入第一行中，构成要求的二维数组。
> 
> **示例 3：**
> 
>     输入：original = [1,2], m = 1, n = 1
>     输出：[]
>     解释：
>     original 中有 2 个元素。
>     无法将 2 个元素放入到一个 1x1 的二维数组中，所以返回一个空的二维数组。
> 
> **示例 4：**
> 
>     输入：original = [3], m = 1, n = 2
>     输出：[]
>     解释：
>     original 中只有 1 个元素。
>     无法将 1 个元素放满一个 1x2 的二维数组，所以返回一个空的二维数组。
> 
> **提示：**
> 
>  *  `1 <= original.length <= 5 * 104`
>  *  `1 <= original[i] <= 105`
>  *  `1 <= m, n <= 4 * 104`

`解答`：

class Solution {
        
        public int[][] construct2DArray(int[] original, int m, int n) {
        
            int[][] ans = new int[][]{
        };
            int length = original.length;
    
            if(length != m * n) return ans;
    
            int index = 0;
            ans = new int[m][n];
    
    
            for(int i = 0;i < m; ++i){
        
                for(int j = 0;j < n; ++j){
        
                    ans[i][j] = original[index++];
                }
            }
    
            return ans;
        }
    }

### ?LCR 158. 库存管理 II ###

[⚪点击跳转：LCR 158. 库存管理 II][LCR 158. _ II]

> 仓库管理员以数组 `stock` 形式记录商品库存表。`stock[i]` 表示商品 `id`，可能存在重复。请返回库存表中数量大于 `stock.length / 2` 的商品 `id`。
> 
> **示例 1:**
> 
>     输入: stock = [6, 1, 3, 1, 1, 1]
>     输出: 1
> 
> **限制：**
> 
>  *  `1 <= stock.length <= 50000`
>  *  给定数组为非空数组，且存在结果数字

`哈希表`：

class Solution {
        
        public int inventoryManagement(int[] stock) {
        
            Map<Integer, Integer> map = new HashMap<>();
            int ans = -1;
    
            for(int num : stock){
        
                if(!map.containsKey(num)){
        
                    map.put(num, 1);
                }else{
        
                    map.put(num, map.get(num) + 1);
                }
            }
    
            for(Map.Entry<Integer, Integer> entry : map.entrySet()){
        
                int key = entry.getKey();
                int value = entry.getValue();
                if(value > stock.length / 2){
        
                    ans = key;
                }
            }
    
            return ans;
        }
    }

`排序求众数`：

class Solution {
        
        public int inventoryManagement(int[] stock) {
        
            Arrays.sort(stock);
            return stock[stock.length / 2];
        }
    }

--------------------

### ?88. 合并两个有序数组 ###

[⚪点击跳转：88. 合并两个有序数组][88.]

> 给你两个按 **非递减顺序** 排列的整数数组 `nums1` 和 `nums2`，另有两个整数 `m` 和 `n` ，分别表示 `nums1` 和 `nums2` 中的元素数目。
> 
> 请你 **合并** `nums2` 到 `nums1` 中，使合并后的数组同样按 **非递减顺序** 排列。
> 
> \*\*注意：\*\*最终，合并后数组不应由函数返回，而是存储在数组 `nums1` 中。为了应对这种情况，`nums1` 的初始长度为 `m + n`，其中前 `m` 个元素表示应合并的元素，后 `n` 个元素为 `0` ，应忽略。`nums2` 的长度为 `n` 。
> 
> **示例 1：**
> 
>     输入：nums1 = [1,2,3,0,0,0], m = 3, nums2 = [2,5,6], n = 3
>     输出：[1,2,2,3,5,6]
>     解释：需要合并 [1,2,3] 和 [2,5,6] 。
>     合并结果是 [1,2,2,3,5,6] ，其中斜体加粗标注的为 nums1 中的元素。
> 
> **示例 2：**
> 
>     输入：nums1 = [1], m = 1, nums2 = [], n = 0
>     输出：[1]
>     解释：需要合并 [1] 和 [] 。
>     合并结果是 [1] 。
> 
> **示例 3：**
> 
>     输入：nums1 = [0], m = 0, nums2 = [1], n = 1
>     输出：[1]
>     解释：需要合并的数组是 [] 和 [1] 。
>     合并结果是 [1] 。
>     注意，因为 m = 0 ，所以 nums1 中没有元素。nums1 中仅存的 0 仅仅是为了确保合并结果可以顺利存放到 nums1 中。
> 
> **提示：**
> 
>  *  `nums1.length == m + n`
>  *  `nums2.length == n`
>  *  `0 <= m, n <= 200`
>  *  `1 <= m + n <= 200`
>  *  `-109 <= nums1[i], nums2[j] <= 109`

`解答`：

class Solution {
        
        public void merge(int[] nums1, int m, int[] nums2, int n) {
        
            int help[] = new int[m + n];
            int p1 = 0;
            int p2 = 0;
            int i = 0;
    
            while(p1 < m && p2 < n){
        
                help[i++] = nums1[p1] <= nums2[p2] ? nums1[p1++] : nums2[p2++];
            }
            while(p1 < m) help[i++] = nums1[p1++];
            while(p2 < n) help[i++] = nums2[p2++];
    
            for(i = 0;i < help.length; ++i){
        
                nums1[i] = help[i];
            }
        }
    }

--------------------

### ?704. 二分查找 ###

[⚪点击跳转：704. 二分查找][704.]

> 给定一个 `n` 个元素有序的（升序）整型数组 `nums` 和一个目标值 `target` ，写一个函数搜索 `nums` 中的 `target`，如果目标值存在返回下标，否则返回 `-1`。
> 
> **示例 1:**
> 
>     输入: nums = [-1,0,3,5,9,12], target = 9
>     输出: 4
>     解释: 9 出现在 nums 中并且下标为 4
> 
> **示例 2:**
> 
>     输入: nums = [-1,0,3,5,9,12], target = 2
>     输出: -1
>     解释: 2 不存在 nums 中因此返回 -1
> 
> **提示：**
> 
> 1.  你可以假设 `nums` 中的所有元素是不重复的。
> 2.  `n` 将在 `[1, 10000]`之间。
> 3.  `nums` 的每个元素都将在 `[-9999, 9999]`之间。

`二分查找`：

class Solution {
        
        public int search(int[] nums, int target) {
        
            int L = 0;
            int R = nums.length - 1;
            int ans = -1;
            while(L <= R){
        
                int mid = (L+R)/2;
                if(nums[mid] == target){
        
                    ans = mid;
                    break;
                }else if(nums[mid] < target){
        
                    L = mid + 1;
                }else if(nums[mid] > target){
        
                    R = mid - 1;
                }
            }
            
            return ans;
        }
    }

--------------------

### ?69. x 的平方根 ###

[⚪点击跳转：69. x 的平方根 ][69. x _]

> 给你一个非负整数 `x` ，计算并返回 `x` 的 **算术平方根** 。
> 
> 由于返回类型是整数，结果只保留 **整数部分** ，小数部分将被 **舍去 。**
> 
> \*\*注意：\*\*不允许使用任何内置指数函数和算符，例如 `pow(x, 0.5)` 或者 `x ** 0.5` 。
> 
> **示例 1：**
> 
>     输入：x = 4
>     输出：2
> 
> **示例 2：**
> 
>     输入：x = 8
>     输出：2
>     解释：8 的算术平方根是 2.82842..., 由于返回类型是整数，小数部分将被舍去。
> 
> **提示：**
> 
>  *  `0 <= x <= 231 - 1`

`暴力`：

class Solution {
        
        public int mySqrt(int x) {
        
           for(long i=0;;i++){
        
               if(i*i>x){
        
                   return (int)i-1;
               }
           }
        }
    }

`二分`：

class Solution {
        
        public int mySqrt(int x) {
        
            int l = 0;
            int r = x;
            int ans = 0;
            while(l <= r){
        
                int mid = l + ((r - l) >> 1);
                if((long) mid * mid <= x){
        
                    ans = mid;
                    l = mid + 1;
                }else{
        
                    r = mid - 1;
                }
            }
            return ans;
        }
    }

--------------------

### ?118. 杨辉三角 ###

[⚪点击跳转:118. 杨辉三角][118.]

> 给定一个非负整数 \*`numRows`，\*生成「杨辉三角」的前 *`numRows`* 行。
> 
> 在「杨辉三角」中，每个数是它左上方和右上方的数的和。
> 
> ![img][img 1]
> 
> **示例 1:**
> 
>     输入: numRows = 5
>     输出: [[1],[1,1],[1,2,1],[1,3,3,1],[1,4,6,4,1]]
> 
> **示例 2:**
> 
>     输入: numRows = 1
>     输出: [[1]]
> 
> **提示:**
> 
>  *  `1 <= numRows <= 30`

`题解`：

class Solution {
        
        public List<List<Integer>> generate(int numRows) {
        
            List<List<Integer>> ans = new ArrayList<>();
            for(int i = 0;i < numRows; ++i){
        
                List<Integer> list = new ArrayList<>();
                for(int j = 0;j <= i; ++j){
        
                    if(j == 0 || j == i){
        
                        list.add(1);
                    }else{
        
                        list.add(ans.get(i - 1).get(j) + ans.get(i - 1).get(j - 1));
                    }
                }
                ans.add(list);
            }
            return ans;
            
        }
    }

--------------------

### ?125. 验证回文串 ###

[⚪点击跳转:125. 验证回文串][125.]

> 如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 **回文串** 。
> 
> 字母和数字都属于字母数字字符。
> 
> 给你一个字符串 `s`，如果它是 **回文串** ，返回 `true` ；否则，返回 `false` 。
> 
> **示例 1：**
> 
>     输入: s = "A man, a plan, a canal: Panama"
>     输出：true
>     解释："amanaplanacanalpanama" 是回文串。
> 
> **示例 2：**
> 
>     输入：s = "race a car"
>     输出：false
>     解释："raceacar" 不是回文串。
> 
> **示例 3：**
> 
>     输入：s = " "
>     输出：true
>     解释：在移除非字母数字字符之后，s 是一个空字符串 "" 。
>     由于空字符串正着反着读都一样，所以是回文串。
> 
> **提示：**
> 
>  *  `1 <= s.length <= 2 * 105`
>  *  `s` 仅由可打印的 ASCII 字符组成

`使用StringBuilder API`：

class Solution {
        
        public boolean isPalindrome(String s) {
        
            StringBuilder sb = new StringBuilder();
            for(int i = 0;i < s.length(); ++i){
        
                char c = s.charAt(i);
                if(Character.isLetterOrDigit(c)){
        
                    sb.append(Character.toLowerCase(c));
                }
            }
            StringBuilder sb_r = new StringBuilder(sb).reverse();
            return sb.toString().equals(sb_r.toString());
        }
    }

--------------------

### ?344. 反转字符串 ###

[⚪点击跳转：344. 反转字符串][344.]

> 编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 `s` 的形式给出。
> 
> 不要给另外的数组分配额外的空间，你必须\*\*[原地][Link 3]修改输入数组\*\*、使用 O(1) 的额外空间解决这一问题。
> 
> **示例 1：**
> 
>     输入：s = ["h","e","l","l","o"]
>     输出：["o","l","l","e","h"]
> 
> **示例 2：**
> 
>     输入：s = ["H","a","n","n","a","h"]
>     输出：["h","a","n","n","a","H"]
> 
> **提示：**
> 
>  *  `1 <= s.length <= 105`
>  *  `s[i]` 都是 [ASCII][] 码表中的可打印字符

`双指针`：

class Solution {
        
        public void reverseString(char[] s) {
        
            if(s.length < 2) return;
            for(int i = 0;i < s.length / 2; ++i){
        
                swap(s, i, s.length - 1 - i);
            }
        }
    
        public void swap(char[] arr, int a, int b){
        
            char temp = arr[a];
            arr[a] = arr[b];
            arr[b] = temp;
        }
    }

--------------------

### ?191. 位1的个数 ###

[⚪点击跳转：191. 位1的个数][191. _1]

> 编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为[汉明重量][Link 4]）。
> 
> **提示：**
> 
>  *  请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
>  *  在 Java 中，编译器使用[二进制补码][Link 5]记法来表示有符号整数。因此，在 **示例 3** 中，输入表示有符号整数 `-3`。
> 
> **示例 1：**
> 
>     输入：n = 00000000000000000000000000001011
>     输出：3
>     解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。
> 
> **示例 2：**
> 
>     输入：n = 00000000000000000000000010000000
>     输出：1
>     解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。
> 
> **示例 3：**
> 
>     输入：n = 11111111111111111111111111111101
>     输出：31
>     解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。
> 
> **提示：**
> 
>  *  输入必须是长度为 `32` 的 **二进制串** 。

`位运算`：

public class Solution {
        
        // you need to treat n as an unsigned value
        public int hammingWeight(int n) {
        
            int ans = 0;
            for(int i = 0;i < 32; ++i){
        
                if((n & 1) == 1) ans++;
                n >>>= 1;
            }
            return ans;
            
        }
    }

--------------------

### ?326. 3 的幂 ###

[⚪点击跳转：326. 3 的幂][326. 3]

> 给定一个整数，写一个函数来判断它是否是 3 的幂次方。如果是，返回 `true` ；否则，返回 `false` 。
> 
> 整数 `n` 是 3 的幂次方需满足：存在整数 `x` 使得 `n == 3x`
> 
> **示例 1：**
> 
>     输入：n = 27
>     输出：true
> 
> **示例 2：**
> 
>     输入：n = 0
>     输出：false
> 
> **示例 3：**
> 
>     输入：n = 9
>     输出：true
> 
> **示例 4：**
> 
>     输入：n = 45
>     输出：false
> 
> **提示：**
> 
>  *  `-231 <= n <= 231 - 1`

`解答`：

class Solution {
        
        public boolean isPowerOfThree(int n) {
        
            if(n == 1) return true;
            if(n == 0) return false;
            while(true){
        
                if(n % 3 == 0){
        
                    n /= 3;
                    if(n == 1) return true;
                }else{
        
                    return false;
                }
            }
        }
    }

--------------------

### ?204. 计数质数 ###

[⚪点击跳转：204. 计数质数][204.]

> 给定整数 `n` ，返回 *所有小于非负整数 `n` 的质数的数量* 。
> 
> **示例 1：**
> 
>     输入：n = 10
>     输出：4
>     解释：小于 10 的质数一共有 4 个, 它们是 2, 3, 5, 7 。
> 
> **示例 2：**
> 
>     输入：n = 0
>     输出：0
> 
> **示例 3：**
> 
>     输入：n = 1
>     输出：0
> 
> **提示：**
> 
>  *  `0 <= n <= 5 * 106`

`埃氏筛`：

class Solution {
        
        public int countPrimes(int n) {
        
            boolean[] flag = new boolean[n];
            Arrays.fill(flag, true);
            for(int i = 2;i*i < n; ++i){
        
                if(flag[i]){
        
                    for(int j = i * i;j < n; j += i){
        
                        flag[j] = false;
                    }
                }
            }
    
            int ans = 0;
            for(int i = 2;i < n; ++i){
        
                if(flag[i]) ++ans;
            }
    
            return ans;
        }
    }

--------------------

### ?2427. 公因子的数目 ###

[⚪点击跳转:2427. 公因子的数目][2427.]

> 给你两个正整数 `a` 和 `b` ，返回 `a` 和 `b` 的 **公** 因子的数目。
> 
> 如果 `x` 可以同时整除 `a` 和 `b` ，则认为 `x` 是 `a` 和 `b` 的一个 **公因子** 。
> 
> **示例 1：**
> 
>     输入：a = 12, b = 6
>     输出：4
>     解释：12 和 6 的公因子是 1、2、3、6 。
> 
> **示例 2：**
> 
>     输入：a = 25, b = 30
>     输出：2
>     解释：25 和 30 的公因子是 1、5 。
> 
> **提示：**
> 
>  *  `1 <= a, b <= 1000`

`暴力`：

class Solution {
        
        public int commonFactors(int a, int b) {
        
            int min = a > b ? b: a;
            int ans = 0;
            for(int i = 1;i <= min; ++i){
        
                if(a % i == 0 && b % i == 0) ans++;
            }
            return ans;
        }
    }

--------------------

### ?1979. 找出数组的最大公约数 ###

[⚪点击跳转：1979. 找出数组的最大公约数][1979.]

> 给你一个整数数组 `nums` ，返回数组中最大数和最小数的 **最大公约数** 。
> 
> 两个数的 **最大公约数** 是能够被两个数整除的最大正整数。
> 
> **示例 1：**
> 
>     输入：nums = [2,5,6,9,10]
>     输出：2
>     解释：
>     nums 中最小的数是 2
>     nums 中最大的数是 10
>     2 和 10 的最大公约数是 2
> 
> **示例 2：**
> 
>     输入：nums = [7,5,6,8,3]
>     输出：1
>     解释：
>     nums 中最小的数是 3
>     nums 中最大的数是 8
>     3 和 8 的最大公约数是 1
> 
> **示例 3：**
> 
>     输入：nums = [3,3]
>     输出：3
>     解释：
>     nums 中最小的数是 3
>     nums 中最大的数是 3
>     3 和 3 的最大公约数是 3
> 
> **提示：**
> 
>  *  `2 <= nums.length <= 1000`
>  *  `1 <= nums[i] <= 1000`

`一次遍历 + 辗转相除`

class Solution {
        
        public int findGCD(int[] nums) {
        
            int min = Integer.MAX_VALUE;
            int max = Integer.MIN_VALUE;
            for(int i = 0;i < nums.length; ++i){
        
                if(nums[i] < min) min = nums[i];
                if(nums[i] > max) max = nums[i];
            }
    
            return GCD(max, min);
        }
    
        //辗转相除法
        public int GCD(int a, int b){
        
            return b == 0 ? a : GCD(b, a%b);
        }
    }

--------------------

### ?1984. 学生分数的最小差值 ###

[⚪点击跳转：1984. 学生分数的最小差值][1984.]

> 给你一个 **下标从 0 开始** 的整数数组 `nums` ，其中 `nums[i]` 表示第 `i` 名学生的分数。另给你一个整数 `k` 。
> 
> 从数组中选出任意 `k` 名学生的分数，使这 `k` 个分数间 **最高分** 和 **最低分** 的 **差值** 达到 **最小化** 。
> 
> 返回可能的 **最小差值** 。
> 
> **示例 1：**
> 
>     输入：nums = [90], k = 1
>     输出：0
>     解释：选出 1 名学生的分数，仅有 1 种方法：
>     - [90] 最高分和最低分之间的差值是 90 - 90 = 0
>     可能的最小差值是 0
> 
> **示例 2：**
> 
>     输入：nums = [9,4,1,7], k = 2
>     输出：2
>     解释：选出 2 名学生的分数，有 6 种方法：
>     - [9,4,1,7] 最高分和最低分之间的差值是 9 - 4 = 5
>     - [9,4,1,7] 最高分和最低分之间的差值是 9 - 1 = 8
>     - [9,4,1,7] 最高分和最低分之间的差值是 9 - 7 = 2
>     - [9,4,1,7] 最高分和最低分之间的差值是 4 - 1 = 3
>     - [9,4,1,7] 最高分和最低分之间的差值是 7 - 4 = 3
>     - [9,4,1,7] 最高分和最低分之间的差值是 7 - 1 = 6
>     可能的最小差值是 2
> 
> **提示：**
> 
>  *  `1 <= k <= nums.length <= 1000`
>  *  `0 <= nums[i] <= 105`

`题解`：

class Solution {
        
        public int minimumDifference(int[] nums, int k) {
        
            Arrays.sort(nums);
            if(k == 1) return 0;
            int n = nums.length;
            int min=Integer.MAX_VALUE;
            for(int i=0;i<=n-k;i++){
        
                if((nums[i+k-1]-nums[i])<min){
        
                    min=nums[i+k-1]-nums[i];
                }
            }
            return min;
        }
    }

--------------------

[![在这里插入图片描述][20a7f1b58dfb4660b75d7f021c157d57.png_pic_center]][20a7f1b58dfb4660b75d7f021c157d57.png_pic_center 1]

[8d8e0d8a542946af858489a536162608.gif_pic_center]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/97f3f78130a1496ebe0677a46c179a7f.gif
[.29.]: https://blog.csdn.net/ebb29bbe?spm=1018.2226.3001.5343
[Link 1]: https://bbs.csdn.net/forums/185241f773fb401b8ca7994dc3d02333?joinKey=cyru4ex9o7wq-mz6v1koj5x-1-add3ae8dc3827dbbd4360c79af92bbbe
[c664fe9835bc4e728f15c7539d868c09.png_pic_center]: https://img-blog.csdnimg.cn/c664fe9835bc4e728f15c7539d868c09.png#pic_center
[c664fe9835bc4e728f15c7539d868c09.png_pic_center 1]: https://blog.csdn.net/ebb29bbe/category_12007200.html?spm=1001.2014.3001.5482
[1.]: https://leetcode.cn/problems/two-sum/
[13.]: https://leetcode.cn/problems/roman-to-integer/
[26.]: https://leetcode.cn/problems/remove-duplicates-from-sorted-array/
[Link 2]: http://baike.baidu.com/item/%E5%8E%9F%E5%9C%B0%E7%AE%97%E6%B3%95
[2022.]: https://leetcode.cn/problems/convert-1d-array-into-2d-array/
[img]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/b3f1b539f06145e58254f8d7a04b490c.png
[LCR 158. _ II]: https://leetcode.cn/problems/shu-zu-zhong-chu-xian-ci-shu-chao-guo-yi-ban-de-shu-zi-lcof/
[88.]: https://leetcode.cn/problems/merge-sorted-array/
[704.]: https://leetcode.cn/problems/binary-search/
[69. x _]: https://leetcode.cn/problems/sqrtx/
[118.]: https://leetcode.cn/problems/pascals-triangle/
[img 1]: https://image.dandelioncloud.cn/pgy_files/images/2024/04/14/55162572fb4a4bce816f9b90d1fa76a0.gif
[125.]: https://leetcode.cn/problems/valid-palindrome/
[344.]: https://leetcode.cn/problems/reverse-string/
[Link 3]: https://baike.baidu.com/item/%E5%8E%9F%E5%9C%B0%E7%AE%97%E6%B3%95
[ASCII]: https://baike.baidu.com/item/ASCII
[191. _1]: https://leetcode.cn/problems/number-of-1-bits/
[Link 4]: https://baike.baidu.com/item/%E6%B1%89%E6%98%8E%E9%87%8D%E9%87%8F
[Link 5]: https://baike.baidu.com/item/%E4%BA%8C%E8%BF%9B%E5%88%B6%E8%A1%A5%E7%A0%81/5295284
[326. 3]: https://leetcode.cn/problems/power-of-three/
[204.]: https://leetcode.cn/problems/count-primes/
[2427.]: https://leetcode.cn/problems/number-of-common-factors/
[1979.]: https://leetcode.cn/problems/find-greatest-common-divisor-of-array/
[1984.]: https://leetcode.cn/problems/minimum-difference-between-highest-and-lowest-of-k-scores/
[20a7f1b58dfb4660b75d7f021c157d57.png_pic_center]: https://img-blog.csdnimg.cn/20a7f1b58dfb4660b75d7f021c157d57.png#pic_center
[20a7f1b58dfb4660b75d7f021c157d57.png_pic_center 1]: https://blog.csdn.net/ebb29bbe?type=blog