网站优化是在哪里做修改,wordpress的安装过程,网站类型定位,vps网站管理助手下载2023/11/30
力扣每日一刷#xff1a;1.两数之和 给定一个整数数组 nums 和一个整数目标值 target#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数#xff0c;并返回它们的数组下标。 你可以假设每种输入只会对应一个答案。但是#xff0c;数组中同一个元…
2023/11/30
力扣每日一刷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( n ) 优public static int[] twoSum(int[] nums, int target) {//定义一个变量存放数组长度int len nums.length;//定义一个哈希表对应的Key —— Value分别指Key-数组中的数值 Value-该值对应的数组下标MapInteger,Integer map new HashMap(len-1);//循环该数组for(int i 0; ilen;i){//如果在哈希表中存在符合要求目标值-当前遍历的值的值则返回该值对应的Value数组下标与当前遍历的值的数组下标组成的新数组if (map.containsKey(target-nums[i])) {return new int[]{i,map.get(target-nums[i])};}//如果哈希表中没有符合要求的值则将当前遍历的值存放进哈希表map.put(nums[i],i);} throw new IllegalArgumentException(数组中没有两数和为目标值);}//暴力枚举 时间复杂度 O( n^2 )public int[] twoSum2(int[] nums, int target) {int len nums.length;//暴力递归for(int i0; i len-1; i){int x nums[i];for(int j i 1;j len; j){int y nums[j];if(x y target){return new int[]{i,j};}}}throw new IllegalArgumentException(数组中没有两数和为目标值);}文字题解 方法一暴力枚举 思路及算法 最容易想到的方法是枚举数组中的每一个数 x寻找数组中是否存在 target - x。 当我们使用遍历整个数组的方式寻找 target - x 时需要注意到每一个位于 x 之前的元素都已经和 x 匹配过因此不需要再进行匹配。而每一个元素不能被使用两次所以我们只需要在 x 后面的元素中寻找 target - x。 方法二哈希表 思路及算法 注意到方法一的时间复杂度较高的原因是寻找 target - x 的时间复杂度过高。因此我们需要一种更优秀的方法能够快速寻找数组中是否存在目标元素。如果存在我们需要找出它的索引。 使用哈希表可以将寻找 target - x 的时间复杂度降低到从 O(N) 降低到 O(1)。 这样我们创建一个哈希表对于每一个 x我们首先查询哈希表中是否存在 target - x然后将 x 插入到哈希表中即可保证不会让 x 和自己匹配。 2023/12/01
力扣每日一刷9.回文数 给你一个整数 x 如果 x 是一个回文整数返回 true 否则返回 false 。 回文数是指正序从左向右和倒序从右向左读都是一样的整数。 例如121 是回文而 123 不是。 示例 1 输入x 121
输出true示例 2 输入x -121
输出false
解释从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。示例 3 输入x 10
输出false
解释从右向左读, 为 01 。因此它不是一个回文数。提示 -231 x 231 - 1 //反转一半数字 优
class Solution {public boolean isPalindrome(int x) {// 特殊情况// 如上所述当 x 0 时x 不是回文数。// 同样地如果数字的最后一位是 0为了使该数字为回文// 则其第一位数字也应该是 0// 只有 0 满足这一属性if (x 0 || (x % 10 0 x ! 0)) {return false;}int revertedNumber 0;while (x revertedNumber) {revertedNumber revertedNumber * 10 x % 10;x / 10;}// 当数字长度为奇数时我们可以通过 revertedNumber/10 去除处于中位的数字。// 例如当输入为 12321 时在 while 循环的末尾我们可以得到 x 12revertedNumber 123// 由于处于中位的数字不影响回文它总是与自己相等所以我们可以简单地将其去除。return x revertedNumber || x revertedNumber / 10;}
}文字题解 方法一反转一半数字 思路 映入脑海的第一个想法是将数字转换为字符串并检查字符串是否为回文。但是这需要额外的非常量空间来创建问题描述中所不允许的字符串。 第二个想法是将数字本身反转然后将反转后的数字与原始数字进行比较如果它们是相同的那么这个数字就是回文。 但是如果反转后的数字大于 int.MAX\text{int.MAX}int.MAX我们将遇到整数溢出问题。 按照第二个想法为了避免数字反转可能导致的溢出问题为什么不考虑只反转 int\text{int}int 数字的一半毕竟如果该数字是回文其后半部分反转后应该与原始数字的前半部分相同。 例如输入 1221我们可以将数字 “1221” 的后半部分从 “21” 反转为 “12”并将其与前半部分 “12” 进行比较因为二者相同我们得知数字 1221 是回文。 算法 首先我们应该处理一些临界情况。所有负数都不可能是回文例如-123 不是回文因为 - 不等于 3。所以我们可以对所有负数返回 false。除了 0 以外所有个位是 0 的数字不可能是回文因为最高位不等于 0。所以我们可以对所有大于 0 且个位是 0 的数字返回 false。 现在让我们来考虑如何反转后半部分的数字。 对于数字 1221如果执行 1221 % 10我们将得到最后一位数字 1要得到倒数第二位数字我们可以先通过除以 10 把最后一位数字从 1221 中移除1221 / 10 122再求出上一步结果除以 10 的余数122 % 10 2就可以得到倒数第二位数字。如果我们把最后一位数字乘以 10再加上倒数第二位数字1 * 10 2 12就得到了我们想要的反转后的数字。如果继续这个过程我们将得到更多位数的反转数字。 现在的问题是我们如何知道反转数字的位数已经达到原始数字位数的一半 由于整个过程我们不断将原始数字除以 10然后给反转后的数字乘上 10所以当原始数字小于或等于反转后的数字时就意味着我们已经处理了一半位数的数字了。 2023/12/02
力扣每日一刷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 。关于罗马数字的详尽书写规则可以参考 罗马数字 - Mathematics 。 //哈希表存数据 优
// 定义一个Map用来存储字符和整数的映射关系static MapCharacter, Integer symbolValues new HashMapCharacter, Integer() {{put(I, 1);put(V, 5);put(X, 10);put(L, 50);put(C, 100);put(D, 500);put(M, 1000);}};// 定义一个函数用来将罗马数字转换为整数public static int romanToInt(String s) {// 定义一个变量ans用来存储转换后的整数int ans 0;// 获取罗马数字的长度int n s.length();// 遍历罗马数字中的每一个字符for (int i 0; i n; i) {// 获取每一个字符对应的整数int value symbolValues.get(s.charAt(i));// 如果当前字符的整数小于下一个字符的整数则减去当前字符的整数if (i n - 1 value symbolValues.get(s.charAt(i 1))) {ans - value;// 否则加上当前字符的整数} else {ans value;}}// 返回转换后的整数return ans;}//暴力模拟
public static int romanToInt2(String s) {int len s.length();int result 0;for(int i0;ilen;i){switch (s.charAt(i)){case I: if(ilen-1 ){result 1;}else if( s.charAt(i1) V || s.charAt(i1) X){result - 1;}else{result 1;}case V:result 5;case X:if(ilen-1 ){result 10;}else if(s.charAt(i1)L || s.charAt(i1)C){result - 10;}else{result 10;}case L:result 50;case C:if(ilen-1 ){result 100;}else if(s.charAt(i1)D || s.charAt(i1)M){result - 100;} else{result 100;}case D: result 500;default:result 1000;}}return result;}2023/12/03
力扣每日一刷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 已按 非严格递增 排列 //暴力解法 不满足题目中原地的要求public static int removeDuplicates(int[] nums) {//定义一个变量len用来存储数组的长度int len nums.length;//定义一个List集合ListInteger list new ArrayList();//遍历数组for(int i0;ilen;i){//如果list集合中不包含当前元素if(!list.contains(nums[i])){//将当前元素添加到list集合中list.add(nums[i]);}}//遍历list集合for(int i0;ilist.size();i){//将list集合中的元素赋值给数组nums[i] list.get(i);}//返回list集合的长度return list.size();}//双指针解法 优public static int removeDuplicates2(int[] nums) {//如果数组为空则返回0if(numsnull){return 0;}//定义两个指针i指向下一个不重复的元素j指向当前元素int len nums.length;int i1;for(int j1;jlen;j){//j指针用来扫描数组i指针指向需要被替换的元素//如果当前元素不等于前一个元素则将当前元素赋值给i指向的位置i自增if(nums[j]!nums[i-1]){nums[i] nums[j];i;}}//返回i的值即不重复元素的数量return i;}class Solution {public int removeDuplicates(int[] nums) {// 数组的长度int n nums.length;// 如果数组为空则返回0if (n 0) {return 0;}// 快慢指针初始值都为1int fast 1, slow 1;// 当快指针小于数组长度时循环while (fast n) {// 如果快指针指向的元素不等于前一个元素if (nums[fast] ! nums[fast - 1]) {// 将快指针指向的元素赋值给慢指针指向的元素nums[slow] nums[fast];// 慢指针加1slow;}// 快指针加1fast;}// 返回慢指针的值return slow;}} 2023/12/04
力扣每日一刷14. 最长公共前缀 编写一个函数来查找字符串数组中的最长公共前缀。 如果不存在公共前缀返回空字符串 。 示例 1 输入strs [flower,flow,flight]
输出fl示例 2 输入strs [dog,racecar,car]
输出
解释输入不存在公共前缀。提示 1 strs.length 2000 strs[i].length 200strs[i] 仅由小写英文字母组成 //横向扫描
public String longestCommonPrefix(String[] strs) {// 判断字符串数组是否为空if(strs null||strs.length0){return ;}// 获取字符串数组的第一个字符串String s1 strs[0];// 获取字符串数组的长度int count strs.length;// 遍历字符串数组for(int i1;icount;i){// 获取两个字符串的最长公共前缀s1 towLongestCommon(s1, strs[i]);// 如果最长公共前缀为空则跳出循环if(s1.isEmpty()){break;}}// 返回最长公共前缀return s1;}private String towLongestCommon(String s1,String s2){// 获取两个字符串的最小长度int min Math.min(s1.length(),s2.length());// 定义索引int index 0;// 遍历两个字符串while (indexmin s1.charAt(index) s2.charAt(index)){index;}// 返回两个字符串的最长公共前缀return s1.substring(0,index);} public String longestCommonPrefix(String[] strs) {// 如果字符串数组为空或者为null则返回空字符串if(strs.length0||strsnull){return ;}// 获取字符串数组中第一个字符串的长度int length strs[0].length();// 获取字符串数组中字符串的数量int count strs.length;// 遍历字符串数组中第一个字符串的每一个字符for(int i0;ilength;i){// 获取字符串数组中第一个字符串的第i个字符char c strs[0].charAt(i);// 遍历字符串数组中剩余的字符串for(int j1;jcount;j){// 获取字符串数组中第j个字符串的第i个字符char c1 strs[j].charAt(i);// 如果字符串数组中第j个字符串的长度小于i或者字符串数组中第j个字符串的第i个字符与第一个字符串的第i个字符不相等则返回第一个字符串的前i个字符if(istrs[j].length() || c!c1){return strs[0].substring(0,i);}}}// 如果遍历完字符串数组中第一个字符串的所有字符没有出现上面的情况则返回第一个字符串return strs[0];//分治算法
class Day5_longestCommonPrefix_3 {public String longestCommonPrefix(String[] strs) {// 获取字符串数组的长度int len strs.length;// 如果字符串数组为空或者长度为0则返回空字符串if (strs null || len 0) {return ;} else {// 否则调用longestCommonPrefix方法传入字符串数组以及起始位置和结束位置return longestCommonPrefix(strs, 0, len - 1);}}private String longestCommonPrefix(String[] strs, int start, int end) {// 如果起始位置等于结束位置则返回该位置的字符串if (start end) {return strs[start];}// 计算中间位置int mid (end - start) / 2 start;// 递归调用longestCommonPrefix方法获取左边字符串的最长公共前缀String left longestCommonPrefix(strs, start, mid);// 递归调用longestCommonPrefix方法获取右边字符串的最长公共前缀String right longestCommonPrefix(strs, mid 1, end);// 返回左右字符串的最长公共前缀return longestCommonPrefix(left,right);}private String longestCommonPrefix(String left,String right){// 获取左右字符串的最小长度int min Math.min(left.length(), right.length());// 遍历最小长度比较左右字符串的每一个字符for (int i 0; i min; i) {// 如果左右字符串的每一个字符不相等则返回从开头到当前字符的字符串if(left.charAt(i)!right.charAt(i)){return left.substring(0,i);}}// 如果左右字符串的每一个字符都相等则返回最小长度长度的字符串return left.substring(0,min);}
}力扣每五日一总结【11/30–12/04】 1.两数之和 哈希表 Key—数组中数的值 Value—当前值对应的数组下标 每次遍历数组中的一个数时从哈希表中查找是否有与当前数和为目标值的数如果有则返回他的Value如果没有将当前数存放到哈希表中。 9.回文数 反转一半数字 先判断满足回文数的条件把不满足回文数条件【负数和个位数为零】的先Pass反转数字计算方法每次将原数%10取个位数加到反转数上将反转数原有的数*10挪出个位数,将原数/10除去已经被加在反转数中的个位数循环结束条件原数反转数判断是否为回文数的条件情况一当原数为偶数—如果反转数直接等于原数则为回文数情况二当原数为奇数—此时反转数比原数多一位需要先将反转数/10去除个位数再与原数比较如果相等则为回文数 13.罗马数组转整数 哈希表存数据 Key—罗马数字 Value—罗马数字对应的值 循环当前罗马字符串依次从哈希表中取出对应的值计算规律如果当前值小于下一个罗马字符对应的值则减去当前值如果大于下一个罗马字符对应的值则加上当前值。 暴力模拟 26. 删除有序数组中的重复项 双指针 定义两个指针一个快指针用于扫描数组中的值一个满指针用于指向待替换元素一旦快指针扫描到的元素与满指针上一元素不同时则将快指针的值赋值给满指针快慢指针均加一如果快指针指向的值等于满指针指向的上一元素则快指针继续扫描满指针不变。 暴力模拟 14. 最长公共前缀 横向扫描 固定数组中的第一个字符串遍历从第二个字符串开始以后的字符串分别与第一个字符串求最长公共前缀把每次求出的最长公共前缀赋值给第一个字符串以此类推。 纵向扫描 固定每个字符串的第一个字符并记录然后开始遍历每个字符串如果每个字符串的第一个字符都相同则比较下一个字符如果不同则使用字符串剪切方法substring返回0当前字符的字符串即为公共前缀。 分治算法 计算一组字符串数组中各个字符串的公共前缀则可以划分为小问题计算两个字符串的公共前缀使用分治思想。使用递归法分别求数组左右部分的最长公共前缀最后输出左右部分的最长公共前缀的公共前缀即为最终答案。 声明以上文字题解为力扣官方题解本人思路均在代码注释以及五日总结中体现更加详细和朴素相比官方题解更易于接受在此感谢力扣官方提供题解拓展思维感谢
