OJ每日练习（14）

（有些题目存在更优解，但留到后期刷leetcode时处理）

题目名称

1. 求1+2+3+……+n（剑指offer #64）
2. 不用加减乘除作加法（剑指offer #65）
3. 构建乘积数组（剑指offer #66)
4. 把字符串转为整数（剑指offer #67)
5. 树中两个节点的最低公共祖先（剑指offer #68)
6. z型打印二叉树（剑指offer #69）
7. 二叉树的层序遍历（剑指offer #70）

---

求1+2+3+……+n（剑指offer #64）

解题思路

不许用循环，那只能是用递归了，又不能使用if之类设立递归基，因此

解题方案

class Solution {
public:
    int Sum_Solution(int n) {
        int res=n;
        res && (res += Sum_Solution(n-1));
        return res;
    }
};

---

不用加减乘除作加法（剑指offer #65）

解题思路

位运算。这里的核心要点在于：

1. a^b 相当于两个数不考虑进位相加
2. (a&b)<<1 相当于两个数的进位
3. 将二者相加

解题方案

class Solution {
public:
    int Add(int num1, int num2){
        while(num2){
            int sum = num1^num2;
            int carry = (num1&num2)<<1;
            num1=sum,num2=carry;
        }
        return num1;
    }
};

---

构建乘积数组（剑指offer #66)

解题思路

将计算过程分为两步：

1. 从左到右算 B[i]=A[0]*A[1]*…*A[i-1]
2. 从右到左算B[i]*=A[i+1]*…*A[n-1]

为了保证O（n），可以采用一个变量保存连乘结果。

解题方案

class Solution {
public:
    vector<int> multiply(const vector<int>& A) {
        vector<int> B(A.size());
        for(int i=0,res=1;i!=A.size();res*=A[i++])
            B[i]=res;
        for(int i=A.size()-1,res=1;i!=-1;res*=A[i--])
            B[i]*=res;
        return B;
    }
};

---

实现atoi

解题思路

这种是纯粹的细节题，技术上难度不大。

解题方案

int StringToInteger(string &str) {
	//Time:O(n) Space:O(1)
	long base = 0, sign = 1;
	int i = str.find_first_not_of(" ");
	if (i == -1) return 0;
	else if (str[i] == '+' || str[i] == '-') {
		sign = str[i++] == '-' ? -1 : 1;
	}
	while (i != str.size() && isdigit(str[i])) {
		base = base * 10 + str[i++] - '0';
		if (base*sign >= INT_MAX) return INT_MAX;
		if (base*sign <= INT_MIN) return INT_MIN;
	}
	return base*sign;
}

---

最低公共祖先

解题思路

若此时为二叉搜索树，那情况十分简单：判断当前root->val与两个节点的值。若两个节点的值都比root大，则祖先在右子树中，若都小，则在左子树之中。若一大一小，则当前即为祖先。

解题方案

Node* FindLowestCommonAncestor(Node* root, Node* n1, Node* n2)
{
    if (!root|| !n1 ||! n2)
        return NULL;
    if (root->data > n1->data && root->data > n2->data)
        return FindLowestCommonAncestor(root->left, n1, n2);
    else if (root->data < n1->data && root->data < n2->data)
        return FindLowestCommonAncestor(root->right, n1, n2);
    else
        return root;
}

---

z型打印二叉树（剑指offer #69）

解题思路

递归解决,当然迭代也是可行的

解题方案

class Solution {
public:
    vector<vector<int> > Print(TreeNode* root) {
        vector<vector<int> > res;
        aux(root,1,res);
        return res;
    }
private:
    void aux(TreeNode* root,int level,vector<vector<int> > &res){
        if(!root)
            return;
        if(level>res.size())
            res.push_back(vector<int>());
        if(level&1)
            res[level-1].push_back(root->val);
        else
            res[level-1].insert(res[level-1].begin(),root->val);
        aux(root->left,level+1,res);
        aux(root->right,level+1,res);
    }
};

---

二叉树的层序遍历（剑指offer #70

解题思路

其实和上一题是一样的。

解题方案

class Solution {
public:
    vector<vector<int> > Print(TreeNode* root) {
        vector<vector<int> > res;
        aux(root,1,res);
        return res;
    }
private:
    void aux(TreeNode* root,int level,vector<vector<int> >res){
        if(!root)
            return;
        if(level>res.size())
            res.push_back(vector<int>());
        
    }
};