Computer >> कंप्यूटर ट्यूटोरियल >  >> प्रोग्रामिंग >> C++

C++ में सूची से nums[i] < nums[k] < nums[j] ट्रिपलेट ढूंढने का प्रोग्राम

समस्या विवरण

मान लीजिए हमारे पास nums नामक संख्याओं की एक सूची है, हमें जांचना है कि क्या (i, j, k) जैसे ट्रिपलेट्स मौजूद हैं जहां i < j < k और nums[i] < nums[k] < nums[j]।

उदाहरण के लिए, यदि इनपुट है nums = [2, 12, 1, 4, 4], तो आउटपुट True होगा, क्योंकि [2, 12, 4] मानदंड से मेल खाता है क्योंकि 2 < 4 < 12।

हल करने का दृष्टिकोण

इस समस्या को हल करने के लिए हम निम्नलिखित चरणों का पालन करेंगे:

  1. n := nums का आकार
  2. आकार n का एक ऐरे left परिभाषित करें
  3. left[0] := nums[0]
  4. i := 1 से n-1 तक: left[i] := min(nums[i], left[i-1])
  5. एक स्टैक st परिभाषित करें
  6. i := n-1 से 1 तक (घटते क्रम में):
    • x := left[i-1]
    • जब तक st खाली नहीं है और st का शीर्ष ≤ x: st से पॉप करें
    • यदि st खाली नहीं है और x < nums[i] और nums[i] > st का शीर्ष, तो true वापस करें
    • nums[i] को st में पुश करें
  7. false वापस करें

उदाहरण

#include <bits/stdc++.h>
using namespace std;

class Solution {
public:
    bool solve(vector<int>& nums) {
        int n = nums.size();
        vector<int> left(n);
        left[0] = nums[0];
        for (int i = 1; i < n; i++) {
            left[i] = min(nums[i], left[i - 1]);
        }
        stack<int> st;
        for (int i = n - 1; i >= 1; i--) {
            int x = left[i - 1];
            while (!st.empty() && st.top() <= x)
                st.pop();
            if (!st.empty() && x < nums[i] && nums[i] > st.top())
                return true;
            st.push(nums[i]);
        }
        return false;
    }
};

bool solve(vector<int>& nums) {
    return (new Solution())->solve(nums);
}

int main() {
    vector<int> v = {2, 12, 1, 4, 4};
    cout << solve(v);
}

इनपुट

{2, 12, 1, 4, 4}

आउटपुट

1
  1. C++ में डौबली लिंक्ड लिस्ट का आकार ढूंढना C++ में डौबली लिंक्ड लिस्ट का आकार ढूंढना

    इस समस्या में, हमें एक डौबली लिंक्ड लिस्ट दी गई है। हमारा कार्य C++ में डौबली लिंक्ड लिस्ट का आकार ढूंढने के लिए एक प्रोग्राम बनाना है। डौबली लिंक्ड लिस्ट एक विशेष प्रकार की लिंक्ड लिस्ट है जिसमें नेविगेशन दोनों तरीकों से संभव है, आगे और पीछे आसानी से सिंगल लिंक्ड लिस्ट की तुलना में। डौबली लिंक्ड ल

  1. - पायथन में संख्याओं की सूची से अंकगणितीय उपअनुक्रमों की संख्या गिनने का प्रोग्राम

    संख्याओं की सूची nums दी गई है। लंबाई ≥ 3 के अंकगणितीय उपअनुक्रमों (subsequences) की संख्या गिनें। अंकगणितीय अनुक्रम वह है जहां लगातार अंतर समान हो। उदाहरण इनपुट: nums = [6, 12, 13, 8, 10, 14] आउटपुट: 3 उपअनुक्रम: [6, 8, 10], [6, 10, 14], [12, 13, 14]। एल्गोरिदम (DP के साथ हैश मैप) dp = डिक्शनरी

  1. - पायथन प्रोग्राम सूची से N सबसे बड़े तत्व खोजने के लिए

    एक पूर्णांक सूची दी गई है, हमारा कार्य सूची में N सबसे बड़े तत्व ढूंढना है। उदाहरण इनपुट : [40, 5, 10, 20, 9] N = 2 आउटपुट: [40, 20] एल्गोरिदम चरण 1: एक पूर्णांक सूची और सबसे बड़ी संख्या की संख्या इनपुट करें। चरण 2: पहले सूची को N बार पार करें। चरण 3: प्रत्येक पारगमन में सबसे बड़ा मान ढूंढें और इसे