LeetCode刷题笔记——腾讯面试精选50题（1）

数和数组

Nim游戏

思路：如果堆中石头的数量不能被4整除，那先手方总能取得胜利。

class Solution {
    public boolean canWinNim(int n) {
        return n % 4 != 0;
    }
}

求众数

思路：摩尔投票法：相同加一票，不同减一票，票数为0时更换投票目标，最后的投票目标即为出现次数大于等于一半的众数。

class Solution {
    public int majorityElement(int[] nums) {
        int vote = 0;
        int curr = nums[0];
        for (int num: nums) {
            if (num==curr) vote++;
            else {
                if (vote==0) {
                    curr = num;
                    vote++;
                } else vote--;
            }
        }
        return curr;
    }
}

回文数

思路：负数不可能为回文数；将数字反转，判断数字与反转后的数字是否相等。

class Solution {
    public boolean isPalindrome(int x) {
        if (x<0) return false;
        int rev = reverseInt(x);
        return rev == x;
    }

    public int reverseInt(int x) {
        int rev = 0;
        while (x>0) {
            rev = rev*10 + x%10;
            x /= 10;
        }
        return rev;
    }
}

存在重复元素

思路：利用set不含重复元素的性质。

class Solution {
    public boolean containsDuplicate(int[] nums) {
        HashSet<Integer> set = new HashSet<>();
        for (int num: nums) {
            if (set.contains(num)) return true;
            set.add(num);
        }
        return false;
    }
}

最大子序和

思路：对数组从前到后进行遍历并求和，若前n项的和为负数，则该和对后面的求和最大值无增益，应舍弃，并将下一位的值作为新的和，若和为正数，则继续添加下一位的值。每次更新和时比较和的最大值。

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

删除排序数组中的重复项

思路：利用慢指针i和快指针j，如果指向的两数相等则增加j以跳过重复项，否则令nums[i+1]=nums[j]，并递增i直到指针j到达末尾。

class Solution {
    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        if (len<2) return len;
        int i=0, j=1;
        while (j < len) {
            if (nums[i]!=nums[j]) {
                nums[i+1] = nums[j];
                i++;
            }
            j++;
        }
        return i+1;
    }
}

合并两个有序数组

思路：由于nums1给了足够的空间，指针从后向前扫描，逐个比较nums1和nums2的末位元素的大小，若nums1[i]>nums2[i]，将nums1[i]放入nums1的最末位。若指针扫描完nums1时nums2未扫描完，把nums2的剩余部分全部置入nums1。

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

整数反转

思路：在Integer类型中，整数的范围是[−2^31, 2^31−1]。以正数为例，在使用10*REV+POP时，如果REV/10大于INT_MAX，则必定发生溢出；如果REV/10刚好等于INT_MAX，比较POP是否大于7（int最大正数个位数是7，最小负数个位数是8），若大于则溢出。

class Solution {
    public int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int pop = 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;
            x /= 10;
        }
        return rev;
    }
}

螺旋矩阵 II

思路：模拟指针运行的路径。设定边界坐标：左l，右r，上t，下b。

1. 从左往右，l->r，横坐标不变，纵坐标变；
2. 从上到下，t->b，纵坐标不变，横坐标变；
3. 从右往左，r->l，横坐标不变，纵坐标变；
4. 从下到上，b->t，纵坐标不变，横坐标变。

循环的终止条件为计数器到达n*n。

class Solution {
    public int[][] generateMatrix(int n) {
        int[][] res = new int[n][n];
        int l = 0, r = n-1, t = 0, b = n-1;
        int num = 1;
        while (num <= n*n) {
            for (int i=l; i<=r; i++) {
                res[t][i] = num++;
            }t++; //从左往右

            for (int i=t; i<=b; i++) {
                res[i][r] = num++;
            }r--; //从上往下

            for (int i=r; i>=l; i--) {
                res[b][i] = num++;
            }b--; //从右往左

            for (int i=b; i>=t; i--) {
                res[i][l] = num++;
            }l++; //从下往上
        }
        return res;
    }
}

