OJ每日练习（7）

Posted on | In

题目名称

  1. Add Two Numbers(Leetcode #2)
  2. Reverse Linked ListⅡ(Leetcode #92）
  3. Partition List(Leetcode #86)
  4. Remove Duplicates from Sorted List(Leetcode #83)
  5. Rotate List（Leetcode #61）
  6. 正则表达式匹配（剑指offer #18）
  7. 表达数值的字符串(剑指offer #19)
  8. 调整数组顺序保证奇数在偶数之前（剑指offer #20）
  9. 链表的倒数第k个节点（剑指offer #21）

Add Two Numbers(Leetcode #2)

题目描述

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Example:

1
2
3
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
Explanation: 342 + 465 = 807.

解题思路

从头到尾遍历即可，需要注意边界情况与鲁棒性。

解题方案

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode preHead(-1); 
        ListNode *cur = &preHead;
	    int carry = 0;
	    while (l1 || l2 || carry) {
		    int sum = (l1 ? l1->val : 0) + (l2 ? l2->val : 0) + carry;
		    carry = sum / 10;
		    cur->next = new ListNode(sum % 10);
		    l1 = l1 ? l1->next : l1;
		    l2 = l2 ? l2->next : l2;
		    cur = cur->next;
	    }
	    return preHead.next;
    }
};

扩展

You are given two non-empty linked lists representing two non-negative integers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
You may assume the two numbers do not contain any leading zero, except the number 0 itself.
Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.
Example:

1
2
Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

解题思路

有大佬提出了不用额外空间也不破坏原有数组的做法，具体解答可见：https://leetcode.com/problems/add-two-numbers-ii/discuss/154058/C++-Solution-without-recursion-and-Space-complexity-O(1) 出于赶时间的原因（其实是没想出来），笔者用栈完成了这道题的求解（把这道题强行变成了上一道题），需要注意的地方在于返回的链表不可逆序连接。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<int> val1,val2;
        while(l1) val1.push(l1->val),l1=l1->next;
        while(l2) val2.push(l2->val),l2=l2->next;
        ListNode* cur = nullptr;
        ListNode* next = cur;
        int carry=0;
        while(!val1.empty() || !val2.empty() || carry){
            int val=(val1.empty()?0:val1.top())+(val2.empty()?0:val2.top())+carry;
            if(!val1.empty()) val1.pop();
            if(!val2.empty()) val2.pop();
            carry=val/10;
            cur = new ListNode(val%10);
            cur->next=next;
            next=cur;
        }
        return cur;
    }
};

Reverse Linked ListⅡ(Leetcode #92）

题目描述

Reverse a linked list from position m to n. Do it in one-pass.
Note: 1 ≤ m ≤ n ≤ length of list.
Example:

1
2
Input: 1->2->3->4->5->NULL, m = 2, n = 4
Output: 1->4->3->2->5->NULL

解题思路

本题可以用模仿单链表翻转（迭代版本）的求解思路完成，也可以运用下一种思路：
假定当前有单链表1->2->3->4->5，m=1,n=3;我们设立三个指针pre,cur,next。最终我们需要做的是将2移动到4的位置，为了完成这一步骤需要m-n次循环，循环过程如下所示：

1
2
3
start:   1->2->3->4->5      pre:1 cur:2 next:3
1st:     1->3->2->4->5      pre:1 cur:2 next:4
2nd:     1->4->3->2->5      pre:1 cur:2 next:5

在每一次循环中，我们需要执行的是：

  1. cur->next = next->next;
  2. next->next = pre->next;
  3. pre->next = next;
  4. next = cur->next;

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        n-=m;
        ListNode preHead(-1);
        preHead.next = head;
        ListNode* pre=&preHead;
        while(--m) pre=pre->next;
        ListNode* cur = pre->next;
        ListNode* next = cur->next;
        while(n--){
            cur->next=next->next;
            next->next = pre->next;
            pre->next = next;
            next=cur->next;
        }
        return preHead.next;
    }
};

Partition List(Leetcode #86)

题目描述

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal to x.
You should preserve the original relative order of the nodes in each of the two partitions.
Example:

1
2
Input: head = 1->4->3->2->5->2, x = 3
Output: 1->2->2->4->3->5

解题思路

STL算法中有stable_partition与partition，前一种我没学过。不过单链表具有非常好的分割特性，不必那么麻烦。直接将原有链表分为两条，然后再合并即可。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
    ListNode* partition(ListNode* head, int x) {
        ListNode preHead1(-1), preHead2(-1);
	    ListNode *p = &preHead1, *q = &preHead2;
	    while (head) {
		    if (head->val < x) p = p->next = head;
		    else q = q->next = head;
		    head = head->next;
	    }
	    p->next = preHead2.next;
	    q->next = nullptr;
	    return preHead1.next;
    }
};

Remove Duplicates from Sorted List(Leetcode #83)

题目描述

Given a sorted linked list, delete all duplicates such that each element appear only once.
Example 1:

1
2
Input: 1->1->2->3->3
Output: 1->2->3

解题思路

单链表不具备随机访问特性，只能从头到尾地遍历一次。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    ListNode *deleteDuplicates(ListNode *head) {
        ListNode* cur=head;
        while(cur){
            while(cur->next && cur->val==cur->next->val)
                cur->next=cur->next->next;
            cur=cur->next;
        }
        return head;
    }
};

扩展

Given a sorted linked list, delete all nodes that have duplicate numbers, leaving only distinct numbers from the original list.
Example:

1
2
Input: 1->1->1->2->3
Output: 2->3

解题思路

我们用prev与cur两个指针完成求解。将所有重复元素直接略过。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
public:
    ListNode* deleteDuplication(ListNode* head){
        if(!head || !head->next)
            return head;
        ListNode preHead(-1);
        preHead.next=head;
        ListNode* pre=&preHead,*cur=head;
        while(cur){
           while(cur->next && cur->val==cur->next->val)
               cur=cur->next;
           if(pre->next==cur)
               pre=cur;
           cur=cur->next;
           pre->next=cur;
        }
        return preHead.next;
    }
};

