摘要:拆分鏈表,將和進行拆分,保證原始鏈表不受影響。要求不能創建任何新的結點,只能調整樹中結點指針的指向。輸入一個字符串長度不超過可能有字符重復字符只包括大小寫字母。遞歸,記錄一個當前節點的位置,該位置指向最后一個節點時記錄一次排列。
1.復雜鏈表的復制
輸入一個復雜鏈表(每個節點中有節點值,以及兩個指針,一個指向下一個節點,另一個特殊指針指向任意一個節點),返回結果為復制后復雜鏈表的head。(注意,輸出結果中請不要返回參數中的節點引用)
思路拆分成三步
1.復制一份鏈表放在前一個節點后面,即根據原始鏈表的每個節點N創建N,把N直接放在N的next位置,讓復制后的鏈表和原始鏈表組成新的鏈表。
2.給復制的鏈表random賦值,即N`.random=N.random.next。
3.拆分鏈表,將N`和N進行拆分,保證原始鏈表不受影響。
代碼</>復制代碼
function Clone(pHead) {
if (pHead === null) {
return null;
}
cloneNodes(pHead);
cloneRandom(pHead);
return reconnetNodes(pHead);
}
function cloneNodes(pHead) {
var current = pHead;
while (current) {
var cloneNode = {
label: current.label,
next: current.next
};
current.next = cloneNode;
current = cloneNode.next;
}
}
function cloneRandom(pHead) {
var current = pHead;
while (current) {
var cloneNode = current.next;
if (current.random) {
cloneNode.random = current.random.next;
} else {
cloneNode.random = null;
}
current = cloneNode.next;
}
}
function reconnetNodes(pHead) {
var cloneHead = pHead.next;
var cloneNode = pHead.next;
var current = pHead;
while (current) {
current.next = cloneNode.next;
current = cloneNode.next;
if (current) {
cloneNode.next = current.next;
cloneNode = current.next;
} else {
cloneNode.next = null;
}
}
return cloneHead;
}
2.二叉搜索樹轉換為雙向鏈表
輸入一棵二叉搜索樹,將該二叉搜索樹轉換成一個排序的雙向鏈表。要求不能創建任何新的結點,只能調整樹中結點指針的指向。
思路1.排序的雙向鏈表-中序遍歷二叉樹
2.記錄鏈表的最后一個節點
3.每次遍歷:設置樹節點的left和鏈表的right進行鏈接,鏈接成功后當前節點成為鏈表的末尾節點,并返回。
代碼</>復制代碼
function Convert(pRootOfTree) {
var lastNode = null;
lastNode = convertToList(pRootOfTree, lastNode);
while (lastNode && lastNode.left) {
lastNode = lastNode.left;
}
return lastNode;
}
function convertToList(treeNode, lastNode) {
if (!treeNode) {
return null;
}
if (treeNode.left) {
lastNode = convertToList(treeNode.left, lastNode);
}
treeNode.left = lastNode;
if (lastNode) {
lastNode.right = treeNode;
}
lastNode = treeNode;
if (treeNode.right) {
lastNode = convertToList(treeNode.right, lastNode);
}
return lastNode;
}
3.字符串的排列
輸入一個字符串,按字典序打印出該字符串中字符的所有排列。例如輸入字符串abc,則打印出由字符a,b,c所能排列出來的所有字符串abc,acb,bac,bca,cab和cba。
思路</>復制代碼
輸入一個字符串,長度不超過9(可能有字符重復),字符只包括大小寫字母。
1.把字符串分成兩部分,第一個字符和后面的字符
2.整個字符串的全排列等于:第一個字符+后面字符的全排列,第一個字符和后面的字符諸葛交換。
第一個字符+后面字符的全排列3.除了第一個字符其他字符的全排列等于:第二個字符+后面字符的全排列。
3.遞歸,記錄一個當前節點的位置,該位置指向最后一個節點時記錄一次排列。
代碼</>復制代碼
function Permutation(str) {
var result = [];
if (!str) {
return result;
}
var array = str.split("");
permutate(array, 0, result);
result.sort();
return [... new Set(result)];
}
function permutate(array, index, result) {
if (array.length - 1 === index) {
result.push(array.join(""));
}
for (let i = index; i < array.length; i++) {
swap(array, index, i);
permutate(array, index + 1, result);
swap(array, i, index);
}
}
function swap(arr, i, j) {
[arr[i], arr[j]] = [arr[j], arr[i]];
}
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/102074.html
摘要:題目題目描述大家都知道斐波那契數列,現在要求輸入一個整數,請你輸出斐波那契數列的第項從開始,第項為。基本思路這道題在劍指中實際是當作遞歸的反例來說的。明顯也符合斐波那契數列的規律矩形覆蓋我們可以用的小矩形橫著或者豎著去覆蓋更大的矩形。 題目 題目描述大家都知道斐波那契數列,現在要求輸入一個整數n,請你輸出斐波那契數列的第n項(從0開始,第0項為0)。 基本思路 這道題在劍指offer中...
摘要:劍指系列刷題第一篇題目來源數組中數字出現的次數大家可以去測試一下自己的代碼博主碼云鏈接文章目錄前言題目描述解題思路解題代碼前言這是劍指系列刷題第一篇文章,大家可以互相學習一下。其中的兩個單身狗是和。 ...
閱讀 520·2023-04-26 00:33
閱讀 3544·2021-11-24 09:39
閱讀 2933·2021-09-22 15:34
閱讀 2322·2019-08-23 18:07
閱讀 2917·2019-08-23 18:04
閱讀 3704·2019-08-23 16:06
閱讀 2900·2019-08-23 15:27
閱讀 1619·2019-08-23 14:32