面試熱題(全排列)

? ? ? ? 給定一個不含重復數字的整數數組?nums?,返回其?所有可能的全排列?。可以?按任意順序?返回答案。

輸入:nums = [1,2,3]
輸出:[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

先在這里說明一下排列和組合的區別?

組合:是指從一個元素集合中選擇出若干個元素,形成一個無序的子集,組合不考慮元素的順序,只關注元素的選擇

排列:是指從一個元素集合中選擇出若干元素,形成一個有序的序列。排列關注元素的順序。

簡單的來說,就是排列是元素是有序的,組合是無序的

一般排列組合問題我們都可以看成是一棵樹(每個元素不允許重復)? ? ? ? ? ?

因為我們這題要求的是不重復的排列數,所以我們的模板就可以套了(模板必須要記的——理解)

//不含重復元素的排列數
void backTrack(int[] nums){1for(int i=0;i<nums.length;i++){if(uesd[i])continue;used[i]=true;path.addLast(nums[i]);backTrack(nums);path.removeLast(nums[i]);used[i]=false;}

源代碼如下:

    //存儲結果集List<List<Integer>> list = new ArrayList<>();//路徑Deque<Integer> path = new LinkedList<>();//是否被訪問boolean[] visited = null;public List<List<Integer>> permute(int[] nums) {//對入參進行判斷if (nums == null || nums.length == 0) {return list;}//對數組進行初始化visited=new boolean[nums.length];//開始遞歸,因為是排列,后面的元素也有可能在前面的元素前面,所以不需要傳遞索引backtracking(nums);//返回結果集return list;}private void backtracking(int[] nums) {//找到滿足條件得到一種情況,存入結果集中if (path.size()== nums.length) {list.add(new ArrayList<>(path));return;}//遍歷每一個元素for (int j = 0; j < nums.length; j++) {//如果被訪問過,直接跳過,避免重復選擇if(visited[j]){continue;}path.add(nums[j]);visited[j]=true;backtracking(nums);//回溯path.removeLast();visited[j]=false;}
}

在這里給大家提供我刷組合排列問題總結的模板:

組合子集問題每個元素的相對位置已經固定,所以每次去枚舉的時候都是從自身的右側開始枚舉

排列問題的每個元素的相對位置是不固定的。左側的元素可能會出現在右側,故每次每次枚舉都是從0位置上開始枚舉的

  • 元素無重不可復選(nums中的元素唯一,每個元素最多只能被使用一次)

/*組合/子集問題回溯模板*/
/* [1,2,3]  */
void backTrack(int[] nums,int start){//順序無關,每次從自身的右邊開始for(int i=start;i<nums.length;i++){path.addLast(nums[i]);backTrack(nums,i+1);path.removeLast(nums[i]);}
}
/* 排列問題回溯模板*/
void backTrack(int[] nums){//順序有關,每次從0開始for(int i=0;i<nums.length;i++){if(uesd[i])continue;used[i]=true;path.addLast(nums[i]);backTrack(nums);path.removeLast(nums[i]);used[i]=false;}
}
  • .元素可重不可復選(nums中的元素可以存在重復,每個元素最多只能被使用一次)

    Arrays.sort(nums);
    /* 組合/子集問題回溯算法框架 */
    void backtrack(int[] nums, int start) {// 回溯算法標準框架for (int i = start; i < nums.length; i++) {// 剪枝邏輯,跳過值相同的相鄰樹枝if (i > start && nums[i] == nums[i - 1]) {continue;}// 做選擇track.addLast(nums[i]);// 注意參數backtrack(nums, i + 1);// 撤銷選擇track.removeLast();}
    }Arrays.sort(nums);
    /* 排列問題回溯算法框架 */
    void backtrack(int[] nums) {for (int i = 0; i < nums.length; i++) {// 剪枝邏輯if (used[i]) {continue;}// 剪枝邏輯,固定相同的元素在排列中的相對位置if (i > 0 && nums[i] == nums[i - 1] && !used[i - 1]) {continue;}// 做選擇used[i] = true;track.addLast(nums[i]);backtrack(nums);// 撤銷選擇track.removeLast();used[i] = false;}
    }
    

有很多人對上述剪枝操作不理解,看了這幅圖你就會豁然開?

  • 元素無重可復選(nums中的元素都是唯一的,每個元素可以被使用若干次)

    /* 組合/子集問題回溯算法框架 */
    void backtrack(int[] nums, int start) {// 回溯算法標準框架for (int i = start; i < nums.length; i++) {// 做選擇track.addLast(nums[i]);// 可以復選,所以i不用+1作為參數backtrack(nums, i);// 撤銷選擇track.removeLast();}
    }/* 排列問題回溯算法框架 */
    void backtrack(int[] nums) {for (int i = 0; i < nums.length; i++) {// 做選擇track.addLast(nums[i]);backtrack(nums);// 撤銷選擇track.removeLast();}
    }

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

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

相關文章

前端三劍客

三劍客 萬維網聯盟&#xff08; World Wide Web Consortium &#xff09;&#xff0c;創建于1994年10月&#xff0c;主要工作是對 web 進行標準化。 ? 該組織定義了網頁的開發需要如下3門技術&#xff1a; ? - HTML:定義網頁的結構 - CSS: 定義網頁的表現&#xff0c;樣式 -…

開源數據庫Mysql_DBA運維實戰 (名詞解釋)

SQL&#xff08;Structured Query Language 即結構化查詢語言&#xff09; SQL語言主要用于存取數據、查詢數據、更新數據和管理關系數據庫系統&#xff0c;SQL語言由IBM開發。 SQL語言分類&#xff1a; DDL語句 數據庫定義語言&#xff1a;數據庫、表、視圖、索引、存儲過程…

Steam 靈感的游戲卡懸停效果

先看效果&#xff1a; 再看代碼&#xff08;查看更多&#xff09;&#xff1a; <!DOCTYPE html> <html lang"en"> <head><meta charset"UTF-8"><title>Steam 靈感的游戲卡懸停效果</title><style>* {margin: …

構建高效外賣系統平臺:從需求到實現

隨著科技的不斷進步和人們生活節奏的加快&#xff0c;外賣成為了越來越多人的飲食選擇。為了滿足這一需求&#xff0c;開發一套高效的外賣系統平臺變得尤為重要。本文將從需求分析開始&#xff0c;逐步引導您了解如何開發一套完整的外賣系統平臺。 第一步&#xff1a;需求分析…

分類預測 | MATLAB實現EVO-CNN多輸入分類預測

分類預測 | MATLAB實現EVO-CNN多輸入分類預測 目錄 分類預測 | MATLAB實現EVO-CNN多輸入分類預測預測效果基本介紹程序設計參考資料 預測效果 基本介紹 1.MATLAB實現EVO-CNN多輸入分類預測 2.代碼說明&#xff1a;量谷優化卷積神經網絡的數據分類預測&#xff1a;要求于Matlab …

【hadoop】windows上hadoop環境的搭建步驟

文章目錄 前言基礎環境下載hadoop安裝包下載hadoop在windows中的依賴配置環境變量 Hadoop hdfs搭建創建hadfs數據目錄修改JAVA依賴修改配置文件初始化hdfs namenode啟動hdfs 前言 在大數據開發領域中&#xff0c;不得不說說傳統經典的hadoop基礎計算框架。一般我們都會將hadoo…

計算機視覺目標檢測性能指標

目錄 精確率&#xff08;Precision&#xff09;和召回率&#xff08;Recall&#xff09; F1分數&#xff08;F1 Score&#xff09; IoU&#xff08;Intersection over Union&#xff09; P-R曲線&#xff08;Precision-Recall Curve&#xff09;和 AP mAP&#xff08;mean…

Leetcode-每日一題【劍指 Offer 30. 包含min函數的棧】

題目 定義棧的數據結構&#xff0c;請在該類型中實現一個能夠得到棧的最小元素的 min 函數在該棧中&#xff0c;調用 min、push 及 pop 的時間復雜度都是 O(1)。 示例: MinStack minStack new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack…

【mysql】事務的四種特性的理解

&#x1f307;個人主頁&#xff1a;平凡的小蘇 &#x1f4da;學習格言&#xff1a;命運給你一個低的起點&#xff0c;是想看你精彩的翻盤&#xff0c;而不是讓你自甘墮落&#xff0c;腳下的路雖然難走&#xff0c;但我還能走&#xff0c;比起向陽而生&#xff0c;我更想嘗試逆風…

TOMCAT基礎

tomcat是一個基于Java開發的&#xff0c;開放源代碼的web應用服務器。它可以解析html頁面中的java代碼&#xff0c;執行動態請求&#xff0c;實現動態頁面。核心功能是將收到的http請求處理并轉發給適當的servlet來處理&#xff0c;然后將響應返回給客戶端。 優點 1&#xff0c…

Django實現音樂網站 ⑼

使用Python Django框架制作一個音樂網站&#xff0c; 本篇主要是后臺對專輯、首頁輪播圖原有功能的基礎上進行部分功能實現和顯示優化。 目錄 專輯功能優化 新增編輯 專輯語種改為下拉選項 添加單曲優化顯示 新增單曲多選 更新歌手專輯數、專輯單曲數 獲取歌手專輯數 保…

【并發編程】自研數據同步工具的優化:創建線程池多線程異步去分頁調用其他服務接口獲取海量數據

文章目錄 場景&#xff1a;解決方案 場景&#xff1a; 前段時間在做一個數據同步工具&#xff0c;其中一個服務的任務是調用A服務的接口&#xff0c;將數據庫中指定數據請求過來&#xff0c;交給kafka去判斷哪些數據是需要新增&#xff0c;哪些數據是需要修改的。 剛開始的設…

Character Animation With Direct3D 讀書筆記

角色動畫簡介 2D動畫&#xff1a;循環播放多張圖片 3D動畫&#xff1a; 骨骼動畫、變形動畫 DirectX入門 Win32 應用程序 Application類&#xff1a;處理主程序循環&#xff0c;圖形設備的初始化 Init&#xff1a;加載資源并創建圖形設備Update&#xff1a;更新游戲世界&am…

Vue中子組件修改父組件傳來的Prop值

vue中子組件不能直接修改父組件傳來的prop值&#xff0c;Prop 是一種傳遞數據的機制&#xff0c;父組件通過 Prop 向子組件傳遞數據&#xff0c;子組件通過 Props 接收父組件傳遞過來的數據&#xff0c;這些數據被封裝成一個個解構體形式的對象&#xff0c;不能直接進行修改。這…

React 18 更新 state 中的對象

參考文章 更新 state 中的對象 state 中可以保存任意類型的 JavaScript 值&#xff0c;包括對象。但是&#xff0c;不應該直接修改存放在 React state 中的對象。相反&#xff0c;當想要更新一個對象時&#xff0c;需要創建一個新的對象&#xff08;或者將其拷貝一份&#xf…

圖像去雨、去雪、去霧論文學習記錄

All_in_One_Bad_Weather_Removal_Using_Architectural_Search 這篇論文發表于CVPR2020&#xff0c;提出一種可以應對多種惡劣天氣的去噪模型&#xff0c;可以同時進行去雨、去雪、去霧操作。但該部分代碼似乎沒有開源。 提出的問題&#xff1a; 當下的模型只能針對一種惡劣天氣…

【ARM 嵌入式 編譯系列 4.1 -- GCC 編譯屬性 likely與unlikely 學習】

文章目錄 GCC likely與unlikely 介紹linux 內核中的 likely/unlikely上篇文章:ARM 嵌入式 編譯系列 4 – GCC 編譯屬性 __read_mostly 介紹 下篇文章: ARM 嵌入式 編譯系列 4.2 – GCC 鏈接規范 extern “C“ 介紹 GCC likely與unlikely 介紹 likely 和 unlikely 是GCC編譯器…

JDBC連接數據庫(mysql)

準備jar包 官網下載即可&#xff0c;這里提供兩個我下載過的jar包&#xff0c;供使用 鏈接&#xff1a;https://pan.baidu.com/s/1snikBD1kEBaaJnVktLvMdQ?pwdrwwq 提取碼&#xff1a;rwwq eclipse導 jar包: 導入成功會有如下所示&#xff1a; ---------------------------…

個人開發中常見單詞拼錯錯誤糾正

個人開發中常見單詞拼錯錯誤糾正 前置說明參考地址后端開發相關前端開發相關客戶端開發相關大數據/云計算相關工具或軟件相關 前置說明 單詞太多啦, 我這里只列表我個人見得比較多的, 我沒見過就不列舉了. 有錯誤或想補充的可以提交在原倉庫提交Pull Request. &#x1f601; …

JavaScript面試題(二)

31、http 的理解 ? HTTP 協議是超文本傳輸協議&#xff0c;是客戶端瀏覽器或其他程序“請求”與 Web 服務器響應之間的應用層通信協議。HTTPS主要是由HTTPSSL構建的可進行加密傳輸、身份認證的一種安全通信通道。 32、http 和 https 的區別 ? 1、https協議需要到ca申請證書…