LeetCode75 Day3

151.反转字符串中的单词

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

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

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

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

示例 1：

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

示例 2：

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

示例 3：

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

提示：

  • 1 <= s.length <= 104
  • s 包含英文大小写字母、数字和空格 ' '
  • s 中 至少存在一个 单词

进阶：如果字符串在你使用的编程语言中是一种可变数据类型，请尝试使用 O(1) 额外空间复杂度的 原地 解法。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
//反转字符串函数
void reverse(char* s, int start, int end) {
    while (start < end) {
        char temp = s[start];
        s[start++] = s[end];
        s[end--] = temp;
    }
}

char * reverseWords(char * s){
    // 1. 移除多余空格
    int len = strlen(s);
    int fast = 0, slow = 0;
    // 移除字符串之前的空格
    while (s[fast] == ' ') {
        fast++;
    }
    // 移除单词之间多余的空格
    while (fast < len - 1) {
        if (s[fast] == ' ' && s[fast + 1] == ' ') {
            fast++;
        } else {
            s[slow++] = s[fast++];
        }
    }
    // 移除字符串后面的空格
    if (s[fast] == ' ') {
        s[slow] = '\0';
    } else {
        s[slow++] = s[fast];
        s[slow] = '\0';
    }

    
    // 2. 反转整个字符串
    reverse(s, 0, slow - 1);

    
    // 3. 反转每一个单词
    for (int i = 0; i < slow; i++) {
        int j = i;
        while (j < slow && s[j] != ' ') {
            j++;
        }
        reverse(s, i, j - 1);
        i = j;
    }

    return s;
}

作者：TaiSui
链接：https://leetcode.cn/problems/reverse-words-in-a-string/solutions/2094189/151fan-zhuan-zi-fu-chuan-li-de-dan-ci-by-arjw/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
  1. 移除多余空格：
    • 使用两个指针 fast 和 slow 来遍历字符串 s。
    • fast 指针用于找到第一个非空格字符的位置，将其复制到 slow 指针所指向的位置，并同时递增两个指针。
    • 当遇到连续的空格时，fast 指针继续递增直到找到一个非空格字符。
    • 这样就实现了移除单词之间多余的空格，并将结果保存在原始的字符串 s 中。
  2. 反转整个字符串：
    • 使用 reverse 函数来反转整个字符串，调用方式为 reverse(s, 0, slow - 1)。
    • 这个 reverse 函数会将 s 中从索引 0 到 slow - 1 的部分进行反转。
  3. 反转每一个单词：
    • 使用一个循环来遍历字符串 s。
    • 当遇到空格或者到达字符串末尾时，就找到了一个单词的结束位置。
    • 调用 reverse 函数来反转当前单词的字符，调用方式为 reverse(s, i, j - 1)，其中 i 是当前单词的起始位置，j 是当前单词的结束位置（不包括空格）。
    • 然后更新循环变量 i 为 j，以继续寻找下一个单词。

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

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

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

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

示例 1:

1
2
输入: nums = [1,2,3,4]
输出: [24,12,8,6]

示例 2:

1
2
输入: nums = [-1,1,0,-3,3]
输出: [0,0,9,0,0]

提示：

  • 2 <= nums.length <= 105
  • -30 <= nums[i] <= 30
  • 保证 数组 nums之中任意元素的全部前缀元素和后缀的乘积都在 32 位 整数范围内

进阶：你可以在 O(1) 的额外空间复杂度内完成这个题目吗？（ 出于对空间复杂度分析的目的，输出数组 不被视为 额外空间。）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
int* productExceptSelf(int* nums, int numsSize, int* returnSize) int* productExceptSelf(int* nums, int numsSize, int* returnSize) {
	*returnSize = numsSize;
	int *result = (int*)malloc(sizeof(int) * numsSize);
	int i = 0, temp = 1;
	for(i = 0; i < numsSize; i++)
	{
		result[i] = temp;
		temp *= nums[i];
	}
    temp = 1;
    for(i = numsSize - 1; i >= 0; i--)
    {
    	result[i] *= temp;
    	temp *= nums[i];
    }
    return result;

  1. 首先，函数通过 malloc 动态分配了一个大小为 numsSize 的整型数组 result，用于存储最终的结果。同时将 returnSize 指向的位置设置为 numsSize，表示返回的数组大小为原始数组的大小。
  2. 接着，代码进入第一个循环，遍历原始数组 nums。在这个循环中，通过变量 temp 记录当前元素之前所有元素的乘积。遍历过程中，将 temp 的值乘以当前元素之前所有元素的乘积，并将结果存储到 result 数组对应的位置。这样，第一个循环结束后，result 数组中存储的是每个元素之前所有元素的乘积。
  3. 然后，代码进入第二个循环，这次从数组的最后一个元素开始向前遍历。在这个循环中，通过变量 temp 记录当前元素之后所有元素的乘积。遍历过程中，将 temp 的值乘以当前元素之后所有元素的乘积，并将结果与之前存储在 result 数组中的值相乘，更新 result 数组对应位置的值。这样，第二个循环结束后，result 数组中存储的是每个元素之前所有元素和之后所有元素的乘积。
  4. 最后，函数返回 result 数组，完成了对原始数组的处理并得到了结果数组。

还有一种代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */

int ra[100000];

int* productExceptSelf(int* nums, int numsSize, int* returnSize){
    for(int i = 0; i < numsSize; i++){
        ra[i] = 1;
    }

    int pre = 1, suf = 1;
    for(int i = 1; i < numsSize; i++){
        pre *= nums[i - 1];
        suf *= nums[numsSize - i];
        ra[i] *= pre;
        ra[numsSize - i - 1] *= suf;
    }
    *returnSize = numsSize;
    return ra;
}

作者：随心
链接：https://leetcode.cn/problems/product-of-array-except-self/solutions/2254723/238-chu-zi-shen-yi-wai-shu-zu-de-cheng-j-xfqm/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
  1. 首先，代码定义了一个全局数组 ra，用于存储最终的结果。这个数组的大小被设置为 100000，可以存储较大规模的结果。
  2. 接着，在第一个 for 循环中，将 ra 数组中的所有元素初始化为1。这是为了在后续的计算中，每个元素都能乘以一个初始值。
  3. 然后，代码定义了两个变量 pre 和 suf，分别用于记录当前元素前面所有元素的乘积和当前元素后面所有元素的乘积。这两个变量初始化为1。
  4. 进入第二个 for 循环，这里的循环从索引1开始，因为第一个元素的前面没有元素了。在这个循环中，代码通过不断更新 pre 和 suf 的值，来计算当前元素之前所有元素的乘积和之后所有元素的乘积。
  5. 在每次循环中，代码将 pre 乘以当前元素的前一个元素，并将 suf 乘以当前元素的后一个元素。然后，将这两个乘积分别与 ra 数组中对应位置的元素相乘，并将结果保存到 ra 数组中对应的位置。
  6. 最后，函数将 numsSize 赋值给 returnSize，表示返回的数组大小为原始数组的大小，并返回 ra 数组。

这段代码定义了一个大小为 100,000 的静态整型数组 ra。它可能用于存储计算结果，但是在实际情况中，它可能会导致内存溢出或者其他问题，因为数组的大小未知，同时最后，函数设置了返回数组的大小，并返回指向 ra 的指针。但是这里的问题是，ra 是一个本地数组，它的内存生存期在函数返回时结束，因此返回指向它的指针是不安全的，应该使用动态内存分配（例如 malloc()）来分配一个新的数组来存储结果。