OJ每日练习（8）

Posted on | In

题目名称

  1. Swap Nodes in Pairs(Leetcode #24)
  2. Copy List with Random Pointer(Leetcode #138）
  3. Linked List Cycle(Leetcode #141)
  4. Reorder List(Leetcode #143)
  5. LRU Cache（Leetcode #146）
  6. 环的入口节点（剑指offer #23）
  7. 翻转链表(剑指offer #24)
  8. 合并已排序的链表（剑指offer #25）
  9. 树的子结构（剑指offer #26）
  10. 二叉树的镜像（剑指offer #27）

Swap Nodes in Pairs(Leetcode #24)

题目描述

Given a linked list, swap every two adjacent nodes and return its head.
Example:

1
Given 1->2->3->4, you should return the list as 2->1->4->3.

Note:
Your algorithm should use only constant extra space.You may not modify the values in the list’s nodes, only nodes itself may be changed.

解题思路

迭代版：采用三指针从头到尾遍历，当不再存在一对节点时终止遍历。
递归版：对于一对节点，我们只需要明确，first->newfirst，second->first,当不再存在节点对时终止递归。

解题方案

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(!head || !head->next)
            return head;
        ListNode preHead(-1);
        preHead.next = head;
        ListNode* pre=&preHead,*cur=head,*next=cur->next;
        while(true){
            pre->next=next;
            cur->next=next->next;
            next->next=cur;
            pre=cur;
            if(cur->next) cur=cur->next;
            else return preHead.next;
            if(cur->next) next=cur->next;
            else return preHead.next;
        }
    }
};

递归

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(!head || !head->next)
            return head;
        ListNode* p = head->next;
        head->next = swapPairs(head->next->next);
        p->next = head;
        return p;
    }
};

Copy List with Random Pointer(Leetcode #138）

题目描述

A linked list is given such that each node contains an additional random pointer which could point to any node in the list or null.Return a deep copy of the list.

解题思路

可以用hashmap完成存储，但这里我采用的时空间O(1)的算法。思路大致如下：

  1. 针对每一个节点都完成复制，从而令链表1—>2->3变成1->1->2->2->3->3
  2. 将random节点进行连接，具体表现为cur->next->random=cur->random->next
  3. 分离两个链表

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
public:
    RandomListNode* Clone(RandomListNode* head){
        if(!head)
            return nullptr;
        RandomListNode* cur=head,*next=cur->next;
        while(cur){
            RandomListNode* copy = new RandomListNode(cur->label);
            cur->next=copy;
            copy->next=next;
            cur=next;
            next=next?next->next:nullptr;
        }
        cur=head,next=cur->next->next;
        while(cur){
            if(cur->random)
                cur->next->random = cur->random->next;
            cur=next;
            next=next?next->next->next:nullptr;
        }
        cur=head,next=cur->next->next;
        RandomListNode pre(-1);
        pre.next = cur->next;
        while(cur){
            cur->next->next = next?next->next:nullptr;
            cur->next=next;
            cur=next;
            next=next?next->next->next:nullptr;
        }
        return pre.next;
    }
};

Linked List Cycle(Leetcode #141)

题目描述

Given a linked list, determine if it has a cycle in it.

解题思路

快慢指针，没什么好说的。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool hasCycle(ListNode *head) {
        if (!head) return false;
	    ListNode *p = head, *q = p;
	    while (p && p->next) {
		    p = p->next->next;
		    q = q->next;
		    if (p == q) 
		        return true;
	    }
	    return false;
    }
};

扩展

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.Note: Do not modify the linked list.

解题思路

还是快慢指针，p的前进速度是q的两倍。设head到环起点的距离为S,环起点到pq相遇点的距离为M。假设当他们相遇时q走了K步，显然存在K=S+M。又p走了2K步（速度2倍），表明环的长度为K，即q再走K-M步必然到达环起点，而K-M=S。因此令一个指针从head前进，当其与q相遇时必然该点为环起点。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(!head || !head->next)
            return nullptr;
        ListNode* p=head,*q=p;
        while(p && p->next){
            p=p->next->next;
            q=q->next;
            if(p==q)
                break;
        }
        if(p!=q)
            return nullptr;
        ListNode* k=head;
        while(k!=q)
            k=k->next,q=q->next;
        return k;
    }
};

Reorder List(Leetcode #143)

题目描述

Given a singly linked list L: L0→L1→…→Ln-1→Ln,reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
You may not modify the values in the list’s nodes, only nodes itself may be changed.
Example 1:

1
Given 1->2->3->4, reorder it to 1->4->2->3.

Example 2:
1
Given 1->2->3->4->5, reorder it to 1->5->2->4->3.

解题思路

解题思路大致是找到中间的那个节点，然后前半部分不动，后半部分翻转，然后再合并两个链表，大致如下所示：1->2->3->4->5 1->2->3<-4<-5 1->5->2->4->3

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
public:
    void reorderList(ListNode* head) {
        if(!head ||!head->next)
            return;
        ListNode* p =head,*q=p;
        while(p->next && p->next->next){//not p && p->next
            p=p->next->next;
            q=q->next;
        }//q is the middle node
        ListNode* cur = q->next;
        q->next=nullptr;
        while(cur){
            ListNode* temp = cur->next;
            cur->next=q;
            q=cur;
            cur=temp;
        }//q is the new first node
        cur=head;
        while(cur){
            ListNode* next =cur->next;
            ListNode* newnext = q->next;
            cur->next=q;
            q->next = next;
            q=newnext;
            cur=next;
        }
    }
};

LRU Cache（Leetcode #146）

