Etibarsız Əməliyyatlar LeetCode Həll

Çətinlik səviyyəsi Mühit
Tez-tez soruşulur Amazon alma BloombergBaxılıb 20

Problem bəyanat

Etibarsız Əməliyyatlar LeetCode Həlli – Tranzaksiya, ehtimal ki, etibarsızdır, əgər:

  • məbləği keçir $1000, və ya;
  • daxilində baş verərsə (və daxil olmaqla) 60 ilə başqa bir əməliyyatın dəqiqələri eyni ad bir fərqli şəhər.

Sizə bir sıra sətirlər verilir transaction hara transactions[i] əməliyyatın adını, vaxtı (dəqiqələrlə), məbləği və şəhəri ifadə edən vergüllə ayrılmış qiymətlərdən ibarətdir.

siyahısını qaytarın transactions ola bilsin ki, etibarsızdır. Cavabı geri qaytara bilərsiniz hər hansı bir sifariş.

Input: transactions = ["alice,20,800,mtv","alice,50,100,beijing"]
Output: ["alice,20,800,mtv","alice,50,100,beijing"]
Explanation: The first transaction is invalid because the second transaction occurs within a difference of 60 minutes, have the same name and is in a different city. Similarly the second one is invalid too.

Izahat

Bruteforce yanaşması:

Əsas ideya bir dəst yaratmaqdır mümkün dublikatları silin İki fərqli baxarkən ($1000 və fərqli bir şəhərdə 60 dəqiqə içində) şərtlər etibarsızdır. Sonra hər bir əməliyyatı bütün digər əməliyyatlarla təkrar-təkrar müqayisə edərək kobud şəkildə zorlayın. Bunu etmək çox asandır, lakin optimal deyil.

Optimallaşdırılmış yanaşma:

  1. Bir yaradın transaction atributlar asanlıqla sorğulana və saxlanıla bilən məlumat strukturu transactions array
  2. Sırala transactions massiv əsasında time
  3. vasitəsilə təkrarlayın transactions massivi və ilə hash cədvəli/lüğət yaradın name açarı və bir sıra kimi transaction indexes dəyər kimi.
  4. Lüğətdə təkrarlayın və keçiddən keçin name xüsusi transaction indexes serial.
    • Artıq 1000 dollar yoxlamaq: Əgər cari əməliyyat amount daha çox 1000, sonra əlavə edin res və növbəti əməliyyata davam edin.
    • Ərzində 60 dəqiqə yoxlaması: daxilində olan mümkün qonşu əməliyyatları təmsil etmək üçün sol və sağ göstəricilərdən istifadə edin 60 dəqiqə.
    • Cari əməliyyat daxilində hər hansı qonşu varsa 60 dəqiqə sonra şəhərin fərqli olub olmadığını yoxlayın. Əgər belədirsə, əlavə edin res və növbəti əməliyyatlara davam edin.

1 Biz əməliyyatları vaxta görə çeşidləməliyik, ona görə də sətri fərdiləşdirilmiş struktura çevirmək funksiyası tələb olunur.
2 Əməliyyatların müqayisəsi səylərini azaltmaq üçün onları adla təsnif etmək üçün unordered_map istifadə edirik.
3 Nəticəni asanlıqla yaratmaq üçün struktura giriş sətri və bool bayrağı əlavə edirik, əməliyyatlardakı digər məlumatlarla birlikdə 6 üzvdən ibarət struktur dizaynını əldə edirik.
4 Daha yaxşı performansa nail olmaq üçün biz yalnız eyni adlı əməliyyatlar üçün çeşidləyə bilərik.

Kodu

Etibarsız əməliyyat üçün C++ kodu

class Solution {
public:
    struct CustomerDetail{
        string name;
        int time;
        int amount;
        string city;
    };
    CustomerDetail prepareCustomerObject(string s){
        vector<string>temp;
        string t;
        istringstream f(s);
        while(getline(f,t,',')){
            temp.push_back(t);
        }
        CustomerDetail obj =  CustomerDetail();
        obj.name=temp[0];
        obj.time=stoi(temp[1]);
        obj.amount=stoi(temp[2]);
        obj.city=temp[3];
        return obj;
    }
    vector<string> invalidTransactions(vector<string>& transactions) {
        vector<bool> invalid(transactions.size());
        vector<CustomerDetail> details;
        map<string/*name*/,vector<int>/*list of indexes*/> hashmap;
        int i=0;
        for(string s: transactions) {
            CustomerDetail obj = prepareCustomerObject(s);
            invalid[i]=obj.amount>1000;
        
            if(hashmap.find(obj.name) != hashmap.end()) {
                vector<int> indexes = hashmap[obj.name];
                
                for(int ind: indexes) {
                    if(details[ind].city != obj.city && abs(obj.time-details[ind].time)<= 60) {
                        invalid[ind]=true;
                        invalid[i]=true;
                    }
                }
            }
            hashmap[obj.name].push_back(i);
            details.push_back(obj);
            i++;
        }
        vector<string> ans;
        for(i=0;i<transactions.size();i++){
            if(invalid[i])
                ans.push_back(transactions[i]);
        }
        return ans;
    }
};

