【算法提升—力扣每日一刷】五日总结【11/30-12/04】

给定一个整数数组 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-该值对应的数组下标Map<Integer,Integer> map = new HashMap<>(len-1);//循环该数组for(int i = 0; i<len;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 i=0; 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 和自己匹配。

• 给你一个整数 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 = 12，revertedNumber = 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，所以，当原始数字小于或等于反转后的数字时，就意味着我们已经处理了一半位数的数字了。

罗马数字包含以下七种字符: 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 <= 15
• s 仅含字符 ('I', 'V', 'X', 'L', 'C', 'D', 'M')
• 题目数据保证 s 是一个有效的罗马数字，且表示整数在范围 [1, 3999] 内
• 题目所给测试用例皆符合罗马数字书写规则，不会出现跨位等情况。
• IL 和 IM 这样的例子并不符合题目要求，49 应该写作 XLIX，999 应该写作 CMXCIX 。
• 关于罗马数字的详尽书写规则，可以参考 罗马数字 - Mathematics 。

//哈希表存数据 优！
// 定义一个Map，用来存储字符和整数的映射关系static Map<Character, Integer> symbolValues = new HashMap<Character, 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 i=0;i<len;i++){switch (s.charAt(i)){case 'I': if(i==len-1 ){result += 1;}else if( s.charAt(i+1)== 'V' || s.charAt(i+1)== 'X'){result -= 1;}else{result += 1;}case 'V':result += 5;case 'X':if(i==len-1 ){result += 10;}else if(s.charAt(i+1)=='L' || s.charAt(i+1)=='C'){result -= 10;}else{result += 10;}case 'L':result += 50;case 'C':if(i==len-1 ){result += 100;}else if(s.charAt(i+1)=='D' || s.charAt(i+1)=='M'){result -= 100;} else{result += 100;}case 'D': result += 500;default:result += 1000;}}return result;}

给你一个 非严格递增排列 的数组 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] <= 104
• nums 已按 非严格递增 排列

//暴力解法   ！不满足题目中原地的要求public static int removeDuplicates(int[] nums) {//定义一个变量len，用来存储数组的长度int len = nums.length;//定义一个List集合List<Integer> list = new ArrayList<>();//遍历数组for(int i=0;i<len;i++){//如果list集合中不包含当前元素if(!list.contains(nums[i])){//将当前元素添加到list集合中list.add(nums[i]);}}//遍历list集合for(int i=0;i<list.size();i++){//将list集合中的元素赋值给数组nums[i] = list.get(i);}//返回list集合的长度return list.size();}

//双指针解法 优！public static int removeDuplicates2(int[] nums) {//如果数组为空，则返回0if(nums==null){return 0;}//定义两个指针，i指向下一个不重复的元素，j指向当前元素int len = nums.length;int i=1;for(int j=1;j<len;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];// 慢指针加1++slow;}// 快指针加1++fast;}// 返回慢指针的值return slow;}}

编写一个函数来查找字符串数组中的最长公共前缀。

如果不存在公共前缀，返回空字符串 ""。

示例 1：

输入：strs = ["flower","flow","flight"]
输出："fl"

示例 2：

输入：strs = ["dog","racecar","car"]
输出：""
解释：输入不存在公共前缀。

提示：

• 1 <= strs.length <= 200
• 0 <= strs[i].length <= 200
• strs[i] 仅由小写英文字母组成

//横向扫描   
public String longestCommonPrefix(String[] strs) {// 判断字符串数组是否为空if(strs ==null||strs.length==0){return "";}// 获取字符串数组的第一个字符串String s1 = strs[0];// 获取字符串数组的长度int count = strs.length;// 遍历字符串数组for(int i=1;i<count;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 (index<min && s1.charAt(index) == s2.charAt(index)){index++;}// 返回两个字符串的最长公共前缀return s1.substring(0,index);}

public String longestCommonPrefix(String[] strs) {// 如果字符串数组为空或者为null，则返回空字符串if(strs.length==0||strs==null){return "";}// 获取字符串数组中第一个字符串的长度int length = strs[0].length();// 获取字符串数组中字符串的数量int count = strs.length;// 遍历字符串数组中第一个字符串的每一个字符for(int i=0;i<length;i++){// 获取字符串数组中第一个字符串的第i个字符char c = strs[0].charAt(i);// 遍历字符串数组中剩余的字符串for(int j=1;j<count;j++){// 获取字符串数组中第j个字符串的第i个字符char c1 = strs[j].charAt(i);// 如果字符串数组中第j个字符串的长度小于i或者字符串数组中第j个字符串的第i个字符与第一个字符串的第i个字符不相等，则返回第一个字符串的前i个字符if(i==strs[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);}
}