剑指offer.C++.code36-40

36. 两个链表的第一个公共结点

• 输入两个链表，找出它们的第一个公共结点。

// Solution:(1)暴力搜索，假设两个链表长度分别为m、n——时间复杂度O(mn)
//          (2)因为公共结点的结构，使用栈分别存放两个链表结点，全入栈后从栈顶弹出直到不同的栈顶——时间O(m+n)，空间O(m+n)
//          (3)先遍历两个计数，长的链表先走差值步，然后同时向后遍历到第一个公共结点——时间O(m+n)
/*
struct ListNode {
    int val;
    struct ListNode *next;
    ListNode(int x) :
            val(x), next(NULL) {
    }
};*/
class Solution {
public:
    ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
        // 两个链表长度和差值
        int len1 = GetListLength(pHead1);
        int len2 = GetListLength(pHead2);
        int lenDiff = len1 - len2;
        ListNode* pLongHead = pHead1;
        ListNode* pShortHead = pHead2;
        if (len1 < len2) {
            lenDiff = len2 - len1;
            pLongHead = pHead2;
            pShortHead = pHead1;
        }
        // 先在长链表上走lenDiff步，再同时走
        for (int i = 0; i < lenDiff; i ++) {
            pLongHead = pLongHead->next;
        }
        while ((pLongHead != NULL) && (pShortHead != NULL) && (pLongHead != pShortHead)) {
            pLongHead = pLongHead->next;
            pShortHead = pShortHead->next;
        }
        // 第一个公共结点；
        ListNode* pFirstCommonNode = pLongHead;
        return pFirstCommonNode;
    }
    
    int GetListLength(ListNode* pHead) {
        int len = 0;
        ListNode* pNode = pHead;
        while (pNode != NULL) {
            pNode = pNode->next;
            len ++;
        }
        return len;
    }
};

拓展——最低公共祖先：

37. 数字在排序数组中出现的次数【二分查找第一个、最后一个k】

• 统计一个数字在排序数组中出现的次数。

// Solution:(1)二分查找k，顺序扫描左右——时间复杂度o(n);
//          (2)二分查找第一个k，二分查找第二个k，计算k的个数——O(logn).
class Solution {
public:
    int GetNumberOfK(vector<int> data ,int k) {
        if (data.size() == 0) // 数组为空，输出0
            return 0;
        // 没有对应的index时，返回-1（与统计出现次数为0不同）
        int firstK_index = GetFirstK(data, k, 0, data.size()-1);
        int lastK_index = GetLastK(data, k, 0, data.size()-1);
        if (firstK_index != -1 && lastK_index != -1)
            return lastK_index - firstK_index + 1;
        else
            return 0;        // 数组不存在数字k，输出0
    }
    
    int GetFirstK(vector<int> data, int k, int start, int end) {
        if (start > end) {
            return -1;
        }
        int mid_index = (start+end)/2;
        if (data[mid_index] == k) {    // 中间数字是k
            if ((mid_index > 0 && data[mid_index-1] != k) || mid_index == 0) {//前一个数字不是k
                return mid_index;      // 返回第一个k的index
            } else {
                end = mid_index - 1;
            }
        } else if (data[mid_index] > k) {// 中间数字比k大，查找前半部分
            end = mid_index - 1;
        } else {    // 中间数字比k小，查找后半部分
            start = mid_index + 1;
        }
        return GetFirstK(data, k, start, end);
    }
    
    int GetLastK(vector<int> data, int k, int start, int end) {
        if (start > end) {
            return -1;
        }
        int mid_index = (start+end)/2;
        if (data[mid_index] == k) {    // 中间数字是k
            if ((mid_index < end && data[mid_index+1] != k) || mid_index == end) {//后一个数字不是k
                return mid_index;      // 返回最后一个k的index
            } else {
                start = mid_index + 1;
            }
        } else if (data[mid_index] > k) {// 中间数字比k大，查找前半部分
            end = mid_index - 1;
        } else {    // 中间数字比k小，查找后半部分
            start = mid_index + 1;
        }
        return GetLastK(data, k, start, end);
    }
};

38. 二叉树的深度【递归】

• 输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。

// Solution:递归计算深度
// rootDepth = max(leftDepth, rightDepth) + 1
/*
struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
    TreeNode(int x) :
            val(x), left(NULL), right(NULL) {
    }
};*/
class Solution {
public:
    int TreeDepth(TreeNode* pRoot)
    {
        if (pRoot == NULL) 
            return 0;
        int leftDeep = TreeDepth(pRoot->left);
        int rightDeep = TreeDepth(pRoot->right);
        return leftDeep > rightDeep ? leftDeep+1 : rightDeep+1;
    }
};

39. 平衡二叉树

• 输入一棵二叉树，判断该二叉树是否是平衡二叉树。

// Solution:(1)遍历二叉树，对每个结点调用上题TreeDepth函数，由于重复计算造成效率低；
//          (2)后序遍历，遍历时记录每个结点的深度(传地址)——每个结点遍历一次的解法
class Solution {
public:
    bool IsBalanced_Solution(TreeNode* pRoot) {
        int rootDepth = 0;
        return IsBalanced(pRoot, rootDepth);
    }
     
    bool IsBalanced(TreeNode* root, int& pNodeDepth) {
        if (root == NULL) {
            return true;
        }
        int leftDepth = 0, rightDepth = 0;
        if (IsBalanced(root->left, leftDepth) && IsBalanced(root->right, rightDepth)) {
            // 左右子树都平衡，且已经计算了depth
            int diff = leftDepth - rightDepth;
            if (diff <= 1 && diff >= -1) {
                pNodeDepth = (rightDepth > leftDepth ? rightDepth : leftDepth) + 1;
                return true;
            }
        }
        return false;
    }

};

40. 数组中只出现一次的数字

• 一个整型数组里除了两个数字之外，其他的数字都出现了两次。请写程序找出这两个只出现一次的数字。

// 二进制和位运算：
// Solution:step1-数组中只出现一次的一个数字求法——逐个数字异或，最后结果为出现一次的数字；
//          step2-将原问题转化为，两个子数组，每个子数组中只有一个仅出现一次的数字，转化为step1;
//          step3-划分两个数组标准为，逐个数异或的结果为1的位置，根据每个数字该位的0/1区分为两个数组.
class Solution {
public:
    void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
        if (data.size() == 0)
            return;
        int orResult = 0;
        for (int i = 0; i < data.size(); i ++) {
            orResult ^= data[i];
        }
        unsigned int indexOf1 = FindFirstBit1(orResult);
        *num1 = 0;
        *num2 = 0;
        for (int i = 0; i < data.size(); i ++) {
            if (IsBit1(data[i], indexOf1)) {
                *num1 ^= data[i];
            } else {
                *num2 ^= data[i];
            }
        }
    }
    
    unsigned int FindFirstBit1(int num) {
        int indexBit = 0;
        while (((num & 1) == 0) && (indexBit < 8 * sizeof(int))) {
            num = num >> 1;
            indexBit ++;
        }
        return indexBit;
    }
    
    bool IsBit1(int num, unsigned int indexBit) {
        num = num >> indexBit;
        return (num & 1);
    }
    
};

step1 step2&3