svilme

class Solution {
    public String longestPalindrome(String s) {
        // 動態規劃
        // dp[i][j]表示子串[i, j]是回文串
        // char(i) == char(j) dp[i][j] = dp[i+1][j-1]
        boolean[][] dp = new boolean[s.length()][s.length()];
        for (int i = 0; i < s.length(); i++) {
            dp[i][i] = true;
        }
        int start = 0;
        int right = 0;
        for (int i = s.length() - 1; i >= 0; i--) {
            for (int j = i + 1; j < s.length(); j++) {
                if (j == i + 1) {
                    dp[i][j] = (s.charAt(i) == s.charAt(j));
                } else {
                    dp[i][j] = (s.charAt(i) == s.charAt(j)) && dp[i + 1][j - 1];
                }
                if (dp[i][j] == true && j - i + 1 > right - start + 1) {
                    start = i;
                    right = j;
                }
            }
        }
        return s.substring(start, right + 1);
    }
}

class Solution {
    public String longestPalindrome(String s) {
        // 從中間向兩側延伸
        int maxLen = 0;
        int start = 0;
        int end = 0;
        for (int i = 0; i < s.length() - 1; i++) {
            int left = i - 1;
            int right = i + 1;
            int count = 1;
            // 以一個字符為中心
            while (left >= 0 && right <= s.length() - 1 && s.charAt(left) == s.charAt(right)) {
                count += 2;
                left--;
                right++;
            }
            if (count > maxLen) {
                start = left + 1;
                end = right - 1;
                maxLen = count;
            }
            // 以兩個字符為中心
            if (i < s.length() - 1 && s.charAt(i) == s.charAt(i + 1)) {
                left = i - 1;
                right = i + 2;
                count = 2;
                while (left >= 0 && right <= s.length() - 1 && s.charAt(left) == s.charAt(right)) {
                    count += 2;
                    left--;
                    right++;
                }
                if (count > maxLen) {
                    start = left + 1;
                    end = right - 1;
                    maxLen = count;
                }
            }
        }
        return s.substring(start, end + 1);
    }
}

class Solution {
    public String reverseWords(String s) {
        // 雙指針從尾部找單詞
        int left = s.length() - 1;
        int right = s.length() - 1;
        StringBuilder sb = new StringBuilder();
        while (left >= 0) {
            while (left >= 0 && s.charAt(left) == ' ') {
                left--;
            }
            right = left;
            while (left >= 0 && s.charAt(left) != ' ') {
                left--;
            }
            sb.append(s.substring(left + 1, right + 1)).append(" ");
        }
        return sb.toString().trim();
    }
}

class Solution {
    public void reverseWords(char[] s) {
        int n = s.length;
        int left = 0, right = 0;
        reverse(s, 0, n-1);
        while (right < n) {
            while (right<n && s[right] != ' ') {
                right++;
            }
            reverse(s, left, right - 1);
            right++;
            left = right;
        }
    }

    private void reverse(char[] s, int i, int j) {
        while(i<j) {
            char t = s[i];
            s[i] = s[j];
            s[j] = t;
            i++;
            j--;
        }
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode oddEvenList(ListNode head) {
        if (head == null || head.next == null || head.next.next == null) {
            return head;
        }
        // 分離奇偶鏈表
        ListNode odd = head; // 奇數鏈表起點
        ListNode even = head.next; // 偶數鏈表起點
        ListNode evenHead = even; // 保存偶數節點鏈表的起點
        while (even != null && even.next != null) {
            odd.next = even.next;
            even.next = odd.next.next;
            odd = odd.next;
            even = even.next;
        }
        odd.next = evenHead;
        return head;
    }
}

class Solution {
    public boolean isIsomorphic(String s, String t) {
        HashMap<Character, Character> reflection = new HashMap<>();
        HashSet<Character> ref_set = new HashSet<>();
        int len = s.length();
        for (int i = 0; i < len; i++) {
            char ch_s = s.charAt(i);
            char ch_t = t.charAt(i);
            if (reflection.containsKey(ch_s)) {
                if (reflection.get(ch_s) != ch_t) {
                    return false;
                }
            } else {
                if (ref_set.contains(ch_t)) {
                    return false; // 不同字符映射在同一個字符上了
                }
                reflection.put(ch_s, ch_t);
                ref_set.add(ch_t); // 添加被映射過的字符
            }
        }
        return true;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode reverseList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode pre = null;
        ListNode cur = head;
        while (cur != null) {
            ListNode nxt = cur.next;
            cur.next = pre;
            pre = cur;
            cur = nxt;
        }
        return pre;
    }
}

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList<>();
        Arrays.sort(nums); // 排序
        for (int i = 0; i < nums.length; i++) { // 先確定一個i
            if (nums[i] > 0) {
                return res;
            }
            if (i > 0 && nums[i] == nums[i - 1]) {
                continue; // i去重
            }
            int left = i + 1; // 雙指針
            int right = nums.length - 1;
            while (left < right) {
                int sum = nums[i] + nums[left] + nums[right];
                if (sum > 0) {
                    right--;
                } else if (sum < 0) {
                    left++;
                } else {
                    res.add(Arrays.asList(nums[i], nums[left], nums[right]));
                    while (left < right && nums[left] == nums[left + 1]) {
                        left++; // left去重
                    }
                    while (right > left && nums[right] == nums[right - 1]) {
                        right--; // right去重
                    }
                    left++;
                    right--;
                }
            }
        }
        return res;
    }
}

