hot150-01-数组/字符串

holic-x...大约 60 分钟

难度说明：🟢简单🟡中等🔴困难

hot150-01-数组/字符串

🟢07-买卖股票的最佳时机（121）🚀

1.题目内容

给定一个数组 prices ，它的第 i 个元素 prices[i] 表示一支给定股票第 i 天的价格。

你只能选择 某一天 买入这只股票，并选择在 未来的某一个不同的日子 卖出该股票。设计一个算法来计算你所能获取的最大利润。

返回你可以从这笔交易中获取的最大利润。如果你不能获取任何利润，返回 0

2.题解思路

暴力思路：双层循环（暴力遍历），依次判断假设当天买入，其后的每一天卖出的利润的最大值

贪心算法：单层循环，以低买高卖的思路操作，记录股票的历史最低价，假设股票是以历史最低价买入，然后卖出的话能获得的利润

👻方法1：贪心算法（低买高卖）

/**
 * 121 买卖股票的最佳时机
 */
public class Solution1 {

    /**
     * 贪心算法：记录股票的历史低价，以及股票隔日卖出时可以获得利益（更新max）
     */
    public int maxProfit(int[] prices) {
        // 记录利益的最大值
        int maxProfit = 0; // Integer.MIN_VALUE（此处设定利润初始化为0,后续利润是负数也没办法卖）
        // 记录股票价格的历史最低价
        int minHisPrice = prices[0]; // 默认第1天为最低价，后续遍历过程中更新最低价
        // 遍历数组元素
        for(int i=1;i<prices.length;i++) {
            // 假设股票当前卖出，计算这个利润值，并对比是否可获得最大利益（更新目前的最大收益）
            maxProfit = Math.max(maxProfit,prices[i] - minHisPrice);
            // 更新历史最低价
            minHisPrice = Math.min(minHisPrice,prices[i]);
        }
        // 返回结果
        return maxProfit;
    }

}

复杂度分析
- 时间复杂度：O(n)，n 为数组长度
- 空间复杂度：O(1) 用了两个字段存储值，常数级别的消耗

🟡09-跳跃游戏（55）

1.题目内容

给你一个非负整数数组 nums ，你最初位于数组的 第一个下标 。数组中的每个元素代表你在该位置可以跳跃的最大长度。

判断你是否能够到达最后一个下标，如果可以，返回 true ；否则，返回 false 。

2.题解思路

👻方法2：动态规划思路

步骤分析
- 【步骤1】：确定dp数组及下标含义（根据穷举规律来理解分析）
  - dp[i]：表示到达i位置时能到达的最远距离
- 【步骤2】：得到推导公式（结合规律得到dp[k]的推导公式，即dp[k]与前面的元素有什么联系）
  - dp[i] = max(dp[i-1], i + nums[i])（max(前i-1个节点的最大距离，当前节点能跳的最大距离)）
- 【步骤3】：初始化dp数组（处理初始状态和一些临界的情况）
  - dp[0]=nums[0]（起始可跳的距离就是当前节点提供的跳跃距离）
- 【步骤4】：确定循环（通过循环和推导公式填充dp数组）
  - 循环遍历数组元素
- 【步骤5】：验证dp数组正确性

简化下述动态规划存储（因为不需要记录过程中的数据，只需要关注最大覆盖的距离，因此此处简化的版本之后就会变成解法【1】的思路）

// 思路：动态规划
public boolean canJump(int[] nums) {
    // 1.dp[i] 表示到达`i`位置时能到达的最远距离
    int[] dp = new int[nums.length];

    // 2.确认dp公式 dp[i] = max{dp[i-1],i+nums[i]} 即max{第i-1个节点能到达的最远位置 , 已走距离+当前可支持跳跃距离}

    // 3.初始化
    dp[0] = nums[0];

    // 4.确定循环
    for (int i = 1; i < nums.length; i++) {
        if (dp[i - 1] < i) { // 比较上一个覆盖范围可否到达当前节点
            return false;
        }
        dp[i] = Math.max(dp[i - 1], i + nums[i]);
    }

    // 5.遍历dp数据，判断dp对应的值是否可以支撑走到当前节点(即前一个范围能否覆盖到当前节点)
    // 此处可以在循环中就进行判断，如果走不到当前节点，则可以直接返回false
    return true;
}

复杂度分析
- 时间复杂度：O(n) n 为数组长度
- 空间复杂度：O(n) n 为数组长度

🟡13-除自身以外的乘积（238）🚀

1.题目内容

