啰嗦

背景：以前学过理解过，相当于复习一遍。但很久没刷题了，忘得差不多
目的：通过代码随想录的网站速成算法，试水暑期实习
难度系数：4/5
目标：十天速成lc100

1. 数组、链表的复习

  • 数组是连续的，增删只是障眼法，移动两下子，没真消失。
  • 那二维数组？C++里是连续的。java不是，请看大屏幕
    alt text
  • 优雅的取中间
    1
    int middle = left + ((right - left) / 2)
  • 边界问题：看区间存在不，区间存在就取=
  • 错误案例1：删除元素，没有理解数组空间是连续的，假删除
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    class Solution {
        public int removeElement(int[] nums, int val) {
            int size=nums.length;
            for(int i=0;i<nums.length;i++)//数组长度不变的好吧，是size在变，判断ij要用size的
            {
                int f=nums[i];
                if(f==val)
                {
                    for(int j=i;j<nums.length-1;j++)//同理的
                    {
                        nums[j]=nums[j+1];

                    }
                    
                    i--;
                    size--;

                }
            }
            return size;
        }

    }
  • 优雅的数组删除：快慢指针。快指针找嗷嗷待哺的新家伙，慢指针是最终新数组。不等于val的时候，把快加入慢。等于val的时候，不加入慢，所以快继续跑。
  • 滑动窗口：其实一直在移动左边界。
  • https://leetcode.com/problems/minimum-size-subarray-sum/

做了三个题，走了。
25.2.21 23：00

滑动窗口

窗口内是什么？
如何移动窗口的起始位置？
如何移动窗口的结束位置？

lc 3

滑动窗口+哈希。
哈希记录的是字母最后出现的位置。遇到重复字符时，更新左边，
判断：如果发现当前元素哈希有值，说明出现过。我们取出这个值，如果大于等于start，说明出现在窗口内，要更新（原重复处+1）。如果小于，说明不在窗口内，不用更新左值。
由于滑动窗口是动态移动的，start 指针可能会移动到某个字符的上次出现位置之后。