数对和 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
设计一个算法，找出数组中两数之和为指定值的所有整数对。一个数只能属于一个数对。

示例 1:

输入: nums = [5,6,5], target = 11
输出: [[5,6]]
示例 2:

输入: nums = [5,6,5,6], target = 11
输出: [[5,6],[5,6]]
提示：

nums.length <= 100000
通过次数6,776提交次数14,755

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/pairs-with-sum-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

排序+双指针

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public List<List<Integer>> pairSums(int[] nums, int target) {
        if (nums == null || nums.length == 0) return new ArrayList<>();
        Arrays.sort(nums);
        List<List<Integer>> resList = new ArrayList<>();
        int len = nums.length;
        int left = 0, right = len - 1;

        while (left < right) {
            int val = nums[left] + nums[right];
            if (val < target) {
                left++;
            } else if (val > target) {
                right--;
            } else {
                resList.add(Arrays.asList(nums[left], nums[right]));
                left++;
                right--;
            }
        }

        return resList;
    }
}

哈希表

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
class Solution {
    public List<List<Integer>> pairSums(int[] nums, int target) {
        Map<Integer, Integer> map = new HashMap<>();

        for (int i = 0; i < nums.length; i++) {
            map.put(nums[i], map.getOrDefault(nums[i], 0) + 1);
        }
        List<List<Integer>> resList = new ArrayList<>();
        for (Map.Entry entry : map.entrySet()) {

            int key = target - (int) entry.getKey();
            if (key == (int) entry.getKey()&&(int)entry.getValue()==1) continue;

            int num = map.getOrDefault(key, 0);
            if(key == (int) entry.getKey())num/=2;

            int addNum = Math.min((int) entry.getValue(), num);
            for (int i = 0; i < addNum; i++) {
                resList.add(Arrays.asList((int) entry.getKey(), key));
            }
            if (addNum > 0) {
                entry.setValue(0);
                map.put(key, 0);
            }
        }

        return resList;
    }
}

展开全文 >>

交换和 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
给定两个整数数组，请交换一对数值（每个数组中取一个数值），使得两个数组所有元素的和相等。

返回一个数组，第一个元素是第一个数组中要交换的元素，第二个元素是第二个数组中要交换的元素。若有多个答案，返回任意一个均可。若无满足条件的数值，返回空数组。

示例:

输入: array1 = [4, 1, 2, 1, 1, 2], array2 = [3, 6, 3, 3]
输出: [1, 3]
示例:

输入: array1 = [1, 2, 3], array2 = [4, 5, 6]
输出: []
提示：

1 <= array1.length, array2.length <= 100000

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/sum-swap-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
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
class Solution {
    public int[] findSwapValues(int[] array1, int[] array2) {
        if (array1 == null || array2 == null || array1.length == 0 || array2.length == 0) return new int[]{};
        int index = 0;
        int sum1 = 0;
        int sum2 = 0;
        Set<Integer> set = new HashSet<>();
        while (index < array1.length || index < array2.length) {
            if (index < array1.length) {
                sum1 += array1[index];
                set.add(array1[index]);
            }
            if (index < array2.length) sum2 += array2[index];
            index++;
        }

        if ((sum1 - sum2) % 2 != 0) return new int[]{};                     //如果两个数的差值不是偶数，那么就不能通过交换使两个和相等
        int diff = (sum1 - sum2) / 2;
        // if (diff - (sum1 - sum2) * 1.0 / 2 != 0) return new int[]{};

        for (int i = 0; i < array2.length; i++) {
            int val = array2[i] + diff;
            if (set.contains(val)) {                                        //通过set将两层循环改成一层
                return new int[]{val, array2[i]};
            }
        }

        return new int[]{};
    }
}

展开全文 >>

T9键盘 

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
在老式手机上，用户通过数字键盘输入，手机将提供与这些数字相匹配的单词列表。每个数字映射到0至4个字母。给定一个数字序列，实现一个算法来返回匹配单词的列表。你会得到一张含有有效单词的列表。映射如下图所示：

Map<Character, String> map = new HashMap<>();
map.put('2', "abc");
map.put('3', "def");
map.put('4', "ghi");
map.put('5', "jkl");
map.put('6', "mno");
map.put('7', "pqrs");
map.put('8', "tuv");
map.put('9', "wxyz");

示例 1:

