2. 两数相加 - 力扣（LeetCode） (opens new window)

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode dummy = new ListNode(0);
        ListNode current = dummy;
        int carry = 0;
        while (l1 != null || l2 != null || carry != 0) {
            int x = (l1 != null) ? l1.val : 0;
            int y = (l2 != null) ? l2.val : 0; 
            int sum = x + y + carry;
            carry = sum / 10;
            current.next = new ListNode(sum % 10);
            current = current.next;
            if (l1 != null) l1 = l1.next;  
            if (l2 != null) l2 = l2.next;
        }
        return dummy.next;
    }
}

43. 字符串相乘 - 力扣（LeetCode） (opens new window)

class Solution {
    public String multiply(String num1, String num2) {
         // 处理乘数为0的情况
        if (num1.equals("0") || num2.equals("0")) {
            return "0";
        }
        int m = num1.length(), n = num2.length();
        // 结果数组
        int[] result = new int[m + n]; 
        // 逆序遍历每一位（从个位开始）
        for (int i = m - 1; i >= 0; i--) {
            int x = num1.charAt(i) - '0';
            for (int j = n - 1; j >= 0; j--) {
                int y = num2.charAt(j) - '0';
                int multiply = x * y;
                // 加上低位已有值
                int sum = multiply + result[i + j + 1];
                // 更新当前位和进位
                result[i + j + 1] = sum % 10;
                result[i + j] += sum / 10;
            }
        }
        // 转换为字符串并跳过前导零
        StringBuilder sb = new StringBuilder();
        for (int digit : result) {
            // 跳过开头的0
            if (sb.length() == 0 && digit == 0) { 
                continue;
            }
            sb.append(digit);
        }
        return sb.length() == 0 ? "0" : sb.toString();
    }
}

146. LRU 缓存 - 力扣（LeetCode） (opens new window)

class LRUCache {
    
    int cap;
    LinkedHashMap<Integer, Integer> cache = new LinkedHashMap<>();

    public LRUCache(int capacity) {
        this.cap = capacity;
    }
    
    public int get(int key) {
        if (!cache.containsKey(key)) return -1;
        // 将 key 变为最近使用
        recent(key);
        return cache.get(key);
    }
    
    public void put(int key, int value) {
        if (cache.containsKey(key)) {
            // 修改 key 的值
            cache.put(key, value);
            // 将 key 变为最近使用
            recent(key);
            return;
        }
        if (cache.size() >= this.cap) {
            // 链表头部就是最久未使用的 key
            int oldestKey = cache.keySet().iterator().next();
            cache.remove(oldestKey);
        }
        // 将新的 key 添加链表尾部
        cache.put(key, value);
    }

    public void recent(int key) {
        int value = cache.get(key);
        // 删除 key，重新插入到队尾
        cache.remove(key);
        cache.put(key, value);
    }
}

31. 下一个排列 - 力扣（LeetCode） (opens new window)

下一个排列的生成需满足变大幅度最小，具体步骤如下：

1. 从右向左找第一个顺序对
   • 目标：找到最后一个满足 nums[i] < nums[i+1] 的位置 i（即“较小数”需尽量靠右）。
   • 意义：i 右侧的子数组 [i+1, n) 必然是降序排列（因为从右向左遍历时，nums[i] >= nums[i+1] 一直成立）。
2. 在右侧子数组中找“较大数”
   • 若 i >= 0，从右向左在 [i+1, n) 中找第一个满足 nums[j] > nums[i] 的位置 j（即“较大数”需尽量小）。
3. 交换与反转
   • 交换 nums[i] 和 nums[j]。
   • 反转子数组 [i+1, n)（因其原本是降序，反转后变为升序，保证变大幅度最小）。
4. 处理边界情况
   • 若未找到 i（即整个数组降序），直接反转整个数组得到最小排列。

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int i = n - 2;
        // 步骤1：从右向左找第一个顺序对
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }
        if (i >= 0) {
            int j = n - 1;
            // 步骤2：找右侧第一个大于 nums[i] 的数
            while (j >= 0 && nums[i] >= nums[j]) {
                j--;
            }
            // 步骤3：交换
            swap(nums, i, j);
        }
        // 步骤4：反转子数组（或处理边界）
        reverse(nums, i + 1);
    }

    private void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private void reverse(int[] nums, int start) {
        int left = start, right = nums.length - 1;
         while (left < right) {
            swap(nums, left, right);
            left++;
            right--;
         }
    }
}