摘要:二維數(shù)組中的查找在一個二維數(shù)組中,每一行都按照從左到右遞增的順序排序,每一列都按照從上到下遞增的順序排序。請完成一個函數(shù),輸入這樣的一個二維數(shù)組和一個整數(shù),判斷數(shù)組中是否含有該整數(shù)。例如輸入前序遍歷序列和中序遍歷序列,則重建二叉樹并返回。
1.二維數(shù)組中的查找
在一個二維數(shù)組中,每一行都按照從左到右遞增的順序排序,每一列都按照從上到下遞增的順序排序。請完成一個函數(shù),輸入這樣的一個二維數(shù)組和一個整數(shù),判斷數(shù)組中是否含有該整數(shù)。
function Find(target, array) { var row = array.length; // 行數(shù) var col = array[0].length; // 列數(shù) // 從左下角開始比較 var r = row - 1; var c = 0; while(r >= 0 && c <= col - 1) { // 注意這里有等于號 if (target > array[r][c]) { c++; } else if (target < array[r][c]) { r--; } else { return true; } } return false; } module.exports = { Find : Find };2.替換空格
請實現(xiàn)一個函數(shù),將一個字符串中的空格替換成“%20”。例如,當字符串為We Are Happy.則經(jīng)過替換之后的字符串為We%20Are%20Happy。
function replaceSpace(str) { // write code here return str.replace(/s/g,"%20"); } module.exports = { replaceSpace : replaceSpace };3.從頭到尾打印鏈表
/*function ListNode(x){ this.val = x; this.next = null; }*/ function printListFromTailToHead(head) { var res=[]; while(head){ res.unshift(head.val); head=head.next; } return res; } module.exports = { printListFromTailToHead : printListFromTailToHead };4.重建二叉樹
輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果,請重建出該二叉樹。假設(shè)輸入的前序遍歷和中序遍歷的結(jié)果中都不含重復(fù)的數(shù)字。例如輸入前序遍歷序列{1,2,4,7,3,5,6,8}和中序遍歷序列{4,7,2,1,5,3,8,6},則重建二叉樹并返回。
/* function TreeNode(x) { this.val = x; this.left = null; this.right = null; } */ function reConstructBinaryTree(pre, vin) { if (!pre || pre.length === 0) { return; } var treeNode = { val: pre[0] } for(var i = 0; i < pre.length; i++) { if (vin[i] === pre[0]) { treeNode.left = reConstructBinaryTree(pre.slice(1, i+1), vin.slice(0, i)); treeNode.right = reConstructBinaryTree(pre.slice(i+1),vin.slice(i+1)); } } return treeNode; } module.exports = { reConstructBinaryTree : reConstructBinaryTree };5.用兩個棧實現(xiàn)隊列
用兩個棧來實現(xiàn)一個隊列,完成隊列的Push和Pop操作。 隊列中的元素為int類型
function Stack(){ var arr = []; this.push = function (node){ arr.push(node); return arr; }; this.pop = function(){ return arr.pop(); }; this.isEmpty = function(){ return arr.length === 0; }; } var stack1 = new Stack(); var stack2 = new Stack(); function push(node) { // write code here stack1.push(node); } function pop() { // write code here if(stack1.isEmpty() && stack2.isEmpty()){ throw new Error("empty queue"); } if(stack2.isEmpty()){ while(!stack1.isEmpty()){ stack2.push(stack1.pop()); } } return stack2.pop(); } module.exports = { push : push, pop : pop };6.旋轉(zhuǎn)數(shù)組的最小數(shù)字
function minNumberInarr(arr) { // write code here var left = 0; var right = arr.length-1; var mid = left; if (arr.length == 0) return; while(arr[left] >= arr[right]){ if(right-left == 1){ mid = right; break; } mid = Math.floor((left+right)/2) if(arr[mid] >= arr[left]){ left = mid; } else if(arr[mid] < arr[left]){ right = mid; } else if(arr[mid] == arr[right] && arr[mid] == arr[left]){ return inOrder(arr); } } return arr[mid]; } function inOrder(arr){ var min = arr[0]; for(var i = 0; i7.斐波那契數(shù)列arr[i]){ min = arr[i]; } } return min; }
輸入一個整數(shù)n,請你輸出斐波那契數(shù)列的第n項。
// 遞歸版本: function f(n) { if (n == 0 || n == 1) { return n; } else { return f(n-1) + f(n-2); } } // 動態(tài)規(guī)劃版本: function f(n) { // write code here if (n == 0 || n == 1) { return n; } var f1 = 0; var f2 = 1; var temp; for (var i = 2; i <= n; i++) { temp = f1 + f2; f1 = f2; f2 = temp; } return f2; }8.跳臺階
一只青蛙一次可以跳上1級臺階,也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法。
function jumpFloor(n) { //0,1,2,3,5,8.... if (n < 0) { return; } if (n >=0 && n <= 2) { return n; } var f1 = 1; var f2 = 2; var temp = 0; for (var i = 0; i < n - 2; i++) { temp = f1; f1 = f2; f2 = temp + f1; } return f2; }9.{{BANNED}}跳臺階
一只青蛙一次可以跳上1級臺階,也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法。
// 0 1 2 4 8 16 32 64... function jumpFloorII(number) { if (number < 0) return; if (number >= 0 && number <= 2) return number; return 2 * jumpFloorII(number - 1) }10.矩形覆蓋(不能AC)
我們可以用21的小矩形橫著或者豎著去覆蓋更大的矩形。請問用n個21的小矩形無重疊地覆蓋一個2*n的大矩形,總共有多少種方法?
// 0,1,2,3,5,8,13,21... function rectCover(number) { // write code here if (number < 1) { return 0; } else if (number == 1 || number == 2) { return number; } else { return rectCover(number - 1) + rectCover(number - 2); } }
文章版權(quán)歸作者所有,未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為,您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請注明本文地址:http://specialneedsforspecialkids.com/yun/82178.html
摘要:導(dǎo)航小助手劍指從尾到頭打印鏈表題目詳情解題思路源代碼總結(jié)劍指從尾到頭打印鏈表題目詳情輸入一個鏈表的頭節(jié)點,從尾到頭反過來返回每個節(jié)點的值用數(shù)組返回。時間復(fù)雜度方法先反轉(zhuǎn)鏈表并求長度,在將反轉(zhuǎn)后的鏈表數(shù)據(jù)拷貝至數(shù)組中。 ...
摘要:假設(shè)反轉(zhuǎn)對象節(jié)點為,反轉(zhuǎn)指向的結(jié)點為,反轉(zhuǎn)后指向的結(jié)點為首結(jié)點。當然也可以根據(jù)棧先進后出的特點,使用棧反轉(zhuǎn)鏈表。 ??前面的話?? 大家好!博主開辟了一個新的專欄—...
摘要:面試題從尾到頭打印鏈表輸入一個鏈表,從尾到頭打印鏈表每個節(jié)點的值面試題重建二叉樹輸入某二叉樹的前序遍歷和中序遍歷的結(jié)果,請重建出該二叉樹。例如輸入前序遍歷序列和中序遍歷序列,則重建二叉樹并返回。隊列中的元素為類型。其中負數(shù)用補碼表示。 面試題2 單例(之前有整理,略) 面試題3 二維數(shù)組中的查找 public boolean find(int target, int [][] arra...
閱讀 3782·2021-09-23 11:32
閱讀 2451·2021-09-06 15:01
閱讀 1616·2021-08-18 10:24
閱讀 3450·2019-12-27 11:44
閱讀 3605·2019-08-30 15:52
閱讀 2512·2019-08-30 11:11
閱讀 671·2019-08-29 17:27
閱讀 600·2019-08-29 16:22