输入: num = "8733", words = ["tree", "used"]
输出: ["tree", "used"]
示例 2:

输入: num = "2", words = ["a", "b", "c", "d"]
输出: ["a", "b", "c"]
提示：

num.length <= 1000
words.length <= 500
words[i].length == num.length
num中不会出现 0, 1 这两个数字

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/t9-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
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
class Solution {
    public List<String> getValidT9Words(String num, String[] words) {
        if (words == null || words.length == 0) return new ArrayList<>();
        Map<Character, String> map = new HashMap<>();
        map.put('2', "abc");
        map.put('3', "def");
        map.put('4', "ghi");
        map.put('5', "jkl");
        map.put('6', "mno");
        map.put('7', "pqrs");
        map.put('8', "tuv");
        map.put('9', "wxyz");

        List<String> res = new ArrayList<>();

        char[] numArr = num.toCharArray();
        for (int i = 0; i < words.length; i++) {
            char[] wordArr = words[i].toCharArray();
            if (wordArr.length == numArr.length) {
                boolean flag = true;
                for (int j = 0; j < wordArr.length; j++) {
                    if (!map.get(numArr[j]).contains(wordArr[j] + "")) flag = false;
                }
                if (flag) res.add(words[i]);
            }
        }

        return res;
    }
}

java语法糖，continue可以直接外层的continue

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
40
41
42
43
44
45
46
47
48
49
50
51
52
53
class Solution {
    public List<String> getValidT9Words(String num, String[] words) {
        HashMap<Character, Character> map = new HashMap<>(26);
        map.put('a', '2');
        map.put('b', '2');
        map.put('c', '2');

        map.put('d', '3');
        map.put('e', '3');
        map.put('f', '3');

        map.put('g', '4');
        map.put('h', '4');
        map.put('i', '4');

        map.put('j', '5');
        map.put('k', '5');
        map.put('l', '5');

        map.put('m', '6');
        map.put('n', '6');
        map.put('o', '6');

        map.put('p', '7');
        map.put('q', '7');
        map.put('r', '7');
        map.put('s', '7');

        map.put('t', '8');
        map.put('u', '8');
        map.put('v', '8');

        map.put('w', '9');
        map.put('x', '9');
        map.put('y', '9');
        map.put('z', '9');
        LinkedList<String> res = new LinkedList<>();
        search:
        for (String word : words) {
            int idx = 0;
            for (char c : word.toCharArray())
                if (map.get(c) != num.charAt(idx++))
                    continue search;
            res.addLast(word);
        }
        return res;
    }
}

作者：gfu
链接：https://leetcode-cn.com/problems/t9-lcci/solution/ying-bian-ma-zheng-ze-by-gfu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

水域大小 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
你有一个用于表示一片土地的整数矩阵land，该矩阵中每个点的值代表对应地点的海拔高度。若值为0则表示水域。由垂直、水平或对角连接的水域为池塘。池塘的大小是指相连接的水域的个数。编写一个方法来计算矩阵中所有池塘的大小，返回值需要从小到大排序。

示例：

输入：
[
  [0,2,1,0],
  [0,1,0,1],
  [1,1,0,1],
  [0,1,0,1]
]
输出： [1,2,4]
提示：

0 < len(land) <= 1000
0 < len(land[i]) <= 1000
通过次数12,279提交次数20,363

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/pond-sizes-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

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
40
41
42
43
44
45
46
47
class Solution {
    int count = 0;

    public int[] pondSizes(int[][] land) {
        if (land == null || land.length == 0 || land[0].length == 0) return new int[]{0};

        PriorityQueue<Integer> pq = new PriorityQueue<>();

        boolean vis[][] = new boolean[land.length][land[0].length];
        for (int i = 0; i < land.length; i++) {
            for (int j = 0; j < land[0].length; j++) {

                if (land[i][j] == 0 && !vis[i][j]) {
                    count = 0;
                    deep(land, vis, i, j);
                    pq.offer(count);
                }
            }
        }

        int[] res = new int[pq.size()];
        int index = 0;
        while (!pq.isEmpty()) {
            res[index] = pq.poll();
            index++;
        }

        return res.length == 0 ? new int[]{0} : res;
    }

