1.两数之和 (序号1)

class Solution {
    public int[] twoSum(int[] nums, int target) {
        // 创建一个哈希表，用于存储数组中的元素及其索引
        // 键是数组中的元素，值是该元素的索引
        Map<Integer, Integer> map = new HashMap<>();

        // 遍历数组中的每个元素
        for (int i = 0; i < nums.length; i++) {
            // 计算当前元素的补数（即目标值减去当前元素）
            int complement = target - nums[i];

            // 检查哈希表中是否存在这个补数
            // 如果存在，说明找到了两个数，它们的和等于目标值
            if (map.containsKey(complement)) {
                // 返回两个索引：补数的索引和当前元素的索引
                return new int[] {map.get(complement), i};
            }

            // 如果没有找到补数，将当前元素及其索引存入哈希表
            // 这样后续可以快速查找目标值的补数
            map.put(nums[i], i);
        }

        // 如果遍历结束后仍未找到解决方案，抛出异常
        // 表示没有找到满足条件的两个数
        throw new IllegalArgumentException("No two sum solution");
    }
}
//使用hash时间复杂度为O(1)

2.回文数（序号9）

class Solution {
    public boolean isPalindrome(int x) {
        // 特殊情况：
        // 如上所述，当 x < 0 时，x 不是回文数。
        // 同样地，如果数字的最后一位是 0，为了使该数字为回文，
        // 则其第一位数字也应该是 0
        // 只有 0 满足这一属性
        if (x < 0 || (x % 10 == 0 && x != 0)) {
            return false;
        }

        int revertedNumber = 0;
        while (x > revertedNumber) {
            revertedNumber = revertedNumber * 10 + x % 10;
            x /= 10;
        }

        // 当数字长度为奇数时，我们可以通过 revertedNumber/10 去除处于中位的数字。
        // 例如，当输入为 12321 时，在 while 循环的末尾我们可以得到 x = 12，revertedNumber = 123，
        // 由于处于中位的数字不影响回文（它总是与自己相等），所以我们可以简单地将其去除。
        return x == revertedNumber || x == revertedNumber / 10;
    }
}

3.罗马数字转整数（序号13）

class Solution {
    Map<Character, Integer> symbolValues = new HashMap<Character, Integer>() {{
        put('I', 1);
        put('V', 5);
        put('X', 10);
        put('L', 50);
        put('C', 100);
        put('D', 500);
        put('M', 1000);
    }};

    public int romanToInt(String s) {
        int ans = 0;
        int n = s.length();
        for (int i = 0; i < n; ++i) {
            int value = symbolValues.get(s.charAt(i));
            if (i < n - 1 && value < symbolValues.get(s.charAt(i + 1))) {
                ans -= value;
            } else {
                ans += value;
            }
        }
        return ans;
    }
}

4.最长前缀（序列14）

思路1 ： 定义初始前缀为空 依次遍历每个数组元素的前缀

class Solution {
    public String longestCommonPrefix(String[] strs) {
        // 如果数组为null或长度为0，直接返回空字符串
        if (strs == null || strs.length == 0) {
            return "";
        }

        // 获取数组长度
        int n = strs.length;
        // 初始化最长公共前缀为空字符串
        String s = "";

        // 遍历第一个字符串的每个字符
        for (int k = 0; k < strs[0].length(); k++) {
            // 获取当前字符
            char currentChar = strs[0].charAt(k);

            // 遍历数组中的每个字符串
            for (int i = 1; i < n; i++) {
                // 如果当前字符串长度不足或字符不匹配，返回当前最长公共前缀
                if (k >= strs[i].length() || strs[i].charAt(k) != currentChar) {
                    return s;
                }
            }

            // 如果所有字符串在当前字符位置都匹配，将该字符加入最长公共前缀
            s += currentChar;
        }

        return s;
    }
}

思路2：（逆向思维）假设最长前缀为第一个元素 由于最长前缀不会超过数组最短元素使用可以任意定义 之后从后往前依次裁剪最长前缀