Yanlış Əməliyyat üçün Java Kodu

class Solution {
    public List<String> invalidTransactions(final String[] transactions) {
    final List<String> invalid = new ArrayList<>();
    final Map<String, List<Transaction>> map = new HashMap<>();

    /*
     * build a map with name as key and value as list of transactions for that name
     */
    for (final String transaction : transactions) {
      final Transaction tran = new Transaction(transaction);

      if (map.containsKey(tran.name)) {
        map.get(tran.name).add(tran);
      } else {
        final List<Transaction> list = new ArrayList<>();
        list.add(tran);
        map.put(tran.name, list);
      }
    }

    for (final String transaction : transactions) {
      final Transaction tran = new Transaction(transaction);

      if (!isValid(map.get(tran.name), tran)) {
        invalid.add(transaction);
      }

    }

    return invalid;
  }

  public boolean isValid(final List<Transaction> transactions, final Transaction transaction) {

    /* if there is only one transaction and the amount is less than 1000 */
    if (transactions.size() <= 1 && transaction.amount < 1000)
      return true;

    /* check against all other transaction to check it this one is valid */
    for (final Transaction tran : transactions) {
      if (transaction.invalidTransaction(tran.city, tran.time)) {
        return false;
      }
    }
    return true;
  }

  class Transaction {
    String name;
    int time;
    int amount;
    String city;

    Transaction(final String transaction) {
      final String[] t = transaction.split(",");
      this.name = t[0];
      this.time = Integer.parseInt(t[1]);
      this.amount = Integer.parseInt(t[2]);
      this.city = t[3];
    }

    /*
     * the amount exceeds $1000, or;
     * 
     * if it occurs within (and including) 60 minutes of another transaction with
     * the same name in a different city. Each transaction string transactions[i]
     * consists of comma separated values representing the name, time (in minutes),
     * amount, and city of the transaction.
     */
    public boolean invalidTransaction(final String city, final int time) {
      return invalidAmount() || differentCity(city, time);
    }

    private boolean differentCity(final String city, final int time) {
      return !this.city.equals(city) && Math.abs(this.time - time) <= 60;
    }

    private boolean invalidAmount() {
      return this.amount > 1000;
    }
  }
}

Etibarsız Əməliyyat üçün Python Kodu

class Transaction:
    def __init__(self, name, time, amount, city):
        self.name = name
        self.time = int(time)
        self.amount = int(amount)
        self.city = city

from collections import defaultdict
class Solution:
    def invalidTransactions(self, transactions):
        transactions = [Transaction(*transaction.split(',')) for transaction in transactions]
        transactions.sort(key=lambda t: t.time) # O(nlogn) time

        trans_indexes = defaultdict(list)
        for i, t in enumerate(transactions): # O(n) time
            trans_indexes[t.name].append(i)

        res = []
        for name, indexes in trans_indexes.items(): # O(n) time
            left = right = 0
            for i, t_index in enumerate(indexes):
                t = transactions[t_index]
                if (t.amount > 1000):
                    res.append("{},{},{},{}".format(t.name, t.time, t.amount, t.city))
                    continue
                while left <= len(indexes)-2 and transactions[indexes[left]].time < t.time - 60: # O(60) time
                    left += 1
                while right <= len(indexes)-2 and transactions[indexes[right+1]].time <= t.time + 60: # O(60) time
                    right += 1
                for i in range(left,right+1): # O(120) time
                    if transactions[indexes[i]].city != t.city:
                        res.append("{},{},{},{}".format(t.name, t.time, t.amount, t.city))
                        break

        return res

Etibarsız Əməliyyatlar üçün Mürəkkəblik Təhlili LeetCode Həll

Zamanın mürəkkəbliyi

O (NLogN)

Kosmik Mürəkkəblik

O(1) çünki biz heç bir əlavə yerdən istifadə etmirik.

Referans: https://en.wikipedia.org/wiki/Hash_table

Şərh yaz

Translate »