Date: April 15, 2023

Topic: DFS

Recall

Notes

• DFS的应用场景：找所有可能解
• 吃吐守恒定律：会到母节点，去其他分支之前，一定要还原成原始状态
• 每一层：我就考虑一个元素，分支：加or不加
• 有多少个元素就有多少层 （n层）

<aside> 📌 SUMMARY:

</aside>

Date: April 16, 2023

Topic: DFS Review

Recall

Queue & Stack & Deque review

DFS review

Notes

• 对于用Interface来new出数据结构，准则

• 不能用interface new interface

• 等号前后的<>里的内容必须保持一致，尽量省略后半段<>

• Java里的String是immutable的，所以放进去的时候不用new一个

• char[] array = input.toCharArray();面试里这一步可以不考虑时间复杂度

• 很多时候，string题会禁止使用StringBuilder

• Test In IDE：

		// create a new StringBuilder
		StringBuilder sb=new StringBuilder();
    // test for append method
    sb.append("a");
    System.out.println(sb);

    // test for insert method
    sb.insert(1,"bcdef");
    System.out.println(sb);

    // test for delete method
    sb.delete(1,3);
    System.out.println(sb);

    // test for deleteCharAt(int index) method
    sb.deleteCharAt(0);
    sb.deleteCharAt(sb.length() - 1);
    System.out.println(sb);

    // test for reverse method
    sb.reverse();
    System.out.println(sb);

    // test for replace(int start, int end, String str) method
    sb.replace(0,1,"ab");
    System.out.println(sb);

    // test for setLength() method
    sb.setLength(2);
    System.out.println(sb);

• Problem 1: All subsets
  • null ≠ empty string || null ≠ “”
  • null ≠ empty ArrayList || new ArrayList<Integer>( ) ≠ null
  • empty ArrayList ≠ ArrayList with an empty string || [ ] ≠ [” “]
  • ArrayList of ArrayList with a null pointer ≠ ArrayList of ArrayList with an empty ArrayList
• Problem 2:

<aside> 📌 SUMMARY:

• BFS1: Use a queue to optimize path
• BFS2: Use a Heap
• DFS: Use a stack </aside>

Date: May 7, 2023

Topic: DFS 2

Recall

Subsets

括号

<aside> 📌 SUMMARY: 模版性很强，写题要总结,想清楚当前层要做什么事

</aside>