class Solution {
    public int rob(int[] nums) {
        // situation1：不打劫第一家
        // situation2：不打劫最後一家 -> 退化為普通的打家劫舍
        if (nums.length == 0) {
            return 0;
        }
        if (nums.length == 1) {
            return nums[0];
        }
        return Math.max(robRange(nums, 0, nums.length - 2), robRange(nums, 1, nums.length - 1));

    }

    int robRange(int[] nums, int start, int end) {
        if (end == start) {
            return nums[start];
        }
        // dp[i]：考慮!!下標i（包括i）以內的房屋，最多可以偷竊的金額為dp[i]
        int[] dp = new int[nums.length];
        dp[start] = nums[start];
        dp[start + 1] = Math.max(nums[start], nums[start + 1]);
        for (int i = start + 2; i <= end; i++) {
            dp[i] = Math.max(dp[i - 1], dp[i - 2] + nums[i]);
        }
        return dp[end];
    }
}

class Solution {
    public String simplifyPath(String path) {
        String[] names = path.split("/");
        Deque<String> stack = new ArrayDeque<>(); // 堆疊或隊列
        for (String name : names) {
            if ("..".equals(name)) { // 上級目錄
                if (!stack.isEmpty()) {
                    stack.pollLast();
                }
            } else if (name.length() > 0 && !".".equals(name)) { // 本級目錄就不管
                stack.offerLast(name);
            }
        }
        StringBuilder sb = new StringBuilder();
        if (stack.isEmpty()) {
            sb.append("/");
        } else {
            while (!stack.isEmpty()) {
                sb.append("/");
                sb.append(stack.pollFirst());
            }
        }
        return sb.toString();
    }
}

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 數字，下標
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0; i < nums.length; i++) {
            if (map.containsKey(target - nums[i])) {
                return new int[] { map.get(target - nums[i]), i };
            } else {
                map.put(nums[i], i);
            }
        }
        return new int[2];
    }
}

class Solution {
    int res = 0;

    public int maxLength(List<String> arr) {
        boolean[] charset = new boolean[26]; // 用來檢測重複的字符
        backtrack(arr, 0, charset, 0);
        return res;
    }

    void backtrack(List<String> arr, int start, boolean[] charset, int count) {
        res = Math.max(res, count); // 每次都更新最大值

        for (int i = start; i < arr.size(); i++) {
            char[] chars = arr.get(i).toCharArray();
            boolean[] charset_copy = charset.clone();
            boolean flag = false;
            for (int j = 0; j < chars.length; j++) {
                if (charset_copy[chars[j] - 'a'] == true) { // 有重複字符
                    flag = true;
                    break;
                } else {
                    charset_copy[chars[j] - 'a'] = true;
                }
            }
            if (flag == true) {
                continue;
            }
            backtrack(arr, i + 1, charset_copy, count + chars.length);
        }
    }
}

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        List<Integer> res = new ArrayList<>();
        // 定義上下左右四個邊界
        int up_bound = 0, down_bound = matrix.length - 1;
        int left_bound = 0, right_bound = matrix[0].length - 1;
        while (up_bound <= down_bound && left_bound <= right_bound) {
            if (up_bound <= down_bound) { // 上
                for (int i = left_bound; i <= right_bound; i++) {
                    res.add(matrix[up_bound][i]);
                }
                up_bound++;
            }
            if (left_bound <= right_bound) {// 右
                for (int i = up_bound; i <= down_bound; i++) {
                    res.add(matrix[i][right_bound]);
                }
                right_bound--;
            }
            if (up_bound <= down_bound) {// 下
                for (int i = right_bound; i >= left_bound; i--) {
                    res.add(matrix[down_bound][i]);
                }
                down_bound--;
            }
            if (left_bound <= right_bound) { // 左
                for (int i = down_bound; i >= up_bound; i--) {
                    res.add(matrix[i][left_bound]);
                }
                left_bound++;
            }

        }
        return res;
    }
}

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        // 動態規劃
        // dp[i][j]表示 text1以下標i-1結尾的子串 與 text2以下標j-1結尾的子串 的最長公共子序列的值
        // char_i ==char_j dp[i][j] = dp[i-1][j-1] + 1
        // or dp[i][j] = max(dp[i-1][j], dp[i][j-1])
        // dp[0][j] = 0; dp[i][0] = 0;
        int[][] dp = new int[text1.length() + 1][text2.length() + 1];
        for (int i = 1; i <= text1.length(); i++) {
            for (int j = 1; j <= text2.length(); j++) {
                if (text1.charAt(i - 1) == text2.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
                }
            }
        }
        return dp[text1.length()][text2.length()];
    }
}

class Solution {
    public String addStrings(String num1, String num2) {
        int ptr1 = num1.length() - 1; // 雙指針
        int ptr2 = num2.length() - 1;
        int carry = 0; // 進位
        StringBuilder sb = new StringBuilder();
        while (ptr1 >= 0 && ptr2 >= 0) {
            int a = num1.charAt(ptr1) - '0';
            int b = num2.charAt(ptr2) - '0';
            sb.append((a + b + carry) % 10);
            carry = (a + b + carry) / 10;
            ptr1--;
            ptr2--;
        }
        while (ptr1 >= 0) {
            int a = num1.charAt(ptr1) - '0';
            sb.append((a + carry) % 10);
            carry = (a + carry) / 10;
            ptr1--;
        }
        while (ptr2 >= 0) {
            int b = num2.charAt(ptr2) - '0';
            sb.append((b + carry) % 10);
            carry = (b + carry) / 10;
            ptr2--;
        }
        if (carry != 0) {
            sb.append(carry);
        }
        return sb.reverse().toString();
    }
}

class Solution {
    public int clumsy(int n) {
        Deque<Integer> stack = new ArrayDeque<>();
        stack.push(n); // 首先將 n 壓入堆疊中
        n--;
        int index = 0; // 用來跟蹤應該使用的操作符

        while (n > 0) {
            if (index % 4 == 0) {
                // 乘法
                stack.push(stack.pop() * n);
            } else if (index % 4 == 1) {
                // 除法
                stack.push(stack.pop() / n);
            } else if (index % 4 == 2) {
                // 加法
                stack.push(n);
            } else {
                // 減法，減法需要入堆疊負數
                stack.push(-n);
            }
            n--;
            index++;
        }

        // 堆疊中所有數字相加
        int result = 0;
        while (!stack.isEmpty()) {
            result += stack.pop();
        }

        return result;
    }
}

