leetcode学习2

Hash

1、两数之和 hash

49、字母异位次分组 hashMap

char[] chars = s.toCharArray();

Arrays.sort(chars);

String str = Arrays.toString(chars);

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

输出: [["bat"],["nat","tan"],["ate","eat","tea"]]

128、最长连续序列 hashSet 遍历数组把所有的数字存起来， 然后遍历数组，找hashset的临近数字while循环去找

双指针：

283. 移动零 交换

11. 盛最多水的容器 左右指针，遍历，抛弃短板才能有有光明的未来

15. 三数之和

先对数组排序，之后，遍历数组，左右指针，左指针等于i的下一位，右指针等于最右边， 计算和等于左指针+右指针+当前元素i的值，

当sum小于0，l++, sum大于0:r--，等于0，l和r同时缩进，注意等于0的时候需要收缩左右指针，去掉相同的元素

42. 接雨水 每个元素找左边的最大值和右边的最大值，

滑动窗口：

3. 无重复字符的最长子串

rk=-1,hash存遍历过的元素，每次遍历到i的时候，删除i-1的元素，rk从rk+1开始往右走，只要元素不在set里面就往set加1，计算rk到i的长度，比max大则刷新

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

给定两个字符串 s 和 p，找到 s中所有 p的 异位词的子串，返回这些子串的起始索引。不考虑答案输出的顺序。

输入: s = "cbaebabacd", p = "abc"

输出: [0,6]

思路：rk=-1 同上，两个26字母数组分别用于记录s和p的字母出现的个数，遍历s，每次遍历到i的时候，删除i-1的元素，rk从rk+1开始往右走，while循环只要s元素的数量小于p元素的数量则rk++，计算rk到i的长度，等于p的长度，则存储i的结果

子串：

560. 和为 K 的子数组 前缀和+HashMap

239 滑动窗口的最大值 优先队列（大顶堆，注意java默认的优先级队列小顶堆），存的是一个2长度的数组，一个用于存数字，一个用于存位置，遍历，移除队列顶部的索引小于i-k的元素，把队列顶部的值取出来就可以了

76. 最小覆盖子串

自定义一个128数组charArray，用于记录t的字符出现的次数的负数。

遍历S，j和i的初始=0,j相当于窗口的左指针负责收缩窗口在每次i遍历的时候，

i每次遍历都往charArray里面++，当加完后小于等于0，则cnt++, j则负责往右走，发现charArray的元素大于0，则j++同时charArray的元素-1，

最后计算一下i到j的长度比上一个长度小，则刷新

普通数组

53. 最大子数组和 前缀和

56. 合并区间 List<int[]> 定义一个数组的列表，然后对输入排序按照第一个数字的值，合并的话，只用看当前元素和List的最后一个元素的比较，比较的是第一个元素的第1位和第二个元素的第0位，小于，则不能合并，

否则取最大值

189. 轮转数组 三次reverse

238. 除自身以外数组的乘积 定义三个数组，一个放结果，一个放左边的所有元素的乘积，一个放右边的左右元素的乘积，res等于左乘以右

41. 缺失的第一个正数

思路：只用找第i个元素的位置的数字的值小于等于数组的长度的元素，这样的元素给他放到合适的位置上，数字123..n应该放在0,1,2,,,,n-1的索引位置上，至于大于数组长度的元素，比如数组长度是5，对于数字8,我就不用关心了

对于这样的元素i，用while循环，将他交换到合适的位置nums[i] - 1上。

最后遍历数组，找到第一个nums[i]!=i+1的位置就是缺失的第一个正数。

动态规划：

爬楼梯、杨辉三角、打家劫舍、完全平方数、零钱兑换

279：完全平方数，典型的背包问题，平方数的和为n的平方数的最小个数，把和作为一个数组的边界

public int numSquares(int n) {

// 完全平方数可以选一个或多个。求和为n的最小的完全平方数的个数

// 思路：和为i的完全平方数的值一定是在1到根号i(i的平方根)，及只有一个数那就是根号i,有多个数那肯定就小于根号i了

// 那么我们遍历j，j的范围在1到根号i，问题就转化为求和为i-j的平方的最小平方数个数，于是状态转移方程就出来了

int[] dp = new int[n + 1];

dp[0] = 0;

dp[1] = 1;

for (int i = 2; i <= n; i++) {

int min = Integer.MAX_VALUE;

for (int j = 1; j * j <= i; j++) {

min = Math.min(dp[i - j * j]+1, min);

}

dp[i] = min;

}

return dp[n];

}

139. 单词拆分

一维动态规划：dp[i]--》s的前i个字符串是否可以由字典中单词拆分而成，

两个for循环，一个遍历i，一个遍历字典，dp[i] = dp【i-字典字符串】&&s[0,i]以字典字符串结尾。

300. 最长递增子序列， 注意这个子序列不是连续的

一维的动态规划，求最长严格递增序列的长度，dp i表示前i个元素,且以i结尾的的最长子序列的长度，那么dp i等于dpj + 1，j等于i往左数第一个小于num i的元素的位置，如果找不到，那就是1，也就是自己是一个序列

dp[i] = Math.max(dp[j] + 1, dp[i]); 注意最后要把所有的dp i汇总求最大的maxRes

152. 乘积最大子数组

因为有正数和负数，所以需要两个数组，dpmax一个用来存放以i结尾的连续子数组的最大值，dpmin一个用来存以i结尾的连续子数组的最小值，如果i是正数则找dpmax i-1 ，如果i是负数则找dpmin找i-1

最后汇总，求最大值

416 分割等和子集

换一个思路，相当于求和为总和一半的子序列，也就是背包问题了

