1390. Four Divisors

Given an integer array nums, return the sum of divisors of the integers in that array that have exactly four divisors.

If there is no such integer in the array, return 0.

Example 1:

Input: nums = [21,4,7]
Output: 32
Explanation:
21 has 4 divisors: 1, 3, 7, 21
4 has 3 divisors: 1, 2, 4
7 has 2 divisors: 1, 7
The answer is the sum of divisors of 21 only.

Constraints:

• 1 <= nums.length <= 10^4
• 1 <= nums[i] <= 10^5

给定一个数组，问其中哪些数只有4个因子，把只有4个因子的数对应的所有因子加起来。

也是很无聊的一个题，按题意照做即可，注意求解因子的时候只需要循环到sqrt(v)即可，因为如果一个因子大于sqrt(v)的话，其对应的另一个因子肯定小于sqrt(v)，也就是之前已经遍历过了。

完整代码如下：

class Solution {
public:
	void FindDivisors(int v, vector<int>& ans) {
		int mid = sqrt(v);
		for (int i = 1; i <= mid; ++i) {
			if (v%i == 0) {
				ans.push_back(i);
				if (v / i != i)ans.push_back(v / i);
			}
		}
	}
	int sumFourDivisors(vector<int>& nums) {
		int ans = 0;
		for (int i = 0; i < nums.size(); ++i) {
			vector<int> divs;
			FindDivisors(nums[i], divs);
			if (divs.size() == 4) {
				for (int j = 0; j < divs.size(); ++j)ans += divs[j];
			}
		}
		return ans;
	}
};

本代码提交AC，用时440MS。

1389. Create Target Array in the Given Order

Given two arrays of integers nums and index. Your task is to create target array under the following rules:

• Initially target array is empty.
• From left to right read nums[i] and index[i], insert at index index[i] the value nums[i] in target array.
• Repeat the previous step until there are no elements to read in nums and index.

Return the target array.

It is guaranteed that the insertion operations will be valid.

Example 1:

Input: nums = [0,1,2,3,4], index = [0,1,2,2,1]
Output: [0,4,1,3,2]
Explanation:
nums       index     target
0            0        [0]
1            1        [0,1]
2            2        [0,1,2]
3            2        [0,1,3,2]
4            1        [0,4,1,3,2]

Example 2:

Input: nums = [1,2,3,4,0], index = [0,1,2,3,0]
Output: [0,1,2,3,4]
Explanation:
nums       index     target
1            0        [1]
2            1        [1,2]
3            2        [1,2,3]
4            3        [1,2,3,4]
0            0        [0,1,2,3,4]

Example 3:

Input: nums = [1], index = [0]
Output: [1]

Constraints:

• 1 <= nums.length, index.length <= 100
• nums.length == index.length
• 0 <= nums[i] <= 100
• 0 <= index[i] <= i

很无聊的一个题。给定一个值数组nums，和一个下标数组index，表示数nums[i]插入到index[i]所在位置。有可能多个数插入到同一个位置了，此时先插入的数要往后挪。

很无聊的一个题，模拟题意照做即可，完整代码如下：

class Solution {
public:
	vector<int> createTargetArray(vector<int>& nums, vector<int>& index) {
		int n = nums.size();
		vector<int> ans;
		for (int i = 0; i < n; ++i) {
			ans.insert(ans.begin() + index[i], nums[i]);
		}
		return ans;
	}
};

本代码提交AC，用时0MS。

34. Find First and Last Position of Element in Sorted Array

Given an array of integers nums sorted in ascending order, find the starting and ending position of a given target value.

Your algorithm’s runtime complexity must be in the order of O(log n).

If the target is not found in the array, return [-1, -1].

Example 1:

Input: nums = [5,7,7,8,8,10], target = 8
Output: [3,4]

Example 2:

Input: nums = [5,7,7,8,8,10], target = 6
Output: [-1,-1]

给定一个有序数组，里面可能有重复元素，要求找出某个元素所有出现位置的起始位置和终止位置。

由于是有序数组，所以直接二分搜索，需要注意的是如果是找起始位置，则找到目标元素后还应该继续往左找，可以想象mid一直遇到target，则要不断执行r=mid-1，直到退出while循环，此时老的mid是等于target的最小下标，所以要返回r+1。类似的，如果找终止位置，则遇到相等后还要继续往右找，即l=mid+1，失败的时候返回上一个mid，即l-1。

完整代码如下：

