视频课
1.绳子覆盖最多的点数[图片上传失败...(image-2bf857-1649069519567)]
解法1:暴力+贪心
[图片上传失败...(image-c13fd3-1649069519567)]
需要在给出的点往前找,假如找到一个点的末尾 973 -- > 873 L为100 二分早到 logN x N
解法二:滑动窗口
设置左右指针 :
left right
[图片上传失败...(image-a476e-1649069519567)]
public static int maxPoints(int[] arr,int L){
//初始化
int left = 0;
int right =0;
int result = 0;
while(left < arr.length){
//不越界且满足题意
while(right < arr.length && arr[right] - arr[left] <= L){
right++;
}
result = Math.max(result,right - (left++));
}
return result;
}
2.交换(字符放左另外的放右边)
[图片上传失败...(image-3efa06-1649069519567)]
解法1:仿冒泡
只要管G放到左边 O(N)
或者第二条G右边求这俩哪个少
[图片上传失败...(image-75ab1b-1649069519567)]
public static int result(int max1,int max2){
}
public static int maxGleft(String s){
//ending with
if(s == null || s.equal("")){
return 0;
}
char[] str = s.toCharArray();
int step1 = 0;
int gindex = 0;
//find G move first
for(int i = 0 ; i < str.length ; i++){
if(str[i] == 'G' ){
step1 = i - (gindex);
gindex++;
}
}
int step2 = 0;
int bindex = 0;
//find G move first
for(int i = 0 ; i < str.length ; i++){
if(str[i] == 'B' ){
step1 = i - (bindex);
bindex++;
}
}
return Math.max(step1,step2);
}
3.最长递增链长度
[图片上传失败...(image-af6aad-1649069519567)]
4.+ - 方法数
[图片上传失败...(image-d1a8c6-1649069519567)]
题目:
题解:
【宫水三叶】一题四解 : 「DFS」&「记忆化搜索」&「全量 DP」&「优化 DP」 - 目标和 - 力扣（LeetCode） (leetcode-cn.com)
解法1:递归+暴力
class Solution {
public int findTargetSumWays(int[] nums, int target) {
return process1(nums,0,target);
}
public int process1(int[] nums,int index,int rest){
if(index == nums.length){
return rest == 0 ? 1 : 0;
}
return process1(nums,index + 1,rest - nums[index]) +
process1(nums,index + 1, rest + nums[index]);
}
}
[图片上传失败...(image-1f2873-1649069519567)]
[图片上传失败...(image-96cc54-1649069519567)]
解法2：记忆化搜索（DP）
[图片上传失败...(image-9f67eb-1649069519567)]
解法3：
1.arr 非负数
2.sum > target 一定 false
3.奇数偶数不一样
4.正负数分开取集合 P{群是 +} N{都是-数} p,n为他们里面的和
**本质上就是求 p - n = target;****
推到:
p-n + (p+n) = target +(p + n) 🕛 2p = target + sum{all data}; p = (target + sum) / 2;得到我们的正数的和要目标值和 所有数集合的一半
同理:
N
解法4:压缩二维数组表格
[图片上传失败...(image-b6fa5a-1649069519567)]
5.司机获得收入（不太会时DP）[图片上传失败...(image-fd2833-1649069519567)]
[图片上传失败...(image-e9fb85-1649069519567)]
public static int maxIncome(int[][] income){
int N = income.length;
//考虑特殊情况的原则下
//1.空
//2.奇数
//3.为0或者1
if(income == null || (N & 1) !=0 || N < 2){
return 0;
}
int M = N>>1;
//接下面的图片部分
}
[图片上传失败...(image-c7ccdc-1649069519567)]
6.还有Set All（）的哈希表
解读,把``setAll`把对应的key 的值全部为括号内的数字
[图片上传失败...(image-c5b3f6-1649069519567)]
利用时间戳来经行最新的值的修改规定
public class setAll{
}
7.最长无重复字符且最长
思路:定位向左找.
关键字:"字串" 不重复
DP
1.a--->17号位置 要之前没有出现过a
2.17号位置和16号位置的最长有关
不需要设置dp数组因为只需要结果几个
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> dic = new HashMap<>();
int res = 0, tmp = 0;
for(int j = 0; j < s.length(); j++) {
int i = j - 1;
while(i >= 0 && s.charAt(i) != s.charAt(j)) i--; // 线性查找 i
tmp = tmp < j - i ? tmp + 1 : j - i; // dp[j - 1] -> dp[j]
res = Math.max(res, tmp); // max(dp[j - 1], dp[j])
}
return res;
}
}
滑动窗口或双指针都可以叫
class Solution {
public int lengthOfLongestSubstring(String s) {
Map<Character, Integer> dic = new HashMap<>();
int i = -1, res = 0;
for(int j = 0; j < s.length(); j++) {
if(dic.containsKey(s.charAt(j)))
i = Math.max(i, dic.get(s.charAt(j))); // 更新左指针 i
dic.put(s.charAt(j), j); // 哈希表记录
res = Math.max(res, j - i); // 更新结果
}
return res;
}
}
class Solution {
public int lengthOfLongestSubstring(String s) {
if(s == null || s == ""){
return 0;
}
char[] str = s.toCharArray();
int[] map = new int[256];
for(int i = 0 ; i < map.length ; i++){
map[i] = -1;
}
map[str[0]] = 0;
int N = str.length;
int ans = 1;
int pre = 1;
for(int j = 1 ; j < N ; j++){
pre = Math.min(j - map[str[j]],pre + 1);
ans = Math.max(pre,ans);
map[str[j]] = j;
}
return ans;
}
}
public int lengthOfLongestSubstring(String s) {
//if(s==null) return 0;这句话可以不加，s.length()长度为0时，不进入下面的循环，会直接返回max=0;
//划定当前窗口的坐标为(start,i],左开右闭,所以start的初始值为-1，而非0。
int max = 0,start =-1;
//使用哈希表map统计各字符最后一次出现的索引位置
HashMap<Character,Integer> map = new HashMap<>();
for(int i=0;i<s.length();i++){
char tmp = s.charAt(i);
//当字符在map中已经存储时，需要判断其索引值index和当前窗口start的大小以确定是否需要对start进行更新:
//当index>start时，start更新为当前的index,否则保持不变。
//注意若index作为新的start，计算当前滑动空间的长度时也是不计入的，左开右闭，右侧s[i]会计入，这样也是防止字符的重复计入。
if(map.containsKey(tmp)) start = Math.max(start,map.get(tmp));
//如果map中不含tmp，此处是在map中新增一个键值对，否则是对原有的键值对进行更新
map.put(tmp,i);
//i-start,为当前滑动空间(start,i]的长度，若其大于max，则需要进行更新。
max = Math.max(max,i-start);
}
return max;
}
[图片上传失败...(image-fd2bed-1649069519567)]
8.做多可以同时比赛的最大场次
存在插值的话可以同时跳下一个,并且标记可以做过的
public static int maxPairNum{
if(k,0||arr == null||arr.length < 2){
return 0;
}
//排序保证有序性
Arrays.sort(arr);
int ans = 0;
int N =arr.length;
int L = 0,R = 0;
boolean[] used = new boolean[N];
while(L<N&& R<N){
if(used[L]){
L++;
}else if(L >=R){
R++;
}else{
int distance = arr[R] - arr[L];
if(distance == k){
ans++;
used[R++] = true;
L++;
}else if(distance < k){
R++;
}else{
L++;
}
}
}
return ans;
}
9.最多装俩人所有人同时过河让最少运送次数
[图片上传失败...(image-c6a15d-1649069519567)]
先判定出口条件(不能超重)
分情况
1.右侧先耗尽[图片上传失败...(image-4b2a3c-1649069519567)]
2.都剩下
10.子数组最大累加和
返回子数字最大的累加和
DP的思想
1.自己和前一位
class Solution {
public int maxSubArray(int[] nums) {
int res = nums[0];
for(int i = 1; i < nums.length; i++) {
nums[i] += Math.max(nums[i - 1], 0);
res = Math.max(res, nums[i]);
}
return res;
}
}
11.分发糖果
你需要按照以下要求，给这些孩子分发糖果：
- 每个孩子至少分配到
1个糖果。- 相邻两个孩子评分更高的孩子会获得更多的糖果。
分[1,2,2]
得到[1,2,1]
[图片上传失败...(image-ad65bc-1649069519567)]
换句话说只需要管严格意义的相等大小关系
[图片上传失败...(image-91749b-1649069519567)]
class Solution {
public int candy(int[] ratings) {
int[] left = new int[ratings.length];
int[] right = new int[ratings.length];
Arrays.fill(left, 1);
Arrays.fill(right, 1);
for(int i = 1; i < ratings.length; i++)
if(ratings[i] > ratings[i - 1]) left[i] = left[i - 1] + 1;
int count = left[ratings.length - 1];
for(int i = ratings.length - 2; i >= 0; i--) {
if(ratings[i] > ratings[i + 1]) right[i] = right[i + 1] + 1;
count += Math.max(left[i], right[i]);
}
return count;
}
}
[图片上传失败...(image-2bc6c4-1649069519567)]
11.5补充问题
相邻分数一样的一样
12.字符串交错
[图片上传失败...(image-5b6da1-1649069519567)]
[图片上传失败...(image-eba288-1649069519567)]
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int n = s1.length(), m = s2.length(), t = s3.length();
if (n + m != t) {
return false;
}
boolean[][] f = new boolean[n + 1][m + 1];
f[0][0] = true;
for (int i = 0; i <= n; ++i) {
for (int j = 0; j <= m; ++j) {
int p = i + j - 1;
if (i > 0) {
f[i][j] = f[i][j] || (f[i - 1][j] && s1.charAt(i - 1) == s3.charAt(p));
}
if (j > 0) {
f[i][j] = f[i][j] || (f[i][j - 1] && s2.charAt(j - 1) == s3.charAt(p));
}
}
}
return f[n][m];
}
}
class Solution {
public boolean isInterleave(String s1, String s2, String s3) {
int m = s1.length(), n = s2.length();
if (s3.length() != m + n) return false;
// 动态规划，dp[i,j]表示s1前i字符能与s2前j字符组成s3前i+j个字符；
boolean[][] dp = new boolean[m+1][n+1];
dp[0][0] = true;
for (int i = 1; i <= m && s1.charAt(i-1) == s3.charAt(i-1); i++) dp[i][0] = true; // 不相符直接终止
for (int j = 1; j <= n && s2.charAt(j-1) == s3.charAt(j-1); j++) dp[0][j] = true; // 不相符直接终止
for (int i = 1; i <= m; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = (dp[i - 1][j] && s3.charAt(i + j - 1) == s1.charAt(i - 1))
|| (dp[i][j - 1] && s3.charAt(i + j - 1) == s2.charAt(j - 1));
}
}
return dp[m][n];
}
}
13.相等子树数量
[图片上传失败...(image-a932b4-1649069519567)]
这个例子有5个[图片上传失败...(image-e25d4e-1649069519567)]
class Solution{
public static int sameTree(Node head){
if(head == null){
return 0;
}
return sameTree(head.left) + sameTree(head.right)
+
(sameTree(head.left,head.right)? 1 : 0);
}
public static boolean same(Node h1,Node h2){
if(h1 == null ^ h2 == null){
return false;
}
if(h1 == null && h2 == null){
return true;
}
return h1.value == h2.value &&
same(h1.left,h2,left)&&
same(h1,right,h2.right);
}
}
优化思路利用hashcode表示
14.编辑距离问题
[图片上传失败...(image-df36d7-1649069519567)]
需要考虑代价的权重
所以哦有字符串比对的我可以以哦那个DP来做
[图片上传失败...(image-b376df-1649069519567)]
我看到“方法一”三个字的时候，惊喜地以为还有方法二。。没有，这次真没有。动态规划是个好东西，但难就难在如何定义DP数组里值的含义。听我来给你捋一捋。
啥叫编辑距离？我们说word1和word2的编辑距离为X，意味着word1经过X步，变成了word2，咋变的你不用管，反正知道就需要X步，并且这是个最少的步数。
我们有word1和word2，我们定义dp[i][j]的含义为：word1的前i个字符和word2的前j个字符的编辑距离。意思就是word1的前i个字符，变成word2的前j个字符，最少需要这么多步。
例如word1 = "horse", word2 = "ros"，那么dp[3][2]=X就表示"hor"和“ro”的编辑距离，即把"hor"变成“ro”最少需要X步。
如果下标为零则表示空串，比如：dp[0][2]就表示空串""和“ro”的编辑距离
定理一：如果其中一个字符串是空串，那么编辑距离是另一个字符串的长度。比如空串“”和“ro”的编辑距离是2（做两次“插入”操作）。再比如"hor"和空串“”的编辑距离是3（做三次“删除”操作）。
定理二：当i>0,j>0时（即两个串都不空时）dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+int(word1[i]!=word2[j]))。
啥意思呢？举个例子，word1 = "abcde", word2 = "fgh",我们现在算这俩字符串的编辑距离，就是找从word1，最少多少步，能变成word2？那就有三种方式：
- 知道"abcd"变成"fgh"多少步（假设X步），那么从"abcde"到"fgh"就是"abcde"->"abcd"->"fgh"。（一次删除，加X步，总共X+1步）
- 知道"abcde"变成“fg”多少步（假设Y步），那么从"abcde"到"fgh"就是"abcde"->"fg"->"fgh"。（先Y步，再一次添加，加X步，总共Y+1步）
- 知道"abcd"变成“fg”多少步（假设Z步），那么从"abcde"到"fgh"就是"abcde"->"fge"->"fgh"。（先不管最后一个字符，把前面的先变好，用了Z步，然后把最后一个字符给替换了。这里如果最后一个字符碰巧就一样，那就不用替换，省了一步）
以上三种方式算出来选最少的，就是答案。所以我们再看看定理二：
dp[i][j]=min(dp[i-1][j]+1,dp[i][j+1]+1,dp[i][j]+int(word1[i]!=word2[j]))
dp[i-1][j]：情况一
dp[i][j-1]+1：情况二
dp[i-1][j-1]+int(word1[i]!=word2[j])：情况三
有了定理二的递推公式，你就建立一个二维数组，考虑好空串的情况，总会写出来
-------------------------------------
进阶
-------------------------------------
先把二维数组的方法做出来，要还没做出来呢，先别往下看。
由定理二可知，dp[i][j]只和dp[i-1][j],dp[i][j-1],dp[i-1][j-1]三个量有关，即二维数组中，当前元素的左边，上边，左上角三个元素。
那我们不用这么大的二维数组存啊！我们就用一维数组，表示原来二维数组中的一行，然后我们就反复覆盖里面的值。dp[i-1][j]就是我当前左边的元素，dp[i][j-1]是没覆盖前我这里的值，dp[i-1][j-1]好像找不见了？那我们就单独用一个变量存着它，我们把它叫lu（left up），则代码为：
class Solution:
def minDistance(self, word1: str, word2: str) -> int:
m=len(word1)
n=len(word2)
dp=list(range(n+1))
for i in range(m):
lu=dp[0]
dp[0]=i+1
for j in range(n):
dp[j+1],lu=min(dp[j]+1,dp[j+1]+1,lu+int(word1[i]!=word2[j])),dp[j+1]
return dp[-1]
时间复杂度 ：O(mn)，其中 m 为 word1 的长度，n 为 word2 的长度
空间复杂度 ：O(n)
(这里可以比较word1和word2的长度，让n是m n里较小的那一个)
class Solution {
public int minDistance(String word1, String word2) {
int n1 = word1.length();
int n2 = word2.length();
int[][] dp = new int[n1 + 1][n2 + 1];
// 第一行
for (int j = 1; j <= n2; j++) dp[0][j] = dp[0][j - 1] + 1;
// 第一列
for (int i = 1; i <= n1; i++) dp[i][0] = dp[i - 1][0] + 1;
for (int i = 1; i <= n1; i++) {
for (int j = 1; j <= n2; j++) {
if (word1.charAt(i - 1) == word2.charAt(j - 1)) dp[i][j] = dp[i - 1][j - 1];
else dp[i][j] = Math.min(Math.min(dp[i - 1][j - 1], dp[i][j - 1]), dp[i - 1][j]) + 1;
}
}
return dp[n1][n2];
}
}
15.公式字符串结算(括号嵌套题目)
[图片上传失败...(image-77be8e-1649069519567)]
public static int[] f(char[] str,int i){
}
[图片上传失败...(image-f80e85-1649069519567)]
16.最大容纳水的数量(接雨水问题)
[图片上传失败...(image-830401-1649069519567)]
1.双指针解法[图片上传失败...(image-fe825d-1649069519567)]
11. 盛最多水的容器（双指针，清晰图解） - 盛最多水的容器 - 力扣（LeetCode） (leetcode-cn.com)
class Solution {
public int maxArea(int[] height) {
int i = 0, j = height.length - 1, res = 0;
while(i < j) {
res = height[i] < height[j] ?
Math.max(res, (j - i) * height[i++]):
Math.max(res, (j - i) * height[j--]);
}
return res;
}
}
leetcode4.接雨水
如何高效解决接雨水问题 :: labuladong的算法小抄 (gitee.io)
17.无效括号变有效括号(不太会)
提议解析[图片上传失败...(image-ec694f-1649069519567)]
【宫水三叶】将括号的「是否合法」转化为「数学判定」 - 删除无效的括号 - 力扣（LeetCode） (leetcode-cn.com)
1.如何考虑字符串是有效的呢?
遍历一遍一定存在左右括号一一匹配的情况
class Solution {
int maxCount;
int maxlen;
int score;
Set<String> set = new HashSet<>();
public List<String> removeInvalidParentheses(String s) {
int length = s.length();
int left = 0;
int right = 0;
for(int i = 0;i < length;i++){
/**
* 统计共有多少个 左括号 和 右括号！
*/
if('(' == s.charAt(i)){
left++;
}else if(')' == s.charAt(i)){
right++;
}
}
/**
* 选用出 最大的合法括号个数，即左括号和右括号中个数较少的一个！
* 因为合法的括号一定是成对出现的！
*/
maxCount = Math.min(left, right);
dfs(s,0,"",0);
return new ArrayList<>(set);
}
void dfs(String s,int index,String current,int score){
if(score < 0 || score > maxCount){
/**
* 小于0说明遍历到了 ')' 但是前面没有 ‘(’ 所以不合法提前结束！
* 大于max，说明后面没有足够数量的')' 和前面的'('匹配了 ，所以也不合法，提前结束！
*/
return;
}
if(index == s.length()){
/**
* 说明遍历到了最后一个字符！
*/
if(score == 0 && current.length() >= maxlen){
/**
* 等于0，说明刚好左右括号匹配合法！！！！
* 如果合法，且大于前面已经遍历过合法的字符串长度，则更新最长合法长度！
*/
if(current.length() > maxlen){
/**
* 如果是大于原来长度，则需要先清空原来合法长度答案
* 如果是等于，则在原来合法长度答案基础上继续添加子答案！
*/
set.clear();
}
set.add(current);
maxlen = current.length();
}
return;
}
char c = s.charAt(index);
if(c == '('){
/**
* 有可能选用这个‘(’，则传入 current + String.valueOf(c),因为增加了一个左括号，所以分数要加1
* 如果不选用这个'('，则直接传入原来字符即可，即不带这个‘(',所以不影响前面合法性，所以分数不变！
* 下面右括号同理！
*/
dfs(s,index + 1,current + String.valueOf(c), score + 1);
dfs(s,index + 1,current, score);
}else if(c == ')'){
dfs(s,index + 1,current + String.valueOf(c), score - 1);
dfs(s,index + 1,current, score);
}else{
/**
* 说明是 字母字符，不影响括号字符合法性！！！所以score分数不变！
*/
dfs(s,index + 1,current + String.valueOf(c), score);
}
}
}
进阶版代码(在遇到不匹配时就修改)
然后返回f(修改的位置,与这个位置一样的字符最先开始的位置)
[图片上传失败...(image-44e340-1649069519567)]
23.约瑟夫环问题(美的笔试题)
剃刀类型的函数使用下面公式变种
问题关键为 i% x
import java.util.ArrayList;
import java.util.List;
public class Yue {
public static void main(String[] args) {
//例如有9人,数到三的人出列，知道最后一个
yuesefu(9, 3);
}
public static void yuesefu(int totalNum, int countNum) {
// 初始化人数
List<Integer> start = new ArrayList<Integer>();
for (int i = 1; i <= totalNum; i++) {
start.add(i);
}
// 从索引0开始计数
int i = 0;
while (start.size() > 0) {
//从0位置计算第三个元素位置在哪里
i = i + 2;
// 通过取模与运维获得下一个索引位置在哪里，避免索引越界
i = i % (start.size());
// 判断是否只剩下二个
if (start.size() < 3) {
System.out.println("start= " + start);
break;
} else {
System.out.println(start.get(i));
start.remove(i);
}
}
}
}
[图片上传失败...(image-3ec4-1649069519567)]