    public void deep(int[][] land, boolean[][] vis, int y, int x) {
        if (x >= land[0].length || x < 0 || y >= land.length || y < 0 || vis[y][x]) return;

        if (land[y][x] == 0) {
            count++;
            vis[y][x] = true;
            deep(land, vis, y + 1, x + 1);
            deep(land, vis, y + 1, x);
            deep(land, vis, y, x + 1);
            deep(land, vis, y + 1, x - 1);
            deep(land, vis, y - 1, x - 1);
            deep(land, vis, y - 1, x);
            deep(land, vis, y, x - 1);
            deep(land, vis, y - 1, x + 1);
        }
    }
}

展开全文 >>

部分排序

面试题 16.16. 部分排序

难度中等61

给定一个整数数组，编写一个函数，找出索引m和n，只要将索引区间[m,n]的元素排好序，整个数组就是有序的。注意：n-m尽量最小，也就是说，找出符合条件的最短序列。函数返回值为[m,n]，若不存在这样的m和n（例如整个数组是有序的），请返回[-1,-1]。

示例：

1
2
输入： [1,2,4,7,10,11,7,12,6,7,16,18,19]
输出： [3,9]

提示：

  • 0 <= len(array) <= 1000000

解题思路

  • 从左往右找逆序的最大值，最大值的位置就是无序的右边界

  • 从右往左找逆序的最小值，最小值的位置就是无需的左边界

菜鸡的写法

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
40
class Solution {
    public int[] subSort(int[] array) {
        if (array == null || array.length == 0) return new int[]{-1, -1};

        int len = array.length;

        int max = Integer.MIN_VALUE;
        boolean flag = false;
        // 从后往前找到逆序的最大值
        for (int i = len - 1; i > 0; i--) {
            if (array[i] < array[i - 1]) flag = true;
            if (flag) max = Math.max(max, array[i]);            
            //找逆序后的左边的最大值，最大值的位置即为无序的右边界
        }
        flag = false;
        int min = Integer.MAX_VALUE;
        // 从前往后找到逆序的最小值
        for (int i = 0; i < len - 1; i++) {
            if (array[i] > array[i + 1]) flag = true;
            if (flag) min = Math.min(min, array[i]);            
            //找逆序后的最小值，最小值的真正位置即为无序的左边界
        }

        int left = -1, right = -1;
        for (int i = 0; i < len; i++) {
            if (array[i] > min) {
                left = i;
                break;
            }
        }
        for (int i = len - 1; i >= 0; i--) {
            if (array[i] < max) {
                right = i;
                break;
            }
        }

        return new int[]{left, right};
    }
}

优雅的写法

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 {
    public int[] subSort(int[] array) {
        if(array == null || array.length == 0) return new int[]{-1, -1};
        int last = -1, first = -1;
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        int len = array.length;

        for(int i = 0; i < len; i++){
            if(array[i] < max){
                //如果当前数字小于目前遍历的最大值，说明他是逆序的，记录最后一个逆序的位置
                last = i;
            }else{
                max = Math.max(max, array[i]);
            }

            if(array[len - 1 - i] > min){                   
                //如果一个数字小于当前遍历到的最小值，说明他是逆序的，记录最前面的一个逆序的位置
                first = len - 1 - i;
            }else{
                min = Math.min(min, array[len - 1 - i]);
            }
        }
        return new int[] {first, last};
    }
}

作者：chen-wei-zhe
链接：https://leetcode-cn.com/problems/sub-sort-lcci/solution/yi-bian-bian-li-shuang-zhi-zhen-by-chen-wei-zhe/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

高效的写法

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 {
    public int[] subSort(int[] array) {
        if (array.length == 0) return new int[]{-1,-1};
        int start = 0;
        int max = array[0];
        int r = -1;
        for (int i = 1; i < array.length; i++) {
            if (array[i] >= max) {
                max = array[i];
            }else {
                r = i;
            }
        }

        int l = -1;
        int min = array[array.length - 1];
        for (int i =  array.length-1; i >= 0; i--) {
            if (array[i] <= min) {
                min = array[i];
            }else {
                l = i;
            }
        }
        return new int[]{l, r};
    }
}

作者：user0230C
链接：https://leetcode-cn.com/problems/sub-sort-lcci/solution/zui-hao-li-jie-de-fang-shi-ji-bai-bai-fen-zhi-99-b/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

最佳直线 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
给定一个二维平面及平面上的 N 个点列表Points，其中第i个点的坐标为Points[i]=[Xi,Yi]。请找出一条直线，其通过的点的数目最多。

