Complete the function below. The function receives the number of rows and returns the generated Pascal's Triangle.
Problem: Pascal's Triangle
Given a non-negative integer numRows, generate the first numRows rows of Pascal's Triangle and return them as a 2D array triangle.
Pascal's Triangle is defined as:
Row i (0-indexed) contains i+1 elements.
The first and last element of each row is 1.
For other positions: triangle[i][j] = triangle[i-1][j-1] + triangle[i-1][j] for 0 < j < i.
Input
A single integer: numRows
Output
Print a 2D array (you may print each row as a list) representing the first numRows rows.
Constraints
0 ≤ numRows ≤ 30
Example
Input:
5
Output:
[
[1],
[1,1],
[1,2,1],
[1,3,3,1],
[1,4,6,4,1]
]
Example
Input
0
Output
[]
Function Description
Complete solvePascalsTriangle. It has one parameter, int numRows. Return the first numRows rows of Pascal's Triangle as a 2D integer array.
Constraints
Use the limits and requirements stated in the prompt.
解法
逐行构造：第 0 行为 [1]，第 i 行除首尾的 1 外，row[j] = prev[j-1] + prev[j]。时间复杂度 O(numRows²)，空间复杂度 O(numRows²) 用于结果。
from typing import List
def solvePascalsTriangle(numRows: int) -> List[List[int]]:
res = []
for i in range(numRows):
row = [1] * (i + 1)
for j in range(1, i):
row[j] = res[i - 1][j - 1] + res[i - 1][j]
res.append(row)
return resclass Solution {
int[][] solvePascalsTriangle(int numRows) {
int[][] res = new int[numRows][];
for (int i = 0; i < numRows; i++) {
res[i] = new int[i + 1];
res[i][0] = res[i][i] = 1;
for (int j = 1; j < i; j++) {
res[i][j] = res[i - 1][j - 1] + res[i - 1][j];
}
}
return res;
}
}class Solution {
public:
vector<vector<int>> solvePascalsTriangle(int numRows) {
vector<vector<int>> res(numRows);
for (int i = 0; i < numRows; i++) {
res[i].assign(i + 1, 1);
for (int j = 1; j < i; j++) {
res[i][j] = res[i - 1][j - 1] + res[i - 1][j];
}
}
return res;
}
};Given an integer array nums and an integer k, return the k most frequent elements.
To make the output deterministic, sort elements by frequency in descending order. If two elements have the same frequency, the smaller numeric value comes first.
Function Description
Complete solveTopKFrequentElements. It has the following parameters:
int[] nums: the input array
int k: the number of elements to return
Return an int[] containing the top k elements in the deterministic order described above.
Constraints
1 ≤ nums.length ≤ 10⁵ -10⁴ ≤ nums[i] ≤ 10⁴ 1 ≤ k ≤ number of distinct elements in nums
Example 1
Input:
nums = [1,1,1,2,2,3]
k = 2Output:
[1,2]Explanation: 1 appears 3 times and 2 appears 2 times, so they are the two most frequent elements.
Example 2
Input:
nums = [4,5,2,1,3]
k = 5Output:
[1,2,3,4,5]Explanation: Every number appears once, so ties are resolved by smaller value first.
解法
用哈希表统计频次，再对 (freq desc, value asc) 排序，取前 k 个。也可用桶排序 O(n)。这里用排序版便于稳定的双关键字排序。时间复杂度 O(n log n)，空间复杂度 O(n)。
from typing import List
from collections import Counter
def solveTopKFrequentElements(nums: List[int], k: int) -> List[int]:
cnt = Counter(nums)
items = sorted(cnt.items(), key=lambda x: (-x[1], x[0]))
return [v for v, _ in items[:k]]class Solution {
int[] solveTopKFrequentElements(int[] nums, int k) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int x : nums) cnt.merge(x, 1, Integer::sum);
List<int[]> items = new ArrayList<>();
for (Map.Entry<Integer, Integer> e : cnt.entrySet()) items.add(new int[]{e.getKey(), e.getValue()});
items.sort((a, b) -> a[1] != b[1] ? b[1] - a[1] : a[0] - b[0]);
int[] res = new int[k];
for (int i = 0; i < k; i++) res[i] = items.get(i)[0];
return res;
}
}class Solution {
public:
vector<int> solveTopKFrequentElements(vector<int>& nums, int k) {
unordered_map<int, int> cnt;
for (int x : nums) cnt[x]++;
vector<pair<int, int>> items(cnt.begin(), cnt.end());
sort(items.begin(), items.end(), [](auto& a, auto& b) {
return a.second != b.second ? a.second > b.second : a.first < b.first;
});
vector<int> res;
for (int i = 0; i < k; i++) res.push_back(items[i].first);
return res;
}
};