Tag Archives: 数组

LeetCode Maximum Sum Circular Subarray

918. Maximum Sum Circular Subarray

Given a circular array C of integers represented by A, find the maximum possible sum of a non-empty subarray of C.

Here, a circular array means the end of the array connects to the beginning of the array.  (Formally, C[i] = A[i] when 0 <= i < A.length, and C[i+A.length] = C[i] when i >= 0.)

Also, a subarray may only include each element of the fixed buffer A at most once.  (Formally, for a subarray C[i], C[i+1], ..., C[j], there does not exist i <= k1, k2 <= j with k1 % A.length = k2 % A.length.)

Example 1:

Input: [1,-2,3,-2]
Output: 3
Explanation: Subarray [3] has maximum sum 3

Example 2:

Input: [5,-3,5]
Output: 10
Explanation: Subarray [5,5] has maximum sum 5 + 5 = 10

Example 3:

Input: [3,-1,2,-1]
Output: 4
Explanation: Subarray [2,-1,3] has maximum sum 2 + (-1) + 3 = 4

Example 4:

Input: [3,-2,2,-3]
Output: 3
Explanation: Subarray [3] and [3,-2,2] both have maximum sum 3

Example 5:

Input: [-2,-3,-1]
Output: -1
Explanation: Subarray [-1] has maximum sum -1

Note:

  1. -30000 <= A[i] <= 30000
  2. 1 <= A.length <= 30000

给定一个循环数组,即数组的最后一个和数字第一个连起来了。求循环数组的最大连续子数组和。

LeetCode Maximum Subarray的升级版,即数组首尾相连了。我一开始想到的解法是,既然数组首尾相连了,那就2*n次dp即可,即把原数组复制一遍,接到原数组后面,形成2*n长的数组,然后照样跑原来的DP算法。这个解法是不对的,比如如果数组是[1,2,3,4]这种全是正数,则跑2n遍之后,ans会一直max更新,导致最后的ans是1+…+4+1+…4,即数组加了两遍,每个数重复加了。另外对于数组[5,-3,5]这种,也会完整数组加两遍。

正确解法是,分两种情况,第一种情况是最大子串和没有跨越首尾,则使用常规DP即可求解。第二种情况是,最大子串和跨越了首尾,则可以把问题转化为求原数组的最小连续子串和,然后用数组总和减去最小连续子串和,就能得到跨越首尾的最大连续子串和。在求解第二种情况时,需要注意如果最小连续子串和是整个数组的情况,比如数组都是负数[-1,-2,-3],则求到的最小连续子串和是整个数组[-1,-2,-3],用数组总和一减变成了空集和为0,但最大连续子串和至少需要1个元素,对于这种情况,丢弃case2的解。

完整代码如下:

class Solution {
public:
    int maxSubarraySumCircular(vector<int>& A) {
        int n = A.size();
        vector<int> dp(n, 0);
        
        // 最大连续子串
        dp[0] = A[0];
        int ans1 = A[0], sum = A[0];
        for(int i = 1; i < n; ++i) {
            dp[i] = max(dp[i - 1], 0) + A[i];
            ans1 = max(ans1, dp[i]);
            
            sum += A[i];
        }
        
        // 最小连续子串
        fill(dp.begin(), dp.end(), 0);
        dp[0] = A[0];
        int ans2 = A[0];
        for(int i = 1; i < n; ++i) {
            dp[i] = min(dp[i - 1], 0) + A[i];
            ans2 = min(ans2, dp[i]);
        }
        
        if(ans2 == sum) ans2 = INT_MIN; // 注意最小连续子串和不能是全长数组
        else ans2 = sum - ans2;
        
        return max(ans1, ans2);
    }
};

本代码提交AC,用时252MS。

LeetCode Number of Good Pairs

1512. Number of Good Pairs

Given an array of integers nums.

A pair (i,j) is called good if nums[i] == nums[j] and i < j.

Return the number of good pairs.

Example 1:

Input: nums = [1,2,3,1,1,3]
Output: 4
Explanation: There are 4 good pairs (0,3), (0,4), (3,4), (2,5) 0-indexed.