设穿过最多点的直线所穿过的全部点编号从小到大排序的列表为S，你仅需返回[S[0],S[1]]作为答案，若有多条直线穿过了相同数量的点，则选择S[0]值较小的直线返回，S[0]相同则选择S[1]值较小的直线返回。

示例：

输入： [[0,0],[1,1],[1,0],[2,0]]
输出： [0,2]
解释： 所求直线穿过的3个点的编号为[0,2,3]
提示：

2 <= len(Points) <= 300
len(Points[i]) = 2
通过次数2,058提交次数3,966

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/best-line-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

向量共线的条件：

x1y2==x2y1

通过两点确定一条直线

1
2
3
A = Y2 - Y1
B = X1 - X2
C = X2Y1 - X1Y2

通过向量共线和一个公共点来判断第三个点是否在直线上

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
class Solution {
    public int[] bestLine(int[][] points) {
        int[] res = new int[2];
        int num = 0;
        int maxNum = 0;
        int len = points.length;

        for (int i = 0; i < points.length; i++) {
            for (int j = i + 1; j < len - 1; j++) {
                num = 2;
                if (len - 1 - j + 1 + 1 <= maxNum) break;//已经凑不够了，提前剪枝
                long x1 = points[j][0] - points[i][0];
                long y1 = points[j][1] - points[i][1];

                for (int k = j + 1; k < len; k++) {
                    long x2 = points[k][0] - points[i][0];
                    long y2 = points[k][1] - points[i][1];
                    if (x1 * y2 == x2 * y1) num++;      //满足向量共线的条件
                }
                if (num > maxNum) {
                    maxNum = num;
                    res[0] = i;
                    res[1] = j;
                }
            }
        }
        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
斐波那契数，通常用 F(n) 表示，形成的序列称为 斐波那契数列 。该数列由 0 和 1 开始，后面的每一项数字都是前面两项数字的和。也就是：

F(0) = 0，F(1) = 1
F(n) = F(n - 1) + F(n - 2)，其中 n > 1
给你 n ，请计算 F(n) 。

示例 1：

输入：2
输出：1
解释：F(2) = F(1) + F(0) = 1 + 0 = 1
示例 2：

输入：3
输出：2
解释：F(3) = F(2) + F(1) = 1 + 1 = 2
示例 3：

输入：4
输出：3
解释：F(4) = F(3) + F(2) = 2 + 1 = 3
 
提示：

0 <= n <= 30

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/fibonacci-number
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int fib(int n) {
        if (n < 2) return n;
        int first = 0, second = 1;
        int sum = 0;
        for (int i = 1; i < n; i++) {
            sum = first + second;
            first = second;
            second = sum;
        }
        return sum;
    }
}

avatar

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
class Solution {
    public int fib(int n) {
        if (n < 2) {
            return n;
        }
        int[][] q = {{1, 1}, {1, 0}};
        int[][] res = pow(q, n - 1);
        return res[0][0];
    }

    public int[][] pow(int[][] a, int n) {
        int[][] ret = {{1, 0}, {0, 1}};
        while (n > 0) {
            if ((n & 1) == 1) {
                ret = multiply(ret, a);
            }
            n >>= 1;
            a = multiply(a, a);
        }
        return ret;
    }

    public int[][] multiply(int[][] a, int[][] b) {
        int[][] c = new int[2][2];
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 2; j++) {
                c[i][j] = a[i][0] * b[0][j] + a[i][1] * b[1][j];
            }
        }
        return c;
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/fibonacci-number/solution/fei-bo-na-qi-shu-by-leetcode-solution-o4ze/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

avatar

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int fib(int n) {
        double sqrt5 = Math.sqrt(5);
        double fibN = Math.pow((1 + sqrt5) / 2, n) - Math.pow((1 - sqrt5) / 2, n);
        return (int) Math.round(fibN / sqrt5);
    }
}

作者：LeetCode-Solution
链接：https://leetcode-cn.com/problems/fibonacci-number/solution/fei-bo-na-qi-shu-by-leetcode-solution-o4ze/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

平分正方形 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
给定两个正方形及一个二维平面。请找出将这两个正方形分割成两半的一条直线。假设正方形顶边和底边与 x 轴平行。