class Solution {
    public String longestCommonPrefix(String[] strs) {
        if (strs == null || strs.length == 0) {
            return "";
        }

        // 取第一个字符串作为初始前缀
        String prefix = strs[0];

        // 遍历数组中的每个字符串
        for (int i = 1; i < strs.length; i++) {
            // 每次更新前缀
            while (strs[i].indexOf(prefix) != 0) {
                // 如果当前字符串不以当前前缀开头，缩短前缀
                prefix = prefix.substring(0, prefix.length() - 1);
                // 如果前缀为空，直接返回
                if (prefix.isEmpty()) {
                    return "";
                }
            }
        }

        return prefix;
    }
}

5.有效括号（序号20）

算法思路

1. 检查字符串长度：
   • 如果字符串长度为奇数，直接返回 false，因为括号必须成对出现。
2. 定义括号对应关系：
   • 使用 HashMap 存储右括号和对应的左括号：
   • java复制 Map<Character, Character> pairs = new HashMap<Character, Character>() {{ put(')', '('); put(']', '[');
   • put('}', '{'); }};
3. 使用栈存储左括号：
   • 使用 Deque 作为栈来存储左括号：
   • java复制Deque<Character> stack = new LinkedList<Character>();
4. 遍历字符串：
   • 逐个字符遍历字符串：java复制for (int i = 0; i < s.length(); i++) { char ch = s.charAt(i);
5. 处理右括号：
   • 如果当前字符是右括号，检查栈顶元素是否匹配：
   • java复制if (pairs.containsKey(ch)) { if (stack.isEmpty() || stack.peek() != pairs.get(ch)) { return false; } stack.pop(); }
6. 处理左括号：
   • 如果当前字符是左括号，压入栈：
   • java复制else { stack.push(ch); }
7. 最终检查栈是否为空：
   • 遍历结束后，如果栈为空，说明所有括号都正确匹配，返回 true；否则，返回 false；
   • java复制return stack.isEmpty();

class Solution {
    public boolean isValid(String s) {
        int n = s.length();
        if (n % 2 == 1) {
            return false;
        }

        Map<Character, Character> pairs = new HashMap<Character, Character>() {{
            put(')', '(');
            put(']', '[');
            put('}', '{');
        }};
        Deque<Character> stack = new LinkedList<Character>();

        for (int i = 0; i < n; i++) {
            char ch = s.charAt(i);
            if (pairs.containsKey(ch)) {
                if (stack.isEmpty() || stack.peek() != pairs.get(ch)) {
                    return false;
                }
                stack.pop();
            } else {
                stack.push(ch);
            }
        }
        return stack.isEmpty();
    }
}

5.合并两个有序链表（序号21）

/**
 * 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 mergeTwoLists(ListNode list1, ListNode list2) {
        // 创建一个虚拟头节点，方便操作
        ListNode dummy = new ListNode(-1);
        ListNode current = dummy;

        // 遍历两个链表，直到其中一个为空
        while (list1 != null && list2 != null) {
            if (list1.val < list2.val) {
                current.next = list1;
                list1 = list1.next;
            } else {
                current.next = list2;
                list2 = list2.next;
            }
            current = current.next;
        }

        // 如果 list1 不为空，直接连接到结果链表
        if (list1 != null) {
            current.next = list1;
        }

        // 如果 list2 不为空，直接连接到结果链表
        if (list2 != null) {
            current.next = list2;
        }

        // 返回合并后的链表（跳过虚拟头节点）
        return dummy.next;
    }
}

6.删除有序数组重复数字（26）

原地去重：

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;

        int j = 0;                 // j 指向当前不重复区间的末尾
        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != nums[j]) {
                j++;
                nums[j] = nums[i]; // 把不重复的元素搬到前面
            }
        }
        return j + 1;             // 新长度
    }
}

双数组:

import java.util.Arrays;

class Solution {
    public int removeDuplicates(int[] nums) {
        if (nums.length == 0) return 0;

        int[] tmp = new int[nums.length]; // 辅助数组
        int j = 0;                        // tmp 的写入指针
        tmp[j] = nums[0];                 // 第 0 个元素肯定保留

        for (int i = 1; i < nums.length; i++) {
            if (nums[i] != tmp[j]) {      // 遇到新的不重复值
                tmp[++j] = nums[i];
            }
        }

        // 把 tmp 的前 j+1 个元素拷回 nums
        System.arraycopy(tmp, 0, nums, 0, j + 1);

        return j + 1;                     // 去重后的长度
    }
}