LeetCode刷题笔记——《剑指Offer》面试题（4）

算法
, , ,

时间效率

数组中出现次数超过一半的数字

思路：摩尔投票法。对于当前投票的目标数num，使用一个计数器vote，遍历数组，若当前元素等于num，vote++，否则vote--。若vote==0，更换投票的目标数。这样遍历完数组，最后留下的必然是出现次数最多的数。如果题目不能保证必定出现“出现次数超过一半的数”，需要额外计算众数出现的次数是否大于数组长度的一半。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int majorityElement(int[] nums) {
        int num = nums[0];
        int vote = 1;
        for (int i=1; i<nums.length; i++) {
            if (num==nums[i]) {
                vote++;
            } else {
                vote--;
                if (vote==0) {
                    num = nums[i];
                    vote = 1;
                }
            }
        }
        return num;
    }
}

最小的k个数

思路一：利用快速排序思想，partition函数会返回一个索引，位于它之前的值都比索引所指向的值小，利用此方法找到最小的k个数时间复杂度为$O(n)$，但此方法会改变原数组。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k==0) return new int[]{};
        if (arr.length<=k) return arr;
        getPivot(arr, 0, arr.length-1, k-1);
        int[] res = new int[k];
        for (int i=0; i<k; i++) {
            res[i] = arr[i];
        }
        return res;
    }

    public void getPivot(int[] arr, int l, int r, int k) {
        int p = partition(arr, l, r);
        if (p<k) getPivot(arr, p+1, r, k);
        else if (p>k) getPivot(arr, l, p-1, k);
        else return;
    }

    //快速排序的partition函数，参考《算法》第四版的写法
    public int partition(int[] arr, int lo, int hi) {
        int i = lo, j = hi+1;
        int pivot = arr[lo];
        while (true) {
            while (arr[++i]<pivot) if (i==hi) break;
            while (arr[--j]>pivot) if (j==lo) break;
            if (i>=j) break;
            swap(arr, i, j);
        }
        swap(arr, lo, j);
        return j;
    }

    public void swap(int[] arr, int i, int j) {
        int t = arr[i];
        arr[i] = arr[j];
        arr[j] = t;
    }
}

思路二：利用最大堆。创建一个保存k个元素的最大堆来保存最小的k个数，始终保持顶部元素为k个元素的最大值，当加入新元素时，只需与顶部元素比较。时间复杂度$O(n \log k)$。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int[] getLeastNumbers(int[] arr, int k) {
        if (k==0) return new int[]{};
        if (arr.length<=k) return arr;
        PriorityQueue<Integer> maxHeap = new PriorityQueue<>(k, new Comparator<Integer>(){
            @Override
            public int compare(Integer o1, Integer o2) {
                return o2-o1;
            }
        });
        for (int i: arr) {
            if (maxHeap.size()<k) maxHeap.offer(i);
            else {
                if (maxHeap.peek()>i) {
                    maxHeap.poll();
                    maxHeap.offer(i);
                }
            }
        }
        int[] res = new int[k];
        for (int i=0; i<k; i++) {
            res[i] = maxHeap.poll();
        }
        return res;
    }
}

数据流中的中位数

思路：用一个大顶堆和一个小顶堆分别保存数据流中一半的数，始终保持大顶堆中的数字小于小顶堆中的数字，这样就可以获取位于中间的两个数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {

    private int count=0;
    // 小顶堆，保证其中的元素都比大顶堆的大
    private PriorityQueue<Integer> minHeap = new PriorityQueue<>();
    // 大顶堆，保证其中的元素都比小顶堆的小
    private PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(11, new Comparator<Integer>(){
        @Override
        public int compare(Integer i1,Integer i2) {
            return i2-i1;
        }
    });

    // 为保证两个堆数据平均分配，第奇数个数放入大顶堆，第偶数个数放入小顶堆
    // 为保证大顶堆中的数永远小于小顶堆中的数，先把要放入大顶堆的数放入小顶堆，小顶堆弹出最小值入大顶堆
    public void Insert(Integer num) {
        count++;
        if (count%2==1) {
            minHeap.offer(num);
            maxHeap.offer(minHeap.poll());
        } else {
            maxHeap.offer(num);
            minHeap.offer(maxHeap.poll());
        }
    }

    public Double GetMedian() {
        if (count%2==1) return new Double (maxHeap.peek());
        else return new Double (minHeap.peek()+maxHeap.peek())/2;
    }
}

连续子数组的最大和

思路：如果前面数之和为负数，它对最大子数组和没有帮助，用当前元素的值作为新的和。

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int FindGreatestSumOfSubArray(int[] array) {
        int sum = Integer.MIN_VALUE, max = array[0], n = array.length;
        for (int i=0; i<n; i++) {
            if (sum < 0) sum = array[i];
            else sum += array[i];
            max = Math.max(max, sum);
        }
        return max;
    }
}

