LeeCode 40.組合總和II

給定一個候選人編號的集合?candidates?和一個目標數?target?,找出?candidates?中所有可以使數字和為?target?的組合。

candidates?中的每個數字在每個組合中只能使用?一次?。

注意:解集不能包含重復的組合。?

示例?1:

輸入: candidates =?[10,1,2,7,6,1,5], target =?8,
輸出:
[
[1,1,6],
[1,2,5],
[1,7],
[2,6]
]

示例?2:

輸入: candidates =?[2,5,2,1,2], target =?5,
輸出:
[
[1,2,2],
[5]
]

提示:

  • 1 <=?candidates.length <= 100
  • 1 <=?candidates[i] <= 50
  • 1 <= target <= 30

答案如下:

void zuhe2(int target, int idx, int* temp, int tempSize, int** res, int*** pRes, int* returnSize, int** returnColumnSizes, int* pCapacity, int* numCountMap);/*** Return an array of arrays of size *returnSize.* The sizes of the arrays are returned as *returnColumnSizes array.* Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().*/
int** combinationSum2(int* candidates, int candidatesSize, int target, int* returnSize, int** returnColumnSizes) { // LeetCode 40.組合和總和// 先統計數組中每個數的出現個數。由題意 1 <= candidates[i] <= 50, numCountMap[n]表示n在candidates數組中出現的次數int numCountMap[51] = { 0 };for (int i = 0; i < candidatesSize; i++) {numCountMap[candidates[i]]++;}// 1 <= target <= 30 , 而數組candidates中的數最小為1,所以組合子數組長度最大可能為30// 但是不知道組合數量,所以結果數組大小不確定。int tempCapacity = candidatesSize < 30 ? candidatesSize : 30;int* temp = (int*)malloc(tempCapacity * sizeof(int)); if (!temp) return NULL;*returnSize = 0;int capacity = 2; // 初始容量,后續容量不夠再擴容*returnColumnSizes = (int*)malloc(capacity * sizeof(int));int** res = (int**)malloc(capacity * sizeof(int*));if (!res) return NULL;zuhe2(target, 0, temp, 0, res ,&res ,returnSize, returnColumnSizes, &capacity, numCountMap);free(temp);return res;
}void zuhe2(int target, int idx, int* temp, int tempSize, int** res, int*** pRes, int* returnSize, int** returnColumnSizes, int* pCapacity, int* numCountMap) {if (target == 0) {// 已滿足,保存結果int* arr_ = (int*)malloc(tempSize * sizeof(int));if (!arr_) return;memcpy(arr_, temp, tempSize * sizeof(int));// 保存前先檢查容量if (*returnSize == *pCapacity) { // 之前申請的內存滿了,不夠再存儲了,擴容int newCapacity = *pCapacity << 1;int** temp_res = (int**)realloc(res, newCapacity * sizeof(int*));if (!temp_res) return;*pRes = temp_res;*returnColumnSizes = (int*)realloc(*returnColumnSizes, newCapacity * sizeof(int));if (*returnColumnSizes == NULL) return;*pCapacity = newCapacity;}*(*pRes + *returnSize) = arr_;*(*returnColumnSizes + *returnSize) = tempSize; // 該組合的數字個數*returnSize = *returnSize + 1;return;}for (int i = idx; i < 51; i++) {// 先判斷i是否使用過了if (numCountMap[i] == 0) {// 該數使用完了continue;}if (i > target) {break;}// 可以加的情況,選中該數temp[tempSize++] = i;numCountMap[i]--;// 再遞歸選給臨時數組下一位賦值。 注意,這里idx參數值必選傳i,不能傳idx,防止選到重復的組合。組合的臨時數組中當前在選的數還可以選,但前面選過的數不能再選zuhe2(target - i, i, temp, tempSize, res, pRes, returnSize, returnColumnSizes, pCapacity, numCountMap);// 回退,不選這個數了tempSize--;numCountMap[i]++;}
}

測試代碼:

void testLeeCode40(void) { // 組合總和IIint nums[] = { 4,4,2,1,4,2,2,1,3 };int target = 6;int numsSize = sizeof(nums) / sizeof(int);int returnSize; // 用于接受結果二維數組的長度。int* returnColumnSizes; // 用來接受結果二維數組的每個元素(即子數組)的長度int** res = combinationSum2(nums, numsSize, target, &returnSize, &returnColumnSizes);printArr(res, returnSize, returnColumnSizes); // 打印二維數組// 釋放內存for (int i = 0; i < returnSize; i++) {free(res[i]);}free(res);free(returnColumnSizes);
}

運行:

ok.? 但是提交到LeeCode,報錯:

看上去是調用realloc函數時報錯重復釋放內存了。? 但是沒看出來哪里重復釋放內存了。沒懂這個報錯哪來的,我自己機器上沒報錯。怎么辦? 我把二維數組的容量直接設置為1000,1000應該是夠用了,避免了動態擴容數組,提交通過了:

這個疑問點后面再研究。

本文來自互聯網用戶投稿,該文觀點僅代表作者本人,不代表本站立場。本站僅提供信息存儲空間服務,不擁有所有權,不承擔相關法律責任。
如若轉載,請注明出處:http://www.pswp.cn/news/919695.shtml
繁體地址,請注明出處:http://hk.pswp.cn/news/919695.shtml
英文地址,請注明出處:http://en.pswp.cn/news/919695.shtml

如若內容造成侵權/違法違規/事實不符,請聯系多彩編程網進行投訴反饋email:809451989@qq.com,一經查實,立即刪除!

相關文章

數據結構:隊列 二叉樹

隊列&#xff08;Queue&#xff09; 是一種先進先出&#xff08;First In First Out, FIFO&#xff09; 的線性數據結構。 隊列的基本特性 1. FIFO 原則 ? 最先進入的元素最先出去 ? 就像現實生活中的排隊&#xff1a;先來的人先接受服務 2. 兩個主要操作端 ? 隊尾&#xff…

FTP工作原理及搭建實操

文章目錄前言一、FTP概述二、FTP工作原理2.1 FTP的作用與模式2.2 FTP工作流程2.2.1 主動模式&#xff08;PORT模式&#xff09;2.2.2 被動模式&#xff08;PASV模式&#xff09;2.2.3 對比表格2.2.4 如何選擇&#xff1f;2.2.5 補充&#xff1a;現代FTP服務器的常見做法三、FTP…

setup 語法糖核心要點

1. 基本語法<!-- 傳統寫法 --> <script lang"ts"> export default {setup() {let name 張三function changeName() { name 李四 }return { name, changeName }} } </script><!-- 語法糖寫法 --> <script setup lang"ts"> …

C++---多態(一個接口多種實現)

C的多態&#xff08;Polymorphism&#xff09;是面向對象編程&#xff08;OOP&#xff09;的三大核心特性之一&#xff08;另外兩個是封裝和繼承&#xff09;&#xff0c;其核心思想是一個接口&#xff0c;多種實現&#xff0c;即同一操作作用于不同對象時&#xff0c;可產生不…

【機器學習深度學習】vLLM的核心優化技術詳解

目錄 前言 一、vLLM簡介&#xff1a;為什么它如此重要&#xff1f; 二、核心技術一&#xff1a;PagedAttention — 顯存管理的革命 2.1 傳統注意力緩存的缺陷 2.2 分頁式存儲管理 三、核心技術二&#xff1a;張量并行 — 多GPU推理的基石 3.1 什么是張量并行&#xff1f…

MySQL 高級主題:索引優化、ORM 與數據庫遷移

第五部分&#xff1a;索引優化1. 為什么需要索引&#xff1f;索引是提高數據庫查詢性能的關鍵數據結構&#xff0c;它類似于書籍的目錄&#xff0c;可以幫助數據庫快速定位到所需數據&#xff0c;而不必掃描整個表。2. 索引類型主鍵索引 (PRIMARY KEY): 唯一且非空&#xff0c;…

Eplan教程:網絡與PLC

歡迎大家來到“Eplan帶你做項目”第六個過程。在第五個過程中&#xff0c;Eplan基于實際項目的繪制&#xff08;電氣設計中的電源回路以及電源分配相關回路&#xff09;重點分享分了“電機的供電和控制圖紙的繪制”。本文中&#xff0c;先猜個問題&#xff0c;設計一個PLC系統&…

大模型落地全攻略:從技術實現到場景應用

大語言模型&#xff08;LLM&#xff09;的快速發展正在重塑各行各業的智能化進程&#xff0c;但其落地應用仍面臨技術適配、場景融合、成本控制等多重挑戰。本文將系統解析大模型落地的四大核心方向 ——微調技術、提示詞工程、多模態應用和企業級解決方案&#xff0c;通過代碼…

【論文】Zotero文獻管理

Zotero文獻管理 寫論文前查找閱讀大量文獻&#xff0c;寫論文時引用文獻&#xff0c;都是一件非常麻煩的事情&#xff0c;一款合適的文獻管理工具可以幫助我們更快捷地完成這些任務。zotero作為一款免費開源的工具&#xff0c;可以實現文獻閱讀、同步管理以及引用管理。 安裝…

MsSQL 函數,實現數字轉換成人民幣大寫

MsSQL 函數&#xff0c;實現數字轉換成人民幣大寫-- 如果函數已存在則刪除 IF OBJECT_ID(dbo.ConvertToRMBChineseNew, FN) IS NOT NULLDROP FUNCTION dbo.ConvertToRMBChineseNew GOCREATE FUNCTION dbo.ConvertToRMBChineseNew (NumberInput SQL_VARIANT -- 使用 SQL_VARIANT…

OpenHarmony深度定制:從系統到模塊的全景剖析與自定義模塊實戰

摘要:OpenHarmony 作為面向萬物互聯時代的開源操作系統,其“系統-子系統-部件-模塊”的四層架構設計,為開發者提供了高度可裁剪、可擴展的能力。本文將系統梳理這四層結構的職責邊界與協作關系,并手把手演示如何向 OpenHarmony 新增一個可交付的自定義模塊(Module),幫助…

數字社會學是干什么的?數字社會學理論與數字社會學家唐興通講數字社會學書籍有哪些?AI社會學人工智能社會學理論框架

在當今社會&#xff0c;傳統物理空間和人際關系網絡成為了許多年輕人尋找合適伴侶的重大障礙。以深圳為例&#xff0c;這座移民城市的大部分居民都來自外地&#xff0c;年輕人的人脈關系、尤其是親戚關系大多仍在家鄉。這使得深圳的單身男女在交友和婚戀方面的選擇面變得狹窄&a…

數據庫-MYSQL配置下載

目錄 一.數據庫概念 一、數據庫的基本定義 二、數據庫管理系統&#xff08;DBMS&#xff09; 三、數據庫系統&#xff08;DBS&#xff09; 四、數據模型 五、數據庫的特點 六、數據庫的應用領域 二.MySql 一、開源免費&#xff0c;降低中大型項目成本 二、跨平臺與兼容…

Java 中表示數據集的常用集合類

Java 中表示數據集的常用集合類 Java 集合框架提供了多種數據結構來表示和操作數據集&#xff0c;每種集合類都有其特定的用途和性能特征。以下是主要的集合類及其特點&#xff1a; 一、List 接口及其實現類 1. ArrayList 特點&#xff1a;基于動態數組實現優點&#xff1a;隨機…

Django REST框架核心:GenericAPIView詳解

Django REST framework (DRF) 中 GenericAPIView 的源碼核心部分。 它是所有“泛型視圖”的基礎類&#xff0c;比如常用的 ListAPIView、RetrieveAPIView、CreateAPIView 都是繼承自它。&#x1f31f; 作用繼承自 APIView&#xff0c;因此仍然是一個標準的 DRF 視圖。提供了常用…

深入解析HashMap的存儲機制:擾動函數、哈希計算與索引定位

今天復習了一下HashMap的部分&#xff0c;寫一篇博客記錄一下今天學習內容雖然之前學習過&#xff0c;但由于后來沒怎么使用過而且也沒復習基本忘得差不多了在Java的HashMap中&#xff0c;高效存儲鍵值對的核心在于哈希算法和索引定位。本文將結合源碼逐步拆解存儲流程&#xf…

【機器學習 / 深度學習】基礎教程

階段一&#xff1a;機器學習 / 深度學習基礎教程定位&#xff1a;針對準備進入 AI多智能體開發 的初學者&#xff0c;打牢機器學習與深度學習的基礎。一、為什么需要學習機器學習/深度學習 在進入智能體&#xff08;Agent&#xff09;開發之前&#xff0c;必須具備一定的 機器學…

ESP32應用——HTTP client(ESP-IDF框架)

目錄 一、前言 二、URL 2.1 URL簡介 2.2 URL示例 三、HTTP 3.1 HTTP協議概述 3.2 HTTP的工作原理 3.2.1 HTTP 請求-響應流程 3.2.2 HTTP 請求結構 3.2.3 HTTP請求方法 3.2.4 HTTP響應結構 3.2.5 HTTP狀態碼 四、ESP HTTP 客戶端流程 五、ESP HTTP 客戶端實戰解析…

動學學深度學習07-現代卷積神經網絡

動學學深度學習pytorch 參考地址&#xff1a;https://zh.d2l.ai/ 文章目錄動學學深度學習pytorch1-第07章-現代卷積神經網絡1. AlexNet1.1 AlexNet 的核心貢獻是什么&#xff1f;1.2 AlexNet 與 LeNet 的主要區別有哪些&#xff1f;1.3 為什么 AlexNet 需要 GPU 訓練&#xff1…

詳細講解Java中的反射和經典面試題(保姆級別)

1.1 反射的概述&#xff1a;專業的解釋&#xff08;了解一下&#xff09;&#xff1a;是在運行狀態中&#xff0c;對于任意一個類&#xff0c;都能夠知道這個類的所有屬性和方法&#xff1b;對于任意一個對象&#xff0c;都能夠調用它的任意屬性和方法&#xff1b;這種動態獲取…