剑指 Offer 51. 数组中的逆序对
一直二分,在遍历的时候,优先考虑分出的数组回到原数组,已全部完毕的情况。
for(int k = left; k <= right; k++) {
if(i == m + 1) { //左分用完
nums[k] = temp[j++];
}
else if(j == right + 1 || temp[i] <= temp[j]) {//注意是||右边用完 或者 无逆序对
nums[k] = temp[i++];
}else {
nums[k] = temp[j++];
ans += m - i + 1;
}
}
剑指 Offer 33. 二叉搜索树的后序遍历序列
利用二叉搜索树的性质,其左子树都小于他,其右子树都大于他;
利用后续遍历的性质,其最后一个节点即为根节点;
那么一个重要的步骤是:
找到第一个右子树的节点(下标) 为了后续递归;
那么在所有操作完毕之后,移动指针,应当指到根节点 && 左子树满足 && 右子树满足;
剑指 Offer 16. 数值的整数次方
巧妙地点是利用二进制数;
利用这个点,因为指数每次都 *2 ,2^i;
所以x更新 x = x * x;
while(b > 0) {
if((b & 1) == 1) {
res *= x;
}
x *= x;
b >>= 1; ** b每次向右移动一位 **
}
剑指 Offer 07. 重建二叉树
为了方便地找到根节点对应的下标,以便于后续的递归;
所以将中序遍历制作成一个HashMap,键:数组值;值:数组下标;
又因为,先序遍历的第一个节点即为根节点注意得到rootval = preorder[prestar];//不是preorder[0];
TreeNode root = new TreeNode(rootval);
int index = map.get(rootval);
root.left = dnn(preorder, prestar + 1, prestar + index - instar, instar, index - 1);
root.right = dnn(preorder, prestar + index - instar + 1, preend, index + 1, inend);
return root;
}