LeetCode做题记录

LeetCode

发布日期: 2022-04-03

文章字数: 3k

阅读时长: 14 分

阅读次数:

前言：在LeetCode上做的题已经有100多道了，但是当我每次想查阅复习已经做过的题目时候，我感到非常不方便。所以特别在此记录每天所做的习题，学习的知识点等。便于复习查阅。（2022.4.3）

2022年

4月

4.3

LeetCode 2 两数相加

思路：

为了方便处理，我们可以将两个链表弄成相同长度。在较短的那个链表前面补0即可。
注意事项就是要考虑进位的处理，同时当遍历到最后一个节点的时候，还要单独判断，是不是需要再去创建一个节点值为1的节点。
Tips:对于链表问题，返回结果为头结点时，通常需要先初始化一个预先指针 pre，该指针的下一个节点指向真正的头结点head。使用预先指针的目的在于链表初始化时无可用节点值，而且链表构造过程需要指针移动，进而会导致头指针丢失，无法返回结果。

class Solution {
    public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
        ListNode pre = new ListNode(0);
        ListNode cur = pre;
        //默认是不进位的
        boolean flag = false;
        while(l1 != null || l2 != null) {
            int x = l1 == null ? 0 : l1.val;
            int y = l2 == null ? 0 : l2.val;
            int sum = x + y;
            if(flag){
                sum++;
                flag = false;
            }
            if(sum >= 10){
                sum = sum % 10;
                flag = true;
            }
            cur.next = new ListNode(sum);

            cur = cur.next;
            if(l1 != null)
                l1 = l1.next;
            if(l2 != null)
                l2 = l2.next;
        }
        //单独判断
        if(flag) {
            cur.next = new ListNode(1);
        }
        return pre.next;

时间复杂度：O(max(m,n))，其中 m 和 n 分别为两个链表的长度。我们要遍历两个链表的全部位置，而处理每个位置只需要 O(1) 的时间。

空间复杂度：O(1)。注意返回值不计入空间复杂度。

LeetCode 34查找排序数组中元素的第一个和最后一个位置

法1：一次二分基本思路

二分查找该元素，找到该元素之后再用while循环去找两个边界。

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int res[] = new int[2];
            if(nums.length==1&&target==nums[0]){
            res[0] = 0;
            res[1] = 0;
            return res;
        }
        res[0] = -1;
        res[1] = -1;
        int left = 0;
        int right = nums.length-1;
        while(left<=right){
            int mid = (right-left)/2+left;
            if(target == nums[mid]){
                int temp = mid;
                while(mid>-1&&nums[mid]==target){
                res[0] = mid;
                mid--;
                }
                while(temp<nums.length&&nums[temp]==target){
                res[1] = temp;
                temp++;
                }
               return res;
            }else if(nums[mid]>target){
                right = mid-1;
            }else left = mid+1;
        }
        return res;  
    }
}

思路二：两次二分

第一次二分找第一个>=target的位置
第二次二分找最后一个<=target的位置

class Solution {
    public int[] searchRange(int[] nums, int target) {
        int[] res = new int[] {-1, -1};
        res[0] = binarySearch(nums, target, true);
        res[1] = binarySearch(nums, target, false);
        return res;
    }
    //leftOrRight为true找左边界 false找右边界
    public int binarySearch(int[] nums, int target, boolean leftOrRight) {
        int res = -1;
        int left = 0, right = nums.length - 1, mid;
        while(left <= right) {
            mid = left + (right - left) / 2;
            if(target < nums[mid])
                right = mid - 1;
            else if(target > nums[mid])
                left = mid + 1;
            else {
                res = mid;
                //处理target == nums[mid]
                if(leftOrRight)
                    right = mid - 1;
                else
                    left = mid + 1;
            }
        }
        return res;
    }
}

时间复杂度O(logn)

LeetCode 139单词拆分

思路一：BFS判断利用队列实现

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        int n = s.length();
        boolean visit[] = new boolean[n+1]; 
         visit[0] = true;
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(0);
        while(!queue.isEmpty()){
            int start = queue.poll();
            for(String word:wordDict){
            int nextStart = start+word.length();
            //如果这个地方以及被访问过了 或者加起来大于了长度
            if(nextStart>n||visit[nextStart]){
                continue;
            }
            //if找到 去判断是不是最后一个
            if(s.indexOf(word,start) == start){
                if(nextStart==n){
                    return true;
                }
                queue.offer(nextStart);
                visit[nextStart] = true;
            }
        }
 
          }
          return false;
    }
}

思路二:动态规划

单词是物品，字符串s为背包

可以重复使用字典中的单词，说明是完全背包问题。

