leetcode记录

记录leetcode做题时的想法和思路,总结一些做题经验。

7.整数反转(简单)

看到这题第一反应是转换成字符串再转回整数没救了,代码写得臭长

class Solution {
    public int reverse(int x) {
        if(x <= Integer.MIN_VALUE || x >= Integer.MAX_VALUE){
            return 0;
        }
        int abs = Math.abs(x);
        String result = "";
        String num = String.valueOf(abs);
        int [] a = new int[num.length()];
        for(int i=0; i<num.length(); i++){
            a[i] = Integer.parseInt(String.valueOf(num.charAt(i)));
        }
        for(int i=num.length()-1; i>=0; i--){
            result = result + a[i];
        }
        if(x < 0){
            result = "-" + result;
        }
        try{
            return Integer.parseInt(result);    
        }catch(Exception e){
            return 0;
        }
    }
}

后面看了官方答案,精简!

class Solution {
    public int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;
            x /= 10;
            if (rev > Integer.MAX_VALUE/10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
            if (rev < Integer.MIN_VALUE/10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;
            rev = rev * 10 + pop;
        }
        return rev;
    }
}

官方解答

9.回文数(简单)

和整数反转差不多,稍微修改下即可

class Solution {
    public boolean isPalindrome(int x) {
        if(x < 0){
            return false;
        }
        Integer pal = 0;
        Integer a = x;
        while(x != 0){
            int pop = x % 10;
            x /= 10;
            pal = pal * 10 + pop;
        }
        if(pal.equals(a)){
            return true;
        }else{
            return false;
        }
    }
}

13.罗马数字转整数(简单)

这题想了蛮久的,没什么思路。看了下评论区的提示:遍历字符串,如果当前字符代表的值不小于其右边,就加上该值;否则就减去该值。以此类推到最左边的数,最终得到的结果即是答案

class Solution {
    public int romanToInt(String s) {
        String[] roman = s.split("");
        int result = 0;
        Map<String, Integer> map = new HashMap<>();
        map.put("I", 1);
        map.put("V", 5);
        map.put("X", 10);
        map.put("L", 50);
        map.put("C", 100);
        map.put("D", 500);
        map.put("M", 1000);
        for(int i=0; i<roman.length; i++){
            if (i<roman.length-1 && map.get(roman[i])<map.get(roman[i+1])){
                result -= map.get(roman[i]);
            }else{
                result += map.get(roman[i]);
            }
        }
        return result;
    }
}

21.合并两个有序链表 (简单)

最开始是想在原链表上完成合并,但难度较大,于是新建一个链表完成合并。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        ListNode head = new ListNode(0);
        ListNode ln = head;
        while(l1 != null && l2 != null){
            if(l1.val < l2.val){
                ln.next = l1;
                ln = ln.next;
                l1 = l1.next;
            }else{
                ln.next = l2;
                ln = ln.next;
                l2 = l2.next;
            }
        }
        if(l1 == null){
            ln.next = l2;
        }
        if(l2 == null){
            ln.next = l1;
        }
        return head.next;
    }
}

26.删除排序数组中的重复项

看了解析,使用双指针法,设i为慢指针,j为快指针。
nums[i]=nums[j] 时,增加j跳过重复项
nums[j]​!=nums[i] 时,跳过重复项的运行已经结束,因此我们必须把 nums[j] 的值复制到 nums[i+1]

class Solution {
    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;
    }
}

58.最后一个单词的长度(简单)

使用 trim() 方法清除字符串两端空格,逆序遍历字符串,遇到第一个空格退出

class Solution {
    public int lengthOfLastWord(String s) {
        s = s.trim();
        int i = s.length()-1;
        for(; i >= 0; i--){
            if(s.charAt(i) == ' '){
                break;
            }
        }
        return s.length()-1-i;
    }
}

66.加一(简单)

最后一个元素加一,不等于 10 加一返回,否则逆序遍历、加一、判断。第一个元素为 10 时扩充数组。

class Solution {
    public int[] plusOne(int[] digits) {
        if(digits[digits.length-1]+1 == 10){
            for(int i = digits.length-1; i >= 0; i--){
                digits[i]++;
                if(digits[i] == 10){
                    digits[i] = 0;
                    if(i == 0){
                        digits = new int[digits.length+1];
                        digits[0] = 1;
                    }
                }else{
                    break;
                }
            }
        }else{
            digits[digits.length-1]++;
        }
        return digits;
    }
}

69.x的平方根(简单)

实现开方运算,可以用二分查找,int类型要注意溢出,判断条件 x/m >= m 代替 m*m <= x 防止溢出

class Solution {
    public int mySqrt(int x) {
        if(x <= 1){
            return x;
        }
        int l = 0;
        int r = x;
        int m = 0;
        while(l <= r){
            m = (l + r) / 2;
            if(x/m >= m && x/(m+1) < (m+1)){
                break;
            }
            if(x/m < m){
                r = m;
            }else{
                l = m;
            }
        }
        return m;
    }
}

