تراکنش های نامعتبر راه حل LeetCode

یک آرایه از تراکنش رشته ها به شما داده می شود که در آن تراکنش ها[i] از مقادیر جدا شده با کاما تشکیل شده است که نشان دهنده نام، زمان (بر حسب دقیقه)، مقدار و شهر تراکنش است.

فهرستی از تراکنش هایی که احتمالاً نامعتبر هستند را برگردانید. شما می توانید پاسخ را به هر ترتیبی برگردانید.

ورودی: معاملات = ["alice, 20, 800, mtv","alice, 50, 100, beijing"] خروجی: ["alice, 20, 800, mtv","alice, 50, 100, beijing"] توضیح: تراکنش اول نامعتبر است زیرا تراکنش دوممعامله در فاصله 60 دقیقه انجام می شود، نام یکسانی دارد و در شهر دیگری است. به همین ترتیب مورد دوم نیز باطل است.

توضیح

رویکرد Bruteforce:

ایده اصلی ایجاد مجموعه ای برای حذف موارد تکراری احتمالی هنگام مشاهده دو شرایط نامعتبر متفاوت (1000 دلار و در مدت 60 دقیقه در یک شهر دیگر) است. سپس با مقایسه مکرر هر تراکنش با تمام تراکنش های دیگر، آن را به صورت brute force انجام دهید. انجام این کار بسیار آسان است، اما بهینه نیست.

رویکرد بهینه:

1. یک ساختار داده تراکنش ایجاد کنید تا بتوان ویژگی ها را به راحتی در یک آرایه تراکنش ها جستجو و ذخیره کرد
2. مرتب سازی معاملات بر اساس آرایه در زمان
3. در آرایه تراکنش ها تکرار کنید و یک جدول/فرهنگ هش با نام به عنوان کلید، و آرایه ای از شاخص های تراکنش به عنوان مقدار ایجاد کنید.
4. از طریق فرهنگ لغت تکرار کنید و از طریق آرایه شاخص های تراکنش خاص نام حلقه بزنید.
   • چک بیش از 1000 دلار: اگر مبلغ تراکنش فعلی بیشتر از 1000 باشد، آن را به بقیه اضافه کنید و به تراکنش بعدی ادامه دهید.
   • بررسی ظرف 60 دقیقه: از اشاره گرهای چپ و راست برای نمایش تراکنش های احتمالی همسایه که در 60 دقیقه هستند استفاده کنید.
   • اگر تراکنش فعلی در 60 دقیقه همسایه ای داشت، بررسی کنید که آیا شهر متفاوت است یا خیر. اگر چنین است، به res اضافه کنید و به تراکنش های بعدی ادامه دهید.

1 ما باید تراکنش ها را بر اساس زمان مرتب کنیم، بنابراین یک تابع تبدیل رشته به یک ساختار سفارشی شده مورد نیاز است. 2 برای کاهش تلاش برای مقایسه تراکنش ها، از unordered_map برای طبقه بندی آنها بر اساس نام استفاده می کنیم. 3 برای ایجاد آسان نتیجه، رشته ورودی و یک پرچم bool را به ساختار اضافه می کنیم، با اطلاعات دیگر در تراکنش ها، طرح ساختار 6 عضوی را دریافت می کنیم. 4 برای رسیدن به عملکرد بهتر، می توانیم فقط برای تراکنش هایی با همین نام مرتب سازی کنیم.

کد

کد C++ برای تراکنش نامعتبر

راه حل کلاس; CustomerDetail readyCustomerObject(رشته ها)CustomerDetail obj = CustomerDetail(); obj.name=temp[0]; obj.time=stoi(temp[1]); obj.amount=stoi(temp[2]); obj.city=temp[3]; retu obj;>بردار نامعتبر تراکنش ها (بردار و تراکنش ها)Hashmap ؛int i = 0 ؛برای (رشته S: معاملات)1000 ؛if (hashmap. find (obj. name)! = hashmap. end ())> hashmap[obj.name].push_back(i); details.push_back(obj); i++;>وکتور ANS ؛برای (i = 0 ؛ iretu ans;>>;

کد جاوا برای معامله نامعتبر

راه حل کلاس(); final Map>MAP = Hashmap جدید<>() ؛/ * * نقشه ای با نام به عنوان کلید و ارزش به عنوان لیست معاملات برای آن نام */ برای (معامله رشته نهایی: معاملات) بسازیددیگر(); list.add(tran); map.put(tran.name, list);>>برای (معامله رشته نهایی: معاملات)> retu invalid;>ISVALID Boolean عمومی (معاملات لیست نهایی ، معامله نهایی) retu true;>معامله کلاس/ * * مبلغ بیش از 1000 دلار ، یا ؛* * اگر در طی (و از جمله) 60 دقیقه معامله دیگر با * با همین نام در یک شهر متفاوت اتفاق بیفتد. هر معاملات رشته ای معامله [i] * از مقادیر جدا شده کاما تشکیل شده است که نام ، زمان (در دقیقه) ، * مقدار و شهر معامله را نشان می دهد.*/ عمومی Boolean InvalidTransaction (Final String City ، زمان نهایی int)Boolean Bettercity Private (Final String City ، Final Int Time)1000;>>>

کد پایتون برای معامله نامعتبر

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 ("<>,<>,<>,<>"<>,<>,<>"

تجزیه و تحلیل پیچیدگی برای معاملات نامعتبر راه حل LeetCode

پیچیدگی زمانی

پیچیدگی فضا

O (1) زیرا ما از هیچ فضای اضافی استفاده نمی کنیم.