中文亚洲精品无码_熟女乱子伦免费_人人超碰人人爱国产_亚洲熟妇女综合网

當(dāng)前位置: 首頁 > news >正文

重慶網(wǎng)上找工作哪個(gè)網(wǎng)站好十大騙子教育培訓(xùn)機(jī)構(gòu)

重慶網(wǎng)上找工作哪個(gè)網(wǎng)站好,十大騙子教育培訓(xùn)機(jī)構(gòu),網(wǎng)站開發(fā)工資,沒有基礎(chǔ)怎么學(xué)網(wǎng)站建設(shè)文章目錄 前言什么是決策樹1. 全排列1.1 題目要求1.2 做題思路1.3 代碼實(shí)現(xiàn) 2. 子集2.1 題目要求2.2 做題思路2.3 代碼實(shí)現(xiàn) 3. 找出所有子集的異或總和再求和3.1 題目要求3.2 做題思路3.3 代碼實(shí)現(xiàn) 4. 全排列II4.1 題目要求4.2 做題思路4.3 代碼實(shí)現(xiàn) 前言 前面我們通過幾個(gè)題目…

在這里插入圖片描述

文章目錄

  • 前言
  • 什么是決策樹
  • 1. 全排列
    • 1.1 題目要求
    • 1.2 做題思路
    • 1.3 代碼實(shí)現(xiàn)
  • 2. 子集
    • 2.1 題目要求
    • 2.2 做題思路
    • 2.3 代碼實(shí)現(xiàn)
  • 3. 找出所有子集的異或總和再求和
    • 3.1 題目要求
    • 3.2 做題思路
    • 3.3 代碼實(shí)現(xiàn)
  • 4. 全排列II
    • 4.1 題目要求
    • 4.2 做題思路
    • 4.3 代碼實(shí)現(xiàn)

前言

前面我們通過幾個(gè)題目基本了解了解決遞歸類問題的基本思路和步驟,相信大家對(duì)于遞歸多多少少有了更加深入的了解。那么本篇文章我將為大家分享結(jié)合決策樹來解決遞歸、搜索和回溯相關(guān)的問題。

什么是決策樹

決策樹是一種基本的分類與回歸方法。在分類問題中,決策樹通過構(gòu)建一棵樹形圖來對(duì)數(shù)據(jù)進(jìn)行分類。樹的每個(gè)節(jié)點(diǎn)表示一個(gè)特征屬性,每個(gè)分支代表一個(gè)特征屬性上的判斷條件,每個(gè)葉節(jié)點(diǎn)代表一個(gè)類別。在回歸問題中,決策樹可以預(yù)測一個(gè)實(shí)數(shù)值。

下面是一個(gè)簡單的決策樹:
在這里插入圖片描述
知道了什么是決策樹,下面我們將運(yùn)用決策樹來解決實(shí)際問題。

1. 全排列

https://leetcode.cn/problems/permutations/

1.1 題目要求

給定一個(gè)不含重復(fù)數(shù)字的數(shù)組 nums ,返回其 所有可能的全排列 。你可以 按任意順序 返回答案。

示例 1:

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

示例 2:

輸入:nums = [0,1]
輸出:[[0,1],[1,0]]

示例 3:

輸入:nums = [1]
輸出:[[1]]

提示:

1 <= nums.length <= 6
-10 <= nums[i] <= 10
nums 中的所有整數(shù) 互不相同
class Solution {public List<List<Integer>> permute(int[] nums) {}
}

1.2 做題思路

相信大家肯定做過跟排列相關(guān)的問題,就是三個(gè)人坐座位的問題。第一座位可以坐A、B、C 任何一個(gè)人,如果第一個(gè)座位坐的是 A 的話,那么第二個(gè)位子 A 就不能再坐了,第二個(gè)位子就只能在 B、C 之間選擇了,如果 B 選擇了第二個(gè)位子,那么第三個(gè)位置就只能 C 選擇了。所以這個(gè)問題通過決策樹來體現(xiàn)的話就是這樣的:

在這里插入圖片描述
但是上面的圖我們會(huì)發(fā)現(xiàn)這幾種情況會(huì)有重復(fù)的情況,那么我們?nèi)绾魏Y選掉這些重復(fù)的情況呢?可以使用一個(gè)標(biāo)記數(shù)組來記錄已經(jīng)選擇過的元素,當(dāng)下一次選擇的時(shí)候就選擇這個(gè)標(biāo)記數(shù)組中沒有被選擇的剩下的元素的其中一個(gè)。這道題目跟上面的例子的思路是一樣的,這里我就不為大家再畫一個(gè)圖了。

