Java?C++題解leetcode904水果成籃
更新時間：2022年10月19日 11:53:45 作者：AnjaVon
這篇文章主要為大家介紹了Java?C++題解leetcode904水果成籃示例詳解，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪
題目要求
閱讀理解
讀完題的我be like:
去看了遍英文版就懂了，題目中的種類【type】不是種類數(shù)……每個數(shù)字代表一種樹【用個字母啥的表示或者翻譯成類型就好理解多了】，那么目標(biāo)就是找從哪里開始可以維持兩種數(shù)字（種類）無規(guī)律交替出現(xiàn)的狀態(tài)最久，這個最久是多少棵樹。
思路：滑動窗口
- 窗口里可放兩棵樹，一棵是棗樹，另一棵還是棗樹。 向后遍歷整排樹，并更新最長狀態(tài)。
Java
數(shù)組
class Solution {
public int totalFruit(int[] fruits) {
int res = 0;
int[] win = new int[fruits.length + 10];
for (int l = 0, r = 0, tot = 0; r < fruits.length; r++) {
if (++win[fruits[r]] == 1)
tot++; // 當(dāng)前種類統(tǒng)計
while (tot > 2) {
if (--win[fruits[l++]] == 0)
tot--;
}
res = Math.max(res, r - l + 1); // 維護(hù)最長狀態(tài)
}
return res;
}
}
- 時間復(fù)雜度：O(n)
- 空間復(fù)雜度：O(n)
哈希表
可使用哈希表構(gòu)建窗口，降低空間復(fù)雜度。
- 鍵對應(yīng)籃子，值對應(yīng)同類樹數(shù)量；
- 當(dāng)值為000注意要徹底刪掉鍵。
class Solution {
public int totalFruit(int[] fruits) {
Map<Integer, Integer> win = new HashMap<Integer, Integer>();
int l = 0, res = 0;
for (int r = 0; r < fruits.length; r++) {
win.put(fruits[r], win.getOrDefault(fruits[r], 0) + 1);
while (win.size() > 2) { // 窗口大小即種類數(shù)
win.put(fruits[l], win.get(fruits[l]) - 1);
if (win.get(fruits[l]) == 0)
win.remove(fruits[l]); // 徹底刪除鍵值
l++;
}
res = Math.max(res, r - l + 1);
}
return res;
}
}
- 時間復(fù)雜度：O(n)
- 空間復(fù)雜度：O(1)
C++
數(shù)組
class Solution {
public:
int totalFruit(vector<int>& fruits) {
int res = 0;
int win[fruits.size() + 10];
memset(win, 0, sizeof(win));
for (int l = 0, r = 0, tot = 0; r < fruits.size(); r++) {
if (++win[fruits[r]] == 1)
tot++; // 當(dāng)前種類統(tǒng)計
while (tot > 2) {
if (--win[fruits[l++]] == 0)
tot--;
}
res = max(res, r - l + 1); // 維護(hù)最長狀態(tài)
}
return res;
}
};
- 時間復(fù)雜度：O(n)
- 空間復(fù)雜度：O(n)
哈希表
可使用哈希表構(gòu)建窗口，降低空間復(fù)雜度。
class Solution {
public:
int totalFruit(vector<int>& fruits) {
unordered_map<int, int> win;
int l = 0, res = 0;
for (int r = 0; r < fruits.size(); r++) {
if (win.count(fruits[r]))
win[fruits[r]]++;
else
win[fruits[r]] = 1;
while (win.size() > 2) { // 窗口大小即種類數(shù)
win[fruits[l]]--;
if (win[fruits[l]] == 0)
win.erase(fruits[l]); // 徹底刪除鍵值
l++;
}
res = max(res, r - l + 1);
}
return res;
}
};
- 時間復(fù)雜度：O(n)
- 空間復(fù)雜度：O(1)
總結(jié)
- 今天不想rust了……主體和這兩種語言差不多，要多些類型轉(zhuǎn)換balabala的內(nèi)容
以上就是Java C++題解leetcode904水果成籃的詳細(xì)內(nèi)容，更多關(guān)于Java C++題解水果成籃的資料請關(guān)注腳本之家其它相關(guān)文章！
您可能感興趣的文章:
相關(guān)文章
這篇文章主要介紹了java socket的正確關(guān)閉姿勢，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-06-06
談?wù)凷pring Boot 數(shù)據(jù)源加載及其多數(shù)據(jù)源簡單實現(xiàn)(小結(jié))
這篇文章主要介紹了談?wù)凷pring Boot 數(shù)據(jù)源加載及其多數(shù)據(jù)源簡單實現(xiàn)，小編覺得挺不錯的，現(xiàn)在分享給大家，也給大家做個參考。一起跟隨小編過來看看吧2019-04-04
這篇文章主要介紹了Java中枚舉類型的一種使用方式，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-08-08
這篇文章主要介紹了springboot配置文件讀取pom文件信息方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-02-02
SpringBoot+MyBatis-Plus實現(xiàn)分頁的項目實踐
MyBatis-Plus是基于MyBatis的持久層增強工具,提供簡化CRUD、代碼生成器、條件構(gòu)造器、分頁及樂觀鎖等功能,極大簡化了開發(fā)工作量并提高了開發(fā)效率,本文就來介紹一下SpringBoot+MyBatis-Plus實現(xiàn)分頁的項目實踐,感興趣的可以了解一下2024-11-11
這篇文章主要為大家詳細(xì)介紹了Java?ynchronized重量級鎖的核心原理，文中示例代碼介紹的非常詳細(xì)，具有一定的參考價值，感興趣的小伙伴們可以參考一下，希望能夠給你帶來幫助2022-03-03
Mybatis往Mapper.xml文件中傳遞多個參數(shù)問題
這篇文章主要介紹了Mybatis往Mapper.xml文件中傳遞多個參數(shù)問題,具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教2024-05-05
這篇文章主要介紹了強烈推薦MyBatis?三種批量插入方式的比較，文章圍繞主題展開詳細(xì)的內(nèi)容介紹，具有一定的參考價值，需要的小伙伴可以參考一下2022-07-07
遍歷集合我相信大部分coder都會遇到,也經(jīng)常使用,而Java給我們提供了多種選擇,接下來就讓我們一起來看看吧,需要的朋友可以參考下2021-05-05
這篇文章主要介紹了解決springboot上傳圖片后無法立即訪問需重啟的問題,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-12-12