Example 2:

Input: nums = [1,1,1,1]
Output: 6
Explanation: Each pair in the array are good.

Example 3:

Input: nums = [1,2,3]
Output: 0

Constraints:

  • 1 <= nums.length <= 100
  • 1 <= nums[i] <= 100

直接按题意做就行:

class Solution {
public:
	int numIdenticalPairs(vector<int>& nums) {
		int ans = 0, n = nums.size();
		for (int i = 0; i < n; ++i) {
			for (int j = i + 1; j < n; ++j) {
				if (nums[i] == nums[j])++ans;
			}
		}
		return ans;
	}
};

本代码提交AC,用时8MS。

剑指 Offer 06. 从尾到头打印链表

剑指 Offer 06. 从尾到头打印链表

输入一个链表的头节点,从尾到头反过来返回每个节点的值(用数组返回)。

示例 1:

输入:head = [1,3,2]
输出:[2,3,1]
 

限制:

0 <= 链表长度 <= 10000

来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/cong-wei-dao-tou-da-yin-lian-biao-lcof
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。


给定一个单链表,从尾到头打印链表的值。先顺序遍历链表,将结果存到一个数组中,然后逆序数组。代码如下:

class Solution {
public:
    vector<int> reversePrint(ListNode* head) {
        if(head == NULL) return {};
        vector<int> ans;
        while(head != NULL) {
            ans.push_back(head->val);
            head = head->next;
        }
        int i = 0, j = ans.size() - 1;
        while(i < j) {
            swap(ans[i++], ans[j--]);
        }
        return ans;
    }
};

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

Leetcode Running Sum of 1d Array

5453. Running Sum of 1d Array

Given an array nums. We define a running sum of an array as runningSum[i] = sum(nums[0]…nums[i]).

Return the running sum of nums.

Example 1:

Input: nums = [1,2,3,4]
Output: [1,3,6,10]
Explanation: Running sum is obtained as follows: [1, 1+2, 1+2+3, 1+2+3+4].

Example 2:

Input: nums = [1,1,1,1,1]
Output: [1,2,3,4,5]
Explanation: Running sum is obtained as follows: [1, 1+1, 1+1+1, 1+1+1+1, 1+1+1+1+1].

Example 3:

Input: nums = [3,1,2,10,1]
Output: [3,4,6,16,17]

Constraints:

  • 1 <= nums.length <= 1000
  • -10^6 <= nums[i] <= 10^6

给定一个数组,求出数组的前缀和。简单题,代码如下:

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

本代码提交AC,用时12MS。

LCP 06. 拿硬币

LCP 06. 拿硬币

桌上有 n 堆力扣币,每堆的数量保存在数组 coins 中。我们每次可以选择任意一堆,拿走其中的一枚或者两枚,求拿完所有力扣币的最少次数。

示例 1:

输入:[4,2,1]

输出:4

解释:第一堆力扣币最少需要拿 2 次,第二堆最少需要拿 1 次,第三堆最少需要拿 1 次,总共 4 次即可拿完。

示例 2:

输入:[2,3,10]

输出:8

限制:

  • 1 <= n <= 4
  • 1 <= coins[i] <= 10

有一个硬币数组,每次可以拿1枚或2枚,问最少拿多少次可以拿完。

简单题,贪心,每次拿2枚。完整代码如下:

class Solution {
public:
	int minCount(vector<int>& coins) {
		int ans = 0;
		for (int i = 0; i < coins.size(); ++i) {
			ans += (coins[i] / 2);
			if (coins[i] % 2 == 1)++ans;
		}
		return ans;
	}
};

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

LeetCode Count Number of Teams

1395. Count Number of Teams

There are n soldiers standing in a line. Each soldier is assigned a unique rating value.

You have to form a team of 3 soldiers amongst them under the following rules:

  • Choose 3 soldiers with index (ijk) with rating (rating[i]rating[j]rating[k]).
  • A team is valid if:  (rating[i] < rating[j] < rating[k]) or (rating[i] > rating[j] > rating[k]) where (0 <= i < j < k < n).

