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

C++ में अद्वितीय भिन्नों की सूची


मान लीजिए हमारे पास भिन्नों की एक सूची है जहां प्रत्येक भिन्न में [अंश, हर] (अंश / हर) होता है। हमें भिन्नों की एक नई सूची ज्ञात करनी है जैसे कि भिन्नों में संख्याएँ:

  • अपने सबसे सरल रूप में हों (20/14, 10/7 बन जाता है)।
  • कोई भी डुप्लिकेट भिन्न (सरल करने के बाद) हटा दिए जाएं।
  • उनके वास्तविक मान के अनुसार आरोही क्रम में सॉर्ट किए जाएं।
  • यदि संख्या ऋणात्मक है, तो '-' चिह्न अंश के साथ होगा।

उदाहरण के लिए, यदि इनपुट है {{16, 8}, {4, 2}, {7, 3}, {14, 6}, {20, 4}, {-6, 12}}, तो आउटपुट [[-1, 2], [2, 1], [7, 3], [5, 1]] होगा।

समाधान दृष्टिकोण

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

  • एक सेट s परिभाषित करें।
  • n := v का आकार
  • एक सरणी r बनाएं।
  • i := 0 से n-1 तक लूप चलाएं:
    • c := |v[i][0]| और |v[i][1]| का GCD
    • v[i][0] := v[i][0] / c
    • v[i][1] := v[i][1] / c
    • {v[i][0], v[i][1]} को r के अंत में डालें।
  • r सरणी को उनके मानों के आधार पर सॉर्ट करें।
  • एक सरणी ret बनाएं।
  • i := 0 से r के आकार - 1 तक लूप चलाएं:
    • यदि ret खाली नहीं है और ret का अंतिम तत्व r[i] के समान है, तो जारी रखें।
    • अन्यथा r[i] को ret के अंत में डालें।
  • ret लौटाएं।

C++ कार्यान्वयन

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

void print_vector(vector<vector<auto>> v) {
    cout << "[";
    for (int i = 0; i < v.size(); i++) {
        cout << "[";
        for (int j = 0; j < v[i].size(); j++) {
            cout << v[i][j] << ", ";
        }
        cout << "],";
    }
    cout << "]" << endl;
}

class Solution {
public:
    static bool cmp(vector<int>& a, vector<int>& b) {
        double aa = (double)a[0] / (double)a[1];
        double bb = (double)b[0] / (double)b[1];
        return aa < bb;
    }
    
    vector<vector<int>> solve(vector<vector<int>>& v) {
        set<vector<int>> s;
        int n = v.size();
        vector<vector<int>> r;
        for (int i = 0; i < n; i++) {
            int c = __gcd(abs(v[i][0]), abs(v[i][1]));
            v[i][0] /= c;
            v[i][1] /= c;
            r.push_back({v[i][0], v[i][1]});
        }
        sort(r.begin(), r.end(), cmp);
        vector<vector<int>> ret;
        for (int i = 0; i < r.size(); i++) {
            if (!ret.empty() && ret.back() == r[i]) continue;
            ret.push_back(r[i]);
        }
        return ret;
    }
};

int main() {
    vector<vector<int>> v = {{16, 8}, {4, 2}, {7, 3}, {14, 6}, {20, 4}, {-6, 12}};
    Solution ob;
    print_vector(ob.solve(v));
    return 0;
}

इनपुट

{{16, 8}, {4, 2}, {7, 3}, {14, 6}, {20, 4}, {-6, 12}}

आउटपुट

[[-1, 2, ],[2, 1, ],[7, 3, ],[5, 1, ],]
  1. C++ में अद्वितीय बाइनरी सर्च ट्री C++ में अद्वितीय बाइनरी सर्च ट्री

    समस्यामान लीजिए हमारे पास एक पूर्णांक n है, हमें उन सभी संरचनात्मक रूप से अद्वितीय बाइनरी सर्च ट्री की गिनती करनी है जो 1 से n तक के मान संग्रहीत करते हैं। उदाहरण के लिए, यदि इनपुट 3 है, तो आउटपुट 5 होगा, क्योंकि ट्री इस प्रकार होंगे:समाधान दृष्टिकोणइसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:आ

  1. C++ में अद्वितीय बाइनरी सर्च ट्री II C++ में अद्वितीय बाइनरी सर्च ट्री II

    समस्यामान लीजिए हमारे पास एक पूर्णांक n है, हमें उन सभी संरचनात्मक रूप से अद्वितीय बाइनरी सर्च ट्री को उत्पन्न करना है जो 1 से n तक के मान संग्रहीत करते हैं। उदाहरण के लिए, यदि इनपुट 3 है, तो ट्री इस प्रकार होंगे:समाधान दृष्टिकोणइसे हल करने के लिए हम निम्न चरणों का पालन करेंगे:generate() नामक एक पुन

  1. - C++ में टाइप इन्फरेंस (प्रकार निगमन)

    टाइप इन्फरेंस या डिडक्शन का अर्थ है प्रोग्रामिंग भाषा में एक एक्सप्रेशन के डेटा टाइप का ऑटोमैटिक डिटेक्शन। यह कुछ स्ट्रॉन्गली स्टैटिकली टाइप्ड भाषाओं में मौजूद एक विशेषता है। C++ में, auto कीवर्ड (C++11 में जोड़ा गया) ऑटोमैटिक टाइप डिडक्शन के लिए उपयोग किया जाता है। उदाहरण के लिए, आप एक वेक्टर पर पु