那么這道題使用代碼的思想該如何解決呢?每次遞歸我們還是將數(shù)組中的所有元素都給列舉出來,不過我們需要根據(jù)標(biāo)記數(shù)組中元素的使用情況來選擇是否可以選擇這個(gè)元素,如果某個(gè)元素沒有被選擇,那么這次就選擇這個(gè)元素,將這個(gè)元素標(biāo)記為已使用,然后繼續(xù)遞歸,當(dāng)當(dāng)前情況列舉完成之后就需要恢復(fù)現(xiàn)場,當(dāng)路徑集合中記錄的元素的個(gè)數(shù)和數(shù)組中的元素個(gè)數(shù)相同的時(shí)候,就說明一種情況已經(jīng)列舉完成,就可以將當(dāng)前情況添加進(jìn)ret集合中,返回。

1.3 代碼實(shí)現(xiàn)

class Solution {List<Integer> path;List<List<Integer>> ret;boolean[] vis;public List<List<Integer>> permute(int[] nums) {//對(duì)全局變量進(jìn)行初始化path = new ArrayList<>();ret = new ArrayList<>();vis = new boolean[nums.length];dfs(nums);return ret;}private void dfs(int[] nums) {//當(dāng)path中元素的大小等于數(shù)組的大小,就說明一種情況已經(jīng)列舉完成,這事需要我們將當(dāng)前path中的數(shù)據(jù)添加進(jìn)ret中,并且返回if (path.size() == nums.length) {ret.add(new ArrayList<>(path));return;}for (int i = 0; i < nums.length; i++) {if (vis[i] == false) {path.add(nums[i]);//將當(dāng)前元素標(biāo)記為已使用vis[i] = true;//考慮該位置之后的其他元素的選擇dfs(nums);//恢復(fù)現(xiàn)場path.remove(path.size() - 1);vis[i] = false;}}}
}

在這里插入圖片描述

2. 子集

https://leetcode.cn/problems/subsets/

2.1 題目要求

給你一個(gè)整數(shù)數(shù)組 nums ,數(shù)組中的元素 互不相同 。返回該數(shù)組所有可能的子集(冪集)。

解集 不能 包含重復(fù)的子集。你可以按 任意順序 返回解集。

示例 1:

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

示例 2:

輸入:nums = [0]
輸出:[[],[0]]

提示:

1 <= nums.length <= 10
-10 <= nums[i] <= 10
nums 中的所有元素 互不相同
class Solution {public List<List<Integer>> subsets(int[] nums) {}
}

2.2 做題思路

前面全排列中是當(dāng)路徑集合中的元素個(gè)數(shù)和數(shù)組中的元素的個(gè)數(shù)相同的時(shí)候視為一種情況,這道題目就不一樣了,這個(gè)是數(shù)組的子集,也就是說每一種情況的元素的個(gè)數(shù)可能是不一樣的,所以我們路徑集合每新添加一個(gè)元素就可以視為一種情況,就需要將路徑中的元素添加進(jìn)ret集合中,思路跟上一道題目是類似的,都是通過決策樹遞歸來實(shí)現(xiàn)的,但是呢?仔細(xì)看題目可以發(fā)現(xiàn),就是集合[1,2],[2,1]是一種情況,也就是說子集的選擇跟順序無關(guān),那么我們又該如何避免出現(xiàn)重復(fù)的情況呢?

這其實(shí)也不難,想想如果是在數(shù)學(xué)中我們會(huì)怎樣思考?如果當(dāng)前位置我們選擇了某個(gè)元素,那么后面的位置我們就從這個(gè)元素的后面元素中去選擇。

在這里插入圖片描述
所以通過代碼體現(xiàn)的話,就是我們可以使用一個(gè) pos 變量來記錄當(dāng)前位置選擇的元素的下標(biāo),然后下一個(gè)位置選擇元素遞歸的話,我們就從 pos 的下一個(gè)位置開始選擇。

2.3 代碼實(shí)現(xiàn)

class Solution {List<Integer> path;List<List<Integer>> ret;public List<List<Integer>> subsets(int[] nums) {path = new ArrayList<>();ret = new ArrayList<>();dfs(nums, 0)return ret;}private void dfs(int[] nums, int pos) {//進(jìn)入這個(gè)函數(shù)就可以將path中的結(jié)果添加進(jìn)ret中,這樣就可以將空集的情況給考慮上ret.add(new ArrayList<>(path));//循環(huán)的話,就從pos位置開始遍歷for (int i = pos; i < nums.length; i++) {path.add(nums[i]);dfs(nums, i + 1);path.remove(path.size() - 1);}}
}

在這里插入圖片描述

3. 找出所有子集的異或總和再求和

https://leetcode.cn/problems/sum-of-all-subset-xor-totals/

3.1 題目要求

一個(gè)數(shù)組的 異或總和 定義為數(shù)組中所有元素按位 XOR 的結(jié)果;如果數(shù)組為 空 ,則異或總和為 0 。

例如,數(shù)組 [2,5,6] 的 異或總和 為 2 XOR 5 XOR 6 = 1 。
給你一個(gè)數(shù)組 nums ,請(qǐng)你求出 nums 中每個(gè) 子集 的 異或總和 ,計(jì)算并返回這些值相加之 和 。

注意:在本題中,元素 相同 的不同子集應(yīng) 多次 計(jì)數(shù)。

數(shù)組 a 是數(shù)組 b 的一個(gè) 子集 的前提條件是:從 b 刪除幾個(gè)(也可能不刪除)元素能夠得到 a 。

示例 1:

輸入:nums = [1,3]
輸出:6
解釋:[1,3] 共有 4 個(gè)子集:
- 空子集的異或總和是 0 。
- [1] 的異或總和為 1 。
- [3] 的異或總和為 3 。
- [1,3] 的異或總和為 1 XOR 3 = 2 。
0 + 1 + 3 + 2 = 6

示例 2:

輸入:nums = [5,1,6]
輸出:28
解釋:[5,1,6] 共有 8 個(gè)子集:
- 空子集的異或總和是 0 。
- [5] 的異或總和為 5 。
- [1] 的異或總和為 1 。
- [6] 的異或總和為 6 。
- [5,1] 的異或總和為 5 XOR 1 = 4 。
- [5,6] 的異或總和為 5 XOR 6 = 3 。
- [1,6] 的異或總和為 1 XOR 6 = 7 。
- [5,1,6] 的異或總和為 5 XOR 1 XOR 6 = 2 。
0 + 5 + 1 + 6 + 4 + 3 + 7 + 2 = 28

示例 3:

輸入:nums = [3,4,5,6,7,8]
輸出:480
解釋:每個(gè)子集的全部異或總和值之和為 480 。

提示:

1 <= nums.length <= 12
1 <= nums[i] <= 20
class Solution {public int subsetXORSum(int[] nums) {}
}

3.2 做題思路

這道題目跟上面的子集思路基本上沒什么區(qū)別,之不過上面的子集是要求出所有子集的情況,而這道題目是求出所有子集異或之后的總和。因?yàn)樗悸坊靖蟼€(gè)題一樣,所以我們直接來看代碼。

3.3 代碼實(shí)現(xiàn)

class Solution {int path;int ret;public int subsetXORSum(int[] nums) {dfs(nums, 0);return ret;}private void dfs(int[] nums, int pos) {//前面是將集合添加進(jìn)ret中,這里我們是將每種情況加進(jìn)ret中ret += path;for (int i = pos; i < nums.length; i++) {//這里我們不是將新加入的元素加入到path集合中,而是將新加入的元素和之前path元素的異或的結(jié)果異或path ^= nums[i];dfs(nums, i + 1);//恢復(fù)現(xiàn)場(兩個(gè)相同的元素異或,結(jié)果為0)path ^= nums[i];}}
}

在這里插入圖片描述

4. 全排列II

https://leetcode.cn/problems/permutations-ii/

4.1 題目要求

給定一個(gè)可包含重復(fù)數(shù)字的序列 nums ,按任意順序 返回所有不重復(fù)的全排列。

示例 1:

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

示例 2:

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

提示:

1 <= nums.length <= 8
-10 <= nums[i] <= 10
class Solution {public List<List<Integer>> permuteUnique(int[] nums) {}
}

4.2 做題思路

這道題目跟 全排列I 是不一樣的,全排列I 中不存在重復(fù)的元素,但是這道題目中存在重復(fù)的元素,也就是說[1, 1, 2] 和 [1, 1, 2] 是同一個(gè)排列,這不看起來就是同一個(gè)排列嗎?難道還能不同嗎?其實(shí)這里的 1 不是同一個(gè)1,[1(下標(biāo)為0), 1(下標(biāo)為1), 2],[1(下標(biāo)為1), 1(下標(biāo)為0), 2],全排列I 中我們只需要使用一個(gè)標(biāo)記數(shù)組來避免同一個(gè)元素被重復(fù)使用的情況,而這個(gè) 全排列II 中,我們還需要篩選出因元素相同而導(dǎo)致的相同排列的情況。那么如何篩選呢?我們來看個(gè)例子:

在這里插入圖片描述

4.3 代碼實(shí)現(xiàn)

class Solution {List<Integer> path;List<List<Integer>> ret;boolean[] vis;public List<List<Integer>> permuteUnique(int[] nums) {path = new ArrayList<>();ret = new ArrayList<>();vis = new boolean[nums.length];//首先將重復(fù)元素給排序到一起Arrays.sort(nums);dfs(nums);return ret;}private void dfs(int[] nums) {if (path.size() == nums.length) {ret.add(new ArrayList<>(path));return;}for (int i = 0; i < nums.length; i++) {if (vis[i] == false && (i == 0 || (nums[i - 1] != nums[i]) || vis[i - 1] == true)) {path.add(nums[i]);vis[i] = true;dfs(nums);//恢復(fù)現(xiàn)場path.remove(path.size() - 1);vis[i] = false;}}}
}

在這里插入圖片描述

http://www.risenshineclean.com/news/58056.html

相關(guān)文章:

  • 天將建設(shè)集團(tuán)有限公司網(wǎng)站企業(yè)網(wǎng)絡(luò)推廣最簡單方法
  • 做網(wǎng)站建設(shè)最好的公司是seo云優(yōu)化軟件
  • 如何做公司自己的網(wǎng)站首頁seo網(wǎng)站seo
  • 大連b2c網(wǎng)站建設(shè)如何建立網(wǎng)站服務(wù)器
  • 小程序網(wǎng)站開發(fā)運(yùn)行合同網(wǎng)站建設(shè)技術(shù)外包
  • 國建設(shè)委員會(huì)網(wǎng)站上查詢搜索引擎優(yōu)化的完整過程
  • 福州電子商務(wù)網(wǎng)站在線識(shí)別圖片
  • 德州匯澤網(wǎng)站建設(shè)seo發(fā)貼軟件
  • 公司設(shè)計(jì)網(wǎng)站搜索引擎營銷的名詞解釋
  • 禮品網(wǎng)站制作免費(fèi)推廣
  • 網(wǎng)站開發(fā) xmind營銷網(wǎng)站建設(shè)方案
  • 請(qǐng)問網(wǎng)上有沒有比較好的網(wǎng)站可以做照片書的呀?要求質(zhì)量比較好的!品牌推廣方案ppt
  • 商城網(wǎng)站開發(fā)報(bào)價(jià)深圳網(wǎng)絡(luò)推廣培訓(xùn)機(jī)構(gòu)
  • 申請(qǐng)免費(fèi)建站海外seo培訓(xùn)
  • 信譽(yù)好的揚(yáng)中網(wǎng)站建設(shè)app推廣軟件有哪些
  • 四川建設(shè)廳官方網(wǎng)站文件下載企業(yè)網(wǎng)絡(luò)營銷策略
  • p2p網(wǎng)站建設(shè) 上海網(wǎng)店代運(yùn)營騙局
  • 做校園網(wǎng)站 怎么備案百度推廣在哪里能看到
  • 網(wǎng)站商城定制網(wǎng)站建設(shè)蘇州seo營銷
  • 昆明網(wǎng)站開發(fā)多少錢免費(fèi)域名注冊(cè)平臺(tái)
  • 做鞋子有什么好網(wǎng)站好北京seo關(guān)鍵詞排名
  • 關(guān)于做ppt的網(wǎng)站有哪些內(nèi)容杭州百度seo代理
  • 織夢網(wǎng)站文章內(nèi)容模板信息發(fā)布推廣平臺(tái)
  • 能訪問各種網(wǎng)站的瀏覽器seo是什么意思 seo是什么職位
  • 網(wǎng)站開發(fā)tt0546軟文營銷的技巧
  • 網(wǎng)站直播間怎么做2023年9月疫情又開始了嗎
  • 南寧網(wǎng)絡(luò)系統(tǒng)開發(fā)win10優(yōu)化大師是官方的嗎
  • 國外網(wǎng)站入口錦繡大地seo官網(wǎng)
  • 網(wǎng)站的內(nèi)容有哪些內(nèi)容嗎褲子seo標(biāo)題優(yōu)化關(guān)鍵詞
  • 如何在工商局網(wǎng)站做身份確認(rèn)關(guān)鍵詞搜索熱度查詢