Return the number of teams you can form given the conditions. (soldiers can be part of multiple teams).

Example 1:

Input: rating = [2,5,3,4,1]
Output: 3
Explanation: We can form three teams given the conditions. (2,3,4), (5,4,1), (5,3,1). 

Example 2:

Input: rating = [2,1,3]
Output: 0
Explanation: We can't form any team given the conditions.

Example 3:

Input: rating = [1,2,3,4]
Output: 4

Constraints:

  • n == rating.length
  • 1 <= n <= 200
  • 1 <= rating[i] <= 10^5

给定一个数组,要求找出这样的升序或者降序的三元组数目。

竞赛阶段,由于n的范围较小,首先尝试暴力O(n^3)解法,代码如下:

class Solution {
public:
	int numTeams(vector<int>& rating) {
		int ans = 0, n = rating.size();
		for (int i = 0; i < n; ++i) {
			for (int j = i + 1; j < n; ++j) {
				for (int k = j + 1; k < n; ++k) {
					if (rating[i] < rating[j] && rating[j] < rating[k])++ans;
					else if (rating[i] > rating[j] && rating[j] > rating[k])++ans;
				}
			}
		}
		return ans;
	}
};

本代码提交AC,用时204MS。

还有更优的O(n^2)的解法。对于每个士兵,统计其左边小于它的数目,和右边大于它的数目,则这两个数相乘即为该士兵能组成的升序数目,类似的可以算到该士兵能组成的降序数目。代码如下:

class Solution {
public:
	int numTeams(vector<int>& rating) {
		int ans = 0, n = rating.size();
		for (int i = 1; i < n - 1; ++i) {
			vector<int> less_num(2, 0), greater_num(2, 0);
			for (int j = 0; j < n; ++j) {
				if (rating[j] < rating[i])++less_num[j < i];
				else if (rating[j] > rating[i])++greater_num[j > i];
			}
			ans += less_num[1] * greater_num[1] + less_num[0] * greater_num[0];
		}
		return ans;
	}
};

本代码提交AC,用时12MS。

LeetCode Create Target Array in the Given Order

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。

LeetCode Lucky Numbers in a Matrix

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。

LeetCode Bulb Switcher III

1375. Bulb Switcher III

There is a room with n bulbs, numbered from 1 to n, arranged in a row from left to right. Initially, all the bulbs are turned off.

At moment k (for k from 0 to n - 1), we turn on the light[k] bulb. A bulb change color to blue only if it is on and all the previous bulbs (to the left) are turned on too.

Return the number of moments in which all turned on bulbs are blue.

Example 1:

Input: light = [2,1,3,5,4]
Output: 3
Explanation: All bulbs turned on, are blue at the moment 1, 2 and 4.

Example 2:

Input: light = [3,2,4,1,5]
Output: 2
Explanation: All bulbs turned on, are blue at the moment 3, and 4 (index-0).

Example 3:

Input: light = [4,1,2,3]
Output: 1
Explanation: All bulbs turned on, are blue at the moment 3 (index-0).
Bulb 4th changes to blue at the moment 3.

Example 4:

Input: light = [2,1,4,3,6,5]
Output: 3

Example 5:

Input: light = [1,2,3,4,5,6]
Output: 6

Constraints:

  • n == light.length
  • 1 <= n <= 5 * 10^4
  • light is a permutation of  [1, 2, ..., n]

Discuss


这道题有点意思。给定n个灯泡,如果某个灯泡及其左边的所有灯泡都亮着,则这个灯泡会变成蓝色。刚开始时所有灯泡都是关着的,现在会进行n次开灯的操作,但开灯的顺序不确定。问有多少次开灯操作会使得亮着的所有灯都是蓝色的。

描述起来有点绕,大家看看题目中的示意图就很清楚了。

暴力解法是每开一次灯,都遍历其左边所有灯是否都亮着,时间复杂度是O(n^2),我估计会TLE,我没试过。

