Trong java ngoài cách duyệt mảng bằng vòng lặp for, for each, while, do while thì còn cách nào không?

Cho em hỏi trong java ngoài cách duyệt mảng bằng vòng lặp for, for each, while, do while thì còn cách nào không ạ?
Hiện tại em đang có code như thế này cho em hỏi có cách nào tối ưu thời gian chạy của nó hơn không ạ?

Đề bài: Nhiệm vụ của bạn là viết một chương trình của một từ điển đơn giản, thực hiện các lệnh sau:

  • insert str : chèn xâu str vào từ điển hiện tại.
  • find str : nếu hiện tại, xâu str nằm trong từ điển thì trả về "yes" , ngược lại là "no" .

Với đầu vào là một tập các lệnh insertfind và ban đầu từ điển sẽ rỗng. Bạn hãy trả về một mảng kết quả có n phần tử, trong đó n chính là số lượng lệnh find có trong input và kết quả thứ i chính là lần find thứ i .

Lưu ý: Các lệnh sẽ được thực hiện theo thứ tự.

Đầu vào/Đầu ra:

  • [Giới hạn thời gian chạy]: 1 giây với C++, 6 giây với Java và C#, 8s với Python, GO và Js.
  • [Giới hạn bộ nhớ]: 128 MB
  • [Đầu vào] array of strings arr_op
    1 ≤ arr_op.size() ≤ 2 x 105
    Đảm bảo arr[i] chỉ có thể là một trong 2 dạng "insert str" hoặc "find str"
    1 ≤ str.size() ≤ 12
    Đảm bảo xâu str chỉ là chứa 1 trong 4 ký tự 'A', 'C', 'G', 'T' .
  • [Đầu ra] Array of String
    Một mảng có n phần tử, trong đó n là số lượng lệnh find và phần từ thứ i là kết quả của lần find thứ i.

Code của em:

static String[] dictionary(String[] arr_op) {
    ArrayList<String> temp = new ArrayList<>();
    ArrayList<String> result = new ArrayList<>();
    for (int i = 0; i < arr_op.length; i++) {
        if (arr_op[i].contains("insert")) {
            temp.add(arr_op[i].substring(7));
        } else {
            if (temp.contains(arr_op[i].substring(5)) == true ) {
                result.add("yes");
            } else {
                result.add("no");
            }
        }
    }
    return result.toArray(new String[0]);
}

Em cảm ơn nhiều ạ.

Chèn mảng cho đúng thứ tự thì oải lắm.

Bài này dùng Set rồi.

5 Likes

Set là sao vậy anh ??? em chưa hiểu ạ?

Trong Java, ngoài cách dùng mấy vòng lặp trên còn có thể dùng method forEach(), mà đằng nào cũng là dùng vòng lặp để duyệt mảng thôi :V

Set nó cũng giống như List thôi, nhưng khác với List , các phần tử trong List có thể giống nhau, còn đối với Set , các phần tử trong Set là duy nhất ( nghĩa là giá trị của các phần tử này không được giống nhau ). @rogp10 gợi ý dùng Set vì với Set em có thể thêm một phần tử mới vào mà không cần phải duyệt mảng :slightly_smiling_face:

Ngoài ra, em dùng markdown sai cách rồi :slightly_smiling_face:

6 Likes

Dạ em cảm ơn anh đã chỉ em cách post code ạ, em đã sửa, để em tham khảo cái set anh nói ạ. Em cảm ơn anh nhiều ạ.

Em cảm ơn bác Gà Coder nhiều lắm ạ!!! nhờ dùng Set mà thời gian chạy code của em đã ngắn hơn tận 1s ạ từ 1.75s chỉ còn 0.57.
Code mới của em đây ạ:

static String[] dictionary(String[] arr_op) {

    Set<String> setInsert = new TreeSet<>();
    ArrayList<String> result = new ArrayList<>();

    for (int i = 0; i < arr_op.length; i++) {
        if (arr_op[i].contains("insert")) {
            setInsert.add(arr_op[i].substring(7));
        } else {
            if (setInsert.contains(arr_op[i].substring(5))) {
                result.add("yes");
            } else {
                result.add("no");
            }
        }
    }
    return result.toArray(new String[0]);
}
3 Likes

Cậu đã test find từ “insert” chưa? :smiley:

  @Test
  public void testName() throws Exception {
    assertThat(dictionary(new String[] {"insert insert", "find insert", "find alah", "insert alah", "find alah"}),
        is(new String[] {"yes", "no", "yes"}));
  }
1 Like

Em vừa test bác ạ :v kết quả bị fail rồi ạ :v vậy bài trên bác có hướng nào cho nó chính xác không ạ ?

1 Like

Cậu có thể dùng hàm String#startsWith

  static String[] dictionary(String[] arr_op) {

    Set<String> dictionary = new TreeSet<>();
    List<String> result = new ArrayList<>();
    
    for (int i = 0; i < arr_op.length; i++) {
      String operation = arr_op[i];
      if (operation.startsWith("insert")) {
        dictionary.add(operation.substring(7));
        continue;
      }
    // ...
  }

Implementation của hàm đó khá tốt nên không tốn kém đâu :smiley:

5 Likes

Dạ em cảm ơn bác nhiều lắm ạ, để em xem và chỉnh lại ạ.

1 Like

Ấy cậu, đừng đánh dấu comment của tớ là solution. Comment của @HR16 mới giải quyết vấn đề ban đầu của cậu.
Comment của tớ chỉ add thêm 1 điểm nhỏ thôi :smiley:

6 Likes

Ok bác :v em đã bỏ rồi ạ :v

1 Like

Bác ơi! cho em hỏi tí ạ :v tại sao bác lại phải tạo ra chuỗi String operation để lưu giá trị của arr_op[i] ạ? nếu em để trực tiếp arr_op[i].startsWith() thì có vấn đề gì không ạ?

À, tớ viết thế cho nó dễ đọc thôi cậu. Cậu đọc operation thì sẽ hiểu đó là “thao tác”, nhưng arr_op[i] thì hơn khó hiểu hơn 1 chút :smiley:
Nếu tính sâu xa hơn chút (cái này mở rộng cho cậu thôi, cậu không cần keo kiệt bộ nhớ tới mức đó đâu :smiley: ), thì cậu tiết kiệm 1 vài phép tính để lấy ra phần tử thứ i của mảng.
Cậu có thể để trực tiếp arr_op[i].startsWith(...) nếu như cậu thấy nó đủ đơn giản để cậu hiểu :smile:

5 Likes

Mình nghĩ sẽ nhanh hơn nếu dùng HashSet :thinking:

2 Likes

Dạ em hiểu rồi :v cảm ơn bác đã góp ý ạ.

Sao lại nhanh hơn bác ? bác giải thích giúp em tí ạ.

Bài này hình như chỉ cần biết là từ đã có trong từ điển không. Trường hợp này ko cần phải duy trì thứ tự của các từ đc thêm vào từ điển. TreeSet sẽ duy trì sự sắp xếp của các từ thêm vào, trong khi đó thì HashSet chỉ băm và thêm vào thôi, không có thứ tự nào cả. Tham khảo đây

6 Likes

Hm, tớ lại nghĩ TreeSet có lợi thế hơn khi dữ liệu đủ lớn cậu à :smile:
Tớ có để ý thấy bạn ấy dùng hàm TreeSet#contains, hàm đó tìm kiếm trong cây, nên sẽ nhanh hơn contains của HashSet.

5 Likes

Tại sao contains của HashSet lại chậm hơn :thinking:

4 Likes
83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?