劍指 offer
- 在一個二維數(shù)組中，每一行都按照從左到右遞增的順序排序烦感，每一列都按照從上到下遞增的順序排序巡社。請完成一個函數(shù)，輸入這樣的一個二維數(shù)組和一個整數(shù)手趣，判斷數(shù)組中是否含有該整數(shù)晌该。
function Find(target, array){
var rowCount = array.length - 1, i, j;
for(i=rowCount,j=0; i >= 0 && j < array[i].length;){
if(target == array[i][j]){
return true;
}else if(target > array[i][j]){
j++;
continue;
}else if(target < array[i][j]){
i--;
continue;
}
}
return false;
}
- 請實現(xiàn)一個函數(shù)，將一個字符串中的空格替換成“%20”绿渣。例如朝群，當字符串為We Are Happy.則經(jīng)過替換之后的字符串為We%20Are%20Happy。
function replaceSpace(str){
return str.replace(/ /g, '%20');
}
- 輸入一個鏈表中符，從尾到頭打印鏈表每個節(jié)點的值姜胖。
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function printListFromTailToHead(head){
if(!head){
return 0;
} else {
var arr = new Array();
var curr = head;
while(curr){
arr.push(curr.val);
curr = curr.next;
}
return arr.reverse();
}
}
- 輸入某二叉樹的前序遍歷和中序遍歷的結果，請重建出該二叉樹淀散。假設輸入的前序遍歷和中序遍歷的結果中都不含重復的數(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.length == 0 || vin.length == 0){
return null;
};
var index = vin.indexOf(pre[0]);
var left = vin.slice(0,index);
var right = vin.slice(index+1);
var node = new TreeNode(vin[index]);
node.left = reConstructBinaryTree(pre.slice(1,index+1),left);
node.right = reConstructBinaryTree(pre.slice(index+1),right);
return node;
}
- 用兩個棧來實現(xiàn)一個隊列慢蜓，完成隊列的Push和Pop操作亚再。 隊列中的元素為int類型。
var stack1 = [];
var stack2 = [];
function push(node){
stack1.push(node);
}
function pop(){
var temp = stack1.pop();
while(temp){
stack2.push(temp);
temp = stack1.pop();
}
var result = stack2.pop();
temp = stack2.pop();
while(temp){
stack1.push(temp);
temp = stack2.pop();
}
return result;
}
- 把一個數(shù)組最開始的若干個元素搬到數(shù)組的末尾胀瞪，我們稱之為數(shù)組的旋轉(zhuǎn)针余。 輸入一個非遞減排序的數(shù)組的一個旋轉(zhuǎn)，輸出旋轉(zhuǎn)數(shù)組的最小元素凄诞。 例如數(shù)組{3,4,5,1,2}為{1,2,3,4,5}的一個旋轉(zhuǎn)，該數(shù)組的最小值為1忍级。 NOTE：給出的所有元素都大于0帆谍，若數(shù)組大小為0，請返回0轴咱。
function minNumberInRotateArray(rotateArray){
var len = rotateArray.length;
if(len === 0){
return 0;
}
return Math.min.apply(null,rotateArray);
}
- 大家都知道斐波那契數(shù)列汛蝙，現(xiàn)在要求輸入一個整數(shù)n，請你輸出斐波那契數(shù)列的第n項朴肺。n<=39
function Fibonacci(n){
var a = 1, b = 1, temp;
if(n <= 0) return 0;
for(var i = 2; i <= n; i++){
temp = b;
b = a + b;
a = temp;
}
return a;
}
- 一只青蛙一次可以跳上1級臺階窖剑，也可以跳上2級。求該青蛙跳上一個n級的臺階總共有多少種跳法戈稿。
function jumpFloor(number){
if(number < 1){
return 0;
}
if(number === 1){
return 1;
}
if(number === 2){
return 2;
}
var temp = 0, a = 1, b = 2;
for(var i = 3; i <= number; i++){
temp = a + b;
a = b;
b = temp;
}
return temp;
}
- 一只青蛙一次可以跳上1級臺階西土，也可以跳上2級……它也可以跳上n級。求該青蛙跳上一個n級的臺階總共有多少種跳法鞍盗。
function jumpFloorII(number){
return Math.pow(2, number - 1);
}
- 我們可以用21的小矩形橫著或者豎著去覆蓋更大的矩形需了。請問用n個21的小矩形無重疊地覆蓋一個2*n的大矩形，總共有多少種方法般甲？
function rectCover(number){
var a = 1, b = 2, temp;
if(number <= 0){
return 0;
}
if(number === 1){
return 1;
}
if(number === 2){
return 2
}
for(var i = 3; i <= number; i++){
temp = a + b;
a = b;
b = temp;
}
return temp;
}
- 輸入一個整數(shù)肋乍，輸出該數(shù)二進制表示中1的個數(shù)。其中負數(shù)用補碼表示敷存。
function NumberOf1(n){
if(n < 0){
n = n >>> 0;
}
var arr = n.toString(2).split('');
return arr.reduce(function(a,b){
return b === "1" ? a + 1 : a;
},0);
}
- 給定一個double類型的浮點數(shù)base和int類型的整數(shù)exponent墓造。求base的exponent次方。
function Power(base, exponent){
return Math.pow(base, exponent);
}
- 輸入一個整數(shù)數(shù)組锚烦，實現(xiàn)一個函數(shù)來調(diào)整該數(shù)組中數(shù)字的順序觅闽，使得所有的奇數(shù)位于數(shù)組的前半部分，所有的偶數(shù)位于位于數(shù)組的后半部分挽牢，并保證奇數(shù)和奇數(shù)谱煤，偶數(shù)和偶數(shù)之間的相對位置不變。
function reOrderArray(array){
var result = [];
var even = [];
array.forEach(function(item){
if((item & 1) === 1){
result.push(item);
} else {
even.push(item);
}
});
return result.concat(even);
}
- 輸入一個鏈表禽拔，輸出該鏈表中倒數(shù)第k個結點刘离。
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function FindKthToTail(head, k){
if(!head || k <= 0){
return null;
}
var i = head, j = head;
while(--k){
j = j.next;
if(!j){
return null;
}
}
while(j.next){
i = i.next;
j = j.next;
}
j = null;
return i;
}
- 輸入一個鏈表室叉，反轉(zhuǎn)鏈表后，輸出鏈表的所有元素硫惕。
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function ReverseList(pHead){
var newHead, temp;
if(!pHead){
return null;
}
if(pHead.next === null){
return pHead;
} else {
newHead = ReverseList(pHead.next);
}
temp = pHead.next;
temp.next = pHead;
pHead.next = null;
temp = null;
return newHead;
}
- 輸入兩個單調(diào)遞增的鏈表茧痕，輸出兩個鏈表合成后的鏈表，當然我們需要合成后的鏈表滿足單調(diào)不減規(guī)則恼除。
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function Merge(pHead1, pHead2){
if(!pHead1){
return pHead2 ? pHead2 : null
} else if(!pHead2){
return pHead1;
}
// debugger;
var curr1 = pHead1;
var curr2 = pHead2;
var result = new ListNode(-1);
var curr = result;
while(curr1 && curr2){
if(curr1.val < curr2.val){
curr.next = curr1;
curr1 = curr1.next;
} else{
curr.next = curr2;
curr2 = curr2.next;
}
curr = curr.next;
}
if(curr1){
curr.next = curr1;
}
if(curr2){
curr.next = curr2;
}
//防止內(nèi)存泄露
curr = result.next;
result.next = null;
result = curr;
curr = curr1 = curr2 = null;
return result;
}
- 輸入兩棵二叉樹A踪旷，B，判斷B是不是A的子結構豁辉。（ps：我們約定空樹不是任意一個樹的子結構）
function HasSubtree(pRoot1, pRoot2){
if(pRoot1 == null || pRoot2 == null){
return false;
}
if(isSubTree(pRoot1, pRoot2)){
return true;
} else{
return HasSubtree(pRoot1.left, pRoot2) || HasSubtree(pRoot1.right, pRoot2);
}
function isSubTree(pRoot1, pRoot2){
if(pRoot2 == null) return true;
if(pRoot1 == null) return false;
if(pRoot1.val === pRoot2.val){
return isSubTree(pRoot1.left, pRoot2.left) && isSubTree(pRoot1.right, pRoot2.right);
} else {
return false;
}
}
}
- 操作給定的二叉樹令野，將其變換為源二叉樹的鏡像。
function Mirror(root){
if(!root){
return null;
}
var temp = root.left;
root.left = root.right;
root.right = temp;
if(root.left){
Mirror(root.left);
}
if(root.right){
Mirror(root.right);
}
}
- 輸入一個矩陣徽级，按照從外向里以順時針的順序依次打印出每一個數(shù)字气破，例如，如果輸入如下矩陣： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 則依次打印出數(shù)字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.
function printMatrix(matrix){
if(!matrix || !matrix.length) return null;
var result = [];
var rows = matrix.length, cols = matrix[0].length;
var len = rows * cols;
var i = 0, j = 0;
var circle = 0;
while(1){
while(j < cols - circle){
result.push(matrix[i][j]);
j++;
}
if(result.length === len) break;
j--, i++;
while(i < rows - circle){
result.push(matrix[i][j])
i++;
}
if(result.length === len) break;
i--, j--;
while(j >= circle){
result.push(matrix[i][j]);
j--;
}
if(result.length === len) break;
j++, i--;
circle++;
while(i >= circle){
result.push(matrix[i][j])
i--;
}
if(result.length === len) break;
j++, i++;
}
return result;
}
- 定義棧的數(shù)據(jù)結構餐抢，請在該類型中實現(xiàn)一個能夠得到棧最小元素的min函數(shù)现使。
var stack = [];
function push(node){
stack.push(node);
}
function pop(){
return stack.pop();
}
function top(){
return stack[stack.length - 1];
}
function min(){
return Math.min.apply(null, stack);
}
- 輸入兩個整數(shù)序列，第一個序列表示棧的壓入順序旷痕，請判斷第二個序列是否為該棧的彈出順序碳锈。假設壓入棧的所有數(shù)字均不相等。例如序列1,2,3,4,5是某棧的壓入順序欺抗，序列4售碳，5,3,2,1是該壓棧序列對應的一個彈出序列，但4,3,5,1,2就不可能是該壓棧序列的彈出序列佩迟。（注意：這兩個序列的長度是相等的）
function IsPopOrder(pushV, popV){
if(!pushV.length || !popV.length){
return false;
}
var temp = [];
var popIndex = 0;
var len = pushV.length;
for(var i = 0; i < len; i++){
temp.push(pushV[i]);
while(temp.length && temp[temp.length - 1] === popV[popIndex]){
temp.pop();
popIndex++;
}
}
return temp.length === 0;
}
- 從上往下打印出二叉樹的每個節(jié)點团滥，同層節(jié)點從左至右打印。
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function PrintFromTopToBottom(root){
if (!root) {
return [];
}
var queue = [];
queue.push(root);
var result = [];
while (queue.length) {
var temp = queue.shift();
result.push(temp.val);
if (temp.left) {
queue.push(temp.left);
}
if (temp.right) {
queue.push(temp.right);
}
}
return result;
}
- 輸入一個整數(shù)數(shù)組报强，判斷該數(shù)組是不是某二叉搜索樹的后序遍歷的結果灸姊。如果是則輸出Yes,否則輸出No。假設輸入的數(shù)組的任意兩個數(shù)字都互不相同秉溉。(測試用例用的是 false/true, 不是題目中的 'Yes'/'No')
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function VerifySquenceOfBST(sequence) {
var len = sequence.length
if (!len) {
return false;
}
return adjustSequence(0, len - 1);
function adjustSequence(start, end){
if (start >= end) {
return true;
}
var root = sequence[end];
for(var i = start; i < end && sequence[i] < root; i++);
var index = i;
for (i = i + 1; i < end; i++) {
if (sequence[i] < root) {
return false;
}
}
return adjustSequence(start, index - 1) && (adjustSequence(index, end - 1));
}
}
- 輸入一顆二叉樹和一個整數(shù)力惯，打印出二叉樹中結點值的和為輸入整數(shù)的所有路徑。路徑定義為從樹的根結點開始往下一直到葉結點所經(jīng)過的結點形成一條路徑召嘶。
/* function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
} */
function FindPath(root, expectNumber){
var temp = [];
// var found = false;
var result = [];
dfs(root, 0);
return result;
function dfs(root, sum){
// debugger;s
if(!root){
return;
}
temp.push(root.val);
sum += root.val;
if(!root.left && !root.right && sum === expectNumber){
result.push(temp.concat());
}
if(root.left){
dfs(root.left, sum);
}
if(root.right){
dfs(root.right, sum);
}
temp.pop();
return;
}
}
- 輸入一個復雜鏈表（每個節(jié)點中有節(jié)點值狰挡，以及兩個指針夸溶，一個指向下一個節(jié)點验辞，另一個特殊指針指向任意一個節(jié)點）虏两，返回結果為復制后復雜鏈表的head。（注意铛只，輸出結果中請不要返回參數(shù)中的節(jié)點引用埠胖，否則判題程序會直接返回空）
function Clone(pHead)
{
if(!pHead){
return null;
}
var head = new RandomListNode(pHead.label);
head.random = pHead.random;
head.next = Clone(pHead.next);
return head;
}
- 輸入一棵二叉搜索樹糠溜，將該二叉搜索樹轉(zhuǎn)換成一個排序的雙向鏈表。要求不能創(chuàng)建任何新的結點直撤，只能調(diào)整樹中結點指針的指向非竿。
將左子樹構成雙向鏈表，返回的是左子樹的尾結點谋竖，將其連接到root的左邊红柱；
將右子樹構成雙向鏈表，將其追加到root結點之后蓖乘，并返回尾結點锤悄；
向左遍歷返回的鏈表至頭結點處，即為所求雙向鏈表的首結點嘉抒。
function Convert(pRootOfTree){
if(!pRootOfTree) {
return null;
}
var lastNode = null;
lastNode = ConvertNode(pRootOfTree);
var head = lastNode;
while(head && head.left) {
head = head.left;
}
return head;
function ConvertNode(node){
if(!node){
return;
}
if(node.left) {
lastNode = ConvertNode(node.left);
}
node.left = lastNode;
if(lastNode){
lastNode.right = node;
}
lastNode = node;
if(node.right){
lastNode = ConvertNode(node.right);
}
return lastNode;
}
}
- 輸入一個字符串,按字典序打印出該字符串中字符的所有排列铁蹈。例如輸入字符串a(chǎn)bc,則打印出由字符a,b,c所能排列出來的所有字符串a(chǎn)bc,acb,bac,bca,cab和cba。
function Permutation(str){
if(!str || str.length === 0){
return [];
}
var result = [];
var arr = str.split('');
var temp = '';
ordering(arr);
result = result.filter(function(item, index){ //去重
return result.indexOf(item) === index;
});
return result;
function ordering(tempArr){
if(tempArr.length === 0){
result.push(temp);
return;
}
for(var i = 0; i < tempArr.length; i++){
temp += tempArr[i];
insideArr = tempArr.concat();
insideArr.splice(i,1);
ordering(insideArr);
temp = temp.substring(0, temp.length - 1); //回溯
}
}
}
- 數(shù)組中有一個數(shù)字出現(xiàn)的次數(shù)超過數(shù)組長度的一半众眨，請找出這個數(shù)字。例如輸入一個長度為9的數(shù)組{1,2,3,2,2,2,5,4,2}容诬。由于數(shù)字2在數(shù)組中出現(xiàn)了5次娩梨，超過數(shù)組長度的一半，因此輸出2览徒。如果不存在則輸出0狈定。
function MoreThanHalfNum_Solution(numbers){
if(!numbers || numbers.length === 0){
return 0;
}
var arr = [];
var len = numbers.length, index;
for(var i = 0; i < len; i++){
var index = numbers[i];
arr[index] !== undefined ? arr[index]++ : arr[index] = 1;
}
var index = -1;
var arrLen = arr.length;
var max = -Infinity;
for(var i = 0; i < arrLen; i++){
if(!arr[i]) continue;
max = arr[i] > max ? (index = i, arr[i]) : max;
}
return max > len / 2 ? index : 0;
}
- 輸入n個整數(shù)，找出其中最小的K個數(shù)习蓬。例如輸入4,5,1,6,2,7,3,8這8個數(shù)字纽什，則最小的4個數(shù)字是1,2,3,4。
function GetLeastNumbers_Solution(input, k){
if(!input || input.length < k){
return [];
}
return input.sort(function(a,b){
return a - b
}).slice(0, k);
}
- HZ偶爾會拿些專業(yè)問題來忽悠那些非計算機專業(yè)的同學躲叼。今天測試組開完會后,他又發(fā)話了:在古老的一維模式識別中,常常需要計算連續(xù)子向量的最大和,當向量全為正數(shù)的時候,問題很好解決芦缰。但是,如果向量中包含負數(shù),是否應該包含某個負數(shù),并期望旁邊的正數(shù)會彌補它呢？例如:{6,-3,-2,7,-15,1,2,2},連續(xù)子向量的最大和為8(從第0個開始,到第3個為止)枫慷。你會不會被他忽悠兹美佟？(子向量的長度至少是1)
function FindGreatestSumOfSubArray(array){
if (array.length < 0)
return 0;
var sum = array[0],
tempsum = array[0];
for (var i = 1; i < array.length; i++) {
tempsum = tempsum < 0 ? array[i] : tempsum + array[i];
sum = tempsum > sum ? tempsum : sum;
}
return sum;
}
- 求出113的整數(shù)中1出現(xiàn)的次數(shù),并算出1001300的整數(shù)中1出現(xiàn)的次數(shù)或听？為此他特別數(shù)了一下1~13中包含1的數(shù)字有1探孝、10、11誉裆、12顿颅、13因此共出現(xiàn)6次,但是對于后面問題他就沒轍了。ACMer希望你們幫幫他,并把問題更加普遍化,可以很快的求出任意非負整數(shù)區(qū)間中1出現(xiàn)的次數(shù)足丢。
function NumberOf1Between1AndN_Solution(n)
{
if (n < 0) return 0;
var ones = 0;
var arr = [];
while(n){
arr.push(n);
n--;
}
return arr.join('').replace(/[^1]+/g,'').length;
}
- 輸入一個正整數(shù)數(shù)組粱腻，把數(shù)組里所有數(shù)字拼接起來排成一個數(shù)庇配，打印能拼接出的所有數(shù)字中最小的一個。例如輸入數(shù)組{3栖疑，32讨永，321}，則打印出這三個數(shù)字能排成的最小數(shù)字為321323遇革。
function PrintMinNumber(numbers)
{
if(!numbers || numbers.length === 0){
return [];
}
var result = [];
var temp = '';
ordering(numbers);
result = result.map(Number).reduce(function(min , a){ //最小值
return min < a ? min : a;
}, Infinity);
return result;
function ordering(tempArr){
var innerLen = 0;
if(tempArr.length === 0){
result.push(temp);
return;
}
for(var i = 0; i < tempArr.length; i++){
innerLen = tempArr[i].toString().length;
temp += tempArr[i];
insideArr = tempArr.concat();
insideArr.splice(i,1);
ordering(insideArr);
temp = temp.substring(0, temp.length - innerLen); //回溯
}
}
}
- 把只包含因子2卿闹、3和5的數(shù)稱作丑數(shù)（Ugly Number）。例如6萝快、8都是丑數(shù)锻霎，但14不是，因為它包含因子7揪漩。 習慣上我們把1當做是第一個丑數(shù)旋恼。求按從小到大的順序的第N個丑數(shù)。
function GetUglyNumber_Solution(index) {
if (index === 0) return 0;
var uglyNum = [1];
var factor2 = 0, factor3 = 0, factor5 = 0;
for (var i = 1; i < index; i++) {
uglyNum[i] = Math.min(uglyNum[factor2] * 2, uglyNum[factor3] * 3, uglyNum[factor5] * 5);
if (uglyNum[i] === uglyNum[factor2] * 2) factor2++;
if (uglyNum[i] === uglyNum[factor3] * 3) factor3++;
if (uglyNum[i] === uglyNum[factor5] * 5) factor5++;
}
return uglyNum[index - 1];
}
- 在一個字符串(1<=字符串長度<=10000奄容，全部由字母組成)中找到第一個只出現(xiàn)一次的字符,并返回它的位置
function FirstNotRepeatingChar(str){
if(!str || !str.length){
return -1;
}
var hash = {};
var tempArr = str.split('');
var unique = [];
var len = str.length, temp;
for(var i = 0; i < len; i++){
temp = tempArr[i];
if(hash[temp]){
hash[temp].push(i);
} else {
hash[temp] = [i];
}
}
for(var key in hash){
if(hash.hasOwnProperty(key)){
if(hash[key].length === 1){
unique.push(hash[key].pop());
}
}
}
return Math.min.apply(null, unique);
}
- 在數(shù)組中的兩個數(shù)字冰更，如果前面一個數(shù)字大于后面的數(shù)字，則這兩個數(shù)字組成一個逆序?qū)Π豪铡］斎胍粋€數(shù)組,求出這個數(shù)組中的逆序?qū)Φ目倲?shù)P蜀细。并將P對1000000007取模的結果輸出。 即輸出P%1000000007
由于時間空間復雜度的限制戈盈，js 貌似無法完成這個題奠衔，所以使用 c++ 完成。
class Solution {
public:
long long InversePairsCore(vector<int> &data, vector<int>©, int start, int end){
if(start == end){
copy[start] = data[start];
return 0;
}
int length = (end - start) / 2;
long long left = InversePairsCore(copy, data, start, start + length);
long long right = InversePairsCore(copy, data, start + length + 1, end);
int i = start + length;
int j = end;
int indexCopy = end;
long long count=0;
while(i >= start && j >= start + length + 1){
if(data[i] > data[j]){
copy[indexCopy--] = data[i--];
count += j - start - length;
} else {
copy[indexCopy--] = data[j--];
}
}
for(; i >= start; --i)
copy[indexCopy--] = data[i];
for(;j >= start + length + 1; --j)
copy[indexCopy--] = data[j];
return left + right + count;
}
int InversePairs(vector<int> data) {
int length = data.size();
if(length <= 0)
return 0;
vector<int> copy;
for(int i = 0; i < length; i++)
copy.push_back(data[i]);
long long count = InversePairsCore(data, copy, 0, length-1);
copy.clear();
return count % 1000000007;
}
};
- 輸入兩個鏈表塘娶，找出它們的第一個公共結點归斤。
function FindFirstCommonNode(pHead1, pHead2){
if(!pHead1 || !pHead2){
return null;
}
var len1 = getLength(pHead1);
var len2 = getLength(pHead2);
var lenDiff = len1 - len2;
var curr1 = pHead1;
var curr2 = pHead2;
if(len2 > len1){
curr1 = pHead2;
curr2 = pHead1;
lenDiff = len2 - len1;
}
for(var i = 0; i < lenDiff; ++i)
curr1 = curr1.next;
while(curr1 && curr2 && curr1 != curr2){
curr1 = curr1.next;
curr2 = curr2.next;
}
return curr1;
function getLength(node){
var len = 0;
curr = node;
while(curr){
len++;
curr = curr.next;
}
return len;
}
}
- 統(tǒng)計一個數(shù)字在排序數(shù)組中出現(xiàn)的次數(shù)。
function GetNumberOfK(data, k){
return data.reduce(function(count, a){
return a === k ? count+1 :count;
}, 0);
}
- 輸入一棵二叉樹刁岸，求該樹的深度脏里。從根結點到葉結點依次經(jīng)過的結點（含根、葉結點）形成樹的一條路徑难捌，最長路徑的長度為樹的深度膝宁。
function TreeDepth(pRoot){
if(!pRoot){
return 0;
}
var depth = 0;
var currDepth = 0;
dfs(pRoot);
return depth;
function dfs(node){
if(!node){
depth = depth > currDepth ? depth : currDepth;
return;
}
currDepth++;
dfs(node.left);
dfs(node.right);
currDepth--;
}
}
- 輸入一棵二叉樹，判斷該二叉樹是否是平衡二叉樹根吁。
function IsBalanced_Solution(pRoot){
if(!pRoot){
return true;
}
var left = TreeDepth(pRoot.left);
var right = TreeDepth(pRoot.right);
var diff = left - right;
if(diff > 1 || diff < -1)
return false;
return IsBalanced_Solution(pRoot.left) && IsBalanced_Solution(pRoot.right);
function TreeDepth(pRoot){
if(!pRoot){
return 0;
}
var depth = 0;
var currDepth = 0;
dfs(pRoot);
return depth;
function dfs(node){
if(!node){
depth = depth > currDepth ? depth : currDepth;
return;
}
currDepth++;
dfs(node.left);
dfs(node.right);
currDepth--;
}
}
}
- 一個整型數(shù)組里除了兩個數(shù)字之外员淫，其他的數(shù)字都出現(xiàn)了兩次。請寫程序找出這兩個只出現(xiàn)一次的數(shù)字击敌。
function FindNumsAppearOnce(array){
if (!array || array.length < 2)
return [];
return array.sort().join(',').replace(/(\d+),\1/g,"").replace(/,+/g,',').replace(/^,|,$/, '').split(',').map(Number);
}
- 小明很喜歡數(shù)學,有一天他在做數(shù)學作業(yè)時,要求計算出9~16的和,他馬上就寫出了正確答案是100介返。但是他并不滿足于此,他在想究竟有多少種連續(xù)的正數(shù)序列的和為100(至少包括兩個數(shù))。沒多久,他就得到另一組連續(xù)正數(shù)和為100的序列:18,19,20,21,22。現(xiàn)在把問題交給你,你能不能也很快的找出所有和為S的連續(xù)正數(shù)序列? Good Luck!
function FindContinuousSequence(sum){
if(sum < 3){
return [];
}
var small = 1, big = 2;
var mid = (1 + sum) / 2;
var curr = small + big;
var result = [];
while(small < mid){
if(curr === sum){
pushSeq(small, big);
}
while(curr > sum && small < mid){
curr -= small;
small++;
if(curr === sum){
pushSeq(small, big);
}
}
big++;
curr += big;
}
result.sort(function(a,b){return a[0] - b[0];});
return result;
function pushSeq(small, big){
var temp = [];
for(var i = small; i <= big; i++){
temp.push(i);
}
result.push(temp);
}
}
- 輸入一個遞增排序的數(shù)組和一個數(shù)字S圣蝎，在數(shù)組中查找兩個數(shù)刃宵，是的他們的和正好是S，如果有多對數(shù)字的和等于S徘公，輸出兩個數(shù)的乘積最小的牲证。
function FindNumbersWithSum(array, sum){
if(!array || !array.length){
return [];
}
var result = [];
var product = [];
var head = 0, tail = array.length - 1;
while(head < tail){
var curr = array[head] + array[tail];
if(curr === sum){
result.push([array[head], array[tail]]);
product.push(array[head] * array[tail]);
tail--;
head++;
} else if(curr > sum){
tail--;
} else {
head++;
}
}
if(result.length === 0){
return [];
}
var min = Math.min.apply(null, product);
var index = product.indexOf(min);
return result[index];
}
- 匯編語言中有一種移位指令叫做循環(huán)左移（ROL），現(xiàn)在有個簡單的任務关面，就是用字符串模擬這個指令的運算結果坦袍。對于一個給定的字符序列S，請你把其循環(huán)左移K位后的序列輸出等太。例如捂齐，字符序列S=”abcXYZdef”,要求輸出循環(huán)左移3位后的結果，即“XYZdefabc”缩抡。是不是很簡單奠宜？OK，搞定它瞻想！
function LeftRotateString(str, n){
if(!str){
return "";
}
var len = str.length;
n = n % len;
var left = str.slice(0,n);
var right = str.slice(n);
return right + left;
}
- 叛拐妫客最近來了一個新員工Fish，每天早晨總是會拿著一本英文雜志蘑险，寫些句子在本子上榴都。同事Cat對Fish寫的內(nèi)容頗感興趣，有一天他向Fish借來翻看漠其，但卻讀不懂它的意思。例如竿音，“student. a am I”和屎。后來才意識到，這家伙原來把句子單詞的順序翻轉(zhuǎn)了春瞬，正確的句子應該是“I am a student.”柴信。Cat對一一的翻轉(zhuǎn)這些單詞順序可不在行，你能幫助他么宽气？
function ReverseSentence(str){
return str.split(' ').reverse().join(' ');
}
- LL今天心情特別好,因為他去買了一副撲克牌,發(fā)現(xiàn)里面居然有2個大王,2個小王(一副牌原本是54張_)...他隨機從中抽出了5張牌,想測測自己的手氣,看看能不能抽到順子,如果抽到的話,他決定去買體育彩票,嘿嘿Ｋ娉！！“紅心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是順子.....LL不高興了,他想了想,決定大\小 王可以看成任何數(shù)字,并且A看作1,J為11,Q為12,K為13萄涯。上面的5張牌就可以變成“1,2,3,4,5”(大小王分別看作2和4),“So Lucky!”绪氛。LL決定去買體育彩票啦。 現(xiàn)在,要求你使用這幅牌模擬上面的過程,然后告訴我們LL的運氣如何涝影。為了方便起見,你可以認為大小王是0枣察。
function IsContinuous(numbers){
if(!numbers || numbers.length < 1){
return false;
}
var len = numbers.length;
numbers.sort(function(a,b){return a - b;});
var zeros = 0, gaps = 0;
for(var i = 0; i < len && numbers[i] == 0; i++){
zeros++;
}
var small = zeros, big = small + 1;
while(big < len){
if(numbers[small] == numbers[big]){
return false;
}
gaps += numbers[big] - numbers[small] - 1;
small = big++;
}
return gaps <= zeros;
}
- 每年六一兒童節(jié),牛客都會準備一些小禮物去看望孤兒院的小朋友,今年亦是如此。HF作為判蚰浚客的資深元老,自然也準備了一些小游戲臂痕。其中,有個游戲是這樣的:首先,讓小朋友們圍成一個大圈。然后,他隨機指定一個數(shù)m,讓編號為0的小朋友開始報數(shù)猿涨。每次喊到m-1的那個小朋友要出列唱首歌,然后可以在禮品箱中任意的挑選禮物,并且不再回到圈中,從他的下一個小朋友開始,繼續(xù)0...m-1報數(shù)....這樣下去....直到剩下最后一個小朋友,可以不用表演,并且拿到盼胀客名貴的“名偵探柯南”典藏版(名額有限哦!!_)。請你試著想下,哪個小朋友會得到這份禮品呢叛赚？(注：小朋友的編號是從0到n-1)
function LastRemaining_Solution(n, m){
if(n < 1 || m < 1){
return -1;
}
var last = 0;
for(var i = 2; i <= n; i++){
last = (last + m) % i;
}
return last;
}
- 求1+2+3+...+n澡绩，要求不能使用乘除法、for红伦、while英古、if、else昙读、switch召调、case等關鍵字及條件判斷語句（A?B:C）。
function Sum_Solution(n){
var sum = 0;
plus(n);
return sum;
function plus(num){
sum += num;
num > 0 && plus(--num);
}
}
- 寫一個函數(shù)蛮浑，求兩個整數(shù)之和唠叛，要求在函數(shù)體內(nèi)不得使用+、-沮稚、*艺沼、/四則運算符號。
function Add(num1, num2){
var sum, carry;
do{
sum = num1 ^ num2;
carry = (num1 & num2) << 1;
num1 = sum;
num2 = carry;
}while(num2 != 0);
return num1;
}
- 將一個字符串轉(zhuǎn)換成一個整數(shù)蕴掏，要求不能使用字符串轉(zhuǎn)換整數(shù)的庫函數(shù)障般。 數(shù)值為0或者字符串不是一個合法的數(shù)值則返回0
function StrToInt(str){
if(str.length === 0){
return 0;
}
var format = str.match(/^(\+?|-?)(\d+)$/);
if(!format){
return 0;
}
var num = 0;
var temp = format[2];
var base = 1;
var flag = format[1];
for(var i = temp.length - 1; i >= 0; i--){
num += parseInt(temp[i]) * base;
base *= 10;
}
return flag === '-' ? num * (-1) : num;
}
- 在一個長度為n的數(shù)組里的所有數(shù)字都在0到n-1的范圍內(nèi)。 數(shù)組中某些數(shù)字是重復的盛杰，但不知道有幾個數(shù)字是重復的挽荡。也不知道每個數(shù)字重復幾次。請找出數(shù)組中任意一個重復的數(shù)字即供。 例如定拟，如果輸入長度為7的數(shù)組{2,3,1,0,2,5,3}，那么對應的輸出是第一個重復的數(shù)字2逗嫡。
function duplicate(numbers, duplication){
if(!numbers || !numbers.length){
return false;
}
var len = numbers.length;
for(var i = 0; i < len; i++){
var curr = numbers[i];
if(numbers.indexOf(curr) !== i){
duplication[0] = curr;
return true;
}
}
return false;
}
- 給定一個數(shù)組A[0,1,...,n-1],請構建一個數(shù)組B[0,1,...,n-1],其中B中的元素B[i]=A[0]A[1]...A[i-1]A[i+1]...A[n-1]青自。不能使用除法。
function multiply(array){
if(!array || !array.length){
return [];
}
var result = [];
var len1 = array.length, len2 = result.length;
result[0] = 1;
for(var i = 1; i < len1; i++){
result[i] = array[i - 1] * result[i - 1];
}
var temp = 1;
for(var i = len1 - 2; i >= 0;--i){
temp *=array[i + 1];
result[i] *= temp
}
return result;
}
- 請實現(xiàn)一個函數(shù)用來匹配包括'.'和''的正則表達式驱证。模式中的字符'.'表示任意一個字符延窜，而''表示它前面的字符可以出現(xiàn)任意次（包含0次）。 在本題中抹锄，匹配是指字符串的所有字符匹配整個模式需曾。例如，字符串"aaa"與模式"a.a"和"abaca"匹配，但是與"aa.a"和"ab*a"均不匹配
function match(s, pattern)
{
if(s === "" && pattern === ""){
return true;
}
if(!pattern || pattern.length === 0){
return false
}
var reg = new RegExp('^' + pattern + '$');
return reg.test(s);
}
- 請實現(xiàn)一個函數(shù)用來判斷字符串是否表示數(shù)值（包括整數(shù)和小數(shù)）呆万。例如商源，字符串"+100","5e2","-123","3.1416"和"-1E-16"都表示數(shù)值。 但是"12e","1a3.14","1.2.3","+-5"和"12e+4.3"都不是谋减。
function isNumeric(s){
var reg = /^[+-]?(?:(\d+)(\.\d+)?|(\.\d+))([eE][+-]?\d+)?$/;
return reg.test(s);
}
- 請實現(xiàn)一個函數(shù)用來找出字符流中第一個只出現(xiàn)一次的字符牡彻。例如，當從字符流中只讀出前兩個字符"go"時出爹，第一個只出現(xiàn)一次的字符是"g"庄吼。當從該字符流中讀出前六個字符“google"時，第一個只出現(xiàn)一次的字符是"l"严就。
function Init(){
streamNums = []; //定義一個全局變量, 不用var
streamNumsLen = 256; //定義一個全局變量, 不用var
streamNumsIndex = 0; //定義一個全局變量, 不用var
for(var i = 0; i < streamNumsLen; i++){
streamNums[i] = -1;
}
}
function Insert(ch){
var code = ch.charCodeAt();
if(streamNums[code] == -1){
streamNums[code] = streamNumsIndex;
} else if(streamNums[code] >= 0){
streamNums[code] = -2;
}
streamNumsIndex++;
}
function FirstAppearingOnce(){
result = '';
var ch = '';
var minIndex = Infinity;
for(var i = 0; i < streamNumsLen; i++){
if(streamNums[i] >= 0 && streamNums[i] < minIndex){
ch = String.fromCharCode(i);
minIndex = streamNums[i];
}
}
return ch == "" ? '#' : ch;
}
- 一個鏈表中包含環(huán)总寻，請找出該鏈表的環(huán)的入口結點。
/*function ListNode(x){
this.val = x;
this.next = null;
}*/
function EntryNodeOfLoop(pHead){
if(!pHead){
return null;
}
var meeting = meetingNode(pHead);
if(!meeting){
return null;
}
var nodeLoop = 1;
var node1 = meeting;
while(node1.next != meeting){
node1 = node1.next;
nodeLoop++;
}
node1 = pHead;
for(var i = 0; i < nodeLoop; i++){
node1 = node1.next;
}
var node2 = pHead;
while(node1 != node2){
node1 = node1.next;
node2 = node2.next;
}
return node1;
function meetingNode(node){
if(!node || !node.next){
return null;
}
var slow = node.next;
var fast = slow.next;
while(fast && slow){
if(fast === slow){
return fast;
}
slow = slow.next;
fast = fast.next;
if(fast){
fast = fast.next;
}
}
return null;
}
}
- 在一個排序的鏈表中梢为，存在重復的結點渐行，請刪除該鏈表中重復的結點，重復的結點不保留铸董，返回鏈表頭指針祟印。 例如，鏈表1->2->3->3->4->4->5 處理后為 1->2->5
function deleteDuplication(pHead){
if(!pHead){
return null;
}
var tempHead = new ListNode(-1);
tempHead.next = pHead;
var preNode = tempHead;
var curr1 = preNode.next;
var curr2 = curr1.next;
while(curr1){
if(!curr2 || curr2.val !== curr1.val){
if(curr1.next !== curr2){
clear(curr1, curr2);
preNode.next = curr2;
} else {
preNode = curr1;
}
curr1 = curr2;
if(curr2){
curr2 = curr2.next;
}
} else {
if(curr2){
curr2 = curr2.next;
}
}
}
return tempHead.next;
function clear(node, stop){
var temp;
while(node !== stop){
temp = node.next;
node.next = null;
node = temp;
}
}
}
- 給定一個二叉樹和其中的一個結點粟害，請找出中序遍歷順序的下一個結點并且返回蕴忆。注意，樹中的結點不僅包含左右子結點悲幅，同時包含指向父結點的指針套鹅。
function GetNext(pNode){
if (!pNode){
return pNode;
}
if (pNode.right){
pNode = pNode.right;
while (pNode.left) {
pNode = pNode.left;
}
return pNode;
} else if(pNode.next && pNode.next.left == pNode){
return pNode.next;
} else if(pNode.next && pNode.next.right == pNode){
while(pNode.next && pNode.next.left != pNode){
pNode = pNode.next ;
}
return pNode.next;
} else {
return pNode.next;
}
}
- 請實現(xiàn)一個函數(shù)，用來判斷一顆二叉樹是不是對稱的汰具。注意芋哭，如果一個二叉樹同此二叉樹的鏡像是同樣的，定義其為對稱的郁副。
function isSymmetrical(pRoot){
if(!pRoot){
return true;
}
return symmetrical(pRoot, pRoot);
function symmetrical(node1,node2){
if(!node1 && !node2)
return true;
if(!node1 || !node2)
return false;
if(node1.val != node2.val)
return false;
return symmetrical(node1.left, node2.right) && symmetrical(node1.right, node2.left);
}
}
- 請實現(xiàn)一個函數(shù)按照之字形打印二叉樹，即第一行按照從左到右的順序打印豌习，第二層按照從右至左的順序打印存谎，第三行按照從左到右的順序打印，其他行以此類推肥隆。
function Print(pRoot) {
var res = [];
if(!pRoot){
return res;
}
var que = [];
que.push(pRoot);
var flag = false;
while(que.length > 0){
var vec = [];
var len = que.length;
for(var i = 0; i < len; i++){
var tmp = que.shift(); //front
vec.push(tmp.val);
if(tmp.left)
que.push(tmp.left);
if(tmp.right)
que.push(tmp.right);
}
if(flag){
vec.reverse();
}
res.push(vec);
flag = !flag;
}
return res;
}
- 從上到下按層打印二叉樹既荚，同一層結點從左至右輸出。每一層輸出一行栋艳。
function Print(pRoot) {
var res = [];
if(!pRoot){
return res;
}
var que = [];
que.push(pRoot);
while(que.length > 0){
var vec = [];
var len = que.length;
for(var i = 0; i < len; i++){
var tmp = que.shift(); //front
vec.push(tmp.val);
if(tmp.left)
que.push(tmp.left);
if(tmp.right)
que.push(tmp.right);
}
res.push(vec);
}
return res;
}
- 請實現(xiàn)兩個函數(shù)恰聘，分別用來序列化和反序列化二叉樹
function Serialize(pNode) {
var str = [];
ser(pNode);
for(var i = str.length - 1; i >= 0; i--){
if(str[i] !== '#'){
break;
}
str.pop();
}
return str.join();
function ser(node){
if(!node){
str.push('#');
return;
}
str.push(node.val);
ser(node.left);
ser(node.right);
}
}
function Deserialize(str) {
var index = -1;
var len = str.length;
if(index >= len){
return null;
}
var arr = str.split(",");
var head = des();
return head;
function des(node){
index++;
if(arr[index] && arr[index] !== '#'){
var temp = new TreeNode(arr[index]);
node = temp;
node.left = des();
node.right = des();
}
return node;
}
}
- 給定一顆二叉搜索樹，請找出其中的第k大的結點。例如晴叨， 5 / \ 3 7 /\ /\ 2 4 6 8 中凿宾，按結點數(shù)值大小順序第三個結點的值為4。
function KthNode(pRoot, k){
if(!pRoot || !k){
return null;
}
return KthCore(pRoot);
function KthCore(node){
var target = null;
if(node.left){
target = KthCore(node.left);
}
if(!target){
if(k === 1)
target = node;
k--;
}
if(!target && node.right)
target = KthCore(node.right);
return target;
}
}
- 如何得到一個數(shù)據(jù)流中的中位數(shù)兼蕊？如果從數(shù)據(jù)流中讀出奇數(shù)個數(shù)值初厚，那么中位數(shù)就是所有數(shù)值排序之后位于中間的數(shù)值。如果從數(shù)據(jù)流中讀出偶數(shù)個數(shù)值孙技，那么中位數(shù)就是所有數(shù)值排序之后中間兩個數(shù)的平均值产禾。
var arr = [];
function Insert(num){
arr.push(num);
arr.sort(function(a,b){
return a - b;
});
return arr;
}
function GetMedian(){
var mid = Math.floor(arr.length / 2);
if((arr.length & 1) === 0){
var n1 = arr[mid];
var n2 = arr[mid - 1];
return (n1 + n2) / 2;
} else {
return arr[mid]
}
}
- 給定一個數(shù)組和滑動窗口的大小，找出所有滑動窗口里數(shù)值的最大值牵啦。例如亚情，如果輸入數(shù)組{2,3,4,2,6,2,5,1}及滑動窗口的大小3，那么一共存在6個滑動窗口哈雏，他們的最大值分別為{4,4,6,6,6,5}楞件； 針對數(shù)組{2,3,4,2,6,2,5,1}的滑動窗口有以下6個： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}僧著， {2,3,[4,2,6],2,5,1}履因， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}盹愚， {2,3,4,2,6,[2,5,1]}栅迄。
function maxInWindows(num, size){
if(!num || num.length === 0){
return null;
}
var max = [];
if(num.length >= size && size >= 1){
var index = [];
for(var i = 0; i < size; ++i){
while(index.length > 0 && num[i] >= num[index[index.length - 1]])
index.pop();
index.push(i);
}
for(var i = size; i < num.length; ++i){
max.push(num[index[0]]);
while(index.length > 0 && num[i] >= num[index[index.length - 1]])
index.pop();
if(index.length > 0 && index[0] <= i - size)
index.shift();
index.push(i);
}
max.push(num[index[0]]);
}
return max;
}
- 請設計一個函數(shù)，用來判斷在一個矩陣中是否存在一條包含某字符串所有字符的路徑皆怕。路徑可以從矩陣中的任意一個格子開始毅舆，每一步可以在矩陣中向左，向右愈腾，向上憋活，向下移動一個格子。如果一條路徑經(jīng)過了矩陣中的某一個格子虱黄，則該路徑不能再進入該格子悦即。 例如 a b c e s f c s a d e e 矩陣中包含一條字符串"bcced"的路徑，但是矩陣中不包含"abcb"路徑橱乱，因為字符串的第一個字符b占據(jù)了矩陣中的第一行第二個格子之后辜梳，路徑不能再次進入該格子。
function hasPath(matrix, rows, cols, path){
var visited = [];
for(var i = 0; i < rows * cols; i++){
visited[i] = false;
}
var pathLen = 0;
try{
for(var i = 0; i < rows; i++){
for(var j = 0; j < cols; j++){
if(core(i,j)){
return true;
}
}
}
} finally {
visited.length = 0;
}
return false;
function core(row, col){
if(path.length === pathLen){
return true;
}
var hasPath = false;
if(row >= 0 && row < rows && col >= 0 && col < cols && matrix[row * cols + col] === path[pathLen] && !visited[row * cols + col]){
pathLen++;
visited[row * cols + col] = true;
hasPath = core(row - 1, col)+ core(row, col - 1)
+ core(row + 1, col) + core(row, col + 1);
if(!hasPath){
pathLen--;
visited[row * cols + col] = false;
}
}
return hasPath;
}
}
- 地上有一個m行和n列的方格泳叠。一個機器人從坐標0,0的格子開始移動作瞄，每一次只能向左，右危纫，上宗挥，下四個方向移動一格乌庶，但是不能進入行坐標和列坐標的數(shù)位之和大于k的格子。 例如契耿，當k為18時瞒大，機器人能夠進入方格（35,37），因為3+5+3+7 = 18宵喂。但是糠赦，它不能進入方格（35,38），因為3+5+3+8 = 19锅棕。請問該機器人能夠達到多少個格子拙泽？
function movingCount(threshold, rows, cols){
var visited = [];
for(var i = 0; i < rows * cols; ++i)
visited[i] = false;
var count = movingCountCore(0, 0);
visited.length = 0;
return count;
function getDigitSum(number){
var sum = 0;
while(number > 0){
sum += number % 10;
number = Math.floor(number / 10);
}
return sum;
}
function check(row, col){
if(row >= 0 && row < rows && col >= 0 && col < cols && getDigitSum(row) + getDigitSum(col) <= threshold && !visited[row * cols + col])
return true;
return false;
}
function movingCountCore(row, col){
var count = 0;
if(check(row, col)) {
visited[row * cols + col] = true;
count = 1 + movingCountCore(row - 1, col)
+ movingCountCore(row, col - 1)
+ movingCountCore(row + 1, col)
+ movingCountCore(row, col + 1);
}
return count;
}
}
手動測試框架
- 二叉樹構造
function TreeNode(x) {
this.val = x;
this.left = null;
this.right = null;
}
function Tree(arr, node, num = 1){
if(!arr || arr.length === 0){
return new TreeNode(null);
}
node = node || new TreeNode(arr[num - 1]);
var curr = node;
if(num * 2 - 1 < arr.length && arr[num * 2 - 1]){
curr.left = new TreeNode(arr[num * 2 - 1]);
Tree(arr, curr.left, num * 2);
}
if(num * 2 < arr.length && arr[num * 2]){
curr.right = new TreeNode(arr[num * 2]);
Tree(arr, curr.right, num * 2 + 1);
}
return node;
}
// 根據(jù)數(shù)組生成二叉樹
var tree = new Tree([3,2,4,8,7,null,10,null,null,5,9]);
console.log(tree);
- 單向鏈表構造
function ListNode(x){
this.val = x;
this.next = null;
}
function LinkedList(arr){
if(!arr || arr.length === 0){
return new ListNode(null);
}
var head = new ListNode(arr[0]);
var len = arr.length;
var curr = head;
for(var i = 1; i < len; i++){
var temp = new ListNode(arr[i]);
curr.next = temp;
curr = curr.next;
}
return head;
}
var ll = new LinkedList([3,2,4,8,7,10,5,9]);
console.log(ll);
- 牛客網(wǎng) Node.js 多行輸入測試 (如果不能運行請更新瀏覽器來支持 es6 語法)
(function(){
/* Todo: This Array contains the input lines in sequence. Each of the elements is like a line of input. */
var test_lines =['5','1 2 3 3 5','3','1 2 1','2 4 5','3 5 3']; // Do not change the name of this array if you don't like bugs.
/****************************************************************
Todo: Add your code here including the callback function of event 'rl.on()' and
global variables except the statements and definitions of 'readline' and 'rl'.
*****************************************************************/
/* global variables here */
var lines = 1;
/* callback function of 'rl.on()' */
function main(line) { // Do not change the name of this function if you don't like bugs.
var str = line.trim();
console.log('lines',lines++,':',str);
}
/**************** End of Your Code *****************/
(function(){
var test_len = test_lines.length;
var test_it = gen(test_lines);
var test_val = test_it.next();
while(test_len){
main(test_val.value);
test_val = test_it.next();
test_len--;
}
function* gen(test_lines){
var len = test_lines.length;
var i = 0;
while(len){
yield test_lines[i];
i++;
}
}
}())
}());
