1、在一个二维数组中(每个一维数组的长度相同),每一行都按照从左到右递增的顺序排序,每一列都按照从上到下递增的顺序排序。请完成一个函数,输入这样的一个二维数组和一个整数,判断数组中是否含有该整数。
输入
7,[[1,2,8,9],[2,4,9,12],[4,7,10,13],[6,8,11,15]]
返回值
true
解
while(line=readline()){ var index=line.indexOf(","); var left=parseInt(line.substring(0,index)); var right=JSON.parse(line.substring(index+1)); print(Find(left,right)); } function Find(target, array) { // write code here var arr = array; for(var i=0;i<arr.length;i++){ for(var j=0;j<arr[i].length;j++){ if(arr[i][j] == target){ return true; } } } return false; }
2、请实现一个函数,将一个字符串中的每个空格替换成“%20”。例如,当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。
解
//第一种 function replaceSpace(str) { let temp = [] for (let i = 0; i<str.length; i++) { if (str[i] === ' ') { temp.push('%20') } else { temp.push(str[i]) } } return temp.join('') } // 第二种 function replaceSpace(str){ // write code here return str.replace(/ /g, "%20"); }
3、输入一个链表,按链表从尾到头的顺序返回一个ArrayList。
输入
{67,0,24,58}
返回值
[58,24,0,67]
解
function printListFromTailToHead(head) { var arrayList = []; var node = head; while(node){ arrayList.unshift(node.val); node = node.next; } return arrayList; }
4、输入某二叉树的前序遍历和中序遍历的结果,请重建出该二叉树。假设输入的前序遍历和中序遍历的结果中都不含重复的数字。例如输入前序遍历序列{1,2,4,7,3,5,6,8}和中序遍历序列{4,7,2,1,5,3,8,6},则重建二叉树并返回。
输入
[1,2,3,4,5,6,7],[3,2,4,1,6,5,7]
返回值
{1,2,5,3,4,6,7}
解
function TreeNode(x) { this.val = x; this.left = null; this.right = null; } function reConstructBinaryTree(pre, vin) { // write code here //利用递归实现 其中preStart代表的是先序遍历的第一个节点的下标位置 后边的依次类推 function rebuild(preStart, preEnd, vinStart, vinEnd) { let node = new TreeNode(pre[preStart]) //判断是否只有一个节点 如果只有一个节点 则返回节点本身 if ((preStart == preEnd) && (vinStart == vinEnd)) { return node } let index = vin.indexOf(pre[preStart]) //查找树的根节点 let leftLen = index - vinStart //左子树的长度 let leftPrend = preStart + leftLen //先选出先序遍历的左子树的所有节点 if (leftLen > 0) { //此时相当于遍历左子树的左子树 因此先序遍历开始的节点需加一 中序遍历结束的节点需减一 node.left = rebuild(preStart + 1, leftPrend, vinStart, index - 1) } if (leftLen < preEnd - preStart) { node.right = rebuild(leftPrend + 1, preEnd, index + 1, vinEnd) } return node } let head = rebuild(0, pre.length - 1, 0, vin.length - 1) return head }
5、用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。
解
let inStack = [] let outStack = [] function push(node) { inStack.push(node) } function pop() { // write code here if(!outStack.length){ while(inStack.length){ outStack.push(inStack.pop()) } } return outStack.pop() }