个人简介：Java领域新星创作者；阿里云技术博主、星级博主、专家博主；正在Java学习的路上摸爬滚打，记录学习的过程~
个人主页：.29.的博客
学习社区：进去逛一逛~
目录
- 基础算法练习题
- 🚀1. 两数之和
- 🚀13. 罗马数字转整数
- 🚀26. 删除有序数组中的重复项
- 🚀2022. 将一维数组转变成二维数组
- 🚀LCR 158. 库存管理 II
- 🚀88. 合并两个有序数组
- 🚀704. 二分查找
- 🚀69. x 的平方根
- 🚀118. 杨辉三角
- 🚀125. 验证回文串
- 🚀344. 反转字符串
- 🚀191. 位1的个数
- 🚀326. 3 的幂
- 🚀204. 计数质数
- 🚀2427. 公因子的数目
- 🚀1979. 找出数组的最大公约数
- 🚀1984. 学生分数的最小差值
基础算法练习题
🚀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. 罗马数字转整数
罗马数字包含以下七种字符:
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 <= 15s仅含字符('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. 删除有序数组中的重复项
给你一个 非严格递增排列 的数组
nums，请你** 原地** 删除重复出现的元素，使每个元素 只出现一次 ，返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回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] <= 104nums已按 非严格递增 排列
哈希表
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. 将一维数组转变成二维数组
给你一个下标从 0 开始的一维整数数组
original和两个整数m和n。你需要使用original中 所有 元素创建一个m行n列的二维数组。
original中下标从0到n - 1（都 包含 ）的元素构成二维数组的第一行，下标从n到2 * n - 1（都 包含 ）的元素构成二维数组的第二行，依此类推。请你根据上述过程返回一个
m x n的二维数组。如果无法构成这样的二维数组，请你返回一个空的二维数组。示例 1：
输入：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 * 1041 <= original[i] <= 1051 <= 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
仓库管理员以数组
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. 合并两个有序数组
给你两个按 非递减顺序 排列的整数数组
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 + nnums2.length == n0 <= m, n <= 2001 <= 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. 二分查找
给定一个
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提示：
- 你可以假设
nums中的所有元素是不重复的。n将在[1, 10000]之间。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 的平方根
给你一个非负整数
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. 杨辉三角
给定一个非负整数 *
numRows，*生成「杨辉三角」的前numRows行。在「杨辉三角」中，每个数是它左上方和右上方的数的和。
示例 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. 验证回文串
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串
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 * 105s仅由可打印的 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. 反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组
s的形式给出。不要给另外的数组分配额外的空间，你必须**原地修改输入数组**、使用 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 <= 105s[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的个数
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
提示：
- 请注意，在某些语言（如 Java）中，没有无符号整数类型。在这种情况下，输入和输出都将被指定为有符号整数类型，并且不应影响您的实现，因为无论整数是有符号的还是无符号的，其内部的二进制表示形式都是相同的。
- 在 Java 中，编译器使用二进制补码记法来表示有符号整数。因此，在 示例 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 的幂
给定一个整数，写一个函数来判断它是否是 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. 计数质数
给定整数
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. 公因子的数目
给你两个正整数
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. 找出数组的最大公约数
给你一个整数数组
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 <= 10001 <= 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. 学生分数的最小差值
给你一个 下标从 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 <= 10000 <= 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;
}
}