除自身以外数组的乘积

思路：首先从前往后遍历，第一个值设为1，之后为乘以前面一个元素的乘积，那么遍历一遍过后，数组中保存的是原数组对应位置元素左边元素的累乘。再从右往左如此遍历，则可以得到原数组对应位置元素右边元素的累乘。将这两个结果相乘，即得除自身以外元素的乘积。

class Solution {
    public int[] productExceptSelf(int[] nums) {
        int k = 1;
        int[] res = new int[nums.length];
        for (int i=0; i<nums.length; i++) {
            res[i] = k;
            k *= nums[i];
        }
        k = 1;
        for (int j=nums.length-1; j>=0; j--) {
            res[j] *= k;
            k *= nums[j];
        }
        return res;
    }
}

盛最多水的容器

思路：采用前后双指针扫描，计算此时的面积并记录最大值。由于面积取决于较低的一条边，更新横坐标时，为了尽快到达最大值，优先让较低的一条边向内靠拢。

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

最接近的三数之和

思路：先对数组排序。然后遍历数组，固定一个数，将其后的数字用前后双指针进行遍历，比较三数之和与目标值的大小，保存与目标值最接近的三数之和。时间复杂度：O(nlongn)+O(n^2)=O(n^2)。

class Solution {
    public int threeSumClosest(int[] nums, int target) {
        if (nums.length<3) return 0;
        Arrays.sort(nums);
        int res = nums[0] + nums[1] + nums[2];
        for (int i=0; i<nums.length-2; i++) {
            int j = i+1, k = nums.length-1;
            while (j<k) {
                int threeSum = nums[i] + nums[j] + nums[k];
                if (Math.abs(threeSum-target)<Math.abs(res-target)) res = threeSum;
                if (threeSum<target) j++;
                else if (threeSum>target) k--;
                else return target;
            }
        }
        return res;
    }
}

数组中的第K个最大元素

思路：创建一个小顶堆，将元素保存在堆中，保证堆的大小<=k，这样位于堆顶的元素就是所求的元素。

import java.util.PriorityQueue;

class Solution {
    public int findKthLargest(int[] nums, int k) {
        PriorityQueue<Integer> minHeap = new PriorityQueue<>(k);
        for (int i=0; i<nums.length; i++) {
            if (i<k) minHeap.offer(nums[i]);
            else if (nums[i]>minHeap.peek()) {
                minHeap.poll();
                minHeap.offer(nums[i]);
            }
        }
        return minHeap.peek();
    }
}

搜索旋转排序数组

思路：使用二分查找。

class Solution {
    public int search(int[] nums, int target) {
        int lo = 0, hi = nums.length-1;
        while (lo<=hi) {
            int mid = (lo+hi)/2;
            if (nums[mid]==target) return mid;
            else if (nums[lo]<=nums[mid]) {
                if (nums[lo]<=target&&nums[mid]>=target) hi=mid;
                else lo = mid+1;
            } else {
                if (nums[mid]<=target&&nums[hi]>=target) lo = mid;
                else hi = mid-1;
            }
        }
        return -1;
    }
}

螺旋矩阵

思路：参见《剑指offer》[顺时针打印矩阵]。

class Solution {
    public List<Integer> spiralOrder(int[][] matrix) {
        ArrayList<Integer> res = new ArrayList<>();
        if (matrix.length==0||matrix[0].length==0) return res;
        int m =matrix.length, n = matrix[0].length;
        // 利用左上角坐标(start, start)来标记圈数
        int start = 0;
        while (start*2<m && start*2<n) {
            res.addAll(printCircle(matrix, m, n, start));
            start++;
        }
        return res;
    }

