-
第 21 楼 / webdriver
- 时间: 2014-9-24 21:44推荐答案来了 (in C++) ...
Both of the two solutions are from leetcode.com/2011/09/r...ching.html .
代码:
class Solution {
public:
bool isMatch(const char *s, const char *p) {
if (*p == '\0') return *s == '\0';
if (*(p+1) == '*') // next is '*'
{
while ((*s == *p || *p == '.') && *s != '\0')
{
if (isMatch(s, p+2))
return true;
s++;
}
return isMatch(s, p+2);
}
if (*s == '\0') return false;
return (*s == *p || *p == '.') && isMatch(s+1, p+1);
}
bool isMatch_2(const char *s, const char *p) {
if (*p == '\0') return *s == '\0';
if (*s == *p || *p == '.' && *s != '\0')
return *(p+1) != '*' ? isMatch(s+1, p+1) :
isMatch(s+1, p) || isMatch(s, p+2);
else
return *(p+1) == '*' && isMatch(s, p+2);
}
};
-
-
- 时间: 2014-9-24 21:47算法问题: Remove Duplicates from Sorted Array
问题描述:
Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.
Do not allocate extra space for another array, you must do this in place with constant memory.
For example,
Given input array A = [1,1,2],
Your function should return length = 2, and A is now [1,2]. -
-
- 时间: 2014-9-24 21:47
-
- 时间: 2014-9-24 21:48
-
- 时间: 2014-9-24 21:49
-
- 时间: 2014-9-24 21:50推荐答案来了 (in C++) ...
1. Delete duplicates directly.
2. Copy value first (like Remove Duplicates from Array) and then delete the remaining elements.
代码:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *deleteDuplicates(ListNode *head) {
return deleteDuplicates_1(head);
}
ListNode *deleteDuplicates_1(ListNode *head) {
if (!head) return head;
ListNode *cur = head;
while (cur->next)
{
if (cur->val == cur->next->val)
{
ListNode *del = cur->next;
cur->next = del->next;
delete del;
}
else
{
cur = cur->next;
}
}
return head;
}
ListNode *deleteDuplicates_2(ListNode *head) {
if (!head) return head;
ListNode *last = head, *cur = head->next;
while (cur)
{
if (last->val != cur->val) {
last = last->next;
last->val = cur->val;
}
cur = cur->next;
}
cur = last->next;
while (cur) {
ListNode *del = cur;
cur = cur->next;
delete del;
}
last->next = NULL;
return head;
}
};
-
- 时间: 2014-9-24 21:51
-
- 时间: 2014-9-24 21:51推荐答案来了 (in C++) ...
1. iterative 2. recursive
代码:
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *deleteDuplicates(ListNode *head) {
return deleteDuplicates_1(head);
}
ListNode *deleteDuplicates_1(ListNode *head) {
ListNode dummy(0), *cur = &dummy;
dummy.next = head;
while (cur->next)
{
ListNode *node = cur->next;
int val = node->val;
if (!node->next || node->next->val != val) {
cur = cur->next;
continue;
}
while (node && node->val == val) {
ListNode *del = node;
node = node->next;
delete del;
}
cur->next = node;
}
return dummy.next;
}
ListNode *deleteDuplicates_2(ListNode *head) {
if (!head) return NULL;
if (!head->next || head->val != head->next->val) {
head->next = deleteDuplicates(head->next);
return head;
}
int val = head->val;
while(head && head->val == val) {
ListNode *del = head;
head = head->next;
delete del;
}
return deleteDuplicates(head);
}
}; -
- 时间: 2014-9-24 21:52
-
- 时间: 2014-9-24 21:53
Leetcode Hacking Practice -- Solution in C++ Part 3
