Leetcode

两数之和

思路一：利用Map，遍历数组时，插入Map，并进行检查key是否存在

整数反转

int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;
            x /= 10;
            if (rev > INT_MAX/10 || (rev == INT_MAX / 10 && pop > 7)) return 0;
            if (rev < INT_MIN/10 || (rev == INT_MIN / 10 && pop < -8)) return 0;
            rev = rev * 10 + pop;
        }
        return rev;
    }

罗马数字转整数

思路一：利用Map预定义映射关系，从前至后遍历罗马数字字符串，取两位或一位，从Map中查询数据，并进行加法。

最长公约前缀

思路一：将所有字符串与第一个字符串进行逐字比较，外层循环第一个字符串，内层循环剩下所有字符串

有效括号

思路一：利用Map预定义括号关系，然后遍历字符串，通过栈结构来与Map匹配分析

合并两个有序链表

思路一：定义Head和Temp节点，循环两个链表，比较节点值大小，小的追加到temp后面，循环结束，追加剩余节点，最后返回Head节点的下一节点

删除排序数组中的重复项

思路一：快慢指针法

public int removeDuplicates(int[] nums) {
    if (nums.length == 0) return 0;
    int i = 0;
    for (int j = 1; j < nums.length; j++) {
        if (nums[j] != nums[i]) {
            i++;
            nums[i] = nums[j];
        }
    }
    return i + 1;
}

实现strStr

思路一：暴力双循环

public int strStr(String haystack, String needle) {
        int haystackLen = haystack.length();
        int needleLen = needle.length();

        for (int i = 0; i < haystackLen - needleLen + 1; i++) {
            int j = 0;
            for (; j < needleLen; j++) {
                if (haystack.charAt(i + j) != needle.charAt(j)) {
                    break;
                }
            }
            if (j == needleLen) {
                return i;
            }
        }

        return -1;
    }

外观数列

思路一：本题的难点在于：报数的概念理解，至少我从题意中没有很清晰的理解，但是感觉像是个递推式。从4->5分析，将4个每一位拆开看（个数+数字），4=1211 => 1=11，2=12，11=21，所以5=111221

public String countAndSay(int n) {
        String str = "1";
        for (int i = 2; i <= n; i++) {
            StringBuilder sBuilder = new StringBuilder();
            char pre = str.charAt(0);
            int counter = 1;
            for (int j = 1; j < str.length(); j++) {
                char temp = str.charAt(j);
                if (temp == pre) {
                    counter++;
                } else {
                    sBuilder.append(counter).append(pre);
                    pre = temp;
                    counter = 1;
                }
            }
            sBuilder.append(counter).append(pre);
            str = sBuilder.toString();
        }

        return str;
    }

最大子序之和

public int maxSubArray(int[] nums) {
        int currSum = nums[0], maxSum = nums[0];
        for(int i = 1; i < nums.length; ++i) {
            currSum = Math.max(nums[i], currSum + nums[i]);
            maxSum = Math.max(maxSum, currSum);
        }
        
        return maxSum;
    }

加一

public int[] plusOne(int[] digits) {
        for (int i = digits.length - 1; i >= 0; i--) {
            digits[i]++;
            digits[i] %= 10;
            if (0 != digits[i]) {
                return digits;
            }
        }

        digits = new int[digits.length + 1];
        digits[0] = 1;
        return digits;
    }

爬楼梯

思路一：动态规划

public int climbStairs(int n) {
        if (n <= 2) {
            return n;
        }

        int[] sum = new int[n + 1];
        sum[1] = 1;
        sum[2] = 2;
        for (int i = 3; i <= n; i++) {
            sum[i] = sum[i - 1] + sum[i - 2];
        }

        return sum[n];
    }

两个有序数组合并

双指针，从后往前遍历

public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = m - 1;
        int p2 = n - 1;
        int p = m + n - 1;
        while (p1 >= 0 && p2 >= 0) {
            nums1[p--] = nums1[p1] > nums2[p2] ? nums1[p1--] : nums2[p2--];
        }
        for (int i = 0; i < p2 + 1; i++) {
            nums1[i] = nums2[i];
        }
    }

对称二叉树

自己与自己对比，左右节点互相对比

public boolean isSymmetric(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode node1 = queue.poll();
            TreeNode node2 = queue.poll();
            if (null == node1 && null == node2) {
                continue;
            }
            if (null == node1 || null == node2) {
                return false;
            }
            if (node1.val != node2.val) {
                return false;
            }
            queue.add(node1.left);
            queue.add(node2.right);
            queue.add(node1.right);
            queue.add(node2.left);
        }

        return true;
    }