算法练习day2
#数据结构 算法练习 2024-04-18

有序数组的平方

代码随想录 有序数组的平方

力扣 977.有序数组的平方

（用时：0.3小时）

这道题很简单，可以用双指针法或者暴力破解。

双指针法

本题允许新构建数组，然后返回值可以是新的数组，因此个人认为才会比较简单。但如果不允许构建数组呢？

  • 题目提供的是一个有序的升序数组，数组中也会有负数和零。整个数组都平方后，数组的大小趋势应该是从两头向中间递减的，如图：
    image-20240418171625395
  • 指针head和tail顾名思义，分别从数组的头和尾开始遍历。
  • 在遍历的时候，比较头和尾的平方大小，大的放入新数组的尾部，不断比较放入，即可得到一个新的升序的平方数组。
  • 注意一下新数组是从后往前赋值的，因此新数组的下标初始值应为数组长度-1.

暴力破解

暴力破解就更简单了。

  • 将原数组按顺序平方后的值放入新数组中。
  • 再对新数组排序既可。

代码实现

暴力破解：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/// <summary>
/// 暴力破解
/// </summary>
/// <param name="nums"></param>
/// <returns></returns>
public int[] SquareOfArrayFun2(int[] nums)
{
    int[] ans = new int[nums.Length];

    for (int i = 0; i < nums.Length; i++)
    {
        ans[i] = nums[i] * nums[i];
    }

    Array.Sort(ans);

    return ans;
}

双指针法：

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
/// <summary>
/// 双指针法
/// </summary>
/// <param name="nums"></param>
/// <returns></returns>
public int[] SquareOfArrayFun1(int[] nums)
{
    int[] ans = new int[nums.Length];
    int head = 0, tail = nums.Length - 1, arrIndex = nums.Length;
    
    while(head <= tail)
    {
        if (nums[head]* nums[head] < nums[tail]* nums[tail])
        {
            ans[--arrIndex] = nums[tail] * nums[tail];
            tail--;
        }
        else
        {
            ans[--arrIndex] = nums[head] * nums[head];
            head++;
        }
    }

    return ans;
}

长度最小的子数组

代码随想录 长度最小的子数组

力扣 209.长度最小的子数组

（用时：0.5小时）

这道题其实难度不高，但是引入了滑动窗口的思想。

滑动窗口

滑动窗口是一个抽象的概念，在不同地方具体是什么都不太也一样。

  • 个人认为窗口其实就是一块“区域”，像是数学的“区间”。
  • 所谓滑动，个人认为是这块区域的起始和终点是可变意思，但是起点和终点始终会保持着起点<=终点这个条件（起点和终点的意义也是这样固定了）。
  • 合起来，滑动窗口可以认为就是一段可变的区间，变化的条件、区间要满足的要求都是人定的。利用这个思想，可以解决一些计算机的问题。

（题外话：滑动窗口也让我想起来计网中的那个滑动窗口hhhh，思想都是很互通呢。）

滑动窗口法

本题本质其实就是要找数组中连续的数字，这些数字连在一起，可以看成一片“区域”。

  • 程序中，可以用两个指针（也不一定是真的指针）表示窗口的起点和终点。让起点和终点按照我们的要求改变，就可以实现查找区域的想法。
  • end指针先向后探索，从start到end这块区域的数相加如果>=target，那么就说明这块区域是符合要求的“子列”。
  • 由于要找最小子列长度，那么单单符合要求并不够，还得比较符合要求的所有子列的长度。此时可以靠start，从目前已经符合要求的start到end的区间中，后移减短子列长度。

start和end配合操作，总结来说：
1.先找到符合要求的子列
2.数一定要连续。依次让起点往后挪，尝试是否有更加“完美”的子列。

重点思考

写的时候，需要重点考虑以下问题：

  • 窗口的start如何定义和改变？
  • 窗口的end如何定义和改变？

个人的一些理解：

  • 窗口的start如何定义和改变？

    start指针主要是用来在现有符合条件的子列上，缩短“优化”子列长度。
    start只有在 s(当前子列和)>=Target时，才能start++以后移
    start能够一直后移，一定是start++后，s(当前子列和)>=Target依旧成立。（不用担心出现start>end而条件还成立的情况。因为s-nums[start]和start++是先后进行的，s的初值是0，target和数组都是正整数，0<正整数。）

  • 窗口的end如何定义和改变？

    end指针主要是用于寻找符合条件的子列，不负责“优化”。
    end只有在找到s(当前子列和)>=Target时，才会停下来，让start“优化”。
    end的边界条件是数组长度。

错误思考

  • 本题写的时候，思路上没有什么阻碍，实现上也是。
  • 但在一个地方出了问题：int的最大值。
  • 以前写习惯了，int的最大值直接定成65535，其实不是。
  • C#中可以用int.MaxValue来替代。

暴力破解法

暴力破解就是双层循环，遍历出所有的可能。

代码实现

滑动窗口法：

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
/// <summary>
/// 滑动窗口法
/// </summary>
/// <param name="target"></param>
/// <param name="nums"></param>
/// <returns></returns>
public int SmallSubarrayFun1(int target, int[] nums)
{
    int start = 0, end = 0, subLen = int.MaxValue, s = 0;
    while(end< nums.Length)
    {
        s += nums[end];
        while (s>=target)
        {
            //先判断并更新目前最短的子列长度
            if (end - start + 1 < subLen)
            {
                subLen = end - start + 1;
            }
            //接着尝试缩短窗口（start后移）
            
            s -= nums[start];
            start++;
        }
        //缩短窗口完毕，继续让end向后探索
        end++;
    }
    if (subLen== int.MaxValue)
    {
        return 0;
    }
    else
    {
        return subLen;
    }
}

拓展思考

如果Target不一定是正整数或数组里包含负数或0呢？