每个正方形的数据square包含3个数值，正方形的左下顶点坐标[X,Y] = [square[0],square[1]]，以及正方形的边长square[2]。所求直线穿过两个正方形会形成4个交点，请返回4个交点形成线段的两端点坐标（两个端点即为4个交点中距离最远的2个点，这2个点所连成的线段一定会穿过另外2个交点）。2个端点坐标[X1,Y1]和[X2,Y2]的返回格式为{X1,Y1,X2,Y2}，要求若X1 != X2，需保证X1 < X2，否则需保证Y1 <= Y2。

若同时有多条直线满足要求，则选择斜率最大的一条计算并返回（与Y轴平行的直线视为斜率无穷大）。

示例：

输入：
square1 = {-1, -1, 2}
square2 = {0, -1, 2}
输出： {-1,0,2,0}
解释： 直线 y = 0 能将两个正方形同时分为等面积的两部分，返回的两线段端点为[-1,0]和[2,0]
提示：

square.length == 3
square[2] > 0
通过次数1,065提交次数2,565

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/bisect-squares-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
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
40
41
42
class Solution {
    public double[] cutSquares(int[] square1, int[] square2) {
        int x1 = square1[0];
        int y1 = square1[1];
        int len1 = square1[2];

        int x2 = square2[0];
        int y2 = square2[1];
        int len2 = square2[2];

        double cenX1 = x1 + len1 * 1.0 / 2;                                                             //计算正方形中心的坐标x
        double cenY1 = y1 + len1 * 1.0 / 2;                                                             //计算正方形中心的坐标y

        double cenX2 = x2 + len2 * 1.0 / 2;
        double cenY2 = y2 + len2 * 1.0 / 2;
                                                                                                        //统计边的最小值和最大值
        int xMin = Math.min(x1, x2), yMin = Math.min(y1, y2), xMax = Math.max(x1 + len1, x2 + len2), yMax = Math.max(y1 + len1, y2 + len2);

        double k = 1;
        if (Math.abs(cenX2 - cenX1) != 0) k = (cenY2 - cenY1) / (cenX2 - cenX1);
        else return new double[]{cenX1, yMin, cenX1, yMax};                                             //斜率无穷大
        if (k == 0) return new double[]{xMin, cenY1, xMax, cenY1};                                      //斜率为0

        double b = cenY1 - k * cenX1;                                                                   //y=kx+b求截距

        if (Math.abs(k) > 1) {                                                                          //如果k的绝对值大于1，与上下两个边相交，否则与左右两个边相交
            if((yMin - b) / k<(yMax - b) / k){
                return new double[]{(yMin - b) / k, (double) yMin, (yMax - b) / k, (double) yMax};
            }else{
                return new double[]{(yMax - b) / k, (double) yMax,(yMin - b) / k, (double) yMin};
            }
        } else if (Math.abs(k) < 1) {
            if((double) xMin<(double) xMax){
                return new double[]{(double) xMin, (k * xMin) + b, (double) xMax, (k * xMax) + b};
            }else{
                return new double[]{(double) xMax, (k * xMax) + b,(double) xMin, (k * xMin) + b};
            }
        } else {
            return new double[]{xMin, yMin, xMax, yMax};
        }
    }
}

展开全文 >>

拼车 

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
40
41
42
43
44
假设你是一位顺风车司机，车上最初有 capacity 个空座位可以用来载客。由于道路的限制，车 只能 向一个方向行驶（也就是说，不允许掉头或改变方向，你可以将其想象为一个向量）。

这儿有一份乘客行程计划表 trips[][]，其中 trips[i] = [num_passengers, start_location, end_location] 包含了第 i 组乘客的行程信息：

必须接送的乘客数量；
乘客的上车地点；
以及乘客的下车地点。
这些给出的地点位置是从你的 初始 出发位置向前行驶到这些地点所需的距离（它们一定在你的行驶方向上）。

请你根据给出的行程计划表和车子的座位数，来判断你的车是否可以顺利完成接送所有乘客的任务（当且仅当你可以在所有给定的行程中接送所有乘客时，返回 true，否则请返回 false）。

 

示例 1：

输入：trips = [[2,1,5],[3,3,7]], capacity = 4
输出：false
示例 2：

输入：trips = [[2,1,5],[3,3,7]], capacity = 5
输出：true
示例 3：

输入：trips = [[2,1,5],[3,5,7]], capacity = 3
输出：true
示例 4：

