# 資料結構 & 演算法 / Java 解題筆記

**菜，就多練。所以我在練了。**

# 演算法 Algorism

## Dynamic Programming（DP，動態規劃）

### 1. UVa 12455 - Bars
> 2023/05/23 CPE - 第四題
題目：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=3886

import java.util.*;

public class Main{
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int set = sc.nextInt();

        while (set-- > 0) {
            int target = sc.nextInt();
            int num = sc.nextInt();

            int[] bar = new int[num];
            for (int i = 0; i < num; i++) {
                bar[i] = sc.nextInt();
            }

            int[] dp = new int[target + 1];

            for (int i = 0; i < num; i++) {
                for (int j = target; j >= bar[i]; j--) {
                    dp[j] = Math.max(dp[j], dp[j - bar[i]] + bar[i]);
                }
            }

            if (dp[target] == target) {
                System.out.println("YES");
            } else {
                System.out.println("NO");
            }
        }

        sc.close();
    }
}

## Breadth-First Search（BFS，廣度優先搜尋）

### 1. UVa 11518 - Dominos 2
> 2024/05/21 CPE - 第五題
題目：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2513

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int set = sc.nextInt(); 

        while(set-- > 0) {
        int n = sc.nextInt();
        int m = sc.nextInt();
        int l = sc.nextInt();

        int[] flag = new int[n + 1];
        ArrayList<ArrayList<Integer>> road = new ArrayList<>();

        for (int i = 0; i <= n; i++) {
            road.add(new ArrayList<>());
        }

        for (int i = 1; i <= m; i++) {
            int from = sc.nextInt();
            int to = sc.nextInt();
            road.get(from).add(to);
        }

        int sum = 0;
        for (int i = 0; i < l; i++) {
            int from = sc.nextInt();
            sum += bfs(from, flag, road);
        }
        System.out.println(sum);
    }

        sc.close();
    }

    static int bfs(int from, int[] flag, ArrayList<ArrayList<Integer>> road) {
        int count = 0;
        Queue<Integer> queue = new LinkedList<>();

        queue.add(from);
        while (!queue.isEmpty()) {
            for (int i = 0; i < queue.size(); i++) {
                int domino = queue.poll();
                if (flag[domino] == 0) {
                    for (int j = 0; j < road.get(domino).size(); j++) {
                        queue.add(road.get(domino).get(j));
                    }
                    flag[domino] = 1;
                    count++;
                }
            }
        }

        return count;
    }
}

## Depth-First Search（DFS，深度優先搜尋）

### 1. UVa 10858 - Unique Factorization
> 2024/05/21 CPE - 第四題
題目：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1799

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        while (true) {
            int num = sc.nextInt();
            if (num == 0)
                break;

            ArrayList<ArrayList<Integer>> count = new ArrayList<>();
            ArrayList<Integer> arr = new ArrayList<Integer>();

            dfs(num, 2, count, arr);

            if (!count.isEmpty()) {
                count.remove(count.size() - 1);
            }

            System.out.println(count.size());
            for (ArrayList<Integer> i : count) {
                System.out.print(i.get(0));
                for (int j = 1; j < i.size(); j++) {
                    System.out.print(" " + i.get(j));
                }
                System.out.println();
            }
        }

        sc.close();
    }

    static void dfs(int num, int d, ArrayList<ArrayList<Integer>> count, ArrayList<Integer> arr) {
        int bound = (int) Math.sqrt(num);

        for (int i = d; i <= bound; i++) {
            if (num % i == 0) {
                arr.add(i);
                dfs(num / i, i, count, arr);
                arr.remove(arr.size() - 1);
            }
        }
        arr.add(num);
        count.add(new ArrayList<>(arr));
        arr.remove(arr.size() - 1);
    }
}

### 2. 樹狀圖分析 Tree Analyses
> 2017年10月 APCS - 第三題
題目：https://zerojudge.tw/ShowProblem?problemid=c463

# 資料結構 Data Structure

## Stack（堆疊）

### 1. UVa 00514 - Rails
> 題目：https://onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=455

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (true) {
            int num = sc.nextInt();
            if (num == 0)
                break;
            while (true) {
                int[] sequence = new int[num];
                sequence[0] = sc.nextInt();
                if (sequence[0] == 0) {
                    System.out.println();
                    break;
                }
                for (int i = 1; i < num; i++) {
                    sequence[i] = sc.nextInt();
                }

                Stack<Integer> stack = new Stack<>();
                int k = 0;
                for (int i = 1; i <= num; i++) {
                    stack.push(i);
                    while (true) {
                        if (!stack.isEmpty() && stack.peek() == sequence[k]) {
                            stack.pop();
                            k++;
                        } else
                            break;
                    }
                }

                if (stack.isEmpty())
                    System.out.println("Yes");
                else
                    System.out.println("No");
            }
        }

        sc.close();
    }
}