给你一个整数数组 nums，返回数组 answer ，其中 answer[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。

题目数据保证数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内。

请 **不要使用除法，**且在 O(n) 时间复杂度内完成此题。

2.题解思路

👻方法2：左右乘积法（动态规划思路：左侧前缀乘积*右侧后缀乘积）

左右乘积法思路（类似动态规划的思路，可以从最简单的案例进行分析寻找规律）
- 分别计算每个元素的左侧乘积和右侧乘积，然后循环遍历进行整合（但需注意此处并不是在循环中嵌套循环去计算，而是分别计算每个元素的左侧乘积和右侧乘积）
- 左侧乘积：正向遍历（从第2个元素位置开始：left[i]=left[i-1]*nums[i-1]）
- 右侧乘积：反向遍历（从倒数第二个元素开始：right[i]=right[i+1]*nums[i+1]）
- res：再次正向遍历，得到res[i]=left[i]*right[i]

public class Solution2 {
    // 左右乘积法：分别计算指定元素左侧和右侧的乘积，然后进行相乘
    public int[] productExceptSelf(int[] nums) {
        // 定义结果
        int[] res = new int[nums.length];

        // 左乘积
        int[] left = new int[nums.length]; // 存储当前元素的左侧乘积（除自身）
        Arrays.fill(left, 1);
        int[] right = new int[nums.length];// 存储当前元素的右侧乘积（除自身）
        Arrays.fill(right, 1);

        // 左侧乘积计算
        for (int i = 1; i < nums.length; i++) {
            left[i] = left[i - 1] * nums[i - 1];
            System.out.print(left[i] + "-");
        }
        System.out.println("-----------");
        // 右侧乘积计算
        for (int i = nums.length - 2; i >= 0; i--) {
            right[i] = right[i + 1] * nums[i + 1];
            System.out.print(right[i] + "-");
        }

        // 再次遍历，得到乘积（每个元素除自身的乘积=left*right）
        for (int i = 0; i < nums.length; i++) {
            res[i] = left[i] * right[i];
        }

        // 返回结果
        return res;
    }
}

复杂度分析
- 时间复杂度：需要进行3次遍历，时间复杂度趋向O(n)
- 空间复杂度：需要用到3个和原数组等长的数组进行处理，空间复杂度趋向O(n)

🟡14-加油站（150）

1.题目内容

在一条环路上有 n 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

给定两个整数数组 gas 和 cost ，如果你可以按顺序绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1 。如果存在解，则保证它是唯一的

示例 1:

输入: gas = [1,2,3,4,5], cost = [3,4,5,1,2]
输出: 3
解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

示例 2:

输入: gas = [2,3,4], cost = [3,4,3]
输出: -1
解释:
你不能从 0 号或 1 号加油站出发，因为没有足够的汽油可以让你行驶到下一个加油站。
我们从 2 号加油站出发，可以获得 4 升汽油。 此时油箱有 = 0 + 4 = 4 升汽油
开往 0 号加油站，此时油箱有 4 - 3 + 2 = 3 升汽油
开往 1 号加油站，此时油箱有 3 - 3 + 3 = 3 升汽油
你无法返回 2 号加油站，因为返程需要消耗 4 升汽油，但是你的油箱只有 3 升汽油。
因此，无论怎样，你都不可能绕环路行驶一周。

2.题解思路

👻方法1：规律法

问题的核心：从某个加油站出发，如果能够到达下一个加油站且剩余油量更多或者刚好够，就继续前进；如果剩余油量不足以到达下一个加油站，就从下一个加油站重新开始尝试确认

初始化：总油量（到达当前的【i】位置需要的总油量）、当前油量（当前【i】位置加油后到达下一个加油站后的剩余油量）、startIdx（出发的加油站起始索引）
依次遍历每个加油站，判断以startIdx开始，能否顺利走到下一个加油站，如果出现不可达情况，则从当前startIdx的下一个位置开始重新计算
- 遍历加油站，更新总油量和到达下一站的剩余油量
- 如果遍历过程中发现某站不可达下一站，则说明当前起始站出发无法完成行程，需要重置出发点和当前油量为0
- 通过不断遍历调试起始站，如果最终可以遍历完所有加油站，且总油量大于等于0，则说明找到了可行的起点，否则返回-1

此处设计巧妙的一点是，遍历过程中只关心的是当前站能否到达下一个站点，如果不能到达则重置起点，在遍历完成后才去校验所需总油量是否大于等于0（以确认循环是否可完成）

核心：如果x可以到达y，但是无法到达y+1，则x-y之间的任何一个点也无法到达y+1。因此循环遍历的过程是，如果无法到达下一个点则不断切换起点位置，确认循环能否完整走完，如果循环可以走完的话，则确认这段距离的总油量是否有剩余，如果无剩余则说明是不可构成环的

利用x点可以到达y但是到达不了y的下一站这个前提条件，然后运用放缩法对等式进行放缩，利用数学就可以得出，如果x可以到达y，但是到达不了y+1，那么x至y之间的任何点也不可能到达y+1。 `当然也可以直接分析得出结论，因为如果从x能到y，但是到不了y的下一站，那么肯定从y开始出发也必然到不了y的下一站，因为x能到y则必然到y时剩余的油量大于等于0，既然这个大于等于0都到不了y的下一站，那么必然从y点重新出发前，油量为0，则肯定到不了y的下一站。依次类推，x至y的所有中间点都到不了y的下一站

public class Solution1 {
    /**
     *  确认是否可以绕一圈
     * @param gas 当前加油站可提供油量
     * @param cost 从当前加油站到下一个加油站需要消耗的油量
     */
    public int canCompleteCircuit(int[] gas, int[] cost) {
        /**
         * 思路：循环遍历每个加油站，确认其是否可到达下一个加油站
         * 需要记录当前总油量、出发起点的加油站索引、从指定索引开始出发至今油量
         */
        int totalGas = 0;
        int startIdx = 0; // 起点加油站索引
        int curGas = 0;

        // 遍历每个加油站，确认是否可到达下一个加油站，如果出现不可到达的情况，则从下一个位置开始重新出发
        for(int i = 0; i < gas.length; i++) {
            // 更新最大油量和当前可剩油量
            totalGas  = totalGas + (gas[i] - cost[i]);
            curGas = curGas + (gas[i] - cost[i]);
            // 判断当前能否走到下一个加油站（如果出现不可达，则应从下一个加油站重新出发进行计算）
            if(curGas < 0) { // (当前剩余油量+可加油量) 小于 到达下一站所需油量，说明此站不可达下一个站，则需切换起点
                startIdx = i + 1; // 切换下一个起点进行计算
                curGas = 0 ; // 重新切换后，当前剩余油量需重置为0
            }
        }
        // 最终判断totalGas是否大于等于0（表示足够或者刚好能够到达）
        return totalGas>=0?startIdx:-1;
    }
}

复杂度分析
- 时间复杂度：
- 空间复杂度：

思路2：tocheck

1.先不考虑循环问题。

-2 -2 -2 3 3 这是每一个站加了油到下一个站能剩余的量(gas[i] - cost[i])（不考虑之前站加的油。）从这个数组可以看出来，是负数的必然不是起点，因为，就不可能走到下一个站。所以必然是正数的才可能是起点。再猜想：该数组的前缀和最小处可能是循环的终点，下一个位置可能是起点。假设该点为a, 若a之前的某个点b是终点，它的差数组接下来一段b->a和是负值，必然不能从b的下一个出发到a点。（因为到达a才是前缀和最小，a前的一段和必然是负值）再假设，终点在a的后边的某个位置b ，则a->b这一段和必然是正数，否则前缀和到b才是最小。在该段和是正数的情况下，从b的下一个出发，很可能无法到达a. 因为，该段和是正数，它在最小前缀的后边，需要最后经过a之后才能取到，但是可能恰好缺少该段和而不能到达a。

2.循环对前缀和的影响。若原差数组是 -2 3 3 -2 -2 求最小前缀和依然可以定位到第一个3作为出发点。但是为什么循环没有影响呢。为什么会等价于-2 -2 -2 3 3呢？其实求前缀和的意义，就是划分，最小最大子段和，对于 -2 3 3 -2 -2 完全肯伊等价于 -2 2 的问题把后边写成一个和其就和 -2 -2 -2 3 3 是一致的的了。都是在前边存在最小前缀和，后边为起点。

不可行的判断

（1）：差数组的和为负数，必然不能走完循环。显然（2）：那么对于和为正数的差数组，一定可以吗？不显然，但是是的。对于该问题总能划分为 -2 -2 -2 3 3 类似的形式，如果后半段有负数如-2 3 3 -2 -2 也等价于 -2 2 问题：总是分为最小前缀和部分，和后边和为正数的形式。正数 >= 最小前缀就一定能走完。

4 ：如果最小前缀是在最后的位置，如果sum >= 0 则说明正数段在前边。

code 将求差和求最小前缀和的过程合并。 */

class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int index = 0;
        int minsum = gas[0] - cost[0];
        int presum = gas[0] - cost[0];
        for(int i = 1; i < gas.length; i++){
            int tempsum = presum + gas[i] - cost[i];
            if(tempsum < minsum) {
                index = i;
                minsum = tempsum;
            }
            presum = tempsum;
        }
        if(presum < 0) return -1;
        return (index+1) % gas.length;
    }
}

🔴15-分糖果（135）

1.题目内容

2.题解思路

👻方法1：

复杂度分析
- 时间复杂度：
- 空间复杂度：

🔴16-接雨水（42）

1.题目内容

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水

2.题解思路

👻方法1：动态规划

将接雨水的思路转化为：计算每个柱子可以接的雨水量，然后进行相应的累加（每个柱子可以接的雨水量等于其min(左侧最大前缀,右侧最大后缀)-柱子高度）

/**
 * 42 接雨水
 */
public class Solution1 {

    public int trap(int[] height) {
        int res = 0;

        /**
         * 接雨水：计算每个柱子可以接的雨水量，然后进行累加
         * 每个柱子可接雨水量=min(左侧最大前缀,右侧最大后缀)-柱子高度
         */
        // 先分别计算每个元素的右侧最大后缀、左侧最大前缀
        int n = height.length;
        int[] leftMax = new int[n];
        leftMax[0] = height[0]; // 初始化
        int[] rightMax = new int[n];
        rightMax[n-1] = height[n - 1]; // 初始化

        // 计算左侧最大前缀
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i-1], height[i]);
        }

        // 计算右侧最大后缀
        for(int i=n-2;i>=0;i--){
            rightMax[i] = Math.max(rightMax[i+1], height[i]);
        }

        // 累计每个柱子可接雨水量(水往低处流，选择较小的柱子然后减去自身高度)
        for(int i=0;i<n;i++){
            res += Math.min(leftMax[i],rightMax[i]) - height[i];
        }

        // 返回结果
        return res;
    }
}

复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(n)

🟢17-罗马数字转整数（13）

1.题目内容

罗马数字包含以下七种字符: 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。

给定一个罗马数字，将其转换成整数

2.题解思路

通常情况下，罗马数字中小的数字在大的数字的右边。若输入的字符串满足该情况，那么可以将每个字符视作一个单独的值，累加每个字符对应的数值即可。

例如 XXVII 可视作 X+X+V+I+I=10+10+5+1+1=27

若存在小的数字在大的数字的左边的情况，根据规则需要减去小的数字。对于这种情况，我们也可以将每个字符视作一个单独的值，若一个数字右侧的数字比它大，则将该数字的符号取反。

例如 XIV 可视作 X−I+V=10−1+5=14

👻方法1：模拟（规律法）

解题核心：只要当前位置的元素比下个位置的元素小，就减去当前值，否则加上当前值

/**
 * 013 罗马数字转整数
 */
public class Solution {

    public int romanToInt(String s) {
        // 定义结果
        int res = 0;

        // 构建字符映射集合
        HashMap<Character, Integer> map = new HashMap<>();
        map.put('I', 1);
        map.put('V', 5);
        map.put('X', 10);
        map.put('L', 50);
        map.put('C', 100);
        map.put('D', 500);
        map.put('M', 1000);

        // 解析字符串（规则：只要当前元素比下一位元素小就减去值，如果比下一位大就加上值）
        int len = s.length();
        for (int i = 0; i < len; i++) {
            int curVal = map.get(s.charAt(i));
            if ((i < len - 1) && (curVal < map.get(s.charAt(i + 1)))) { // 如果当前元素比下一位小则减去当前值，如果比下一位元素大就加上，且i最大可达n-2的位置（注意数组越界）
                res -= curVal;
            } else {
                res += curVal;
            }
        }
        // 返回结果
        return res;
    }
}

复杂度分析
- 时间复杂度：O(n)
- 空间复杂度：O(1)

🟡18-整数转罗马数字（45）

1.题目内容

七个不同的符号代表罗马数字，其值如下：

符号	值
I	1
V	5
X	10
L	50
C	100
D	500
M	1000

罗马数字是通过添加从最高到最低的小数位值的转换而形成的。将小数位值转换为罗马数字有以下规则：

如果该值不是以 4 或 9 开头，请选择可以从输入中减去的最大值的符号，将该符号附加到结果，减去其值，然后将其余部分转换为罗马数字。
如果该值以 4 或 9 开头，使用 减法形式，表示从以下符号中减去一个符号，例如 4 是 5 (V) 减 1 (I): IV ，9 是 10 (X) 减 1 (I)：IX。仅使用以下减法形式：4 (IV)，9 (IX)，40 (XL)，90 (XC)，400 (CD) 和 900 (CM)。
只有 10 的次方（I, X, C, M）最多可以连续附加 3 次以代表 10 的倍数。你不能多次附加 5 (V)，50 (L) 或 500 (D)。如果需要将符号附加4次，请使用 减法形式。

给定一个整数，将其转换为罗马数字。

示例 1：
输入：num = 3749
输出： "MMMDCCXLIX"
解释：
3000 = MMM 由于 1000 (M) + 1000 (M) + 1000 (M)
 700 = DCC 由于 500 (D) + 100 (C) + 100 (C)
  40 = XL 由于 50 (L) 减 10 (X)
   9 = IX 由于 10 (X) 减 1 (I)
注意：49 不是 50 (L) 减 1 (I) 因为转换是基于小数位

示例 2：
输入：num = 58
输出："LVIII"
解释：
50 = L
 8 = VIII
 
示例 3：
输入：num = 1994
输出："MCMXCIV"
解释：
1000 = M
 900 = CM
  90 = XC
   4 = IV

2.题解思路

👻方法1：模拟（规律法）

思路分析

根据罗马数字的表示规则：可以看到其一共列举了13种独特的符号

普通规则：1 (I)，5 (V)，10 (X)，50 (L)，100 (C) 和 1000 (M)
减法规则：4 (IV)，9 (IX)，40 (XL)，90 (XC)，400 (CD) 和 900 (CM)

罗马数字的规则是：对于罗马数字从左到右的每一位，选择尽可能大的符号值。对于 140，最大可以选择的符号值为 C=100。接下来，对于剩余的数字 40，最大可以选择的符号值为 XL=40。因此，140 的对应的罗马数字为 C+XL=CXL

因此可以借助罗马数字的唯一表示规律：每次都循环找到不超过num的最大符号值，用num减去这个符号值，并将这个符号值拼接到结果中，循环直到num减为0

写法1：暴力循环

public class Solution2 {

    public String intToRoman(int num) {
        // 构建字符串序列
        StringBuilder roman = new StringBuilder();

        // 罗马数字表示规则：一直找最大的字符值，找到后进行拼接，并减去对应整数值，以此类推，直到num为0（硬核遍历方式）
        while (num > 0) {
            // 从大到小遍历
            if (num >= 1000) {
                num -= 1000;
                roman.append("M");
            } else if (num >= 900) {
                num -= 900;
                roman.append("CM");
            } else if (num >= 500) {
                num -= 500;
                roman.append("D");
            } else if (num >= 400) {
                num -= 400;
                roman.append("CD");
            } else if (num >= 100) {
                num -= 100;
                roman.append("C");
            } else if (num >= 90) {
                num -= 90;
                roman.append("XC");
            } else if (num >= 50) {
                num -= 50;
                roman.append("L");
            } else if (num >= 40) {
                num -= 40;
                roman.append("XL");
            } else if (num >= 10) {
                num -= 10;
                roman.append("X");
            } else if (num >= 9) {
                num -= 9;
                roman.append("IX");
            } else if (num >= 5) {
                num -= 5;
                roman.append("V");
            } else if (num >= 4) {
                num -= 4;
                roman.append("IV");
            } else if (num >= 1) {
                num -= 1;
                roman.append("I");
            }
        }
        // 返回结果
        return roman.toString();
    }

}

写法2：集合遍历

/**
 * 012 整数转罗马数字
 */
public class Solution1 {

    public String intToRoman(int num) {
        // 构建字符串序列
        StringBuilder roman = new StringBuilder();

        // 定义罗马数字映射集(将13种情况进行列举):每次查找都优先找最大的，此处借助需构建有序性（此处也可以通过两个数组做）
        LinkedHashMap<Integer, String> map = new LinkedHashMap<>();
        map.put(1000, "M");
        map.put(900, "CM");
        map.put(500, "D");
        map.put(400, "CD");
        map.put(100, "C");
        map.put(90, "XC");
        map.put(50, "L");
        map.put(40, "XL");
        map.put(10, "X");
        map.put(9, "IX");
        map.put(5, "V");
        map.put(4, "IV");
        map.put(1, "I");

        // 罗马数字表示规则：一直找最大的字符值，找到后进行拼接，并减去对应整数值，以此类推，直到num为0
        Iterator<Map.Entry<Integer, String>> it = map.entrySet().iterator();
        while (it.hasNext()) { // 依次遍历映射集
            Map.Entry<Integer, String> entry = it.next();
            int key = entry.getKey();
            String value = entry.getValue();
            while (num >= key) { // 如果num>=key 说明需进行转化（因为映射集本身从大到小进行排序，因此此处就是在转化最大值）
                roman.append(value);
                num -= key;
            }
            if (num == 0) { // 当num为0的时候，退出，直到所有的字符遍历完成
                break;
            }
        }
        return roman.toString();
    }

}

写法3：集合遍历（和写法2类似，此处用数组做）

public class Solution3 {

    public String intToRoman(int num) {
        // 构建字符串序列
        StringBuilder roman = new StringBuilder();

        // 定义罗马数字映射集(将13种情况进行列举):每次查找都优先找最大的，此处借助需构建有序性（此处也可以通过两个数组做）
        int[] numbers = new int[]{1000, 900, 500, 400, 100, 90, 50, 40, 10, 9, 5, 4, 1};
        String[] romans = new String[]{"M","CM", "D","CD","C","XC", "L", "XL", "X", "IX", "V", "IV", "I"};

        // 罗马数字表示规则：一直找最大的字符值，找到后进行拼接，并减去对应整数值，以此类推，直到num为0
        for(int i=0;i<numbers.length;i++) {
            while(num>=numbers[i]){
                roman.append(romans[i]);
                num -= numbers[i];
            }
            if(num==0){
                break;
            }
        }

        // 返回结果
        return roman.toString();
    }

}

复杂度分析
- 时间复杂度：
- 空间复杂度：

🟢19-最后一个单词的长度（58）

1.题目内容

给你一个字符串 s，由若干单词组成，单词前后用一些空格字符隔开。返回字符串中 最后一个 单词的长度。

单词是指仅由字母组成、不包含任何空格字符的最大子字符串

示例 1：

输入：s = "Hello World"
输出：5
解释：最后一个单词是“World”，长度为 5。

示例 2：

输入：s = "   fly me   to   the moon  "
输出：4
解释：最后一个单词是“moon”，长度为 4。

示例 3：

输入：s = "luffy is still joyboy"
输出：6
解释：最后一个单词是长度为 6 的“joyboy”。

2.题解思路

👻方法1：字符串切割

可借助String的split将字符串切割为字符串数组，然后取最后一个

/**
 * 058 最后一个单词的长度
 */
public class Solution1 {
    // 思路：字符串切割，取最后一个字母
    public int lengthOfLastWord(String s) {
        String[] splitStr = s.split(" ");
        return splitStr[splitStr.length - 1].length();
    }
}

复杂度分析
- 时间复杂度：
- 空间复杂度：

👻方法2：反向遍历

反向遍历字符串，从第一个非空格字符开始遍历，遇到空格则说明这个单词结束了

public class Solution2 {
    // 思路：反向遍历（从第一个非空格字符开始遍历，后面遇到空格说明单词遍历结束了）
    public int lengthOfLastWord(String s) {

        // 定义结果
        int res = 0;

        // 逆序（反向遍历）
        for(int i = s.length() - 1; i >= 0; i--) {
            char c = s.charAt(i);

            // 跳过尾部可能存在的空格字符，且要遍历的第一个字母肯定不为空(因此遍历退出的条件是字符为空格且res不为空)
            if(c==' ' && res !=0){
                break ;
            }

            // 非空格字符才计算
            if(c!=' '){
                res ++;
            }
        }

        // 返回结果
        return res;
    }
}

复杂度分析
- 时间复杂度：
- 空间复杂度：

🟢20-最长公共前缀（14）

1.题目内容

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

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

示例 1：

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

示例 2：

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

2.题解思路

👻方法1：正常思路

正常分析思路：理想情况下最长前缀是这个数组中长度最小的字符串，因此可以拆分思路：

（1）找到这个理想的最长前缀 minStr (长度最小的字符串)
（2）通过截取这个minStr 的前缀来依次进行匹配，确认最长

/**
 * 14 最长公共前缀
 */
public class Solution1 {

    /**
     * 思路：理想情况下最长前缀是这个数组中长度最小的字符串，因此可以拆分思路：
     * 1.找到这个理想的最长前缀 prefix(长度最小的字符串)
     * 2.通过截取这个prefix来依次进行匹配，确认最长
     */
    public String longestCommonPrefix(String[] strs) {
        // 定义最大前缀
        String maxPrefix = "";

        String minStr = strs[0];
        // 1.找到minStr(最短ed字符串)
        for (int i = 0; i < strs.length; i++) {
            if (strs[i].length() < minStr.length()) {
                minStr = strs[i];
            }
        }

        // 预设maxPrefix为理想情况
        maxPrefix = minStr;

        // 2.通过截取minStr，分别和数组元素进行匹配（此处需注意i最大可以取到minStr.length()位置）
        for(int i = 0; i <= minStr.length(); i++) {
            String prefix = minStr.substring(0, i);
            // 如果校验不匹配则直接返回
            if(!valid(prefix,strs)){
                return minStr.substring(0, i-1);
            }
        }

        return maxPrefix; // return null; ""表示不存在最长前缀
    }

    // 校验数组中的每个元素是否有公共前缀
    public boolean valid(String prxfix,String[] strs) {
        for (String str : strs) {
            if(!str.startsWith(prxfix)) {
                return false;
            }
        }
        return true;
    }

}

复杂度分析
- 时间复杂度：O(n²) 理想情况下找出最小字符串，然后遍历数组校验前缀是否匹配，最坏的情况就是数组中所有元素都一样，因此遍历匹配就会变成暴力的双层校验
- 空间复杂度：O(1)

👻方法2：技巧法（排序：比较最长和最短）

分析：通过将字符串进行排序，然后比较最短的字符和最长的字符的最大公共前缀即可

例如：["flower","flow","flight"] 字符串排序后：[]

/**
 * 14 最长公共前缀
 */
public class Solution2 {

    /**
     * 思路：先对字符串数组进行排序，然后只需要比较最短和最长字符串这两个元素的最大前缀
     */
    public String longestCommonPrefix(String[] strs) {

        String maxPrefix = "";

        // 对字符串数组进行排序
        Arrays.sort(strs);

        // 获取最短和最长的两个元素（首位）
        String minStr = strs[0];
        String maxStr = strs[strs.length - 1];

        maxPrefix = minStr; // 理想情况下maxPrefix是最小的字符串

        // 定义游标位置（记录最大前缀的位置）
        int idx = 0;
        for (int i = 0; i <= minStr.length(); i++) {
            // 如果最大的字符串包括了这个前缀部分，则可以继续后移
            if (maxStr.startsWith(minStr.substring(0, idx))) {
                idx++;
            } else {
                // 不包括说明不符合
                return minStr.substring(0, idx - 1);
            }
        }

        return maxPrefix;
    }

}

复杂度分析
- 时间复杂度：
- 空间复杂度：

🟡21-反转字符串中的单词（151）

1.题目内容

给你一个字符串 s ，请你反转字符串中单词的顺序。

单词是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的单词分隔开。

返回单词顺序颠倒且单词之间用单个空格连接的结果字符串。

**注意：**输入字符串 s中可能会存在前导空格、尾随空格或者单词间的多个空格。返回的结果字符串中，单词间应当仅用单个空格分隔，且不包含任何额外的空格。

示例 1：

输入：s = "the sky is blue"
输出："blue is sky the"

示例 2：

输入：s = "  hello world  "
输出："world hello"
解释：反转后的字符串中不能存在前导空格和尾随空格。

示例 3：

输入：s = "a good   example"
输出："example good a"
解释：如果两个单词间有多余的空格，反转后的字符串需要将单词间的空格减少到仅有一个

2.题解思路

👻方法1：字符串切割+反向遍历

切割字符串（需注意可能存在多个连续空格的情况，需要引入正则表达式进行限定）

/**
 * 151 反转字符串中的单词
 */
public class Solution1 {
    /**
     * 思路分析：字符串切割思路：先把单词拆出来，然后逆序遍历单词数组
     */
    public String reverseWords(String s) {
        // 定义结果
        StringBuilder res = new StringBuilder();

        // 字符串切割，拆分单词(注意首尾空格和连续空格的情况)
        s = s.trim(); // 去除首尾空格
        String[] words = s.split("\\s+"); //  s.split(" ") 单个空格切分

        // 逆序遍历，插入结果集
        for (int i = words.length - 1; i >= 0; i--) {
            res.append(words[i]);
            // 单词补充空格（如果遍历到最后一个单词则不需要补充）
            if (i > 0) {
                res.append(" ");
            }
        }

        // 返回结果
        return res.toString();
    }
}

复杂度分析
- 时间复杂度：
- 空间复杂度：

👻方法2：字符串切割（split）+反转（reverse）+拼接（join）

思路：和思路1类似，此处完全依靠Java工具类（语言特性）完成操作

public class Solution2 {
    /**
     * 思路分析：字符串切割思路
     * 字符串切割（split） + 反转（reverse） + 拼接（join）
     */
    public String reverseWords(String s) {

        // 1.切割字符串（注意首尾空格和连续空格的处理）
        String[] words = s.trim().split("\\s+");

        // 2.反转数组
        List<String> list = Arrays.asList(words);
        Collections.reverse(list);

        // 3.拼接返回
        return String.join(" ", list);
    }
}

复杂度分析
- 时间复杂度：
- 空间复杂度：

🟡22-Z字形变换（6）

1.题目内容

将一个给定字符串 s 根据给定的行数 numRows ，以从上往下、从左到右进行 Z 字形排列。

比如输入字符串为 "PAYPALISHIRING" 行数为 3 时，排列如下：

P   A   H   N
A P L S I I G
Y   I   R

之后，你的输出需要从左往右逐行读取，产生出一个新的字符串，比如："PAHNAPLSIIGYIR"。

请你实现这个将字符串进行指定行数变换的函数：

string convert(string s, int numRows);

示例 1：

输入：s = "PAYPALISHIRING", numRows = 3
输出："PAHNAPLSIIGYIR"

示例 2：

输入：s = "PAYPALISHIRING", numRows = 4
输出："PINALSIGYAHRPI"
解释：
P     I    N
A   L S  I G
Y A   H R
P     I

示例 3：

输入：s = "A", numRows = 1
输出："A"

2.题解思路

👻方法1：规律法

结合题意，问题的核心可以梳理为两部分：

【步骤1】将元素放在合适的位置（例如此处可以用二维数据或者List<StringBuffer>来存储）（需考虑指定行数的边界情况，如果numRows<2直接返回即可）
【步骤2】遍历元素（遍历生成的集合）

/**
 * 006 Z字形变换
 */
public class Solution1 {
    /**
     * Z 字形变换：实际就是将字符串按照顺序存放到一个二维数组中
     * 此处的二维数组：可以用一个List<StringBuffer>来平替，便于操作
     */
    public String convert(String s, int numRows) {

        // 对边界进行处理
        if(numRows < 2) return s;

        // 定义一个集合分别存储行的数据，通过flag来指定当前行(此处使用StringBuilder便于拼接，也可以用二维数组)
        List<StringBuilder> list = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            list.add(new StringBuilder());
        }

        int idx = 0;// 记录当前插入行的位置
        int flag = -1; // 一个操作标识
        // 遍历元素，然后将其插入集合合适的位置
        for (int i = 0; i < s.length(); i++) {
            // 插入指定元素
            StringBuilder curRow = list.get(idx); // 获取当前插入行
            curRow.append(s.charAt(i)); // 插入元素

            // 如果遇到行的上下边界则需要进行切换(此处Z型反转的逻辑需注意处理)
            if (idx == 0 || idx == numRows - 1) {
                flag = -flag; // 取相反数，表示切换+1、-1操作（遇到上边界则后面的操作是+1、遇到下边界则后面的操作是-1）
            }

            // 更新插入的行位置
            idx = idx + flag;
        }

        // 遍历处理好的元素（按行输出）
        StringBuilder res = new StringBuilder();
        for (StringBuilder sb : list) {
            res.append(sb);
        }
        // 返回结果
        return res.toString();
    }

}

复杂度分析
- 时间复杂度：初始化容器需要时间、遍历封装需要时间、遍历读取需要时间，整体看为O(n)
- 空间复杂度：需要一个List<StringBuilder>进行存储，其大小取决于指定行数、字符串大小

核心思路：
- 【1】定义一个和target等大的窗口
- 【2】通过这个窗口截取源字符串，然后进行校验

/**
 * 028 找出字符串中第一个匹配项的下标
 */
public class Solution1 {

    /**
     * 思路：快速判断target字符串是否为原字符串的一部分，如果不是则返回-1，如果是则找出其索引
     * 滑动窗口思路：定义一个和target等大的窗口，因此滑动校验目标字符串是否存在target
     */
    public int strStr(String haystack, String needle) {
        // 定义一个滑动窗口的开始和结束索引的起始位置
        int start = 0;
        int end = needle.length();

        // 遍历字符串，确认target是否存在（当end滑到右侧表示遍历结束）
        while(end<=haystack.length()) { // 注意边界条件
            // 判断窗口是否和target匹配，如果匹配则返回
            if(haystack.substring(start,end).equals(needle)) {
                return start;
            }
            // 如果没有找到合适的值，则窗口继续向右移动
            start ++;
            end ++;
        }
        // 无响应结果
        return -1;
    }
}

复杂度分析
- 时间复杂度：O(n)（n为源字符串长度）
- 空间复杂度：O(1)

👻方法2：投机取巧法（indexOf）

class Solution {
    public int strStr(String haystack, String needle) {
        return haystack.indexOf(needle);
    }
}

复杂度分析
- 时间复杂度：
- 空间复杂度：

复杂度分析
- 时间复杂度：
- 空间复杂度：

昵称

邮箱

网址

按正序
按倒序
按热度

hot150-01-数组/字符串

预览: