October

10-28 重新排序得到2的幂

🧩 回溯

class Solution {
    boolean[] vis;
    public boolean reorderedPowerOf2(int n) {
        char[] cs = Integer.toString(n).toCharArray();
        Arrays.sort(cs); // 优化: 135ms -> 35ms
        vis = new boolean[cs.length];
        return backTrack(cs, 0, 0);
    }

    private boolean backTrack(char[] cs, int idx, int num) {
        if (idx == cs.length) {
            return isPowerOfTwo(num);
        }
        for (int i = 0; i < cs.length; ++ i) {
            if (num == 0 && cs[i] == '0') continue;
            if (vis[i]) continue;
            if (i > 0 && !vis[i - 1] && cs[i] == cs[i - 1]) continue;
            vis[i] = true;
            if (backTrack(cs, idx + 1, num * 10 + cs[i] - '0')) {
                return true;
            }
            vis[i] = false;
        }
        return false;
    }
    private boolean isPowerOfTwo(int n) {
        return (n & (n - 1)) == 0;
    }
}

🧩 预处理 + Hash

class Solution {
    // 1ms
    public boolean reorderedPowerOf2(int n) {
        Set<String> set = new HashSet<>();
        for (int i = 0; i < 32; ++ i) {
            set.add(countDigits(1 << i));
        }
        return set.contains(countDigits(n));
    }

    private String countDigits(int num){
        char[] cnt = new char[10];
        while (num > 0) {
            ++ cnt[num % 10];
            num /= 10;
        }
        return new String(cnt);
    }
}

10-27 删除无效的括号

🧩 DFS

class Solution {
    Set<String> set = new HashSet<>();
    int len, min;
    public List<String> removeInvalidParentheses(String s) {
        int l = 0, r = 0;  // 统计应该删除的左右括号数量
        int lcnt = 0, rcnt = 0; // 统计左右括号数量
        for (char c : s.toCharArray()) {
            if (c == '(') {
                l ++;
                lcnt ++;
            } else if (c == ')') {
                if (l != 0) l --;
                else r ++;
                rcnt ++;
            }
        }
        len = s.length() - l - r; // 最终答案的字符串长度
        min = Math.min(lcnt, rcnt);
        dfs(s, "", 0, l, r, 0);
        return new ArrayList<>(set);
    }

    private void dfs(String s, String cur, int idx, int l, int r, int cnt) {
        if (l < 0 || r < 0 || cnt < 0 || cnt > min) {
            return;
        }
        if (l == 0 && r == 0 && idx == s.length()) {
            set.add(cur);
        }
        if (idx == s.length()) return;
        char ch = s.charAt(idx);
        if (ch == '(') {
            dfs(s, cur + String.valueOf(ch), idx + 1, l, r, cnt + 1);
            dfs(s, cur, idx + 1, l - 1, r, cnt);
        } else if (ch == ')') {
            dfs(s, cur + String.valueOf(ch), idx + 1, l, r, cnt - 1);
            dfs(s, cur, idx + 1, l, r - 1, cnt);
        } else {
            dfs(s, cur + String.valueOf(ch), idx + 1, l, r, cnt);
        }
    }
}

10-26 下一个更大元素I

🧩 单调栈(1)

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<>();
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < nums2.length; ++ i) {
            int num = nums2[i];
            while (!stack.isEmpty() && num > stack.peek()) {
                map.put(stack.pop(), num);
            }
            stack.push(num);
        }

        int[] ans = new int[nums1.length];
        for (int i = 0; i < nums1.length; ++ i) {
            ans[i] = map.getOrDefault(nums1[i], -1);
        }
        return ans;
    }
}

🧩 单调栈(2)

class Solution {
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
        Deque<Integer> stack = new ArrayDeque<Integer>();
        for (int i = nums2.length - 1; i >= 0; --i) {
            int num = nums2[i];
            while (!stack.isEmpty() && num >= stack.peek()) {
                stack.pop();
            }
            map.put(num, stack.isEmpty() ? -1 : stack.peek());
            stack.push(num);
        }
        int[] res = new int[nums1.length];
        for (int i = 0; i < nums1.length; ++i) {
            res[i] = map.get(nums1[i]);
        }
        return res;
    }
}

10-22 求众数II

🧩 摩尔投票法

func majorityElement(nums []int) []int {
    ans := []int{}
    elem1, elem2 := 0, 0
    vote1, vote2 := 0, 0
    // 投票法确认预选元素
    for _, v := range nums {
        if (vote1 > 0 && elem1 == v) {
            vote1 ++
        } else if (vote2 > 0 && elem2 == v) {
            vote2 ++
        } else if (vote1 == 0) {
            elem1 = v
            vote1 ++
        } else if (vote2 == 0) {
            elem2 = v
            vote2 ++
        } else { // 三个均不相同的元素,相互抵消1次
            vote1 --
            vote2 --
        }
    }
    // 统计元素出现次数
    cnt1, cnt2 := 0, 0
    for _, v := range nums {
        if v == elem1 {
            cnt1 ++
        }
        if v == elem2 {
            cnt2 ++;
        }
    }
    // 校验元素是否满足要求
    if vote1 > 0 && cnt1 > len(nums) / 3 {
        ans = append(ans, elem1)
    }
    if vote2 > 0 && cnt2 > len(nums) / 3 {
        ans = append(ans, elem2)
    }
    return ans;
}

10-21 加一

🧩 找出最长的后缀9

func plusOne(digits []int) []int {
    n := len(digits)
    for i := n - 1; i >= 0; i -- {
        if digits[i] != 9 {
            digits[i] ++
            for j := i + 1; j < n; j ++ {
                digits[j] = 0;
            }
            return digits
        }
    }
    ans := make([]int, n + 1)
    ans[0] = 1
    return ans
}

10-19 添加与搜索单词 🌟

🧩 Trie树 + DFS

class WordDictionary {
    private TrieNode root;
    public WordDictionary() {
        root = new TrieNode();
    }

    // 添加单词
    public void addWord(String word) {
        root.insert(word);
    }

    // 搜索单词
    public boolean search(String word) {
        return dfs(word, 0, root);  
    }

    public boolean dfs(String word, int idx, TrieNode curNode) {
        if (word.length() == idx) {
            return curNode.isEnd;
        }
        char ch = word.charAt(idx);
        if (Character.isLetter(ch)) {
            curNode = curNode.sub[ch - 'a'];
            if (curNode != null && dfs(word, idx + 1, curNode)) {
                return true;
            }
        } else {
            for (int i = 0; i < 26; ++ i) {
                TrieNode child = curNode.sub[i];
                if (child != null && dfs(word, idx + 1, child)) {
                    return true;
                }
            }
        }
        return false;
    }

    class TrieNode {
        TrieNode[] sub = new TrieNode[26];
        boolean isEnd = false;

        public void insert(String word) {
            TrieNode cur = this;
            for (int i = 0; i < word.length(); ++ i) {
                int idx = word.charAt(i) - 'a';
                if (cur.sub[idx] == null) {
                    cur.sub[idx] = new TrieNode();
                }
                cur = cur.sub[idx];
            }
            cur.isEnd = true;
        }
    }
}

10-17 二叉搜索树中第K小的元素

🧩 中序遍历 迭代

func kthSmallest(root *TreeNode, k int) int {
    stack := []*TreeNode{}
    for {
        for root != nil {
            stack = append(stack, root)
            root = root.Left
        }
        root, stack = stack[len(stack) - 1], stack[:len(stack) - 1]
        k --
        if k == 0 {
            return root.Val
        }
        root = root.Right
    }
}

10-15 外观数列

🧩 递归

func countAndSay(n int) string {
    if n == 1 {
        return "1";
    }
    s := countAndSay(n - 1)
    sb := &strings.Builder{}
    for i := 0; i < len(s); i ++ {
        cnt := 1
        for i + 1 < len(s) && s[i] == s[i + 1] {
            cnt ++
            i ++
        }
        sb.WriteString(strconv.Itoa(cnt))
        sb.WriteByte(s[i])
    }
    return sb.String();
}

10-08 重复的DNA序列

const L = 10
// 四种字符用两个比特表示
var bin = map[byte]int{'A':0, 'C':1, 'G':2, 'T':3}

func findRepeatedDnaSequences(s string) (ans []string) {
    n := len(s)
    if (len(s) < L) {
        return ans;
    }
    x := 0
    //将一个长为 10 的字符串用 20 个比特表示
    for _, ch := range s[:L-1] {
        x = x << 2 | bin[byte(ch)]
    }
    cnt := map[int]int{}
    for i := L; i <= n; i ++ {
        x = (x << 2 | bin[s[i - 1]]) & (1 << (2*L) - 1) 
        cnt[x] ++
        if cnt[x] == 2 {
            ans = append(ans, s[i - L:i])
        }
    }
    return ans;
}

10-05 窥探迭代器

type PeekingIterator struct {
    iter     *Iterator
    _hasNext bool
    _next    int
}

func Constructor(iter *Iterator) *PeekingIterator {
    return &PeekingIterator{iter, iter.hasNext(), iter.next()}
}

func (this *PeekingIterator) hasNext() bool {
    return this._hasNext;
}

func (this *PeekingIterator) next() int {
    ret := this._next;
    this._hasNext = this.iter.hasNext();
    if this._hasNext {
        this._next = this.iter.next();
    }
    return ret;
}

func (this *PeekingIterator) peek() int {
    return this._next;
}

10-04 密钥格式化

func licenseKeyFormatting(s string, k int) string {
    sb := []byte{}
    cnt := 0
    for i := len(s) - 1; i >= 0; i-- {
        if s[i] == '-' {
            continue
        }
        if cnt == k {
            cnt = 0
            sb = append(sb, '-')
        }
        sb = append(sb, byte(unicode.ToUpper(rune(s[i]))))
        cnt ++
    }
    // 反转
    for i, n := 0, len(sb); i < n / 2; i ++ {
        sb[i], sb[n - 1 - i] = sb[n - 1 - i], sb[i]
    }
    return string(sb);
}

10-03 分数到小数

func fractionToDecimal(numerator int, denominator int) string {
    if numerator % denominator == 0 {
        return strconv.Itoa(numerator / denominator)
    }
    s := []byte{}
    if numerator < 0 != (denominator < 0) {
        s = append(s, '-')
    }

    numerator = abs(numerator)
    denominator = abs(denominator)
    // 整数部分
    integerPart := numerator / denominator
    s = append(s, strconv.Itoa(integerPart)...)
    s = append(s, '.')

    // 小数部分
    idxMap := map[int]int{}
    remainder := numerator % denominator
    for remainder != 0 && idxMap[remainder] == 0 {
        idxMap[remainder] = len(s)
        remainder *= 10
        s = append(s, '0' + byte(remainder / denominator))
        remainder %= denominator
    }
    // 判断是否有循环
    if remainder > 0 {
        insertIdx := idxMap[remainder]
        s = append(s[:insertIdx], append([]byte{'('}, s[insertIdx:]...)...)
        s = append(s, ')')
    }
    return string(s)
}

10-02 数字转换为十六进制数

func toHex(num int) string {
    if num == 0 {
        return "0";
    }
    sb := &strings.Builder{}
    for i := 7; i >= 0; i-- {
        val := num >> (i * 4) & 0xf;
        if val > 0 || sb.Len() > 0 {
            var digit byte
            if val < 10 {
                digit = '0' + byte(val)
            } else {
                digit = 'a' + byte(val - 10)
            }
            sb.WriteByte(digit)
        }
    }
    return sb.String();
}

Try and fail, but don't fail to try.