算法入門篇九 暴力遞歸

牛客網?左程云老師的算法入門課

暴力遞歸

原則

?漢諾塔問題

問題

  • 打印n層漢諾塔從左邊移動到最右邊的過程?

思想

一共六個過程，左到右、左到中，中到左，中到右，右到左，右到中，互相嵌套使用

左到右

  • 將1-》N-1移動到中間的那個桿上
  • 將N從最左邊移動到最右邊
  • 將1》-N-1移動到最右邊的那個桿上

左到中

  • 將1-N-1從左移動到右
  • N從左移動到中
  • 將1-》N-1從右移動到中

。。。。。。

代碼

package class08;public class Code01_Hanoi {public static void hanoi(int n) {if (n > 0) {func(n, "左", "右", "中");}}// 1~i 圓盤 目標是from -> to， other是另外一個public static void func(int N, String from, String to, String other) {if (N == 1) { // baseSystem.out.println("Move 1 from " + from + " to " + to);} else {func(N - 1, from, other, to);System.out.println("Move " + N + " from " + from + " to " + to);func(N - 1, other, to, from);}}public static void printAllWays(int n) {leftToRight(n);}public static void leftToRight(int n) {if(n== 1) {System.out.println("Move 1 from left to right");return ;}leftToMid(n-1);System.out.println("Move " +n + " from left to right");midToRight(n-1);}public static void leftToMid(int n) {if(n== 1) {System.out.println("Move 1 from left to mid");return ;}leftToRight(n-1);System.out.println("Move " +n + " from left to mid");rightToMid(n-1);}public static void midToRight(int n) {}public static void rightToMid(int n) {}public static void main(String[] args) {int n = 3;hanoi(n);}}

例子

打印一個字符串的全部子序列，包括空字符串

（從左往右依次嘗試的模型）

  • 需要保證字符的前后順序
  • “abc” =》a,b,c,ab,ac,bc,abc,null
  • 暴力窮舉

打印字符串的全部排列

思路

  • 全排列，先前所選用的字符，后面后不可以選擇了。

代碼

package class08;import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;public class Code03_PrintAllPermutations {public static ArrayList<String> Permutation(String str) {ArrayList<String> res = new ArrayList<>();if (str == null || str.length() == 0) {return res;}char[] chs = str.toCharArray();process(chs, 0, res);return res;}// str[i..]范圍上，所有的字符，都可以在i位置上，后續都去嘗試// str[0..i-1]范圍上，是之前做的選擇// 請把所有的字符串形成的全排列，加入到res里去public static void process(char[] str, int i, ArrayList<String> res) {if (i == str.length) {res.add(String.valueOf(str));}boolean[] visit = new boolean[26]; // visit[0 1 .. 25]for (int j = i; j < str.length; j++) {if (!visit[str[j] - 'a']) {visit[str[j] - 'a'] = true;swap(str, i, j);process(str, i + 1, res);swap(str, i, j);}}}public static void swap(char[] chs, int i, int j) {char tmp = chs[i];chs[i] = chs[j];chs[j] = tmp;}public static List<String> getAllC(String s) {List<String> ans = new ArrayList<>();ArrayList<Character> set = new ArrayList<>();for (char cha : s.toCharArray()) {set.add(cha);}process(set, "", ans);return ans;}public static void process(ArrayList<Character> list, String path, List<String> ans) {if (list.isEmpty()) {ans.add(path);return;}HashSet<Character> picks = new HashSet<>();//set中每一個字符，都可以作為當前字符，但是一旦當前決定要，后續就不能再次使用了 （去重）for (int index = 0; index < list.size(); index++) {if (!picks.contains(list.get(index))) {picks.add(list.get(index));String pick = path + list.get(index);ArrayList<Character> next = new ArrayList<>(list);next.remove(index);process(next, pick, ans);}}}public static void main(String[] args) {String s = "aac";List<String> ans = getAllC(s);for (String str : ans) {System.out.println(str);}}}

數字轉化

題目要求

思路?

  • 輸入原始的字符串111，下面012對應其位置，對于第i個節點，i可以自己實現轉化，或者連帶i+1實現轉化

  • 但是需要判定i和i+1是否超出26，因為26最大代表z

  • 遇到0的時候，要判定：比如“102”，如果1自己單獨做決定，那么0自己不可以做決定，0和2也不可以做決定，因此0只可以和且在一起，才是有效的

代碼

package class08;public class Code06_ConvertToLetterString {public static int number(String str) {if (str == null || str.length() == 0) {return 0;}return process(str.toCharArray(), 0);}// i之前的位置，如何轉化已經做過決定了, 不用再關心// str[i... ] 有多少種轉化的結果public static int process(char[] str, int i) {if (i == str.length) { // base case//來到終止的位置，之前的路徑代表一種有效的方法return 1;}// i沒有到終止位置if (str[i] == '0') {//“102”的情形，0做不了決定return 0;}// str[i]字符不是‘0’if (str[i] == '1') {int res = process(str, i + 1); // i自己作為單獨的部分，后續有多少種方法if (i + 1 < str.length) {res += process(str, i + 2); // (i和i+1)作為單獨的部分，后續有多少種方法}return res;}if (str[i] == '2') {int res = process(str, i + 1); // i自己作為單獨的部分，后續有多少種方法// (i和i+1)作為單獨的部分并且沒有超過26，后續有多少種方法if (i + 1 < str.length && (str[i + 1] >= '0' && str[i + 1] <= '6')) {res += process(str, i + 2); // (i和i+1)作為單獨的部分，后續有多少種方法}return res;}// str[i] == '3' ~ '9'return process(str, i + 1);}public static int dpWays(String s) {if (s == null || s.length() == 0) {return 0;}char[] str = s.toCharArray();int N = str.length;int[] dp = new int[N + 1];dp[N] = 1;for (int i = N - 1; i >= 0; i--) {if (str[i] == '0') {dp[i] = 0;} else if (str[i] == '1') {dp[i] = dp[i + 1];if (i + 1 < N) {dp[i] += dp[i + 2];}} else if (str[i] == '2') {dp[i] = dp[i + 1]; if (i + 1 < str.length && (str[i + 1] >= '0' && str[i + 1] <= '6')) {dp[i] += dp[i + 2];}} else {dp[i] = dp[i + 1];}}return dp[0];}public static void main(String[] args) {System.out.println(number("11111"));}}

背包問題

題目要求

代碼

package class08;public class Code07_Knapsack {public static int getMaxValue(int[] w, int[] v, int bag) {return process(w, v, 0, 0, bag);}// index   當前貨物的貨物號//w【index】當前貨物的重量//v【index】當前貨物的價值//alreadyW：0至index-1已經做出的決定，所形成的目前的重量//bag：袋子的總共重量（固定參數）//index。。。后續所有貨物的自由選擇，返回最大的價值public static int process(int[] w, int[] v, int index, int alreadyW, int bag) {if (alreadyW > bag) {//超重了return -1;}// 重量沒超if (index == w.length) {return 0;}int p1 = process(w, v, index + 1, alreadyW, bag);//不要當前index貨物，獲得的最大價值int p2next = process(w, v, index + 1, alreadyW + w[index], bag);//要當前貨物，當前貨物的價值 + 后續得到的價值int p2 = -1;if (p2next != -1) {p2 = v[index] + p2next;}return Math.max(p1, p2);}public static int maxValue(int[] w, int[] v, int bag) {return process(w, v, 0, bag);}// 只剩下rest的空間了，// index...貨物自由選擇，但是不要超過rest的空間// 返回能夠獲得的最大價值public static int process(int[] w, int[] v, int index, int rest) {if (rest <= 0) { // base case 1return 0;}// rest >=0if (index == w.length) { // base case 2return 0;}// 有貨也有空間int p1 = process(w, v, index + 1, rest);int p2 = Integer.MIN_VALUE;if (rest >= w[index]) {p2 = v[index] + process(w, v, index + 1, rest - w[index]);}return Math.max(p1, p2);}public static int dpWay(int[] w, int[] v, int bag) {int N = w.length;int[][] dp = new int[N + 1][bag + 1];for (int index = N - 1; index >= 0; index--) {for (int rest = 1; rest <= bag; rest++) {dp[index][rest] = dp[index + 1][rest];if (rest >= w[index]) {dp[index][rest] = Math.max(dp[index][rest], v[index] + dp[index + 1][rest - w[index]]);}}}return dp[0][bag];}public static void main(String[] args) {int[] weights = { 3, 2, 4, 7 };int[] values = { 5, 6, 3, 19 };int bag = 11;System.out.println(maxValue(weights, values, bag));System.out.println(dpWay(weights, values, bag));}}

取牌

思路

  • 第一種情形，只剩下一張牌的時候，直接取最后一張牌就可以了

  • 如果取最左邊的牌，計算我的成績為arr【L】+S（arr，L+1，R）

  • 如果取最右邊的牌，計算我的成績為arr【R】+S（arr，L，R-1）

  • 對于上面兩種情形取最大值就是我的選擇

  • 其中S為黑盒函數，因為先手和后手是互換的角色，當先手取完牌之后，其角色就變成后手了

代碼

package class08;public class Code08_CardsInLine {public static int win1(int[] arr) {if (arr == null || arr.length == 0) {return 0;}return Math.max(f(arr, 0, arr.length - 1), s(arr, 0, arr.length - 1));}public static int f(int[] arr, int i, int j) {if (i == j) {return arr[i];}return Math.max(arr[i] + s(arr, i + 1, j), arr[j] + s(arr, i, j - 1));}public static int s(int[] arr, int i, int j) {if (i == j) {return 0;//后手沒有牌可以拿}return Math.min(f(arr, i + 1, j), f(arr, i, j - 1));//要讓對方拿最小的值}public static int win2(int[] arr) {if (arr == null || arr.length == 0) {return 0;}int[][] f = new int[arr.length][arr.length];int[][] s = new int[arr.length][arr.length];for (int j = 0; j < arr.length; j++) {f[j][j] = arr[j];for (int i = j - 1; i >= 0; i--) {f[i][j] = Math.max(arr[i] + s[i + 1][j], arr[j] + s[i][j - 1]);s[i][j] = Math.min(f[i + 1][j], f[i][j - 1]);}}return Math.max(f[0][arr.length - 1], s[0][arr.length - 1]);}public static void main(String[] args) {int[] arr = { 1, 9, 1 };System.out.println(win1(arr));System.out.println(win2(arr));}}

N皇后問題

思路

  • 假設先前一個皇后的位置是（a，b），那么再次擺一個皇后的位置是（c，d），因為是從上往下執行，因此可以保證每個皇后之間不共行

  • 通過比對b和d判定皇后之間是否共列

  • 通過比對|c-a|==|d-b|來判定是否處于一個斜線上

代碼

package class08;public class Code09_NQueens {public static int num1(int n) {if (n < 1) {return 0;}// record[0] ?  record[1]  ?  record[2]int[] record = new int[n]; // record[i] -> i行的皇后，放在了第幾列return process1(0, record, n);}// 潛臺詞：record[0..i-1]的皇后，任何兩個皇后一定都不共行、不共列，不共斜線// 目前來到了第i行// record[0..i-1]表示之前的行，放了的皇后位置// n代表整體一共有多少行// 返回值是，擺完所有的皇后，合理的擺法有多少種public static int process1(int i, int[] record, int n) {if (i == n) { // 終止行return 1;}int res = 0;for (int j = 0; j < n; j++) { // 當前行在i行，嘗試i行所有的列  -> j// 當前i行的皇后，放在j列，會不會和之前(0..i-1)的皇后，不共行共列或者共斜線，// 如果是，認為有效// 如果不是，認為無效if (isValid(record, i, j)) {record[i] = j;res += process1(i + 1, record, n);}}return res;}// record[0..i-1]你需要看，record[i...]不需要看// 返回i行皇后，放在了j列，是否有效public static boolean isValid(int[] record, int i, int j) {for (int k = 0; k < i; k++) { // 之前的某個k行的皇后if (j == record[k] || Math.abs(record[k] - j) == Math.abs(i - k)) {return false;}}return true;}// 請不要超過32皇后問題，如果類型改為long，則可以計算64皇后問題public static int num2(int n) {if (n < 1 || n > 32) {//throw new RuntimeException("問題太大，難以計算")；//運行錯誤：不用try catch 和 拋出聲明//預期錯誤：使用try catch ，比如，將異常捕獲，然后告訴使用者，輸入類型出錯 return 0;}int limit = n == 32 ? -1 : (1 << n) - 1;return process2(limit, 0, 0, 0);}//優化版本 遞歸使用、使用二進制類型計算// colLim 列的限制，1的位置不能放皇后，0的位置可以// leftDiaLim 左斜線的限制，1的位置不能放皇后，0的位置可以// rightDiaLim 右斜線的限制，1的位置不能放皇后，0的位置可以public static int process2(int limit, int colLim, int leftDiaLim,int rightDiaLim) {if (colLim == limit) { // base casereturn 1;}// 所有候選皇后的位置，都在pos上int pos = limit & (~(colLim | leftDiaLim | rightDiaLim));int mostRightOne = 0;int res = 0;while (pos != 0) {mostRightOne = pos & (~pos + 1);pos = pos - mostRightOne;res += process2(limit, colLim | mostRightOne,(leftDiaLim | mostRightOne) << 1,(rightDiaLim | mostRightOne) >>> 1);}return res;}public static void main(String[] args) {int n = 14;long start = System.currentTimeMillis();System.out.println(num2(n));long end = System.currentTimeMillis();System.out.println("cost time: " + (end - start) + "ms");start = System.currentTimeMillis();System.out.println(num1(n));end = System.currentTimeMillis();System.out.println("cost time: " + (end - start) + "ms");}
}

?

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

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

相關文章

rtsp和sdp

rtsp和sdp

RTSP 是由Realnetwork 和Netscape共同提出的如何有效地在IP網絡上傳輸流媒體數據的應用層協議 。 實時流協議&#xff08;RTSP&#xff09;建立并控制一個或幾個時間同步的連續流媒體&#xff0c;如音頻和視頻。盡管連續媒體流與控制流交叉是可能的&#xff0c;RTSP本身并不發…
閱讀更多...
使用javascript實現對于chineseocr的API調用

使用javascript實現對于chineseocr的API調用

ChineseOCR在線API 網頁地址 界面 提供多種接口調用方式&#xff0c;比如在線調用、Javascript api調用、curl api調用和python api調用四種方式&#xff0c;本次使用javascript api調用的方式進行OCR識別在線Javascript工具 在線工具網頁鏈接在線Base64 轉化工具 在線工具…
閱讀更多...
移動流媒體業務的技術與標準

移動流媒體業務的技術與標準

1 引言 　　流媒體業務是從Internet上發展起來的一種多媒體應用&#xff0c;指使用流&#xff08;Streaming&#xff09;方式在網絡上傳輸的多媒體文件&#xff0c;包括音頻、視頻和動畫等。 　　流媒體傳輸技術的主要特點是以流&#xff08;streaming&#xff09;的形式進行多…
閱讀更多...
使用python實現對于chineseocr的API調用

使用python實現對于chineseocr的API調用

ChineseOCR在線API 網頁鏈接 界面 提供多種接口調用方式&#xff0c;比如在線調用、Javascript api調用、curl api調用和python api調用四種方式&#xff0c;本次使用javascript api調用的方式進行OCR識別在線Base64 轉化工具 Base64在線小工具代碼修改 新增一個變量fill_w…
閱讀更多...
UDP穿透NAT

UDP穿透NAT

NAT(Network AddressTranslators)&#xff0c;網絡地址轉換&#xff1a; 網絡地址轉換是在IP地址日益缺乏的情況下產生的&#xff0c;它的主要目的就是為了能夠地址重用。NAT分為兩大類&#xff0c;基本的NAT和NAPT(Network Address/Port Translator)。 最開始NAT是運行在路由器…
閱讀更多...
算法入門篇十 圖

算法入門篇十 圖

圖的存儲方式 臨接表臨接矩陣 表達 點集/邊集有向圖/無向圖 Graph&#xff08;大結構就是圖&#xff09;&#xff08;包含點集合和邊集合&#xff09; import java.util.HashMap; import java.util.HashSet;public class Graph {public HashMap<Integer, Node> nodes;…
閱讀更多...
SDP協議 學習筆記

SDP協議 學習筆記

SDP:Session Description ProtocolSDP格式:Session descriptionv (protocolversion)o (owner/creatorand session identifier)s (sessionname)i* (sessioninformation)u* (URI ofdescription)e* (emailaddress)p* (phonenumber)c*(connection information - not required if in…
閱讀更多...
以太坊私有鏈 使用dev模式

以太坊私有鏈 使用dev模式

dev 使用dev模式&#xff0c;創建一個管理員賬號&#xff0c;控制挖礦&#xff0c;將證明機制改為POA啟動dev模式&#xff0c;需要重新創建一個文件夾&#xff0c;重新搭建私有鏈條 命令 mkdir myDevChain cd myDevChain geth --datadir . --dev console 2>output.log 實…
閱讀更多...
超文本傳輸協議

超文本傳輸協議

超文本傳輸協議 超文本傳輸協議超文件傳輸協定(HTTP&#xff0c;HyperTextTransfer Protocol)是因特網上應用最為廣泛的一種網絡傳輸協定。所有的WWW文件都必須遵守這個標準。設計HTTP最初的目的是為了提供一種發布和接收HTML頁面的方法。 目錄 介紹請求信息請求方法安全方法超…
閱讀更多...
以太坊區塊鏈 JSON-RPC

以太坊區塊鏈 JSON-RPC

RPC定義 以太坊客戶端提供了API和一組遠程調用的&#xff08;RPC&#xff09;命令&#xff0c;這些命令被編碼成json的格式&#xff0c;被叫做JSON-RPC-API。本質上&#xff0c;JSON-RPC API就是一個接口&#xff0c;允許我們編寫的程序使用以太坊客戶端作為網關&#xff0c;訪…
閱讀更多...
利用MFC調用libvlc.dll作一個簡單的播放器

利用MFC調用libvlc.dll作一個簡單的播放器

簡單介紹MFC調用libvlc.dll作一個簡單的播放器&#xff0c;拋磚引玉&#xff0c;各位VC達人繼續深入研究&#xff0c;Jeremiah對VC確實不太感興趣&#xff0c;所以就不做太深入的研究了。2009.10.29修改&#xff1a;加入clip_children屬性設置。參開第1步。環境&#xff1a; …
閱讀更多...
對于以太坊虛擬機 （EVM）及其相關知識的講解

對于以太坊虛擬機 （EVM）及其相關知識的講解

以太坊虛擬機&#xff08;EVM&#xff09; EVM是智能合約的運行環境作為區塊驗證協議的一部分&#xff0c;參與網絡的每個節點都會運行EVM&#xff0c;審查節點會檢查驗證正在驗證的區塊中列出的交易&#xff0c;并運行EVM中交易觸發的代碼EVM是沙盒封裝的&#xff0c;并且是完…
閱讀更多...
對于以太坊的Solidity語言介紹

對于以太坊的Solidity語言介紹

Solidity是什么 Solidity是一門面向合約的、為實現智能合約而創建的高級編程語言&#xff0c;主要目的是為了在以太坊虛擬機&#xff08;EVM&#xff09;上運行Solidity是靜態語言&#xff0c;支持繼承、庫和復雜的用戶定義等特性內含的類型除了常見的編程語言中的標準類型&am…
閱讀更多...
live555 接收rtsp視頻流流程分析

live555 接收rtsp視頻流流程分析

live555 接收rtsp視頻流流程分析 RTSP交互流程 C表示RTSP客戶端&#xff0c;S表示RTSP服務端 ① C->S: OPTIONrequest //詢問S有哪些方法可用 S->C: OPTION response //S回應信息中包括提供的所有可用方法 ② C->S: DESCRIBErequest //要求得到S…
閱讀更多...
使用Remix編寫Solidity語言的小例子

使用Remix編寫Solidity語言的小例子

設置數值/取數值/加法運算 講解 uint默認使用256位數的整型view表示這個函數僅僅對于數據僅僅是讀取&#xff0c;沒有修改操作returns(uint )&#xff0c;如果單純指定uint&#xff0c;返回的是函數體內的return值&#xff0c;如果包含uint sum,uint SAD_a&#xff0c;那么返…
閱讀更多...
RTP協議棧簡介

RTP協議棧簡介

流媒體指的是在網絡中使用流技術傳輸的連續時基媒體&#xff0c;其特點是在播放前不需要下載整個文件&#xff0c;而是采用邊下載邊播放的方式&#xff0c;它是視頻會議、IP電話等應用場合的技術基礎。RTP是進行實時流媒體傳輸的標準協議和關鍵技術&#xff0c;本文介紹如何在L…
閱讀更多...
深入理解Solidity

深入理解Solidity

Solidity源文件布局 pragma&#xff08;版本雜注&#xff09; 用于指定源文件的版本&#xff0c;表明編譯器的版本&#xff0c;例如 pragma solidity ^0.4.0^用于指代版本號需要大于0.4.0但是不可以超過大的層級&#xff0c;必須小于0.5.0也可以使用大于等于小于來指定版本 i…
閱讀更多...
H264 流媒體 編碼匯總

H264 流媒體 編碼匯總

實時傳輸協議&#xff08;RTP&#xff09;和實時控制協議&#xff08;RTCP&#xff09; RTP是一種提供端對端傳輸服務的實時傳輸協議&#xff0c;用來支持在單目標廣播和多目標廣播網絡服務中傳輸實時數據&#xff0c;而實時數據的傳輸則由RTCP協議來監視和控制。 RTP定義在RFC…
閱讀更多...
使用多線程的方式調用chineseocr_API

使用多線程的方式調用chineseocr_API

ChineseOCR在線API 網頁鏈接 界面 提供多種接口調用方式&#xff0c;比如在線調用、Javascript api調用、curl api調用和python api調用四種方式&#xff0c;本次使用javascript api調用的方式進行OCR識別代碼 import glob import base64 import os import requests import …
閱讀更多...
開源好代碼 音視頻

開源好代碼 音視頻

VirtualDub 一、簡介 圖1VirtualDub主界面 VirtualDub是一款開源的音視頻捕獲、處理軟件。VirtualDub也可稱為一款多媒體編輯軟件&#xff0c;因為它包含了多媒體輸入、編輯、處理、輸出等各個環節&#xff0c;但是作者并未將它定位為一款多媒體編輯軟件&#xff08;參見官網&a…
閱讀更多...
最新文章

Copyright @ 2022~2023