剑指offer 52与53


剑指offer 52与53

1.面试题52. 两个链表的第一个公共节点

method1:设公共长度为c,第一个链表除公共部分长度为a,第二个链表除公共部分长度为b。若公共部分存在,则(a+c) + b = (b+c) +a,否则,(a+b) = (b+a)。

直接遍历即可,其中一个链表指针遍历完,让它重新指向另一个链表head节点,最终两个指针指向的就是公共节点。

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        if(!headA || !headB) return nullptr;

        ListNode* p = headA,*q = headB;
        while(p != q) {
            p = !p ? headB : p->next;
            q = !q ? headA : q->next;
        }
        return p;
    }
};

method2:根据长度来计算公共节点,时间复杂度O(n),空间复杂度O(1)。

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        int len1 = 0;
        int len2 = 0;
        int headA_len = getLen(headA,len1);
        int headB_len = getLen(headB,len2);
        ListNode* p = headA,*q = headB;
        int disp = 0,i=0;
        if(headA_len > headB_len) {
            disp = headA_len - headB_len;
            while(i<disp) {
                p = p->next;
                i++;
            }
        } else if(headA_len < headB_len) {
            disp = headB_len - headA_len;
            while(i<disp) {
                q = q->next;
                i++;
            }
        }
        while(p) {
            if(p == q) return p;
            p = p->next;
            q = q->next;
        }
        return NULL;
    }
    int getLen(ListNode* head,int len) {
        if(!head) return 0;
        ListNode* p = head;
        while(p) {
            p = p->next;
            len++;
        }
        return len;
    }
};

method3:使用一个集合存储第一个链表所有节点,然后判断另一个节点在不在集合中,若在直接返回,不在就往后遍历,直到链表完毕还没有,就返回空。时间复杂度O(n),空间复杂度O(n),

class Solution {
public:
    ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
        set<ListNode*> s;
        ListNode* p= headA;
        while(p) {
            s.insert(p);
            p = p->next;
        }
        p = headB;
        while(p) {
            if(s.count(p)>0) return p;
            p = p->next;
        }
        return NULL;
    }

};

2.面试题53 - I. 在排序数组中查找数字 I

method1:递归查找

class Solution {
public:
    int search(vector<int>& nums, int target) {
        return _bs(nums,0,nums.size()-1,target);
    }
    int _bs(vector<int>& nums,int l,int r,int target) {
        if(l>r) return 0;
        int count = 0;
        int mid = l+(r-l)/2;
        if(nums[mid] > target) {
            count = _bs(nums,l,mid-1,target);
        } else if(nums[mid] < target) {
            count = _bs(nums,mid+1,r,target) ;
        } else if(nums[mid] == target) {
            count += 1 + _bs(nums,l,mid-1,target) + _bs(nums,mid+1,r,target);
        }
        return count;
    }
};

method2:查找出第一个等于target与最后一个等于target的位置,然后相互减即可。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        if(nums.size() == 0) return 0;
        int left = getLeftIndex(nums,target);
        int right = getRightIndex(nums,target);
        if(left==-1 || right==-1) return 0;
        return right-left+1;
    }
    int getLeftIndex(vector<int>& nums, int target) {
        int l = 0, r = nums.size()-1;
        while(l<=r) {
            int mid = l + (r-l)/2;
            if(nums[mid]<target) {
                l = mid+1;
            } else if(nums[mid]>target) {
                r = mid-1;
            } else {
                // 不能往下查找了或者可以往下查找但是前面不满足
                if(mid==0 || nums[mid-1]!=target) 
                    return mid;
                else 
                    r = mid-1;
            }
        }
        return -1;
    }
    int getRightIndex(vector<int>& nums, int target) {
        int l = 0, r = nums.size()-1;
        while(l<=r) {
            int mid = l + (r-l)/2;
            if(nums[mid]<target) {
                l = mid+1;
            } else if(nums[mid]>target) {
                r = mid-1;
            } else {
                // 不能往上查找了或者可以往上查找但是后面不满足
                if(mid==nums.size()-1 || nums[mid+1]!=target) return mid;
                else l = mid+1;
            }
        }
        return -1;
    }
};

method3:STL内置函数调用。

class Solution {
public:
    int search(vector<int>& nums, int target) {
        return upper_bound(nums.begin(),nums.end(),target) - lower_bound(nums.begin(),nums.end(),target);
    }
};

3.面试题53 - II. 0~n-1中缺失的数字

method1:so easy 二分,直接递归,如果这个nums是一个有序的那么返回-1,根据第一个元素是否是0,判断是最后一个元素+1,还是0.

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int n = nums.size();
        // 如果这个数在中间[0,1,3]
        int res = recursion(nums,0,n-1);
        if(res != -1) return res; 
        // 排除[0,1,2]与[1,2,3]有序结果
        return nums[0] == 0 ? nums[n-1]+1 : 0;   
    }
    int recursion(vector<int>& nums,int left,int right) {
        if(left>right) return -1;

        int mid = left + (right-left) / 2;
        if(mid+1 < nums.size() && nums[mid] + 2 == nums[mid+1])
            return nums[mid]+1;
        int res1 = recursion(nums,left,mid-1);
        int res2 = recursion(nums,mid+1,right);
        if(res1 == -1) return res2;
        return res1;
    }
};

method2:直接遍历.

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        // [0,nums.size()+1]
        for(int i=0;i<nums.size();i++) {
            if(nums[i]!=i) return i;
        }
        return nums.size();
    }
};

##


更多内容,订阅公众号

文章作者: light-city
版权声明: 本博客所有文章除特別声明外,均采用 CC BY 4.0 许可协议。转载请注明来源 light-city !
评论
  目录