【Java】基础算法练习题
基础算法练习题
🚀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. 罗马数字转整数
罗马数字包含以下七种字符: 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. 删除有序数组中的重复项
给你一个 非严格递增排列 的数组 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. 将一维数组转变成二维数组
给你一个下标从 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
仓库管理员以数组 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. 合并两个有序数组
给你两个按 非递减顺序 排列的整数数组 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. 二分查找
给定一个 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 的平方根
给你一个非负整数 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. 杨辉三角
给定一个非负整数 *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. 验证回文串
如果在将所有大写字符转换为小写字符、并移除所有非字母数字字符之后，短语正着读和反着读都一样。则可以认为该短语是一个 回文串 。
字母和数字都属于字母数字字符。
给你一个字符串 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. 反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 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的个数
编写一个函数，输入是一个无符号整数（以二进制串的形式），返回其二进制表达式中数字位数为 ‘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 的幂
给定一个整数，写一个函数来判断它是否是 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. 计数质数
给定整数 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. 公因子的数目
给你两个正整数 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. 找出数组的最大公约数
给你一个整数数组 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. 学生分数的最小差值
给你一个 下标从 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;
}
}本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2024-03-02，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录