class Solution {
public:
	int FindFirstIndex(vector<int>& nums, int target) {
		int l = 0, r = nums.size() - 1;
		while (l <= r) {
			int mid = l + (r - l) / 2;
			if (target <= nums[mid])r = mid - 1;
			else l = mid + 1;
		}
		if (r + 1 < nums.size() && nums[r + 1] == target)return r + 1;
		else return -1;
	}
	int FindLastIndex(vector<int>& nums, int target) {
		int l = 0, r = nums.size() - 1;
		while (l <= r) {
			int mid = l + (r - l) / 2;
			if (target >= nums[mid])l = mid + 1;
			else r = mid - 1;
		}
		if (l - 1 >= 0 && nums[l - 1] == target)return l - 1;
		else return -1;
	}
	vector<int> searchRange(vector<int>& nums, int target) {
		return { FindFirstIndex(nums,target),FindLastIndex(nums,target) };
	}
};

本代码提交AC，用时4MS。

1383. Maximum Performance of a Team

There are n engineers numbered from 1 to n and two arrays: speed and efficiency, where speed[i] and efficiency[i] represent the speed and efficiency for the i-th engineer respectively. Return the maximum performance of a team composed of at most k engineers, since the answer can be a huge number, return this modulo 10^9 + 7.

The performance of a team is the sum of their engineers’ speeds multiplied by the minimum efficiency among their engineers. 

Example 1:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 2
Output: 60
Explanation: 
We have the maximum performance of the team by selecting engineer 2 (with speed=10 and efficiency=4) and engineer 5 (with speed=5 and efficiency=7). That is, performance = (10 + 5) * min(4, 7) = 60.

Example 2:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 3
Output: 68
Explanation:
This is the same example as the first but k = 3. We can select engineer 1, engineer 2 and engineer 5 to get the maximum performance of the team. That is, performance = (2 + 10 + 5) * min(5, 4, 7) = 68.

Example 3:

Input: n = 6, speed = [2,10,3,1,5,8], efficiency = [5,4,3,9,7,2], k = 4
Output: 72

Constraints:

• 1 <= n <= 10^5
• speed.length == n
• efficiency.length == n
• 1 <= speed[i] <= 10^5
• 1 <= efficiency[i] <= 10^8
• 1 <= k <= n

给定n个工程师，每个工程师有自己的速度值speed和效率值efficiency，一个包含k个工程师的团队的总体performance等于所有工程师的速度之和乘以最小效率：sum(speed)*min(efficiency)。问最多选k个工程师，最大的performance是多少。

我一开始被“最多k个”迷惑了，一直以为是一个DP题，后来看题解发现不是。

由于performance=sum(speed)*min(efficiency)，所以首先对n个工程师按efficiency从大到小排序，然后对于前m个工程师，他们的最小efficiency就是当前遍历到的第m个工程师的efficiency。如果m已经超过k，则需要从m个工程师中剔除掉速度最小的工程师，因为此时的min(efficiency)固定是第m个工程师的efficiency，所以只需要剔除速度低的工程师。

那么，如果最优解是少于k个人，这种方法能否找到最优解呢？其实是可以的，因为对于每加入一个工程师，我们都会和当前最优解对比，刚开始的时候，队列中的人数肯定少于k。

完整代码如下：

class Solution {
public:
	int maxPerformance(int n, vector<int>& speed, vector<int>& efficiency, int k) {
		vector<pair<int, int>> workers;
		for (int i = 0; i < n; ++i) {
			workers.push_back(make_pair(efficiency[i], speed[i]));
		}
		sort(workers.begin(), workers.end()); // 默认对pair.first升序排列
		priority_queue <int, vector<int>, greater<int> > pq; // pq默认是最大堆，这是构建最小堆
		long long ans = 0;
		long long sum_speed = 0;
		for (int i = n - 1; i >= 0; --i) {
			sum_speed += workers[i].second;
			pq.push(workers[i].second);
			if (pq.size() > k) {
				sum_speed -= pq.top();
				pq.pop();
			}
			ans = max(ans, sum_speed*workers[i].first);
		}
		return ans % (int)(1e9 + 7);
	}
};

本代码提交AC，用时108MS。

1381. Design a Stack With Increment Operation

Design a stack which supports the following operations.

Implement the CustomStack class:

• CustomStack(int maxSize) Initializes the object with maxSize which is the maximum number of elements in the stack or do nothing if the stack reached the maxSize.
• void push(int x) Adds x to the top of the stack if the stack hasn’t reached the maxSize.
• int pop() Pops and returns the top of stack or -1 if the stack is empty.
• void inc(int k, int val) Increments the bottom k elements of the stack by val. If there are less than k elements in the stack, just increment all the elements in the stack.