class Solution {
    public int largestValsFromLabels(int[] values, int[] labels, int numWanted, int useLimit) {
        // 貪心
        int n = values.length;
        Integer[] id = new Integer[n];
        for (int i = 0; i < n; i++) {
            id[i] = i; // 存放下標
        }
        // 對下標按value降序排序
        Arrays.sort(id, (a, b) -> values[b] - values[a]);
        // label 和 使用次數
        HashMap<Integer, Integer> map = new HashMap<>();
        int sum = 0;
        int count = 0;
        for (int i = 0; i < n; i++) {
            if (count == numWanted) {
                break;
            }
            if (map.getOrDefault(labels[id[i]], 0) == useLimit) {
                continue;
            }
            sum += values[id[i]];
            count++;
            map.put(labels[id[i]], map.getOrDefault(labels[id[i]], 0) + 1);
        }
        return sum;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode();
        ListNode p = dummy;
        int carry = 0;
        while (l1 != null || l2 != null) {
            int val1 = l1 == null ? 0 : l1.val;
            int val2 = l2 == null ? 0 : l2.val;
            int sum = val1 + val2 + carry;
            ListNode node = new ListNode(sum % 10);
            carry = sum / 10;
            p.next = node;
            p = p.next;
            if (l1 != null) {
                l1 = l1.next;
            }
            if (l2 != null) {
                l2 = l2.next;
            }
        }
        if (carry != 0) {
            p.next = new ListNode(carry);
        }
        return dummy.next;
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        Deque<ListNode> stack1 = new ArrayDeque<>();
        Deque<ListNode> stack2 = new ArrayDeque<>();
        ListNode ptr = l1;
        while (ptr != null) {
            stack1.push(ptr);
            ptr = ptr.next;
        }
        ptr = l2;
        while (ptr != null) {
            stack2.push(ptr);
            ptr = ptr.next;
        }
        ListNode dummy = new ListNode(-1, null);
        int carry = 0;
        while (!stack1.isEmpty() && !stack2.isEmpty()) {
            ListNode a = stack1.pop();
            ListNode b = stack2.pop();
            int c = (a.val + b.val + carry) % 10;
            carry = (a.val + b.val + carry) / 10;
            ListNode node = new ListNode(c);
            node.next = dummy.next;
            dummy.next = node;
        }
        while (!stack1.isEmpty()) { // 也可以空的返回0
            ListNode a = stack1.pop();
            int c = (a.val + carry) % 10;
            carry = (a.val + carry) / 10;
            ListNode node = new ListNode(c);
            node.next = dummy.next;
            dummy.next = node;
        }
        while (!stack2.isEmpty()) {
            ListNode b = stack2.pop();
            int c = (b.val + carry) % 10;
            carry = (b.val + carry) / 10;
            ListNode node = new ListNode(c);
            node.next = dummy.next;
            dummy.next = node;
        }
        if (carry != 0) {
            ListNode node = new ListNode(carry);
            node.next = dummy.next;
            dummy.next = node;
        }
        return dummy.next;
    }
}

class Solution {
    public int maximumGap(int[] nums) {
        if (nums.length < 2) {
            return 0;
        }
        Arrays.sort(nums); // O(nlogn) -> 改為使用 基數排序 或 桶排序
        int res = 0;
        for (int i = 0; i < nums.length - 1; i++) {
            res = Math.max(res, nums[i + 1] - nums[i]);
        }
        return res;
    }
}

class Solution {
    List<List<Integer>> res;
    List<Integer> track;
    int sum;

    public List<List<Integer>> combinationSum(int[] candidates, int target) {
        res = new ArrayList<>();
        track = new ArrayList<>();
        sum = 0;
        backtrack(candidates, target, 0);
        return res;
    }

    void backtrack(int[] candidates, int target, int startIndex) {
        if (sum > target) {
            return;
        }
        if (sum == target) {
            res.add(new ArrayList<>(track));
            return;
        }
        for (int i = startIndex; i < candidates.length; i++) {
            sum = sum + candidates[i];
            track.add(candidates[i]);
            backtrack(candidates, target, i);
            sum = sum - candidates[i]; // 回溯
            track.removeLast();
        }
    }
}

class Solution {
    Deque<Integer> numStack = new ArrayDeque<>();
    Deque<StringBuilder> stack = new ArrayDeque<>();

    public String decodeString(String s) {
        int ptr = 0;
        stack.push(new StringBuilder());

        while (ptr < s.length()) {
            char currentChar = s.charAt(ptr);

            if (Character.isDigit(currentChar)) {
                int num = 0;
                while (Character.isDigit(s.charAt(ptr))) {
                    num = num * 10 + (s.charAt(ptr) - '0');
                    ptr++;
                }
                numStack.push(num);
                continue; // 跳過 '['
            } else if (currentChar == ']') {
                int repeatTimes = numStack.pop();
                StringBuilder decodedString = stack.pop();
                StringBuilder parent = stack.peek();

                for (int i = 0; i < repeatTimes; i++) {
                    parent.append(decodedString);
                }
            } else if (currentChar == '[') {
                stack.push(new StringBuilder());
            } else {
                stack.peek().append(currentChar);
            }
            ptr++;
        }
        return stack.pop().toString();
    }
}

/**
 * Definition for singly-linked list.
 * public class ListNode {
 * int val;
 * ListNode next;
 * ListNode() {}
 * ListNode(int val) { this.val = val; }
 * ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode removeNthFromEnd(ListNode head, int n) {
        ListNode dummy = new ListNode(-1, head);
        ListNode slow = dummy, fast = dummy;
        for (int i = 0; i < n; i++) {
            fast = fast.next;
        }
        while (fast.next != null) {
            slow = slow.next;
            fast = fast.next;
        }
        slow.next = slow.next.next;
        return dummy.next;
    }
}