Untitled
Darin
plain_text
2 years ago
4.7 kB
4
Indexable
package SoldierManagement; class UserSolution { class Node // Soldier Node { int id, team, score; Node prev, next; Node(int id, int team) { this.id = id; this.team = team; this.prev = null; this.next = null; } Node(int id, int team, int score) { this.id = id; this.team = team; this.score = score; this.prev = null; this.next = null; } } // 1D Array to Store soldiers id: 1, 100000 public static int MAX_N = 100001; Node[] pool = new Node[MAX_N]; // 2D-Array of Double LinkedList Nodes // Mảng 2 chiều quản lý các lính khác ID thuộc cùng một đội và điểm số Node[][] teams = new Node[6][6]; public void init() { // System.out.println("Init Called:"); // Add Dummy nodes (các nút giả) in the DLL for (int i = 1; i <= 5; i++) { for (int j = 1; j <= 5; j++) { // teams[team][score] => (Head Node) teams[i][j] = new Node(-1, -1); teams[i][j].next = teams[i][j]; // point next of dummy to self teams[i][j].prev = teams[i][j]; // point prev of dummy to self } } return; } public void hire(int mId, int mTeam, int mScore) { // System.out.println("Hire Called:"); // 1. Create node - id độc nhất, kèm theo đội mà lính thuộc về pool[mId] = new Node(mId, mTeam); // 2. Add Node to memory pool (thêm vào bộ nhớ) Node node = pool[mId]; // cả prev và next đều là null // 3. Add Node to teams[team][score] Node head = teams[mTeam][mScore]; node.prev = head.prev; node.next = head; // cập nhật node trước node được thêm, next của nó không phải là head // nữa mà là node mới head.prev.next = node; // cập nhật node giả head.prev = node; return; } public void fire(int mId) { // System.out.println("Fire Called:"); // 1. Get Node Node node = pool[mId]; // 2. Update next & prev => Easy deletion node.prev.next = node.next; node.next.prev = node.prev; return; } public void updateSoldier(int mId, int mScore) { // System.out.println("Update Soldier Called:"); // 1. Get Node Node node = pool[mId]; // 2. Delete node from team & prev ** score fire(mId); // 3. Add Node again in team & new ** score hire(mId, node.team, mScore); return; } public void updateTeam(int mTeam, int mChangeScore) { // System.out.println("Update Team Called:"); if (mChangeScore < 0) // Score decreases { for (int i = 1; i <= 5; i++) { int new_score = i + mChangeScore; if (new_score < 1) new_score = 1; if (new_score != i) // we need to move lists { Node old_head = teams[mTeam][i]; Node new_head = teams[mTeam][new_score]; // Next of last node in old list // vì old_head.prev chính là last node old_head.prev.next = new_head.next; // first of new points to last of old new_head.next.prev = old_head.prev; new_head.next = old_head.next; new_head.next.prev = new_head; // Reset List old_head.next = old_head; old_head.prev = old_head; } } } else // Score increases { for (int i = 5; i >= 1; i--) { int new_score = i + mChangeScore; if (new_score > 5) new_score = 5; if (new_score < 1) new_score = 1; if (new_score != i) // we need to move lists { Node old_head = teams[mTeam][i]; Node new_head = teams[mTeam][new_score]; // Next of last node in old list old_head.prev.next = new_head.next; new_head.next.prev = old_head.prev; // first of new points // to last of old new_head.next = old_head.next; new_head.next.prev = new_head; // Reset List old_head.next = old_head; old_head.prev = old_head; } } } return; } public int bestSoldier(int mTeam) { // System.out.println("Best Soldier Called:"); int max = 0; // 1. Traverse over all scores for the given team // In reverse order because we need soldier with highest score & highest // id for (int i = 5; i >= 1; i--) { Node head = teams[mTeam][i]; if (head.next != head) // When the list is not empty { Node temp; temp = head.next; // pointer to traverse list while (temp != head) { if (temp.id > max) // update max max = temp.id; temp = temp.next; // move to next } // after this lists only with less score will be present // So if this list was not empty & we found a max // That max is the only possible max break; } } return max; } }
Editor is loading...