1~n整数中1出现的次数

思路：以百位为例，要计算百位上数字1出现的次数，把百位之前的数字记为a，十位和个位组成的数字记为b。

  1. 如果百位为0，百位1出现的次数取决于百位之前的数字，即a*100。
  2. 如果百位为1，百位1出现的次数既包括百位之前的数字，即a*100，也包括百位之后的数字，即b+1。
  3. 如果百位大于1，百位1出现的次数取决于百位之前的数字，即(a+1)*100。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int NumberOf1Between1AndN_Solution(int n) {
        int res = 0;
        int i = 1, before = 0, behind = 0, current = 0;
        while (n/i!= 0) {
            before = n/(i*10);
            behind = n-(n/i)*i;
            current = (n/i)%10;
            if (current==0) res += i*before;
            else if (current==1) res += i*before+behind+1;
            else res += i*(before+1);
            i *= 10;
        }
        return res;
    }
}

数字序列中的某一位数字

思路：要确定数字序列第n位数，就先要确定n属于那一个数字（记为num）；首先要确定num是几位数。

  1. 确定num是几位数。1位数包括1～9共9个数字，2位数包括10～99共90个数字，以此类推，n位数包括10^(n-1)开始到10^n-1共9*10^(n-1)个数字。假设通过此计算得到num是digit位数，该位数的第一个数为start。
  2. 通过n得知num是digit位数中的第几个，确定num。
  3. 将num转化为字符串，计算第n位是哪一个数字。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int findNthDigit(int n) {
        long start = 1, count = 9;
        int digit = 1;
        while (n>count) {
            n -= count;
            start *= 10;
            digit += 1;
            count = start * digit * 9;
        }
        long num = start + (n-1)/digit;
        String str = num+"";
        int number = str.charAt((n-1)%digit) - '0';
        return number;
    }
}

把数组排成最小的数

思路：把数字转换为字符串，按照两数字组合后的顺序排序：如果ab>ba，则a>b，否则a<=b。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public String PrintMinNumber(int [] numbers) {
        String[] str = new String[numbers.length];
        for (int i=0; i<numbers.length; i++) {
            str[i] = String.valueOf(numbers[i]);
        }
        Arrays.sort(str, new Comparator<String>(){
            @Override
            public int compare(String s1, String s2) {
                String s1s2 = s1 + s2;
                String s2s1 = s2 + s1;
                return s1s2.compareTo(s2s1);
            }
        });
        StringBuilder sb = new StringBuilder();
        for (String num: str) {
            sb.append(num);
        }
        return sb.toString();
    }
}

把数字翻译成字符串

思路：动态规划。dp[i]表示从第一位数到到num[i-1]有几种翻译方法。如果这一位数无法和前一位数组成有效翻译，此时dp[i]=dp[i-1]；如果这一位可以与前一位一起翻译，此时dp[i]=dp[i-2]+dp[i-1]。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int translateNum(int num) {
        char[] ch = String.valueOf(num).toCharArray();
        int[] dp = new int[ch.length+1];
        dp[0] = 1;
        dp[1] = 1;
        for (int i=2; i<=ch.length; i++) {
            if (ch[i-2]=='1' || (ch[i-2]=='2' && ch[i-1]<='5')) {
                dp[i] = dp[i-2] + dp[i-1];
            } else {
                dp[i] = dp[i-1];
            }
        }
        return dp[ch.length];
    }
}

礼物的最大价值

思路：动态规划，先初始化矩阵，记录最左一列和最上一行的初始值，然后遍历获得最大值。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int maxValue(int[][] grid) {
        int m = grid.length, n = grid[0].length;
        int[][] res = new int[m][n];
        res[0][0] = grid[0][0];
        for (int i=1; i<m; i++) {
            res[i][0] = grid[i][0] + res[i-1][0];
        }
        for (int j=1; j<n; j++) {
            res[0][j] = grid[0][j] + res[0][j-1];
        }
        for (int i=1; i<m; i++) {
            for (int j=1; j<n; j++) {
                res[i][j] = Math.max(res[i-1][j], res[i][j-1]) + grid[i][j];
            }
        }
        return res[m-1][n-1];
    }
}

最长不含重复字符的子字符串

