9,405 次浏览 2021年8月22日2021年10月15日由cst

LeetCode刷题

题解

只出现一次的数字

方法1：使用HashMap的getOrDefault

class Solution {
    public int singleNumber(int[] nums) {
       Map<Integer,Integer> map=new HashMap<>();
       for(int i : nums){
           map.put(i,map.getOrDefault(i,0)+1);
       }
       for(Map.Entry<Integer,Integer> entry : map.entrySet() ){
           if(entry.getValue() == 1){
               return entry.getKey();
           }
       }
       return -1;
    }
}

方法2：异或运算，根据此性质：a^b^a = b^a^a = b^(a^a) = b^0= b

class Solution {
    public int singleNumber(int[] nums) {
        int single = 0;
        for (int num : nums) {
            single ^= num;
        }
        return single;
    }
}

多数元素

方式1：摩尔投票法

class Solution {
    public int majorityElement(int[] nums) {
        int count = 0;
        int candidate = -1;
        for (int num : nums) {
            if (count == 0) {
                candidate = num;
            }
            count += (num == candidate) ? 1 : -1;
        }
        return candidate;
    }
}

方式2：排序后，取数组中间的那个数

public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length / 2];
}

搜索二维矩阵 II

根据此有序的二维矩阵，此题要从左下角或右上角开始搜索

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
         // 从左下角开始搜索
        int row = matrix.length-1;
        int col = 0;

        while (row >= 0 && col < matrix[0].length) {
            if (matrix[row][col] > target) {
                row--;
            } else if (matrix[row][col] < target) {
                col++;
            } else { //找到
                return true;
            }
        }

        return false;
    }
}

合并两个有序数组

双指针方法

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int tail = nums1.length - 1;
        int p1 = m - 1;
        int p2 = n - 1;
        while (p2 >= 0) {
            if (p1 < 0 || nums1[p1] <= nums2[p2]) {
                nums1[tail--] = nums2[p2--];
            } else {
                nums1[tail--] = nums1[p1--];
            }
        }
    }
}

合并两个有序链表

//递归方式
class Solution {
    public ListNode mergeTwoLists(ListNode l1, ListNode l2) {
        if (l1 == null) {
            return l2;
        } else if (l2 == null) {
            return l1;
        } else if (l1.val < l2.val) {
            l1.next = mergeTwoLists(l1.next, l2);
            return l1;
        } else {
            l2.next = mergeTwoLists(l1, l2.next);
            return l2;
        }
    }
}

两个链表的第一个公共节点

public class Solution {
    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode A = headA, B = headB;
        while (A != B) {
            A = A != null ? A.next : headB;
            B = B != null ? B.next : headA;
        }
        return A;
    }
}

源自https://leetcode-cn.com/