LeetCode 485 509 532

485. Max Consecutive Ones

Given a binary array, find the maximum number of consecutive 1s in this array.

题目给定一个由0，1组成的数组，找出其中最大的连续的 1 的数量

第一次的做法，遍历一遍数组，当 1 持续出现时，计数器 cnt 持续加一，当 1 中断即出现 0 时，如果发现 1 持续出现的数量最大，则记录计数器的值。计数器归零。

也就是说 maxi 保存着最长的持续的 1 的长度

 1int findMaxConsecutiveOnes(int* nums, int numsSize){
 2    int maxi = 0, cnt = 0;
 3    for (int i=0; i<numsSize; i++) {
 4        if (nums[i] == 1) {
 5            cnt += 1;
 6        } else {
 7            if (cnt > maxi) maxi = cnt;
 8            cnt = 0;
 9        }
10    }
11    if (cnt > maxi) maxi = cnt;
12    return maxi;
13}

509. Fibonacci Number

The Fibonacci numbers, commonly denoted F(n) form a sequence, called the Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from 0 and 1. That is,

1F(0) = 0,   F(1) = 1
2F(N) = F(N - 1) + F(N - 2), for N > 1.

Given N, calculate F(N).

这题是斐波那契数列，第一个想到的方法是用递归做，然后再用循环做了一遍。

1// 递归
2// Runtime: 12 ms
3// Memory Usage: 6.9 MB
4int fib(int N){
5    if (N == 0) return 0;
6    if (N == 1) return 1;
7    return fib(N-1)+fib(N-2);
8}

 1// 循环
 2// Runtime: 0 ms
 3// Memory Usage: 6.7 MB
 4int fib(int N){
 5    if (N == 0) return 0;
 6    if (N == 1) return 1;
 7    int a = 0, b = 1, c = 0;
 8    for (int i=2; i<=N; i++) {
 9        c = a+b;
10        a = b;
11        b = c;
12    }
13    return c;
14}

532. K-diff Pairs in an Array

Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k.

给定数组 nums 和 k，找出两数距离为 k 的组合数量，并且组合不能重复。这题搬运一下题目提供的样例和要求：

Example 1:

1Input: [3, 1, 4, 1, 5], k = 2
2Output: 2
3Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5).
4Although we have two 1s in the input, we should only return the number of unique pairs.

Example 2:

1Input:[1, 2, 3, 4, 5], k = 1
2Output: 4
3Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).

Example 3:

1Input: [1, 3, 1, 5, 4], k = 0
2Output: 1
3Explanation: There is one 0-diff pair in the array, (1, 1).

Note:

1. The pairs (i, j) and (j, i) count as the same pair.
2. The length of the array won’t exceed 10,000.
3. All the integers in the given input belong to the range: [-1e7, 1e7].

部分参考讨论区。

给定的数组包含重复元素，如果 k != 0 那么将所有数字丢入一个集合 set 中，就可以达到去重的目的。去重之后对每个元素加 k，判断加 k 之后的数字是否还在集合中，如果在，则说明这两个数字可以成为一个符合题意的组合。

但实际上是存在 k == 0 的情况的，所以需要对每个元素计数，这里就可以使用字典了。构建一个 map，用数字作为键，数字出现的次数作为值，之后遍历这个字典寻找符合要求的组合。

在提交评测的时候发现，测试用例包含 k < 0 的情况，这是增加一行代码，让检测到 k < 0 的时候之间返回 0，减少时间消耗。

 1// Runtime: 10 ms
 2// Memory Usage: 40.1 MB
 3class Solution {
 4    public int findPairs(int[] nums, int k) {
 5
 6        if (k < 0) return 0;  // Attention: This line make runtime from 19ms to 10ms ...
 7
 8        HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
 9        for (int num: nums) {
10            map.put(num, map.getOrDefault(num, 0)+1);
11        }
12
13        int cnt = 0;
14        for (Map.Entry<Integer, Integer> pair : map.entrySet()) {
15            int key = pair.getKey();
16            int value = pair.getValue();
17            if (k == 0 && value > 1) {
18                pair.setValue(value-1);
19                cnt++;
20            } else if (k > 0) {
21                if (map.containsKey(key+k)) cnt++;
22            }
23        }
24        return cnt;
25    }
26}