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

括号

coins

Notes

有没有这个解，return boolean的DFS

1.1 给一个set of n integers，分成两个n/2 sizes each subsets。让他们俩几乎相等

• 每一层：分配一个元素：
• branch：要么加到A这个集合里，要么就把它加到B这个集合里
• 如何求B sum？
• 先求total sum
• DFS枚举所有可能A的sum
• if (Math.abs(total - A Sum) - A Sum） < globalMin) update

1.2找到所有size为K的解

在base case加一个if statement

1.3 没有重复元素的subset

• 对于重复解：根本就不产生，而不是产生完再去重
• 对于DFS中的去重问题，最重要的是什么？
• 必须要sorted array才可以用下面这个方法去重：

while (index + 1 < nums.length && nums[index + 1] == nums[index]) {
	index++；
}

• 增加括号的种类 stack
• 如何处理合法性？
• 对于这道题，N种括号的题目：
• 加左括号的条件： if (i % 2== 0)
• 加右括号的条件：if (!stack.isEmpty() && stack.peek() == 我这个右括号对应的左括号）

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

</aside>