《LeetCode Hot100》 Day01

Day01

1. 轮转数组

思路：

（1） 使用O(1) 空间复杂度解决，就需要原地解决，不能创建新的数组。

（2） 先整体反转数组，再反转前k个数，再反转剩下的数。即可完整本题。

（3） 所以需要定义一个方法实现反转这个功能，该方法接受三个参数：数组，起始索引，终止索引。

完整代码如下：

class Solution {
​public void rotate(int[] nums, int k) {
​
•    int n = nums.length;
​
•    k %= n; // 轮转 k 次等于轮转 k%n 次
​
•    reverse(nums, 0, n - 1);
​
•    reverse(nums, 0, k - 1);
​
•    reverse(nums, k, n - 1);
​}
​private void reverse(int[] nums, int i, int j) {
​
•    while (i < j) {
​
•      int temp = nums[i];
​
•      nums[i++] = nums[j];
​
•      nums[j--] = temp;
​
•    }
​}
​
}

1. 在排序数组中查找元素的第一个和最后一个位置

思路：

（1） 从前往后依次遍历，找到目标值在数组中第一次出现的位置，终止此次循环。

（2） 从后往前遍历，找到目标值在数组中最后一次出现的位置，终止此次循环。

代码：

 class Solution {
​
•    public int[] searchRange(int[] nums, int target) {
​
•      int start = -1;
​
•      int end = -1;
​
•      int length = nums.length;
​
•      // 查找开始位置
​
•      for (int i = 0; i < length; i++) {
​
•        if (nums[i] == target) {
​
•          start = i;
​
•          break; // 找到第一个位置后可以结束
​
•        }
​
•      }
​
•      // 查找结束位置
​
•      for (int i = length - 1; i >= 0; i--) {
​
•        if (nums[i] == target) {
​
•          end = i;
​
•          break; // 找到最后一个位置后可以结束
​
•        }
​
•      }
​
•      return new int[] {start, end};
​
•    }
​}

1. 字符串解码

   

思路：

（1） 从前往后遍历字符串，如果当前字符是字母，则直接添加到res字符串中。

（2） 如果当前字符是'['，则将当前res存储到特定栈中，并将multi也存储到对应的特定栈中。并重置res和multi。

（3） 如果当前字符是']'，则将栈中的res和multi都取出来，其中res重复multi次，添加到一个temp字符串中。

（4） 如果当前字符是数字，则将multi的值*10再加上当前的数字，乘以10的目的是为了当数字为多位数时，确保正确拼接为一个正确的数字。

代码：

class Solution {
​public String decodeString(String s) {
​
•    StringBuilder res = new StringBuilder();  // 存储当前解码的结果
​
•    int multi = 0;               // 当前重复次数
​
•    LinkedList<Integer> stack_multi = new LinkedList<>();  // 存储之前的重复次数
​
•    LinkedList<String> stack_res = new LinkedList<>();    // 存储之前的解码结果
​
•    // 遍历每个字符
​
•    for(Character c : s.toCharArray()) {
​
•      if(c == '[') {
​
•        // 遇到 '[' 时，先保存当前的重复次数和解码结果
​
•        stack_multi.addLast(multi);  // 保存当前的重复次数
​
•        stack_res.addLast(res.toString());  // 保存当前解码结果
​
•        multi = 0;  // 重置重复次数
​
•        res = new StringBuilder();  // 重置解码结果
​
•      }
​
•      else if(c == ']') {
​
•        // 遇到 ']' 时，进行解码操作
​
•        StringBuilder temp = new StringBuilder();
​
•        int cur_multi = stack_multi.removeLast();  // 获取并移除之前保存的重复次数
​
•        for(int i = 0; i < cur_multi; i++) {
​
•          temp.append(res);  // 将当前结果重复指定次数
​
•        }
​
•        res = new StringBuilder(stack_res.removeLast() + temp);  // 拼接之前的解码结果和重复部分
​
•      }
​
•      else if(c >= '0' && c <= '9') {
​
•        // 如果是数字，将其转换为数字并更新重复次数
​
•        multi = multi * 10 + Integer.parseInt(c + "");
​
•      }
​
•      else {
​
•        // 如果是字母，直接添加到当前的解码结果中
​
•        res.append(c);
​
•      }
​
•    }
​
•    return res.toString();  // 返回最终解码的字符串
​}
​
}