还有一种数学方法,牛顿迭代法
牛顿法解 f(x)=0 的迭代公式是 next=cur-f(x)/f'(x)
实在不理解原理也没关系,只要知道,不断迭代 res = (res + x/res) / 2 就会趋于结果。

class Solution {
    public int mySqrt(int x) {
        if(x <= 1){
            return x;
        }
        long res = x;
        while(res > (x/res)){
            res = (res + x/res) / 2;
        }
        return (int)res; 
    }
}

70.爬楼梯(简单)

因为每次可以爬 12 级台阶,所以到达i阶的方法有:

  1. i-1 阶时,爬 1 级台阶
  2. i-2 阶时,爬 2 级台阶

到达 i 阶的方法总数可有 (i-1) + (i-2) 得出

动态规划:

class Solution {
    public int climbStairs(int n) {
        if(n == 1){
            return 1;
        }
        int[] dp = new int[n+1];
        dp[1] = 1;
        dp[2] = 2;
        for(int i = 3; i <= n; i++){
            dp[i] = dp[i-1] + dp[i-2];
        }
        return dp[n];
    }
}

根据上述分析,可以得出 dp[] 其实是一个斐波那契数列

斐波那契数:

public class Solution {
    public int climbStairs(int n) {
        if (n == 1) {
            return 1;
        }
        int first = 1;
        int second = 2;
        for (int i = 3; i <= n; i++) {
            int third = first + second;
            first = second;
            second = third;
        }
        return second;
    }
}

官方解答

83.删除排序链表中的重复元素(简单)

将首次出现的元素存入HashMap,如果已存在,则跳过该元素。该方法效率比较低。

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        Map<Integer, Integer> map = new HashMap<>();
        ListNode myhead = new ListNode(0);
        ListNode ln = myhead;
        while(head != null){
            if(!map.containsKey(head.val)){
                map.put(head.val, 1);
                ln.next = head;
                ln = ln.next;
            }
            head = head.next;
        }
        ln.next = null;
        return myhead.next;
    }
}

直接法:

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode deleteDuplicates(ListNode head) {
        ListNode current = head;
        while(current != null && current.next != null){
            if(current.next.val == current.val){
                current.next = current.next.next;
            }else{
                current = current.next;
            }
        }
        return head;
    }
}

88.合并两个有序数组(简单)

nums2 的元素从 nums1 的尾部开始插入,也可以替换 nums1 中的 0 最后调用内置排序算法,算是一种偷懒的解法

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int j = n+m-1;
        for(int i = 0; i < n; i++){
            nums1[j] = nums2[i];
            j--;
        }
        Arrays.sort(nums1);
    }
}

因为两个数组是有序的,且长度固定,可以使用逆序归并排序

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int k = n+m-1;
        int i = m-1;
        int j = n-1;
        while(k >= 0){
            if(i < 0){
                nums1[k--] = nums2[j--];
            }else if(j < 0){
                break;
            }else if(nums1[i] < nums2[j]){
                nums1[k--] = nums2[j--];
            }else{
                nums1[k--] = nums1[i--];
            }
        }
    }
}

100. 相同的树(简单)

需要注意空指针,难度不大,使用递归即可

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        if(p == null && q == null){
            return true;
        }else if(p != null && q != null && p.val == q.val){
            return isSameTree(p.left, q.left) && isSameTree(p.right, q.right);
        }else{
            return false;
        }
    }
}

101. 对称二叉树(简单)

这题与上一题有点类似,将 p 的左子树与 q 的右子树比较,p 的右子树与 q 的左子树比较。

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isSymmetric(TreeNode root) {
        return isMirror(root, root);
    }
    public boolean isMirror(TreeNode p, TreeNode q){
        if(p == null && q == null){
            return true;
        }else if(p != null && q != null && p.val == q.val){
            return isMirror(p.left, q.right) && isMirror(p.right, q.left);
        }else{
            return false;
        }
    }
}

官方解答

104. 二叉树的最大深度(简单)

使用DFS(深度优先搜索)即可

递归:

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int maxDepth(TreeNode root) {
        if(root == null) {
            return 0;
        }else{
            return Math.max(maxDepth(root.left), maxDepth(root.right)) + 1;
        }
    }
}

迭代:

class Solution {
  public int maxDepth(TreeNode root) {
    Queue<Pair<TreeNode, Integer>> stack = new LinkedList<>();
    if (root != null) {
      stack.add(new Pair(root, 1));
    }

    int depth = 0;
    while (!stack.isEmpty()) {
      Pair<TreeNode, Integer> current = stack.poll();
      root = current.getKey();
      int current_depth = current.getValue();
      if (root != null) {
        depth = Math.max(depth, current_depth);
        stack.add(new Pair(root.left, current_depth + 1));
        stack.add(new Pair(root.right, current_depth + 1));
      }
    }
    return depth;
  }
}

官方解答

  • 用支付宝打我
  • 用微信打我

Long may the sunshine

评论已关闭。

召唤蕾姆