二叉树 1. 寻找一条路径等于给定值 方法1：如果有父节点链接，那么遍历每个节点回溯路径的和即可。 方法2：根据二叉树的先根遍历思想，通过一个栈保存从根到当前节点的路径，每遍历一个节点，都从sum值中减去此节点的权值，此点遍历结束后，再从栈中弹出此节点，并在sum中加上此节点的权值。当sum为零且当前节点为叶子节点时，打印栈中保存的路径。 2. 给前序和中序序列还原二叉树 前序的第一个节点preO …

阅读全文→

19.1 Write a function to swap a number in place without temporary variables x=x^y y=x^y x=x^y 19.2 Design an algorithm to figure out if someone has won in a game of tic-tac-toe We could use 1 for play …

阅读全文→

公用题干为一个包含正数及负数的数组k 1.找到连续的子数组和最大，最小，最接近m（比如0） 最大的dp方程为dp[i]=max{dp[i-1]+k[i], k[i]}，最小情况完全类似 def submax(k[]): smax=MIN, cmax=0 for i in range(0,len(k)-1): cmax=max(cmax+k[i], k[i]) smax=max(smax, cmax …

阅读全文→

13.1 Write a method to print the last K lines of an input file using C++. int tail(const string &fname, int lines, list &res) { ifstream fs(fname.c_str()); if(!fs) return -1; int status = 0; i …

阅读全文→