dp[i] : 字符串长度为i的话，dp[i]为true，表示可以拆分为一个或多个在字典中出现的单词。
如果确定dp[j] 是true，且 [j, i] 这个区间的子串出现在字典里，那么dp[i]一定是true。（j < i ）。所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。
所以递推公式是 if([j, i] 这个区间的子串出现在字典里 && dp[j]是true) 那么 dp[i] = true。

class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        boolean[] valid = new boolean[s.length() + 1];
        valid[0] = true;
        for (int i = 1; i <= s.length(); i++) {
            for (int j = 0; j < i; j++) {
                if (wordDict.contains(s.substring(j,i)) && valid[j]) {
                    valid[i] = true;
                }
            }
        }

        return valid[s.length()];
    }
}

时间复杂度：O(n^3)，因为substring返回子串的副本是O(n)的复杂度（这里的n是substring的长度）
空间复杂度：O(n)

4.4

LeetCode 347 前K个高频元素

思路1:

topk问题（前k大）用小根堆，维护堆大小不超过K即可。每次压入堆前和堆顶元素比较，如果比堆顶元素还小，直接扔掉，否则压入堆。检查堆的大小是否超过了K，如果超过了那就弹出堆顶部。复杂度O(nlogk)
避免使用大根堆，因为你必须得把全部元素压入堆，复杂度是O(nlogn)

求前K大，用小根堆，求前K小，用大根堆。

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int num : nums) {
            if (map.containsKey(num)) {
                map.put(num, map.get(num) + 1);
            } else {
                map.put(num, 1);
            }
        }
        PriorityQueue<Integer> queue = new PriorityQueue<>(new Comparator<Integer>() {
            @Override
            public int compare(Integer o1, Integer o2) {
                return map.get(o1) - map.get(o2);
            }
        });
        for(Integer key:map.keySet()){
            if(queue.size()<k){
                queue.add(key);
            }else if(map.get(key)>map.get(queue.peek())){
                queue.remove();
                queue.add(key);
            }
        }
        List<Integer> res = new ArrayList<>();
        while (!queue.isEmpty()){
            res.add(queue.remove());
        }
        return res.stream().mapToInt(Integer::valueOf).toArray();
    }
}

LeetCode633 平方数之和

思路：双指针

假设a<=b 导入a = 0，b为根号c

a^2 + b^2 = c 返回true
a^2 + b^2 < c a++
a^2 + b^2 > c b++

a = b 时候结束查找如果此时还没有找到那就返回false

class Solution {
    public boolean judgeSquareSum(int c) {
        long left = 0;
        long right = (long) Math.sqrt(c);
        while (left <= right) {
            long sum = left * left + right * right;
            if (sum == c) {
                return true;
            } else if (sum > c) {
                right--;
            } else {
                left++;
            }
        }
        return false;
    }
}

复杂度O(c^1/2) 最坏情况下a和b一共枚举了0到根号c中的所有整数

空间复杂度为O(1）

另外也可以先用二分找到最大的小于等于根号C的数字，然后再双指针。

4.5

LeetCode 240 计算质数

思路一:

对正整数n，用2到根号n之间(包含边界)的所有整数去除，均无法整除，则n为质数。
一切不为2的偶数一定不是质数

int countPrimes(int n) {
    if(n < 3)
        return 0;;
    //直接从3开始
    int count = 1;
    for (int i = 3; i < n; i++){
        //当某个数为 2 的 n 次方时（n为自然数），其 & (n - 1) 所得值将等价于取余运算所得值
        //*如果 x = 2^n ，则 x & (n - 1) == x % n
        if ((i % 2) == 0)
            continue; ;
        bool sign = true;
        //用 j * j <= i 代替 j <= √i 会更好。
        //因为我们已经排除了所有偶数，所以每次循环加二将规避偶数会减少循环次数
        for (int j = 3; j * j <=i; j+=2){
            if (i % j == 0){
                sign = false;
                break;
            }
        }
        if (sign)
            count++; ;
    }
    return count;
}

思路二: 厄拉多塞筛选法

具体思路: 在遍历时候，每得到一个数字，就把它的倍数标记，优化筛选过程。

public int CountPrimes(int n)
{
    int count = 0;
    bool[] signs = new bool[n];
    for (int i = 2; i < n; i++)
    {
        if (!signs[i])
        {
            count++;
            for (int j = i + i; j < n; j += i)
            {
                //排除不是质数的数
                signs[j] = true;
            }
        }
    }
    return count;
}

LeetCode 191 位1的个数

思路1：常规模拟

public int hammingWeight(int n) {
    int count = 0;
    while (n != 0) {
        if ((n & 1) == 1)
            count++;
        n >>>= 1;
    }
    return count;
}

特殊解法: Java中Integer.bitCount()源码，tql

public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        n = n - ((n >>> 1) & 0x55555555);
        n = (n & 0x33333333) + ((n >>> 2) & 0x33333333);
        n = (n + (n >>> 4)) & 0x0f0f0f0f;
        n = n + (n >>> 8);
        n = n + (n >>> 16);
        return n & 0x3f;
    }
}

