視頻課
1.繩子覆蓋最多的點(diǎn)數(shù)[圖片上傳失敗...(image-2bf857-1649069519567)]
解法1:暴力+貪心
[圖片上傳失敗...(image-c13fd3-1649069519567)]
需要在給出的點(diǎn)往前找,假如找到一個(gè)點(diǎn)的末尾 973 -- > 873 L為100 二分早到 logN x N
解法二:滑動窗口
設(shè)置左右指針 :
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右邊求這倆哪個(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.+ - 方法數(shù)
[圖片上傳失敗...(image-d1a8c6-1649069519567)]
題目:
題解:
【宮水三葉】一題四解 : 「DFS」&「記憶化搜索」&「全量 DP」&「優(yōu)化 DP」 - 目標(biāo)和 - 力扣（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 非負(fù)數(shù)
2.sum > target 一定 false
3.奇數(shù)偶數(shù)不一樣
4.正負(fù)數(shù)分開取集合 P{群是 +} N{都是-數(shù)} p,n為他們里面的和
**本質(zhì)上就是求 p - n = target;****
推到:
p-n + (p+n) = target +(p + n) ?? 2p = target + sum{all data}; p = (target + sum) / 2;得到我們的正數(shù)的和要目標(biāo)值和 所有數(shù)集合的一半
同理:
N
解法4:壓縮二維數(shù)組表格
[圖片上傳失敗...(image-b6fa5a-1649069519567)]
5.司機(jī)獲得收入（不太會時(shí)DP）[圖片上傳失敗...(image-fd2833-1649069519567)]
[圖片上傳失敗...(image-e9fb85-1649069519567)]
public static int maxIncome(int[][] income){
int N = income.length;
//考慮特殊情況的原則下
//1.空
//2.奇數(shù)
//3.為0或者1
if(income == null || (N & 1) !=0 || N < 2){
return 0;
}
int M = N>>1;
//接下面的圖片部分
}
[圖片上傳失敗...(image-c7ccdc-1649069519567)]
6.還有Set All（）的哈希表
解讀,把``setAll`把對應(yīng)的key 的值全部為括號內(nèi)的數(shù)字
[圖片上傳失敗...(image-c5b3f6-1649069519567)]
利用時(shí)間戳來經(jīng)行最新的值的修改規(guī)定
public class setAll{
}
7.最長無重復(fù)字符且最長
思路:定位向左找.
關(guān)鍵字:"字串" 不重復(fù)
DP
1.a--->17號位置 要之前沒有出現(xiàn)過a
2.17號位置和16號位置的最長有關(guān)
不需要設(shè)置dp數(shù)組因?yàn)橹恍枰Y(jié)果幾個(gè)
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); // 更新結(jié)果
}
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時(shí)拐纱，不進(jìn)入下面的循環(huán)胆建，會直接返回max=0;
//劃定當(dāng)前窗口的坐標(biāo)為(start,i],左開右閉,所以start的初始值為-1孟辑，而非0。
int max = 0,start =-1;
//使用哈希表map統(tǒng)計(jì)各字符最后一次出現(xiàn)的索引位置
HashMap<Character,Integer> map = new HashMap<>();
for(int i=0;i<s.length();i++){
char tmp = s.charAt(i);
//當(dāng)字符在map中已經(jīng)存儲時(shí)，需要判斷其索引值index和當(dāng)前窗口start的大小以確定是否需要對start進(jìn)行更新:
//當(dāng)index>start時(shí)洋幻，start更新為當(dāng)前的index,否則保持不變。
//注意若index作為新的start歇拆，計(jì)算當(dāng)前滑動空間的長度時(shí)也是不計(jì)入的鞋屈，左開右閉范咨，右側(cè)s[i]會計(jì)入故觅，這樣也是防止字符的重復(fù)計(jì)入。
if(map.containsKey(tmp)) start = Math.max(start,map.get(tmp));
//如果map中不含tmp渠啊，此處是在map中新增一個(gè)鍵值對输吏，否則是對原有的鍵值對進(jìn)行更新
map.put(tmp,i);
//i-start,為當(dāng)前滑動空間(start,i]的長度，若其大于max替蛉，則需要進(jìn)行更新贯溅。
max = Math.max(max,i-start);
}
return max;
}
[圖片上傳失敗...(image-fd2bed-1649069519567)]
8.做多可以同時(shí)比賽的最大場次
存在插值的話可以同時(shí)跳下一個(gè),并且標(biāo)記可以做過的
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.最多裝倆人所有人同時(shí)過河讓最少運(yùn)送次數(shù)
[圖片上傳失敗...(image-c6a15d-1649069519567)]
先判定出口條件(不能超重)
分情況
1.右側(cè)先耗盡[圖片上傳失敗...(image-4b2a3c-1649069519567)]
2.都剩下
10.子數(shù)組最大累加和
返回子數(shù)字最大的累加和
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.分發(fā)糖果
你需要按照以下要求，給這些孩子分發(fā)糖果：
- 每個(gè)孩子至少分配到
1個(gè)糖果躲查。- 相鄰兩個(gè)孩子評分更高的孩子會獲得更多的糖果它浅。
分[1,2,2]
得到[1,2,1]
[圖片上傳失敗...(image-ad65bc-1649069519567)]
換句話說只需要管嚴(yán)格意義的相等大小關(guān)系
[圖片上傳失敗...(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補(bǔ)充問題
相鄰分?jǐn)?shù)一樣的一樣
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;
// 動態(tài)規(guī)劃，dp[i,j]表示s1前i字符能與s2前j字符組成s3前i+j個(gè)字符镣煮；
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.相等子樹數(shù)量
[圖片上傳失敗...(image-a932b4-1649069519567)]
這個(gè)例子有5個(gè)[圖片上傳失敗...(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);
}
}
優(yōu)化思路利用hashcode表示
14.編輯距離問題
[圖片上傳失敗...(image-df36d7-1649069519567)]
需要考慮代價(jià)的權(quán)重
所以哦有字符串比對的我可以以哦那個(gè)DP來做
[圖片上傳失敗...(image-b376df-1649069519567)]
我看到“方法一”三個(gè)字的時(shí)候姐霍，驚喜地以為還有方法二。典唇。沒有镊折，這次真沒有。動態(tài)規(guī)劃是個(gè)好東西介衔，但難就難在如何定義DP數(shù)組里值的含義恨胚。聽我來給你捋一捋。
啥叫編輯距離炎咖？我們說word1和word2的編輯距離為X赃泡，意味著word1經(jīng)過X步，變成了word2乘盼，咋變的你不用管急迂，反正知道就需要X步，并且這是個(gè)最少的步數(shù)蹦肴。
我們有word1和word2僚碎，我們定義dp[i][j]的含義為：word1的前i個(gè)字符和word2的前j個(gè)字符的編輯距離。意思就是word1的前i個(gè)字符阴幌，變成word2的前j個(gè)字符勺阐，最少需要這么多步卷中。
例如word1 = "horse", word2 = "ros"，那么dp[3][2]=X就表示"hor"和“ro”的編輯距離渊抽，即把"hor"變成“ro”最少需要X步蟆豫。
如果下標(biāo)為零則表示空串，比如：dp[0][2]就表示空串""和“ro”的編輯距離
定理一：如果其中一個(gè)字符串是空串懒闷，那么編輯距離是另一個(gè)字符串的長度十减。比如空串“”和“ro”的編輯距離是2（做兩次“插入”操作）。再比如"hor"和空串“”的編輯距離是3（做三次“刪除”操作）愤估。
定理二：當(dāng)i>0,j>0時(shí)（即兩個(gè)串都不空時(shí)）dp[i][j]=min(dp[i-1][j]+1,dp[i][j-1]+1,dp[i-1][j-1]+int(word1[i]!=word2[j]))帮辟。
啥意思呢？舉個(gè)例子玩焰，word1 = "abcde", word2 = "fgh",我們現(xiàn)在算這倆字符串的編輯距離由驹，就是找從word1，最少多少步昔园，能變成word2蔓榄？那就有三種方式：
- 知道"abcd"變成"fgh"多少步（假設(shè)X步），那么從"abcde"到"fgh"就是"abcde"->"abcd"->"fgh"默刚。（一次刪除甥郑，加X步，總共X+1步）
- 知道"abcde"變成“fg”多少步（假設(shè)Y步）荤西，那么從"abcde"到"fgh"就是"abcde"->"fg"->"fgh"澜搅。（先Y步，再一次添加皂冰，加X步店展，總共Y+1步）
- 知道"abcd"變成“fg”多少步（假設(shè)Z步），那么從"abcde"到"fgh"就是"abcde"->"fge"->"fgh"秃流。（先不管最后一個(gè)字符赂蕴，把前面的先變好，用了Z步舶胀，然后把最后一個(gè)字符給替換了概说。這里如果最后一個(gè)字符碰巧就一樣，那就不用替換嚣伐，省了一步）
以上三種方式算出來選最少的糖赔，就是答案。所以我們再看看定理二：
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])：情況三
有了定理二的遞推公式轩端，你就建立一個(gè)二維數(shù)組放典，考慮好空串的情況，總會寫出來
-------------------------------------
進(jìn)階
-------------------------------------
先把二維數(shù)組的方法做出來，要還沒做出來呢奋构，先別往下看壳影。
由定理二可知，dp[i][j]只和dp[i-1][j],dp[i][j-1],dp[i-1][j-1]三個(gè)量有關(guān)弥臼，即二維數(shù)組中宴咧，當(dāng)前元素的左邊，上邊径缅，左上角三個(gè)元素掺栅。
那我們不用這么大的二維數(shù)組存啊纳猪！我們就用一維數(shù)組氧卧，表示原來二維數(shù)組中的一行，然后我們就反復(fù)覆蓋里面的值兆旬。dp[i-1][j]就是我當(dāng)前左邊的元素假抄，dp[i][j-1]是沒覆蓋前我這里的值怎栽，dp[i-1][j-1]好像找不見了丽猬？那我們就單獨(dú)用一個(gè)變量存著它，我們把它叫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]
時(shí)間復(fù)雜度 ：O(mn)脚祟，其中 m 為 word1 的長度，n 為 word2 的長度
空間復(fù)雜度 ：O(n)
(這里可以比較word1和word2的長度强饮，讓n是m n里較小的那一個(gè))
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.公式字符串結(jié)算(括號嵌套題目)
[圖片上傳失敗...(image-77be8e-1649069519567)]
public static int[] f(char[] str,int i){
}
[圖片上傳失敗...(image-f80e85-1649069519567)]
16.最大容納水的數(shù)量(接雨水問題)
[圖片上傳失敗...(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)]
【宮水三葉】將括號的「是否合法」轉(zhuǎn)化為「數(shù)學(xué)判定」 - 刪除無效的括號 - 力扣（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++){
/**
* 統(tǒng)計(jì)共有多少個(gè) 左括號 和 右括號行您！
*/
if('(' == s.charAt(i)){
left++;
}else if(')' == s.charAt(i)){
right++;
}
}
/**
* 選用出 最大的合法括號個(gè)數(shù)，即左括號和右括號中個(gè)數(shù)較少的一個(gè)剪廉！
* 因?yàn)楹戏ǖ睦ㄌ栆欢ㄊ浅蓪Τ霈F(xiàn)的娃循！
*/
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說明遍歷到了 ')' 但是前面沒有 ‘(’ 所以不合法提前結(jié)束！
* 大于max斗蒋，說明后面沒有足夠數(shù)量的')' 和前面的'('匹配了 捌斧，所以也不合法，提前結(jié)束泉沾！
*/
return;
}
if(index == s.length()){
/**
* 說明遍歷到了最后一個(gè)字符捞蚂！
*/
if(score == 0 && current.length() >= maxlen){
/**
* 等于0，說明剛好左右括號匹配合法ｕ尉俊Ｐ昭浮！！
* 如果合法丁存，且大于前面已經(jīng)遍歷過合法的字符串長度色冀，則更新最長合法長度！
*/
if(current.length() > maxlen){
/**
* 如果是大于原來長度柱嫌，則需要先清空原來合法長度答案
* 如果是等于锋恬，則在原來合法長度答案基礎(chǔ)上繼續(xù)添加子答案！
*/
set.clear();
}
set.add(current);
maxlen = current.length();
}
return;
}
char c = s.charAt(index);
if(c == '('){
/**
* 有可能選用這個(gè)‘(’编丘，則傳入 current + String.valueOf(c),因?yàn)樵黾恿艘粋€(gè)左括號与学，所以分?jǐn)?shù)要加1
* 如果不選用這個(gè)'('，則直接傳入原來字符即可嘉抓，即不帶這個(gè)‘(',所以不影響前面合法性索守，所以分?jǐn)?shù)不變！
* 下面右括號同理抑片！
*/
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分?jǐn)?shù)不變！
*/
dfs(s,index + 1,current + String.valueOf(c), score);
}
}
}
進(jìn)階版代碼(在遇到不匹配時(shí)就修改)
然后返回f(修改的位置,與這個(gè)位置一樣的字符最先開始的位置)
[圖片上傳失敗...(image-44e340-1649069519567)]
23.約瑟夫環(huán)問題(美的筆試題)
剃刀類型的函數(shù)使用下面公式變種
問題關(guān)鍵為 i% x
import java.util.ArrayList;
import java.util.List;
public class Yue {
public static void main(String[] args) {
//例如有9人,數(shù)到三的人出列植捎，知道最后一個(gè)
yuesefu(9, 3);
}
public static void yuesefu(int totalNum, int countNum) {
// 初始化人數(shù)
List<Integer> start = new ArrayList<Integer>();
for (int i = 1; i <= totalNum; i++) {
start.add(i);
}
// 從索引0開始計(jì)數(shù)
int i = 0;
while (start.size() > 0) {
//從0位置計(jì)算第三個(gè)元素位置在哪里
i = i + 2;
// 通過取模與運(yùn)維獲得下一個(gè)索引位置在哪里衙解，避免索引越界
i = i % (start.size());
// 判斷是否只剩下二個(gè)
if (start.size() < 3) {
System.out.println("start= " + start);
break;
} else {
System.out.println(start.get(i));
start.remove(i);
}
}
}
}
[圖片上傳失敗...(image-3ec4-1649069519567)]