我的O(n)的方法如下。在开灯的过程中,记录当前开过的灯的最大编号max_id,同时记录目前已经亮着的灯的数目n。如果max_id==n,则此次开灯操作能使得亮着的灯都变成蓝色。举个例子,如果max_id==n==5,说明目前亮着5盏灯,且这5盏灯的最大编号是5,那说明其余亮着的灯的编号肯定是1,2,3,4,所以这5盏灯都会变成蓝色。

完整代码如下:

class Solution {
public:
	int numTimesAllBlue(vector<int>& light) {
		int ans = 0;
		int curmax = 0;
		for (int i = 0; i < light.size(); ++i) {
			curmax = max(curmax, light[i]);
			if (curmax == i + 1)++ans;
		}
		return  ans;
	}
};

本代码提交AC,用时112MS。

LeetCode Print Binary Tree

655. Print Binary Tree

Print a binary tree in an m*n 2D string array following these rules:

  1. The row number m should be equal to the height of the given binary tree.
  2. The column number n should always be an odd number.
  3. The root node’s value (in string format) should be put in the exactly middle of the first row it can be put. The column and the row where the root node belongs will separate the rest space into two parts (left-bottom part and right-bottom part). You should print the left subtree in the left-bottom part and print the right subtree in the right-bottom part. The left-bottom part and the right-bottom part should have the same size. Even if one subtree is none while the other is not, you don’t need to print anything for the none subtree but still need to leave the space as large as that for the other subtree. However, if two subtrees are none, then you don’t need to leave space for both of them.
  4. Each unused space should contain an empty string "".
  5. Print the subtrees following the same rules.

Example 1:

Input:
     1
    /
   2
Output:
[["", "1", ""],
 ["2", "", ""]]

Example 2:

Input:
     1
    / \
   2   3
    \
     4
Output:
[["", "", "", "1", "", "", ""],
 ["", "2", "", "", "", "3", ""],
 ["", "", "4", "", "", "", ""]]

Example 3:

Input:
      1
     / \
    2   5
   / 
  3 
 / 
4 
Output:

[["",  "",  "", "",  "", "", "", "1", "",  "",  "",  "",  "", "", ""]
 ["",  "",  "", "2", "", "", "", "",  "",  "",  "",  "5", "", "", ""]
 ["",  "3", "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]
 ["4", "",  "", "",  "", "", "", "",  "",  "",  "",  "",  "", "", ""]]

Note: The height of binary tree is in the range of [1, 10].


很有意思的一个题,考察了二叉树的多个知识点。

给定一棵二叉树,要求逐层打印出每一层节点的值,而且子节点的位置要在父节点位置的下一层的左边。根据样例可以看到,打印出来的二维数组,如果把每层节点连起来的话,就是原来二叉树的形状。

观察样例可以发现这样一些规律:二叉树的高度就是二维数组的行数;假设高度为h,则二维数组的列数就是$2^h-1$。所以,首先根据LeetCode Maximum Depth of Binary Tree求出二叉树的高度,然后构造好目标大小的二维数组。

接着就是根据二叉树填充数组了。树的题目一般都是用递归来解决,这题也不例外。我们设计一个work函数,每次传入当前需要填充的树节点,二维数组的行号(层数),该节点所在的列数范围。当填充好这个节点后,递归的填充其左节点和右节点,层数加一,同时更新列数范围。

完整代码如下:

class Solution {
public:
	int height(TreeNode* root) {
		if (root == NULL)return 0;
		if (root->left == NULL && root->right == NULL)return 1;
		int lh = height(root->left), rh = height(root->right);
		return (lh > rh ? lh : rh) + 1;
	}
	void work(TreeNode* root, vector<vector<string>>& strTree,int layer,int left,int right) {
		if (root == NULL)return;
		int mid = (left + right) / 2;
		strTree[layer][mid] = to_string(root->val);
		work(root->left, strTree, layer + 1, left, mid - 1);
		work(root->right, strTree, layer + 1, mid + 1, right);
	}
	vector<vector<string>> printTree(TreeNode* root) {
		int h = height(root);
		vector<vector<string>> strTree(h, vector<string>((1 << h) - 1, ""));
		work(root, strTree, 0, 0, strTree[0].size() - 1);
		return strTree;
	}
};

本代码提交AC,用时0MS,性能还是不错的。