Hỏi đáp
Chia sẻ kiến thức, cùng nhau phát triển
Mình đang học về Symbol Table trong Java. Nói nôm na thì giống Hash Table vậy đó. Mình có 1 cái API như sau:
public class LinkedList <Key extends Comparable<Key>, Value extends Comparable<Value>> {
private Node first; // the linked list of key-value pairs
// a helper linked list data type
private class Node {
private Key key;
private Value val;
private Node next;
public Node(Key key, Value val, Node next) {
this.key = key;
this.val = val;
this.next = next;
}
}
/**
* Tạo 1 empty symbol table.
*/
public LinkedList() {
}
/**
* Trả về giá trị của Key đó đang giữ trong table.
*/
public Value get(Key key) {
return null;
}
/**
* Insert vào table một cặp key-value.
* Nếu key đã tồn tại trong table thì giá trị mới sẽ overwrite giá trị cũ.
*/
public void put(Key key, Value val) {
}
/**
*Xóa 1 cặp key-value trong table
*/
public void delete(Key key) {
}
/**
* Trả về size của table
*/
public int size () {
return 1;
}
/**
* Trả về giá trị key lớn thứ 2 trong table
*/
public Key secondMaxKey () {
return null; // TODO
}
/**
* Trả về số lượng key nhỏ hơn key truyền vào. Ví dụ:
-Key-Value:
-A-1 B-2 C-10 D-4 E-0
-rank(D) sẽ trả về giá trị kiểu int là 3.
* Dùng recursion
*/
public int rank (Key key) {
return -1; // Không biết làm
}
}
Mình làm xong hết rồi ngoại trừ phần rank. Phần rank nếu làm bình thường dùng loop thì dễ nhưng ở đây họ yêu cầu dùng recursion (Đệ quy). Bạn nào có thể chỉ cho mình hướng làm được ko? Mình chỉ biết base case là trả về 1 nếu như key == null.
