[数据结构与算法]LeetCode打卡

?

1.两个数组的交集

由于所求交集要求元素不重复，所以我们想到用集合HashSet处理
遍历第一个数组，将所有元素(不含重复)放入集合a中，再遍历第二个数组，如果有元素存在于集合a中，那么将该元素存入集合b，集合b即为交集，遍历存放数组即可

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
        
        HashMap<Integer,Integer> map = new HashMap<>();
        HashSet<Integer> set = new HashSet<>();
        int[] arr = new int[Math.min(nums1.length,nums2.length)];
        int con = 0;
        for(int num : nums1){
            if (!map.containsKey(num)){
                map.put(num,1);
            }
        }
        for(int num : nums2){
            if (map.containsKey(num)){
                set.add(num);
            }
        }
        for(int num : set){
            arr[con] = num;
            con++;
        }
        return Arrays.copyOfRange(arr,0,con);
    }
}

2、多数元素

本题解法很多，可以用哈希表存放每个数据出现的次数，超过一半就是答案呢。还可以排序之后求索引为一半的位置上，一定是众数，但是要求时间复杂度O(n),空间复杂度O(1)，就得想一个精妙的办法–摩尔投票法

摩尔投票法是指众数的票永远比其他所有人的票加起来都多，就像是特朗普如果有美国51%的选票，他可能被希拉里或者拜登打下台吗？

代码如下

/*
执行用时：
1 ms
, 在所有 Java 提交中击败了
99.89%
的用户
内存消耗：
44.5 MB
, 在所有 Java 提交中击败了
48.53%
的用户
通过测试用例：
43 / 43
*/
class Solution {
    public int majorityElement(int[] nums) {
        int cnt = 0;
        int candidate = 0;
        for(int i : nums){
            if (cnt == 0){ //如果选票为0，那么重新选择候选者
                candidate = i;
            }
            cnt += (candidate == i) ? 1 : -1;
        }
        return candidate;
    }
}

3、丢失的数字

排序之后，判断索引为i的位置上的元素是否为 i，如果不是，返回索引值，就是要找的数，如果发现都满足那是咋回事，那就是最后一个数啦。

class Solution {
    public int missingNumber(int[] nums) {
        Arrays.sort(nums);
        int res = 0;
        boolean flag = false;
        for(int i = 0 ; i < nums.length; i++){
            if (nums[i] != i){
                res = i;
                flag = true;
                break;
            }
        }
        if (flag){
             return res;
        }else{
            return nums.length;
        }
    }
}

四、二进制求和

这题，java直接用parseInt一个重载的方法直接将二进制字符串转为Integer，相加之后再Integer.toBinaryString()直接转为二进制的字符串。但是Integer的数字位数有限，因此不够健壮，推荐使用模拟法，逐个加，保持进位是否为1；且最后一位必须加上判断是否还需加1位

class Solution {
    public String addBinary(String a, String b) {
        //模拟
        StringBuffer sb1 = new StringBuffer(a);
        StringBuffer sb2 = new StringBuffer(b);
        String s1 = sb1.reverse().toString();
        String s2 = sb2.reverse().toString();
        StringBuffer sb = new StringBuffer();
        int len1 = a.length();
        int len2 = b.length();
        int l = Math.max(len1,len2);
        int cnt = 0;
        for(int i = 0 ; i < l ; i++){
            int n1 =  i < a.length() ? Integer.parseInt(new String(new char[]{s1.charAt(i)})) : 0;
            int n2 =  i < b.length() ? Integer.parseInt(new String(new char[]{s2.charAt(i)})) : 0;
            sb.append((n1 + n2 + cnt)  % 2);
            if (n1 + n2 + cnt >= 2){
                cnt = 1;
            }else {
                cnt = 0;
            }
        }
        //还要看最后一位是不是要进一
        if (cnt == 1){
            sb.append(1);
        }
        return sb.reverse().toString();
    }
}

五、两数相加

和上一题一样的思路

/**
 * 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 addTwoNumbers(ListNode l1, ListNode l2) {
        if (l1 == null ){
            return l2;
        }
        if (l2 == null ){
            return l1;
        }
        int cnt = 0;//记录是否进位1,记得一轮后要清零
        int i,j,n1,n2;
        ListNode head = new ListNode();
        ListNode temp = head;
        while (l1 != null || l2 != null){
            n1 = l1 != null? l1.val : 0;
            n2 = l2 != null?l2.val : 0;
            i = (n1 + n2 + cnt) %10;
            temp.next = new ListNode(i);
            temp = temp.next;
            if (n1 + n2 + cnt >= 10){
                cnt = 1;
            }else {
                cnt = 0;
            }
            if (l1 !=null){
                l1 = l1.next;
            }
            if (l2 !=null){
                l2 = l2.next;
            }
        }
        if (cnt == 1){
            temp.next = new ListNode(1);
        }
        return head.next;
    }
}

六、爬楼梯

递归超时，所以选择动态规划，滚动数组求解

class Solution {
    public int climbStairs(int n) {
        int p = 0, q = 0 ,r = 1;
        for(int i = 0 ; i < n ; i++){
            p = q;
            q = r;
            r = p+q;
        }
        return r;
    }
}