【每日算法Day 17】数组基础3

今天的几道题和数组本身性质和操作关系不大，更多的是针对问题本身给出只需要一次遍历的具体算法，以及将数组用作动态规划的容器。

# LeetCode 134. 加油站 (opens new window)

# 题目描述

在一条环路上有 N 个加油站，其中第 i 个加油站有汽油 gas[i] 升。

你有一辆油箱容量无限的的汽车，从第 i 个加油站开往第 i+1 个加油站需要消耗汽油 cost[i] 升。你从其中的一个加油站出发，开始时油箱为空。

如果你可以绕环路行驶一周，则返回出发时加油站的编号，否则返回 -1。

说明:

如果题目有解，该答案即为唯一答案。
输入数组均为非空数组，且长度相同。
输入数组中的元素均为非负数。

# 示例

输入: 
gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]

输出: 3

解释:
从 3 号加油站(索引为 3 处)出发，可获得 4 升汽油。此时油箱有 = 0 + 4 = 4 升汽油
开往 4 号加油站，此时油箱有 4 - 1 + 5 = 8 升汽油
开往 0 号加油站，此时油箱有 8 - 2 + 1 = 7 升汽油
开往 1 号加油站，此时油箱有 7 - 3 + 2 = 6 升汽油
开往 2 号加油站，此时油箱有 6 - 4 + 3 = 5 升汽油
开往 3 号加油站，你需要消耗 5 升汽油，正好足够你返回到 3 号加油站。
因此，3 可为起始索引。

1
2
3
4
5
6
7
8
9
10
11
12
13
14

# 解题思路

暴力法直接遍历从每个加油站出发，查看能不能行得通，就不赘述了。

个人感觉官方的反证法不是很好理解，下面给出我的思路。考虑从每个加油站出发，要到达下一个加油站至少需要车子已有油多少升。以示例为例：

gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]

1
2

记tmpCost[i]=cost[i]-gas[i]，那么我们就能得到

tmpCost=[2,2,2,-3,-3]

其中负数表示加油站能额外提供给车子的油量，显然当tmpCost的总和小于等于0时有解，否则无解（因为整个过程中车子自己不能变出油来）。在一遍扫描的过程中使用一个变量totalCost存储tmpCost[i]的和就可以了（并不需要建立该O(n)大小的数组，上面的数组只是为了便于说明）。

下面要找到开始出发点，假设出发点为startIndex，当前位置为i，则一旦[startIndex,i]区间中所有的tmpCost之和大于0，说明汽车走不下去了。使用一个变量startToCurrentCost来保存这个值，当汽车走到当前位置走不下去时，重置startIndex为i+1、startToCurrentCost为0。

当最终遍历完，并且totalCost<0时，startIndex就是始发加油站，否则无解返回-1。

public int canCompleteCircuit(int[] gas, int[] cost) {
    int totalCost=0,startIndex=0,startToCurrentCost=0;
    for(int i=0;i<gas.length;i++){
        //tmpCost表示从当前加油站到达下一个加油站至少需要汽车已有油多少升
        int tmpCost=cost[i]-gas[i];
        totalCost+=tmpCost;
        startToCurrentCost+=tmpCost;

        //如果该值大于零，则重置始发站为下一站点，重置startToCurrentCost为0
        if (startToCurrentCost > 0) {
            startIndex = i + 1;
            startToCurrentCost = 0;
        }
    }
    if(totalCost<=0)
        return startIndex;
    else
        return -1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

关于startToCurrentCost的值重置的说明：

如果始发站的tmpCost>0则直接不满足条件，此时i=startIndex则startIndex+=1从下一点开始继续找，只有tmpCost<=0的点才有可能是始发站。
当以tmpCost<=0的点开头并扫描了一定长度到达i后发现startToCurrentCost[startIndex,i]>0，而对于[startIndex,i）区间中任何一点j，由于都有startToCurrentCost[startIndex,j]<=0，则找不到任意一个j为新的startIndex使得startToCurrentCost[j,i]<=0。所以把startIndex重置为i+1。

该算法只扫描一遍数组，用到了常量级的额外空间，时间复杂度为O(n)，空间复杂度为O(1)。

P.S. 执行用时0ms，内存消耗39.8MB，很奇怪明明是O(1)空间复杂度但在所有Java提交中只击败了5.88%的用户，不知道其他大佬是怎么再减少内存消耗的2333，欢迎交流。

# LeetCode 118. 杨辉三角

# 题目描述

给定一个非负整数 numRows，生成杨辉三角的前 numRows 行。

# 解题思路

杨辉三角边缘的数都为1，从第三层开始，非边缘的点下标若为i，则其值由上层下标为i-1和i的数相加而得，显然这是个动态规划的问题。题目本身也要求返回的是动态规划用到的DP数组本身。

杨辉三角的数组下标相加关系
      0
    0   1
  0   1   2
0   1   2   3

1
2
3
4
5

public List<List<Integer>> generate(int numRows) {
    List<List<Integer>> list = new ArrayList<>();
    //行从1开始计，第i行有i个数（也可以从0开始计）
    for (int i = 1; i <= numRows; i++) {
        List<Integer> subList = new ArrayList<>();
        for (int j = 0; j < i; j++) {
            if (j == 0 || j == i - 1) {
                subList.add(1);
            } else {
                subList.add(list.get(i-2).get(j)+list.get(i-2).get(j-1));
            }
        }
        list.add(subList);
    }
    return list;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

时间复杂度和空间复杂度都为O(numRows^2)O(numRows^2)。

扩展：给定一个非负索引 k，其中 k ≤ 33，返回杨辉三角的第 k 行。可以使用上面的算法，还可以进一步将空间复杂度优化到O(k) 。每次从倒数第二个元素开始往前更新它等于原来这个位置的数 + 前一个位置的数，对右边元素的覆盖不会影响到左侧元素的计算。

# LeetCode 169. 多数元素 (opens new window)

# 题目描述

给定一个大小为 n 的数组，找到其中的多数元素。多数元素是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。

你可以假设数组是非空的，并且给定的数组总是存在多数元素。

# 解题思路

暴力法、排序法和哈希表的方法就不说了，有一种Boyer-Moore 投票算法。其核心是多数元素对统计的影响一定过半。时间复杂度为O(n)，空间复杂度为O(1)。

public int majorityElement(int[] nums) {
    int count = 0, currentMajority = nums[0];
    for (int i = 1; i < nums.length; i++) {
        if (count <= 0)
            currentMajority = nums[i];
        count += (nums[i] == currentMajority) ? 1 : -1;
    }
    return currentMajority;
}

1
2
3
4
5
6
7
8
9

Wallace's Blog

Choose mode