2024.01.19_学习日记
天气：小雨
学习地点：家
学习时长：4h
学习内容
- 网易面试题（lc135进阶）
这个题原版是分发糖果的问题，首先一个小孩分发多少糖果，取决于左边有多少连续比他小的值，也取决于右边有多少连续比他小的值，所以设置两个额外的数组用来放左边和右边两边遍历情况下的当前数值，从1开始，如果右边比左边大，那么加1，如果小或者一样大，继续是1，遍历结束得到左数组，右边的数组也是一样，最后取两个数组的最大值即可。进阶版的就要考虑首尾相连的问题，这个时候就是考虑用局部最小值当作首尾两个值，然后数组按顺序构建新数组解耦掉原数组，然后再分别左右遍历，取最大值即可。 - 小红书笔试题
这个题的思路很简单，就是首先按照红色-蓝色代价排序，然后统计0、红蓝各有多少个，剔除掉奇数、红蓝有大于n/2的情况，然后再首先把蓝色需要多少个才能变成一半算出来，红色同样，先全部变成红色，然后数组遍历蓝色次数，把红变蓝需要的代价减掉就行了。code在这里 - 腾讯笔试题
这个题是进阶版，低阶版是没有偶数这个条件，低阶版首先是排序，然后左右指针，分别遍历，左指针+右指针如果大于limit，右指针左移，res+1，如果小于等于limit，右指针左移，左指针右移，一个while搞定，最后返回res。进阶版就是分成奇偶两个数组，然后按上述方法统计，最后相加即可。 - 题目
子数组是连续的，这个题想到统计以每个位置结尾得时候，有多少个子数组，最后累加。然后想到以i位置结尾的时候，需要找到前缀和为sum-arr【i】的个数，所以前缀和要用一个hashmap统计出来，hashmap里首先要加上一个0：1，因为如果当前数字=sum，前缀和如果没有sum-sum这个0值的话，就会生成0，但其实是1，因为子数组就是i位置这一个数形成得数组。所以遍历一次，每次先看前缀和有几个，然后更新当前和到前缀和里，遍历一次累加ans即可。 - 京东笔试题
要求每一部分01比例一样，先把整体01比例求出来，分割后的肯定也是这个比例，所以用map记录每个位置的前面所有01比例，如果当前整个是该比例，那么看map里有多少个该比例的个数，如果没有，那就是1，如果有就是1+该map数字，同时如果该位置比例有效，那更新map+1，最后返回res数组。