    public List<Integer> printCircle(int[][] matrix, int m, int n, int start) {
        ArrayList<Integer> res = new ArrayList<>();
        int x = n-1-start, y = m-1-start;
        // left->right
        for (int i=start; i<=x; i++) {
            res.add(matrix[start][i]);
        }
        //top->bottom
        if (start<y) {
            for (int i=start+1; i<=y; i++) {
                res.add(matrix[i][x]);
            }
        }
        //right->left
        if (start<x && start<y) {
            for (int i=x-1;i>=start;i--) {
                res.add(matrix[y][i]);
            }
        }
        // bottom->top
        if (start<x && start<y-1) {
            for (int i=y-1;i>=start+1;i--) {
                res.add(matrix[i][start]);
            }
        }
        return res;
    }
}

三数之和

思路：考察对于特殊用例如边界值的处理以及对于算法的优化。

1. 先排除一些不存在解的情况，比如元素全部为正数，或者数组长度少于3的情况；
2. 对数组排序，固定一个数，然后用前后双指针遍历数组，找到和为0的数组，加入解的集合；
3. 在每一次指针变更时，要注意去除重复项。

class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        List<List<Integer>> res = new ArrayList();
        int n = nums.length;
        if (n < 3) return res;
        Arrays.sort(nums);
        if (nums[0] > 0) return res;
        for (int i=0; i<n-2; i++) {
            if (i > 0 && nums[i] == nums[i-1]) continue;
            int j = i+1, k = n-1;
            while (j<k) {
                int sum = nums[i] + nums[j] + nums[k];
                if (sum == 0) {
                    res.add(Arrays.asList(nums[i], nums[j], nums[k]));
                    while (j<k && nums[j+1] == nums[j]) j++;
                    while (k>j && nums[k-1] == nums[k]) k--;
                    j++;
                    k--;
                } else if (sum < 0) j++;
                else k--;
            }
        }
        return res;
    }
}

寻找两个有序数组的中位数

思路：题目要求时间复杂度O(logn)，因此只能使用二分查找。

把此题扩展到查找两个有序数组中第k大的数。如果两个数组长度和m+n为奇数，只需要求k=(m+n+1)/2；如果m+n是偶数，求出k=(m+n+1)/2和k=(m+n+2)/2的均值（m、n分别为数组A、数组B的长度；k从1开始计算，数组下标从0开始计算）。

比较两个有序数组的第k/2个数字。如果A[k/2+1]<B[k/2+1]，说明A[k/2+1]以及位于它之前的A中的元素都不可能是第k个元素，把它们排除，然后继续按照此方法比较剩下的元素中第k-k/2个元素。

如果有一个数组为空了，那么另一个数组的第k个元素就是两个数组中的第k个元素。

如果k=1，则比较两个数组的头元素，取其中较小的那个值。

class Solution {
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int k = m + n;
        if (k % 2 == 1) {
            return new Double(findKth(nums1, nums2, 0, 0, (k+1)/2));
        } // k为奇数的情况
        else {
            return (findKth(nums1, nums2, 0, 0, k/2)+findKth(nums1, nums2, 0, 0, (k+2)/2))/2.0;
        } // k为偶数的情况
    }

    public int findKth(int[] nums1, int[] nums2, int i1, int i2, int k) {
        int m = nums1.length;
        int n = nums2.length;
        // 如果有一个数组为空，取另一个数组的第k个元素
        if (m-i1<=0) return nums2[i2+k-1];
        if (n-i2<=0) return nums1[i1+k-1];
        // 如果k==1，取两数组头部元素中较小的那一个
        if (k==1) return Math.min(nums1[i1], nums2[i2]);
        // 比较第k/2个元素的大小
        int mid = k/2-1;
        // 当第k/2个元素的指针超过数组长度时，取那个数组的尾元素进行比较
        int j1 = Math.min(m-1, i1+mid);
        int j2 = Math.min(n-1, i2+mid);
        // 删除第k/2个元素较小的那个数组的前k/2个元素，同时缩小k
        if (nums1[j1]<nums2[j2]) return findKth(nums1, nums2, j1+1, i2, k-j1-1+i1);
        else return findKth(nums1, nums2, i1, j2+1, k-j2-1+i2);
    }
}