51的网站是啥,网站挂马怎么处理,郑州妇科医院排行榜,wordpress评论提交特效目录
第一题
题目来源
题目内容
解决方法
方法一#xff1a;哈希表
方法二#xff1a;逐个判断字符
方法三#xff1a;模拟减法
第二题
题目来源
题目内容
解决方法
方法一#xff1a;水平扫描法
方法二#xff1a;垂直扫描法
方法三#xff1a;分治法
方…目录
第一题
题目来源
题目内容
解决方法
方法一哈希表
方法二逐个判断字符
方法三模拟减法
第二题
题目来源
题目内容
解决方法
方法一水平扫描法
方法二垂直扫描法
方法三分治法
方法四二分查找
第三题
题目来源
题目内容
解决方法
方法一双指针 第一题
题目来源
13. 罗马数字转整数 - 力扣LeetCode
题目内容 解决方法
方法一哈希表
根据题目要求我们需要将给定的罗马数字转换成整数。根据题目中给出的规则我们可以逐个字符判断并累加得到最终的整数表示。
具体的步骤如下
初始化一个变量result为0表示最终的整数结果。遍历给定的罗马数字字符串s从左往右逐个字符判断
如果当前字符的值比下一个字符的值小则需要执行减法操作。根据题目中的特殊规则可以判断当前字符的值是负数。将该负数加到result上并跳过下一个字符。否则直接将当前字符的值加到result上。
返回result作为最终的整数表示。
class Solution {public int romanToInt(String s) {MapCharacter, Integer romanMap new HashMap();romanMap.put(I, 1);romanMap.put(V, 5);romanMap.put(X, 10);romanMap.put(L, 50);romanMap.put(C, 100);romanMap.put(D, 500);romanMap.put(M, 1000);int result 0;for (int i 0; i s.length(); i) {int value romanMap.get(s.charAt(i));if (i s.length() - 1 value romanMap.get(s.charAt(i 1))) {result - value;} else {result value;}}return result;
}}
复杂度分析
时间复杂度O(n)其中n是给定的罗马数字字符串的长度。遍历一次罗马数字字符串每个字符只被访问一次。空间复杂度O(1)。虽然我们使用了一个哈希表来存储罗马数字字符与对应的数值映射关系但是由于罗马数字字符数量有限且固定因此哈希表的大小是恒定不变的可以视为常数级别的空间复杂度。除此之外我们并没有使用任何额外的数据结构。
LeetCode运行结果 方法二逐个判断字符
除了使用哈希表的方法还可以使用逐个判断字符的方法来将罗马数字转换成整数。
具体的步骤如下 初始化一个变量result为0表示最终的整数结果。 遍历给定的罗马数字字符串s从左往右逐个字符判断 如果当前字符是I并且下一个字符是V或X则需要执行减法操作将4或9加到result上并跳过下一个字符。 如果当前字符是X并且下一个字符是L或C则需要执行减法操作将40或90加到result上并跳过下一个字符。 如果当前字符是C并且下一个字符是D或M则需要执行减法操作将400或900加到result上并跳过下一个字符。 否则直接将当前字符的值加到result上。 返回result作为最终的整数表示。
class Solution {public int romanToInt(String s) {int result 0;for (int i 0; i s.length(); i) {char currentChar s.charAt(i);if (currentChar I i s.length() - 1 (s.charAt(i 1) V || s.charAt(i 1) X)) {result - 1;} else if (currentChar X i s.length() - 1 (s.charAt(i 1) L || s.charAt(i 1) C)) {result - 10;} else if (currentChar C i s.length() - 1 (s.charAt(i 1) D || s.charAt(i 1) M)) {result - 100;} else {switch (currentChar) {case I:result 1;break;case V:result 5;break;case X:result 10;break;case L:result 50;break;case C:result 100;break;case D:result 500;break;case M:result 1000;break;default:break;}}}return result;
}}
该算法直接根据题目中的规则进行逐个字符判断并计算最终的整数结果。时间复杂度为O(n)其中n是给定的罗马数字字符串的长度。空间复杂度为O(1)。
LeetCode运行结果 方法三模拟减法
还有一种方法是基于模拟减法的思路来将罗马数字转换成整数。
具体的步骤如下 初始化一个变量result为0表示最终的整数结果。 遍历给定的罗马数字字符串s从左往右逐个字符判断 如果当前字符的值比前一个字符的值大则需要执行减法操作。将两个字符对应的值进行减法操作并将结果加到result上。注意这里要通过减去两倍的前一个字符的值来抵消之前被加上的值。 否则直接将当前字符的值加到result上。 返回result作为最终的整数表示。
class Solution {
public int romanToInt(String s) {MapCharacter, Integer romanMap new HashMap();romanMap.put(I, 1);romanMap.put(V, 5);romanMap.put(X, 10);romanMap.put(L, 50);romanMap.put(C, 100);romanMap.put(D, 500);romanMap.put(M, 1000);int result 0;int prevValue 0;for (int i 0; i s.length(); i) {int value romanMap.get(s.charAt(i));if (value prevValue) {result value - 2 * prevValue;} else {result value;}prevValue value;}return result;
}}
该算法通过模拟减法的操作来计算最终的整数结果。时间复杂度为O(n)其中n是给定的罗马数字字符串的长度。空间复杂度为O(1)。
LeetCode运行结果 第二题
题目来源
14. 最长公共前缀 - 力扣LeetCode
题目内容 解决方法
方法一水平扫描法
可以使用水平扫描法来查找字符串数组中的最长公共前缀。
具体的步骤如下
1、初始化一个空字符串prefix表示最长公共前缀。
2、如果输入的字符串数组为空或长度为0则直接返回空字符串。
3、遍历字符串数组中的第一个字符串strs[0]的每个字符
对于每个字符遍历字符串数组中的其他字符串strs[i]其中i从1到n-1n是字符串数组的长度。如果当前字符在其他字符串的相同位置上的字符不相等或者其他字符串的长度小于等于当前位置则表示不匹配直接返回当前的公共前缀。否则将当前字符添加到prefix中。
4、返回prefix作为最长公共前缀。
class Solution {public String longestCommonPrefix(String[] strs) {if (strs null || strs.length 0) {return ;}String prefix strs[0];for (int i 1; i strs.length; i) {while (strs[i].indexOf(prefix) ! 0) {prefix prefix.substring(0, prefix.length() - 1);if (prefix.isEmpty()) {return ;}}}return prefix;
}}
该算法通过逐个字符比较字符串数组中的字符串来查找最长公共前缀。时间复杂度为O(mn)其中m是最长公共前缀的长度n是字符串数组的长度。空间复杂度为O(1)。
LeetCode运行结果 方法二垂直扫描法
具体的步骤如下
1、如果输入的字符串数组为空或长度为0则直接返回空字符串。
2、遍历字符串数组中的每个字符的索引位置idx从0到字符数组中最短字符串的长度-1
对于每个索引位置idx遍历字符串数组中的每个字符串strs[i]其中i从0到n-1n是字符串数组的长度。如果当前索引位置超过了当前字符串的长度或者当前字符在其他字符串的相同位置上的字符不相等则表示不匹配直接返回当前的公共前缀。否则将当前字符添加到最长公共前缀的末尾。
3、返回最长公共前缀作为结果。
class Solution {
public String longestCommonPrefix(String[] strs) {if (strs null || strs.length 0) {return ;}int minLength getMinLength(strs);StringBuilder prefix new StringBuilder();for (int idx 0; idx minLength; idx) {char currentChar strs[0].charAt(idx);for (int i 1; i strs.length; i) {if (strs[i].charAt(idx) ! currentChar) {return prefix.toString();}}prefix.append(currentChar);}return prefix.toString();
}private int getMinLength(String[] strs) {int minLength Integer.MAX_VALUE;for (String str : strs) {minLength Math.min(minLength, str.length());}return minLength;
}}
该算法通过逐个字符比较字符串数组中的字符串来查找最长公共前缀。时间复杂度为O(mn)其中m是最短字符串的长度n是字符串数组的长度。空间复杂度为O(1)。
LeetCode运行结果 方法三分治法
具体的步骤如下
如果输入的字符串数组为空或长度为0则直接返回空字符串。调用一个辅助函数longestCommonPrefixHelper传入字符串数组和索引范围[0, n-1]n是字符串数组的长度。在longestCommonPrefixHelper函数中如果起始索引等于结束索引则返回当前字符串作为最长公共前缀。将索引范围划分为两半分别调用longestCommonPrefixHelper函数来获取左半部分和右半部分的最长公共前缀。对左半部分和右半部分的最长公共前缀进行比较取两者的最长公共前缀作为结果。
class Solution {
public String longestCommonPrefix(String[] strs) {if (strs null || strs.length 0) {return ;}return longestCommonPrefixHelper(strs, 0, strs.length - 1);
}private String longestCommonPrefixHelper(String[] strs, int start, int end) {if (start end) {return strs[start];}int mid (start end) / 2;String leftPrefix longestCommonPrefixHelper(strs, start, mid);String rightPrefix longestCommonPrefixHelper(strs, mid 1, end);return commonPrefix(leftPrefix, rightPrefix);
}private String commonPrefix(String str1, String str2) {int length Math.min(str1.length(), str2.length());int i 0;while (i length str1.charAt(i) str2.charAt(i)) {i;}return str1.substring(0, i);
}}
该算法使用递归地将字符串数组划分为更小的部分最终求得最长公共前缀。时间复杂度为O(mnlogn)其中m是字符串的平均长度n是字符串数组的长度。空间复杂度为O(logn)用于递归调用栈的额外空间。
LeetCode运行结果 方法四二分查找
具体的步骤如下
如果输入的字符串数组为空或长度为0则直接返回空字符串。将最短的字符串作为起始点将最长的字符串作为终止点。计算起始点和终止点的中点mid。判断从起始点到中点的字符串是否都是其他字符串的公共前缀。如果是则继续在右半部分查找否则在左半部分查找。重复步骤3和步骤4直到起始点和终止点相等或者起始点大于终止点。返回起始点和终止点相等的字符串作为结果。
class Solution {
public String longestCommonPrefix(String[] strs) {if (strs null || strs.length 0) {return ;}int minLength getMinLength(strs);int start 0, end minLength - 1;while (start end) {int mid (start end) / 2;if (isCommonPrefix(strs, mid)) {start mid 1;} else {end mid - 1;}}return strs[0].substring(0, (start end 1) / 2);
}private int getMinLength(String[] strs) {int minLength Integer.MAX_VALUE;for (String str : strs) {minLength Math.min(minLength, str.length());}return minLength;
}private boolean isCommonPrefix(String[] strs, int idx) {String prefix strs[0].substring(0, idx 1);for (int i 1; i strs.length; i) {if (!strs[i].startsWith(prefix)) {return false;}}return true;
}}
该算法使用二分查找来逐步缩小最长公共前缀的范围时间复杂度为O(mnlogm)其中m是最短字符串的长度n是字符串数组的长度。空间复杂度为O(1)。
LeetCode运行结果 第三题
题目来源
15. 三数之和 - 力扣LeetCode
题目内容 解决方法
方法一双指针
可以使用双指针的方法来解决这个问题。首先对数组进行排序然后使用两个指针i和j来遍历数组。
具体的步骤如下
对数组进行排序确保数组是有序的。遍历数组对于每个元素nums[i]设置两个指针left和right分别指向i之后的开始和结束位置。在left和right之间使用双指针法寻找满足nums[i]nums[left]nums[right]0的三元组。如果找到满足条件的三元组将其加入结果集。跳过重复的元素即如果nums[i]和nums[i-1]相等则跳过当前循环。
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
class Solution {
public ListListInteger threeSum(int[] nums) {ListListInteger result new ArrayList();if (nums null || nums.length 3) {return result;}Arrays.sort(nums); // 排序数组for (int i 0; i nums.length - 2; i) {if (i 0 nums[i] nums[i - 1]) {continue; // 跳过重复的元素}int target -nums[i];int left i 1, right nums.length - 1;while (left right) {int sum nums[left] nums[right];if (sum target) {result.add(Arrays.asList(nums[i], nums[left], nums[right]));left;right--;// 跳过重复的元素while (left right nums[left] nums[left - 1]) {left;}while (left right nums[right] nums[right 1]) {right--;}} else if (sum target) {left;} else {right--;}}}return result;
}
}
该算法的时间复杂度为O(n^2)其中n是数组的长度。排序的时间复杂度为O(nlogn)双指针的遍历时间复杂度为O(n^2)。空间复杂度为O(logn)或O(n)取决于排序算法的实现。最终返回的结果列表所占用的空间不计入空间复杂度。
LeetCode运行结果
