2021第一篇刷題筆記。今早開(kāi)晨會(huì)領(lǐng)導(dǎo)也說(shuō)了一句話：每天進(jìn)步一點(diǎn)點(diǎn)。長(zhǎng)年累月就是翻天覆地的變化。好了，不多說(shuō)閑話啦，刷題繼續(xù)。
前K個(gè)高頻單詞
題目：給一非空的單詞列表，返回前 k 個(gè)出現(xiàn)次數(shù)最多的單詞。返回的答案應(yīng)該按單詞出現(xiàn)頻率由高到低排序。如果不同的單詞有相同出現(xiàn)頻率，按字母順序排序。
示例 1：
輸入: ["i", "love", "leetcode", "i", "love", "coding"], k = 2
輸出: ["i", "love"]
解析: "i" 和 "love" 為出現(xiàn)次數(shù)最多的兩個(gè)單詞，均為2次。
注意，按字母順序 "i" 在 "love" 之前。
示例 2：
輸入: ["the", "day", "is", "sunny", "the", "the", "the", "sunny", "is", "is"], k = 4
輸出: ["the", "is", "sunny", "day"]
解析: "the", "is", "sunny" 和 "day" 是出現(xiàn)次數(shù)最多的四個(gè)單詞，
出現(xiàn)次數(shù)依次為 4, 3, 2 和 1 次。
注意：
假定 k 總為有效值， 1 ≤ k ≤ 集合元素?cái)?shù)。
輸入的單詞均由小寫(xiě)字母組成。
擴(kuò)展練習(xí)：
嘗試以 O(n log k) 時(shí)間復(fù)雜度和 O(n) 空間復(fù)雜度解決。
思路：如果不考慮擴(kuò)展中的時(shí)間空間復(fù)雜度的話，這個(gè)題還是比較容易的。比如單純的用map計(jì)數(shù)。然后統(tǒng)計(jì)出現(xiàn)的頻率。最后得出結(jié)果。然后考慮時(shí)間空間復(fù)雜度我也覺(jué)得這個(gè)思路沒(méi)啥問(wèn)題，我去寫(xiě)代碼試試。
貼第一版代碼：
class Solution {
public List<String> topKFrequent(String[] words, int k) {
Map<String,Integer> map = new HashMap<String, Integer>();
for(String s:words) {
map.put(s, map.getOrDefault(s, 0)+1);
}
//所有的key放到list
List<String> list = new ArrayList<String>(map.keySet());
//排序規(guī)則：如果頻率相同則字段排序，頻率不同大的靠前
Collections.sort(list, (s1,s2)->map.get(s1).equals(map.get(s2))?s1.compareTo(s2):map.get(s2)-map.get(s1));
//截取前k個(gè)元素
return list.subList(0, k);
}
}
我竟然沒(méi)get到這個(gè)題的難點(diǎn)在哪里，反著這個(gè)代碼ac了性能也還行。我去看看題解吧：
看到一個(gè)天秀的寫(xiě)法，java一句話搞定：
return Arrays.stream(words)
.collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))
.entrySet()
.stream()
.sorted((o1, o2) -> {
if (o1.getValue().equals(o2.getValue())) {
return o1.getKey().compareTo(o2.getKey());
} else {
return o2.getValue().compareTo(o1.getValue());
}
})
.map(Map.Entry::getKey)
.limit(k)
.collect(Collectors.toList());
怎么說(shuō)呢，反正不要任何邏輯單純看上面答案的話我覺(jué)得很帥，但是我要維護(hù)的項(xiàng)目里這么寫(xiě)我大概會(huì)打死上一個(gè)開(kāi)發(fā)。。。真的是天秀，感覺(jué)這個(gè)題也就這樣了，下一題。
島嶼的最大面積
題目：給定一個(gè)包含了一些 0 和 1 的非空二維數(shù)組 grid 。一個(gè) 島嶼 是由一些相鄰的 1 (代表土地) 構(gòu)成的組合，這里的「相鄰」要求兩個(gè) 1 必須在水平或者豎直方向上相鄰。你可以假設(shè) grid 的四個(gè)邊緣都被 0（代表水）包圍著。找到給定的二維數(shù)組中最大的島嶼面積。(如果沒(méi)有島嶼，則返回面積為 0 。)
示例 1:
[[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]]
對(duì)于上面這個(gè)給定矩陣應(yīng)返回 6。注意答案不應(yīng)該是 11 ，因?yàn)閸u嶼只能包含水平或垂直的四個(gè)方向的 1 。
示例 2:
[[0,0,0,0,0,0,0,0]]
對(duì)于上面這個(gè)給定的矩陣, 返回 0。
注意: 給定的矩陣grid 的長(zhǎng)度和寬度都不超過(guò) 50。
思路：這個(gè)題我做過(guò)類似的，反正第一反應(yīng)就是遞歸。以前有個(gè)朋友圈的題目，就是有關(guān)系的算一個(gè)圈，最多看有多少個(gè)圈。這個(gè)題其實(shí)可以算是朋友圈的變種。有關(guān)系的算一個(gè)圈，找出圈中人數(shù)最多的那個(gè)數(shù)目？思路很清晰，我去擼代碼。
第一版ac代碼:
class Solution {
int max = 0;
public int maxAreaOfIsland(int[][] grid) {
int res = 0;
if(grid.length==0 || grid[0].length == 0) return res;
for(int i = 0;i<grid.length;i++) {
for(int j = 0;j<grid[0].length;j++) {
if(grid[i][j] == 1) {
dfs(grid, i, j);
res = Math.max(res, max);
max = 0;
}
}
}
return res;
}
public void dfs(int[][] grid,int x,int y) {
max++;//進(jìn)入到當(dāng)前方法說(shuō)明當(dāng)前值是1.面積+1
grid[x][y] = 0;//計(jì)算過(guò)面積的歸0
if(x>0 && grid[x-1][y]==1) dfs(grid, x-1, y);
if(y>0 && grid[x][y-1]==1) dfs(grid, x, y-1);
if(x<grid.length-1 && grid[x+1][y]==1) dfs(grid, x+1, y);
if(y<grid[0].length-1 && grid[x][y+1]==1) dfs(grid, x, y+1);
}
}
雖然題目挺簡(jiǎn)單，但是暫時(shí)也找不到優(yōu)化點(diǎn)，我直接去看性能第一的代碼了：
class Solution {
public int maxAreaOfIsland(int[][] grid) {
int m=grid.length,n=grid[0].length;
int sum=0;
for(int i=0;i<m;i++){
for(int j=0;j<n;j++){
if(grid[i][j] == 1){
sum=Math.max(dfs(grid, i, j),sum);
}
}
}
return sum;
}
public boolean inArea(int[][] grid,int i,int j){
return i>=0&&i<grid.length&&j>=0&&j<grid[0].length;
}
public int dfs(int[][] grid,int i,int j){
if(!inArea(grid,i,j)){
return 0;
}
if(grid[i][j]!=1){
return 0;
}
grid[i][j]=2;//防止重復(fù)遍歷 不進(jìn)行統(tǒng)計(jì) 將屬于統(tǒng)一個(gè)島嶼的均進(jìn)行標(biāo)注
return 1+dfs(grid,i+1,j)+dfs(grid,i,j+1)+dfs(grid,i-1,j)+dfs(grid,i,j-1);
}
}
差不多的思路，就是處理上的細(xì)節(jié)。我這里是單純的有個(gè)1加一次。用全局變量計(jì)數(shù)。人家是返回是1的個(gè)數(shù)。反正這個(gè)題總而言之思路就這樣，下一題。
劃分為k個(gè)相等的子集
題目：給定一個(gè)整數(shù)數(shù)組 nums 和一個(gè)正整數(shù) k，找出是否有可能把這個(gè)數(shù)組分成 k 個(gè)非空子集，其總和都相等。
示例 1：
輸入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
輸出： True
說(shuō)明： 有可能將其分成 4 個(gè)子集（5），（1,4），（2,3），（2,3）等于總和。
提示：
1 <= k <= len(nums) <= 16
0 < nums[i] < 10000
思路：這個(gè)題的大概想法:第一步算出數(shù)組總和，看能不能被k整除，不能直接false。還有最大元素不能大于商，否則永遠(yuǎn)也分割不了。這些都沒(méi)問(wèn)題了再去做幾數(shù)之和等于sum/k。等于則消除。需要注意的是要盡量用較大的元素小消除，比如 4，5，9 最后差一個(gè)9的話，要盡量選直接是9的而不要選擇九個(gè)1，因?yàn)榫艂€(gè)1比一個(gè)9更靈活。而且注意這個(gè)數(shù)組的長(zhǎng)度小于等于16？范圍這么小的么。。。嘖嘖，反正目前的思路就是這樣，我去寫(xiě)代碼試試。
只能說(shuō)這個(gè)題不愧最大數(shù)只有16個(gè)，死去活來(lái)的調(diào)試，我先貼第一版本的代碼：
class Solution {
public boolean canPartitionKSubsets(int[] nums, int k) {
int sum = 0;
for(int i = 0; i < nums.length; i++) sum += nums[i];
if(sum % k != 0) return false;
sum = sum / k;//子集的和
Arrays.sort(nums);
//如果子集的和小于數(shù)組最大的直接返回false
if(nums[nums.length - 1] > sum) return false;
//建立一個(gè)長(zhǎng)度為k的桶
int[] arr = new int[k];
//桶的每一個(gè)值都是子集的和
Arrays.fill(arr, sum);
//從數(shù)組最后一個(gè)數(shù)開(kāi)始進(jìn)行遞歸
return dfs(nums, nums.length - 1, arr);
}
public boolean dfs(int[] nums,int idx,int[] arr) {
if(idx<0) return true;//所有元素都放完了
for(int i = 0;i<arr.length;i++) {
//當(dāng)前元素=桶中元素 或 當(dāng)前元素小于桶中元素剩下的部分大于等于最小的那個(gè),否則哪怕當(dāng)前元素能放進(jìn)去剩下的空缺也填不上
if(nums[idx]==arr[i] || (nums[idx]<arr[i] && arr[i]-nums[idx]>=nums[0])) {
arr[i] -= nums[idx];//當(dāng)前元素放進(jìn)桶，遞歸看是不是true
if(dfs(nums, idx-1, arr)) return true;
arr[i] += nums[idx];//當(dāng)前元素放這個(gè)桶不行，所以拿出來(lái)
}
}
//走到這步說(shuō)明當(dāng)前元素放哪都不行了，所以false
return false;
}
}
因?yàn)檫@個(gè)題我調(diào)試了好多次，所以注釋寫(xiě)的挺全的，畢竟是為了方便自己的理解。簡(jiǎn)單來(lái)說(shuō)這個(gè)題的主要目的就是分桶。本來(lái)我是想用最開(kāi)始的思路去湊成一個(gè)個(gè)目標(biāo)和為子元素和的target?？茨懿荒軠惓蒶個(gè)。
但是這樣最大的問(wèn)題就是元素使用問(wèn)題：因?yàn)榈箶?shù)第二個(gè)測(cè)試案例10,10,10,7,7,7,7,7,7,6,6,6.這個(gè)測(cè)試你案例分三個(gè)桶，正常應(yīng)該和是30.如果我較大的數(shù)字優(yōu)先使用，那么前三個(gè)10就湊成一個(gè)30，然后后面的就怎么都湊不成了。所以這個(gè)思路就這么pass了，其實(shí)到這里我是想出辦法優(yōu)化了的，比如這里發(fā)現(xiàn)前三個(gè)湊一起false，那么退一位前兩個(gè)，再退一位前一個(gè)和所有的湊，凡是debug起來(lái)死去活來(lái)的，就12個(gè)元素我這邊都點(diǎn)下一步點(diǎn)的手抽筋了，所以開(kāi)始想還有沒(méi)有別的好一點(diǎn)的實(shí)現(xiàn)方法。最終如上面的代碼差不多思路：
其實(shí)這里是用滿桶往下減還是用空桶往上加都可以。反正最終每一個(gè)元素都可以安排的明明白白的就行。上面代碼性能也挺好的了，我再去看看題解吧?？从袥](méi)有什么更有意思的思路：
行吧，官方題解據(jù)說(shuō)是dp解法的，我沒(méi)看懂，貼上來(lái)分享下就過(guò)了:
boolean search(int used, int todo, Boolean[] memo, int[] nums, int target) {
if (memo[used] == null) {
memo[used] = false;
int targ = (todo - 1) % target + 1;
for (int i = 0; i < nums.length; i++) {
if ((((used >> i) & 1) == 0) && nums[i] <= targ) {
if (search(used | (1<<i), todo - nums[i], memo, nums, target)) {
memo[used] = true;
break;
}
}
}
}
return memo[used] == true;
}
public boolean canPartitionKSubsets(int[] nums, int k) {
int sum = Arrays.stream(nums).sum();
if (sum % k > 0) return false;
Boolean[] memo = new Boolean[1 << nums.length];
memo[(1 << nums.length) - 1] = true;
return search(0, sum, memo, nums, sum / k);
}
然后這個(gè)代碼的性能還不如我上面自己寫(xiě)的呢，所以就不多說(shuō)了，下一題。
二叉搜索樹(shù)中的插入操作
題目：給定二叉搜索樹(shù)（BST）的根節(jié)點(diǎn)和要插入樹(shù)中的值，將值插入二叉搜索樹(shù)。 返回插入后二叉搜索樹(shù)的根節(jié)點(diǎn)。 輸入數(shù)據(jù) 保證 ，新值和原始二叉搜索樹(shù)中的任意節(jié)點(diǎn)值都不同。注意，可能存在多種有效的插入方式，只要樹(shù)在插入后仍保持為二叉搜索樹(shù)即可。 你可以返回 任意有效的結(jié)果 。
思路：這個(gè)題怎么說(shuō)呢，暫時(shí)沒(méi)get到難點(diǎn)在哪里，遵循左小右大不就行了么，我的想法是往最后一層插入。應(yīng)該肯定能插進(jìn)去。我去代碼試一下吧
兩次ac，第一次被卡在給定root是null的情況下，真的是一言難盡，我直接貼代碼：
/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public TreeNode insertIntoBST(TreeNode root, int val) {
if(root == null) return new TreeNode(val);
dfs(root, val);
return root;
}
public void dfs(TreeNode root, int val) {
if(root.val>val) {
if(root.left == null) {
root.left = new TreeNode(val);
return;
}else {
dfs(root.left, val);
}
}else {
if(root.right == null) {
root.right = new TreeNode(val);
return;
}else {
dfs(root.right, val);
}
}
}
}
因?yàn)檫@個(gè)題不是很難，所以就下一題了，沒(méi)啥好說(shuō)的。
設(shè)計(jì)鏈表
題目：設(shè)計(jì)鏈表的實(shí)現(xiàn)。您可以選擇使用單鏈表或雙鏈表。單鏈表中的節(jié)點(diǎn)應(yīng)該具有兩個(gè)屬性：val 和 next。val 是當(dāng)前節(jié)點(diǎn)的值，next 是指向下一個(gè)節(jié)點(diǎn)的指針/引用。如果要使用雙向鏈表，則還需要一個(gè)屬性 prev 以指示鏈表中的上一個(gè)節(jié)點(diǎn)。假設(shè)鏈表中的所有節(jié)點(diǎn)都是 0-index 的。
在鏈表類中實(shí)現(xiàn)這些功能：
get(index)：獲取鏈表中第 index 個(gè)節(jié)點(diǎn)的值。如果索引無(wú)效，則返回-1。
addAtHead(val)：在鏈表的第一個(gè)元素之前添加一個(gè)值為 val 的節(jié)點(diǎn)。插入后，新節(jié)點(diǎn)將成為鏈表的第一個(gè)節(jié)點(diǎn)。
addAtTail(val)：將值為 val 的節(jié)點(diǎn)追加到鏈表的最后一個(gè)元素。
addAtIndex(index,val)：在鏈表中的第 index 個(gè)節(jié)點(diǎn)之前添加值為 val 的節(jié)點(diǎn)。如果 index 等于鏈表的長(zhǎng)度，則該節(jié)點(diǎn)將附加到鏈表的末尾。如果 index 大于鏈表長(zhǎng)度，則不會(huì)插入節(jié)點(diǎn)。如果index小于0，則在頭部插入節(jié)點(diǎn)。
deleteAtIndex(index)：如果索引 index 有效，則刪除鏈表中的第 index 個(gè)節(jié)點(diǎn)。
示例：
MyLinkedList linkedList = new MyLinkedList();
linkedList.addAtHead(1);
linkedList.addAtTail(3);
linkedList.addAtIndex(1,2); //鏈表變?yōu)?-> 2-> 3
linkedList.get(1); //返回2
linkedList.deleteAtIndex(1); //現(xiàn)在鏈表是1-> 3
linkedList.get(1); //返回3
提示：
所有val值都在 [1, 1000] 之內(nèi)。
操作次數(shù)將在 [1, 1000] 之內(nèi)。
請(qǐng)不要使用內(nèi)置的 LinkedList 庫(kù)。
思路：這個(gè)題就是開(kāi)放式題，簡(jiǎn)單來(lái)說(shuō)我的思路就是用ArrayList?他只說(shuō)不要用內(nèi)置的LinkedList了啊。。然后頭插就是add 在index=0的，尾插就是正常追加。。。然后這個(gè)題的考點(diǎn)呢？什么鬼。。有點(diǎn)蒙，我不確定這么實(shí)現(xiàn)是不是在要求內(nèi)的。要不然自己寫(xiě)個(gè)鏈表也行啊，但是這樣刪除指定下標(biāo)元素的話就是從頭理到那個(gè)下標(biāo)再去刪除。。。所以種種實(shí)現(xiàn)方式我選擇去看題解。。
public class ListNode {
int val;
ListNode next;
ListNode(int x) { val = x; }
}
class MyLinkedList {
int size;
ListNode head; // sentinel node as pseudo-head
public MyLinkedList() {
size = 0;
head = new ListNode(0);
}
/** Get the value of the index-th node in the linked list. If the index is invalid, return -1. */
public int get(int index) {
// if index is invalid
if (index < 0 || index >= size) return -1;
ListNode curr = head;
// index steps needed
// to move from sentinel node to wanted index
for(int i = 0; i < index + 1; ++i) curr = curr.next;
return curr.val;
}
/** Add a node of value val before the first element of the linked list. After the insertion, the new node will be the first node of the linked list. */
public void addAtHead(int val) {
addAtIndex(0, val);
}
/** Append a node of value val to the last element of the linked list. */
public void addAtTail(int val) {
addAtIndex(size, val);
}
/** Add a node of value val before the index-th node in the linked list. If index equals to the length of linked list, the node will be appended to the end of linked list. If index is greater than the length, the node will not be inserted. */
public void addAtIndex(int index, int val) {
// If index is greater than the length,
// the node will not be inserted.
if (index > size) return;
// [so weird] If index is negative,
// the node will be inserted at the head of the list.
if (index < 0) index = 0;
++size;
// find predecessor of the node to be added
ListNode pred = head;
for(int i = 0; i < index; ++i) pred = pred.next;
// node to be added
ListNode toAdd = new ListNode(val);
// insertion itself
toAdd.next = pred.next;
pred.next = toAdd;
}
/** Delete the index-th node in the linked list, if the index is valid. */
public void deleteAtIndex(int index) {
// if the index is invalid, do nothing
if (index < 0 || index >= size) return;
size--;
// find predecessor of the node to be deleted
ListNode pred = head;
for(int i = 0; i < index; ++i) pred = pred.next;
// delete pred.next
pred.next = pred.next.next;
}
}
/**
* Your MyLinkedList object will be instantiated and called as such:
* MyLinkedList obj = new MyLinkedList();
* int param_1 = obj.get(index);
* obj.addAtHead(val);
* obj.addAtTail(val);
* obj.addAtIndex(index,val);
* obj.deleteAtIndex(index);
*/
代碼就這樣了，這個(gè)題我覺(jué)得更沒(méi)啥好說(shuō)的，下一題。
兩個(gè)字符串的最小ASCII刪除和
題目：給定兩個(gè)字符串s1, s2，找到使兩個(gè)字符串相等所需刪除字符的ASCII值的最小和。
示例 1:
輸入: s1 = "sea", s2 = "eat"
輸出: 231
解釋: 在 "sea" 中刪除 "s" 并將 "s" 的值(115)加入總和。
在 "eat" 中刪除 "t" 并將 116 加入總和。
結(jié)束時(shí)，兩個(gè)字符串相等，115 + 116 = 231 就是符合條件的最小和。
示例 2:
輸入: s1 = "delete", s2 = "leet"
輸出: 403
解釋: 在 "delete" 中刪除 "dee" 字符串變成 "let"，
將 100[d]+101[e]+101[e] 加入總和。在 "leet" 中刪除 "e" 將 101[e] 加入總和。
結(jié)束時(shí)，兩個(gè)字符串都等于 "let"，結(jié)果即為 100+101+101+101 = 403 。
如果改為將兩個(gè)字符串轉(zhuǎn)換為 "lee" 或 "eet"，我們會(huì)得到 433 或 417 的結(jié)果，比答案更大。
注意:
0 < s1.length, s2.length <= 1000。
所有字符串中的字符ASCII值在[97, 122]之間。
思路：這個(gè)題可以簡(jiǎn)單的理解為找出兩個(gè)字符串的最大公共子序列，并且使其ASCII編碼最大（因?yàn)榭偩幋a是一定的，留下的越大刪除的越小。）按照這個(gè)思路我們可以先獲取最大公共子序列，因?yàn)樽址a沒(méi)有倍數(shù)關(guān)系，不存在某兩個(gè)字符頂一個(gè)字符，所以肯定是找最大公共子序列。可能結(jié)果有多個(gè)，但是選擇ASCII編碼最大的那個(gè)。我去實(shí)現(xiàn)下試試
ac了，這個(gè)題不算難，我先貼代碼再解釋：
class Solution {
public int minimumDeleteSum(String s1, String s2) {
int len = s1.length();
int len2 = s2.length();
int sum = 0;
for(int i = 0;i<len;i++) sum += s1.charAt(i);
for(int i = 0;i<len2;i++) sum += s2.charAt(i);
int[][] dp = new int[len+1][len2+1];
for(int i =0;i<len;i++) {
for(int j = 0;j<len2;j++) {
if(s1.charAt(i) == s2.charAt(j)) {
dp[i+1][j+1] = dp[i][j]+((int)s1.charAt(i));
}else {
dp[i+1][j+1] = Math.max(dp[i][j+1], dp[i+1][j]);
}
}
}
return sum-(dp[len][len2]*2);
}
}
這里我的思路和上面的差不多，一開(kāi)始是求出最長(zhǎng)子序列的長(zhǎng)度，用的是常規(guī)的dp計(jì)數(shù)法，代碼如下：
public int minimumDeleteSum(String s1, String s2) {
int len = s1.length();
int len2 = s2.length();
int[][] dp = new int[len+1][len2+1];
for(int i =0;i<len;i++) {
for(int j = 0;j<len2;j++) {
if(s1.charAt(i) == s2.charAt(j)) {
dp[i+1][j+1] = dp[i][j]+1;
}else {
dp[i+1][j+1] = Math.max(dp[i][j+1], dp[i+1][j]);
}
}
}
return dp[len][len2];
}
這樣一個(gè)方法是求出最長(zhǎng)子序列的長(zhǎng)度的。但是這里有一個(gè)問(wèn)題，可能同樣長(zhǎng)度有好多，所以怎么找出最長(zhǎng)子序列的ASCII碼最大值呢？于是乎這里不要用計(jì)數(shù)的方式，而是直接記ASCII碼。也無(wú)所謂長(zhǎng)度不長(zhǎng)度的，反正碼大就行。
然后最后的結(jié)果其實(shí)是最大的子序列的ASCII碼的值。
又因?yàn)閮蓚€(gè)字符串都保存這些字符，所以*2就是有用的字符?？倲?shù)-有用的就是刪除了的字符。
感覺(jué)思路沒(méi)啥問(wèn)題，我去看看性能第一的代碼了：
class Solution {
public int minimumDeleteSum(String s1, String s2) {
char[] c1 = s1.toCharArray();
char[] c2 = s2.toCharArray();
int m = c1.length;
int n = c2.length;
int[] dp = new int[n + 1];
for(int i = n - 1; i >= 0; i--) {
dp[i] = dp[i + 1] + c2[i];
}
for(int i = m - 1; i >= 0; i--) {
int pre = dp[n];
dp[n] += c1[i];
for(int j = n - 1; j >= 0; j--) {
int temp = dp[j];
if(c1[i] == c2[j]) {
dp[j] = pre;
} else {
dp[j] = Math.min(dp[j] + c1[i], dp[j + 1] + c2[j]);
}
pre = temp;
}
}
return dp[0];
}
}
感覺(jué)思路差不多，只不過(guò)人家是倒著往前算的。。還算是比較好看懂，這個(gè)題就這樣了啊。
乘積小于K的子數(shù)組
題目：給定一個(gè)正整數(shù)數(shù)組 nums。找出該數(shù)組內(nèi)乘積小于 k 的連續(xù)的子數(shù)組的個(gè)數(shù)。
示例 1:
輸入: nums = [10,5,2,6], k = 100
輸出: 8
解釋: 8個(gè)乘積小于100的子數(shù)組分別為: [10], [5], [2], [6], [10,5], [5,2], [2,6], [5,2,6]。
需要注意的是 [10,5,2] 并不是乘積小于100的子數(shù)組。
說(shuō)明:
0 < nums.length <= 50000
0 < nums[i] < 1000
0 <= k < 10^6
思路：這個(gè)題怎么說(shuō)呢，暴力法就是遍歷。因?yàn)槭沁B續(xù)數(shù)組，所以直到下一個(gè)不合適的位置就好了，但是我覺(jué)得有可能會(huì)超時(shí)，一會(huì)兒可以試試。而優(yōu)化算法呢，就是滑窗。下一個(gè)元素不用從下下一個(gè)開(kāi)始一個(gè)個(gè)往后算了， 前面符合要求的后面肯定也符合。反正有很明確的思路，我去實(shí)現(xiàn)試試
我就這么說(shuō)吧，當(dāng)我第一次看到測(cè)試案例的無(wú)數(shù)個(gè)1，我就是知道我超時(shí)了。然后第二次看到測(cè)試案例無(wú)數(shù)個(gè)1里面混了一個(gè)6，我就知道這個(gè)測(cè)試案例太騷了。先貼代碼：
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
int sum = 1;
int res = 0;
int j = 0;
for(int i = 0;i<nums.length;i++) {
if(nums[i]>=k) continue;
j = Math.max(i,j);
for(;j<nums.length;j++) {
sum = sum * nums[j];
if(sum>=k) break;
}
//j到這里一定是第一個(gè)不滿足條件的下標(biāo)（也可能是沒(méi)元素了）
res += j-i;
//因?yàn)槌说趈個(gè)已經(jīng)超過(guò)了，所以退回到?jīng)]超過(guò)的時(shí)候
if(j<nums.length) sum /= nums[j];
//當(dāng)前的結(jié)果是上一個(gè)最大結(jié)果除第一個(gè)數(shù)
sum /= nums[i];
}
return res;
}
}
思路蠢得要死，但是都做了三分之二了，所以咬牙用這個(gè)思路做了下來(lái)。我覺(jué)得這個(gè)思路應(yīng)該挺屌的，不知道為啥我實(shí)現(xiàn)起來(lái)性能這么差，應(yīng)該就是我這個(gè)人的問(wèn)題。。我去看看性能排行第一的代碼：
class Solution {
public int numSubarrayProductLessThanK(int[] nums, int k) {
if (nums == null || nums.length == 0 || k <= 1) return 0;
int count = 0, prod = 1;
for (int i = 0, j = 0; i < nums.length; i++) {
prod *= nums[i];
while (prod >= k) {
prod /= nums[j++];
}
count += i - j + 1;
}
return count;
}
}
這個(gè)思路和我的多像啊，也就思路像，處理起來(lái)完全比不上，心都碎了。
一個(gè)很完美的雙指針。j是左邊的下標(biāo)。i是最后的下標(biāo)。一開(kāi)始左邊的固定，右邊的往后走，發(fā)現(xiàn)溢出了左邊下標(biāo)右移。
反正是看能看懂，寫(xiě)又寫(xiě)不出來(lái)。太難了。
本篇筆記就記到這里，如果稍微幫到你了記得點(diǎn)個(gè)喜歡點(diǎn)個(gè)關(guān)注，也祝大家工作順順利利！生活健健康康！