Example 1:

Input
["CustomStack","push","push","pop","push","push","push","increment","increment","pop","pop","pop","pop"]
[[3],[1],[2],[],[2],[3],[4],[5,100],[2,100],[],[],[],[]]
Output
[null,null,null,2,null,null,null,null,null,103,202,201,-1]
Explanation
CustomStack customStack = new CustomStack(3); // Stack is Empty []
customStack.push(1);                          // stack becomes [1]
customStack.push(2);                          // stack becomes [1, 2]
customStack.pop();                            // return 2 --> Return top of the stack 2, stack becomes [1]
customStack.push(2);                          // stack becomes [1, 2]
customStack.push(3);                          // stack becomes [1, 2, 3]
customStack.push(4);                          // stack still [1, 2, 3], Don't add another elements as size is 4
customStack.increment(5, 100);                // stack becomes [101, 102, 103]
customStack.increment(2, 100);                // stack becomes [201, 202, 103]
customStack.pop();                            // return 103 --> Return top of the stack 103, stack becomes [201, 202]
customStack.pop();                            // return 202 --> Return top of the stack 102, stack becomes [201]
customStack.pop();                            // return 201 --> Return top of the stack 101, stack becomes []
customStack.pop();                            // return -1 --> Stack is empty return -1.

Constraints:

• 1 <= maxSize <= 1000
• 1 <= x <= 1000
• 1 <= k <= 1000
• 0 <= val <= 100
• At most 1000 calls will be made to each method of increment, push and pop each separately.

设计一个栈Stack的数据结构，简单题，使用vector模拟。完整代码如下：

class CustomStack {
private:
	vector<int> container;
	int msz;
public:
	CustomStack(int maxSize) {
		msz = maxSize;
	}

	void push(int x) {
		if (container.size() < msz) {
			container.push_back(x);
		}
	}

	int pop() {
		if (container.size() > 0) {
			int val = container[container.size() - 1];
			container.pop_back();
			return val;
		}
		else {
			return -1;
		}
	}

	void increment(int k, int val) {
		for (int i = 0; i < k&&i < container.size(); ++i) {
			container[i] += val;
		}
	}
};

本代码提交AC，用时40MS。

1380. Lucky Numbers in a Matrix

Given a m * n matrix of distinct numbers, return all lucky numbers in the matrix in any order.

A lucky number is an element of the matrix such that it is the minimum element in its row and maximum in its column.

Example 1:

Input: matrix = [[3,7,8],[9,11,13],[15,16,17]]
Output: [15]
Explanation: 15 is the only lucky number since it is the minimum in its row and the maximum in its column

Example 2:

Input: matrix = [[1,10,4,2],[9,3,8,7],[15,16,17,12]]
Output: [12]
Explanation: 12 is the only lucky number since it is the minimum in its row and the maximum in its column.

Example 3:

Input: matrix = [[7,8],[1,2]]
Output: [7]

Constraints:

• m == mat.length
• n == mat[i].length
• 1 <= n, m <= 50
• 1 <= matrix[i][j] <= 10^5.
• All elements in the matrix are distinct.

给定一个没有重复元素的矩阵，要求找出矩阵中的幸运数字，幸运数字的定义是它是所在行的最小值且是所在列的最大值。

有点意思的题目，如果暴力解法，遍历每个元素，同时判断它是否是所在行最小值且所在列最大值的话，时间复杂度高达$O((mn)^2)$，不可取。

更好的方法是，在遍历的过程中，记录当前行的最小值即当前列的最大值，最后判断一下最小值的数组和最大值的数组是否有相等元素，如果有的话，说明这个数是所在行的最小值且是所在列的最大值。可以这样做的原因是矩阵中没有重复元素。

完整代码如下：

class Solution {
public:
	vector<int> luckyNumbers(vector<vector<int>>& matrix) {
		vector<int> ans;
		int m = matrix.size(), n = matrix[0].size();
		vector<int> rowmin(m, INT_MAX), colmax(n, INT_MIN);
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j) {
				rowmin[i] = min(rowmin[i], matrix[i][j]);
				colmax[j] = max(colmax[j], matrix[i][j]);
			}
		}
		for (int i = 0; i < m; ++i) {
			for (int j = 0; j < n; ++j) {
				if (rowmin[i] == colmax[j])ans.push_back(rowmin[i]);
			}
		}
		return ans;
	}
};

本代码提交AC，用时24MS。