Untitled
plain_text
2 months ago
85 kB
1
Indexable
Never
Contact Info DB: package ContactInfoDB; import java.util.Arrays; import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.Set; class UserSolution { // String là value / giá trị dữ liệu chứ không phải tên trường // 5 fields -> 5 hashMap Map<String, Set<Record>> hashMap[] = new HashMap[5]; void InitDB() { for (int i = 0; i < 5; i++) hashMap[i] = new HashMap<>(); } // hashMap[0] đại diện cho NAME Field, nhận vào keyword là một dữ liệu của // NAME field và match tới // một bản record được lưu trong HashSet void Add(String... fields) { Record record = new Record(fields); for (int i = 0; i < fields.length; i++) hashMap[i].computeIfAbsent(fields[i], k -> new HashSet<>()).add( record); } // khi hashMap get, tham số là String và trả về kiểu Set<Record> // field được biểu thị là int, nên được dùng làm index cho hashMap[] để xác // định kiểu Field // lưu ý Set<Record> được lưu dưới dạng HashSet<>() // lưu ý phương thức getOrDefault // khi không có giá trị ánh xạ nào được trả về, một bản HashSet mới mặc định // sẽ được tạo ra // size khi đó = 0, rỗng int Delete(int field, String str) { Set<Record> records = hashMap[field].getOrDefault(str, new HashSet<>()); int size = records.size(); // xóa record khỏi hashMap // không được phép vừa tìm, duyệt vừa xóa trên records // nên phải tạo một bản copy new HashSet<>(records) để duyệt trên đó for (Record record : new HashSet<>(records)) for (int i = 0; i < 5; i++) hashMap[i].get(record.field[i]).remove(record); return size; } int Change(int field, String str, int changefield, String changestr) { Set<Record> records = hashMap[field].getOrDefault(str, new HashSet<>()); int size = records.size(); for (Record record : new HashSet<>(records)) { hashMap[changefield].get(record.field[changefield]).remove(record); record.field[changefield] = changestr; hashMap[changefield].computeIfAbsent(changestr, k -> new HashSet<>()).add(record); } return size; } // returnfield là index cần request khi đã tìm được bản record -> // record.field[returnfield] Solution.Result Search(int field, String str, int returnfield) { Solution.Result result = new Solution.Result(); Set<Record> records = hashMap[field].getOrDefault(str, new HashSet<>()); result.count = records.size(); if (records.size() == 1) { // tùy với loại Collection mà có cách lấy phần tử khác nhau, đây là // cách tổng quát Record record = (Record) records.toArray()[0]; result.str = record.field[returnfield]; } return result; } } class Record { String field[]; // nhận vào value Record(String... strings) { field = Arrays.copyOf(strings, strings.length); } } package ElectronicBulletinBoard; // VŨ HÀ THÀNH import java.util.HashMap; import java.util.HashSet; import java.util.TreeSet; public class UserSolution2 { private HashMap<String, User> userMap; private HashMap<Integer, Post> postMap; private TreeSet<Post> postTree; private TreeSet<User> userTree; public void init() { userMap = new HashMap<>(); postMap = new HashMap<>(); postTree = new TreeSet<>(); userTree = new TreeSet<>(); } public int writeMessage(char[] mUser, int mID, int mPoint) { String name = new String(mUser).trim(); User user = userMap.computeIfAbsent(name, User::new); Post post = new Post(mID, mPoint, user, null); postMap.put(mID, post); postTree.add(post); update(user, mPoint); return user.point; } private void update(User user, int point) { userTree.remove(user); user.point += point; userTree.add(user); } private void update(Post post, int point) { postTree.remove(post); post.total += point; postTree.add(post); } public int commentTo(char[] mUser, int mID, int mTarget, int mPoint) { User user = userMap .computeIfAbsent(new String(mUser).trim(), User::new); Post target = postMap.get(mTarget); Post post = new Post(mID, mPoint, user, target); update(user, mPoint); postMap.put(mID, post); while (post.target != null) post = post.target; update(post, mPoint); return post.total; } public int erase(int mID) { Post post = postMap.get(mID); int count = remove(post); if (post.target == null) { postTree.remove(post); return post.user.point; } Post parent = post; while (parent.target != null) { parent = parent.target; parent.attached.remove(post); } update(parent, -count); return parent.total; } public int remove(Post post) { int count = post.point; for (Post child : post.attached) count += remove(child); postMap.remove(post.id); update(post.user, -post.point); return count; } public void getBestMessages(int[] mBestMessageList) { int count = 0; for (Post post : postTree) { mBestMessageList[count] = post.id; if (++count == 5) { break; } } } public void getBestUsers(char[][] mBestUserList) { int count = 0; for (User user : userTree) { for (int i = 0; i < user.name.length(); i++) { mBestUserList[count][i] = user.name.charAt(i); } mBestUserList[count][user.name.length()] = '\0'; if (++count == 5) { break; } } } private static class User implements Comparable<User> { public int point; public String name; public User(String name) { this.name = name; } @Override public int compareTo(User o) { return point != o.point ? o.point - point : name.compareTo(o.name); } } private static class Post implements Comparable<Post> { public int id; public int point; public int total; public User user; public Post target; public HashSet<Post> attached = new HashSet<>(); public Post(int id, int point, User user, Post target) { this.id = id; this.point = point; this.total = point; this.user = user; if (target != null) { this.target = target; target.attached.add(this); } } @Override public int compareTo(Post o) { return total != o.total ? o.total - total : id - o.id; } } } package ElectronicBulletinBoard; import java.util.ArrayList; import java.util.Comparator; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.TreeSet; class UserSolution { // map key name -> object User Map<String, User> users = new HashMap<>(); Map<Integer, Message> messages = new HashMap<>(); TreeSet<User> topUsers = new TreeSet<>( (a, b) -> a.point == b.point ? a.name.compareTo(b.name) : b.point - a.point); TreeSet<Message> topPosts = new TreeSet<>( (a, b) -> a.total == b.total ? a.id - b.id : b.total - a.total); // sai, khi khai bao kiểu này, chỉ đúng trong init() // TreeSet<User> topUsers = new TreeSet<>(DesSort); public void init() { users.clear(); messages.clear(); topUsers.clear(); topPosts.clear(); } // được dùng để viết cả post, comment và reply public int writeMessage(char[] mUser, int mID, int mPoint) { String name = new String(mUser).trim(); User user = users.computeIfAbsent(name, k -> new User()); user.name = name; // update điểm // tuy nhiên khi đối tượng được update dữ liệu thuộc tính // treeSet cũng không thay đổi --> với treeSet cần remove và add lại // user.point += mPoint; topUsers.remove(user); user.point += mPoint; topUsers.add(user); // muốn tạo đối tượng Post, trước đó cần tạo đối tượng User Message newPost = new Message(user, mID, mPoint); messages.put(mID, newPost); topPosts.add(newPost); return user.point; } // người có tên mUser, thêm comment hoặc reply mID, có điểm số mPoint vào // post hoặc comment mTarget // return tổng điểm của post mà comment hoặc reply được thêm public int commentTo(char[] mUser, int mID, int mTarget, int mPoint) { writeMessage(mUser, mID, mPoint); Message target = messages.get(mTarget); Message written = messages.get(mID); // nếu target là Post thì target.above == null, khi đó written.above = // target (Post) // nếu target là Comment thì target.above != null và == Post // tóm lại là mục đích ở đây là cắm hết comments và replies vào post // vậy làm sao để phân biệt được đâu là comments, đâu là replies để phục // vụ cho chức năng Delete // sử dụng arrayList bên trong đối tượng written.above = target.above != null ? target.above : target; // khi sử dụng class Message chung chung cho cả 3 kiểu post, comment, // reply // nó sẽ add hết vào treeSet topPosts trong khi yêu cầu là thằng này chỉ // được chứa Post --> cần khắc phục topPosts.remove(written); target.children.add(written); // thêm vào danh sách con arraylist của // target để quản lý // cập nhật điểm cho Post sau khi có thêm comment hoặc reply topPosts.remove(written.above); // xóa Post written.above.total += mPoint; topPosts.add(written.above); return written.above.total; } public int erase(int mID) { Message object = messages.get(mID); if (object.above != null) { // object là comment hoặc reply // cập nhật điểm cho post topPosts.remove(object.above); remove(object); topPosts.add(object.above); return object.above.total; // trả về tổng điểm của post } else { // object là post topPosts.remove(object); remove(object); return object.user.point; // trả về tổng điểm của user viết post } } void remove(Message object) { for (Message m : object.children) { if (m.isAlive) { remove(m); // gọi đệ quy } } // BASE CASE object.isAlive = false; // cập nhật điểm cho User topUsers.remove(object.user); object.user.point -= object.point; topUsers.add(object.user); // cập nhật điểm cho Post nếu object là comment hoặc reply if (object.above != null) { object.above.total -= object.point; } // C2 không cần sử dụng hàm đệ quy vì bài toán chỉ cho 3 tầng } // lưu kết quả ID của top post vào mBestMessageList[] void getBestMessages(int[] mBestMessageList) { int i = 0; for (Message post : topPosts) { mBestMessageList[i] = post.id; if (++i == 5) { break; } } } // mảng char mBestUserList[5][?] lưu tên của top 5 người nhiều điểm nhất void getBestUsers(char[][] mBestUserList) { int i = 0; for (User user : topUsers) { int j; for (j = 0; j < user.name.length(); j++) { mBestUserList[i][j] = user.name.charAt(j); } mBestUserList[i][j] = '\0'; // yêu cầu đề bài là save ký tự 0 vào // cuối if (++i == 5) { break; } } } class User { String name; int point; } // Message là đối tượng được dùng để chỉ chung: Post và Comment // thuộc tính comments trong nó dùng để chỉ chung comments (thuộc 1 Post) // hoặc replies (thuộc 1 comment) class Message { User user; int id, point, total; boolean isAlive = true; Message above; // ? List<Message> children = new ArrayList<>(); // ? Message(User mUser, int mID, int mPoint) { user = mUser; id = mID; total = point = mPoint; } } // sắp xếp giảm dần theo điểm, bằng điểm thì xét tên theo thứ tự từ điển Comparator<User> DesSort = new Comparator<User>() { public int compare(User o1, User o2) { if (o1.point == o2.point) { return o1.name.compareTo(o2.name); } return o2.point - o1.point; } }; } package ElectronicsMarket; // Tham khảo thêm bài làm của CloudyWind và Doãn Thanh Tùng import java.util.ArrayList; import java.util.List; class UserSolution { // danh sách mặt hàng được phân theo [warehouse][type] // mỗi list[][] sẽ là một ArrayList List<Product> list[][] = new ArrayList[2][3]; int charge; // phí ship void init(int mCharge) { charge = mCharge; for (int i = 0; i < 2; i++) { for (int j = 0; j < 3; j++) { // danh sách products trong warehouse i, type j list[i][j] = new ArrayList<UserSolution.Product>(); } } } // thêm sản phẩm vào list, có cùng warehouse và type int stock(int mType, int mPrice, int mPerformance, int mPosition) { list[mPosition][mType].add(new Product(mPrice, mPerformance)); return list[mPosition][mType].size(); } // binary search Solution.Result order(int mBudget) { // res lưu giá tiền không vượt quá mBudget và có max performance Solution.Result res = new Solution.Result(); int l = 0; int r = 1000000; // max performance while (l + 1 < r) { int mid = (l + r) / 2; // lưu giá trị min của mỗi type trong warehouse 0, 1 và cả hai int[][] MinVals = new int[3][3]; for (int i = 0; i < 2; i++) { for (int j = 0; j < 3; j++) { int minPrice = 500000; // max budget for (Product p : list[i][j]) { if (p.performance >= mid && p.price < minPrice) { minPrice = p.price; // tìm product có performance đủ lớn và có giá min // trong list[i][j] } } MinVals[i][j] = minPrice; } } // tìm min trong min của mỗi warehouse MinVals[2][0] = Math.min(MinVals[0][0], MinVals[1][0]); MinVals[2][1] = Math.min(MinVals[0][1], MinVals[1][1]); MinVals[2][2] = Math.min(MinVals[0][2], MinVals[1][2]); // tìm min price của tổng các linh kiện trong các trường hợp min // nếu mua từ cùng một warehouse thì không mất phí vận chuyển charge int minPrice = Math.min(Math.min(MinVals[0][0] + MinVals[0][1] + MinVals[0][2], MinVals[1][0] + MinVals[1][1] + MinVals[1][2]), MinVals[2][0] + MinVals[2][1] + MinVals[2][2] + charge); // đây là giá tiền nhỏ nhất để mua các sản phẩm mà mỗi sản phẩm có // performance lớn hơn mid // tức là giá tiền nhỏ nhất để có được sản phẩm với performance là // mid // vì performanc tổng chính là performance nhỏ nhất trong số các sản // phẩm if (minPrice <= mBudget) { res.mPrice = minPrice; res.mPerformance = l = mid; } else { r = mid; } } return res; } class Product { int price, performance; public Product(int mPrice, int mPerformance) { price = mPrice; performance = mPerformance; } } } package HotelTravel; import java.util.HashMap; import java.util.Map; import java.util.PriorityQueue; import java.util.Queue; class UserSolution { Hotel[] hotels; void init(int N, int mBrands[]) { hotels = new Hotel[N]; for (int i = 0; i < N; i++) { hotels[i] = new Hotel(); hotels[i].brand = mBrands[i]; } } void connect(int mHotelA, int mHotelB, int mDistance) { hotels[mHotelA].roads.put(hotels[mHotelB], mDistance); hotels[mHotelB].roads.put(hotels[mHotelA], mDistance); } int merge(int mHotelA, int mHotelB) { int a = hotels[mHotelA].brand; int b = hotels[mHotelB].brand; int count = 0; for (Hotel hotel : hotels) { if (hotel.brand == b || hotel.brand == a) { hotel.brand = a; ++count; } } return count; } int move(int mStart, int mBrandA, int mBrandB) { for (Hotel hotel : hotels) { // ? hotel.distance = Integer.MAX_VALUE; } Queue<Hotel> queue = new PriorityQueue<>((a, b) -> a.distance - b.distance); // sắp xếp tăng dần hotels[mStart].distance = 0; queue.add(hotels[mStart]); int result = 0; int count = 0; while (true) { Hotel hotel = queue.poll(); // lấy hotel có khoảng cách ngắn nhất // tới hotel xuất phát if (hotel.distance > 0 && (hotel.brand == mBrandA || hotel.brand == mBrandB)) { if (hotel.brand == mBrandA) { mBrandA = -1; } else { mBrandB = -1; } result += hotel.distance; if (++count == 2) { return result; } } // lưu ý cách duyệt key trong map // thuật toán dijkstra, từ node start, duyệt tất cả các con đường // nối từ nó (kể cả các đỉnh đã được duyệt rồi) // cập nhật giá trị cho các node nó nối tới // nếu node nó nối tới đã có giá trị mà lớn hơn giá trị tổng đi từ // đỉnh hiện tại, thì cập nhật lại cho node mới đó // chọn đỉnh có trọng số nhỏ nhất làm điểm đến tiếp theo // những đỉnh làm điểm đến thì không cần duyệt nữa for (Hotel next : hotel.roads.keySet()) { // duyệt danh sách key là // các hotel dưới dạng // Set int road = hotel.roads.get(next); if (hotel.distance + road < next.distance) { queue.remove(next); next.distance = hotel.distance + road; queue.add(next); } } } } class Hotel { int brand; int distance; // khoảng cách min từ vị trí start tới hotel này Map<Hotel, Integer> roads = new HashMap<>(); // mỗi hotel có một map, lưu khoảng cách đường tới các hotel bên cạnh // dùng để connect, thay cho arraylist } } package LibraryClassification; import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.Set; class UserSolution { // private final static int MAX_N = 5; // private final static int MAX_NAME_LEN = 7; // private final static int MAX_TAG_LEN = 4; // map type -> books Map<String, Set<String>> books = new HashMap<>(); // map bookname -> int section // db lưu trữ sách - section phục vụ cho thêm, sửa, xóa Map<String, Integer> map = new HashMap<>(); // M sections, đánh số từ 1 tới M void init(int M) { books.clear(); map.clear(); } void add(char mName[], int mTypeNum, char mTypes[][], int mSection) { for (int i = 0; i < mTypeNum; i++) { books.computeIfAbsent(string(mTypes[i]), k -> new HashSet<>()).add( string(mName)); } map.put(string(mName), mSection); } int moveType(char mType[], int mFrom, int mTo) { // lấy danh sách sách có tham số Type / hashMap // từ danh sách đó lọc ra các sách có tham số Section / hashMap // cập nhật là method put int count = 0; for (String book : books.get(string(mType))) { if (map.get(book) == mFrom) { map.put(book, mTo); count++; } } return count; // trả về số sách được dịch chuyển } void moveName(char mName[], int mSection) { // bản chất là cập nhật section của sách // dùng lại put map.put(string(mName), mSection); } void deleteName(char mName[]) { // sections đánh dấu từ 1 tới M map.put(string(mName), 0); } // trả về số lượng sách thuộc mSection có ít nhất một nhãn dán Type trong // mảng // mTypes // lưu ý đếm trùng // CTDL HashSet int countBook(int mTypeNum, char mTypes[][], int mSection) { Set<String> set = new HashSet<>(); for (int i = 0; i < mTypeNum; i++) { if (books.containsKey(string(mTypes[i]))) { for (String book : books.get(string(mTypes[i]))) { if (map.get(book) == mSection) { set.add(book); } } } } return set.size(); } String string(char[] s) { int n = -1; while (s[++n] != 0) ; return new String(s, 0, n); // char[], startIndex, endIndex } // void mstrcpy(char dst[], char src[]) // { // int c = 0; // while ((dst[c] = src[c]) != '\0') ++c; // } // int mstrcmp(char str1[], char str2[]) // { // int c = 0; // while (str1[c] != '\0' && str1[c] == str2[c]) ++c; // return str1[c] - str2[c]; // } } package LibraryClassification; import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.Set; class UserSolution2 { Map<String, Set<String>> books = new HashMap<>();; Map<String, Integer> sections = new HashMap<>(); void init(int M) { books.clear(); sections.clear(); } void add(char mName[], int mTypeNum, char mTypes[][], int mSection) { for (int i = 0; i < mTypeNum; i++) books.computeIfAbsent(string(mTypes[i]), k -> new HashSet<>()).add( string(mName)); sections.put(string(mName), mSection); } int moveType(char mType[], int mFrom, int mTo) { int cnt = 0; for (String book : books.get(string(mType))) if (sections.get(book) == mFrom) { sections.put(book, mTo); cnt++; } return cnt; } void moveName(char mName[], int mSection) { sections.put(string(mName), mSection); } void deleteName(char mName[]) { sections.put(string(mName), 0); } int countBook(int mTypeNum, char mTypes[][], int mSection) { Set<String> set = new HashSet<>(); for (int i = 0; i < mTypeNum; i++) if (books.containsKey(string(mTypes[i]))) for (String book : books.get(string(mTypes[i]))) if (sections.get(book) == mSection) set.add(book); return set.size(); } String string(char[] s) { int n = -1; while (s[++n] != 0) ; return new String(s, 0, n); } } package LockerAssignment; import java.util.HashMap; import java.util.Map; import java.util.TreeSet; class UserSolution { // map id người --> id allocated locker Map<Integer, Integer> map; // tsSize --> tìm vị trí trống theo yêu cầu để đặt // tsID --> hỗ trợ nối blank space sau khi có người rời TreeSet<Space> tsSize, tsID; int N; // số lockers public void init(int N) { this.N = N; map = new HashMap<>(); // ưu tiên size lớn -> sắp xếp giảm dần theo Size // ưu tiên locker trống đầu tiên -> sắp xếp tăng dần theo Start tsSize = new TreeSet<>((a, b) -> a.size() == b.size() ? a.start - b.start : b.size() - a.size()); // danh sách blank locker theo thứ tự ID tsID = new TreeSet<>((a, b) -> a.start - b.start); tsSize.add(new Space(1, N)); tsID.add(new Space(1, N)); } public int arrive(int mId) { // xác định chuỗi blank dài nhất -> remove tại 2 cây Space blank = tsSize.pollFirst(); tsID.remove(blank); // xác định ID của blank locker để allocated -> return ID này // điểm giữa chuỗi space, nếu chuỗi chẵn thì nhích hơn về bên trái int id = (blank.start + blank.end) / 2; // chuỗi blank dài nhất có start = 1 hoặc end = N if (blank.start == 1) { id = 1; } else if (blank.end == N) { id = N; } map.put(mId, id); // xác định lại các blank space để thêm vào treeSet // nếu chuỗi có độ dài >= 3 và id nằm giữa thì có 2 blank mới được tạo // nếu chuỗi có độ dài 1 thì không có blank nào mới // nếu chuỗi có độ dài >= 2 và id nằm ở đầu hoặc cuối thì có 1 blank mới // được tạo if (id > blank.start) { tsSize.add(new Space(blank.start, id - 1)); tsID.add(new Space(blank.start, id - 1)); } if (id < blank.end) { tsSize.add(new Space(id + 1, blank.end)); tsID.add(new Space(id + 1, blank.end)); } return id; // locker number allocated } public int leave(int mId) { int idSpace = map.remove(mId); Space blank = new Space(idSpace, idSpace); // nối blank space // tìm -> kiểm tra start, end, null -> remove và set lại start end cho // blank Space front = tsID.lower(blank); Space behind = tsID.higher(blank); if (front != null && front.end == idSpace - 1) { tsSize.remove(front); tsID.remove(front); blank.start = front.start; } if (behind != null && behind.start == idSpace + 1) { tsSize.remove(behind); tsID.remove(behind); blank.end = behind.end; } // thêm blank mới (đã được gộp với blank xung quanh) vào treeSet tsSize.add(blank); tsID.add(blank); return N - map.size(); // số lượng ô trống = N - số những vị trí có người, tức // map.size() // C2 là duyệt treeSet, tính tổng các size của các Space trong treeSet } class Space { int start, end, size; // boolean blank ? Space(int mStart, int mEnd) { start = mStart; end = mEnd; } int size() { return end - start + 1; // không cần +1 cũng được } } } package LockerAssignment; import java.util.Comparator; import java.util.HashMap; import java.util.TreeSet; class UserSolution2 { static int N, countEmpty; HashMap<Integer, Range> blankMap = new HashMap<Integer, Range>(); Comparator<Range> compare = new Comparator<Range>() { public int compare(Range o1, Range o2) { if (o1.size == o2.size) { return o1.start - o2.start; } return o2.size - o1.size; } }; TreeSet<Range> ts = new TreeSet<Range>(compare); HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>(); void init(int N) { this.N = N; countEmpty = N; blankMap.clear(); ts.clear(); hm.clear(); addRange(1, N); } void addRange(int start, int end) { // nếu làm theo cách arrive và arrive1 thì không cần đoạn code này // if (start > end) // return; Range newRange = new Range(start, end); blankMap.put(start, newRange); blankMap.put(end, newRange); ts.add(newRange); } void removeRange(Range blank) { blankMap.remove(blank.start); blankMap.remove(blank.end); ts.remove(blank); } public int arrive(int mId) { // đặt thì phải remove Range blank = ts.pollFirst(); blankMap.remove(blank.start); blankMap.remove(blank.end); int idSpace = -1; countEmpty--; if (blank.start == 1) { if (blank.end > 1) { addRange(2, blank.end); } idSpace = 1; } else if (blank.end == N) { if (blank.start < N) { addRange(blank.start, N - 1); } idSpace = N; } else { // idSpace = blank.start + blank.size / 2; // if (blank.size % 2 == 0) { // idSpace--; // } idSpace = (blank.start + blank.end) / 2; if (idSpace > blank.start) { addRange(blank.start, idSpace - 1); } if (idSpace < blank.end) { addRange(idSpace + 1, blank.end); } } hm.put(mId, idSpace); return idSpace; } public int arrive1(int mId) { countEmpty--; // tìm blank dài nhất -> xóa khỏi tsSize và hashMap, ở cách 1 thì là // tsID Range blank = ts.pollFirst(); blankMap.remove(blank.start); blankMap.remove(blank.end); int idSpace = (blank.start + blank.end) / 2; if (blank.start == 1) { idSpace = 1; } else if (blank.end == N) { idSpace = N; } if (idSpace > blank.start) { addRange(blank.start, idSpace - 1); } if (idSpace < blank.end) { addRange(idSpace + 1, blank.end); } hm.put(mId, idSpace); return idSpace; } public int arrive2(int mId) { int idSpace = -1; countEmpty--; Range blank = ts.pollFirst(); blankMap.remove(blank.start); blankMap.remove(blank.end); if (blank.start == 1) { addRange(2, blank.end); idSpace = 1; } else if (blank.end == N) { addRange(blank.start, N - 1); idSpace = N; } else { // idSpace = blank.start + blank.size / 2; // if (blank.size % 2 == 0) { // idSpace--; // } idSpace = (blank.start + blank.end) / 2; addRange(blank.start, idSpace - 1); addRange(idSpace + 1, blank.end); } hm.put(mId, idSpace); return idSpace; } public int leave(int mId) { countEmpty++; // int idSpace = hm.get(mId); // hm.remove(mId); int idSpace = hm.remove(mId); Range front = blankMap.get(idSpace - 1); Range behind = blankMap.get(idSpace + 1); if (front != null && behind != null) { removeRange(front); removeRange(behind); addRange(front.start, behind.end); } else if (behind != null) { removeRange(behind); addRange(idSpace, behind.end); } else if (front != null) { removeRange(front); addRange(front.start, idSpace); } else { addRange(idSpace, idSpace); } return countEmpty; } static class Range { // range of blank spaces int start, end, size; public Range(int mStart, int mEnd) { start = mStart; end = mEnd; this.size = end - start + 1; } } } package MagicString; import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.Set; class UserSolution { // DB quản lý các String prefix -> Node Map<String, Node> map = new HashMap<>(); // dùng để cập nhật thời gian chết cho cụm String - Node Set<Node> set = new HashSet<>(); // quản trị cây Node void init(int N) { map.clear(); set.clear(); } // vấn đề thời gian sống được quyết định bởi endTime của node mới nhất // endTime của String được quyết định theo nhóm mà nó gia nhập // Node cũ gia nhập Node mới // quy tắc kết bạn: kết bạn với cả bạn của bạn int generateString(int mTimestamp, int mLifespan, int mLen, char mStr[]) { Node newNode = new Node(); newNode.cnt[mLen]++; newNode.endTime = mTimestamp + mLifespan; set.add(newNode); // chưa put vào map vội // node cha gồm các chuỗi cũng chứa sub keyword của node con // node cha là node mới hơn được tạo for (int i = 0; i < mLen - 2; i++) { // tại sao cần "" ở đầu ? String sub = "" + mStr[i] + mStr[i + 1] + mStr[i + 2]; Node node = map.get(sub); // node này có thể đã chết nhưng ta không // quan tâm if (node != null) { node = node.getRoot(); node.update(mTimestamp); if (!node.isDeleted) { newNode.merge(node); } } map.put(sub, newNode); } return checkString(mTimestamp, mLen); } int checkString(int mTimestamp, int mLen) { int count = 0; set.forEach(node -> node.update(mTimestamp)); // xác định sống chết set.removeIf(node -> node.isDeleted); // vừa lọc vừa xóa node for (Node node : set) { count += node.cnt[mLen]; } return count; } // tổ chức cây // mỗi Node đại diện cho một nhóm các chuỗi có chung substring class Node { int endTime; boolean isDeleted; Node parent; // ? int[] cnt = new int[11]; // đếm số chuỗi theo độ dài Node getRoot() { return parent == null ? this : parent.getRoot(); } void update(int time) { if (endTime <= time) { isDeleted = true; } } void merge(Node node) { // ? if (node != this) { node.isDeleted = true; node.parent = this; for (int i = 5; i <= 10; i++) { cnt[i] += node.cnt[i]; // ? } } } } } package MagicString; // Soumitra Jain import java.util.ArrayList; import java.util.HashMap; class UserSolution2 { class Word { int deathTime; boolean isDel; int[] dataArr = new int[11]; Word parent; public Word() { this.parent = this; } } private Word findParent(Word word) { if (word.parent == word) { return word; } return findParent(word.parent); } private void union(Word a, Word b) { Word aParent = findParent(a); Word bParent = findParent(b); if (aParent == bParent) { return; } b.parent = a; for (int i = 5; i < 11; i++) { a.dataArr[i] += b.dataArr[i]; } b.isDel = true; } private void update(Word word, int timeStamp) { if (word.deathTime <= timeStamp) { word.isDel = true; } } HashMap<String, Word> hMap = new HashMap<>(); ArrayList<Word> db = new ArrayList<>(); void init(int N) { hMap.clear(); db.clear(); } int generateString(int mTimestamp, int mLifespan, int mLen, char mStr[]) { Word w1 = new Word(); w1.dataArr[mLen]++; w1.deathTime = mTimestamp + mLifespan; db.add(w1); for (int i = 0; i < mLen - 2; i++) { String str = "" + mStr[i] + mStr[i + 1] + mStr[i + 2]; if (hMap.containsKey(str)) { Word temp = hMap.get(str); Word tempParent = findParent(temp); update(tempParent, mTimestamp); if (!tempParent.isDel) { union(w1, tempParent); } } hMap.put(str, w1); } return checkString(mTimestamp, mLen); } int checkString(int mTimestamp, int mLen) { int res = 0; ArrayList<Word> toBeRemoved = new ArrayList<>(); for (Word word : db) { update(word, mTimestamp); if (word.isDel) { toBeRemoved.add(word); } } for (Word word : toBeRemoved) { db.remove(word); } for (Word word : db) { res += word.dataArr[mLen]; } return res; } } package MagicString; // Bùi Văn Long, Bùi Khánh Hiển import java.util.ArrayList; import java.util.List; class UserSolution3 { // HashMap<String, Word> wordDB = new HashMap<>(); // List<Word> wordList = new ArrayList<>(); // Word[][][] wordDB = new Word[26][26][26]; List<Word> wordList = new ArrayList<>(); Word[][][] wordDB = new Word[26][26][26]; void init(int N) { wordList.clear(); for (int i = 0; i < 26; i++) { for (int j = 0; j < 26; j++) { for (int k = 0; k < 26; k++) { wordDB[i][j][k] = null; } } } } int generateString(int mTimestamp, int mLifespan, int mLen, char mStr[]) { Word word = new Word(); word.count[mLen]++; word.deadTime = mTimestamp + mLifespan; wordList.add(word); for (int i = 0; i < mLen - 2; i++) { int a = mStr[i] - 'a'; int b = mStr[i + 1] - 'a'; int c = mStr[i + 2] - 'a'; if (wordDB[a][b][c] != null) { Word tmp = wordDB[a][b][c]; Word tmp_parent = find(tmp); update(tmp_parent, mTimestamp); if (tmp_parent.isAlive) { union(word, tmp_parent); } } wordDB[a][b][c] = word; // String s = ""; // s = "" + mStr[i] + mStr[i + 1] + mStr[i + 2]; // if (wordMap.containsKey(s)) { // Word tmp = wordMap.get(s); // Word tmp_parent = find(tmp); // update(tmp_parent, mTimestamp); // if (tmp_parent.isAlive) { // union(word, tmp_parent); // } // } } return checkString(mTimestamp, mLen); } int checkString(int mTimestamp, int mLen) { int ans = 0; List<Word> deadList = new ArrayList<>(); for (Word word : wordList) { update(word, mTimestamp); if (!word.isAlive) { deadList.add(word); } } for (Word word : deadList) { wordList.remove(word); } for (Word word : wordList) { ans += word.count[mLen]; } return ans; } // Disjoint Set private Word find(Word word) { if (word.parent == word) { return word; } return find(word.parent); } private void union(Word w1, Word w2) { Word w1_parent = find(w1); Word w2_parent = find(w2); if (w1_parent == w2_parent) { return; } w2.parent = w1; for (int i = 5; i < 11; i++) { w1.count[i] += w2.count[i]; } w2.isAlive = false; } private void update(Word w, int Timestamp) { if (w.deadTime <= Timestamp) { w.isAlive = false; } } class Word { int deadTime; boolean isAlive; int[] count = new int[11]; Word parent; public Word() { this.isAlive = true; this.parent = this; } } } package MemorySystem; import java.util.HashMap; import java.util.Map; import java.util.TreeSet; class UserSolution { // map điểm bắt đầu lưu trữ và kích cỡ của đoạn lưu trữ đó Map<Integer, Integer> mapSize; TreeSet<Memory> freeSpace; public void init(int N) { mapSize = new HashMap<>(); // định vị theo thứ tự freeSpace = new TreeSet<>((a, b) -> a.start - b.start); freeSpace.add(new Memory(0, N)); } public int allocate(int mSize) { TreeSet<Memory> sortedFreeSpace = new TreeSet<>((a, b) -> a.size() - b.size()); sortedFreeSpace.addAll(freeSpace); Memory memory = sortedFreeSpace.ceiling(new Memory(0, mSize)); if (memory == null) { return -1; } mapSize.put(memory.start, mSize); freeSpace.remove(memory); if (mSize < memory.size()) { Memory remain = new Memory(memory.start + mSize, memory.end); freeSpace.add(remain); } return memory.start; } public int release(int mAddr) { if (!mapSize.containsKey(mAddr)) { return -1; } // trả về value của key bị remove int size = mapSize.remove(mAddr); Memory memory = new Memory(mAddr, mAddr + size); // gộp freeSpace Memory front = freeSpace.lower(memory); Memory rear = freeSpace.higher(memory); if (front != null && front.end == mAddr) { freeSpace.remove(front); memory.start = front.start; } if (rear != null && rear.start == mAddr + size) { freeSpace.remove(rear); memory.end = rear.end; } freeSpace.add(memory); return size; } class Memory { int start, end; Memory(int mStart, int mEnd) { start = mStart; end = mEnd; } int size() { return end - start; } } } package MemorySystem; import java.util.Comparator; import java.util.HashMap; import java.util.TreeSet; class UserSolution2 { class Memory { int start; int end; int size; boolean blank; public Memory(int mStart, int mEnd, int mSize) { start = mStart; end = mEnd; size = mSize; blank = true; } } HashMap<Integer, Memory> hm = new HashMap<>(); TreeSet<Memory> ts = new TreeSet<>(new CmpSize()); public void init(int N) { hm.clear(); ts.clear(); Memory memory = new Memory(0, N - 1, N); ts.add(memory); hm.put(memory.start, memory); hm.put(memory.end, memory); } public int allocate(int mSize) { Memory temp = new Memory(-1, 0, mSize); Memory empty = ts.ceiling(temp); RemoveMemory(empty); int result = -1; if (empty != null) { temp.start = empty.start; temp.end = temp.start + mSize - 1; temp.size = mSize; temp.blank = false; hm.put(temp.start, temp); hm.put(temp.end, temp); result = temp.start; if (empty.size > temp.size) { Memory newMemory = new Memory(empty.start + mSize, empty.end, empty.size - mSize); hm.put(newMemory.start, newMemory); hm.put(newMemory.end, newMemory); ts.add(newMemory); } } return result; } public void RemoveMemory(Memory Memory) { if (Memory != null) { ts.remove(Memory); hm.remove(Memory.start); hm.remove(Memory.end); } } public int release(int mAddr) { Memory temp = hm.get(mAddr); int result = -1; if (temp != null && !temp.blank && temp.start == mAddr) { temp.blank = true; result = temp.size; Memory before = hm.get(temp.start - 1); if (before != null && before.blank) { temp.start = before.start; temp.size += before.size; ts.remove(before); } Memory after = hm.get(temp.end + 1); if (after != null && after.blank) { temp.end = after.end; temp.size += after.size; ts.remove(after); } hm.put(temp.start, temp); hm.put(temp.end, temp); ts.add(temp); } return result; } class CmpSize implements Comparator<Memory> { public int compare(Memory n1, Memory n2) { if (n1.size == n2.size) return n1.start - n2.start; return n1.size - n2.size; } } } package NewsFeed; import java.util.TreeSet; class UserSolution { News news[]; TreeSet<News> sections[] = new TreeSet[10]; int[] interested; void init() { news = new News[50001]; for (int i = 0; i < 10; i++) { sections[i] = new TreeSet<>((a, b) -> a.read == b.read ? b.id - a.id : b.read - a.read); } // sắp xếp giảm dần theo lượt đọc interested = new int[100001]; for (int i = 0; i < 100001; i++) { interested[i] = -1; } } void addNews(int mSection, int mNewsId) { news[mNewsId] = new News(mNewsId, mSection); sections[mSection].add(news[mNewsId]); } void eraseNews(int mNewsId) { sections[news[mNewsId].section].remove(news[mNewsId]); } void readNews(int mUserId, int mNewsId) { News n = news[mNewsId]; interested[mUserId] = n.section; sections[n.section].remove(n); n.read++; sections[n.section].add(n); } void changeSection(int mNewsId, int mSection) { sections[news[mNewsId].section].remove(news[mNewsId]); sections[mSection].add(news[mNewsId]); news[mNewsId].section = mSection; } int getList(int mUserId, int mList[]) { int count = 0; while (!isEmpty()) { int maxScore = 0; int maxId = 0; for (int i = 0; i < 10; i++) { if (!sections[i].isEmpty()) { News topNews = sections[i].first(); int score = interested[mUserId] == i ? topNews.read + 10 : topNews.read; if (score > maxScore || (score == maxScore && topNews.id > maxId)) { maxScore = score; maxId = topNews.id; } } } sections[news[maxId].section].remove(news[maxId]); mList[count++] = maxId; if (count == 10) { break; } } for (int i = 0; i < count; i++) { sections[news[mList[i]].section].add(news[mList[i]]); } return count; } boolean isEmpty() { for (int i = 0; i < 10; i++) { if (!sections[i].isEmpty()) { return false; } } return true; } class News { int id, section, read; public News(int mId, int mSection) { id = mId; section = mSection; } } } package NewsNotification; // Doãn Thanh Tùng import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.PriorityQueue; import java.util.Queue; import java.util.Set; import java.util.TreeSet; class UserSolution { Map<Integer, Channel> channels = new HashMap<>(); Map<Integer, User> users = new HashMap<>(); Map<Integer, News> news = new HashMap<>(); Queue<News> heap = new PriorityQueue<>((a, b) -> a.time - b.time); void init(int N, int K) { channels.clear(); users.clear(); news.clear(); heap.clear(); } void registerUser(int mTime, int mUID, int mNum, int mChannelIDs[]) { User user = users.computeIfAbsent(mUID, k -> new User()); for (int i = 0; i < mNum; i++) { Channel channel = channels.computeIfAbsent(mChannelIDs[i], k -> new Channel()); channel.users.put(mUID, mTime); user.channels.add(channel); } } int offerNews(int mTime, int mNewsID, int mDelay, int mChannelID) { News n = new News(mTime + mDelay, mNewsID, mChannelID); news.put(mNewsID, n); heap.add(n); return channels.get(mChannelID).users.size(); } void cancelNews(int mTime, int mNewsID) { News n = news.get(mNewsID); Channel channel = channels.get(n.channelID); channel.news.remove(n); heap.remove(n); } int checkUser(int mTime, int mUID, int mRetIDs[]) { while (!heap.isEmpty() && heap.peek().time <= mTime) { News news = heap.poll(); Channel channel = channels.get(news.channelID); channel.news.add(news); } int size = 0; TreeSet<News> top3 = new TreeSet<>((a, b) -> a.time == b.time ? b.id - a.id : b.time - a.time); for (Channel channel : users.get(mUID).channels) { int registerTime = channel.users.get(mUID); Set<News> noticed = channel.news.headSet(new News(registerTime + 1, 0, 0)); size += noticed.size(); int cnt = 0; for (News news : noticed) { if (cnt++ == 3) break; if (top3.add(news) && top3.size() > 3) top3.pollLast(); } channel.users.put(mUID, mTime); } int i = 0; for (News news : top3) mRetIDs[i++] = news.id; return size; } } class Channel { Map<Integer, Integer> users = new HashMap<>(); TreeSet<News> news = new TreeSet<>((a, b) -> a.time == b.time ? b.id - a.id : b.time - a.time); } class User { List<Channel> channels = new ArrayList<>(); } class News { int time, id, channelID; News(int mTime, int mID, int mChannelID) { time = mTime; id = mID; channelID = mChannelID; } } package NotepadProgram; import java.util.LinkedList; class UserSolution { int H, W, cursor, size; LinkedList<Character> notepad[]; int count[][]; void init(int H, int W, char mStr[]) { this.H = H; this.W = W; notepad = new LinkedList[H]; // mỗi hàng là một LinkedList for (int i = 0; i < H; i++) notepad[i] = new LinkedList<Character>(); count = new int[H][26]; cursor = 0; size = 0; int i = 0; // index của xâu cần nhập - dùng để nhập int row = 0; while (mStr[i] != '\0') { if (i == (row + 1) * W) row++; notepad[row].add(mStr[i]); // nhập ký tự mStr[i] // đếm số lần xuất hiện trong hàng của ký tự count[row][mStr[i] - 'a']++; size++; i++; } } void insert(char mChar) { int row = cursor / W; int col = cursor % W; // thêm ký tự vào vị trí col của linkedlist row notepad[row].add(col, mChar); count[row][mChar - 'a']++; cursor++; size++; // dịch phần tử tràn xuống hàng dưới for (int i = row; i < H; i++) { if (notepad[i].size() > W) { char temp = notepad[i].removeLast(); count[i][temp - 'a']--; notepad[i + 1].addFirst(temp); count[i + 1][temp - 'a']++; } } } char moveCursor(int mRow, int mCol) { // -1 để đưa về index 0 cursor = (mRow - 1) * W + mCol - 1; if (cursor >= size) { cursor = size; return '$'; } return notepad[mRow - 1].get(mCol - 1); } int countCharacter(char mChar) { int row = cursor / W; int col = cursor % W; int cnt = 0; int i = 0; for (char c : notepad[row]) { if (i >= col && mChar == c) cnt++; i++; } for (int j = row + 1; j < H; j++) cnt += count[j][mChar - 'a']; return cnt; } } package NotepadProgram; import java.util.ArrayList; import java.util.Collections; class UserSolution2 { int H, W, cursor, size; ArrayList<Character> notepad[]; int count[][]; void init(int H, int W, char mStr[]) { this.H = H; this.W = W; notepad = new ArrayList[H]; // mỗi hàng là một ArrayList for (int i = 0; i < H; i++) notepad[i] = new ArrayList<Character>(); count = new int[H][26]; cursor = 0; size = 0; int i = 0; // index của xâu cần nhập - dùng để nhập int row = 0; while (mStr[i] != '\0') { if (i == (row + 1) * W) row++; notepad[row].add(mStr[i]); // nhập ký tự mStr[i] count[row][mStr[i] - 'a']++; // đếm số lần xuất hiện trong hàng của ký tự size++; i++; } } void insert(char mChar) { int row = cursor / W; int col = cursor % W; // thêm ký tự vào vị trí col của ArrayList row notepad[row].add(col, mChar); count[row][mChar - 'a']++; cursor++; size++; // dịch phần tử tràn xuống hàng dưới for (int i = row; i < H; i++) { if (notepad[i].size() > W) { char temp = notepad[i].remove(notepad[i].size() - 1); count[i][temp - 'a']--; notepad[i + 1].add(0, temp); count[i + 1][temp - 'a']++; } } } char moveCursor(int mRow, int mCol) { // -1 để đưa về index 0 cursor = (mRow - 1) * W + mCol - 1; if (cursor >= size) { cursor = size; return '$'; } return notepad[mRow - 1].get(mCol - 1); } int countCharacter(char mChar) { int row = cursor / W; int col = cursor % W; // int cnt = 0; // int i = col; // for (char c : notepad[row]) { // if (i >= col && mChar == c) // cnt++; // i++; // tăng index cho tới khi bằng với vị trí cursor // } int cnt = Collections.frequency( notepad[row].subList(col, notepad[row].size()), mChar); // kể từ các row lớn hơn, cộng thẳng tần số xuất hiện for (int j = row + 1; j < H; j++) cnt += count[j][mChar - 'a']; return cnt; } } package PhylogeneticTree; import java.util.ArrayList; import java.util.HashMap; import java.util.HashSet; import java.util.List; import java.util.Map; import java.util.Set; class UserSolution { Map<String, Node> map = new HashMap<>(); static int countNode; public void init(char[] mRootSpecies) { map.clear(); map.put(new String(mRootSpecies), new Node()); } public void add(char[] mSpecies, char[] mParentSpecies) { Node a = map.get(new String(mParentSpecies)); Node b = new Node(); b.parent = a; b.depth = a.depth + 1; a.link.add(b); b.link.add(a); map.put(new String(mSpecies), b); } public int getDistance(char[] mSpecies1, char[] mSpecies2) { Node a = map.get(new String(mSpecies1)); Node b = map.get(new String(mSpecies2)); int count = 0; // dịch node cho đến khi trùng nhau // chiến thuật là cho 2 node dịch dần lên node cha, mỗi lần count++ // cả 2 đều có chung node cha, vấn đề cần dịch sao cho gặp nhau ở node // cha gần nhất while (a != b) { if (a.depth > b.depth) { a = a.parent; } else { b = b.parent; } count++; } return count; } int getCount(char[] mSpecies, int mDistance) { countNode = 0; // nếu đặt global countNode = 0 và bên trong hàm getCount // thiếu đoạn này thì sẽ sai --> do countNode cần phải // reset mỗi khi hàm này được gọi Node start = map.get(new String(mSpecies)); deQuy(start, null, mDistance); return countNode; } // đệ quy // không có chu trình nên không cần mảng đánh dấu các đỉnh đã được duyệt void deQuy(Node cur, Node pre, int dis) { if (dis == 0) { countNode++; return; } for (Node next : cur.link) { if (next != pre) { deQuy(next, cur, dis - 1); } } } public int getCount1(char[] mSpecies, int mDistance) { Node start = map.get(new String(mSpecies)); return deQuy1(start, null, mDistance); } // đệ quy // không có chu trình nên không cần mảng đánh dấu các đỉnh đã được duyệt public int deQuy1(Node cur, Node pre, int dis) { int count = 0; if (dis == 0) { return 1; } for (Node next : cur.link) { if (next != pre) { count += deQuy1(next, cur, dis - 1); } } return count; } String string(char[] s) { return new String(s).trim(); } class Node { Node parent; int depth; // ? List<Node> link = new ArrayList<>(); Set<Node> link2 = new HashSet<>(); } } package Reorganization; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; class UserSolution { Map<Integer, Node> map = new HashMap<>(); Node root; int curGroup; public void init(int mId, int mNum) { root = new Node(mId, mNum); map.put(mId, root); } public int add(int mId, int mNum, int mParent) { Node parent = map.get(mParent); if (parent.child.size() == 2) { return -1; } Node node = new Node(mId, mNum); map.put(mId, node); // connect node to its parent node.parent = parent; parent.child.add(node); // trả về tổng số người - root là parent Node cur = parent; // thêm mNum vào mọi node phía trên nó while (cur != null) { cur.total += mNum; cur = cur.parent; } return parent.total; } public int remove(int mId) { Node node = map.remove(mId); if (node == null) { return -1; } // cập nhật trạng thái node.isRemoved = true; // xóa khỏi danh sách node con của node cha Node parent = node.parent; parent.child.remove(node); // cập nhật total của các node bên trên node bị xóa Node cur = parent; while (cur != null) { if (cur.isRemoved) { // quan trọng return -1; } cur.total -= node.total; cur = cur.parent; } return node.total; } int tryCut(Node node, int M, int K) { // nếu có tòa nhà mà số lượng người lớn hơn K thì auto dừng if (curGroup > M || node.num > K) { curGroup = M + 1; return 0; } // từ Node gốc, xác định số người ở hai nhánh trái - phải // số lượng người ở nhánh trái numL là hàm đệ quy của node con thứ 1 // số lượng người ở nhánh phải numR là hàm đệ quy của node con thứ 2 // return của hàm tryCut phải là tổng số người của subTree tại node là // tham số truyền vào // return node.num + numL (của node đó) + numR (của node đó) int numL, numR; numL = numR = 0; int size = node.child.size(); if (size >= 1) { numL = tryCut(node.child.get(0), M, K); } if (size == 2) { numR = tryCut(node.child.get(1), M, K); } // có thể chia nhánh trái của node (tức là tạo group từ node và nhánh // trái của nó) // numL là số người còn lại trong nhóm con trái chứ không phải số người // trong nhóm con trái // mục đích gán lại bằng 0 là để loại bỏ số lượng người còn lại ở nhóm // con trái // khỏi số lượng người ở nhóm hiện tại khi return ở cuối // khi numL hoặc numR được gán = 0, tức là số đó được gom thành 1 group if (node.num + numL > K) { numL = 0; curGroup++; } if (node.num + numR > K) { numR = 0; curGroup++; } // nếu chỉ dính 1 trong 2 if bên trên thì if thứ 3 này sẽ không dính // nếu cả 2 if bên trên đều không dính thì kiểm tra if thứ 3 này // quy tắc đệ quy là ép xuống phía dưới các đoạn nhỏ nhất có thể mà <= K // nên lựa chọn chia cắt nhóm con lớn hơn // vì kết quả của nhóm hiện tại chính lại được dùng để gán vào numL hoặc // numR của node bên trên // nên cần đảm bảo việc gom nhóm nhỏ nhất if (node.num + numL + numR > K) { if (numL >= numR) { numL = 0; } else { numR = 0; } curGroup++; } // trả về số lượng người của subTree hiện tại từ node tham số return node.num + numL + numR; } public int reorganize(int M, int K) { curGroup = 1; tryCut(root, M, K); return curGroup <= M ? 1 : 0; } } class Node { // represent a department int id; int num; // people in current department int total; // people in total subtree boolean isRemoved; Node parent; List<Node> child = new ArrayList<>(); public Node(int mId, int mNum) { id = mId; num = total = mNum; } } package Reorganization; import java.util.HashMap; class UserSolution3 { public class department { int ID; int members; int sum_members; department parent; department[] subsivisions = new department[2]; boolean isremove; public department(int id, int num, department par) { this.ID = id; this.members = num; this.parent = par; this.sum_members = num; } } HashMap<Integer, department> hashIDdeparment = new HashMap<>(); int cnt = 0; department Root; public void init(int mId, int mNum) { hashIDdeparment.clear(); Root = new department(mId, mNum, null); hashIDdeparment.put(mId, Root); return; } public int add(int mId, int mNum, int mParent) { department parent = hashIDdeparment.get(mParent); if (parent.subsivisions[1] != null && parent.subsivisions[0] != null) { // parent // co // 2 // subsivision // roi return -1; } department ndepartment = new department(mId, mNum, parent); hashIDdeparment.put(mId, ndepartment); if (parent.subsivisions[0] == null) { // add subsivisions cho parent parent.subsivisions[0] = ndepartment; ; } else { parent.subsivisions[1] = ndepartment; } department temp = parent; while (temp != null) { temp.sum_members += mNum; temp = temp.parent; } return parent.sum_members; } public int remove(int mId) { department rmdepartment = hashIDdeparment.remove(mId); // neu ko ton tai // key mId => // rmdepartment // = null if (rmdepartment == null) { return -1; } department parent = rmdepartment.parent; rmdepartment.isremove = true; if (parent.subsivisions[0] == rmdepartment) { // xoa subsivisions cua // parent parent.subsivisions[0] = null; } else { parent.subsivisions[1] = null; } department temp = rmdepartment.parent; int x = rmdepartment.sum_members; while (temp != null) { if (temp.isremove) { return -1; } temp.sum_members -= x; ; temp = temp.parent; } return x; } public int reorganize(int M, int K) { cnt = 0; make(M, K, Root); if (cnt < M) { return 1; } return 0; } int make(int M, int K, department dp) { if (dp == null) { return 0; } if (dp.members > K) { // ton tai department co employees lon hon K => // fail cnt = M; return 0; } if (cnt >= M) { return 0; } int left = make(M, K, dp.subsivisions[0]); int right = make(M, K, dp.subsivisions[1]); int rsWleft = dp.members + left; int rsWright = dp.members + right; int rsWleft_right = dp.members + left + right; if (rsWleft_right <= K) { // ko chia return rsWleft_right; } if (rsWleft <= K && rsWright <= K) { cnt++; if (rsWleft <= rsWright) { return rsWleft; } else { return rsWright; } } if (rsWleft <= K) { cnt++; return rsWleft; } if (rsWright <= K) { cnt++; return rsWright; } cnt += 2; return dp.members; } } package SchoolRecordInquiry; import java.util.Comparator; import java.util.HashMap; import java.util.Map; import java.util.PriorityQueue; import java.util.TreeSet; class UserSolution { // chọn cấu trúc dữ liệu phù hợp // map id --> đối tượng Map<Integer, Student> map = new HashMap<>(); // danh sách quản lý học sinh theo khối và giới tính // vì đây là hai thuộc tính tham số khi query TreeSet<Student> students[][] = new TreeSet[4][2]; public void init() { map.clear(); for (int i = 1; i <= 3; i++) { for (int j = 0; j < 2; j++) { // sắp xếp tăng dần theo điểm số và id (nếu điểm số bằng nhau // thì trả về id nhỏ hơn) // students[i][j] = new TreeSet<>( // (a, b) -> a.score == b.score ? a.id - b.id : a.score // - b.score); // students[i][j] = new TreeSet<>(new sort()); students[i][j] = new TreeSet<>(sort); } } } public int add(int mId, int mGrade, char mGender[], int mScore) { // khởi tạo đối tượng từ tham số truyền vào Student newStudent = new Student(mId, mGrade, mGender, mScore); map.put(mId, newStudent); students[mGrade][newStudent.gender].add(newStudent); // trả về id student có điểm cao nhất return students[mGrade][newStudent.gender].last().id; } public int remove2(int mId) { Student student = map.get(mId); // map.remove(mId); không cần vì khi put đã được update lại if (student != null) { students[student.grade][student.gender].remove(student); if (!students[student.grade][student.gender].isEmpty()) { return students[student.grade][student.gender].first().id; } } return 0; } public int remove(int mId) { Student student = map.remove(mId); // return null nếu key không tồn tại // Student student = map.get(mId); // map.remove(mId); không cần vì khi put đã được update lại if (student == null) { return 0; } students[student.grade][student.gender].remove(student); if (students[student.grade][student.gender].isEmpty()) { return 0; } return students[student.grade][student.gender].first().id; } public int query(int mGradeCnt, int mGrade[], int mGenderCnt, char mGender[][], int mScore) { TreeSet<Student> querySet = new TreeSet<>( (a, b) -> a.score == b.score ? a.id - b.id : a.score - b.score); for (int i = 0; i < mGradeCnt; i++) { for (int j = 0; j < mGenderCnt; j++) { Student student = new Student(198, mGrade[i], mGender[j], mScore); // ? Student lowest = students[student.grade][student.gender] .ceiling(student); if (lowest != null) { querySet.add(lowest); } } } return querySet.isEmpty() ? 0 : querySet.first().id; } public int query2(int mGradeCnt, int mGrade[], int mGenderCnt, char mGender[][], int mScore) { PriorityQueue<Student> heap = new PriorityQueue<>(sort); for (int i = 0; i < mGradeCnt; i++) { for (int j = 0; j < mGenderCnt; j++) { // Student student = new Student(198, mGrade[i], mGender[j], // mScore); // ? int gender = mGender[j][0] == 'm' ? 1 : 0; Student lowest = students[mGrade[i]][gender] .ceiling(new Student(-1, -1, mGender[j], mScore)); if (lowest != null) { heap.add(lowest); } } } return heap.isEmpty() ? 0 : heap.poll().id; } class sort implements Comparator<Student> { public int compare(Student o1, Student o2) { if (o1.score == o2.score) { return o1.id - o2.id; } return o1.score - o2.score; } } Comparator<Student> sort = new Comparator<Student>() { public int compare(Student o1, Student o2) { if (o1.score == o2.score) { return o1.id - o2.id; } return o1.score - o2.score; } }; class Student { int id, grade, gender, score; Student(int mId, int mGrade, char[] mGender, int mScore) { id = mId; grade = mGrade; gender = mGender[0] == 'm' ? 1 : 0; score = mScore; } } } package SchoolRecordInquiry; import java.util.HashMap; import java.util.PriorityQueue; import java.util.TreeSet; class UserSolution2 { TreeSet<Student>[][] students; HashMap<Integer, Student> map; public void init() { map = new HashMap<>(); students = new TreeSet[4][2]; for (int i = 0; i < 4; i++) { for (int j = 0; j < 2; j++) { students[i][j] = new TreeSet<>( (a, b) -> a.score == b.score ? a.id - b.id : a.score - b.score); } } } public int add(int mId, int mGrade, char mGender[], int mScore) { int gender = 1; // if (mGender[0] - 'a' == 5) // gender = 0; if (mGender[0] == 'f') { gender = 0; } Student newStudent = new Student(mId, mGrade, gender, mScore); map.put(mId, newStudent); students[mGrade][gender].add(newStudent); return students[mGrade][gender].last().id; } public int remove(int mId) { Student student = map.get(mId); if (student == null) return 0; map.remove(student.id); students[student.grade][student.gender].remove(student); if (students[student.grade][student.gender].isEmpty()) return 0; return students[student.grade][student.gender].first().id; } public int query(int mGradeCnt, int mGrade[], int mGenderCnt, char mGender[][], int mScore) { // chuyển mảng mGender -> gender int[] gender = { 0, 1 }; if (mGenderCnt == 1) { int G = 1; // if (mGender[0][0] - 'a' == 5) // G = 0; if (mGender[0][0] == 'f') G = 0; gender = new int[] { G }; } PriorityQueue<Student> heap = new PriorityQueue<>( (a, b) -> a.score == b.score ? a.id - b.id : a.score - b.score); for (int k = 0; k < mGradeCnt; k++) { for (int l = 0; l < mGenderCnt; l++) { int i = mGrade[k]; int j = gender[l]; // if (!students[i][j].isEmpty()) { // Student tailStudent = students[i][j].ceiling(new Student( // -1, -1, -1, mScore)); // if (tailStudent != null) { // heap.add(tailStudent); // } // } Student lowest = students[i][j].ceiling(new Student(-1, -1, -1, mScore)); if (lowest != null) { heap.add(lowest); } } } if (heap.isEmpty()) return 0; return heap.poll().id; } class Student { int id; int score; int gender; int grade; public Student(int mId, int mGrade, int mGender, int mScore) { id = mId; grade = mGrade; gender = mGender; score = mScore; } } } package SecondHandMarketApp; // tham khảo lời giải của Vũ Chí Bảo, XZ // tham khảo UserSolution4 với phương thức filter import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.HashMap; import java.util.List; import java.util.Map; class UserSolution { // map string tag với danh sách sản phẩm Map<String, List<Product>> products; void init(int N) { products = new HashMap<String, List<Product>>(); } void addProduct(int mPrice, int tagNum, char tagName[][]) { // khởi tạo // thêm sản phẩm vào từng tag riêng Product product = new Product(mPrice); String[] tags = new String[tagNum]; for (int i = 0; i < tagNum; i++) { tags[i] = string(tagName[i]); products.computeIfAbsent(tags[i], k -> new ArrayList<>()).add( product); } // sort tags để khi ghép tag được chuỗi duy nhất // thêm sản phầm vào cả 3 tags Arrays.sort(tags); for (int i = 0; i < tagNum; i++) { for (int j = i + 1; j < tagNum; j++) { for (int j2 = j + 1; j2 < tagNum; j2++) { products.computeIfAbsent(tags[i] + tags[j] + tags[j2], k -> new ArrayList<>()).add(product); } } } } int buyProduct(char tag1[], char tag2[], char tag3[]) { String[] tags = { string(tag1), string(tag2), string(tag3) }; Arrays.sort(tags); String tag = tags[0] + tags[1] + tags[2]; // xóa tất cả sản phẩm có isRemoved = true được gắn với tag products.computeIfAbsent(tag, k -> new ArrayList<>()).removeIf( x -> x.isRemoved); if (products.get(tag).isEmpty()) { return -1; } Product res = Collections.min(products.get(tag), (a, b) -> a.price - b.price); // tốt hơn là remove luôn khỏi danh sách của các tag1, tag2, tag3 // Product res = Collections.max(products.get(tag), (a, b) -> b.price // - a.price); res.isRemoved = true; return res.price; } void adjustPrice(char tag1[], int changePrice) { for (Product product : products.get(string(tag1))) { product.price += changePrice; } // version đủ hơn // String key = string(tag1); // if (!products.containsKey(key)) { // return; // } // List<Product> proList = products.get(key); // for (Product product : proList) { // if (!product.isRemoved) { // product.price += changePrice; // } // } } String string(char s[]) { int n = -1; while (s[++n] != 0) ; // tăng n = độ dài mảng ký tự // String temp = new String(s); // int n = temp.indexOf('\0'); return new String(s, 0, n); // return String.valueOf(str, 0, c); } // String charToString(char tagName[]) { // StringBuilder res = new StringBuilder(); // for (int i = 0; tagName[i] != '\0'; i++) { // res.append(tagName[i]); // } // return res.toString(); // } } class Product { int price; boolean isRemoved; public Product(int mPrice) { price = mPrice; isRemoved = false; } } package SurvivalTrain; // Doãn Thanh Tùng import java.util.ArrayList; import java.util.List; import java.util.TreeSet; class UserSolution3 { TreeSet<Passenger> sections[]; Passenger passengers[]; List<Integer> jobs[]; void init(int N, int M, int J, int mPoint[], int mJobID[]) { sections = new TreeSet[N / M]; jobs = new ArrayList[J]; // lưu id của các hành khách cùng job for (int i = 0; i < J; i++) jobs[i] = new ArrayList<>(); passengers = new Passenger[N]; for (int i = 0; i < N; i++) { if (sections[i / M] == null) sections[i / M] = new TreeSet<>( (a, b) -> a.point == b.point ? a.id - b.id : b.point - a.point); // sắp xếp giảm dần theo điểm và // tăng dần theo id passengers[i] = new Passenger(i, mPoint[i], mJobID[i]); sections[i / M].add(passengers[i]); jobs[mJobID[i]].add(i); } } void destroy() { } int update(int mID, int mPoint) { Passenger p = passengers[mID]; for (int i = 0; i < sections.length; i++) { if (sections[i].remove(p)) { p.point += mPoint; sections[i].add(p); break; } } return p.point; } int updateByJob(int mJobID, int mPoint) { int sum = 0; for (int i = 0; i < sections.length; i++) { for (int pID : jobs[mJobID]) { if (sections[i].remove(passengers[pID])) { passengers[pID].point += mPoint; sum += passengers[pID].point; sections[i].add(passengers[pID]); } } } return sum; } // section có kiểu dữ liệu treeSet đã đã được định nghĩa với comparator sắp // xếp // nên khi add dữ liệu sẽ tự động sắp xếp int move(int mNum) { int sum = 0; // lưu danh sách hành khách List<Passenger> temp[] = new ArrayList[sections.length - 1]; for (int i = 0; i <= sections.length - 2; i++) { temp[i] = new ArrayList<>(); // find and remove min from section 0 to length-2 // store in temp[] for (int j = 0; j < mNum; j++) { Passenger smallest = sections[i].pollLast(); // do sắp xếp giảm // dần temp[i].add(smallest); sum += smallest.point; } // find and remove max from section 1 to length-1 // readd max to sections before for (int j = 0; j < mNum; j++) { Passenger largest = sections[i + 1].pollFirst(); sections[i].add(largest); sum += largest.point; } } // readd min to sections after for (int i = 0; i < temp.length; i++) sections[i + 1].addAll(temp[i]); return sum; } class Passenger { int id, point, jobID; Passenger(int mID, int mPoint, int mJobID) { id = mID; point = mPoint; jobID = mJobID; } } } package SurvivalTrain; import java.util.ArrayList; import java.util.List; import java.util.TreeSet; class UserSolution4 { TreeSet<Passenger> sections[]; Passenger passengers[]; List<Integer> jobs[]; int sectionSize; void init(int N, int M, int J, int mPoint[], int mJobID[]) { sectionSize = M; sections = new TreeSet[N / M]; jobs = new ArrayList[J]; // lưu id của các hành khách cùng job for (int i = 0; i < J; i++) jobs[i] = new ArrayList<>(); passengers = new Passenger[N]; for (int i = 0; i < N; i++) { if (sections[i / M] == null) sections[i / M] = new TreeSet<>( (a, b) -> a.point == b.point ? a.id - b.id : b.point - a.point); // sắp xếp giảm dần theo điểm và // tăng dần theo id passengers[i] = new Passenger(i, mPoint[i], mJobID[i]); sections[i / M].add(passengers[i]); jobs[mJobID[i]].add(i); } } void destroy() { } // sai vì cách truy xuất dữ liệu section tương ứng passenger chỉ đúng khi sự // dịch chuyển chưa xảy ra sau init // int update(int mID, int mPoint) { // Passenger p = passengers[mID]; // int sectionIndex = p.id / sectionSize; // if (sections[sectionIndex].remove(p)) { // p.point += mPoint; // sections[sectionIndex].add(p); // } // return p.point; // } // // int updateByJob(int mJobID, int mPoint) { // int sum = 0; // for (int pID : jobs[mJobID]) { // Passenger p = passengers[pID]; // int sectionIndex = p.id / sectionSize; // if (sections[sectionIndex].remove(p)) { // p.point += mPoint; // sum += p.point; // sections[sectionIndex].add(p); // } // } // return sum; // } int update(int mID, int mPoint) { Passenger p = passengers[mID]; for (int i = 0; i < sections.length; i++) { if (sections[i].remove(p)) { p.point += mPoint; sections[i].add(p); break; } } return p.point; } int updateByJob(int mJobID, int mPoint) { int sum = 0; for (int i = 0; i < sections.length; i++) { for (int pID : jobs[mJobID]) { if (sections[i].remove(passengers[pID])) { passengers[pID].point += mPoint; sum += passengers[pID].point; sections[i].add(passengers[pID]); } } } return sum; } // section có kiểu dữ liệu treeSet đã đã được định nghĩa với comparator sắp // xếp // nên khi add dữ liệu sẽ tự động sắp xếp int move(int mNum) { int sum = 0; // sum là tổng điểm các hành khách được di chuyển, nói cách khác là các // điểm min max // lưu danh sách hành khách List<Passenger> temp[] = new ArrayList[sections.length - 1]; for (int i = 0; i <= sections.length - 2; i++) { temp[i] = new ArrayList<>(); // find and remove min from section 0 to length-2 // store in temp[] for (int j = 0; j < mNum; j++) { Passenger smallest = sections[i].pollLast(); // do sắp xếp giảm // dần temp[i].add(smallest); sum += smallest.point; } // find and remove max from section 1 to length-1 // readd max to sections before for (int j = 0; j < mNum; j++) { Passenger largest = sections[i + 1].pollFirst(); sections[i].add(largest); sum += largest.point; } } // readd min to sections after for (int i = 0; i < temp.length; i++) sections[i + 1].addAll(temp[i]); return sum; } class Passenger { int id, point, jobID; Passenger(int mID, int mPoint, int mJobID) { id = mID; point = mPoint; jobID = mJobID; } } } package SurvivalTrain; import java.util.ArrayList; import java.util.Comparator; import java.util.List; import java.util.TreeSet; class UserSolution5 { TreeSet<Passenger> sections[]; Passenger passengers[]; List<Integer> jobs[]; int numS; void init(int N, int M, int J, int mPoint[], int mJobID[]) { numS = N / M; sections = new TreeSet[numS]; passengers = new Passenger[N]; jobs = new ArrayList[J]; for (int i = 0; i < J; i++) jobs[i] = new ArrayList<>(); for (int i = 0; i < N; i++) { if (sections[i / M] == null) sections[i / M] = new TreeSet<>(new maxFirst()); // sections[i / M] = new TreeSet<>( // (a, b) -> a.point == b.point ? a.id - b.id : b.point // - a.point); passengers[i] = new Passenger(i, mPoint[i], mJobID[i], i / M); sections[i / M].add(passengers[i]); jobs[mJobID[i]].add(i); } } int update(int mID, int mPoint) { Passenger p = passengers[mID]; sections[p.sectionIndex].remove(p); p.point += mPoint; sections[p.sectionIndex].add(p); return p.point; } int updateByJob(int mJobID, int mPoint) { int sum = 0; for (int pID : jobs[mJobID]) { Passenger p = passengers[pID]; sections[p.sectionIndex].remove(p); p.point += mPoint; sum += p.point; sections[p.sectionIndex].add(p); } return sum; } int move(int mNum) { int sum = 0; List<Passenger> temp[] = new ArrayList[numS - 1]; for (int i = 0; i <= numS - 2; i++) { temp[i] = new ArrayList<>(); for (int j = 0; j < mNum; j++) { Passenger min = sections[i].pollLast(); min.sectionIndex++; temp[i].add(min); sum += min.point; } for (int j = 0; j < mNum; j++) { Passenger max = sections[i + 1].pollFirst(); max.sectionIndex--; sections[i].add(max); sum += max.point; } } for (int i = 0; i < temp.length; i++) sections[i + 1].addAll(temp[i]); return sum; } class maxFirst implements Comparator<Passenger> { public int compare(Passenger a, Passenger b) { if (a.point == b.point) return a.id - b.id; else return b.point - a.point; } } class Passenger { int id, point, jobID, sectionIndex; Passenger(int mID, int mPoint, int mJobID, int mSectionIndex) { id = mID; point = mPoint; jobID = mJobID; sectionIndex = mSectionIndex; } } void destroy() { } } package SurvivalTrain; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.TreeSet; class UserSolution6 { TreeSet<Passenger> sections[]; Passenger passengers[]; List<Integer> jobs[]; HashMap<Integer, Integer> passengerSectionMap; void init(int N, int M, int J, int mPoint[], int mJobID[]) { sections = new TreeSet[N / M]; jobs = new ArrayList[J]; // lưu id của các hành khách cùng job for (int i = 0; i < J; i++) jobs[i] = new ArrayList<>(); passengers = new Passenger[N]; passengerSectionMap = new HashMap<>(); for (int i = 0; i < N; i++) { if (sections[i / M] == null) sections[i / M] = new TreeSet<>( (a, b) -> a.point == b.point ? a.id - b.id : b.point - a.point); // sắp xếp giảm dần theo điểm và // tăng dần theo id passengers[i] = new Passenger(i, mPoint[i], mJobID[i]); sections[i / M].add(passengers[i]); passengerSectionMap.put(i, i / M); jobs[mJobID[i]].add(i); } } void destroy() { } int update(int mID, int mPoint) { Passenger p = passengers[mID]; int sectionIndex = passengerSectionMap.get(mID); sections[sectionIndex].remove(p); p.point += mPoint; sections[sectionIndex].add(p); return p.point; } int updateByJob(int mJobID, int mPoint) { int sum = 0; for (int pID : jobs[mJobID]) { Passenger p = passengers[pID]; int sectionIndex = passengerSectionMap.get(pID); sections[sectionIndex].remove(p); p.point += mPoint; sum += p.point; sections[sectionIndex].add(p); } return sum; } // section có kiểu dữ liệu treeSey đã đã được định nghĩa với comparator sắp // xếp // nên khi add dữ liệu sẽ tự động sắp xếp int move(int mNum) { int sum = 0; // lưu danh sách hành khách List<Passenger> temp[] = new ArrayList[sections.length - 1]; for (int i = 0; i <= sections.length - 2; i++) { temp[i] = new ArrayList<>(); // find and remove min from section 0 to length-2 // store in temp[] for (int j = 0; j < mNum; j++) { Passenger smallest = sections[i].pollLast(); // do sắp xếp giảm // dần passengerSectionMap.put(smallest.id, i + 1); temp[i].add(smallest); sum += smallest.point; } // find and remove max from section 1 to length-1 // readd max to sections before for (int j = 0; j < mNum; j++) { Passenger largest = sections[i + 1].pollFirst(); passengerSectionMap.put(largest.id, i); sections[i].add(largest); sum += largest.point; } } // readd min to sections after for (int i = 0; i < temp.length; i++) sections[i + 1].addAll(temp[i]); return sum; } class Passenger { int id, point, jobID; Passenger(int mID, int mPoint, int mJobID) { id = mID; point = mPoint; jobID = mJobID; } } } package ValueOfRestaurant; // Đang Lỗi import java.util.ArrayDeque; import java.util.ArrayList; import java.util.List; import java.util.Map; import java.util.PriorityQueue; import java.util.Queue; // N cities, mỗi thành phố có ID từ 1 -> N // tên của các nhà hàng được thêm vào thành phố theo ID của cities class UserSolution { // dùng mảng để lưu các đối tượng cities City[] cities; // map tên -> điểm của nhà hàng Map<String, Integer> mapScore; // map substring -> điểm số max trong số những nhà hàng chứa substring Map<String, Integer> mapMax; // cần CTDL tối ưu để lưu N cities và M roads // dùng mảng để lưu N đối tượng cities, trong đối tượng cities có danh sách // Integer linkTo để lưu những thành phố khác cùng nó tạo thành đường void init(int N, int M, int mRoads[][]) { cities = new City[N + 1]; for (int i = 1; i <= N; i++) { cities[i] = new City(); } // mRoads[i][0] là chỉ số cities1; mRoads[i][1] là chỉ số cities2 // của 2 đầu road thứ i (index từ 0 -> M-1) for (int i = 0; i < M; i++) { cities[mRoads[i][0]].linkTo.add(mRoads[i][1]); cities[mRoads[i][1]].linkTo.add(mRoads[i][0]); // đường 2 chiều } } public void addRestaurant(int mCityID, char mName[]) { cities[mCityID].resList.add(string(mName)); } // thêm mScore vào điểm số hiện tại của nhà hàng mName // --> add, update // cấu trúc map lưu nhà hàng, có put vừa add + update // nếu nhà hàng chưa có điểm thì cần tạo mới --> getOrDefault void addValue(char mName[], int mScore) { String name = string(mName); int score = mapScore.getOrDefault(name, 0) + mScore; mapScore.put(name, score); // add hoặc update // gen tất cả các substring có thể for (int i = 0; i < name.length(); i++) { for (int j = 1; i + j <= name.length(); j++) { String sub = name.substring(i, i + j); if (mapMax.getOrDefault(sub, 0) < score) { mapMax.put(sub, score); } } } } // nếu không có nhà hàng nào chứa substring mStr thì return 0 int bestValue(char mStr[]) { return mapMax.getOrDefault(string(mStr), 0); } public int regionalValue(int mCityID, int mDist) { Queue<Integer> queue = new ArrayDeque<>(); Queue<Integer> top3 = new PriorityQueue<>(); // sắp xếp tăng dần // lưu quãng đường từ thành phố hiện tại tới một thành phố bất kỳ int[] dist = new int[cities.length]; queue.add(mCityID); while (!queue.isEmpty()) { int curCity = queue.poll(); // lọc ra top3 nhà hàng có điểm cao nhất trong 1 city // lại được đặt trong vòng while để duyệt city nên khi kết thúc vòng // while, sẽ tìm được top 3 nhà hàng ở tất cả city trong bán kính for (String name : cities[curCity].resList) { top3.add(mapScore.getOrDefault(name, 0)); if (top3.size() > 3) { top3.poll(); // xóa phần tử nhỏ nhất } } for (int next : cities[curCity].linkTo) { if (dist[next] == 0 && next != mCityID) { dist[next] = dist[curCity] + 1; if (dist[next] <= mDist) { queue.add(next); } } } } int sum = 0; for (int score : top3) { sum += score; } return sum; } class City { // danh sách nhà hàng trong city List<String> resList = new ArrayList<>(); // danh sách những thành phố mà city này nối tới List<Integer> linkTo = new ArrayList<>(); } String string(char[] s) { return new String(s).trim(); } } package ValueOfRestaurant; // Doãn Thanh Tùng import java.util.ArrayDeque; import java.util.ArrayList; import java.util.HashMap; import java.util.List; import java.util.Map; import java.util.PriorityQueue; import java.util.Queue; class UserSolution2 { City[] city; Map<String, Integer> mapScore, best; void init(int N, int M, int mRoads[][]) { city = new City[N + 1]; for (int i = 1; i <= N; i++) city[i] = new City(); for (int i = 0; i < M; i++) { city[mRoads[i][0]].connect.add(mRoads[i][1]); city[mRoads[i][1]].connect.add(mRoads[i][0]); } mapScore = new HashMap<>(); best = new HashMap<>(); } void addRestaurant(int mCityID, char mName[]) { city[mCityID].restaurants.add(string(mName)); } void addValue(char mName[], int mScore) { String name = string(mName); int score = mapScore.getOrDefault(name, 0) + mScore; mapScore.put(name, score); for (int i = 0; i < name.length(); i++) { for (int j = 1; i + j <= name.length(); j++) { String sub = name.substring(i, i + j); if (best.getOrDefault(sub, 0) < score) best.put(sub, score); } } } int bestValue(char mStr[]) { return best.getOrDefault(string(mStr), 0); } int regionalValue(int mCityID, int mDist) { Queue<Integer> queue = new ArrayDeque<>(), top3 = new PriorityQueue<>(); int[] dist = new int[city.length]; queue.add(mCityID); while (!queue.isEmpty()) { int currCity = queue.poll(); for (String name : city[currCity].restaurants) { top3.add(mapScore.getOrDefault(name, 0)); if (top3.size() > 3) top3.poll(); } for (int i : city[currCity].connect) if (dist[i] == 0 && i != mCityID) { dist[i] = dist[currCity] + 1; if (dist[i] <= mDist) queue.add(i); } } int sum = 0; for (int score : top3) sum += score; return sum; } String string(char[] s) { int n = -1; while (s[++n] != 0) ; return new String(s, 0, n); } } class City { List<String> restaurants = new ArrayList<>(); List<Integer> connect = new ArrayList<>(); } package WordMaze; import java.util.HashMap; import java.util.Map; import java.util.TreeSet; class UserSolution { // mapDir[] là global database Map<String, TreeSet<String>> mapDir[] = new HashMap[3]; // mapDir dùng để lưu trữ tất cả tiền tố, trung tố, hậu tố và map vào các từ // được sắp xếp theo thứ tự từ điển // String = keyword - tiền tố, hậu tố... / TreeSet<String> là danh sách từ // toàn vẹn Map<String, Room> map = new HashMap<>(); Room current; void init() { map.clear(); for (int i = 0; i < 3; i++) { mapDir[i] = new HashMap<>(); } } void addRoom(int mID, char[] mWord, int[] mDirLen) { Room room = new Room(mID, mWord, mDirLen); room.addToHash(); } void setCurrent(char mWord[]) { current = map.get(string(mWord)); } // di chuyển current, nếu không được return 0 int moveDir(int mDir) { String keyWord = current.dir[mDir]; if (mapDir[mDir].get(keyWord) != null) { for (String word : mapDir[mDir].get(keyWord)) { Room room = map.get(word); if (room != current) { current = room; return room.id; } } } return 0; } void changeWord(char mWord[], char mChgWord[], int mChgLen[]) { Room room = map.get(string(mWord)); room.removeFromHash(); addRoom(room.id, mChgWord, mChgLen); if (room == current) { // nếu phòng đang thay đổi là current thì cập // nhật lại current current = map.get(string(mChgWord)); } } class Room { int id; String word; String dir[] = new String[3]; Room(int mID, char[] mWord, int[] mDirlen) { id = mID; word = string(mWord); dir[0] = word.substring(0, mDirlen[0]); dir[1] = word.substring(4, 7); dir[2] = word.substring(word.length() - mDirlen[2]); } void addToHash() { // thêm Room vào map với từ khóa word // đảo ngược map.put(word, this); // back mapDir[2].computeIfAbsent(word.substring(0, 2), k -> new TreeSet<>()).add(word); mapDir[2].computeIfAbsent(word.substring(0, 4), k -> new TreeSet<>()).add(word); // middle mapDir[1].computeIfAbsent(word.substring(4, 7), k -> new TreeSet<>()).add(word); // front mapDir[0].computeIfAbsent(word.substring(7), k -> new TreeSet<>()) .add(word); mapDir[0].computeIfAbsent(word.substring(9), k -> new TreeSet<>()) .add(word); } void removeFromHash() { map.remove(word); mapDir[2].get(word.substring(0, 2)).remove(word); mapDir[2].get(word.substring(0, 4)).remove(word); mapDir[1].get(word.substring(4, 7)).remove(word); mapDir[0].get(word.substring(7)).remove(word); mapDir[0].get(word.substring(9)).remove(word); } } String string(char[] s) { return new String(s).trim(); } }