Rotate List（Leetcode #61）

题目描述

Given a linked list, rotate the list to the right by k places, where k is non-negative.
Example:

1
2
Input: 1->2->3->4->5->NULL, k = 2
Output: 4->5->1->2->3->NULL

Explanation:
1
2
rotate 1 steps to the right: 5->1->2->3->4->NULL
rotate 2 steps to the right: 4->5->1->2->3->NULL

解题思路

STL有关于rotate的算法实现，但单链表自身存在特殊性质：我们可以把它连接成环，确定开头后再断开即可。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if (!head || !head->next)
            return head;
        ListNode *node = head;
        int length = 1;
        while (node->next) {
            ++length;
            node = node->next;
        }
        node->next = head;
        int step = length - k % length;
        while (step--)
            node = node->next;
        head = node->next;
        node->next = nullptr;
        return head;
    }
};

正则表达式匹配（剑指offer #18）

题目描述

本题与leetcode#10 相同。是一道难度较大的题（我感觉字符串的题都好难啊）。

解题思路

如果第2个字符不为*，那么我们先判断首字符是否匹配。若首字符匹配，递归式判断剩下的,否则返回false。若第二个字符为*且当前首字符匹配，我们有两种选择：

  1. 无视模式串中的’*’
  2. 无视文本串中当前匹配的字符

若第二个字符为*且当前首字符不匹配，直接认为p[0]p[1]为空，继续执行匹配。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool match(char* s, char* p){
        if(*p=='\0')
            return *s=='\0';
        if(*(p+1)!='*'){
            if(*p==*s || *p=='.' && *s!='\0')
                return match(s+1,p+1);
            else
                return false;
        }
        else{
            while(*p==*s || *p=='.' && *s!='\0'){
                if(match(s,p+2))
                    return true;
                s++;
            }
            return match(s,p+2);
        }
    }
};

表达数值的字符串

解题思路

类似于JSON项目中解析数字的实现。

解题方案

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool isNumeric(char* s){
        if(*s=='\0') return false;
        if(*s=='+'|| *s=='-')
            ++s;
        while(isdigit(*s)) ++s;
        if(*s=='.'){
            ++s;
            if(!isdigit(*s)) return false;
            while(isdigit(*s)) ++s;
        }
        if(*s=='e'||*s=='E'){
            ++s;
            if(*s=='+'|| *s=='-') ++s;
            if(!isdigit(*s)) return false;
            while(isdigit(*s)) ++s;
        }
        return *s=='\0';
    }
};

调整数组顺序保证奇数在偶数之前（剑指offer #20）

解题思路

这道题就是在考察stable_partition的实现，简单地说，可以利用插排或者冒泡。如果不用稳定的话，那直接参照STL的partition实现。

解题方案

1
2
3
4
5
6
7
8
9
class Solution {
public:
    void reOrderArray(vector<int> &array) {
       for(size_t i=0;i!=array.size();++i)
           for(size_t j=array.size()-1;j>i;--j)
               if(array[j]&1 && !(array[j-1]&1))
                   swap(array[j],array[j-1]);
    }
};

链表的倒数第k个节点

解题思路

快慢指针，不过需要注意鲁棒性。

解题方案

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