淘宝网站的推广方案,做h5的网站有哪些,销售外包服务,友情链接查询工具个人简介#xff1a;Java领域新星创作者#xff1b;阿里云技术博主、星级博主、专家博主#xff1b;正在Java学习的路上摸爬滚打#xff0c;记录学习的过程~ 个人主页#xff1a;.29.的博客 学习社区#xff1a;进去逛一逛~ 目录 基础算法练习题#x1f680;1. 两数之和… 个人简介Java领域新星创作者阿里云技术博主、星级博主、专家博主正在Java学习的路上摸爬滚打记录学习的过程~ 个人主页.29.的博客 学习社区进去逛一逛~ 目录 基础算法练习题1. 两数之和13. 罗马数字转整数26. 删除有序数组中的重复项2022. 将一维数组转变成二维数组LCR 158. 库存管理 II88. 合并两个有序数组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) {MapInteger, 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 LCD 和 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 应该写作 XLIX999 应该写作 CMXCIX 。 自己想的菜
class Solution {public int romanToInt(String s) {MapCharacter, Integer cMap new HashMap();MapString, 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) {MapInteger, Integer map new HashMap();int index 0;for(int num : nums){if(!map.containsKey(num)){map.put(num, index);}}for(Map.EntryInteger,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 中第一个 n2 的部分为 [1,2] 构成二维数组的第一行。
original 中第二个 n2 的部分为 [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) {MapInteger, 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.EntryInteger, 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 (LR)/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 i0;;i){if(i*ix){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 ListListInteger generate(int numRows) {ListListInteger ans new ArrayList();for(int i 0;i numRows; i){ListInteger 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 valuepublic 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 minInteger.MAX_VALUE;for(int i0;in-k;i){if((nums[ik-1]-nums[i])min){minnums[ik-1]-nums[i];}}return min;}
}