LeetCode 762 二进制表示中质数个计算置位

思路:以上两题的整合题，将二者结合起来即可。

class Solution {
    public int countPrimeSetBits(int left, int right) {
        int ans = 0;
        for (int x = left; x <= right; ++x) {
            if (isPrime(Integer.bitCount(x))) {
                ++ans;
            }
        }
        return ans;
    }

    private boolean isPrime(int x) {
        if (x < 2) {
            return false;
        }
        for (int i = 2; i * i <= x; ++i) {
            if (x % i == 0) {
                return false;
            }
        }
        return true;
    }
}

4.6

LeetCode7 整数反转

class Solution {
    public int reverse(int x) {
        long n = 0;
        while(x!=0){
            n = n*10+x%10;
            x = x/10;
        }
        return (int)n==n? (int)n:0;
    }
}

return (int)n == n ? n : 0把n强制转换为int类型与long类型n进行比较，可以改变n的取值方式然后再跟long的n进行比较，避免发生返回溢出的int错误数值。

LeetCode 11 盛水最多的容器

基本的表达式: area = min(height[i], height[j]) * (j - i) 使用两个指针，值小的指针向内移动，这样就减小了搜索空间因为面积取决于指针的距离与值小的值乘积，如果值大的值向内移动，距离一定减小，而求面积的另外一个乘数一定小于等于值小的值，因此面积一定减小，而我们要求最大的面积，因此值大的指针不动，而值小的指针向内移动遍历

class Solution {
    public int maxArea(int[] height) {
        //Area = Max(min(height[i],height[j])*[j-1])
        if(height.length<=1) return -1;
        int i = 0,j = height.length-1;
        int res = 0;
        while(i<j){
            int h = Math.min(height[i],height[j]);
            res = Math.max(res,h*(j-i));
            if(height[i]<=height[j]){
                i++;
            }else{
                j--;
            }
        }
        return res;

    }
}

4.7

LeetCode 349两个数组的交集

思路:

用一个布尔数组进行标记先用一个for循环增强遍历nums1，让下标为nums1数组里的值的都为true

然后再for循环增强遍历nums2 找到一个就边为false 这样可以保证唯一性

class Solution {
    public int[] intersection(int[] nums1, int[] nums2) {
         boolean nums[] = new boolean[1001];
        int[] res = new int[nums1.length>nums2.length?nums2.length:nums1.length];
        for (int i : nums1) {
            nums[i] = true;
        }
        int index = 0;
        for (int i : nums2) {
            if (nums[i] == true) {
                res[index++] = i;
                nums[i] = false;
            }
        }
        int[] result = new int[index];
        System.arraycopy(res, 0, result, 0, index);
        return result;
    }
}

LeetCode 350 两个数组的交集2

思路:与上题的做法有一点不同，这次用int类型的标记数组，下标为出现的次数即可，其余做法类似.

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
        int []visit  = new int[1001];
        int temp[] = new int[Math.min(nums1.length,nums2.length)];
        for(int i:nums1){
            visit[i]++;  
        }
        int index = 0;
        for(int i: nums2){
            if(visit[i]>0){
                temp[index++] = i;
                visit[i]--;
            }
        }
        int[] result = new int[index];
        System.arraycopy(temp, 0, result, 0, index);
        return result;
    }
}

LeetCode 74 搜索二维矩阵

思路：两次二分

第一次二分在第一列中找最后一个<=target的数组

第二次二分在所在数的那一行中找target

class Solution {
    public boolean searchMatrix(int[][] matrix, int target) {
        int rowIndex = binarySearchFirstColumn(matrix, target);
        if (rowIndex < 0) {
            return false;
        }
        return binarySearchRow(matrix[rowIndex], target);
    }

    public int binarySearchFirstColumn(int[][] matrix, int target) {
        int low = 0, high = matrix.length - 1;
        while (low <= high) {
            int mid = (high - low ) / 2 + low;
            if (matrix[mid][0] <= target) {
                if(mid==high||matrix[mid+1][0]>target){
                    return mid;
                }
                else low = mid + 1;
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }

    public boolean binarySearchRow(int[] row, int target) {
        int low = 0, high = row.length - 1;
        while (low <= high) {
            int mid = (high - low) / 2 + low;
            if (row[mid] == target) {
                return true;
            } else if (row[mid] > target) {
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return false;
    }
}