思路：滑动窗口。遍历字符串，向右扩展窗口的大小，并用一个哈希表记录字符串中每个字符出现的最后位置，当当前窗口中出现重复字符，依据哈希表中记录的位置缩小左边界，并更新最大长度。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int lengthOfLongestSubstring(String s) {
        if (s.length()==0) return 0;
        HashMap<Character, Integer> map = new HashMap<>();
        int left = -1, right = 0;
        int res = 0;
        while (right<s.length()) {
            char c = s.charAt(right);
            if (map.containsKey(c)) {
                left = Math.max(left, map.get(c));
            }
            map.put(c, right);
            res = Math.max(res, right-left);
            right++;
        }
        return res;
    }
}

时间效率与空间效率的平衡

丑数

思路：下一个丑数必定是从已有的丑数乘以2、3、5中的一个得到的最小值。维护三个指针，分别为乘以2、3、5得到的丑数，下一个丑数在这些指针指向的数乘以2/3/5产生。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public int GetUglyNumber_Solution(int index) {
        if (index < 2) return index;
        int[] nums = new int[index];
        nums[0] = 1;
        int p2 = 0, p3 = 0, p5 = 0, i = 1;
        while (i < index) {
            int newUgly = Math.min(nums[p2]*2, Math.min(nums[p3]*3, nums[p5]*5));
            if (nums[p2]*2==newUgly) p2++;
            if (nums[p3]*3==newUgly) p3++;
            if (nums[p5]*5==newUgly) p5++;
            nums[i++] = newUgly;
        }
        return nums[index-1];
    }
}

字符串中第一个只出现一次的字符

思路：使用哈希表，空间换时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
import java.util.HashMap;

public class Solution {
    public int FirstNotRepeatingChar(String str) {
        if (str.length()==0) return -1;
        char[] chars = str.toCharArray();
        HashMap<Character, Integer> map = new HashMap<>();
        for (int i=0; i<chars.length; i++) {
            if (map.containsKey(chars[i])) {
                map.put(chars[i], map.get(chars[i])+1);
            } else {
                map.put(chars[i], 1);
            }
        }
        for (int j=0; j<chars.length; j++) {
            if (map.get(chars[j])==1) {
                return j;
            }
        }
        return -1;
    }
}

字符流中第一个只出现一次的字符

思路：使用哈希表，空间换时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
import java.util.HashMap;
import java.lang.StringBuilder;

public class Solution {
    private HashMap<Character, Integer> map = new HashMap<>();
    private StringBuilder sb = new StringBuilder("");
    //Insert one char from stringstream
    public void Insert(char ch) {
        if (map.containsKey(ch)) map.put(ch, map.get(ch)+1);
        else map.put(ch, 1);
        sb.append(ch);
    }
  //return the first appearence once char in current stringstream
    public char FirstAppearingOnce() {
        for (int i=0; i<sb.length(); i++) {
            if (map.get(sb.charAt(i))==1) return sb.charAt(i);
        }
        return '#';
    }
}

数组中的逆序对

思路：归并排序，在将左子序列和右子序列合并时，如果右边指针所指向的数小于左边指针指向的数，那么左子序列中所有剩余的数与右边指针指向的数形成逆序对。只要在将右子序列中的数放入结果序列时计算逆序对即可。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
class Solution {
    public int reversePairs(int[] nums) {
        int[] copy = new int[nums.length];
        return mergeSort(nums, 0, nums.length-1, copy);
    }

    public int mergeSort(int[] nums, int left, int right, int[] copy) {
        if (left>=right) return 0;
        int mid = left + (right-left)/2;
        int l = mergeSort(nums, left, mid, copy);
        int r = mergeSort(nums, mid+1, right, copy);
        return l+r+merge(nums, left, right, mid, copy);
    }

    public int merge(int[] nums, int left, int right, int mid, int[] copy) {
        for (int i=left; i<=right; i++) {
            copy[i] = nums[i];
        }
        int res = 0;
        int i=left, j=mid+1, k=left;
        while (i<=mid && j<=right) {
            if (copy[i]<=copy[j]) {
                nums[k] = copy[i];
                i++;
            } else {
                res += mid-i+1;//比归并排序仅多了这一步
                nums[k] = copy[j];
                j++;
            }
            k++;
        }
        while (i<=mid) nums[k++] = copy[i++];
        while (j<=right) nums[k++] = copy[j++];
        return res;
    }
}

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

思路：设链表A的长度为a+c，链表B的长度为b+c，其中c为公共部分。将A和B首尾相接，得到长为a+c+b的链表；同理将B和A首尾相接，得到长为b+c+a的链表，两个链表同时开始遍历，指针会在第一个公共节点相遇。如果两个链表不存在公共节点，两个指针会同时到达null。

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
        ListNode p1 = pHead1, p2 = pHead2;
        while (p1 != p2) {
            if (p1 == null) p1 = pHead2;
            else p1 = p1.next;
            if (p2 == null) p2 = pHead1;
            else p2 = p2.next;
        }
        return p1;
    }
}