[Leetcode] 73, 134, 53

73. Set Matrix Zeroes

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place. Solution(1): 这道题要求找到0的元素，然后将它所在的行和列置0。这题的关键点是要求in-place操作，因此在进行置0之前必须将所有0元素的位置找到并加以记录，因此关键点是如何进行记录。 使用两个数组分别记录每个行是否要置0，每个列是否要置0，空间O(m+n)。 Code: class Solution { public: void setZeroes(vector<vector<int>>& matrix) { int m = matrix.size(); if(m==0) return; int n = matrix[0].size(); if(n==0) return; vector<bool> column(n,false); vector<bool> row(m,false); for(int i=0; i<m; i++){ for(int t=0; t<n; t++){ if(matrix[i][t]==0){ column[t] = true; row[i] = true; } } } for(int i=0; i<m; i++){ if(row[i]){ for(int t=0; t<n; t++) matrix[i][t] = 0; //fill(matrix[i].begin(),matrix[i].end(),0) } } for(int i=0; i<n; i++){ if(column[i]){ for(int t=0; t<m; t++) matrix[t][i] = 0; } } } }; Solution(2):复用第一行和第一列用来记录是否清零，空间O(1)。 注意corner case，容易写错！ class Solution { public: void setZeroes(vector<vector<int>>& matrix) { int m = matrix.size(); if(m==0) return; int n = matrix[0].size(); if(n==0) return; bool column0 = false; for(int i=0; i<m; i++){ if(matrix[i][0]==0){ column0 = true; } } bool row0 = false; for(int i=0; i<n; i++){ if(matrix[0][i]==0){ row0 = true; } } for(int i=1; i<m; i++){ for(int t=1; t<n; t++){ if(matrix[i][t]==0){ matrix[i][0] = 0; matrix[0][t] = 0; } } } for(int i=1; i<m; i++){ if(matrix[i][0]==0){ for(int t=1; t<n; t++) matrix[i][t] = 0; //fill(matrix[i].begin(),matrix[i].end(),0) } } for(int i=1; i<n; i++){ if(matrix[0][i]==0){ for(int t=1; t<m; t++) matrix[t][i] = 0; } } if(row0) for(int t=0; t<n; t++) matrix[0][t] = 0; if(column0) for(int t=0; t<m; t++) matrix[t][0] = 0; } };

134. Gas Station

There are N gas stations along a circular route, where the amount of gas at station i is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station's index if you can travel around the circuit once, otherwise return -1.

Note: The solution is guaranteed to be unique.

Solution(1): 最直接的思路是对于每个点都测试一下是否能够作为起点，时间复杂度为O(n^2)，但是这样做会超时。

因此对于这种解法稍微做点优化，增加排除条件，降低遍历次数：

1、当经过该点会损失油的时候（gas[i]-cost[i]<0），该点一定不是起点；

2、前一个点为非损失油点且非起点的点，一定不是起点。

class Solution { public: int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { for(int i=0; i<gas.size(); i++){ gas[i] = gas[i] - cost[i]; } for(int i=0; i<gas.size(); ){ if(gas[i]>=0){ if(testStartPoint(i,gas)) return i; else{ for(int t=i+1; t<gas.size(); t++){ if(gas[t]<0){ i = t; break; } } if(gas[i]>=0) i = gas.size(); } }else{ i++; } } return -1; } private: bool testStartPoint(int n,vector<int>& gas){ int gasVolumn = 0; int i = n; int size = gas.size(); do{ gasVolumn = gasVolumn + gas[i]; if(gasVolumn<0) return false; i = (i+1)%size; }while(i!=n); return true; } }; Solution(2):如果走完整个路程，剩下的油量为负数（sum(gas[i]-cost[i])），那么一定无解。如果剩余油量大于等于0，当求和时每次遇到出现负数的情况，就将前面的点都放到末尾，以下一位为开头，因为最后总和大于等于0，则前面所有的路程走完之后，走到新的末尾点时，每个点的油量也是非负数。

像这样，使用几个数，记录下当前的信息，压缩遍历的次数是数组题中的常用做法。

Code:

class Solution { public: int canCompleteCircuit(vector<int>& gas, vector<int>& cost) { if(gas.size()==0) return -1;//注意 int sum = 0; int total = 0; int start = 0; for(int i=0; i<gas.size(); i++){ sum += gas[i] - cost[i]; total += gas[i] - cost[i]; if(sum<0){ start = i+1; sum = 0; } } if(total<0) return -1; else return start; } }; 类似的问题有LC53.maximum subarray

53. Maximum Subarray

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4], the contiguous subarray [4,-1,2,1] has the largest sum = 6.

Solution: 假设对于a 0 -a i ，已知最大值，当a i+1 加入到数组中时，最大值就变成了max(max i ,a i+1 ,a i+1 -min i )。其中ai+1-mini表示以ai+1作为最后一个数的子数组的最大和。 Code: class Solution { public:     int maxSubArray(vector<int>& nums) {         int MIN = 0;          int MAX = nums[0];          int total = nums[0];         for(int i=1; i<nums.size(); i++){             MIN = min(MIN, total);             MAX = max(MAX, nums[i]+total-MIN);              total += nums[i];         }         return MAX;     } };