输入：trips = [[3,2,7],[3,7,9],[8,3,9]], capacity = 11
输出：true
 

提示：

你可以假设乘客会自觉遵守 “先下后上” 的良好素质
trips.length <= 1000
trips[i].length == 3
1 <= trips[i][0] <= 100
0 <= trips[i][1] < trips[i][2] <= 1000
1 <= capacity <= 100000
通过次数14,585提交次数24,148

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/car-pooling
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：不管上车人是谁，也不管下车人是谁，上车的时候加人，下车的时候减人。

然后遍历行程序列，对路途中的在行程中的人数计数，如果大于capacity就不能顺利接收

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean carPooling(int[][] trips, int capacity) {
        if (trips == null || trips.length == 0) return true;
        int[] pc = new int[1001];

        for (int i = 0; i < trips.length; i++) {
            pc[trips[i][1]] += trips[i][0];
            pc[trips[i][2]] -= trips[i][0];
        }

        int stay = 0;
        for (int i = 0; i < pc.length; i++) {
            stay += pc[i];
            if (stay > capacity) return false;
        }

        return true;
    }
}

展开全文 >>

生存人数 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
给定 N 个人的出生年份和死亡年份，第 i 个人的出生年份为 birth[i]，死亡年份为 death[i]，实现一个方法以计算生存人数最多的年份。

你可以假设所有人都出生于 1900 年至 2000 年（含 1900 和 2000 ）之间。如果一个人在某一年的任意时期处于生存状态，那么他应该被纳入那一年的统计中。例如，生于 1908 年、死于 1909 年的人应当被列入 1908 年和 1909 年的计数。

如果有多个年份生存人数相同且均为最大值，输出其中最小的年份。

示例：

输入：
birth = {1900, 1901, 1950}
death = {1948, 1951, 2000}
输出： 1901

提示：

0 < birth.length == death.length <= 10000
birth[i] <= death[i]
通过次数6,168提交次数8,986

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/living-people-lcci
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
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
class Solution {
    public int maxAliveYear(int[] birth, int[] death) {
        if (birth == null || death == null) return 0;

        Arrays.sort(birth);
        Arrays.sort(death);

        int[] arr = new int[birth.length];

        arr[0] = 1;
        for (int i = 1; i < birth.length; i++) {
            arr[i] = arr[i - 1] + 1;
        }

        int maxIndex = 0, maxVal = 0;

        for (int i = 0; i < death.length; i++) {
            int j = 0;
            while (j < death.length && birth[i] > death[j]) {
                arr[i]--;
                j++;
            }
            if (arr[i] > maxVal) {
                maxIndex = i;
                maxVal = arr[i];
            }
        }

        return birth[maxIndex];
    }
}

前缀和

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
class Solution {
    public int maxAliveYear(int[] birth, int[] death) {
		int[] lives = new int[102];
		for (int birthyear : birth)
			lives[birthyear - 1900]++;
		for (int deathyear : death)
			lives[deathyear - 1900 + 1]--;

		int[] preSum = new int[102];
		preSum[0] = lives[0];
		for (int i = 1; i < preSum.length; i++) {
			preSum[i] = lives[i] + preSum[i - 1];
		}

		int maxlives = -1;
		int minyear = 0;
		for (int i = 0; i < preSum.length; i++) {
			if (preSum[i] > maxlives) {
				minyear = i + 1900;
				maxlives = preSum[i];
			}
		}
		return minyear;
	}
}

作者：cjvv
链接：https://leetcode-cn.com/problems/living-people-lcci/solution/javaqian-zhui-he-by-cjvv/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int maxAliveYear(int[] birth, int[] death) {
        int[] changes = new int[102];
        int len = birth.length, res = 1900, max_alive = 0, cur_alive = 0;
        for (int i = 0; i < len; ++i) {
            ++changes[birth[i] - 1900];
            --changes[death[i] - 1899];
        }
        for (int i = 1; i < 101; ++i) {
            cur_alive += changes[i];
            if (cur_alive > max_alive) {
                max_alive = cur_alive;
                res = 1900 + i;
            }
        }
        return res;
    }
}
作者：gfu
链接：https://leetcode-cn.com/problems/living-people-lcci/solution/shu-zu-cun-chu-mei-nian-ren-shu-bian-hua-by-gfu/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

我是一只<br>又水又笨又菜的<br>菜狗子<br>希望有一天被领走