背包问题的做法是什么？dp[i][j]表示前i个物品是否能达到重量或者和为j,i表示元素的索引，j表示背包的重量，相当于求M个物品，每个物品的重量已知的，是否能选出来几个把背包装满。

多维动态规划

62.不同路径

二维动态规划dpij表示走到ij的路径数，最终的路径数等于上面+左边的

64. 最小路径和

二维动态规划dpij表示走到ij的最小路径和，则dpij等于上面的路径+gridij 和 左边的的路径+gridij 两者取最小值

5、最长回文子串

boolean[][] dp，其中dpij表示从i开始到j的元素区间是否是回文字符串

1143. 最长公共子序列

给定两个字符串，求最长的公共子序列，dpij表示s的前i个字符串和t的前j个字符串的最长公共子串，当i和j的字符相等时，等于dp[i - 1][j - 1] + 1，否则等于Math.max(dp[i - 1][j], dp[i][j - 1])

72. 编辑距离

dpij表示word1的前i个元素和word2的前j个元素的最小编辑距离，不管i和j的元素等不等，都需要计算dp[i - 1][j] + 1, dp[i][j - 1] + 1，

还需要计算如果i和j的元素相等，则要加上看dp[i - 1][j - 1]，如果不等则看dp[i - 1][j - 1] + 1，如下所示：

dp[i][j] = Math.min(dp[i - 1][j] + 1, dp[i][j - 1] + 1);

if (word1.charAt(i - 1) == word2.charAt(j - 1)) {

dp[i][j] = Math.min(dp[i - 1][j - 1], dp[i][j]);

} else {

dp[i][j] = Math.min(dp[i - 1][j - 1] + 1, dp[i][j]);

}

贪心算法

121. 买卖股票的最佳时机

从右往左遍历，找到右边的最大值，然后右边的最大值减去当前的元素的值就是当前元素的最佳股票售价，最后汇总求所有元素的股票

55. 跳跃游戏

思路：用一个变量遍历到当前元素时可以达到的最大距离maxEnd。初始的时候等于0，maxEnd 的值刷新的条件是i的位置在 maxEnd的区间内，那么maxEnd = Math.max(i + nums[i], maxEnd);

然后判断如果此时maxEnd的值大于等于nums.length - 1即最后一个元素的下标，则说明可达，返回true

45. 跳跃游戏 II

前提：一定可以跳到n-1

结果是求step,初始等于0，

定义一个position初始等于n-1,那么我就从左边往右边遍历，找到第一个元素i可达到这个position的，此时刷新posion的位置为当前这个元素i.同时step++，

只要posion的位置大于0,我就继续上面的遍历。

763. 划分字母区间

给定一个字符串S，分为尽可能多的片段，同一字母最多出现在一个片段中。

思路：用一个数组charArray存下来字母的最后一次出现的位置。用一个变量记录当当前元素为止的所有元素的最右位置

然后我去遍历这个字符串，对于当前元素i，lastIndex = Math.max(lastIndex, charArray[s.charAt(i) - 'a']);

如果i等于lastIndex。记录长度i - begin + 1 就是要求的结果，刷新begin

技巧：

136. 只出现一次的数字

只有一个数字是只出现一次，其他的只出现2次，方法是所有的数组的值相异或^=，求得最后的结果就是那个只出现一次的数字

169. 多数元素 多数元素是指在数组中出现次数 大于 ⌊ n/2 ⌋ 的元素。

// 排序

Arrays.sort(nums);

// 求中间位置的元素

return nums[nums.length/2];

75. 颜色分类

只包含0 1 2的元素数组，把数字按照0 1 2的顺序排列。

方法：交换法，遍历数组把0交换到前面。再遍历数组把1交换到前面，剩下的就都是2了

int k=0;

for(int i=0;i<nums.length;i++){

if(nums[i]==0){

swap(nums,i,k);

k++;

}

}

int j = k;

for(int i=k;i<nums.length;i++){

if(nums[i]==1){

swap(nums,i,j);

j++;

}

}

31. 下一个排列 求一个数组的下一个字典排列

思路：遍历数组nums，从右往左遍历，如果发现i比i-1的值大，则把i-1的元素和从最右边开始遍历得到的最右的一个次小的元素交换，之后对i到最右边的元素交换

例子：12643321 -》13643221-》13122346

for (int i = nums.length - 1; i > 0; i--) {

if (nums[i] > nums[i - 1]) {

int minGreat = Integer.MAX_VALUE;

int target = i-1;

for (int j = nums.length - 1; j >= i; j--) {

if (nums[j] > nums[i - 1] && nums[j] < minGreat) {

minGreat = nums[j];

target = j;

}

}

swap(nums, i-1, target);

// i到末尾做翻转

reverse(nums, i, nums.length - 1);

return;

}

}

// 数组做逆序排列 12345 54321 1234 4321

for (int i = 0; i < nums.length / 2; i++) {

swap(nums, i, nums.length - 1 - i);

}

287. 寻找重复数 给定一个包含 n + 1 个整数的数组 nums ，其数字都在 [1, n] 范围内（包括 1 和 n），可知至少存在一个重复的整数

把nums[i]放在i的位置上，在放之前如果发现目标位置已经有值了，证明这个数就是重复的数

for (int i = 0; i <= n; i++) {

// 当当前位置的元素不等于索引时，需要将其放到正确的位置

while (nums[i] != i) {

int target = nums[i];

// 如果目标位置已经有了正确的值，说明找到了重复元素

if (nums[target] == target) {

return target;

}

// 交换元素到正确的位置

int temp = nums[target];

nums[target] = nums[i];

nums[i] = temp;

}

}

// 理论上不会到达这里，因为题目保证有重复元素

return -1;

}