算法总结-数组/字符串

1.合并两个有序数组

1.答案

package com.sunxiansheng.arithmetic.day15;/*** Description: 88. 合并两个有序数组** @Author sun* @Create 2025/1/23 10:13* @Version 1.0*/
public class t88 {public void merge(int[] nums1, int m, int[] nums2, int n) {// 倒着合并就可int left = m - 1;int right = n - 1;int cur = m + n - 1;while (left >= 0 && right >= 0) {if (nums1[left] > nums2[right]) {nums1[cur--] = nums1[left--];} else {nums1[cur--] = nums2[right--];}}// 到这，一定有一个指针小于0了，将剩下的元素填到数组的前面while (left >= 0) {nums1[cur--] = nums1[left--];}while (right >= 0) {nums1[cur--] = nums2[right--];}}
}

2.思路

就是倒着合并，最后将剩下的部分填到数组前面即可

2.移除元素

1.答案

package com.sunxiansheng.arithmetic.day15;/*** Description: 27. 移除元素** @Author sun* @Create 2025/1/23 10:24* @Version 1.0*/
public class t27 {public static int removeElement(int[] nums, int val) {// 双指针int slow = 0;for (int fast = 0; fast < nums.length; fast++) {// 只要fast指向的不是被删除的就移动if (nums[fast] != val) {nums[slow++] = nums[fast];}}return slow;}
}

2.思路

双指针算法，只要fast指向的不是被删除的就移动

3.删除有序数组中的重复项 II

1.答案

package com.sunxiansheng.arithmetic.day15;/*** Description: 80. 删除有序数组中的重复项 II** @Author sun* @Create 2025/1/23 14:46* @Version 1.0*/
public class t80 {public int removeDuplicates(int[] nums) {// 双指针int slow = 0;for (int fast = 0; fast < nums.length; fast++) {if (slow < 2 || nums[fast] > nums[slow - 2]) {nums[slow++] = nums[fast];}}return slow;}
}

2.思路

当slow是小于2的或者fast指向的元素是大于slow-2的才替换

4.多数元素

1.答案

package com.sunxiansheng.arithmetic.day15;/*** Description: 169. 多数元素** @Author sun* @Create 2025/1/23 15:27* @Version 1.0*/
public class t169 {public int majorityElement(int[] nums) {int num = nums[0];int count = 1;for (int i = 1; i < nums.length; i++) {// 相同的就增加，不同的就抵消if (nums[i] == num) {count++;} else {count--;// 如果发现数量为0，就更换数字if (count == 0) {num = nums[i];count = 1;}}}return num;}
}

2.思路

相同的增加，不同的就抵消，如果发现数量为0，就更换数字

5.轮转数组

1.答案

package com.sunxiansheng.arithmetic.day16;/*** Description: 189. 轮转数组** @Author sun* @Create 2025/1/24 09:51* @Version 1.0*/
public class t189 {public static void rotate(int[] nums, int k) {// 计算余数int remainderInDivision = k % nums.length;// 余数是0就不翻转了if (remainderInDivision == 0) {return;}// 整体翻转flips(nums, 0, nums.length - 1);// 如果余数不是0，就翻转0到remainderInDivision - 1flips(nums, 0, remainderInDivision - 1);// 翻转剩余的部分flips(nums, remainderInDivision, nums.length - 1);}/*** 翻转指定区域的数组** @param nums* @param start* @param end*/private static void flips(int[] nums, int start, int end) {while (start < end) {int temp = nums[start];nums[start] = nums[end];nums[end] = temp;start++;end--;}}
}

2.思路

先求余数，如果余数是0直接不翻转了，如果不是0就先翻转整个数组，然后翻转0到余数-1的元素，最后再翻转剩下的元素

6.买卖股票的最佳时机

1.答案

package com.sunxiansheng.arithmetic.day16;/*** Description: 121. 买卖股票的最佳时机** @Author sun* @Create 2025/1/24 10:07* @Version 1.0*/
public class t121 {public int maxProfit(int[] prices) {int min = prices[0];int maxProfit = Integer.MIN_VALUE;// 每次遍历都更新最小值和计算结果for (int i = 0; i < prices.length; i++) {// 更新最小值min = Math.min(min, prices[i]);// 更新结果maxProfit = Math.max(maxProfit, prices[i] - min);}return maxProfit;}
}

2.思路

每次遍历都更新最小值和计算结果

7.买卖股票的最佳时机 II

1.答案

package com.sunxiansheng.arithmetic.day16;/*** Description: 122. 买卖股票的最佳时机 II** @Author sun* @Create 2025/1/24 10:28* @Version 1.0*/
public class t122 {public int maxProfit(int[] prices) {// 相邻两天，只要能盈利就卖int res = 0;for (int i = 0; i < prices.length - 1; i++) {if (prices[i] < prices[i + 1]) {res += prices[i + 1] - prices[i];}}return res;}
}

2.思路

相邻两天，只要盈利就卖

8.跳跃游戏

1.答案

package com.sunxiansheng.arithmetic.day16;/*** Description: 55. 跳跃游戏** @Author sun* @Create 2025/1/24 10:35* @Version 1.0*/
public class t55 {public boolean canJump(int[] nums) {int distance = 0;// 每次先判断自己能不能到，如果能到就更新最远距离for (int i = 0; i < nums.length; i++) {if (i <= distance) {// 能到，则更新最远距离distance = Math.max(distance, i + nums[i]);} else {// 如果不能到，就直接返回falsereturn false;}}return true;}
}

2.思路

每次先判断自己能不能到，如果能到就更新最远距离

9.H 指数

1.答案

package com.sunxiansheng.arithmetic.day16;import java.util.Arrays;/*** Description: 274. H 指数** @Author sun* @Create 2025/1/24 11:43* @Version 1.0*/
public class t274 {public static int hIndex(int[] citations) {// 排序Arrays.sort(citations);// 记录目前是第几篇文章int cur = 0;// 判断是自然退出还是不满足要求退出boolean flag = true;// 逆序遍历，只要满足当前的文章引用数大于等于当前的文章数，即满足H指数要求for (int i = citations.length - 1; i >= 0; i--) {// 当前文章数cur++;// 不满足h指数要求，就退出if (citations[i] < cur) {flag = false;break;}}// 自然退出就是cur，非自然退出要减一return flag ? cur : cur - 1;}
}

2.思路

先排序，然后根据目前是第几篇文章来判断是否满足h指数的要求，不满足要求就退出

10.O(1) 时间插入、删除和获取随机元素

1.答案

package com.sunxiansheng.arithmetic.day17;import java.util.*;/*** Description: 380. O(1) 时间插入、删除和获取随机元素** @Author sun* @Create 2025/1/27 09:41* @Version 1.0*/
public class RandomizedSet {/*** 数组存储元素*/private List<Integer> nums;/*** map存储值和下标*/private Map<Integer, Integer> map;Random random;/*** 初始化*/public RandomizedSet() {nums = new ArrayList<>();map = new HashMap<>();random = new Random();}/*** 插入元素** @param val* @return*/public boolean insert(int val) {// 元素不存在，则向集合中插入if (!map.containsKey(val)) {map.put(val, nums.size());nums.add(val);return true;}return false;}/*** 删除元素** @param val* @return*/public boolean remove(int val) {// 找到元素下标Integer index = map.get(val);// 如果不存在就直接返回falseif (index == null) {return false;}// 删除最后一个元素if (index == nums.size() - 1) {nums.remove(nums.size() - 1);} else {// 使用最后一个元素替换被删除的元素Integer lastElement = nums.get(nums.size() - 1);nums.set(index, lastElement);nums.remove(nums.size() - 1);// 更新替换元素的位置map.put(lastElement, index);}// 从map中删除该元素map.remove(val);return true;}/*** 获取随机元素** @return*/public int getRandom() {return nums.get(random.nextInt(nums.size()));}
}

2.思路

数组存储元素，map存储值和下标，需要注意的是在删除的时候如果删除的是最后一个元素，就直接删除即可

11.除自身以外数组的乘积

1.答案

package com.sunxiansheng.arithmetic.day17;/*** Description: 238. 除自身以外数组的乘积** @Author sun* @Create 2025/1/27 10:17* @Version 1.0*/
public class t238 {public static int[] productExceptSelf(int[] nums) {int[] res = new int[nums.length];// 使用一个元素来记录前缀积int prefix = 1;// 计算前缀积填充到结果for (int i = 0; i < nums.length; i++) {res[i] = prefix;// 更新前缀积prefix *= nums[i];}// 使用一个元素来计算后缀积int suffix = 1;for (int i = nums.length - 1; i >= 0; i--) {// 当前元素乘上后缀积作为结果res[i] *= suffix;// 更新后缀积suffix *= nums[i];}return res;}
}

2.思路

就是先计算一遍前缀积，然后计算一遍后缀积前缀积乘上后缀积就是结果

12.分发糖果

1.答案

package com.sunxiansheng.arithmetic.day17;import java.util.Arrays;/*** Description: 135. 分发糖果** @Author sun* @Create 2025/1/27 10:32* @Version 1.0*/
public class t135 {public int candy(int[] ratings) {// 左贪心和右贪心，只要当前孩子的评分比一边孩子的评分高，就让当前孩子的糖果多一个// 初始化糖果数组int[] candies = new int[ratings.length];// 都是一个糖果Arrays.fill(candies, 1);// 左贪心for (int i = 1; i < candies.length; i++) {if (ratings[i] > ratings[i - 1]) {candies[i] = candies[i - 1] + 1;}}// 记录结果int res = 0;res += candies[ratings.length - 1];// 右贪心for (int i = candies.length - 2; i >= 0; i--) {// 这里还要考虑如果当前孩子的糖果已经比右边的数量多了，就不要再加了if (ratings[i] > ratings[i + 1] && candies[i] <= candies[i + 1]) {candies[i] = candies[i + 1] + 1;}// 记录结果res += candies[i];}return res;}
}

2.思路

左贪心和右贪心，只要当前孩子的评分比一边孩子的评分高，就让当前孩子的糖果多一个，在第二次贪心的时候需要注意，如果当前孩子的糖果已经比右边的数量多了，就不要再加了

13.整数转罗马数字

1.答案

package com.sunxiansheng.arithmetic.day17;/*** Description: 12. 整数转罗马数字** @Author sun* @Create 2025/1/27 10:53* @Version 1.0*/
public class t12 {int[] values = {1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};String[] symbols = {"M", "CM", "D", "CD", "C", "XC", "L", "XL", "X", "IX", "V", "IV", "I"};public String intToRoman(int num) {// 存储结果StringBuilder sb = new StringBuilder();// 表示当前的位置int cur = 0;while (num > 0 && cur < values.length) {// 能减就减，不能减就换下一个元素if (num - values[cur] >= 0) {sb.append(symbols[cur]);num -= values[cur];} else {cur++;}}return sb.toString();}
}

2.思路

能减就减，不能减就换下一个元素

14.最长公共前缀

1.答案

package com.sunxiansheng.arithmetic.day17;import java.util.Arrays;/*** Description: 14. 最长公共前缀** @Author sun* @Create 2025/1/27 11:03* @Version 1.0*/
public class t14 {public static String longestCommonPrefix(String[] strs) {// 字典序排序，比较首尾Arrays.sort(strs);// 首尾元素String start = strs[0];String end = strs[strs.length - 1];// 记录结果StringBuilder sb = new StringBuilder();for (int i = 0; i < start.length(); i++) {if (start.charAt(i) != end.charAt(i)) {break;}sb.append(start.charAt(i));}return sb.toString();}
}

2.思路

字典序排序，比较首尾