今日头条 面试题一例

之前同学面试今日头条，碰到了破浪数问题 即在数组上升下降不定时，找到其中一个波峰 如{1,2,3, 1,0,-1, -3,1,3, 4,5,2, 1,0,2, 3,2,1}找到3即可

最优为O(logn)解法 随手写了一下，马马虎虎能满足要求；望指正

public class test{ // static int[] array = new int[]{1,2,3, 1,0,-1, -3,1,3, 4,5,2, 1,0,2, 3,2,1}; // static int[] array = new int[]{1,2,3, 1,0,-1, -3,1}; static int[] array = new int[10]; public static int inner(int left, int right ){ System.out.println("left"+left+"right"+right); if (left<=0 || right>=array.length-1 || right-left<0){ return -32767; } if (left == right || right-left == 1){ if(array[left]-array[left-1]>0 && array[right+1]-array[right]<0){ return Math.max(array[left], array[right]); }else if (array[left]-array[left-1]==0 && array[right+1]-array[right]==0){ return Math.max(array[left], array[right]); } else{return -32767;} } if(array[left]-array[left-1]>0 && array[right+1]-array[right]<0){ right = left+(right-left+1)/2 ; return inner(left, right); }else if(array[right]-array[left-1]>0 && array[right+1]-array[right]>0){ int temp = right-left; int returnValue = inner(right, right+temp); if(returnValue == -32767){ returnValue = inner(left+1, right); } return returnValue; }else if(array[left]-array[left-1]<0 && array[right+1]-array[right]<0){ int temp = right-left; int returnValue = inner(left-temp, left); if(returnValue == -32767){ returnValue = inner(left, right-1); } return returnValue; // right++; } else if(array[left]-array[left-1]<0 && array[right+1]-array[right]>0){ right--; // left++; }else{ right--; // left++; } return inner(left, right); } public static int fourth(){ } public static void main(String[] args) { for(int i : array) System.out.println(i); // O(log n) // for(int i=0;i<array.length();i++){ int left = 1; int right = array.length-2; int result = 0; result = inner(left, right); System.out.println(result); } }

还有一道题是判断是否是平衡二叉树的 如果某二叉树中任意结点的左右子树的深度相差不超过1，那么它就是一棵平衡二叉树。 源于剑指offer：

bool IsBalanced(BinaryTreeNode* pRoot, int* depth) { if(pRoot== NULL) { *depth = 0; return true; } int nLeftDepth,nRightDepth; bool bLeft= IsBalanced(pRoot->m_pLeft, &nLeftDepth); bool bRight = IsBalanced(pRoot->m_pRight, &nRightDepth); if (bLeft && bRight) { int diff = nRightDepth-nLeftDepth; if (diff<=1 || diff>=-1) { *depth = 1+(nLeftDepth > nRightDepth ? nLeftDepth : nRightDepth); return true; } } return false; } bool IsBalanced(BinaryTreeNode* pRoot) { int depth = 0; return IsBalanced(pRoot, &depth); }