leetcode

移除数组的重复元素

首先处理特殊情况：如果数组长度为0，直接返回；
因此从下标1开始处理数组，由于给定的数组 nums 是有序的，对于i <= k <= j ，有nums[i]=nums[k]=nums[j]
设置快慢指针slow ,fast, 均从1开始，nums[0~slow-1]是不重复的被保留数组元素
若nums[fast] != nums[slow - 1]，则说明当前元素与被保留数组的元素都不一样，可以纳入被保留数组直接让nums[slow] = nums[fast]

移除数组的重复元素2

处理特殊情况：如果数组长度< 2，直接返回；
从下标2开始处理数组，快慢指针slow,fast均为2,nums[0~slow-1]是能够被保留的数组元素
若nums[fast] != nums[slow - 2]，也就是说如果当前元素与被保留的元素中倒数第二个元素不一样，那么说明该元素与被保留数组的最后两位元素都不一样，可以纳入被保留数组，即让nums[slow] = nums[right]，slow++

多数元素

给定一个大小为 n 的数组 nums ，返回其中的多数元素。多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。
以O(N)的时间复杂度，O(1)的空间复杂度解决。
这是我目前看到的最直观形象的解法，时间复杂度O(n)，空间复杂度O(1)。
“同归于尽消杀法” ：
由于多数超过50%, 比如100个数，那么多数至少51个，剩下少数是49个。
a. 第一个到来的士兵，直接插上自己阵营的旗帜占领这块高地，此时领主 winner 就是这个阵营的人，现存兵力 count = 1。
b. 如果新来的士兵和前一个士兵是同一阵营，则集合起来占领高地，领主不变，winner 依然是当前这个士兵所属阵营，现存兵力 count++；
c. 如果新来到的士兵不是同一阵营，则前方阵营派一个士兵和它同归于尽。 此时前方阵营兵力count –。（即使双方都死光，这块高地的旗帜 winner 依然不变，因为已经没有活着的士兵可以去换上自己的新旗帜）
d. 当下一个士兵到来，发现前方阵营已经没有兵力，新士兵就成了领主，winner 变成这个士兵所属阵营的旗帜，现存兵力 count ++。
就这样各路军阀一直以这种以一敌一同归于尽的方式厮杀下去，直到少数阵营都死光，那么最后剩下的几个必然属于多数阵营，winner 就是多数阵营。（多数阵营 51个，少数阵营只有49个，死剩下的2个就是多数阵营的人）

字母异位词分组

给你一个字符串数组，请你将 字母异位词 组合在一起。可以按任意顺序返回结果列表。字母异位词 是由重新排列源单词的所有字母得到的一个新单词。

示例 
输入: strs = ["eat", "tea", "tan", "ate", "nat", "bat"]
输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

字符串排序方法

把所有字符串都按字母表进行排序，含有相同字母的字符串都会变成一样的顺序，如eat -> aet , tea -> aet ，再创建从字符串映射到字符串容器的哈希表，遍历字符串数组，把相同字符串映射到同一个容器中。 时间复杂度O(nklogk) ，空间复杂度O(n)

字符串计数器方法

a. 使用哈希表。键为计数排序字符串key，这个技术排序字符串key的意思是按照字母顺序表排序，同时每个字母会注明出现次数，比如”cat” “atc” 对应的字符串为 “a1c1t1”；值为字符串数组。
b. 遍历输入的字符串数组中的每一个字符串，转换为key，然后放到哈希表对应的位置。
c. 最后把哈希表的所有值即字符串数组放到结果返回。
时间复杂度为O(nk)，每个字符串都需要转化为计数排序字符串。
空间复杂度为O(n),需要使用哈希表存储

接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。

输入：height = [0,1,0,2,1,0,1,3,2,1,2,1]
输出：6
解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图，在这种情况下，可以接 6 个单位的雨水（蓝色部分表示雨水）。 
示例 2：
输入：height = [4,2,0,3,2,5]
输出：9

1.动态规划

维护两个数组，leftmax[n], rightmax[n]，leftmax数组每个元素代表的是左边到该下标为止最高的高度，rightmax数组每个元素则是右边最高的高度。
设置一个sum变量用来计数总雨水量，遍历height数组，每个元素能容纳的雨水单位为min (leftmax[i], rightmax[i]) - height[i]
时间复杂度为O(n),空间复杂度为O(n)

2.双指针

动态规划需要O(n)空间复杂度，设置一个雨水总容纳量sum,设置left和right指针分别从最左和最右边开始，设置leftMax和rightMax分别代表左边的最高值和右边的最高值；left往右，right往左，直到相遇时停止。
类似于两队人打擂台赛（没有体力消耗），永远都是最强的留在场上（继续守擂）
直到有另一个更强的击败他成为全场最强（全场最强同时也是他所在队伍目前出场的最强）
举例，有A队和B队
B队攻擂成功->B队当前攻擂人比A队所有人都厉害
curB > curA -> curB > Max(A) -> MAX(B) > Max(A)
A队守擂成功->A队当前守擂人比B队所有人都厉害
curA > curB -> curA > Max(B) -> Max(A) > MAX(B)
也就是说，如果当前左边的高度小于右边的高度，说明右边依旧是当前最高的，可以计算左边格子容纳的水量，不用担心左指针的右边太矮，因为最终右边会由右指针的最高或者左指针的最高来支撑

找到字符串中所有字母异位词

给定两个字符串 s 和 p，找到 s 中所有 p 的 异位词 的子串，返回这些子串的起始索引。不考虑答案输出的顺序。
异位词 指由相同字母重排列形成的字符串（包括相同的字符串）。

输入: s = "cbaebabacd", p = "abc"
输出: [0,6]

解释:
起始索引等于 0 的子串是 “cba”, 它是 “abc” 的异位词。
起始索引等于 6 的子串是 “bac”, 它是 “abc” 的异位词。
设置一个count数组记录p中所有字母的个数，用left、right指针来维护一个窗口的左右边界，然后遍历s。
先将字母c放入窗口，对应的count[c]减1，然后进行判断窗口中是否有多余的字母，这个多余的判断使用count[c]是否小于0，小于0说明目前装入的字母不是我们需要的字母或者已经超过异味词所需字母数量，从left指针处开始拿出字母，直到满足count[c]不小于0；在每一轮的最后判断当前窗口大小是否等于异位词长度，是则将left指针放入结果集。
空间复杂度O(k),时间复杂度O(n)