题目描述

Design and implement a data structure for Least Recently Used (LRU) cache. It should support the following operations: get and put.
get(key) - Get the value (will always be positive) of the key if the key exists in the cache, otherwise return -1.
put(key, value) - Set or insert the value if the key is not already present. When the cache reached its capacity, it should invalidate the least recently used item before inserting a new item.
Follow up:
Could you do both operations in O(1) time complexity?
Example:

1
2
3
4
5
6
7
8
9
10
LRUCache cache = new LRUCache( 2 /* capacity */ );
cache.put(1, 1);
cache.put(2, 2);
cache.get(1);       // returns 1
cache.put(3, 3);    // evicts key 2
cache.get(2);       // returns -1 (not found)
cache.put(4, 4);    // evicts key 1
cache.get(1);       // returns -1 (not found)
cache.get(3);       // returns 3
cache.get(4);       // returns 4

解题思路

我们采用hashmap与双链表来完成LRU算法，原因在于双链表的插入与删除可以O(1),hashmap的查找可以O（1）。
具体实现细节：

  1. 越靠近链表头部说明最近使用频次越高，反之则说明最少。
  2. 访问节点时，若该节点存在，将其交换至链表头部，同时更新hashmap中该节点的地址。
  3. 插入节点时，若size已饱和，将list尾端元素删除，同时删除hashmap中对应的项，将新节点放在链表头部。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
//LRUCache.h
#pragma once
#include <list>
#include <unordered_map>
struct CacheNode {
	int key;
	int value;
	CacheNode(int k, int v) :key(k), value(v) {};
};
class LRUCache {
private:
	std::list<CacheNode> cacheList;
	std::unordered_map<int, std::list<CacheNode>::iterator> cacheMap;
	size_t capacity;
public:
	LRUCache(int cap) :capacity(cap) {};
	int get(int);
	void set(int, int);
private:
	LRUCache() {};//Exists no LRUCache without a cap
};


//LRUCache.cpp
#include "LRUCache.h"

int LRUCache::get(int key) {
	if (cacheMap.find(key) == cacheMap.end())
		return -1;
	else {
		//move the element to the list's begin so we determine it as the recently used element
		cacheList.splice(cacheList.begin(), cacheList, cacheMap[key]);
		cacheMap[key] = cacheList.begin();
		return cacheMap[key]->value;
	}
}

void LRUCache::set(int k, int v) {
	if (cacheMap.find(k) == cacheMap.end()) {
		if (cacheList.size() == capacity) {
			//erase the least used lement from both map and list
			cacheMap.erase(cacheList.back().key);
			cacheList.pop_back();
		}
		//insert the CacheNode into the list and map
		cacheList.insert(cacheList.begin(), CacheNode(k, v));
		cacheMap[k] = cacheList.begin();
	}
	else {
		//Update the CacheNode's value and move it to the list's begin
		cacheMap[k]->value = v;
		cacheList.splice(cacheList.begin(), cacheList, cacheMap[k]);
		cacheMap[k] = cacheList.begin();
	}
}

环的入口节点（剑指offer #23）

（本题已在上文有所提及，略去不表）

翻转链表 (剑指offer #24)

解题思路

无非是分为迭代和递归两种。
迭代：1->2->3 => 1<-2 3 => 1<-2<-3
递归：找出末尾节点p=func(head)，然后对于每一个输入节点head，都有head->next->next=head,head->next=nullptr;

解题方案

迭代

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    ListNode* ReverseList(ListNode* head) {
        if(!head || !head->next)
            return head;
        ListNode* pre=nullptr;
        ListNode* cur=head;
        while(cur){
            ListNode* next = cur->next;
            cur->next=pre;
            pre=cur;
            cur=next;
        }
        return pre;
    }
};

递归

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    ListNode* ReverseList(ListNode* head) {
        if(!head || !head->next)
            return head;
        ListNode *p = ReverseList(head->next);
        head->next->next=head;
        head->next=nullptr;
        return p;
    }
};

合并已排序的链表（剑指offer #25）

解题思路

直接参考了STL merge算法。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
public:
    ListNode *mergeTwoLists(ListNode *l1, ListNode *l2) {
        ListNode pre(-1);
        ListNode *cur=&pre;
        while(l1 && l2){
            if(l1->val<l2->val) cur=cur->next=l1,l1=l1->next;
            else cur=cur->next=l2,l2=l2->next;
        }
        cur->next=l1?l1:l2;
        return pre.next;
    }
};

树的子结构（剑指offer #26）

解题思路

递归解法建立在求解两个树是否相等的基础上。撰写一个判断两个树是否相等的函数，然后再主函数中针对左右子树递归调用即可。

解题方案

（本解法认为空树是任何树的子树）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool isSubtree(TreeNode* s, TreeNode* t) {
        if(!s) return false;
        if(isSame(s,t)) return true;
        return isSubtree(s->left,t)||isSubtree(s->right,t);
    }
private:
    bool isSame(TreeNode* a, TreeNode*b){
        if(!a&&!b) return true;
        if((!a||!b)||a->val!=b->val) return false;
        return isSame(a->left,b->left) && isSame(a->right,b->right);
    }
};

树的镜像

解题思路

同样是递归思路求解。递归过程如下：

  1. root为空，返回；
  2. 若root不为空，交换两颗子树，并对它们执行镜像操作。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    void Mirror(TreeNode *pRoot) {
        swapTree(pRoot);
    }
    
    void swapTree(TreeNode *root){
        if(!root)
            return;
        swap(root->left,root->right);
        swapTree(root->left);
        swapTree(root->right);
    }
};