算法总结-数组/字符串

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 - 1
        flips(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 {
                // 如果不能到，就直接返回false
                return 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);
        // 如果不存在就直接返回false
        if (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.思路

字典序排序，比较首尾