|
精品推薦：
《征服數(shù)據(jù)結構》專欄：50多種數(shù)據(jù)結構徹底征服 《經典圖論算法》專欄：50多種經典圖論算法全部掌握 2024年10月11號，上海格力汽車科技有限公司成立，注冊資本2000萬人民幣，最大股東是珠海格力智能裝備有限公司。經營范圍含汽車零部件研發(fā)，汽車零部件及配件制造，工業(yè)機器人制造，工業(yè)機器人銷售等。 對此網(wǎng)友質疑：格力跨界造車，但電動汽車的核心在于電池、電機和電控，這三大件格力是否有技術儲備？畢竟跟空調還是差挺多的。 還有網(wǎng)友說：2000萬夠干嘛，研發(fā)一個輪子都夠嗆。不過2000萬對于造車來說確實非常少。我在企查查上查了下小米汽車的注冊資本是1000000萬元人民幣，蔚來汽車是300000萬美元，基本上都是上百億。 而格力2千萬的注冊資本估計勉強能招20個年薪百萬的高級工程師，關鍵20個人在一年以內也造不出車啊，超過一年工資又不夠發(fā)了。不過網(wǎng)友的評論也是相當幽默，基本都是調侃，大家可以看下。 --------------下面是今天的算法題-------------- 來看下今天的算法題，這題是LeetCode的第368題：最大整除子集。 給你一個由無重復正整數(shù)組成的集合 nums ，請你找出并返回其中最大的整除子集 answer ，子集中每一元素對 (answer[i], answer[j]) 都應當滿足：1，answer[i] % answer[j] == 0 ，或 2，answer[j] % answer[i] == 0 輸入：nums = [1,2,3] 輸出：[1,2] 解釋：[1,3] 也會被視為正確答案。
輸入：nums = [1,2,4,8] 輸出：[1,2,4,8]
1 <= nums.length <= 1000 1 <= nums[i] <= 2 * 10^9 nums 中的所有整數(shù)互不相同
這題讓找出最長的整除子集，注意這里是子集，不是子序列，所以我們可以對數(shù)組進行排序，這樣這題就變成了我們前面講的《最長遞增子序列》。按照前面那題的思路就可以解這道題了。這里定義dp[i]表示以第 i 個元素為結尾的最長整除子集長度，如果nums[i]能被nums[j]整除(j<i)，可以嘗試把nums[i]放到nums[j]后面，看能不能構成更長的整除子集，如果能，就更新長度。
但這題讓返回的是子集，而不是子集的長度，所有我們還需要記錄選擇的過程，使用一個變量path來記錄。public List<Integer> largestDivisibleSubset(int[] nums) {
Arrays.sort(nums);// 先對數(shù)組進行排序
int n = nums.length;
int[] dp = new int[n];
int[] path = new int[n];// 記錄最大整除子序列的下標
Arrays.fill(dp, 1); // 初始化數(shù)組dp的每個值為1
Arrays.fill(path, -1);// 初始 -1 。
int max = 1;// 記錄最大整除子集的長度
int maxIndex = 0;// 記錄最大整除子集中最后一個元素的下標
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
// 記錄路徑，表示最大整除子集中 i 前面一個是 j
path[i] = j;
}
}
// 如果找到更大的子集，就記錄最大的
if (dp[i] > max) {
max = dp[i];// 最大整除子集長度
maxIndex = i;// 最大整除子集最后一個元素的位置
}
}
// prev很類似于鏈表，每一個都是記錄前一個的位置
List<Integer> res = new ArrayList<>();
while (maxIndex != -1) {
res.add(nums[maxIndex]);
maxIndex = path[maxIndex];
}
return res;
}
public:
vector<int> largestDivisibleSubset(vector<int> &nums) {
sort(nums.begin(), nums.end());// 先對數(shù)組進行排序
int n = nums.size();
vector<int> dp(n, 1);
vector<int> path(n, -1);// 記錄最大整除子序列的下標
int max = 1;// 記錄最大整除子集的長度
int maxIndex = 0;// 記錄最大整除子集中最后一個元素的下標
for (int i = 1; i < n; i++) {
for (int j = 0; j < i; j++) {
if (nums[i] % nums[j] == 0 && dp[j] + 1 > dp[i]) {
dp[i] = dp[j] + 1;
// 記錄路徑，表示最大整除子集中 i 前面一個是 j
path[i] = j;
}
}
// 如果找到更大的子集，就記錄最大的
if (dp[i] > max) {
max = dp[i];// 最大整除子集長度
maxIndex = i;// 最大整除子集最后一個元素的位置
}
}
// prev很類似于鏈表，每一個都是記錄前一個的位置
vector<int> res;
while (maxIndex != -1) {
res.push_back(nums[maxIndex]);
maxIndex = path[maxIndex];
}
return res;
}
def largestDivisibleSubset(self, nums: List[int]) -> List[int]:
nums.sort()# 先對數(shù)組進行排序
n = len(nums)
dp = [1] * n
path = [-1] * n #記錄最大整除子序列的下標
max_len = 1 #記錄最大整除子集的長度
max_index = 0 #記錄最大整除子集中最后一個元素的下標
for i in range(1, n):
for j in range(i):
if nums[i] % nums[j] == 0 and dp[j] + 1 > dp[i]:
dp[i] = dp[j] + 1
path[i] = j #記錄路徑，表示最大整除子集中 i 前面一個是 j
# 如果找到更大的子集，就記錄最大的
if dp[i] > max_len:
max_len = dp[i] #最大整除子集長度
max_index = i # 最大整除子集最后一個元素的位置
res = []
# prev很類似于鏈表，每一個都是記錄前一個的位置
while max_index != -1:
res.append(nums[max_index])
max_index = path[max_index]
return res
博哥，真名：王一博，畢業(yè)十多年，《算法秘籍》作者，專注于數(shù)據(jù)結構和算法的講解，在全球30多個算法網(wǎng)站中累計做題2000多道，在公眾號中寫算法題解800多題，對算法題有自己獨特的解題思路和解題技巧，喜歡的可以給個關注，也可以下載我整理的1000多頁的PDF算法文檔。數(shù)組，稀疏表(Sparse Table)，單向鏈表，雙向鏈表，塊狀鏈表，跳表，隊列和循環(huán)隊列，雙端隊列，單調隊列，棧，單調棧，雙端棧，散列表，堆，字典樹(Trie樹)，ArrayMap，SparseArray，二叉樹，二叉搜索樹(BST)，笛卡爾樹，AVL樹，樹堆(Treap)，FHQ-Treap，哈夫曼樹，滾動數(shù)組，差分數(shù)組，LRU緩存，LFU緩存 …… 《經典圖論算法》專欄 圖的介紹，圖的表示方式，鄰接矩陣轉換，廣度優(yōu)先搜索(BFS)，深度優(yōu)先搜索(DFS)，A*搜索算法，迭代深化深度優(yōu)先搜索(IDDFS)，IDA*算法，雙向廣度優(yōu)先搜索，迪杰斯特拉算法(Dijkstra)，貝爾曼-福特算法(Bellman-Ford)，SPFA算法，弗洛伊德算法(Floyd)，卡恩(Kahn)算法，基于DFS的拓撲排序，約翰遜算法(Johnson) ……
|
