leetcode面试算法题

1.数组/字符串

合并两个有序数组

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int p1 = 0;//遍历数组1
        int p2 = 0;//遍历数组2

        int[] nums3 = new int[m + n];
        int p = 0;
        while (p1 < m && p2 < n) {//当数组1、2都没遍历完
            nums3[p++] = nums1[p1] <= nums2[p2] ? nums1[p1++] : nums2[p2++];
        }

        while (p1 < m) {
            nums3[p++] = nums1[p1++];
        }

        while (p2 < n) {
            nums3[p++] = nums2[p2++];
        }

        for (int i = 0; i < m + n; i++) {
            nums1[i] = nums3[i];
        }
    }
}

移除元素

class Solution {
     public int removeElement(int[] nums, int val) {

        if(nums.length<1) return 0;

        int l = 0;
        int r = nums.length - 1;
        int res = 0;

        while (l < r) {
            if (nums[l] == val) {
                //换到最末尾的元素一定是和val相同，但换过来的元素还没比较，因此不能直接l--
                swap(l, r--, nums);
            } else {
                res++;//数组有效长度+1
                l++;
            }
        }

         if (nums[l] != val) {
            res++;
        }

        return res;
    }
     public void swap(int a, int b, int[] nums) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }
}

最长回文串

最长回文串长度 = 出现偶数次 + 出现奇数次 - 1(变成偶数次) + 1(如果存在奇数次出现次数，就把其中一个放中间)

class Solution {
    public int longestPalindrome(String s) {
        int res = 0;

        HashMap<Character, Integer> map = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {//统计每个字符出现的次数
            char c = s.charAt(i);
            if (!map.containsKey(c)) {
                map.put(c, 1);
            } else {
                map.put(c, map.get(c) + 1);
            }
        }

        boolean flag = false;//用于判断是否有奇数次字符出现
        for (Integer value : map.values()) {
            if ((value & 1) == 0) {//说明该数是偶数
                res += value;//出现偶数次的字符一定可以用来构建回文字符串
            } else {//奇数次就取奇数次-1位偶数次
                flag = true;
                res += value - 1;
            }
        }

        if (flag) {//选一个奇数放中间，长度+1
            res += 1;
        }
        return res;
    }
}

2.哈希表

有效的字母异位词

class Solution {
       public boolean isAnagram(String s, String t) {

        if (s.length() != t.length()) return false;

        int[] num = new int[26];

        for (int i = 0; i < s.length();i++){
            num[s.charAt(i)-'a']++;
            num[t.charAt(i)-'a']--;
        }

        for (int i : num) {
            if (i!=0){
                return false;
            }
        }

        return true;
    }
}

快乐数

        解释：由于我们知道int的最大值为2147483647，而在这个数字之内的最大的next(next 为各位数字的平方和)。是1999_999_999 (1999_999_999 = 1*1 + 9*9*9(一共有9位数位9))。

        根据以上表格，我们可以发现，即使数字很大，next 范围也会跌下来，很快陷入 [1,243] 这个范围内，这是因为即使是1999_999_999，在经过一次运算以后，也会变成730，而730在[100,999]这个范围之内，说明之后进行快乐数运算，一定会在[1,243]这个范围之内！

        所以在有限次循环之内，就会出现相同的值。接下来面临循环或者达到 1 退出。这是典型的环形链表问题，我们可以通过快慢指针来解决。

class Solution {
    public boolean isHappy(int n) {
        int m = getNext(getNext(n));//快指针，每次进行两次运算
        while (m != n) {
            m = getNext(getNext(m));
            n = getNext(n);
        }
        if (m == 1) {//比较最后相遇的值
                return true;
        }
        return false;
    }

    public int getNext(int n) {//获取当前n的下一个数
        int sum = 0;
        while (n > 0) {
            int m = n % 10;
            n = n / 10;
            sum += m * m;
        }
        return sum;
    }
}

3.栈和队列

数据流中的中位数

思路

1.准备大小两个堆。

2.开始时，第一个数放大根堆。

3.后面放的每一个数字，都和大根堆堆顶元素比较。

        若：大于等于堆顶元素，放入小根堆；小于堆顶元素，放入大根堆。

       每放完一次数，进行一次判断。如果此时大小根堆的长度差绝对值等于2。从元素更多的那个堆的堆顶，弹出一个元素到另一个堆的堆顶。

4.简单来说，就是保证两个堆，各占n/2个元素！

class MedianFinder {

    //小根堆，堆顶元素最小
    PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(
            new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o1 - o2;
                }
            }
    );

    //大根堆，堆顶元素最大
    PriorityQueue<Integer> maxHeap = new PriorityQueue<>(
            new Comparator<Integer>() {
                @Override
                public int compare(Integer o1, Integer o2) {
                    return o2 - o1;
                }
            }
    );

    public MedianFinder() {

    }

    public void addNum(int num) {
        //添加元素时，默认先跟大根堆堆顶元素比较

        if (maxHeap.size() == 0) {//如果大根堆没有元素，直接添加
            maxHeap.add(num);
            return;
        }
        if (num <= maxHeap.peek()) {//如果当前元素比大根堆堆顶元素小，添加到大根堆中
            maxHeap.add(num);
        } else {//反之添加到小根堆中
            minHeap.add(num);
        }
        //判断大小根堆中的元素之差如果等于2，就进行调整
        if (Math.abs(maxHeap.size() - minHeap.size()) == 2) {
            if (maxHeap.size() > minHeap.size()) {//大根堆元素多了
                minHeap.add(maxHeap.poll());
            } else {
                maxHeap.add(minHeap.poll());
            }
        }
    }

    public double findMedian() {

        if (maxHeap.size()>minHeap.size()){
            return maxHeap.peek();
        }
        if (maxHeap.size()<minHeap.size()){
            return minHeap.peek();
        }
        
        return (maxHeap.peek() + minHeap.peek()) / 2.00;
    }
}