สมมติว่าเรามีรายการตัวเลขที่เรียกว่า nums และอีกจำนวนหนึ่งคือ k เราต้องตรวจสอบว่ารายการสามารถแบ่งออกเป็นรายการได้หรือไม่ โดยแต่ละรายการมีค่า k และค่าต่างๆ เพิ่มขึ้นอย่างต่อเนื่อง
ดังนั้น หากอินพุตมีค่าเท่ากับ nums =[4, 3, 2, 4, 5, 6], k =3 ผลลัพธ์จะเป็น True เนื่องจากเราสามารถแบ่งรายการออกเป็น [2, 3, 4] และ [ 4, 5, 6]
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
กำหนดหนึ่งแผนที่
-
สำหรับแต่ละคีย์ใน m
-
เพิ่ม m[it] ขึ้น 1
-
-
โอเค :=จริง
-
ในขณะที่ (ขนาดของ m ไม่ใช่ 0 และ ok เป็นจริง) ทำ -
-
โอเค :=เท็จ
-
สำหรับแต่ละคีย์-ค่าจับคู่ในหน่วย m
-
ถ้า (it.key - 1) ไม่อยู่ในหน่วย m แล้ว −
-
ธง :=จริง
-
สำหรับการเริ่มต้น i :=it.key เมื่อฉัน <=it.key + k - 1 อัปเดต (เพิ่ม i ขึ้น 1) ทำ -
-
ถ้าฉันไม่มีอยู่ใน m แล้ว −
-
ธง :=เท็จ
-
-
-
ถ้าแฟล็กเป็นจริง −
-
สำหรับการเริ่มต้น i :=it.key เมื่อฉัน <=it.key + k - 1 อัปเดต (เพิ่ม iby 1) ทำ -
-
(ลด m[i] ลง 1)
-
ถ้า m[i] เท่ากับ 0 แล้ว −
-
ลบฉันออกจาก m
-
-
-
โอเค :=จริง
-
ออกจากวง
-
-
-
-
-
คืนค่า จริง เมื่อ m ว่างเปล่า มิฉะนั้น เท็จ
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น -
ตัวอย่าง
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
bool solve(vector<int> nums, int k) {
map <int, int> m;
for(auto& it : nums){
m[it]++;
}
bool ok = true;
while(m.size() && ok){
ok = false;
for(auto& it : m){
if(!m.count(it.first - 1)){
bool flag = true;
for(int i = it.first; i <= it.first + k - 1;i++){
if(!m.count(i))
flag = false;
}
if(flag){
for(int i = it.first; i <= it.first + k - 1;i++){
m[i]--;
if(m[i] == 0)
m.erase(i);
}
ok = true;
break;
}
}
}
}
return m.empty();
}
};
main(){
vector<int> v = {4, 3, 2, 4, 5, 6};
Solution ob;
cout << ob.solve(v, 3);
}
อินพุต
{4, 3, 2, 4, 5, 6} ผลลัพธ์
1
