代码拉取完成，页面将自动刷新
/*****************************************************************************
*
* 文件名称: leetcode.c
*
* 功能摘要: leetcode编程题
*
* 创建时间: 2014-12-31 16:00
*
* 文件版本: 0.1
*
* 文件作者: llxwj
*
* Copyright (C) 2012 All rights reserved.
*
*****************************************************************************
*
* 修改记录:
*
****************************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <stdint.h>
#include <ctype.h>
#include <CUnit/CUnit.h>
#include <CUnit/Basic.h>
#include <CUnit/TestDB.h>
#define bool int
#define true 1
#define false 0
#define ARRAY_NUM(x) ((sizeof(x) / sizeof(x[0])))
typedef void list_t;
/*****************************************************************************
* 单链表
****************************************************************************/
typedef struct ListNode
{
int val;
struct ListNode *next;
}ListNode;
static struct ListNode* ListAppend(struct ListNode* head, int val)
{
struct ListNode* p = NULL;
struct ListNode* t = NULL;
p = (struct ListNode*)malloc(sizeof(struct ListNode));
if(p != NULL)
{
p->val = val;
p->next = NULL;
}
if(head == NULL)
{
return p;
}
t = head;
while(t->next != NULL) t = t->next;
t->next = p;
return head;
}
static int ListLength(struct ListNode* head)
{
int l = 0;
while(head != NULL)
{
head = head->next;
l++;
}
return l;
}
static struct ListNode* ListDestroy(struct ListNode* head)
{
struct ListNode* t = NULL;
while(head != NULL)
{
t = head;
head = head->next;
free(t);
}
return NULL;
}
static void ListPrint(ListNode* head)
{
while(head)
{
printf("%d->", head->val);
head=head->next;
}
printf("\n");
}
static ListNode* ListMakeCycle(ListNode* head, int k)
{
ListNode* tail = NULL;
ListNode* dest = NULL;
int index = 0;
int length = 0;
if((head == NULL) || (k < 0)) return NULL;
tail = head;
while(tail->next != NULL)
{
tail = tail->next;
length++;
}
if(length < k) return NULL;
dest = head;
while((dest->next != NULL) && (index < k))
{
dest = dest->next;
index++;
}
tail->next = dest;
return tail;
}
typedef int (*visit_func_t)(void* context, void* data, unsigned long size);
typedef int (*cmp_func_t)(void* data1, void* data2);
#define LBE_ERR_FOREACH_STOP (-40)
#define LBE_ERR_FIND_STOP (-41)
#define LBE_ERR_FIND (-6)
static int ListForeach(ListNode* list, void* context, visit_func_t visit)
{
ListNode* node = NULL;
if((list == NULL) || (visit == NULL))
{
return -1;
}
for(node = list; node != NULL; node = node->next)
{
if(visit(context, (void*)node->val, 0) == LBE_ERR_FOREACH_STOP)
{
break;
}
}
return 0;
}
int ListFind(ListNode* list, void* data, cmp_func_t cmp)
{
ListNode* node = NULL;
int index = 0;
if((list == NULL) || (cmp == NULL))
{
return -1;
}
for(node = list; node != NULL; node = node->next)
{
if(cmp(data, (void*)node->val) == 0)
{
return index;
}
index++;
}
return LBE_ERR_FIND;
}
int ListGet(ListNode* list, int index, void** data)
{
ListNode* node = NULL;
if((list == NULL) || (index < 0) || (data == NULL))
{
return -1;
}
for(node = list; (node != NULL) && (index > 0); node = node->next)
{
index--;
}
*data = (void*)(node->val);
return 0;
}
/*****************************************************************************
* 队列
****************************************************************************/
typedef struct QueueNode
{
void* data;
struct QueueNode* next;
}QueueNode;
typedef struct Queue
{
int size;
struct QueueNode* list;
}Queue;
static QueueNode* QueueNodeAppend(QueueNode* head, void* data)
{
QueueNode* p = NULL;
QueueNode* t = NULL;
p = (QueueNode*)malloc(sizeof(QueueNode));
if(p != NULL)
{
p->data = data;
p->next = NULL;
}
if(head == NULL)
{
return p;
}
t = head;
while(t->next != NULL) t = t->next;
t->next = p;
return head;
}
static void QueueNodeDestroy(QueueNode* head)
{
QueueNode* t = NULL;
while(head != NULL)
{
t = head;
head = head->next;
free(t);
}
}
static Queue* QueueNew(void)
{
Queue* q = NULL;
q = (Queue*)malloc(sizeof(Queue));
if(q != NULL)
{
q->list = NULL;
q->size = 0;
}
return q;
}
static void QueueDestroy(Queue* q)
{
if(q == NULL)
{
return;
}
if(q->list != NULL)
{
QueueNodeDestroy(q->list);
}
free(q);
}
static void QueuePush(Queue* q, void* data)
{
if(q == NULL)
{
return;
}
q->list = QueueNodeAppend(q->list, data);
}
static void* QueuePop(Queue* q)
{
QueueNode* head = NULL;
void* data = NULL;
if(q == NULL)
{
return NULL;
}
if(q->list == NULL)
{
return NULL;
}
head = q->list;
q->list= q->list->next;
data = head->data;
free(head);
return data;
}
static bool QueueIsEmpty(Queue* q)
{
if(q == NULL)
{
return true;
}
if(q->list == NULL)
{
return true;
}
return false;
}
static int QueueSize(Queue* q)
{
int size = 0;
QueueNode* node = NULL;
if(q == NULL)
{
return 0;
}
if(q->list == NULL)
{
return 0;
}
node = q->list;
while(node != NULL)
{
node = node->next;
size++;
}
return size;
}
/*****************************************************************************
* 栈
****************************************************************************/
typedef struct StackNode
{
void* data;
struct StackNode* next;
}StackNode;
typedef struct Stack
{
int size;
StackNode* list;
}Stack;
static StackNode* StackNodeAppend(StackNode* head, void* data)
{
StackNode* p = NULL;
StackNode* t = NULL;
p = (StackNode*)malloc(sizeof(StackNode));
if(p != NULL)
{
p->data = data;
p->next = NULL;
}
if(head == NULL)
{
return p;
}
t = head;
while(t->next != NULL) t = t->next;
t->next = p;
return head;
}
static void StackNodeDestroy(StackNode* head)
{
StackNode* t = NULL;
while(head != NULL)
{
t = head;
head = head->next;
free(t);
}
}
static Stack* StackNew(void)
{
Stack* s = NULL;
s = (Stack*)malloc(sizeof(Stack));
if(s != NULL)
{
s->list = NULL;
}
return s;
}
static void StackDestroy(Stack* s)
{
if(s == NULL)
{
return;
}
if(s->list != NULL)
{
StackNodeDestroy(s->list);
s->list = NULL;
}
free(s);
}
static bool StackIsEmpty(Stack* s)
{
if(s == NULL)
{
return true;
}
if(s->list == NULL)
{
return true;
}
return false;
}
static void StackPush(Stack* s, void* data)
{
if(s == NULL)
{
return;
}
s->list = StackNodeAppend(s->list, data);
}
static void* StackPop(Stack* s)
{
StackNode* p = NULL;
StackNode* n = NULL;
void* data = NULL;
if(s == NULL)
{
return NULL;
}
if(s->list == NULL)
{
return NULL;
}
n = s->list;
while(n->next != NULL)
{
p = n;
n = n->next;
}
if(p == NULL)
{
data = n->data;
free(p);
s->list = NULL;
}
else
{
p->next = NULL;
data = n->data;
free(n);
}
return data;
}
static void StackTop(Stack* s, void** data)
{
StackNode* n = NULL;
if((s == NULL) || (data == NULL))
{
return;
}
if(s->list == NULL)
{
return;
}
n = s->list;
while(n->next != NULL)
{
n = n->next;
}
*data = n->data;
}
static int StackSize(Stack* s)
{
int size = 0;
StackNode* node = NULL;
if(s == NULL)
{
return 0;
}
if(s->list == NULL)
{
return 0;
}
node = s->list;
while(node != NULL)
{
node = node->next;
size++;
}
return size;
}
/*****************************************************************************
* 二叉树
****************************************************************************/
typedef struct TreeNode
{
int val;
struct TreeNode* left;
struct TreeNode* right;
struct TreeNode* next;
struct TreeNode* parent;
}TreeNode, TreeLinkNode;
static TreeNode* TreeNew(int val, TreeNode* l, TreeNode* r, TreeNode* p)
{
TreeNode* t = NULL;
t = (TreeNode*)malloc(sizeof(TreeNode));
if(t != NULL)
{
t->val = val;
t->left = l;
t->right = r;
t->next = NULL;
t->parent = p;
}
return t;
}
static TreeNode* TreeAppend(TreeNode* root, int val)
{
if(root == NULL)
{
return TreeNew(val, NULL, NULL, NULL);
}
return root;
}
static void TreeGetNodesNumber(struct TreeNode* root, int* n)
{
if(root != NULL)
{
*n = *n + 1;
TreeGetNodesNumber(root->left, n);
TreeGetNodesNumber(root->right, n);
}
}
/*****************************************************************************
* Min Stack
****************************************************************************/
typedef struct
{
Stack* noraml;
Stack* min;
}MinStackPriv;
typedef struct MinStack
{
void (*push)(struct MinStack* ms, int x);
void (*pop)(struct MinStack* ms);
int (*top)(struct MinStack* ms);
int (*getMin)(struct MinStack* ms);
char priv[0];
}MinStack;
void MinStackPush(MinStack* ms, int x)
{
MinStackPriv* priv = NULL;
int val = 0;
if(ms == NULL) return;
priv = (MinStackPriv*)ms->priv;
StackPush(priv->noraml, (void*)x);
if(StackIsEmpty(priv->min))
{
StackPush(priv->min, (void*)x);
}
else
{
StackTop(priv->min, (void**)&val);
if(x <= val)
{
StackPush(priv->min, (void*)x);
}
}
}
void MinStackPop(MinStack* ms)
{
int normal_top = 0;
int min_top = 0;
MinStackPriv* priv = NULL;
if(ms == NULL) return;
priv = (MinStackPriv*)ms->priv;
StackTop(priv->min, (void**)&min_top);
StackTop(priv->noraml, (void**)&normal_top);
StackPop(priv->noraml);
if(min_top == normal_top)
{
StackPop(priv->min);
}
}
int MinStackTop(MinStack* ms)
{
int top = 0;
MinStackPriv* priv = NULL;
if(ms == NULL) return INT_MIN;
priv = (MinStackPriv*)ms->priv;
StackTop(priv->noraml, (void**)&top);
return top;
}
int MinStackGetMin(MinStack* ms)
{
int min = 0;
MinStackPriv* priv = NULL;
if(ms == NULL) return INT_MIN;
priv = (MinStackPriv*)ms->priv;
StackTop(priv->min, (void**)&min);
return min;
}
MinStack* MinStackNew(void)
{
MinStack* ms = NULL;
MinStackPriv* priv = NULL;
ms = malloc(sizeof(MinStack) + sizeof(MinStackPriv));
if(ms == NULL)
{
return NULL;
}
priv = (MinStackPriv*)ms->priv;
priv->min = StackNew();
priv->noraml = StackNew();
ms->push = MinStackPush;
ms->pop = MinStackPop;
ms->top = MinStackTop;
ms->getMin = MinStackGetMin;
return ms;
}
void MinStackFree(MinStack* ms)
{
MinStackPriv* priv = NULL;
if(ms != NULL)
{
priv = (MinStackPriv*)ms->priv;
StackDestroy(priv->min);
StackDestroy(priv->noraml);
free(ms);
}
}
/*****************************************************************************
* Two Sum
****************************************************************************/
typedef struct
{
int number;
int count;
}TwoSumTemplatet;
typedef struct
{
ListNode* list;
}TwoSumPriv;
typedef struct
{
ListNode* list;
int value;
bool find;
}TwoSumContext;
typedef struct TwoSum
{
void (*add)(struct TwoSum* ts, int number);
bool (*find)(struct TwoSum* ts, int value);
char priv[0];
}TwoSum;
static int TwoSumCompare(void* data1, void* data2)
{
TwoSumTemplatet* tst1 = data1;
TwoSumTemplatet* tst2 = data2;
if((tst1 == NULL) || (tst2 == NULL))
{
return -1;
}
if(tst1->number == tst2->number)
{
return 0;
}
else if(tst1->number > tst2->number)
{
return 1;
}
else
{
return -1;
}
}
static void TwoSumAdd(TwoSum* ts, int number)
{
TwoSumPriv* priv = NULL;
TwoSumTemplatet* tst = NULL;
TwoSumTemplatet* old = NULL;
int index = 0;
if(ts == NULL) return;
priv = (TwoSumPriv*)ts->priv;
tst = malloc(sizeof(TwoSumTemplatet));
if(tst == NULL) return;
tst->number = number;
tst->count = 1;
index = ListFind(priv->list, tst, TwoSumCompare);
if(index >= 0)
{
ListGet(priv->list, index, (void**)&old);
old->count++;
free(tst);
}
else
{
ListAppend(priv->list, (int)tst);
}
}
static int TwoSumForeach(void* context, void* data, unsigned long size)
{
TwoSumContext* tsc = NULL;
TwoSumTemplatet* tst = NULL;
TwoSumTemplatet another = {0};
int index = 0;
tsc = context;
tst = data;
another.number = tsc->value - tst->number;
if((another.number == tst->number) && (tst->count > 1))
{
tsc->find = true;
return LBE_ERR_FOREACH_STOP;
}
else if(another.number != tst->number)
{
index = ListFind(tsc->list, &another, TwoSumCompare);
if(index >= 0)
{
tsc->find = true;
return LBE_ERR_FOREACH_STOP;
}
}
return 0;
}
static bool TwoSumFind(TwoSum* ts, int value)
{
TwoSumPriv* priv = NULL;
TwoSumContext tsc = {0};
priv = (TwoSumPriv*)ts->priv;
tsc.find = false;
tsc.list = priv->list;
tsc.value = value;
ListForeach(priv->list, &tsc, TwoSumForeach);
return tsc.find;
}
static TwoSum* TwoSumNew()
{
TwoSum* ts = NULL;
TwoSumPriv* priv = NULL;
ts = (TwoSum*)malloc(sizeof(TwoSum) + sizeof(TwoSumPriv));
if(ts == NULL)
{
return NULL;
}
priv = (TwoSumPriv*)ts->priv;
priv->list = NULL;
//priv->list = ListNew(lbe_free);
ts->add = TwoSumAdd;
ts->find = TwoSumFind;
return ts;
}
static void TwoSumFree(TwoSum* ts)
{
TwoSumPriv* priv = NULL;
priv = (TwoSumPriv*)ts->priv;
ListDestroy(priv->list);
free(ts);
}
/*****************************************************************************
* OJ's Binary Tree Serialization:
* The serialization of a binary tree follows a level order traversal, where
* '#' signifies a path terminator where no node exists below.
* Here's an example:
* 1
* / \
* 2 3
* /
* 4
* \
* 5
* The above binary tree is serialized as "{1,2,3,#,#,4,#,#,5}".
****************************************************************************/
static TreeNode* TreeNewByStringOJ(const char* s)
{
TreeNode* root = NULL;
TreeNode* p = NULL;
int val = 0;
Queue* q = NULL;
int negative = 1;
q = QueueNew();
if(s == NULL) return NULL;
if(*s != '{') return NULL;
s++;
while((*s != '\0') && (*s != ',') && (*s != '}'))
{
if(*s == '-')
{
negative = -1;
}
else
{
val = val * 10 + (*s - '0');
}
s++;
}
s++;
root = TreeNew(val * negative, NULL, NULL, NULL);
QueuePush(q, root);
while(!QueueIsEmpty(q) && (*s != '\0'))
{
p = QueuePop(q);
if(*s != '#')
{
val = 0;
negative = 1;
while((*s != ',') && (*s != '\0') && (*s != '}'))
{
val = val * 10 + (*s - '0');
s++;
}
s++;
p->left = TreeNew(val * negative, NULL, NULL, p);
QueuePush(q, p->left);
}
else
{
s++; //jump '#'
if(*s == '\0') break;
s++; //jump ','
if(*s == '\0') break;
}
if(*s == '\0') break;
if(*s != '#')
{
val = 0;
negative = 1;
while((*s != ',') && (*s != '\0') && (*s != '}'))
{
if(negative == '-')
{
negative = -1;
}
else
{
val = val * 10 + (*s - '0');
}
s++;
}
s++;
p->right = TreeNew(val * negative, NULL, NULL, p);
QueuePush(q, p->right);
}
else
{
s++; //jump '#'
if(*s == '\0') break;
s++; //jump ','
if(*s == '\0') break;
}
}
QueueDestroy(q);
return root;
}
/*****************************************************************************
* Myself Binary Tree Serialization:
* The serialization of a binary tree use preorder traversal sequence, where
* '#' signifies a path terminator where no node exists below.
* Here's an example:
* 1
* / \
* 2 3
* /
* 4
* \
* 5
* The above binary tree is serialized as "1,2,#,#,3,4,#,5,#,#,".
****************************************************************************/
static TreeNode* TreeNewByString(const char* s)
{
TreeNode* root = NULL;
TreeNode* p = NULL;
bool has_left = true;
int val = 0;
if(s == NULL)
{
return NULL;
}
if((s[0] == '#') && (s[1] == ',') && (s[2] == '#'))
{
return NULL;
}
while(*s != ',')
{
val = val * 10 + (*s - '0');
s++;
}
s++;
root = TreeNew(val, NULL, NULL, NULL);
p = root;
while(*s != '\0')
{
if(*s == '#')
{
if(has_left)
{
has_left = false;
}
else
{
p = p->parent;
}
s++;
s++;
continue;
}
val = 0;
while((*s != ',') && (*s != '\0'))
{
val = val * 10 + (*s - '0');
s++;
}
s++;
if(has_left)
{
p->left = TreeNew(val, NULL, NULL, p);
p = p->left;
has_left = true;
}
else
{
p->right = TreeNew(val, NULL, NULL, p);
p = p->right;
has_left = true;
}
}
return root;
}
static TreeNode* TreeDestroy(TreeNode* root)
{
if(root == NULL) return NULL;
if(root->left != NULL)
{
TreeDestroy(root->left);
root->left = NULL;
}
if(root->right != NULL)
{
TreeDestroy(root->right);
root->right = NULL;
}
if((root->left == NULL) && (root->right == NULL))
{
free(root);
}
return NULL;
}
static int TreeDepth(struct TreeNode* root)
{
int left_depth = 0;
int right_depth = 0;
if(root == NULL) return 0;
left_depth = TreeDepth(root->left);
right_depth = TreeDepth(root->right);
return (left_depth > right_depth ? left_depth : right_depth) + 1;
}
static int TreeHeight(struct TreeNode* root)
{
int left_height = 0;
int right_height = 0;
if(root == NULL) return -1;
left_height = TreeHeight(root->left);
right_height = TreeHeight(root->right);
return (left_height > right_height ? left_height : right_height) + 1;
}
static void TreePreorder(TreeNode* root)
{
if(root == NULL) return;
printf("%d ", root->val);
if(root->left != NULL)
{
TreePreorder(root->left);
}
else
{
printf("# ");
}
if(root->right != NULL)
{
TreePreorder(root->right);
}
else
{
printf("# ");
}
}
static void TreeInorder(TreeNode* root)
{
if(root == NULL) return;
if(root->left != NULL)
{
TreeInorder(root->left);
}
else
{
printf("# ");
}
printf("%d ", root->val);
if(root->right != NULL)
{
TreeInorder(root->right);
}
else
{
printf("# ");
}
}
static void TreePostorder(TreeNode* root)
{
if(root == NULL) return;
if(root->left != NULL) TreePostorder(root->left);
if(root->right != NULL) TreePostorder(root->right);
printf("%d ", root->val);
}
/*****************************************************************************
* 2:Add Two Numbers
* You are given two linked lists representing two non-negative numbers. 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.
* Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
* Output: 7 -> 0 -> 8
* 解释: 342
* +465 = 807-> 反序就是708
*
* Difficulty: Medium
*
* Link: https://oj.leetcode.com/problems/add-two-numbers/
*
* Code:
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*
* 解法:
* L1 NULL NOTNULL NULL NOTNULL
* L2 NULL NULL NOTNULL NOTNULL
* 返回 NULL L1 L2 (Equal Length or Not Equal Length)
****************************************************************************/
struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2)
{
struct ListNode* p1 = NULL;
struct ListNode* p2 = NULL;
struct ListNode* l3 = NULL;
int carry = 0;
int val = 0;
if((l1 == NULL) && (l2 == NULL)) return NULL;
if((l1 == NULL) && (l2 != NULL)) return l2;
if((l1 != NULL) && (l2 == NULL)) return l1;
p1 = l1;
p2 = l2;
while((p1 != NULL) && (p2 != NULL))
{
val = p1->val + p2->val + carry;
carry = val / 10;
l3 = ListAppend(l3, val % 10);
p1 = p1->next;
p2 = p2->next;
}
if(p1 != NULL)
{
while(p1 != NULL)
{
val = p1->val + carry;
carry = val / 10;
ListAppend(l3, val % 10);
p1 = p1->next;
}
if(carry != 0)
{
ListAppend(l3, carry);
carry = 0;
}
}
if(p2 != NULL)
{
while(p2 != NULL)
{
val = p2->val + carry;
carry = val / 10;
ListAppend(l3, val % 10);
p2 = p2->next;
}
if(carry != 0)
{
ListAppend(l3, carry);
carry = 0;
}
}
if(carry != 0)
{
ListAppend(l3, carry);
}
return l3;
}
/*****************************************************************************
* 6: ZigZag Conversion
* The string "PAYPALISHIRING" is written in a zigzag pattern on a given
* number of rows like this: (you may want to display this pattern in a fixed
* font for better legibility)
* P A H N
* A P L S I I G
* Y I R
* And then read line by line: "PAHNAPLSIIGYIR"
* Write the code that will take a string and make this conversion given a
* number of rows:
* string convert(string text, int nRows);
* convert("PAYPALISHIRING", 3) should return "PAHNAPLSIIGYIR".
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/zigzag-conversion/
*
* Code:
* char* convert(char* s, int numRows) {
*
* }
*
* n_rows:
* 1: 1 2 3 4 5 6 ... ... gap = 0
* 2: 1 3 5 7 gap = 2
* 2 4 6 8
* return 1357...2468
* 3: 1 5 9 gap = 4
* 2 4 6 8 10
* 3 7 11
* return 159...2468,10...37,11...
* 4: 1 7 13 gap = 6
* 2 6 8 12 14
* 3 5 9 11 15
* 4 10 16
* return 1,7,13...2,6,8,12,14,...3,5,9,11,15,...,4,10,16...
*
* 我们发现如下规律,共有n行：
* 1 第i行从i开始
* 2 第一行与最后一行间隔是2(n-1)
* 2 中间第i行两个数的间隔是2(n-i),2(i-1)交替[如果i从0起则是2(n-i-1),2i交替]
* 如有四行的情况:每行的起始都是,1,2,3,4
* 第一行间隔:2(4-1)=6
* 第二行间隔:2(4-2)=4,2(2-1)=2,
* 第三行间隔:2(4-3)=2,2(3-1)=4,
* 第四行间隔:2(4-1)=6
****************************************************************************/
char* convert(char* s, int numRows)
{
int n = 0;
char* p = s;
int i = 0;
int j = 0;
bool flag = true;
char* _006_str = NULL;
int m = 0;
if(s == NULL) return s;
if(*s == 0) return s;
if(numRows <= 1) return s;
_006_str = (char*)malloc(strlen(s) + 1);
memset(_006_str, 0, strlen(s) + 1);
while(*p)
{
p++;
n++;
}
for(i = 0; i < numRows; i++)
{
j = i;
flag = true;
while(j < n)
{
_006_str[m++] = s[j];
if((i == 0) || (i == (numRows - 1)))
{
j = j + 2 * (numRows - 1);
}
else
{
if(flag)
{
flag = false;
j = j + 2 * (numRows - i - 1);
}
else
{
flag = true;
j = j + 2 * i;
}
}
}
}
return _006_str;
}
/*****************************************************************************
* 7: Reverse Integer
* Reverse digits of an integer.
* Example1: x = 123, return 321
* Example2: x = -123, return -321
*
* Have you thought about this?
* Here are some good questions to ask before coding. Bonus points for you
* if you have already thought through this!
*
* If the integer's last digit is 0, what should the output be? ie, cases
* such as 10, 100.
*
* Did you notice that the reversed integer might overflow? Assume the input
* is a 32-bit integer, then the reverse of 1000000003 overflows. How should
* you handle such cases?
*
* For the purpose of this problem, assume that your function returns 0 when
* the reversed integer overflows.
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/reverse-integer/
*
* Code:
* int reverse(int x) {
* }
****************************************************************************/
int reverse(int x)
{
int64_t result = 0;
int64_t remainder = 0;
while(x != 0)
{
remainder = x % 10;
result = result * 10 + remainder;
x = x / 10;
}
if((result > INT_MAX) || (result < INT_MIN))
{
return 0;
}
return result;
}
/*****************************************************************************
* 8:String to Integer (atoi)
* Implement atoi to convert a string to an integer.
* Hint: Carefully consider all possible input cases. If you want a challenge,
* please do not see below and ask yourself what are the possible input cases.
* Notes: It is intended for this problem to be specified vaguely (ie, no
* given input specs). You are responsible to gather all the input
* requirements up front.
*
* spoilers alert... click to show requirements for atoi.
* Requirements for atoi:
* The function first discards as many whitespace characters as necessary
* until the first non-whitespace character is found. Then, starting from
* this character, takes an optional initial plus or minus sign followed by
* as many numerical digits as possible, and interprets them as a numerical
* value.
*
* The string can contain additional characters after those that form the
* integral number, which are ignored and have no effect on the behavior of
* this function.
*
* If the first sequence of non-whitespace characters in str is not a valid
* integral number, or if no such sequence exists because either str is empty
* or it contains only whitespace characters, no conversion is performed.
*
* If no valid conversion could be performed, a zero value is returned. If
* the correct value is out of the range of representable values,
* INT_MAX (2147483647) or INT_MIN (-2147483648) is returned.
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/string-to-integer-atoi/
*
* Code:
* int myAtoi(char *str) {
* }
****************************************************************************/
int myAtoi(char* str)
{
int64_t result = 0;
int negative = 1;
int start = 0;
if(str == NULL) return 0;
if(*str == '\0') return 0;
while((*str != '\0') && (result < INT_MAX) && (result > INT_MIN))
{
if((*str == '-') && isdigit(*(str + 1)))
{
negative = -1;
}
else if((*str == '+') && isdigit(*(str + 1)))
{
negative = 1;
}
else if(isdigit(*str))
{
result = result * 10 + *str - '0';
start = 1;
}
else if(start == 1)
{
break;
}
else if(isspace(*str))
{
}
else
{
break;
}
str++;
}
result = result * negative;
if(result > INT_MAX)
{
return INT_MAX;
}
else if(result < INT_MIN)
{
return INT_MIN;
}
else
{
return result;
}
}
/*****************************************************************************
* 9:Palindrome Number
* Determine whether an integer is a palindrome. Do this without extra space.
* click to show spoilers.
* Some hints:
* Could negative integers be palindromes? (ie, -1)
*
* If you are thinking of converting the integer to string, note the
* restriction of using extra space.
*
* You could also try reversing an integer. However, if you have solved the
* problem "Reverse Integer", you know that the reversed integer might
* overflow. How would you handle such case?
* There is a more generic way of solving this problem.
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/palindrome-number/
*
* Code:
* bool isPalindrome(int x) {
* }
*
* http://blog.163.com/hljmdjlln@126/blog/static/5473620620120412525181/
* 有趣的数-回文数（Palindrome number）
* 回文数是数学界中的一种有趣的现象。比如121就是一个回文数。回文数的数字互相对
* 应，从中间一个任意一位数字起，左右每隔一个的数字都相等。回文数有许多神奇的
* 规律和奥秘。主要分为读数回文数、平方回文数、乘积回文数以及倒乘回文数。
* 一、读数回文数
* 【解释】读数回文数是指一个正整数，正着读和倒着读内容一致。
* 【举例】数字：98789
* 正读：九万八千七百八十九（98789）
* 倒读：九万八千七百八十九（98789）
* 正读与倒读内容一致，所以这个数字就是读书回文数。
* 注：读书回文数的数位都是奇数个。
* 二、 平方回文数
* 【解释】平方回文数是指，一个数的平方是一个回文数。
* 【举例】11^2=121，111^2=12321，1111^2=1234321 ，122^2=484
* 三、回文算式
* 【解释】等号左边是两个或多个因数相乘，右边是它们的乘积或几个因数相乘。如果
* 把每个算式中的 “×”和“=”去掉，那么，它们都变成回文数，所以，我们不妨把这些算
* 式叫做“回文算式”。
* 【举例】3×51=153
* 6×21=126
* 4307×62=267034
* 9×7×533=33579
* 12×42=24×21
* 34×86=68×43
* 102×402=204×201
* 1012×4202=2024×2101
* 不知你是否注意到，如果分别把上面的回文算式等号两边的因数交换位置，得到的仍
* 是一个回文算式。比如：
* 42×12=21×24 ，
* 43×68=86×34，
* 仍是回文算式。
* 还有更奇妙的回文算式，请看：
* 12×231=132×21（积是2772），
* 12×4032=2304×21（积是48384），
* 这种回文算式，连乘积都是回文数。
* 注：四位的回文数一定能被11整除。设它为abba，那它等于
* a*1000+b*100+b*10+a=1001a+110b，
* 能被11整除。
* 另外，在数学上还有一种算式称为『回文式』。回文式即是从左右看皆通的算式。
* 你们且看 112 x 113 = 12656 这条算式的特别之处？只要把此算式由尾写起，即成为
* 以下式子
* 12656 = 311 x 211，可以发现两条算式均成立。
* 112不但乘以113有此特性，乘以某些数也有同样的效果：
* (1) 112 x 124 = 13888 将式子由右到左写是 88831 = 421 x 211
* (2) 112 x 133 = 14896 将式子由右到左写是 69841 = 331 x 211
* (3) 112 x 223 = 24976 将式子由右到左写是 67942 = 322 x 211
* 其实，某些平方数也有此结果：
* 12 x 12=144将式子由右到左写是 441= 21 x 21
* 13 x 13=169将式子由右到左写是 961=31 x 31
* 经过仔细发现，我们在完全平方数，完全立方数中也找到了不少『回文』的例子，它
* 令我们理性的数学平添了不少感性的诗情画意。
****************************************************************************/
bool isPalindrome(int x)
{
int64_t result = 0;
int64_t remainder = 0;
int64_t backup = x;
if(x < 0) return false;
while(x != 0)
{
remainder = x % 10;
result = result * 10 + remainder;
x = x / 10;
}
if(result == backup)
{
return true;
}
else
{
return false;
}
}
/*****************************************************************************
* 13:Roman to Integer
* Given a roman numeral, convert it to an integer.
* Input is guaranteed to be within the range from 1 to 3999.
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/roman-to-integer/
*
* Code:
* int romanToInt(char* s) {
*
* }
*
* 记数方法:
* 基本字符 I V X L C D M
* 相应的阿拉伯数字表示为 1 5 10 50 100 500 1000
* 1、相同的数字连写，所表示的数等于这些数字相加得到的数，如：Ⅲ = 3；
* 2、小的数字在大的数字的右边，所表示的数等于这些数字相加得到的数，
* 如：Ⅷ = 8；Ⅻ = 12；
* 3、小的数字，（限于Ⅰ、X 和C）在大的数字的左边，所表示的数等于大数减小数得到
* 的数，如：Ⅳ= 4；Ⅸ= 9；
* 4、正常使用时，连写的数字重复不得超过三次。（表盘上的四点钟“IIII”例外）
* 5、在一个数的上面画一条横线，表示这个数扩大1000倍。
* 组数规则:
* 有几条须注意掌握：
* 1、基本数字Ⅰ、X 、C 中的任何一个，自身连用构成数目，或者放在大数的右边连用
* 构成数目，都不能超过三个；放在大数的左边只能用一个。
* 2、不能把基本数字V 、L 、D 中的任何一个作为小数放在大数的左边采用相减的方
* 法构成数目；放在大数的右边采用相加的方式构成数目，只能使用一个。
* 3、V 和X 左边的小数字只能用Ⅰ。
* 4、L 和C 左边的小数字只能用X。
* 5、D 和M 左边的小数字只能用C。
* 对照举例:
* 个位数举例
* Ⅰ,1 】Ⅱ，2】 Ⅲ，3】 Ⅳ，4 】Ⅴ，5 】Ⅵ，6】Ⅶ，7】 Ⅷ，8 】Ⅸ，9 】
* 十位数举例
* Ⅹ，10】 Ⅺ，11 】Ⅻ，12】 XIII,13】 XIV,14】 XV,15 】XVI,16 】XVII,17 】
* XVIII,18】 XIX,19】 XX,20】XXI,21 】XXII,22 】XXIX,29】 XXX,30】 XXXIV,34】
* XXXV,35 】XXXIX,39】 XL,40】L,50 】LI,51】LV,55】 LX,60】LXV,65】 LXXX,80】
* XC,90 】XCIII,93】 XCV,95 】XCVIII,98】 XCIX,99 】
* 百位数举例
* C,100】 CC,200 】CCC,300 】CD,400】 D,500 】DC,600 】DCC,700】 DCCC,800 】
* CM,900】 CMXCIX,999】
* 千位数举例
* M,1000】 MC,1100 】MCD,1400 】MD,1500 】MDC,1600 】MDCLXVI,1666】
* MDCCCLXXXVIII,1888 】MDCCCXCIX,1899 】MCM,1900 】MCMLXXVI,1976】
* MCMLXXXIV,1984】 MCMXC,1990 】MM,2000 】MMMCMXCIX,3999】
* 千位数以上举例(括号表示有上划线)
* (LXV)CCLIX，65,259 】
* ((CXXXIV))(CMXLV)DLXXXIV，134945584】
， (CLXXXIIIDCL)183650】
****************************************************************************/
int romanToInt(char* s)
{
int result = 0;
if(s == NULL) return 0;
if(*s == '\0') return 0;
while(*s != '\0')
{
if((s[0] == 'I') && (s[1] == 'V'))
{
result -= 1;
}
else if((s[0] == 'I') && (s[1] == 'X'))
{
result -= 1;
}
else if((s[0] == 'X') && (s[1] == 'L'))
{
result -= 10;
}
else if((s[0] == 'X') && (s[1] == 'C'))
{
result -= 10;
}
else if((s[0] == 'C') && (s[1] == 'D'))
{
result -= 100;
}
else if((s[0] == 'C') && (s[1] == 'M'))
{
result -= 100;
}
else if(s[0] == 'I')
{
result += 1;
}
else if(s[0] == 'V')
{
result += 5;
}
else if(s[0] == 'X')
{
result += 10;
}
else if(s[0] == 'L')
{
result += 50;
}
else if(s[0] == 'C')
{
result += 100;
}
else if(s[0] == 'D')
{
result += 500;
}
else if(s[0] == 'M')
{
result += 1000;
}
s++;
}
return result;
}
/*****************************************************************************
* 14:Longest Common Prefix
* Write a function to find the longest common prefix string amongst an array
* of strings.
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/longest-common-prefix/
*
* Code:
* char* longestCommonPrefix(char** strs, int strsSize) {
*
* }
****************************************************************************/
char* longestCommonPrefix(char** strs, int strsSize)
{
static char prefix[128] = {0};
int i = 0;
int j = 0;
memset(prefix, 0, sizeof(prefix));
if((strs == NULL) || (strsSize <= 0)) return prefix;
strcpy(prefix, strs[0]);
for(i = 1; i < strsSize; i++)
{
for(j = 0; (prefix[j] != '\0') && (strs[i][j] != '\0'); j++)
{
if(prefix[j] != strs[i][j])
{
break;
}
}
prefix[j] = '\0';
}
return prefix;
}
/*****************************************************************************
* 19:Remove Nth Node From End of List
* Given a linked list, remove the nth node from the end of list and return
* its head.
* For example,
* Given linked list: 1->2->3->4->5, and n = 2.
* After removing the second node from the end, the linked list becomes
* 1->2->3->5.
* Note:
* Given n will always be valid.
* Try to do this in one pass.
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/remove-nth-node-from-end-of-list/
*
* Code:
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
*
* struct ListNode* removeNthFromEnd(struct ListNode* head, int n) {
*
* }
****************************************************************************/
struct ListNode* removeNthFromEnd(struct ListNode* head, int n)
{
struct ListNode* fast = NULL;
struct ListNode* slow = NULL;
struct ListNode* temp = NULL;
if(head == NULL) return head;
if(head->next == NULL)
{
free(head);
return NULL;
}
fast = slow = head;
n = n + 1;
while((n > 0) && (fast != NULL))
{
fast = fast->next;
n--;
}
if(n == 1)
{
temp = slow->next;
free(slow);
return temp;
}
while(fast != NULL)
{
slow = slow->next;
fast = fast->next;
}
temp = slow->next;
slow->next = slow->next->next;
free(temp);
return head;
}
/*****************************************************************************
* 20: Valid Parentheses
* Given a string containing just the characters '(', ')', '{', '}', '[' and
* ']', determine if the input string is valid.
* The brackets must close in the correct order, "()" and "()[]{}" are all
* valid but "(]" and "([)]" are not.
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/valid-parentheses/
*
* Code:
* bool isValid(char* s) {
* };
*
****************************************************************************/
bool isValid(char* s)
{
char* stack = NULL;
int top = 0;
char open = 0;
bool status = true;
if(s == NULL) return false;
if(*s == '\0') return false;
stack = (char*)malloc(strlen(s) + 1);
memset(stack, 0, strlen(s) + 1);
while(*s != '\0')
{
if((*s == '{') || (*s == '(') || (*s == '['))
{
stack[top++] = *s;
s++;
continue;
}
if(top == 0)
{
status = false;
break;
}
else if(*s == '}')
{
open = stack[--top];
if(open != '{')
{
status = false;
break;
}
}
else if(*s == ')')
{
open = stack[--top];
if(open != '(')
{
status = false;
break;
}
}
else if(*s == ']')
{
open = stack[--top];
if(open != '[')
{
status = false;
break;
}
}
s++;
}
if(status && top != 0)
{
status = false;
}
free(stack);
return status;
}
/*****************************************************************************
* 21: Merge Two Sorted Lists
* Merge two sorted linked lists and return it as a new list. The new list
* should be made by splicing together the nodes of the first two lists.
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/merge-two-sorted-lists/
*
* Code:
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
* struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
* }
****************************************************************************/
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2)
{
struct ListNode* p = NULL;
struct ListNode* t = NULL;
struct ListNode* h = NULL;
if(l1 != NULL && l2 == NULL)
{
return l1;
}
if(l1 == NULL && l2 == NULL)
{
return l1;
}
if(l1 == NULL && l2 != NULL)
{
return l2;
}
if(l1->val < l2->val)
{
h = l1;
l1 = l1->next;
h->next = NULL;
}
else
{
h = l2;
l2 = l2->next;
h->next = NULL;
}
p = h;
while(l1 != NULL && l2 != NULL)
{
if(l1->val < l2->val)
{
t = l1->next;
p->next = l1;
p = p->next;
p->next = NULL;
l1 = t;
}
else if(l1->val > l2->val)
{
t = l2->next;
p->next = l2;
p = p->next;
p->next = NULL;
l2 = t;
}
else
{
t = l1->next;
p->next = l1;
p = p->next;
p->next = NULL;
l1 = t;
t = l2->next;
p->next = l2;
p = p->next;
p->next = NULL;
l2 = t;
}
}
if(l1 != NULL)
{
p->next = l1;
}
if(l2 != NULL)
{
p->next = l2;
}
return h;
}
/*****************************************************************************
* 24:Swap Nodes in Pairs
* Given a linked list, swap every two adjacent nodes and return its head.
*
* For example,
* Given 1->2->3->4, you should return the list as 2->1->4->3.
* Your algorithm should use only constant space. You may not modify the
* values in the list, only nodes itself can be changed.
*
* Difficulty: Medium
*
* Link: https://oj.leetcode.com/problems/swap-nodes-in-pairs/
*
* Code:
* Definition for singly-linked list.
* struct ListNode {
* int val;
* struct ListNode *next;
* };
* struct ListNode* swapPairs(struct ListNode* head) {
*
* }
****************************************************************************/
struct ListNode* swapPairs(struct ListNode* head)
{
struct ListNode* p = NULL;
struct ListNode* t = NULL;
struct ListNode* tail = NULL;
if(head == NULL) return head;
if(head->next == NULL) return head;
tail = head;
p = head->next->next;
head = head->next;
head->next = tail;
tail->next = NULL;
while(p != NULL)
{
if(p->next == NULL)
{
tail->next = p;
break; /* odd number */
}
t = p->next->next;
tail->next = p->next;
p->next->next = p;
tail = p;
tail->next = NULL;
p = t;
}
return head;
}
/*****************************************************************************
* 26: 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].
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/remove-duplicates-from-sorted-array/
*
* Code:
* int removeDuplicates(int* nums, int numsSize) {
* };
****************************************************************************/
int removeDuplicates(int nums[], int numsSize)
{
int i = 0;
int j = 0;
if((nums == NULL) || (numsSize == 0)) return 0;
while(j < numsSize)
{
while((nums[i] == nums[j]) && (j < numsSize))
{
j++;
}
i++;
nums[i] = nums[j];
}
return i;
}
/*****************************************************************************
* 27: Remove Element
* Given an array and a value, remove all instances of that value in place and
* return the new length.
* The order of elements can be changed. It doesn't matter what you leave
* beyond the new length.
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/remove-element/
*
* Code:
* int removeElement(int* nums, int numsSize, int val) {
* }
****************************************************************************/
int removeElement(int* nums, int numsSize, int val)
{
int i = 0;
int j = 0;
if((nums == NULL) || (numsSize == 0))
{
return 0;
}
while(i < numsSize)
{
if(nums[i] == val)
{
for(j = i; j < numsSize; j++)
{
nums[j] = nums[j + 1];
}
numsSize--;
continue;
}
i++;
}
return numsSize;
}
/*****************************************************************************
* 28: Implement strStr()
* Returns the index of the first occurrence of needle in haystack, or -1 if
* needle is not part of haystack.
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/implement-strstr/
*
* Code:
* int strStr(char *haystack, char *needle) {
*
* }
*
****************************************************************************/
int strStr(char* haystack, char* needle)
{
char* p1 = NULL;
char* p2 = NULL;
char* start = NULL;
if((haystack == NULL) || (needle == NULL))
{
return -1;
}
if((*haystack == '\0') && (*needle == '\0'))
{
return 0;
}
if((*haystack != '\0') && (*needle == '\0'))
{
return 0;
}
if((*haystack == '\0') && (*needle != '\0'))
{
return -1;
}
p1 = haystack;
p2 = needle;
while((*p1 != '\0') && (*p2 != '\0'))
{
if(*p1 == *p2)
{
if(start == NULL) start = p1;
p2++;
}
else
{
if(start != NULL)
{
p1 = start;
}
start = NULL;
p2 = needle;
}
p1++;
}
if(*p2 == '\0')
{
return start - haystack;
}
else
{
return -1;
}
}
/*****************************************************************************
* 36: Valid Sudoku
*
* Determine if a Sudoku is valid, according to: [Sudoku Puzzles - The Rules.]
* http://sudoku.com.au/TheRules.aspx:
* There are just 3 rules to Sudoku.
* (1).Each row must have the numbers 1-9 occuring just once.
* (2).Each column must have the numbers 1-9 occuring just once.
* (3).And the numbers 1-9 must occur just once in each of the 9 sub-boxes of
* the grid.
*
* The Sudoku board could be partially filled, where empty cells are filled
* with the character '.'.
* A partially filled sudoku which is valid.
* Note:
* A valid Sudoku board (partially filled) is not necessarily solvable. Only
* the filled cells need to be validated.
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/valid-sudoku/
*
* Code:
* bool isValidSudoku(char** board, int boardRowSize, int boardColSize) {
*
* }
****************************************************************************/
bool isValidSudoku(char** board, int boardRowSize, int boardColSize)
{
int i = 0;
int j = 0;
int m = 0;
int n = 0;
int r = 0;
int c = 0;
char cell[9] = {0};
if(board == NULL) return false;
for(i = 0; i < boardRowSize; i++)
{
memset(cell, 0, sizeof(cell));
for(j = 0; j < boardColSize; j++)
{
if((board[i][j] != '.') && (board[i][j] >= '1') && (board[i][j] <= '9'))
{
if(cell[board[i][j] - '0' - 1] != 0)
{
return false;
}
else
{
cell[board[i][j] - '0' - 1] = 1;
}
}
}
}
for(i = 0; i < boardColSize; i++)
{
memset(cell, 0, sizeof(cell));
for(j = 0; j < boardRowSize; j++)
{
if((board[j][i] != '.') && (board[j][i] >= '1') && (board[j][i] <= '9'))
{
if(cell[board[j][i] - '0' - 1] != 0)
{
return false;
}
else
{
cell[board[j][i] - '0' - 1] = 1;
}
}
}
}
//行序号为(i - 1) / 3 *3 到(i - 1) / 3 *3+2
//列序号为(i - 1)%3 *3 到(i - 1)%3 *3+2
for(i = 0; i < boardRowSize; i++)
{
memset(cell, 0, sizeof(cell));
for(m = 0; m < 3; m++)
{
for(n = 0; n < 3; n++)
{
r = (i - 1) / 3 * 3 + m;
c = (i - 1) % 3 * 3 + n;
if((board[r][c] != '.') && (board[r][c] >= '1') && (board[r][c] <= '9'))
{
if(cell[board[r][c] - '0' - 1] != 0)
{
return false;
}
else
{
cell[board[r][c] - '0' - 1] = 1;
}
}
}
}
}
return true;
}
/*****************************************************************************
* 38: Count and Say
* The count-and-say sequence is the sequence of integers beginning as follows:
* 1, 11, 21, 1211, 111221, ...
* 1 is read off as "one 1" or 11.
* 11 is read off as "two 1s" or 21.
* 21 is read off as "one 2, then one 1" or 1211.
* Given an integer n, generate the nth sequence.
* Note: The sequence of integers will be represented as a string.
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/count-and-say/
*
* Code:
* char* countAndSay(int n) {
* }
*
* 题意是n=1时输出字符串1；n=2时，数上次字符串中的数值个数，因为上次字符串有1
* 个1，所以输出11；n=3时，由于上次字符是11，有2个1，所以输出21；n=4时，由于
* 上次字符串是21，有1个2和1个1，所以输出1211。依次类推
*
* 以下的实现n有限制.n太大会有内存溢出的死机故障.(现在估计n能达到30)
****************************************************************************/
char* countAndSay(int n)
{
static char _038_say[1024 * 4] = {0};
static char _038_say2[1024 * 4] = {0};
char* p = NULL;
char* t = NULL;
int i = 0;
int offset = 0;
char current = 0;
int num = 0;
_038_say[0] = '1';
_038_say[1] = 0;
for(i = 1; i < n; i++)
{
p = _038_say;
t = _038_say2;
while(*p)
{
current = *p;
num = 0;
while(current == *p)
{
num++;
p++;
}
offset = sprintf(t, "%d%d", num, current - '0');
t += offset;
}
strcpy(_038_say, _038_say2);
}
return _038_say;
}
/*****************************************************************************
* 58: Length of Last Word
* Given a string s consists of upper/lower-case alphabets and empty space
* characters ' ', return the length of last word in the string.
* If the last word does not exist, return 0.
* Note: A word is defined as a character sequence consists of non-space
* characters only.
* For example, Given s = "Hello World", return 5.
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/length-of-last-word/
*
* Code:
* int lengthOfLastWord(char* s) {
*
* }
****************************************************************************/
int lengthOfLastWord(char* s)
{
int s_len = 0;
char* p = NULL;
if(s == NULL) return 0;
p = s;
while(*p){p++;}
do{p--;}while((p > s) && (*p == ' '));
while((p >= s) && (*p != ' ')){p--;s_len++;}
return s_len;
}
/*****************************************************************************
* 61: Rotate List
* Given a list, rotate the list to the right by k places, where k is
* non-negative.
*
* For example:Given 1->2->3->4->5->NULL and k = 2,return 4->5->1->2->3->NULL.
*
* Difficulty: Medium
*
* Link: https://oj.leetcode.com/tag/linked-list/
*
* Code:
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* };
* struct ListNode *rotateRight(struct ListNode *head, int k) {
*
* }
*
* Given [0,1,2] rotate 1 steps to right -> [2,0,1]
* Given [0,1,2] rotate 2 steps to right -> [1,2,0]
* Given [0,1,2] rotate 3 steps to right -> [0,1,2]
* Given [0,1,2] rotate 4 steps to right -> [2,0,1]
* 先求出链表的长度size,其实按着倒数第K%size个位置旋转,这个位置即size-(K%size)
* http://www.cnblogs.com/kaituorensheng/p/3647668.html
****************************************************************************/
struct ListNode* rotateRight(struct ListNode* head, int k)
{
#if 0
ListNode* fast = NULL;
ListNode* slow = NULL;
ListNode* fast_prev = NULL;
ListNode* slow_prev = NULL;
int length = 0;
if(head == NULL) return NULL;
if(k <= 0) return head;
if(head->next == NULL) return head;
fast = head;
while(fast != NULL)
{
fast = fast->next;
length++;
}
k = k % length;
fast = slow = head;
while((fast != NULL) && (k > 0))
{
fast = fast->next;
k--;
}
while(fast != NULL)
{
fast_prev = fast;
fast = fast->next;
slow_prev = slow;
slow = slow->next;
}
if(slow_prev != NULL)
{
slow_prev->next = NULL;
}
if(fast_prev != NULL)
{
fast_prev->next = head;
}
return slow;
#else
int i = 0;
if(head == NULL || head->next == NULL || k == 0)
{
return head;
}
int length = 0;
struct ListNode *ptr = head, *tail = head;
while (ptr != NULL) {
length++;
tail = ptr;
ptr = ptr->next;
}
k %= length;
ptr = head;
for(i = 0; i < length - k - 1; i++) {
ptr = ptr-> next;
}
tail->next = head;
head = ptr->next;
ptr->next = NULL;
return head;
#endif
}
/*****************************************************************************
* 66: Plus One
* Given a non-negative number represented as an array of digits, plus one to
* the number.
* The digits are stored such that the most significant digit is at the head
* of the list.
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/plus-one/
*
* Code:
* int* plusOne(int* digits, int digitsSize, int* returnSize) {
*
* }
****************************************************************************/
int* plusOne(int* digits, int digitsSize, int* returnSize)
{
int i = 0;
int val = 0;
int carray = 1;
if((digits == NULL) || (digitsSize == 0) || (returnSize == NULL))
{
return NULL;
}
for(i = 0; i < digitsSize; i++)
{
if(digits[i] != 9)
{
break;
}
}
if(i == digitsSize)
{
*returnSize = digitsSize + 1;
for(i = digitsSize - 1; i >= 0; i--)
{
val = digits[i] + carray;
carray = val / 10;
val = val % 10;
digits[i + 1] = val;
}
digits[0] = 1;
}
else
{
*returnSize = digitsSize;
for(i = digitsSize - 1; i >= 0; i--)
{
val = digits[i] + carray;
carray = val / 10;
val = val % 10;
digits[i] = val;
}
}
return digits;
}
/*****************************************************************************
* 67: Add Binary
* Given two binary strings, return their sum (also a binary string).
* For example, a = "11" b = "1" Return "100".
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/add-binary/
*
* Code:
* char* addBinary(char* a, char* b) {
* }
****************************************************************************/
char* addBinary(char* a, char* b)
{
int a_len = 0;
int b_len = 0;
int carray = 0;
int val = 0;
char* ta = NULL; //tail of string a
char* tb = NULL; //tail of string b
char* sum = NULL;
int sum_len = 0;
if(a == NULL && b == NULL) return NULL;
if(a == NULL && b != NULL) return b;
if(a != NULL && b == NULL) return a;
ta = a; while(*ta){ta++; a_len++;} ta--;
tb = b; while(*tb){tb++; b_len++;} tb--;
sum_len = a_len > b_len ? (a_len + 2) : (b_len + 2);
sum = (char*)malloc(sum_len);
if(sum == NULL)
{
return NULL;
}
sum[--sum_len] = 0;
while((ta >= a) && (tb >= b))
{
val = carray + *ta - '0' + *tb - '0';
carray = val / 2;
val = val % 2;
sum[--sum_len] = val + '0';
ta--;
tb--;
}
while(ta >= a)
{
val = carray + *ta - '0';
carray = val / 2;
val = val % 2;
sum[--sum_len] = val + '0';
ta--;
}
while(tb >= b)
{
val = carray + *tb - '0';
carray = val / 2;
val = val % 2;
sum[--sum_len] = val + '0';
tb--;
}
if(carray == 1)
{
sum[--sum_len] = '1';
}
return sum + sum_len;
}
/*****************************************************************************
* 70: Climbing Stairs
* You are climbing a stair case. It takes n steps to reach to the top.
* Each time you can either climb 1 or 2 steps. In how many distinct ways can
* you climb to the top?
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/climbing-stairs/
*
* Code:
* int climbStairs(int n) {
* }
*
* 思路：
* （1）题意为有一个n阶的梯子，一次你只能上一个或两个台阶，求你有多少种上台阶
* 的方法。这道题其实很简单，就看你能不能想到它和某一个挺有名数列之间的联系，
* 其考察我们发现规律和对常见数学数列理解的能力。
* （2）这里我们不妨列举，并从中发现规律：
* 当n=1时，ways=1
* 当n=2时，有[2] [1,1]两种情况，ways=2
* 当n=3时，有[1,1,1] [1,2] [2,1]三种情况，ways=3
* 当n=4时，有[1,1,1,1] [2,2] [1,1,2] [1,2,1] [2,1,1]五种情况，ways=5
* 当n=5时，有[1,1,1,1,1] [2,2,1] [2,1,2] [1,2,2] [1,1,1,2] [1,1,2,1]
* [1,2,1,1] [2,1,1,1]八种情况，ways=8
* （3）这样我想你一眼就能看出规律了，当n>3时，n对应的情况数字为n-1和n-2之和。
* 此时，规律正好和斐波那契数列出现的规律对应。
* （4）斐波拉切数列是这样一个数列：1、1、2、3、5、8、13、21、……在数学上，其被
* 以递归的方法定义：F0=0，F1=1，Fn=F(n-1) + F(n-2)（n>=2）
****************************************************************************/
int climbStairs(int n)
{
int i = 0;
int fn_1 = 1;
int fn_2 = 1;
int fn = 0;
if(n <= 0) return 0;
if(n == 1) return 1;
for(i = 2; i <= n; i++)
{
fn = fn_1 + fn_2;
fn_1 = fn_2;
fn_2 = fn;
}
return fn;
}
/*****************************************************************************
* 78: Subsets
* Given a set of distinct integers, nums, return all possible subsets.
* Note:
* (1) Elements in a subset must be in non-descending order.
* (2)The solution set must not contain duplicate subsets.
* For example,
* If nums = [1,2,3], a solution is:
* [
* [3],
* [1],
* [2],
* [1,2,3],
* [1,3],
* [2,3],
* [1,2],
* []
* ]
*
* Difficulty: Medium
*
* Link: https://oj.leetcode.com/problems/subsets/
*
* Code:
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *columnSizes array.
* Note: Both returned array and *columnSizes array must be malloced,
* assume caller calls free().
* int** subsets(int* nums, int numsSize, int** columnSizes, int* returnSize)
* {
* }
****************************************************************************/
static int subsets_compare(const void * a, const void * b)
{
return (*(int*)a - *(int*)b);
}
int** subsets(int* nums, int numsSize, int** columnSizes, int* returnSize)
{
int i = 0;
int j = 0;
int idx = 0;
int size = 0;
int max = 1 << numsSize;
int* temp = NULL;
int** result = NULL;
int* column = NULL;
if((nums == NULL) || (numsSize == 0) || (columnSizes == NULL)
|| (returnSize == NULL)) return NULL;
result = (int**)malloc(sizeof(int*) * max);
column = (int*)malloc(sizeof(int) * max);
for(i = 0;i < max;i++)
{
temp = (int*)malloc(sizeof(int) * max);
idx = 0;
size = 0;
j = i;
while(j > 0)
{
if(j & 1)
{
temp[size++] = nums[idx];
}
idx++;
j = j >> 1;
}
qsort(temp, size, sizeof(int), subsets_compare);
result[i] = temp;
column[i] = size;
}
*columnSizes = column;
*returnSize = max;
return result;
}
/*****************************************************************************
* 82: Remove Duplicates from Sorted List II
* Given a sorted linked list, delete all nodes that have duplicate numbers,
* leaving only distinct numbers from the original list.
*
* For example,
* Given 1->2->3->3->4->4->5, return 1->2->5.
* Given 1->1->1->2->3, return 2->3.
*
* Difficulty: Medium
*
* Link: https://oj.leetcode.com/problems/sort-list/
*
* Code:
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* };
* struct ListNode *deleteDuplicates(struct ListNode *head) {
*
* }
*
* 解法: 从当前链表中剪下第一个节点,这样就分成两个链表.对第二个链表进行遍历,如
* 果第二个链表的头元素等于第一个链表尾巴元素,则对第二个链表的元素执行删除操作
* ,直到不等于第一个链表尾元素即可,同时删除第一个链表的尾巴,并把第二个链表的头
* 元素,剪下来添加到第一个链表上.如果不等则把第二个链表的头元素剪下来添加到第
* 一个链表的尾巴上,并移动第一个链表的尾巴.如此循环直至第二个链表为空
*
* 变量解释:
* tail 第一个链表的尾巴
* prev 第一个链表尾巴的前驱
* curr 第二个链表的头(当前待处理的节点)
* next 第二个链表头的后继
****************************************************************************/
struct ListNode* deleteDuplicatesII(struct ListNode* head)
{
struct ListNode* prev = NULL;
struct ListNode* next = NULL;
struct ListNode* tail = NULL;
struct ListNode* curr = NULL;
if(head == NULL) return head;
curr = head->next;
head->next = NULL;
tail = head;
while(curr != NULL)
{
next = curr->next;
if(tail->val == curr->val)
{
while((curr != NULL) && (curr->val == tail->val))
{
next = curr->next;
free(curr);
curr = next;
}
if(curr != NULL)
{
next = curr->next;
curr->next = NULL;
}
if(prev == NULL)
{
free(tail);
head = tail = curr;
}
else
{
prev->next = curr;
free(tail);
tail = curr;
}
}
else
{
curr->next = NULL;
prev = tail;
tail->next = curr;
tail = tail->next;
}
curr = next;
}
return head;
}
/*****************************************************************************
* 83: Remove Duplicates from Sorted List
* Given a sorted linked list, delete all duplicates such that each element
* appear only once.
*
* For example,
* Given 1->1->2, return 1->2.
* Given 1->1->2->3->3, return 1->2->3.
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/remove-duplicates-from-sorted-list/
*
* Code:
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* };
* struct ListNode *deleteDuplicates(struct ListNode *head) {
*
* }
****************************************************************************/
struct ListNode* deleteDuplicates(struct ListNode* head)
{
struct ListNode* fast = NULL;
struct ListNode* slow = NULL;
struct ListNode* next = NULL;
if(head == NULL) return NULL;
slow = head;
fast = slow->next;
while((fast != NULL) && (slow != NULL))
{
while((fast != NULL) && (fast->val == slow->val))
{
next = fast->next;
free(fast);
fast = next;
}
slow->next = fast;
if(fast != NULL) fast = fast->next;
slow = slow->next;
}
return head;
}
/*****************************************************************************
* 86: Partition List
* 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.
* For example,
* Given 1->4->3->2->5->2 and x = 3, return 1->2->2->4->3->5.
*
* Difficulty: Medium
*
* Link: https://oj.leetcode.com/problems/partition-list/
*
* Code:
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* };
* struct ListNode *partition(struct ListNode *head, int x) {
*
* }
*
* 解法:
* 从头开始扫描单链表,如果遇到>x的节点,剪断单链表,变成两个单链表,记下第一个单
* 链表的尾巴.从第二个单链表开始扫描,遇到<=x的节点,剪下来接到第一个单链表的尾
* 巴,直至第二个单链表扫描完成.然后将第一个单链表与第二个单链表拼接.
****************************************************************************/
struct ListNode* partition(struct ListNode* head, int x)
{
struct ListNode* tail = NULL;
struct ListNode* curr = NULL;
struct ListNode* next = NULL;
struct ListNode* prev = NULL;
struct ListNode* second = NULL;
if(head == NULL) return head;
curr = head;
while((curr != NULL) && (curr->val < x))
{
tail = curr;
curr = curr->next;
}
if(curr == NULL)
{
return head;
}
second = curr;
prev = curr;
curr = curr->next;
while(curr != NULL)
{
next = curr->next;
if(curr->val < x)
{
prev->next = curr->next;
curr->next = NULL;
if(tail != NULL)
{
tail->next = curr;
tail = tail->next;
}
else
{
tail = curr;
head = tail;
}
}
else
{
prev = curr;
}
curr = next;
}
if(tail != NULL)
{
tail->next = second;
}
return head;
}
/*****************************************************************************
* 88: Merge Sorted Array
* Given two sorted integer arrays A and B, merge B into A as one sorted array.
*
* Note:
* You may assume that A has enough space (size that is greater or equal to
* m + n) to hold additional elements from B. The number of elements
* initialized in A and B are m and n respectively.
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/merge-sorted-array/
*
* Code:
* void merge(int* nums1, int m, int* nums2, int n) {
* }
*
* 解法:不用额外的存储空间
* 示例1:A[1,2,4,5,*,*,*]; B[3]
* 调用方法:A,4,B,1
* 第一轮循环:A[1,2,4,5,5]
* 第二轮循环:A[1,2,4,4,5]
* 第三轮循环:A[1,2,3,4,5]
* 从尾巴上开始存放,不会破坏A数组的原来的数据,把数据重新按有序的方法从尾端开始
* 排放.
****************************************************************************/
void merge(int* nums1, int m, int* nums2, int n)
{
int ia = 0;
int ib = 0;
int ic = 0;
if((nums1 == NULL) || (nums2 == NULL)) return;
if(n == 0) return;
ia = m - 1;
ib = n - 1;
ic = m + n - 1;
while((ia >= 0) && (ib >= 0))
{
if(nums1[ia] > nums2[ib])
{
nums1[ic--] = nums1[ia--];
}
else
{
nums1[ic--] = nums2[ib--];
}
}
for(ic = 0; ic <= ib; ic++)
{
nums1[ic] = nums2[ic];
}
}
/*****************************************************************************
* 92: Reverse Linked List II
* Reverse a linked list from position m to n. Do it in-place and in one-pass.
*
* For example:
* Given 1->2->3->4->5->NULL, m = 2 and n = 4,
* return 1->4->3->2->5->NULL.
*
* Note:
* Given m, n satisfy the following condition: 1 ≤ m ≤ n ≤ length of list.
*
* Difficulty: Medium
*
* Link: https://oj.leetcode.com/problems/reverse-linked-list-ii/
*
* Code:
*
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* };
* struct ListNode* reverseBetween(struct ListNode* head, int m, int n) {
* }
*
* 解法:
* |-------------|
* V
* 头---尾 尾---头 头---尾
* ^
* |________|
* 从链表头往后数m个节点,然后把接下来的m-n+1个节点反序,然后再把剩下的接上.
****************************************************************************/
struct ListNode* reverseBetween(struct ListNode* head, int m, int n)
{
struct ListNode* curr = NULL;
struct ListNode* prev = NULL;
struct ListNode* next = NULL;
struct ListNode* tail1 = NULL;
struct ListNode* tail2 = NULL;
if(head == NULL) return head;
if((m <= 0) || (n <= 0) || (m > n)) return NULL;
if(head->next == NULL) return head;
if(m == n) return head;
n = n - m;
m = m - 1;
for(curr = head; (m > 0) && (curr != NULL); m--)
{
prev = curr;
curr = curr->next;
}
tail2 = curr;
tail1 = prev;
prev = curr;
curr = curr->next;
while((curr != NULL) && (n-- > 0))
{
next = curr->next;
curr->next = prev;
prev = curr;
curr = next;
}
if(tail2 != NULL)
{
tail2->next = curr;
}
if(tail1 != NULL)
{
tail1->next = prev;
}
else
{
head = prev;
}
return head;
}
/*****************************************************************************
* 94: Binary Tree Inorder Traversal
* Given a binary tree, return the inorder traversal of its nodes' values.
* For example: Given binary tree {1,#,2,3},
* 1
* \
* 2
* /
* 3
* return [1,3,2].
*
* Note: Recursive solution is trivial, could you do it iteratively?
*
* Difficulty: Medium
*
* Link: https://oj.leetcode.com/problems/binary-tree-inorder-traversal/
*
* Code:
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* };
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
* int* inorderTraversal(struct TreeNode* root, int* returnSize) {
*
* }
****************************************************************************/
static void inorder(struct TreeNode* root, int* list, int* index)
{
if(root == NULL) return;
inorder(root->left, list, index);
list[*index] = root->val;
*index += 1;
inorder(root->right, list, index);
}
int* inorderTraversal(struct TreeNode* root, int* returnSize)
{
int* l = NULL;
int index = 0;
if((root == NULL) || (returnSize == NULL)) return NULL;
TreeGetNodesNumber(root, returnSize);
l = (int*)malloc(sizeof(int) * (*returnSize));
inorder(root, l, &index);
return l;
}
/*****************************************************************************
* 98: Validate Binary Search Tree
* Given a binary tree, determine if it is a valid binary search tree (BST).
* Assume a BST is defined as follows:
* (1)The left subtree of a node contains only nodes with keys less than the
* node's key.
* (2)The right subtree of a node contains only nodes with keys greater than
* the node's key.
* (3)Both the left and right subtrees must also be binary search trees.
*
* Difficulty: Medium
*
* Link: https://oj.leetcode.com/problems/validate-binary-search-tree/
*
* Code:
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* };
* bool isValidBST(struct TreeNode *root) {
* }
* };
* 二叉搜索树定义为或者是一棵空树，或者是具有下列性质的二叉树:若它的左子树
* 不空，则左子树上所有结点的值均小于它的根结点的值；若它的右子树不空，则右
* 子树上所有结点的值均大于它的根结点的值:它的左、右子树也分别为二叉排序树。
* 递归判断，递归时传入两个参数，一个是左界，一个是右界，节点的值必须在两个界
* 的中间，同时在判断做子树和右子树时更新左右界。
* 在http://blog.csdn.net/longhopefor/article/details/25687119有个说明.
* 用栈的解法:
* bool isValidBST(struct TreeNode* root)
* {
* Stack* s = NULL;
* struct TreeNode* p = NULL;
* int64_t last_val = INT64_MIN;
* bool status = true;
*
* if(root == NULL) return true;
* s = StackNew();
* p = root;
* while((p != NULL) || (!StackIsEmpty(s)))
* {
* while(p != NULL)
* {
* StackPush(s, p);
* p = p->left;
* }
* if(!StackIsEmpty(s))
* {
* p = StackPop(s);
* if(p->val <= last_val)
* {
* status = false;
* break;
* }
* last_val = p->val;
* p = p->right;
* }
* }
* StackDestroy(s);
* return status;
* }
****************************************************************************/
static bool IsBST(struct TreeNode* root, int64_t left, int64_t right)
{
if(root == NULL)
{
return true;
}
return (left < root->val) && (root->val < right)
&& IsBST(root->left, left, root->val)
&& IsBST(root->right, root->val, right);
}
bool isValidBST(struct TreeNode* root)
{
return IsBST(root, INT64_MIN, INT64_MAX);
}
/*****************************************************************************
* 100:Same Tree
* Given two binary trees, write a function to check if they are equal or not.
* Two binary trees are considered equal if they are structurally identical
* and the nodes have the same value.
*
* Difficulty: Easy
*
* Link:https://oj.leetcode.com/problems/same-tree/
*
* Code:
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* };
* bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
*
* }
****************************************************************************/
bool isSameTree(struct TreeNode* p, struct TreeNode* q)
{
if((p == NULL) && (q == NULL)) return true;
if((p == NULL) || (q == NULL)) return false;
if((p->val == q->val)
&& isSameTree(p->left, q->left) && isSameTree(p->right, q->right))
{
return true;
}
else
{
return false;
}
}
/*****************************************************************************
* 101:Symmetric Tree
* Given a binary tree, check whether it is a mirror of itself (ie, symmetric
* around its center).
* For example, this binary tree is symmetric:
* 1
* / \
* 2 2
* / \ / \
* 3 4 4 3
* But the following is not:
* 1
* / \
* 2 2
* \ \
* 3 3
* Note: Bonus points if you could solve it both recursively and iteratively.
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/symmetric-tree/
*
* Code:
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* };
* bool isSymmetric(struct TreeNode *root) {
*
* }
*原来用队列,列表的解法,非递归
bool leetcode_101_is_symmetric(TreeNode* root)
{
dlist_t* array = NULL;
queue_t* q = NULL;
queue_t* q2 = NULL;
queue_t* temp = NULL;
TreeNode* p = NULL;
TreeNode* p2 = NULL;
bool status = true;
int index = 0;
int size = 0;
if(root == NULL) return true;
q = lbe_queue_dlist_new(NULL);
q2 = lbe_queue_dlist_new(NULL);
array = lbe_dlist_new(NULL);
lbe_queue_push(q, root);
while(!lbe_queue_is_empty(q) && (status == true))
{
while(!lbe_queue_is_empty(q))
{
p = lbe_queue_pop0(q);
if(p != NULL)
{
if(p->left != NULL) lbe_queue_push(q2, p->left);
if(p->right != NULL) lbe_queue_push(q2, p->right);
lbe_dlist_append(array, p->left);
lbe_dlist_append(array, p->right);
}
else
{
lbe_dlist_append(array, NULL);
lbe_dlist_append(array, NULL);
}
}
size = lbe_dlist_size(array);
if(size % 2 != 0)
{
status = false;
break;
}
for(index = 0; index < size / 2; index++)
{
lbe_dlist_get(array, index, (void**)&p);
lbe_dlist_get(array, size - index - 1, (void**)&p2);
if(((p == NULL) && (p2 != NULL)) || ((p != NULL) && (p2 == NULL)))
{
status = false;
break;
}
if((p != NULL) && (p2 != NULL) && (p->val != p2->val))
{
status = false;
break;
}
}
lbe_dlist_clear(array);
temp = q2;
q2 = q;
q = temp;
}
lbe_queue_free(q);
lbe_queue_free(q2);
return status;
}
****************************************************************************/
static bool isSubtreeSymmetric(struct TreeNode* p, struct TreeNode* q)
{
if((p == NULL) && (q == NULL)) return true;
if((p == NULL) || (q == NULL)) return false;
return (p->val == q->val)
&& isSubtreeSymmetric(q->left, p->right)
&& isSubtreeSymmetric(q->right, p->left);
}
bool isSymmetric(struct TreeNode* root)
{
if(root == NULL) return true;
return isSubtreeSymmetric(root->left, root->right);
}
/*****************************************************************************
* 102:Binary Tree Level Order Traversal
* Given a binary tree, return the level order traversal of its nodes' values.
* (ie, from left to right, level by level).
* For example: Given binary tree {3,9,20,#,#,15,7},
* 3
* / \
* 9 20
* / \
* 15 7
* return its level order traversal as:
* [
* [3],
* [9,20],
* [15,7]
* ]
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/binary-tree-level-order-traversal/
*
* Code:
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* };
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *columnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume
* caller calls free().
* int** levelOrder(struct TreeNode* root, int** columnSizes, int* returnSize)
* {
* }
****************************************************************************/
int** levelOrder(struct TreeNode* root, int** columnSizes, int* returnSize)
{
int** vector = NULL;
Queue* q1 = NULL;
Queue* q2 = NULL;
Queue* temp = NULL;
struct TreeNode* p = NULL;
int height = 0;
int index = 0;
if((root == NULL) || (columnSizes == NULL) || (returnSize == NULL))
{
return NULL;
}
*returnSize = TreeHeight(root) + 1;
vector = (int**)malloc(sizeof(int*) * (*returnSize));
if(vector == NULL)
{
return NULL;
}
*columnSizes = (int*)malloc(sizeof(int) * (*returnSize));
if(*columnSizes == NULL)
{
free(vector);
return NULL;
}
q1 = QueueNew();
q2 = QueueNew();
QueuePush(q1, root);
while(!QueueIsEmpty(q1))
{
(*columnSizes)[height] = QueueSize(q1);
vector[height] = (int*)malloc(sizeof(int) * ((*columnSizes)[height]));
while(!QueueIsEmpty(q1))
{
p = QueuePop(q1);
vector[height][index++] = p->val;
if(p->left != NULL)
{
QueuePush(q2, p->left);
}
if(p->right != NULL)
{
QueuePush(q2, p->right);
}
}
temp = q2;
q2 = q1;
q1 = temp;
height++;
index = 0;
}
QueueDestroy(q1);
QueueDestroy(q2);
return vector;
}
/*****************************************************************************
* 104:Maximum Depth of Binary Tree
* Given a binary tree, find its maximum depth.
* The maximum depth is the number of nodes along the longest path from the
* root node down to the farthest leaf node.
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/maximum-depth-of-binary-tree/
*
* Code:
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* };
* int maxDepth(struct TreeNode *root) {
* }
****************************************************************************/
int maxDepth(TreeNode* root)
{
int left_depth = 0;
int right_depth = 0;
if(root == NULL) return 0;
if((root->left == NULL) && (root->right == NULL)) return 1;
left_depth = maxDepth(root->left) + 1;
right_depth = maxDepth(root->right) + 1;
return left_depth > right_depth ? left_depth : right_depth;
}
/*****************************************************************************
* 107: Binary Tree Level Order Traversal II
* Given a binary tree, return the bottom-up level order traversal of its
* nodes' values. (ie, from left to right, level by level from leaf to root).
* For example:
* Given binary tree {3,9,20,#,#,15,7},
* 3
* / \
* 9 20
* / \
* 15 7
* return its bottom-up level order traversal as:
* [
* [15,7],
* [9,20],
* [3]
* ]
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/binary-tree-level-order-traversal-ii/
*
* Code:
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* };
* Return an array of arrays of size *returnSize.
* The sizes of the arrays are returned as *columnSizes array.
* Note: Both returned array and *columnSizes array must be malloced, assume
* caller calls free().
* int** levelOrderBottom(struct TreeNode* root, int** columnSizes,
* int* returnSize) {
*
* }
*****************************************************************************/
int** levelOrderBottom(struct TreeNode* root, int** columnSizes, int* returnSize)
{
int** vector = NULL;
Queue* q = NULL;
Queue* q2 = NULL;
Queue* q3 = NULL;
Queue* temp = NULL;
Stack* s = NULL;
struct TreeNode* p = NULL;
int height = 0;
int index = 0;
if((root == NULL) || (columnSizes == NULL) || (returnSize == NULL))
{
return NULL;
}
*returnSize = TreeHeight(root) + 1;
*returnSize = TreeHeight(root) + 1;
vector = (int**)malloc(sizeof(int*) * (*returnSize));
if(vector == NULL)
{
return NULL;
}
*columnSizes = (int*)malloc(sizeof(int) * (*returnSize));
if(*columnSizes == NULL)
{
free(vector);
return NULL;
}
q = QueueNew();
q2 = QueueNew();
q3 = QueueNew();
s = StackNew();
QueuePush(q3, root);
StackPush(s, q3);
QueuePush(q, root);
while(!QueueIsEmpty(q))
{
q3 = QueueNew();
while(!QueueIsEmpty(q))
{
p = QueuePop(q);
if(p->left != NULL)
{
QueuePush(q2, p->left);
QueuePush(q3, p->left);
}
if(p->right != NULL)
{
QueuePush(q2, p->right);
QueuePush(q3, p->right);
}
}
if(!QueueIsEmpty(q3))
{
StackPush(s, q3);
}
else
{
QueueDestroy(q3);
}
temp = q2;
q2 = q;
q = temp;
}
while(!StackIsEmpty(s))
{
temp = StackPop(s);
(*columnSizes)[height] = QueueSize(temp);
vector[height] = (int*)malloc(sizeof(int) * ((*columnSizes)[height]));
while(!QueueIsEmpty(temp))
{
p = QueuePop(temp);
vector[height][index++] = p->val;
}
index = 0;
height++;
QueueDestroy(temp);
}
QueueDestroy(q);
QueueDestroy(q2);
StackDestroy(s);
return vector;
}
/*****************************************************************************
* 110: Balanced Binary Tree
* Given a binary tree, determine if it is height-balanced.
* For this problem, a height-balanced binary tree is defined as a binary
* tree in which the depth of the two subtrees of every node never differ
* by more than 1.
*
* Difficulty: Easy
*
* Link:https://oj.leetcode.com/problems/balanced-binary-tree/
*
* Code:
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
* class Solution {
* public:
* bool isBalanced(TreeNode *root) {
*
* }
* };
****************************************************************************/
bool leetcode_110_is_balanced(TreeNode* root)
{
if(root == NULL) return true;
return leetcode_110_is_balanced(root->left)
&& leetcode_110_is_balanced(root->right);
}
/*****************************************************************************
* 111:Minimum Depth of Binary Tree
* Given a binary tree, find its minimum depth.
* The minimum depth is the number of nodes along the shortest path from the
* root node down to the nearest leaf node.
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/minimum-depth-of-binary-tree/
*
* Code:
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
* class Solution {
* public:
* int minDepth(TreeNode *root) {
*
* }
* };
****************************************************************************/
int leetcode_111_min_depth(TreeNode* root)
{
int left_depth = 0;
int right_depth = 0;
if(root == NULL) return 0;
if((root->left == NULL) && (root->right == NULL)) return 1;
if((root->left == NULL) && (root->right != NULL))
{
return 1 + leetcode_111_min_depth(root->right);
}
if((root->left != NULL) && (root->right == NULL))
{
return 1 + leetcode_111_min_depth(root->left);
}
left_depth = leetcode_111_min_depth(root->left) + 1;
right_depth = leetcode_111_min_depth(root->right) + 1;
return left_depth > right_depth ? right_depth : left_depth;
}
/*****************************************************************************
* 112: Path Sum
* Given a binary tree and a sum, determine if the tree has a root-to-leaf
* path such that adding up all the values along the path equals the given
* sum.
*
* For example:
* Given the below binary tree and sum = 22,
* 5
* / \
* 4 8
* / / \
* 11 13 4
* / \ \
* 7 2 1
* return true, as there exist a root-to-leaf path 5->4->11->2 which sum is 22.
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/path-sum/
*
* Code:
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*
* class Solution {
* public:
* bool hasPathSum(TreeNode *root, int sum) {
* }
* };
****************************************************************************/
bool leetcode_112_has_path_sum(TreeNode* root, int sum)
{
if(root == NULL) return false;
if((root->left == NULL) && (root->right == NULL) && ((sum- root->val) == 0)) return true;
return leetcode_112_has_path_sum(root->left, sum - root->val) ||
leetcode_112_has_path_sum(root->right, sum - root->val);
}
/*****************************************************************************
* 114:Flatten Binary Tree to Linked List
* Given a binary tree, flatten it to a linked list in-place.
* For example,
* Given
* 1
* / \
* 2 5
* / \ \
* 3 4 6
* The flattened tree should look like:
* 1
* \
* 2
* \
* 3
* \
* 4
* \
* 5
* \
* 6
* Hints: If you notice carefully in the flattened tree, each node's right
* child points to the next node of a pre-order traversal.
*
* Difficulty: Medium
*
* Link:https://oj.leetcode.com/problems/flatten-binary-tree-to-linked-list/
*
* Code:
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
* class Solution {
* public:
* void flatten(TreeNode *root) {
*
* }
* };
****************************************************************************/
void leetcode_114_flatten(TreeNode* root)
{
#if 0
stack_t* s = NULL;
TreeNode* p = NULL;
TreeNode* q = NULL;
if(root == NULL) return;
s = lbe_stack_dlist_new(NULL);
lbe_stack_push(s, root);
while(!lbe_stack_is_empty(s))
{
p = lbe_stack_pop0(s);
if(p->right != NULL) lbe_stack_push(s, p->right);
if(p->left != NULL) lbe_stack_push(s, p->left);
p->left = p->right = NULL;
if(q == NULL)
{
q = p;
}
else
{
q->right = p;
q = q->right;
}
}
lbe_stack_free(s);
#endif
}
/*****************************************************************************
* 116: Populating Next Right Pointers in Each Node
* Given a binary tree
* struct TreeLinkNode {
* TreeLinkNode *left;
* TreeLinkNode *right;
* TreeLinkNode *next;
* }
* Populate each next pointer to point to its next right node. If there is
* no next right node, the next pointer should be set to NULL.
* Initially, all next pointers are set to NULL.
*
* Note:
* (1):You may only use constant extra space.
* (2):You may assume that it is a perfect binary tree (ie, all leaves are
* at the same level, and every parent has two children).
*
* For example,
* Given the following perfect binary tree,
* 1
* / \
* 2 3
* / \ / \
* 4 5 6 7
* After calling your function, the tree should look like:
* 1 -> NULL
* / \
* 2 -> 3 -> NULL
* / \ / \
* 4->5->6->7 -> NULL
*
* Difficulty: Medium
*
* Link: https://oj.leetcode.com/problems/populating-next-right-pointers-in-each-node/
*
* Code:
* Definition for binary tree with next pointer.
* struct TreeLinkNode {
* int val;
* TreeLinkNode *left, *right, *next;
* TreeLinkNode(int x) : val(x), left(NULL), right(NULL), next(NULL) {}
* };
* class Solution {
* public:
* void connect(TreeLinkNode *root) {
*
* }
* };
****************************************************************************/
void leetcode_116_connect(TreeLinkNode* root)
{
#if 0
queue_t* q1 = NULL;
queue_t* q2 = NULL;
queue_t* temp = NULL;
TreeLinkNode* p1 = NULL;
TreeLinkNode* p2 = NULL;
if(root == NULL) return;
q1 = lbe_queue_dlist_new(NULL);
q2 = lbe_queue_dlist_new(NULL);
lbe_queue_push(q1, root);
while(!lbe_queue_is_empty(q1))
{
while(!lbe_queue_is_empty(q1))
{
p1 = lbe_queue_pop0(q1);
if(p2 == NULL)
{
p2 = p1;
}
else
{
p2->next = p1;
p2 = p2->next;
}
if(p1->left != NULL)
{
lbe_queue_push(q2, p1->left);
}
if(p1->right != NULL)
{
lbe_queue_push(q2, p1->right);
}
}
p2 = NULL;
temp = q2;
q2 = q1;
q1 = temp;
}
lbe_queue_free(q1);
lbe_queue_free(q2);
#endif
}
/*****************************************************************************
* 118:Pascal's Triangle
* Given numRows, generate the first numRows of Pascal's triangle.
* For example, given numRows = 5,Return
* [
* [1],
* [1,1],
* [1,2,1],
* [1,3,3,1],
* [1,4,6,4,1]
* ]
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/pascals-triangle/
*
* Code:
* class Solution {
* public:
* vector<vector<int> > generate(int numRows) {
* }
* };
****************************************************************************/
#if 0
list_t* leetcode_118_generate(int num_rows)
{
list_t* rows = NULL;
list_t* row = NULL;
list_t* last = NULL;
int i = 0;
int j = 0;
int v1 = 0;
int v2 = 0;
rows = lbe_list_new((free_func_t)lbe_list_free);
if(num_rows <= 0) return rows;
for(i = 0; i < num_rows; i++)
{
row = lbe_list_new(NULL);
lbe_list_append(row, (void*)1);
for(j = 1; j <= i; j++)
{
if(j == i)
{
lbe_list_append(row, (void*)1);
}
else
{
lbe_list_get(last, j, (void**)&v1);
lbe_list_get(last, j - 1, (void**)&v2);
lbe_list_append(row, (void*)(v1 + v2));
}
}
last = row;
lbe_list_append(rows, row);
}
return rows;
}
#endif
/*****************************************************************************
* 119: Pascal's Triangle II
* Given an index k, return the kth row of the Pascal's triangle.
* For example, given k = 3,
* Return [1,3,3,1].
* Note:
* Could you optimize your algorithm to use only O(k) extra space?
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/pascals-triangle-ii/
*
* Code:
* class Solution {
* public:
* vector<int> getRow(int rowIndex) {
* }
* };
* 杨辉三角:
* 前提：端点的数为1.
* 1、每个数等于它上方两数之和。
* 2、每行数字左右对称，由1开始逐渐变大。
* 3、第n行的数字有n项。
* 4、第n行数字和为2n-1。
* 5、第n行的第m个数和第n-m+1个数相等，即C(n-1,m-1)=C(n-1,n-m)（组合数性质之一）
* 6、每个数字等于上一行的左右两个数字之和。可用此性质写出整个杨辉三角。即第n+1行的第i个数
* 等于第n行的第i-1个数和第i个数之和，这也是组合数的性质之一。即C(n+1,i)=C(n,i)+C(n,i-1)
* 7、第n行的m个数可表示为C(n-1,m-1)（n-1下标，m-1上标），即为从n-1个不同元素中取m-1
* 个元素的组合数。（见右图）组合数计算方法：C(n,m)=n!/[m!(n-m)!]
* 8、(a+b)^n的展开式中的各项系数依次对应杨辉三角的第(n+1)行中的每一项。
* 9、将第2n+1行第1个数，跟第2n+2行第3个数、第2n+3行第5个数……连成一线，这些数的和是第
* 4n+1个斐波那契数；将第2n行第2个数(n>1)，跟第2n-1行第4个数、第2n-2行第6个数……这些数
* 之和是第4n-2个斐波那契数。
* 10、将各行数字相排列，可得11的n-1（n为行数）次方：1=11^0; 11=11^1; 121=11^2……;
* 细心的人可能会发现当n≥5时会不符合这一条性质，其实是这样的：把第n行的最右面的数字"1"放在
* 个位，然后把左面的一个数字的个位对齐到十位... ...，以此类推，把空位用“0”补齐，然后把所有
* 的数加起来，得到的数正好是11的n-1次方。以n=11为例，第十一行的数为：
* 1,10,45,120,210,252,210,120,45,10,1；
*
* 第n行的:
* 第一个数为1，
* 第二个数为1×(n-1)，
* 第三个数为1×(n-1)×（n-2）/2，
* 第四个数为1×(n-1)×（n-2）/2×（n-3）/3…依此类推。
*
* k = 3(n=4), Return [1,3,3,1].
* k = 4(n=5), Return [1,4,6,4,1]
****************************************************************************/
#if 0
list_t* leetcode_119_get_row(int row_index)
{
int v1 = 0;
int v2 = 0;
int i = 0;
int j = 0;
list_t* l = NULL;
if(row_index <= 0) return NULL;
l = lbe_list_new(NULL);
for(i = 0; i < (row_index + 1); i++)
{
lbe_list_append(l, (void*)1);
}
for(i = 1; i <= row_index; i++)
{
for(j = i; j > 0; j--)
{
if(j == i)
{
lbe_list_set(l, j, (void*)1);
}
else
{
lbe_list_get(l, j, (void**)&v1);
lbe_list_get(l, j - 1, (void**)&v2);
lbe_list_set(l, j, (void*)(v1 + v2));
}
}
}
return l;
}
#endif
/*****************************************************************************
* 125: Valid Palindrome
* Given a string, determine if it is a palindrome, considering only
* alphanumeric characters and ignoring cases.
* For example,
* "A man, a plan, a canal: Panama" is a palindrome.
* "race a car" is not a palindrome.
* Note:
* Have you consider that the string might be empty? This is a good question
* to ask during an interview.
* For the purpose of this problem, we define empty string as valid palindrome.
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/valid-palindrome/
*
* Code:
* class Solution {
* public:
* bool isPalindrome(string s) {
* }
* };
****************************************************************************/
bool leetcode_125_is_palindrome(char* p)
{
//const char* p = s.c_str();
const char* e = NULL;
if(p == NULL) return false;
if(*p == '\0') return true;
e = p;
while(*e) // move to end;
{
e++;
}
while(p <= e)
{
if(!isalnum(*p))
{
p++;
}
else if(!isalnum(*e))
{
e--;
}
else if(tolower(*p) == tolower(*e))
{
p++;
e--;
}
else
{
return false;
}
}
return true;
}
/*****************************************************************************
* 136: Single Number
* Given an array of integers, every element appears twice except for one.
* Find that single one.
* Note: Your algorithm should have a linear runtime complexity. Could you
* implement it without using extra memory?
*
* Difficulty: Medium
*
* Link: https://oj.leetcode.com/problems/single-number/
*
* Code:
* class Solution {
* public:
* int singleNumber(int A[], int n) {
* }
* };
* 解法: http://www.cnblogs.com/changchengxiao/p/3413294.html
* 对于异或来说：
* 1. 异或运算是可交换，即 a ^ b = b ^ a
* 2. 0 ^ a = a
* 那么如果对所有元素做异或运算，其结果为那个出现一次的元素，理解是a1 ^ a2 ^ ....，可以将
* 所有相同元素交换至相邻位置，首先运算相同元素，则会产生(n - 1)/2个0异或积，剩余一个单一
* 元素，他们的异或积为这个单一元素自己，得解。
* 本题扩展
* 1.一个数组中有两个元素只出现一次，其他所有元素都出现两次，求这两个只出现一次的元素
* [解题思路]
* 将数组所有元素都进行异或得到一个不为0的结果，根据这个结果中的不为0的某一位将数组分成两组,
* 将两组中的元素进行异或，如两个数组的异或值都不为0，则得到最后结果
* 2.一个数组中有一个元素只出现1次，其他所有元素都出现k次，求这个只出现1次的元素
* [解题思路]
* 当k为偶数时，同lss,当k为奇数时，将数组中每个元素的每一位相加mod k，得到结果即位出现1次的
* 元素，时间复杂度O(nlen)，空间复杂度为O(1)
****************************************************************************/
int leetcode_136_single_number(int A[], int n)
{
int i = 0;
int result = 0;
if((A == NULL) || (n == 0)) return 0;
if(n % 2 != 1) return 0;
result = A[0];
for(i = 1; i < n; i++)
{
result = result ^ A[i];
}
return result;
}
/*****************************************************************************
* 137:Single Number II
* Given an array of integers, every element appears three times except for
* one. Find that single one.
* Note: Your algorithm should have a linear runtime complexity. Could you
* implement it without using extra memory?
*
* Difficulty: Medium
*
* Link: https://oj.leetcode.com/problems/single-number-ii/
*
* Code:
* class Solution {
* public:
* int singleNumber(int A[], int n) {
* }
* };
* 解法: http://blog.csdn.net/jiadebin890724/article/details/23306837
* int数据共有32位，可以用32变量存储这N个元素中各个二进制位上1出现的次数，最后在进行模三操
* 作，如果为1，那说明这一位是要找元素二进制表示中为1的那一位。时间：O(32*N)，这是一个通用
* 的解法，如果把出现3次改为 k 次，那么只需模k就行了。
****************************************************************************/
int leetcode_137_signle_number_ii(int A[], int n)
{
int i = 0;
int j = 0;
int bitnum[32] = {0};
int res = 0;
if((A == NULL) || (n == 0)) return 0;
if(n % 3 != 1) return 0;
for(i = 0; i < 32; i++){
for(j = 0; j < n; j++){
bitnum[i] += (A[j]>>i)&1;
}
res |= (bitnum[i] % 3) << i;
}
return res;
}
/*****************************************************************************
* 141:Linked List Cycle
* Given a linked list, determine if it has a cycle in it.
*
* Follow up: Can you solve it without using extra space?
*
* Difficulty: Medium
*
* Link: https://oj.leetcode.com/problems/linked-list-cycle/
*
* Code:
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
* class Solution {
* public:
* bool hasCycle(ListNode *head) {
*
* }
* };
****************************************************************************/
bool leetcode_141_has_cycle(ListNode* head)
{
ListNode* fast = NULL;
ListNode* slow = NULL;
if(head == NULL) return false;
if(head->next == head) return true;
fast = slow = head;
while((fast != NULL) && (fast->next != NULL))
{
slow = slow->next;
fast = fast->next->next;
if(slow == fast)
{
return true;
}
}
return false;
}
/*****************************************************************************
* 142:Linked List Cycle II
* Given a linked list, return the node where the cycle begins. If there is
* no cycle, return null.
*
* Follow up: can you solve it without using extra space
*
* Difficulty: Medium
*
* Link: https://oj.leetcode.com/problems/linked-list-cycle-ii/
*
* Code:
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
* class Solution {
* public:
* ListNode *detectCycle(ListNode *head) {
*
* }
* };
*
* Input: {1}, no cycle
* Output: tail connects to node index 0
* Expected: no cycle
*
****************************************************************************/
ListNode* leetcode_142_detect_cycle(ListNode* head)
{
ListNode* fast = NULL;
ListNode* slow = NULL;
if(head == NULL) return NULL;
if(head->next == NULL) return NULL;
if(head->next == head) return head;
slow = fast = head;
while((fast != NULL) && (fast->next != NULL))
{
fast = fast->next->next;
slow = slow->next;
if(fast == slow)
{
break;
}
}
if(fast != slow)
{
return NULL;
}
fast = head;
while(fast != slow)
{
fast = fast->next;
slow = slow->next;
}
return fast;
}
/*****************************************************************************
* 143: Reorder List
* Given a singly linked list L: L0→L1→…→Ln-1→Ln,
* reorder it to: L0→Ln→L1→Ln-1→L2→Ln-2→…
* You must do this in-place without altering the nodes' values.
* For example, Given {1,2,3,4}, reorder it to {1,4,2,3}.
*
* Difficulty: Medium
*
* Link: https://oj.leetcode.com/problems/reorder-list/
*
* Code:
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
* class Solution {
* public:
* void reorderList(ListNode *head) {
*
* }
* };
* 解法:
* 先把链表的头剪下来,这样分成两个链表,循环遍历第二链表,第一次先剪下链表的尾巴接到第一个链表的
* 尾巴,第二次剪下链表的头部,接到第一个链表的尾巴.直到第二个链表为空.
* 递归解法的思想:
* 从单链表中剪下头和尾巴,如果无法剪下或只剪下头或只剪下为尾巴,递归结束.
* 前面的解法太耗时间,重新实现:
* 把链表一分为二.然后把第二个链表反转.然后把第一个链表与第二个链表连接起来即可.
* 对单链表遍历了O(n) + O(n/2) + O(n/2) + O(n/2) = 2n + n/2
* 而第一种方法则遍历了, (n - 1) + (n - 2 - 1) + (n - 2 - 2 - 1) + ...
****************************************************************************/
void leetcode_143_reorder_list(ListNode* head)
{
#if 0
ListNode* p = NULL;
ListNode* tail = NULL;
ListNode* t = NULL;
ListNode* prev = NULL;
if(head == NULL) return;
p = head->next;
head->next = NULL;
tail = head;
while(p != NULL)
{
t = p;
while(t->next != NULL)
{
prev = t;
t = t->next;
}
if(t == p)
{
tail->next = p;
p = p->next;
tail = tail->next;
tail->next = NULL;
}
else
{
prev->next = NULL;
tail->next = t;
tail = tail->next;
tail->next = p;
tail = tail->next;
p = p->next;
tail->next = NULL;
}
}
#else
ListNode* p1 = NULL; //first list
ListNode* p2 = NULL; //second list
ListNode* tail = NULL; //first list tail
ListNode* prev = NULL;
ListNode* next = NULL;
ListNode* p1_next = NULL;
ListNode* p2_next = NULL;
if(head == NULL) return;
p2 = p1 = head;
while((p1 != NULL) && (p1->next != NULL))
{
p2 = p2->next;
p1 = p1->next->next;
}
tail = p2;
p2 = p2->next;
tail->next = NULL;
while(p2 != NULL)
{
next = p2->next;
p2->next = prev;
prev = p2;
p2 = next;
}
p1 = head->next;
head->next = NULL;
tail = head;
p2 = prev;
while((p1 != NULL) && (p2 != NULL))
{
p1_next = p1->next;
p2_next = p2->next;
tail->next = p2;
tail = tail->next;
tail->next = p1;
tail = tail->next;
tail->next = NULL;
p1 = p1_next;
p2 = p2_next;
}
if(p1 != NULL)
{
tail->next = p1;
}
#endif
}
/*****************************************************************************
* 144: Binary Tree Preorder Traversal
* Given a binary tree, return the preorder traversal of its nodes' values.
* For example:
* Given binary tree {1,#,2,3},
* 1
* \
* 2
* /
* 3
* return [1,2,3].
* Note: Recursive solution is trivial, could you do it iteratively?
*
* Difficulty: Medium
*
* Link: https://oj.leetcode.com/problems/binary-tree-preorder-traversal/
*
* Code:
* Definition for binary tree
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
* class Solution {
* public:
* vector<int> preorderTraversal(TreeNode *root) {
* }
* };
****************************************************************************/
#if 0
list_t* leetcode_144_preorder_traversal(TreeNode* root)
{
list_t* l = NULL;
stack_t* s = NULL;
TreeNode* p = NULL;
if(root == NULL) return NULL;
s = lbe_stack_dlist_new(NULL);
l = lbe_list_new(NULL);
lbe_stack_push(s, root);
while(!lbe_stack_is_empty(s))
{
p = lbe_stack_pop0(s);
lbe_list_append(l, (void*)p->val);
if(p->right != NULL) lbe_stack_push(s, p->right);
if(p->left != NULL) lbe_stack_push(s, p->left);
}
lbe_stack_free(s);
return l;
}
#endif
/*****************************************************************************
* 147: Insertion Sort List
* Sort a linked list using insertion sort.
*
* Difficulty: Medium
*
* Link: https://oj.leetcode.com/problems/insertion-sort-list/
*
* Code:
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
* class Solution {
* public:
* ListNode *insertionSortList(ListNode *head) {
*
* }
* };
****************************************************************************/
ListNode* leetcode_147_insertion_sort_list(ListNode* head)
{
ListNode* sort = NULL;
ListNode* prev = NULL;
ListNode* p = NULL;
ListNode* t = NULL;
ListNode* next = NULL;
if(head == NULL) return head;
sort = head;
p = head->next;
sort->next = NULL;
while(p != NULL)
{
next = p->next;
p->next = NULL;
t = sort;
prev = NULL;
while(t != NULL)
{
if(t->val > p->val)
{
break;
}
prev = t;
t = t->next;
}
if(prev != NULL)
{
p->next = prev->next;
prev->next = p;
}
else
{
p->next = sort;
sort = p;
}
p = next;
}
return sort;
}
/*****************************************************************************
* 155:Min Stack
* Design a stack that supports push, pop, top, and retrieving the minimum
* element in constant time.
* push(x) -- Push element x onto stack.
* pop() -- Removes the element on top of the stack.
* top() -- Get the top element.
* getMin() -- Retrieve the minimum element in the stack.
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/min-stack/
*
* Code:
* class MinStack {
* public:
* void push(int x) {
* }
*
* void pop() {
* }
*
* int top() {
* }
*
* int getMin() {
* }
* };
****************************************************************************/
MinStack* leetcode_155_min_stack(void)
{
//return MinStackNew();
}
/*****************************************************************************
* 160:Intersection of Two Linked Lists
* Write a program to find the node at which the intersection of two singly
* linked lists begins.
*
* For example, the following two linked lists:
* A: a1 → a2
* ↘
* c1 → c2 → c3
* ↗
* B: b1 → b2 → b3
* begin to intersect at node c1.
*
* Notes:
* If the two linked lists have no intersection at all, return null.
* The linked lists must retain their original structure after the function returns.
* You may assume there are no cycles anywhere in the entire linked structure.
* Your code should preferably run in O(n) time and use only O(1) memory.
*
* Difficulty: Easy
*
* Link:https://oj.leetcode.com/problems/intersection-of-two-linked-lists/
*
* Code:
* 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) {
*
* }
* };
****************************************************************************/
ListNode* leetcode_160_get_intersection_node(ListNode* headA, ListNode* headB)
{
ListNode* pa = NULL;
ListNode* pb = NULL;
int la = 0;
int lb = 0;
int i = 0;
if((headA == NULL) || (headB == NULL))
{
return NULL;
}
for(pa = headA; pa != NULL; pa = pa->next)
{
la++;
}
for(pb = headB; pb != NULL; pb = pb->next)
{
lb++;
}
if(pa != pb)
{
return NULL;
}
pa = headA;
pb = headB;
if(la > lb)
{
for(i = 0; i < (la - lb); i++)
{
pa = pa->next;
}
}
else
{
for(i = 0; i < (lb - la); i++)
{
pb = pb->next;
}
}
while(pa != NULL)
{
if(pa == pb)
{
break;
}
pa = pa->next;
pb = pb->next;
}
return pa;
}
/*****************************************************************************
* 165:Compare Version Numbers
* Compare two version numbers version1 and version1.
* If version1 > version2 return 1, if version1 < version2 return -1,
* otherwise return 0.
*
* You may assume that the version strings are non-empty and contain only
* digits and the . character. The . character does not represent a decimal
* point and is used to separate number sequences. For instance, 2.5 is not
* "two and a half" or "half way to version three", it is the fifth
* second-level revision of the second first-level revision.
*
* Here is an example of version numbers ordering:
* 0.1 < 1.1 < 1.2 < 13.37
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/compare-version-numbers/
*
* Code:
* class Solution {
* public:
* int compareVersion(string version1, string version2) {
*
* }
* };
*
* Compile Error:
* Line 9: no match for ‘operator==’ (operand types are ‘std::string
* {aka std::basic_string<char>}’ and ‘long int’)
* Compile Error:
* Line 14: invalid conversion from ‘const char*’ to ‘char*’ [-fpermissive]
* Wrong Answer, Input: "1", "1.1" Output: 1 Expected: -1
****************************************************************************/
int leetcode_165_compare_version(char* version1, char* version2)
{
const char* p1 = NULL;
const char* p2 = NULL;
int v1 = 0;
int v2 = 0;
if((version1 == NULL) || (version2 == NULL))
{
return 0;
}
p1 = version1;
p2 = version2;
while((*p1 != '\0') || (*p2 != '\0'))
{
while((*p1 != '\0') && (*p1 != '.'))
{
v1 = v1 * 10 + (*p1 - '0');
p1++;
}
while((*p2 != '\0') && (*p2 != '.'))
{
v2 = v2 * 10 + (*p2 - '0');
p2++;
}
if(v1 < v2)
{
return -1;
}
else if(v1 > v2)
{
return 1;
}
else
{
v1 = 0;
v2 = 0;
if((*p1 == '\0') && (*p2 == '\0'))
{
return 0;
}
else if((*p1 == '\0') && (*p2 != '\0'))
{
p2++;
}
else if((*p1 != '\0') && (*p2 == '\0'))
{
p1++;
}
else
{
p1++;
p2++;
}
}
}
return 0;
}
/*****************************************************************************
* 168: Excel Sheet Column Title
* Given a positive integer, return its corresponding column title as appear
* in an Excel sheet.
* For example:
* 1 -> A
* 2 -> B
* 3 -> C
* ...
* 26 -> Z
* 27 -> AA
* 28 -> AB
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/excel-sheet-column-title/
*
* Code:
* class Solution {
* public:
* string convertToTitle(int n) {
* }
* };
****************************************************************************/
char* leetcode_168_convert_to_title(int n)
{
static char _168_title[128] = {0};
char temp = 0;
unsigned int i = 0;
unsigned int j = 0;
int m = 0;
if(n <= 0) return NULL;
while((n > 0) && (i < (sizeof(_168_title) - 1)))
{
m = (n - 1) % 26;
_168_title[i++] = 'A' + m;
n = (n - 1) / 26;
}
_168_title[i] = '\0';
while(j < i / 2)
{
temp = _168_title[j];
_168_title[j] = _168_title[i - j - 1];
_168_title[i - j - 1] = temp;
j++;
}
//return string(_168_title);
return _168_title;
}
/*****************************************************************************
* 169: Majority Element
* Given an array of size n, find the majority element. The majority element
* is the element that appears more than ⌊ n/2 ⌋ times.
* You may assume that the array is non-empty and the majority element always
* exist in the array.
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/majority-element/
*
* Code:
* class Solution {
* public:
* int majorityElement(vector<int> &num) {
* }
* };
****************************************************************************/
int leetcode_169_majority_element(int num[], int n)
{
int times = 0;
int candidate = 0;
int i = 0;
for(i = 0; i < n; i ++)
{
if(times == 0)
{
candidate = num[i];
times = 1;
}
else
{
if(candidate == num[i])
times++;
else
times--;
}
}
return candidate;
}
/*****************************************************************************
* 170:Two Sum III - Data structure design
* Design and implement a TwoSum class. It should support the following
* operations:add and find.
* add - Add the number to an internal data structure.
* find - Find if there exists any pair of numbers which sum is equal to the
* value.
* For example,add(1); add(3); add(5);
* find(4) -> true
* find(7) -> false
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/two-sum-iii-data-structure-design/
*
* Code:
* public class TwoSum {
* public void add(int number) {
* }
* public boolean find(int value) {
* }
* }
****************************************************************************/
TwoSum* leetcode_170_two_sum(void)
{
return TwoSumNew();
}
/*****************************************************************************
* 171:Excel Sheet Column Number
* Related to question Excel Sheet Column Title
* Given a column title as appear in an Excel sheet, return its corresponding
* column number.
* For example:
* A -> 1
* B -> 2
* C -> 3
* ...
* Z -> 26
* AA -> 27
* AB -> 28
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/excel-sheet-column-number/
*
* Code:
* class Solution {
* public:
* int titleToNumber(string s) {
* }
* };
****************************************************************************/
int leetcode_171_title_to_number(char* s)
{
int n = 0;
if(s == NULL) return 0;
if(*s == '\0') return 0;
while(*s != '\0')
{
if((*s >= 'A') && (*s <= 'Z'))
{
n = n * ('Z' - 'A' + 1) + (*s - 'A') + 1;
}
else
{
return 0;
}
s++;
}
return n;
}
/*****************************************************************************
* 172:Factorial Trailing Zeroes
* Given an integer n, return the number of trailing zeroes in n!.
* Note: Your solution should be in logarithmic time complexity.
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/factorial-trailing-zeroes/
*
* Code:
* class Solution {
* public:
* int trailingZeroes(int n) {
* }
* };
*
* 解法:
* 以下列出0至20的阶乘
* 0=1注意(0的阶乘是存在的)
* 1=1
* 2=2
* 3=6
* 4=24
* 5=120
* 6=720
* 7=5,040
* 8=40,320
* 9=362,880
* 10=3,628,800
* 11=39,916,800
* 12=479,001,600
* 13=6,227,020,800
* 14=87,178,291,200
* 15=1,307,674,368,000
* 16=20,922,789,888,000
* 17=355,687,428,096,000
* 18=6,402,373,705,728,000
* 19=121,645,100,408,832,000
* 20=2,432,902,008,176,640,000
* 另外数学家定义0=1所以0=1
* 而当n≥5时n的个位数字都是0.
****************************************************************************/
int leetcode_172_trailing_zeroes(int n)
{
int zeroes = 0;
if(n < 5) return 0;
while(n >= 5)
{
n = n / 5;
zeroes += n;
}
return zeroes;
}
/*****************************************************************************
* 179:Largest Number
* Given a list of non negative integers, arrange them such that they form
* the largest number.
* For example, given [3, 30, 34, 5, 9], the largest formed number is 9534330.
* Note: The result may be very large, so you need to return a string instead
* of an integer.
*
* Difficulty: Easy
*
* Link: https://oj.leetcode.com/problems/largest-number/
*
* Code:
* class Solution {
* public:
* string largestNumber(vector<int> &num) {
* }
* };
*
* 解法:
* 数字等长, 则大的在前. 如 9,5 则9先输出,46,48则48先.
* 数字不等长,则按短的比较,如果不等则大的在前.如果相等,则比较长的下一个数与短的高位数,
* 如果相等取长的,否则取大的在前.
****************************************************************************/
char* leetcode_179_largest_number(int* num, int size)
{
static char _179_number[512] = {0};
char* p = _179_number;
int i = 0;
int max = 0;
int max_len = 0;
int cur_len = 0;
int n = size;
int digit = 0;
int value = 0;
int len = 0;
memset(_179_number, 0, sizeof(_179_number));
if((num == NULL) || (size <= 0)) return _179_number;
p[0] = '0';
for(i = 0; i < size && num[i] == 0; i++);
if(i >= size) return _179_number;
while(n > 0)
{
for(i = 0; i < size && num[i] == -1; i++);
max = i;
for(i = max + 1;i < size; i++)
{
if(num[i] == -1) continue;
for(max_len = 0, value = num[max];
value != 0;
value = value / 10, max_len++);
for(cur_len = 0, value = num[i];
value != 0;
value = value / 10, cur_len++);
if(max_len > cur_len)
{
for(value = num[max], len = max_len - cur_len;
len > 0;
len--, value = value / 10);
if(value < num[i])
{
max = i;
}
else if(value == num[i])
{
for(value = num[max], len = max_len - cur_len;
len > 0;
len--, digit = value % 10, value = value / 10);
if((num[i] < 10) && (num[i] >= digit))
{
max = i;
}
else if(num[i] / 10 > digit)
{
max = i;
}
}
}
else if(max_len < cur_len)
{
for(value = num[i], len = cur_len - max_len;
len > 0;
len--, value = value / 10);
if(value > num[max])
{
max = i;
}
else if(value == num[max])
{
for(value = num[i], len = cur_len - max_len;
len > 0;
len--, digit = value % 10, value = value / 10);
if((num[max] < 10) && (num[max] <= digit))
{
max = i;
}
else if(num[max] / 10 < digit)
{
max = i;
}
}
}
else
{
if(num[max] < num[i])
{
max = i;
}
}
}
p += sprintf(p, "%d", num[max]);
num[max] = -1;
n--;
}
return _179_number;
}
/*****************************************************************************
* 以下是测试用例.
****************************************************************************/
static void _002_add_two_numbers(void)
{
ListNode* l1 = NULL;
ListNode* l2 = NULL;
ListNode* l3 = NULL;
ListNode* p = NULL;
/*************************************************************************
* 5 + 5 = 10
************************************************************************/
l1 = ListAppend(l1, 5);
l2 = ListAppend(l2, 5);
l3 = addTwoNumbers(l1, l2);
CU_ASSERT_EQUAL(l3->val, 0);
CU_ASSERT_EQUAL(l3->next->val, 1);
l1 = ListDestroy(l1);
l2 = ListDestroy(l2);
l3 = ListDestroy(l3);
/*************************************************************************
* 243 + 564 = 807
************************************************************************/
l1 = ListAppend(l1, 2);
l1 = ListAppend(l1, 4);
l1 = ListAppend(l1, 3);
l2 = ListAppend(l2, 5);
l2 = ListAppend(l2, 6);
l2 = ListAppend(l2, 4);
l3 = addTwoNumbers(l1, l2);
CU_ASSERT_EQUAL(ListLength(l3), 3); p = l3;
CU_ASSERT_EQUAL(p->val, 7); p = p->next;
CU_ASSERT_EQUAL(p->val, 0); p = p->next;
CU_ASSERT_EQUAL(p->val, 8); p = p->next;
l1 = ListDestroy(l1);
l2 = ListDestroy(l2);
l3 = ListDestroy(l3);
/*************************************************************************
* 2 + 3 = 5
************************************************************************/
l1 = ListAppend(l1, 2);
l2 = ListAppend(l2, 3);
l3 = addTwoNumbers(l1, l2);
CU_ASSERT_EQUAL(l3->val, 5);
l1 = ListDestroy(l1);
l2 = ListDestroy(l2);
l3 = ListDestroy(l3);
/*************************************************************************
* 2 + 8 = 10
************************************************************************/
l1 = ListAppend(l1, 2);
l2 = ListAppend(l2, 8);
l3 = addTwoNumbers(l1, l2);
CU_ASSERT_EQUAL(ListLength(l3), 2);
CU_ASSERT_EQUAL(l3->val, 0);
CU_ASSERT_EQUAL(l3->next->val, 1);
l1 = ListDestroy(l1);
l2 = ListDestroy(l2);
l3 = ListDestroy(l3);
/*************************************************************************
* 5 + 5
************************************************************************/
l1 = ListAppend(l1, 5);
l2 = ListAppend(l2, 5);
l3 = addTwoNumbers(l1, l2);
CU_ASSERT_EQUAL(ListLength(l3), 2);
CU_ASSERT_EQUAL(l3->val, 0);
CU_ASSERT_EQUAL(l3->next->val, 1);
l1 = ListDestroy(l1);
l2 = ListDestroy(l2);
l3 = ListDestroy(l3);
/*************************************************************************
* 18 + 0
************************************************************************/
l1 = ListAppend(l1, 1);
l1 = ListAppend(l1, 8);
l2 = ListAppend(l2, 0);
l3 = addTwoNumbers(l1, l2);
CU_ASSERT_EQUAL(ListLength(l3), 2);
CU_ASSERT_EQUAL(l3->val, 1);
CU_ASSERT_EQUAL(l3->next->val, 8);
l1 = ListDestroy(l1);
l2 = ListDestroy(l2);
l3 = ListDestroy(l3);
/*************************************************************************
* 1 + 99
************************************************************************/
l1 = ListAppend(l1, 1);
l2 = ListAppend(l2, 9);
l2 = ListAppend(l2, 9);
l3 = addTwoNumbers(l1, l2);
CU_ASSERT_EQUAL(ListLength(l3), 3);
CU_ASSERT_EQUAL(l3->val, 0);
CU_ASSERT_EQUAL(l3->next->val, 0);
CU_ASSERT_EQUAL(l3->next->next->val, 1);
l1 = ListDestroy(l1);
l2 = ListDestroy(l2);
l3 = ListDestroy(l3);
/*************************************************************************
* 2 + 344 = 346
************************************************************************/
l1 = ListAppend(l1, 2);
l2 = ListAppend(l2, 3);
l2 = ListAppend(l2, 4);
l2 = ListAppend(l2, 4);
l3 = addTwoNumbers(l1, l2);
CU_ASSERT_EQUAL(ListLength(l3), 3);
CU_ASSERT_EQUAL(l3->val, 5);
CU_ASSERT_EQUAL(l3->next->val, 4);
CU_ASSERT_EQUAL(l3->next->next->val, 4);
l1 = ListDestroy(l1);
l2 = ListDestroy(l2);
l3 = ListDestroy(l3);
/*************************************************************************
* 344 + 2 = 346
************************************************************************/
l1 = ListAppend(l1, 2);
l2 = ListAppend(l2, 3);
l2 = ListAppend(l2, 4);
l2 = ListAppend(l2, 4);
l3 = addTwoNumbers(l2, l1);
CU_ASSERT_EQUAL(ListLength(l3), 3);
CU_ASSERT_EQUAL(l3->val, 5);
CU_ASSERT_EQUAL(l3->next->val, 4);
CU_ASSERT_EQUAL(l3->next->next->val, 4);
l1 = ListDestroy(l1);
l2 = ListDestroy(l2);
l3 = ListDestroy(l3);
/*************************************************************************
* 1 + 299999 = 300000
************************************************************************/
l1 = ListAppend(l1, 1);
l2 = ListAppend(l2, 2);
l2 = ListAppend(l2, 9);
l2 = ListAppend(l2, 9);
l2 = ListAppend(l2, 9);
l2 = ListAppend(l2, 9);
l2 = ListAppend(l2, 9);
l3 = addTwoNumbers(l2, l1);
CU_ASSERT_EQUAL(ListLength(l3), 6); p = l3;
CU_ASSERT_EQUAL(p->val, 3); p = p->next;
CU_ASSERT_EQUAL(p->val, 9); p = p->next;
CU_ASSERT_EQUAL(p->val, 9); p = p->next;
CU_ASSERT_EQUAL(p->val, 9); p = p->next;
CU_ASSERT_EQUAL(p->val, 9); p = p->next;
CU_ASSERT_EQUAL(p->val, 9); p = p->next;
l1 = ListDestroy(l1);
l2 = ListDestroy(l2);
l3 = ListDestroy(l3);
}
static void _006_convert(void)
{
CU_ASSERT_EQUAL(strcmp(convert("PAYPALISHIRING", 3), "PAHNAPLSIIGYIR"), 0);
}
static void _007_reverse(void)
{
CU_ASSERT_EQUAL(reverse(0), 0);
CU_ASSERT_EQUAL(reverse(123), 321);
CU_ASSERT_EQUAL(reverse(-321), -123);
CU_ASSERT_EQUAL(reverse(1534236469), 0);
}
static void _008_atoi(void)
{
CU_ASSERT_EQUAL(myAtoi(NULL), 0);
CU_ASSERT_EQUAL(myAtoi(""), 0);
CU_ASSERT_EQUAL(myAtoi("1234"), 1234);
CU_ASSERT_EQUAL(myAtoi("-12"), -12);
CU_ASSERT_EQUAL(myAtoi("+2"), 2);
CU_ASSERT_EQUAL(myAtoi(" adf sdf -12"), 0);
CU_ASSERT_EQUAL(myAtoi(" adf -sdf 12"), 0);
CU_ASSERT_EQUAL(myAtoi("-"), 0);
CU_ASSERT_EQUAL(myAtoi(" adf 123sddf123"), 0);
CU_ASSERT_EQUAL(myAtoi(" adf -1sddf123"), 0);
CU_ASSERT_EQUAL(myAtoi("2147483648"), INT_MAX);
CU_ASSERT_EQUAL(myAtoi("-2147483649"), INT_MIN);
CU_ASSERT_EQUAL(myAtoi("3122147483649"), INT_MAX);
CU_ASSERT_EQUAL(myAtoi("-3147483649"), INT_MIN);
CU_ASSERT_EQUAL(myAtoi("+-2"), 0);
}
static void _009_is_palindrome(void)
{
CU_ASSERT_EQUAL(isPalindrome(121), true);
CU_ASSERT_EQUAL(isPalindrome(231), false);
CU_ASSERT_EQUAL(isPalindrome(98789), true);
CU_ASSERT_EQUAL(isPalindrome(-2147447412), false);
}
static void _013_roman_to_int(void)
{
CU_ASSERT_EQUAL(romanToInt(NULL), 0);
CU_ASSERT_EQUAL(romanToInt(""), 0);
CU_ASSERT_EQUAL(romanToInt("I"), 1);
CU_ASSERT_EQUAL(romanToInt("II"), 2);
CU_ASSERT_EQUAL(romanToInt("III"), 3);
CU_ASSERT_EQUAL(romanToInt("IV"), 4);
CU_ASSERT_EQUAL(romanToInt("V"), 5);
CU_ASSERT_EQUAL(romanToInt("VI"), 6);
CU_ASSERT_EQUAL(romanToInt("VII"), 7);
CU_ASSERT_EQUAL(romanToInt("VIII"), 8);
CU_ASSERT_EQUAL(romanToInt("IX"), 9);
CU_ASSERT_EQUAL(romanToInt("X"), 10);
CU_ASSERT_EQUAL(romanToInt("XI"), 11);
CU_ASSERT_EQUAL(romanToInt("XII"), 12);
CU_ASSERT_EQUAL(romanToInt("XIII"), 13);
CU_ASSERT_EQUAL(romanToInt("XIV"), 14);
CU_ASSERT_EQUAL(romanToInt("XV"), 15);
CU_ASSERT_EQUAL(romanToInt("XVI"), 16);
CU_ASSERT_EQUAL(romanToInt("XVII"), 17);
CU_ASSERT_EQUAL(romanToInt("XVIII"), 18);
CU_ASSERT_EQUAL(romanToInt("XIX"), 19);
CU_ASSERT_EQUAL(romanToInt("XX"), 20);
CU_ASSERT_EQUAL(romanToInt("XXI"), 21);
CU_ASSERT_EQUAL(romanToInt("XXII"), 22);
CU_ASSERT_EQUAL(romanToInt("XXIX"), 29);
CU_ASSERT_EQUAL(romanToInt("XXX"), 30);
CU_ASSERT_EQUAL(romanToInt("XXXIV"), 34);
CU_ASSERT_EQUAL(romanToInt("XXXV"), 35);
CU_ASSERT_EQUAL(romanToInt("XXXIX"), 39);
CU_ASSERT_EQUAL(romanToInt("XL"), 40);
CU_ASSERT_EQUAL(romanToInt("L"), 50);
CU_ASSERT_EQUAL(romanToInt("LX"), 60);
CU_ASSERT_EQUAL(romanToInt("LXV"), 65);
CU_ASSERT_EQUAL(romanToInt("LXXX"), 80);
CU_ASSERT_EQUAL(romanToInt("XC"), 90);
CU_ASSERT_EQUAL(romanToInt("XCIII"), 93);
CU_ASSERT_EQUAL(romanToInt("XCV"), 95);
CU_ASSERT_EQUAL(romanToInt("XCVIII"), 98);
CU_ASSERT_EQUAL(romanToInt("XCIX"), 99);
CU_ASSERT_EQUAL(romanToInt("C"), 100);
CU_ASSERT_EQUAL(romanToInt("CC"), 200);
CU_ASSERT_EQUAL(romanToInt("CCC"), 300);
CU_ASSERT_EQUAL(romanToInt("CD"), 400);
CU_ASSERT_EQUAL(romanToInt("D"), 500);
CU_ASSERT_EQUAL(romanToInt("DC"), 600);
CU_ASSERT_EQUAL(romanToInt("DCC"), 700);
CU_ASSERT_EQUAL(romanToInt("DCCC"), 800);
CU_ASSERT_EQUAL(romanToInt("CM"), 900);
CU_ASSERT_EQUAL(romanToInt("CMXCIX"), 999);
CU_ASSERT_EQUAL(romanToInt("M"), 1000);
CU_ASSERT_EQUAL(romanToInt("MC"), 1100);
CU_ASSERT_EQUAL(romanToInt("MCD"), 1400);
CU_ASSERT_EQUAL(romanToInt("MD"), 1500);
CU_ASSERT_EQUAL(romanToInt("MDC"), 1600);
CU_ASSERT_EQUAL(romanToInt("MDCLXVI"), 1666);
CU_ASSERT_EQUAL(romanToInt("MDCCCLXXXVIII"), 1888);
CU_ASSERT_EQUAL(romanToInt("MDCCCXCIX"), 1899);
CU_ASSERT_EQUAL(romanToInt("MCM"), 1900);
CU_ASSERT_EQUAL(romanToInt("MCMLXXVI"), 1976);
CU_ASSERT_EQUAL(romanToInt("MCMLXXXIV"), 1984);
CU_ASSERT_EQUAL(romanToInt("MCMXC"), 1990);
CU_ASSERT_EQUAL(romanToInt("MM"), 2000);
CU_ASSERT_EQUAL(romanToInt("MMMCMXCIX"), 3999);
}
static void _014_longest_common_prefix(void)
{
char* A[] = {"ab", "ab1", "ab2"};
char* B[] = {"abc", "abdefsd", "ab"};
char* C[] = {"abesdfsasdf", "abesxxxxysdfs", "abes1"};
char* D[] = {"asdfes", "bdefes", "cdfeasd"};
char* E[] = {"aa","a"};
CU_ASSERT_EQUAL(strcmp(longestCommonPrefix(A, ARRAY_NUM(A)), "ab"), 0);
CU_ASSERT_EQUAL(strcmp(longestCommonPrefix(B, ARRAY_NUM(B)), "ab"), 0);
CU_ASSERT_EQUAL(strcmp(longestCommonPrefix(C, ARRAY_NUM(C)), "abes"), 0);
CU_ASSERT_EQUAL(strcmp(longestCommonPrefix(D, ARRAY_NUM(D)), ""), 0);
CU_ASSERT_EQUAL(strcmp(longestCommonPrefix(E, ARRAY_NUM(E)), "a"), 0);
}
static void _019_remove_nth_node_from_end(void)
{
ListNode* list = NULL;
int index = 0;
/*************************************************************************
* 删除倒数第二个节点
************************************************************************/
for(index = 1; index <= 5; index++)
{
list = ListAppend(list, index);
}
list = removeNthFromEnd(list, 2);
CU_ASSERT_EQUAL(ListLength(list), 4);
CU_ASSERT_EQUAL(list = ListDestroy(list), NULL);
/*************************************************************************
* 删除倒数第一个节点,并且只有一个节点.
************************************************************************/
list = ListAppend(list, 1);
list = removeNthFromEnd(list, 1);
CU_ASSERT_EQUAL(ListLength(list), 0);
CU_ASSERT_PTR_EQUAL(list = ListDestroy(list), NULL);
/*************************************************************************
* 删除多个节点中倒数第一个节点.
************************************************************************/
for(index = 1; index < 6; index++)
{
list = ListAppend(list, index);
}
CU_ASSERT_EQUAL(ListLength(list), 5);
list = removeNthFromEnd(list, 1);
CU_ASSERT_EQUAL(ListLength(list), 4);
CU_ASSERT_PTR_EQUAL(list = ListDestroy(list), NULL);
/*************************************************************************
* 删除只有两个节点中的倒数第二个节点,也就是头节点.
************************************************************************/
for(index = 1; index <= 2; index++)
{
list = ListAppend(list, index);
}
list = removeNthFromEnd(list, 2);
CU_ASSERT_EQUAL(ListLength(list), 1);
CU_ASSERT_EQUAL(list->val, 2);
}
static void _020_is_valid(void)
{
CU_ASSERT_EQUAL(isValid(NULL), false);
CU_ASSERT_EQUAL(isValid(""), false);
CU_ASSERT_EQUAL(isValid("]"), false);
CU_ASSERT_EQUAL(isValid("}"), false);
CU_ASSERT_EQUAL(isValid(")"), false);
CU_ASSERT_EQUAL(isValid("[]"), true);
CU_ASSERT_EQUAL(isValid("[)"), false);
CU_ASSERT_EQUAL(isValid("(){}[]"), true);
CU_ASSERT_EQUAL(isValid("((}}"), false);
CU_ASSERT_EQUAL(isValid("(({}))[[()]]"), true);
}
static void _021_merge_two_sorted_lists(void)
{
ListNode* l1 = NULL;
ListNode* l2 = NULL;
ListNode* l3 = NULL;
ListNode* p = NULL;
int i = 0;
for(i = 1; i <= 9; i += 2)
{
l1 = ListAppend(l1, i);
}
for(i = 2; i <= 10; i += 2)
{
l2 = ListAppend(l2, i);
}
l3 = mergeTwoLists(l1, l2);
p = l3;
for(i = 1; (i <= 10) && (p != NULL); i++)
{
CU_ASSERT_EQUAL(p->val, i);
p = p->next;
}
l3 = ListDestroy(l3);
}
static void _024_swap_pairs(void)
{
ListNode* l = NULL;
ListNode* p = NULL;
int i = 0;
int a[] = {2, 1, 4, 3};
/*************************************************************************
* 标准测试,偶数个节点.
************************************************************************/
for(i = 1; i < 5; i++)
{
l = ListAppend(l, i);
}
CU_ASSERT_PTR_NOT_NULL(l = swapPairs(l));
CU_ASSERT_EQUAL(ListLength(l), 4);
for(p = l, i = 0; p != NULL; p = p->next, i++)
{
CU_ASSERT_EQUAL(a[i], p->val);
}
l = ListDestroy(l);
/*************************************************************************
* 一个节点的情况.
************************************************************************/
l = ListAppend(l, 1);
CU_ASSERT_PTR_NOT_NULL(l = swapPairs(l));
CU_ASSERT_EQUAL(ListLength(l), 1);
CU_ASSERT_EQUAL(l->val, 1);
l = ListDestroy(l);
/*************************************************************************
* 大于2的奇数个节点.
************************************************************************/
for(i = 1; i <=7; i++)
{
l = ListAppend(l, i);
}
CU_ASSERT_PTR_NOT_NULL(l = swapPairs(l));
CU_ASSERT_EQUAL(ListLength(l), 7);
for(p = l; p->next != NULL; p = p->next);
CU_ASSERT_EQUAL(p->val, 7);
l = ListDestroy(l);
}
static void _026_remove_duplicates(void)
{
int A1[] = {1, 1, 2};
int B1[] = {1, 2};
int A2[] = {1};
int B2[] = {1};
int length = -1;
size_t i = 0;
length = removeDuplicates(A1, sizeof(A1) / sizeof(A1[0]));
CU_ASSERT_EQUAL(length, 2);
for(i = 0; i < sizeof(B1) / sizeof(B1[0]); i++)
{
CU_ASSERT_EQUAL(B1[i], A1[i]);
}
length = removeDuplicates(A2, 1);
CU_ASSERT_EQUAL(length, 1);
CU_ASSERT_EQUAL(A2[0], B2[0]);
}
static void _027_remove_element(void)
{
int A1[] = {3, 3};
int length = -1;
length = removeElement(A1, 2, 3);
CU_ASSERT_EQUAL(length, 0);
}
static void _028_implement_strstr(void)
{
CU_ASSERT_EQUAL(strStr(NULL, NULL), -1);
CU_ASSERT_EQUAL(strStr("", ""), 0);
CU_ASSERT_EQUAL(strStr("a", ""), 0);
CU_ASSERT_EQUAL(strStr("", "a"), -1);
CU_ASSERT_EQUAL(strStr("abcabc", "abc"), 0);
CU_ASSERT_EQUAL(strStr("xyxxssdfa", "abcd"), -1);
CU_ASSERT_EQUAL(strStr("xyyyyabcddd", "abc"), 5);
CU_ASSERT_EQUAL(strStr("xabeds", "abc"), -1);
CU_ASSERT_EQUAL(strStr("mississippi", "issip"), 4);
CU_ASSERT_EQUAL(strStr("mississippi", "pi"), 9);
}
static void _036_is_valid_sudoku(void)
{
char* a1[9]=
{
(char*)".21......",
(char*)"....6....",
(char*)"......7..",
(char*)"....5....",
(char*)"..5......",
(char*)"......3..",
(char*)".........",
(char*)"3...8.1..",
(char*)"........8"
};
char* a2[9] =
{
(char*)".87654321",
(char*)"2........",
(char*)"3........",
(char*)"4........",
(char*)"5........",
(char*)"6........",
(char*)"7........",
(char*)"8........",
(char*)"9........"
};
char* a3[9] =
{
"......5..",
".........",
"........3",
".2.7.....",
"8365....1",
".....1...",
"2.......5",
"........7",
"...4...7."
};
CU_ASSERT_EQUAL(isValidSudoku(NULL, 0, 0), false);
CU_ASSERT_EQUAL(isValidSudoku(a1, 9, 9), true);
CU_ASSERT_EQUAL(isValidSudoku(a2, 9, 9), true);
CU_ASSERT_EQUAL(isValidSudoku(a3, 9, 9), false);
}
static void _038_count_and_say(void)
{
CU_ASSERT_EQUAL(strcmp(countAndSay(1), "1"), 0);
CU_ASSERT_EQUAL(strcmp(countAndSay(2), "11"), 0);
CU_ASSERT_EQUAL(strcmp(countAndSay(3), "21"), 0);
CU_ASSERT_EQUAL(strcmp(countAndSay(4), "1211"), 0);
CU_ASSERT_EQUAL(strcmp(countAndSay(5), "111221"), 0);
CU_ASSERT_EQUAL(strcmp(countAndSay(20), "11131221131211132221232112111312111213111213211231132132211211131221131211221321123113213221123113112221131112311332211211131221131211132211121312211231131112311211232221121321132132211331121321231231121113112221121321133112132112312321123113112221121113122113121113123112112322111213211322211312113211"), 0);
}
static void _058_length_of_last_word(void)
{
CU_ASSERT_EQUAL(lengthOfLastWord(NULL), 0);
CU_ASSERT_EQUAL(lengthOfLastWord("avsdfe"), 6);
CU_ASSERT_EQUAL(lengthOfLastWord("avsdfe "), 6);
CU_ASSERT_EQUAL(lengthOfLastWord("avsdfe 1 "), 1);
CU_ASSERT_EQUAL(lengthOfLastWord(" aaa "), 3);
CU_ASSERT_EQUAL(lengthOfLastWord("a"), 1);
}
static void _061_rotate_right(void)
{
ListNode* list = NULL;
list = ListAppend(list, 1);
list = ListAppend(list, 2);
list = ListAppend(list, 3);
list = ListAppend(list, 4);
list = ListAppend(list, 5);
list = rotateRight(list, 2);
CU_ASSERT_EQUAL(ListLength(list), 5);
CU_ASSERT_EQUAL(list->val, 4);
CU_ASSERT_EQUAL(list->next->val, 5);
list = ListDestroy(list);
list = ListAppend(list, 1);
list = rotateRight(list, 1);
CU_ASSERT_EQUAL(ListLength(list), 1);
CU_ASSERT_EQUAL(list->val, 1);
list = ListDestroy(list);
list = ListAppend(list, 1);
list = ListAppend(list, 2);
list = rotateRight(list, 3);
CU_ASSERT_EQUAL(ListLength(list), 2);
CU_ASSERT_EQUAL(list->val, 2);
CU_ASSERT_EQUAL(list->next->val, 1);
list = ListDestroy(list);
list = ListAppend(list, 1);
list = rotateRight(list, 99);
CU_ASSERT_EQUAL(ListLength(list), 1);
CU_ASSERT_EQUAL(list->val, 1);
list = ListDestroy(list);
list = ListAppend(list, 1);
list = ListAppend(list, 2);
list = ListAppend(list, 3);
list = ListAppend(list, 4);
list = ListAppend(list, 5);
list = rotateRight(list, 5);
CU_ASSERT_EQUAL(ListLength(list), 5);
CU_ASSERT_EQUAL(list->val, 1);
CU_ASSERT_EQUAL(list->next->val, 2);
list = ListDestroy(list);
}
static void _066_plus_one(void)
{
int a1[] = {6, 2, 7, 9};
int a2[] = {9, 9, 0};
int size = 0;
int* b = 0;
/*************************************************************************
* 6279 + 1 = 6280
************************************************************************/
CU_ASSERT_PTR_NOT_NULL(b = plusOne(a1, 4, &size));
CU_ASSERT_EQUAL(size, 4);
CU_ASSERT_EQUAL(b[0], 6);
CU_ASSERT_EQUAL(b[1], 2);
CU_ASSERT_EQUAL(b[2], 8);
CU_ASSERT_EQUAL(b[3], 0);
/*************************************************************************
* 99 + 1 = 100
************************************************************************/
CU_ASSERT_PTR_NOT_NULL(b = plusOne(a2, 2, &size));
CU_ASSERT_EQUAL(size, 3);
CU_ASSERT_EQUAL(b[0], 1);
CU_ASSERT_EQUAL(b[1], 0);
CU_ASSERT_EQUAL(b[2], 0);
}
static void _067_add_binary(void)
{
CU_ASSERT_EQUAL(addBinary(NULL, NULL), NULL);
CU_ASSERT_EQUAL(strcmp(addBinary("11", NULL), "11"), 0);
CU_ASSERT_EQUAL(strcmp(addBinary(NULL, "11"), "11"), 0);
CU_ASSERT_EQUAL(strcmp(addBinary("11", "1"), "100"), 0);
CU_ASSERT_EQUAL(strcmp(addBinary("1", "111"), "1000"), 0);
CU_ASSERT_EQUAL(strcmp(addBinary("1010", "1011"), "10101"), 0);
}
static void _070_climb_stairs(void)
{
CU_ASSERT_EQUAL(climbStairs(1), 1);
CU_ASSERT_EQUAL(climbStairs(2), 2);
CU_ASSERT_EQUAL(climbStairs(3), 3);
}
static void _078_subsets(void)
{
int A[] = {1, 2, 3};
int B[] = {4, 1, 0};
int** result = NULL;
int* column = NULL;
int size = 0;
char resstr[256] = {0};
char* buf = NULL;
int i = 0;
int j = 0;
CU_ASSERT_PTR_NOT_NULL(result = subsets(A, ARRAY_NUM(A), &column, &size));
CU_ASSERT_EQUAL(size, 1 << ARRAY_NUM(A));
free(column);
free(result);
CU_ASSERT_PTR_NOT_NULL(result = subsets(B, ARRAY_NUM(B), &column, &size));
CU_ASSERT_EQUAL(size, 1 << ARRAY_NUM(B));
buf = resstr;
buf += sprintf(buf, "[");
for(i = 0; i < size; i++)
{
buf += sprintf(buf, "[");
for(j = 0; j < column[i]; j++)
{
buf += sprintf(buf, "%d", result[i][j]);
if((j < column[i]) && (j != column[i] - 1))
{
buf += sprintf(buf, ",");
}
}
buf += sprintf(buf, "]");
if(i != (size - 1))
{
buf += sprintf(buf, ",");
}
}
buf += sprintf(buf, "]");
CU_ASSERT_EQUAL(
strcmp(resstr, "[[],[4],[1],[1,4],[0],[0,4],[0,1],[0,1,4]]"), 0);
free(column);
free(result);
}
static void _082_delete_duplicates_ii(void)
{
ListNode* list = NULL;
ListNode* p = NULL;
int i = 0;
/*************************************************************************
* Input:1->2->2->2->3->4->4->4->5->6->6 Output:1->3->5
************************************************************************/
list = ListAppend(list, 1);
list = ListAppend(list, 2);
list = ListAppend(list, 2);
list = ListAppend(list, 2);
list = ListAppend(list, 3);
list = ListAppend(list, 4);
list = ListAppend(list, 4);
list = ListAppend(list, 4);
list = ListAppend(list, 5);
list = ListAppend(list, 6);
list = ListAppend(list, 6);
list = deleteDuplicatesII(list);
CU_ASSERT_EQUAL(ListLength(list), 3);
for(i = 1, p = list; (i <= 5) && (p != NULL); i += 2, p = p->next)
{
CU_ASSERT_EQUAL(p->val, i);
}
list = ListDestroy(list);
/*************************************************************************
* Input:1->1->1->1 Output:Empty
************************************************************************/
list = ListAppend(list, 1);
list = ListAppend(list, 1);
list = ListAppend(list, 1);
list = ListAppend(list, 1);
list = deleteDuplicatesII(list);
CU_ASSERT_EQUAL(ListLength(list), 0);
list = ListDestroy(list);
/*************************************************************************
* Input:1->1->1->2->3->6->6 Output:2->3
************************************************************************/
list = ListAppend(list, 1);
list = ListAppend(list, 1);
list = ListAppend(list, 1);
list = ListAppend(list, 2);
list = ListAppend(list, 3);
list = ListAppend(list, 6);
list = ListAppend(list, 6);
list = deleteDuplicatesII(list);
CU_ASSERT_EQUAL(ListLength(list), 2);
CU_ASSERT_EQUAL(list->val, 2);
CU_ASSERT_EQUAL(list->next->val, 3);
list = ListDestroy(list);
/*************************************************************************
* Input:1 Output:1
************************************************************************/
list = ListAppend(list, 1);
list = deleteDuplicatesII(list);
CU_ASSERT_EQUAL(ListLength(list), 1);
CU_ASSERT_EQUAL(list->val, 1);
list = ListDestroy(list);
/*************************************************************************
* Input:1->2->3->4 Output:1->2->3->4
************************************************************************/
list = ListAppend(list, 1);
list = ListAppend(list, 2);
list = ListAppend(list, 3);
list = ListAppend(list, 4);
list = deleteDuplicatesII(list);
CU_ASSERT_EQUAL(ListLength(list), 4);
list = ListDestroy(list);
}
static void _083_delete_duplicates(void)
{
ListNode* list = NULL;
ListNode* p = NULL;
int i = 0;
/*************************************************************************
* Input:1->2->2->2->3->4->4->4->5->6->6 Output:1->2->3->4->5->6
************************************************************************/
list = ListAppend(list, 1);
list = ListAppend(list, 2);
list = ListAppend(list, 2);
list = ListAppend(list, 2);
list = ListAppend(list, 3);
list = ListAppend(list, 4);
list = ListAppend(list, 4);
list = ListAppend(list, 4);
list = ListAppend(list, 5);
list = ListAppend(list, 6);
list = ListAppend(list, 6);
list = deleteDuplicates(list);
CU_ASSERT_EQUAL(ListLength(list), 6);
for(i = 1, p = list; (i <= 6) && (p != NULL); i += 1, p = p->next)
{
CU_ASSERT_EQUAL(p->val, i);
}
list = ListDestroy(list);
/*************************************************************************
* Input:1->1->1->1 Output:1
************************************************************************/
list = ListAppend(list, 1);
list = ListAppend(list, 1);
list = ListAppend(list, 1);
list = ListAppend(list, 1);
list = deleteDuplicates(list);
CU_ASSERT_EQUAL(ListLength(list), 1);
CU_ASSERT_EQUAL(list->val, 1);
list = ListDestroy(list);
/*************************************************************************
* Input:1->1->1->2->3->6->6 Output:1->2->3->6
************************************************************************/
list = ListAppend(list, 1);
list = ListAppend(list, 1);
list = ListAppend(list, 1);
list = ListAppend(list, 2);
list = ListAppend(list, 3);
list = ListAppend(list, 6);
list = ListAppend(list, 6);
list = deleteDuplicates(list);
CU_ASSERT_EQUAL(ListLength(list), 4);
CU_ASSERT_EQUAL(list->val, 1);
CU_ASSERT_EQUAL(list->next->val, 2);
list = ListDestroy(list);
/*************************************************************************
* Input:1 Output:1
************************************************************************/
list = ListAppend(list, 1);
list = deleteDuplicates(list);
CU_ASSERT_EQUAL(ListLength(list), 1);
CU_ASSERT_EQUAL(list->val, 1);
list = ListDestroy(list);
/*************************************************************************
* Input:1->2->3->4 Output:1->2->3->4
************************************************************************/
list = ListAppend(list, 1);
list = ListAppend(list, 2);
list = ListAppend(list, 3);
list = ListAppend(list, 4);
list = deleteDuplicates(list);
CU_ASSERT_EQUAL(ListLength(list), 4);
list = ListDestroy(list);
}
static void _086_partition_list(void)
{
ListNode* list = NULL;
ListNode* p = NULL;
size_t i = 0;
int a1[] = {1, 4, 3, 2, 5, 2};
int b1[] = {1, 2, 2, 4, 3, 5};
int a2[] = {4, 1, 3, 2, 5, 2};
int b2[] = {1, 2, 2, 4, 3, 5};
/*************************************************************************
* Input:1->4->3->2->5->2 Output:1->2->2->4->3->5
************************************************************************/
for(i = 0; i < ARRAY_NUM(a1); i++)
{
list = ListAppend(list, a1[i]);
}
list = partition(list, 3);
CU_ASSERT_EQUAL(ListLength(list), ARRAY_NUM(a1));
for(i = 0, p = list; i < ARRAY_NUM(b1); i++, p = p->next)
{
CU_ASSERT_EQUAL(p->val, b1[i]);
}
list = ListDestroy(list);
/*************************************************************************
* Input: 4->1->3->2->5->2 3 Output:1->2->4->3->5
************************************************************************/
for(i = 0; i < ARRAY_NUM(a2); i++)
{
list = ListAppend(list, a2[i]);
}
list = partition(list, 3);
CU_ASSERT_EQUAL(ListLength(list), ARRAY_NUM(a2));
for(i = 0, p = list; i < ARRAY_NUM(b2); i++, p = p->next)
{
CU_ASSERT_EQUAL(p->val, b2[i]);
}
list = ListDestroy(list);
/*************************************************************************
* Input: 4->1->3->2->5->2 1 Output:4->1->3->2->5->2
************************************************************************/
for(i = 0; i < ARRAY_NUM(a2); i++)
{
list = ListAppend(list, a2[i]);
}
list = partition(list, 1);
CU_ASSERT_EQUAL(ListLength(list), ARRAY_NUM(a2));
for(i = 0, p = list; i < ARRAY_NUM(b2); i++, p = p->next)
{
CU_ASSERT_EQUAL(p->val, a2[i]);
}
list = ListDestroy(list);
/*************************************************************************
* Input: {1}, 2 Output: {1}
************************************************************************/
list = ListAppend(list, 1);
list = partition(list, 2);
CU_ASSERT_EQUAL(ListLength(list), 1);
CU_ASSERT_EQUAL(list->val, 1);
list = ListDestroy(list);
/*************************************************************************
* Input: {3,1,2},3 Output:{1,2,3}
************************************************************************/
list = ListAppend(list, 3);
list = ListAppend(list, 1);
list = ListAppend(list, 2);
list = partition(list, 3);
CU_ASSERT_EQUAL(ListLength(list), 3);
list = ListDestroy(list);
}
static void _088_merge_sorted_array(void)
{
int A1[] = {1,2,4,5,6,-1};
int B1[] = {3};
int C1[] = {1,2,3,4,5,6};
int A2[] = {-1,-1,0,0,0,0};
int B2[] = {-1,0};
int C2[] = {-1,-1,-1,0,0,0};
size_t i = 0;
merge(A1, 5, B1, 1);
for(i = 0; i < sizeof(A1) / sizeof(A1[0]); i++)
{
CU_ASSERT_EQUAL(C1[i], A1[i]);
}
merge(A2, 4, B2, 2);
for(i = 0; i < sizeof(A2) / sizeof(A2[0]); i++)
{
CU_ASSERT_EQUAL(C2[i], A2[i]);
}
}
static void _092_reverse_between(void)
{
ListNode* l = NULL;
ListNode* p = NULL;
size_t i = 0;
int a[] = {1, 4, 3, 2, 5};
/*************************************************************************
* 标准测试.
************************************************************************/
for(i = 1; i <= 5; i++)
{
l = ListAppend(l, i);
}
CU_ASSERT_PTR_NOT_NULL(l = reverseBetween(l, 2, 4));
CU_ASSERT_EQUAL(ListLength(l), 5);
for(p = l, i = 0; (p != NULL) && (i < sizeof(a) / sizeof(a[0]));
p = p->next, i++)
{
CU_ASSERT_EQUAL(p->val, a[i]);
}
l = ListDestroy(l);
/*************************************************************************
* m = n = 等于链表长度
************************************************************************/
for(i = 1; i <= 5; i++)
{
l = ListAppend(l, i);
}
CU_ASSERT_PTR_NOT_NULL(l = reverseBetween(l, 5, 5));
CU_ASSERT_EQUAL(ListLength(l), 5);
l = ListDestroy(l);
/*************************************************************************
* 只有一个节点的情况.
************************************************************************/
l = ListAppend(l, 5);
CU_ASSERT_PTR_NOT_NULL(l = reverseBetween(l, 1, 1));
CU_ASSERT_EQUAL(ListLength(l), 1);
l = ListDestroy(l);
/*************************************************************************
* 只有两个节点的情况.
************************************************************************/
l = ListAppend(l, 3);
l = ListAppend(l, 5);
CU_ASSERT_PTR_NOT_NULL(l = reverseBetween(l, 1, 1));
CU_ASSERT_EQUAL(ListLength(l), 2);
CU_ASSERT_EQUAL(l->val, 3);
CU_ASSERT_EQUAL(l->next->val, 5);
CU_ASSERT_PTR_NOT_NULL(l = reverseBetween(l, 1, 2));
CU_ASSERT_EQUAL(ListLength(l), 2);
CU_ASSERT_EQUAL(l->val, 5);
CU_ASSERT_EQUAL(l->next->val, 3);
l = ListDestroy(l);
}
static void _094_inorder_traversal(void)
{
TreeNode* t = NULL;
int* l = NULL;
int size = 0;
CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{1,#,2,3}"));
CU_ASSERT_PTR_NOT_NULL(l = inorderTraversal(t, &size));
CU_ASSERT_EQUAL(3, size);
CU_ASSERT_EQUAL(1, l[0]);
CU_ASSERT_EQUAL(3, l[1]);
CU_ASSERT_EQUAL(2, l[2]);
CU_ASSERT_PTR_NULL(t = TreeDestroy(t));
free(l);
}
static void _098_is_valid_bst(void)
{
TreeNode* t = NULL;
CU_ASSERT_EQUAL(isValidBST(NULL), true);
CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{1}"));
CU_ASSERT_EQUAL(isValidBST(t), true);
CU_ASSERT_PTR_NULL(t = TreeDestroy(t));
CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{1,2}"));
CU_ASSERT_EQUAL(isValidBST(t), false);
CU_ASSERT_PTR_NULL(t = TreeDestroy(t));
CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{1,1}"));
CU_ASSERT_EQUAL(isValidBST(t), false);
CU_ASSERT_PTR_NULL(t = TreeDestroy(t));
CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{3,#,2}"));
CU_ASSERT_EQUAL(isValidBST(t), false);
CU_ASSERT_PTR_NULL(t = TreeDestroy(t));
CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{4,2,6,1,3,5,7}"));
CU_ASSERT_EQUAL(isValidBST(t), true);
CU_ASSERT_PTR_NULL(t = TreeDestroy(t));
CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{10,5,15,#,#,6,20}"));
CU_ASSERT_EQUAL(isValidBST(t), false);
CU_ASSERT_PTR_NULL(t = TreeDestroy(t));
CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{-2147483648}"));
CU_ASSERT_EQUAL(isValidBST(t), true);
CU_ASSERT_PTR_NULL(t = TreeDestroy(t));
CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{-2147483648,#,2147483647}"));
CU_ASSERT_EQUAL(isValidBST(t), true);
CU_ASSERT_PTR_NULL(t = TreeDestroy(t));
}
static void _100_same_tree(void)
{
TreeNode* t1 = NULL;
TreeNode* t2 = NULL;
t1 = TreeNew(1, NULL, NULL, NULL);
CU_ASSERT_EQUAL(isSameTree(NULL, NULL), true);
CU_ASSERT_EQUAL(isSameTree(t1, NULL), false);
CU_ASSERT_EQUAL(isSameTree(NULL, t1), false);
CU_ASSERT_PTR_NULL(t1 = TreeDestroy(t1));
t1 = TreeNewByString("2,3,4,#,5,6,#,#,#,#,#,");
t2 = TreeNewByString("2,3,4,#,5,6,#,#,#,#,#,");
CU_ASSERT_EQUAL(isSameTree(t1, t2), true);
CU_ASSERT_PTR_NULL(t1 = TreeDestroy(t1));
CU_ASSERT_PTR_NULL(t2 = TreeDestroy(t2));
t1 = TreeNewByString("2,3,4,#,#,#,#,");
t2 = TreeNewByString("2,3,#,#,#,");
CU_ASSERT_EQUAL(isSameTree(t1, t2), false);
CU_ASSERT_PTR_NULL(t1 = TreeDestroy(t1));
CU_ASSERT_PTR_NULL(t2 = TreeDestroy(t2));
}
static void _101_is_symmetric(void)
{
TreeNode* t = NULL;
CU_ASSERT_EQUAL(isSymmetric(NULL), true);
CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{1}"));
CU_ASSERT_EQUAL(isSymmetric(t), true);
CU_ASSERT_PTR_NULL(t = TreeDestroy(t));
CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{1,2,2,3,4,4,3}"));
CU_ASSERT_EQUAL(isSymmetric(t), true);
CU_ASSERT_PTR_NULL(t = TreeDestroy(t));
CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{1,2,2,#,3,#,3}"));
CU_ASSERT_EQUAL(isSymmetric(t), false);
CU_ASSERT_PTR_NULL(t = TreeDestroy(t));
CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{1,2}"));
CU_ASSERT_EQUAL(isSymmetric(t), false);
CU_ASSERT_PTR_NULL(t = TreeDestroy(t));
}
static void _102_level_order(void)
{
TreeNode* t = NULL;
int** vector = NULL;
int* columnSizes = NULL;
int height = NULL;
/*************************************************************************
* Input:{3,9,20,#,#,15,7}, Output:[[3],[9,20],[15,7]]
************************************************************************/
CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{3,9,20,#,#,15,7}"));
CU_ASSERT_PTR_NOT_NULL(vector = levelOrder(t, &columnSizes, &height));
CU_ASSERT_PTR_NOT_NULL(columnSizes);
CU_ASSERT_EQUAL(height, 3);
CU_ASSERT_EQUAL(columnSizes[0], 1);
CU_ASSERT_EQUAL(vector[0][0], 3);
CU_ASSERT_EQUAL(columnSizes[1], 2);
CU_ASSERT_EQUAL(vector[1][0], 9);
CU_ASSERT_EQUAL(vector[1][1], 20);
CU_ASSERT_EQUAL(columnSizes[2], 2);
CU_ASSERT_EQUAL(vector[2][0], 15);
CU_ASSERT_EQUAL(vector[2][1], 7);
free(vector);
free(columnSizes);
t = TreeDestroy(t);
vector = NULL;
columnSizes = NULL;
height = 0;
/*************************************************************************
* Input:{1,2,3,4,5}, Output:[[1],[2,3],[4,5]]
************************************************************************/
CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{1,2,3,4,5}"));
CU_ASSERT_PTR_NOT_NULL(vector = levelOrder(t, &columnSizes, &height));
CU_ASSERT_PTR_NOT_NULL(columnSizes);
CU_ASSERT_EQUAL(height, 3);
CU_ASSERT_EQUAL(columnSizes[0], 1);
CU_ASSERT_EQUAL(vector[0][0], 1);
CU_ASSERT_EQUAL(columnSizes[1], 2);
CU_ASSERT_EQUAL(vector[1][0], 2);
CU_ASSERT_EQUAL(vector[1][1], 3);
CU_ASSERT_EQUAL(columnSizes[2], 2);
CU_ASSERT_EQUAL(vector[2][0], 4);
CU_ASSERT_EQUAL(vector[2][1], 5);
free(vector);
free(columnSizes);
t = TreeDestroy(t);
}
static void _104_max_depth(void)
{
TreeNode* t = NULL;
CU_ASSERT_EQUAL(maxDepth(NULL), 0);
CU_ASSERT_PTR_NOT_NULL(t = TreeNewByString("2,#,#,"));
CU_ASSERT_EQUAL(maxDepth(t), 1);
CU_ASSERT_PTR_NULL(t = TreeDestroy(t));
CU_ASSERT_PTR_NOT_NULL(t = TreeNewByString("2,3,4,#,5,6,#,#,#,"));
CU_ASSERT_EQUAL(maxDepth(t), 5);
CU_ASSERT_PTR_NULL(t = TreeDestroy(t));
}
static void _107_level_order_bottom(void)
{
TreeNode* t = NULL;
int** vector = NULL;
int* columnSizes = NULL;
int height = 0;
/*************************************************************************
* Input:{3,9,20,#,#,15,7}, Output:[[15,7],[9,20],[3]]
************************************************************************/
CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{3,9,20,#,#,15,7}"));
CU_ASSERT_PTR_NOT_NULL(vector = levelOrderBottom(t, &columnSizes, &height));
CU_ASSERT_PTR_NOT_NULL(columnSizes);
CU_ASSERT_EQUAL(height, 3);
CU_ASSERT_EQUAL(columnSizes[0], 2);
CU_ASSERT_EQUAL(vector[0][0], 15);
CU_ASSERT_EQUAL(vector[0][1], 7);
CU_ASSERT_EQUAL(columnSizes[1], 2);
CU_ASSERT_EQUAL(vector[1][0], 9);
CU_ASSERT_EQUAL(vector[1][1], 20);
CU_ASSERT_EQUAL(columnSizes[2], 1);
CU_ASSERT_EQUAL(vector[2][0], 3);
free(vector);
free(columnSizes);
t = TreeDestroy(t);
}
static void _110_lbe_is_balanced(void)
{
CU_ASSERT_EQUAL(leetcode_110_is_balanced(NULL), true);
}
static void _111_min_depth(void)
{
TreeNode* t = NULL;
CU_ASSERT_EQUAL(leetcode_111_min_depth(NULL), 0);
CU_ASSERT_PTR_NOT_NULL(t = TreeNewByString("2,#,#,"));
CU_ASSERT_EQUAL(leetcode_111_min_depth(t), 1);
CU_ASSERT_PTR_NULL(t = TreeDestroy(t));
CU_ASSERT_PTR_NOT_NULL(t = TreeNewByString("2,3,4,#,5,6,#,#,#,"));
CU_ASSERT_EQUAL(leetcode_111_min_depth(t), 5);
CU_ASSERT_PTR_NULL(t = TreeDestroy(t));
CU_ASSERT_PTR_NOT_NULL(t = TreeNewByString("1,2,#,#,#,"));
CU_ASSERT_EQUAL(leetcode_111_min_depth(t), 2);
CU_ASSERT_PTR_NULL(t = TreeDestroy(t));
CU_ASSERT_PTR_NOT_NULL(t = TreeNewByString("1,2,3,5,#,#,#,4,#,#,#,"));
CU_ASSERT_EQUAL(leetcode_111_min_depth(t), 3);
CU_ASSERT_PTR_NULL(t = TreeDestroy(t));
CU_ASSERT_PTR_NOT_NULL(t = TreeNewByString("2,3,4,#,5,6,#,#,#,#,1,#,#,#,"));
CU_ASSERT_EQUAL(leetcode_111_min_depth(t), 3);
CU_ASSERT_PTR_NULL(t = TreeDestroy(t));
}
static void _112_path_sum(void)
{
TreeNode* root = NULL;
root = TreeNew(5, NULL, NULL, NULL);
root->left = TreeNew(4, NULL, NULL, NULL);
root->right = TreeNew(8, NULL, NULL, NULL);
root->left->left = TreeNew(11, NULL, NULL, NULL);
root->left->left->left = TreeNew(7, NULL, NULL, NULL);
root->left->left->right = TreeNew(2, NULL, NULL, NULL);
root->right->left = TreeNew(13, NULL, NULL, NULL);
root->right->right = TreeNew(4, NULL, NULL, NULL);
root->right->right->right = TreeNew(1, NULL, NULL, NULL);
CU_ASSERT_EQUAL(leetcode_112_has_path_sum(root, 22), 1);
CU_ASSERT_PTR_NULL(root = TreeDestroy(root));
}
static void _114_flatten(void)
{
TreeNode* t = NULL;
t = TreeNewByStringOJ("{1}");
CU_ASSERT_PTR_NOT_NULL(t);
leetcode_114_flatten(t);
CU_ASSERT_PTR_NOT_NULL(t);
CU_ASSERT_EQUAL(1, t->val);
TreeDestroy(t);
t = TreeNewByStringOJ("{1,2,5,3,4,#,6}");
CU_ASSERT_PTR_NOT_NULL(t);
leetcode_114_flatten(t);
CU_ASSERT_PTR_NOT_NULL(t);
CU_ASSERT_EQUAL(1, t->val);
CU_ASSERT_EQUAL(2, t->right->val);
CU_ASSERT_EQUAL(3, t->right->right->val);
CU_ASSERT_EQUAL(4, t->right->right->right->val);
CU_ASSERT_EQUAL(5, t->right->right->right->right->val);
CU_ASSERT_EQUAL(6, t->right->right->right->right->right->val);
TreeDestroy(t);
}
static void _116_connect(void)
{
TreeLinkNode* t;
CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{1,2,3,4,5,6,7"));
leetcode_116_connect(t);
CU_ASSERT_EQUAL(t->val, 1);
CU_ASSERT_EQUAL(t->next, NULL);
CU_ASSERT_EQUAL(t->left->val, 2);
CU_ASSERT_EQUAL(t->left->next->val, 3);
CU_ASSERT_EQUAL(t->right, t->left->next);
CU_ASSERT_EQUAL(t->left->left->val, 4);
CU_ASSERT_EQUAL(t->left->left->next->val, 5);
CU_ASSERT_EQUAL(t->left->left->next, t->left->right);
CU_ASSERT_EQUAL(t->right->left->val, 6);
CU_ASSERT_EQUAL(t->right->right, t->right->left->next);
CU_ASSERT_EQUAL(t->right->left->next->val, 7);
CU_ASSERT_EQUAL(t->left->left->next->next->val, 6);
CU_ASSERT_EQUAL(t->left->left->next->next->next->val, 7);
CU_ASSERT_PTR_NULL(t = TreeDestroy(t));
}
static void _118_generate(void)
{
#if 0
list_t* row = NULL;
list_t* rows = NULL;
int val = 0;
CU_ASSERT_PTR_NOT_NULL(rows = leetcode_118_generate(0));
CU_ASSERT_EQUAL(lbe_list_size(rows), 0);
lbe_list_free(rows);
CU_ASSERT_PTR_NOT_NULL(rows = leetcode_118_generate(1));
CU_ASSERT_EQUAL(lbe_list_size(rows), 1);
CU_ASSERT_EQUAL(lbe_list_get(rows, 0, (void**)&row), LBE_OK);
CU_ASSERT_EQUAL(lbe_list_size(row), 1);
CU_ASSERT_EQUAL(lbe_list_get(row, 0, (void**)&val), LBE_OK);
CU_ASSERT_EQUAL(val, 1);
lbe_list_free(rows);
CU_ASSERT_PTR_NOT_NULL(rows = leetcode_118_generate(3));
CU_ASSERT_EQUAL(lbe_list_size(rows), 3);
CU_ASSERT_EQUAL(lbe_list_get(rows, 0, (void**)&row), LBE_OK);
CU_ASSERT_EQUAL(lbe_list_size(row), 1);
CU_ASSERT_EQUAL(lbe_list_get(row, 0, (void**)&val), LBE_OK);
CU_ASSERT_EQUAL(val, 1);
CU_ASSERT_EQUAL(lbe_list_get(rows, 1, (void**)&row), LBE_OK);
CU_ASSERT_EQUAL(lbe_list_size(row), 2);
CU_ASSERT_EQUAL(lbe_list_get(row, 0, (void**)&val), LBE_OK);
CU_ASSERT_EQUAL(val, 1);
CU_ASSERT_EQUAL(lbe_list_get(row, 1, (void**)&val), LBE_OK);
CU_ASSERT_EQUAL(val, 1);
CU_ASSERT_EQUAL(lbe_list_get(rows, 2, (void**)&row), LBE_OK);
CU_ASSERT_EQUAL(lbe_list_size(row), 3);
CU_ASSERT_EQUAL(lbe_list_get(row, 0, (void**)&val), LBE_OK);
CU_ASSERT_EQUAL(val, 1);
CU_ASSERT_EQUAL(lbe_list_get(row, 1, (void**)&val), LBE_OK);
CU_ASSERT_EQUAL(val, 2);
CU_ASSERT_EQUAL(lbe_list_get(row, 2, (void**)&val), LBE_OK);
CU_ASSERT_EQUAL(val, 1);
lbe_list_free(rows);
CU_ASSERT_PTR_NOT_NULL(rows = leetcode_118_generate(4));
CU_ASSERT_EQUAL(lbe_list_size(rows), 4);
CU_ASSERT_EQUAL(lbe_list_get(rows, 3, (void**)&row), LBE_OK);
CU_ASSERT_EQUAL(lbe_list_size(row), 4);
CU_ASSERT_EQUAL(lbe_list_get(row, 0, (void**)&val), LBE_OK);
CU_ASSERT_EQUAL(val, 1);
CU_ASSERT_EQUAL(lbe_list_get(row, 1, (void**)&val), LBE_OK);
CU_ASSERT_EQUAL(val, 3);
CU_ASSERT_EQUAL(lbe_list_get(row, 2, (void**)&val), LBE_OK);
CU_ASSERT_EQUAL(val, 3);
CU_ASSERT_EQUAL(lbe_list_get(row, 3, (void**)&val), LBE_OK);
CU_ASSERT_EQUAL(val, 1);
lbe_list_free(rows);
#endif
}
static void _119_get_row(void)
{
#if 0
list_t* l = NULL;
int _3[] = {1, 3, 3, 1};
int _4[] = {1, 4, 6, 4, 1};
int _5[] = {1, 5, 10, 10, 5, 1};
unsigned int i = 0;
int val = 0;
CU_ASSERT_PTR_NOT_NULL(l = leetcode_119_get_row(ARRAY_NUM(_3) - 1));
CU_ASSERT_EQUAL(lbe_list_size(l), ARRAY_NUM(_3));
for(i = 0; i < ARRAY_NUM(_3); i++)
{
CU_ASSERT_EQUAL(lbe_list_get(l, i, (void**)&val), LBE_OK);
CU_ASSERT_EQUAL(val, _3[i]);
}
lbe_list_free(l);
CU_ASSERT_PTR_NOT_NULL(l = leetcode_119_get_row(ARRAY_NUM(_4) - 1));
CU_ASSERT_EQUAL(lbe_list_size(l), ARRAY_NUM(_4));
for(i = 0; i < ARRAY_NUM(_4); i++)
{
CU_ASSERT_EQUAL(lbe_list_get(l, i, (void**)&val), LBE_OK);
CU_ASSERT_EQUAL(val, _4[i]);
}
lbe_list_free(l);
CU_ASSERT_PTR_NOT_NULL(l = leetcode_119_get_row(ARRAY_NUM(_5) - 1));
CU_ASSERT_EQUAL(lbe_list_size(l), ARRAY_NUM(_5));
for(i = 0; i < ARRAY_NUM(_5); i++)
{
CU_ASSERT_EQUAL(lbe_list_get(l, i, (void**)&val), LBE_OK);
CU_ASSERT_EQUAL(val, _5[i]);
}
lbe_list_free(l);
#endif
}
static void _125_is_palindrome(void)
{
CU_ASSERT_EQUAL(leetcode_125_is_palindrome(NULL), false);
CU_ASSERT_EQUAL(leetcode_125_is_palindrome(""), true);
CU_ASSERT_EQUAL(leetcode_125_is_palindrome("A man, a plan, a canal: Panama"), true);
CU_ASSERT_EQUAL(leetcode_125_is_palindrome("race a car"), false);
CU_ASSERT_EQUAL(leetcode_125_is_palindrome("Nella's simple hymn: \"I attain my help, Miss Allen.\""), true);
CU_ASSERT_EQUAL(leetcode_125_is_palindrome("1a2"), false);
CU_ASSERT_EQUAL(leetcode_125_is_palindrome("Sore was I ere I saw Eros."), true);
}
static void _136_single_number(void)
{
int A[] = {1, 2, 3, 4, 3, 1,4};
CU_ASSERT_EQUAL(leetcode_136_single_number(A, ARRAY_NUM(A)), 2);
}
static void _137_single_number_ii(void)
{
int A[] = {1, 3, 5, 3, 2, 1, 1, 5, 3, 5};
CU_ASSERT_EQUAL(leetcode_137_signle_number_ii(A, ARRAY_NUM(A)), 2);
}
static void _141_has_cycle(void)
{
ListNode* list = NULL;
ListNode* tail = NULL;
int i = 0;
for(i = 1; i <= 10; i++) list = ListAppend(list, i);
CU_ASSERT_PTR_NOT_NULL(tail = ListMakeCycle(list, 3));
CU_ASSERT_EQUAL(leetcode_141_has_cycle(list), true);
tail->next = NULL;
list = ListDestroy(list);
}
static void _142_detect_cycle(void)
{
ListNode* list = NULL;
ListNode* tail = NULL;
ListNode* cycle = NULL;
int i = 0;
for(i = 1; i<= 10; i++) list = ListAppend(list, i);
CU_ASSERT_PTR_NOT_NULL(tail = ListMakeCycle(list, 2));
CU_ASSERT_EQUAL(leetcode_141_has_cycle(list), true);
CU_ASSERT_PTR_NOT_NULL(cycle = leetcode_142_detect_cycle(list));
CU_ASSERT_PTR_EQUAL(cycle, list->next->next);
tail->next = NULL;
list = ListDestroy(list);
list = ListAppend(list, 1);
CU_ASSERT_PTR_NULL(cycle = leetcode_142_detect_cycle(list));
list = ListDestroy(list);
list = ListAppend(list, 1);
list->next = list;
CU_ASSERT_EQUAL(leetcode_141_has_cycle(list), true);
CU_ASSERT_PTR_EQUAL(list, cycle = leetcode_142_detect_cycle(list));
list->next = NULL;
list = ListDestroy(list);
}
static void _144_preorder_traversal(void)
{
#if 0
TreeNode* t = NULL;
list_t* list = NULL;
int val = 0;
CU_ASSERT_PTR_NULL(leetcode_144_preorder_traversal(NULL));
CU_ASSERT_PTR_NOT_NULL(t = TreeNewByStringOJ("{1,#,2,3}"));
CU_ASSERT_PTR_NOT_NULL(list = leetcode_144_preorder_traversal(t));
CU_ASSERT_EQUAL(lbe_list_size(list), 3);
CU_ASSERT_EQUAL(lbe_list_get(list, 0, (void**)&val), LBE_OK);
CU_ASSERT_EQUAL(val, 1);
CU_ASSERT_EQUAL(lbe_list_get(list, 1, (void**)&val), LBE_OK);
CU_ASSERT_EQUAL(val, 2);
CU_ASSERT_EQUAL(lbe_list_get(list, 2, (void**)&val), LBE_OK);
CU_ASSERT_EQUAL(val, 3);
lbe_list_free(list);
t = TreeDestroy(t);
#endif
}
static void _143_reorder_list(void)
{
ListNode* list = NULL;
/*************************************************************************
* Input: {1,2,3,4} Output:{1,4,2,3}
************************************************************************/
list = ListAppend(list, 1);
list = ListAppend(list, 2);
list = ListAppend(list, 3);
list = ListAppend(list, 4);
leetcode_143_reorder_list(list);
CU_ASSERT_EQUAL(ListLength(list), 4);
CU_ASSERT_EQUAL(list->val, 1);
CU_ASSERT_EQUAL(list->next->val, 4);
CU_ASSERT_EQUAL(list->next->next->val, 2);
CU_ASSERT_EQUAL(list->next->next->next->val, 3);
list = ListDestroy(list);
/*************************************************************************
* Input:{1}, Output:{1}
************************************************************************/
list = ListAppend(list, 1);
leetcode_143_reorder_list(list);
CU_ASSERT_EQUAL(ListLength(list), 1);
CU_ASSERT_EQUAL(list->val, 1);
list = ListDestroy(list);
/*************************************************************************
* Input:{1,2}, Output:{1,2}
************************************************************************/
list = ListAppend(list, 1);
list = ListAppend(list, 2);
leetcode_143_reorder_list(list);
CU_ASSERT_EQUAL(ListLength(list), 2);
CU_ASSERT_EQUAL(list->val, 1);
CU_ASSERT_EQUAL(list->next->val, 2);
list = ListDestroy(list);
/*************************************************************************
* Input:{1,2,3}, Output:{1,3,2}
************************************************************************/
list = ListAppend(list, 1);
list = ListAppend(list, 2);
list = ListAppend(list, 3);
leetcode_143_reorder_list(list);
CU_ASSERT_EQUAL(ListLength(list), 3);
CU_ASSERT_EQUAL(list->val, 1);
CU_ASSERT_EQUAL(list->next->val, 3);
CU_ASSERT_EQUAL(list->next->next->val, 2);
list = ListDestroy(list);
/*************************************************************************
* Input:{1,2,3,4,5}, Output:{1,5,2,4,3}
************************************************************************/
list = ListAppend(list, 1);
list = ListAppend(list, 2);
list = ListAppend(list, 3);
list = ListAppend(list, 4);
list = ListAppend(list, 5);
leetcode_143_reorder_list(list);
CU_ASSERT_EQUAL(ListLength(list), 5);
CU_ASSERT_EQUAL(list->val, 1);
CU_ASSERT_EQUAL(list->next->val, 5);
CU_ASSERT_EQUAL(list->next->next->val, 2);
CU_ASSERT_EQUAL(list->next->next->next->val, 4);
CU_ASSERT_EQUAL(list->next->next->next->next->val, 3);
list = ListDestroy(list);
}
static void _147_insertion_sort_list(void)
{
ListNode* list = NULL;
ListNode* p = NULL;
int i = 0;
list = ListAppend(list, 3);
list = ListAppend(list, 5);
list = ListAppend(list, 2);
list = ListAppend(list, 4);
list = ListAppend(list, 1);
list = leetcode_147_insertion_sort_list(list);
CU_ASSERT_EQUAL(ListLength(list), 5);
p = list;
for(i = 1; i <= 5; i++)
{
CU_ASSERT_EQUAL(p->val, i);
p = p->next;
}
list = ListDestroy(list);
}
static void _155_min_stack(void)
{
#if 0
MinStack* ms = NULL;
CU_ASSERT_PTR_NOT_NULL(ms = leetcode_155_min_stack());
ms->push(ms, 10);
CU_ASSERT_EQUAL(ms->top(ms), 10);
ms->push(ms, 20);
CU_ASSERT_EQUAL(ms->top(ms), 20);
CU_ASSERT_EQUAL(ms->getMin(ms), 10);
ms->push(ms, 9);
CU_ASSERT_EQUAL(ms->getMin(ms), 9);
ms->push(ms, 21);
ms->push(ms, 8);
CU_ASSERT_EQUAL(ms->getMin(ms), 8);
ms->pop(ms);
CU_ASSERT_EQUAL(ms->getMin(ms), 9);
CU_ASSERT_EQUAL(ms->top(ms), 21);
ms->pop(ms);
CU_ASSERT_EQUAL(ms->getMin(ms), ms->top(ms));
MinStackFree(ms);
#endif
}
static void _160_intersection_linked_list(void)
{
ListNode* a = NULL;
ListNode* b = NULL;
ListNode* c = NULL;
ListNode* p = NULL;
ListNode* node = NULL;
int i = 0;
int la = 0;
int lb = 0;
int lc = 0;
for(i = 0; i < 5; i++)
{
a = ListAppend(a, i);
}
for(i = 5; i < 10; i++)
{
b = ListAppend(b, i);
}
for(i = 10; i < 15; i++)
{
c = ListAppend(c, i);
}
la = ListLength(a);
lb = ListLength(b);
lc = ListLength(c);
for(p = a; p->next != NULL; p = p->next);
p->next = c;
for(p = b; p->next != NULL; p = p->next);
p->next = c;
CU_ASSERT_EQUAL(ListLength(a), la + lc);
CU_ASSERT_EQUAL(ListLength(b), lb + lc);
node = leetcode_160_get_intersection_node(a, b);
CU_ASSERT_PTR_EQUAL(node, c);
}
static void _165_compare_version(void)
{
CU_ASSERT_EQUAL(leetcode_165_compare_version(NULL, NULL), 0);
CU_ASSERT_EQUAL(leetcode_165_compare_version(NULL, "0.1"), 0);
CU_ASSERT_EQUAL(leetcode_165_compare_version("0.1", NULL), 0);
CU_ASSERT_EQUAL(leetcode_165_compare_version("0.1", "1.1"), -1);
CU_ASSERT_EQUAL(leetcode_165_compare_version("1.1", "1.2"), -1);
CU_ASSERT_EQUAL(leetcode_165_compare_version("1.2", "13.37"), -1);
CU_ASSERT_EQUAL(leetcode_165_compare_version("0.1.2", "0.1.3"), -1);
CU_ASSERT_EQUAL(leetcode_165_compare_version("0.1.2", "0.1.1"), 1);
CU_ASSERT_EQUAL(leetcode_165_compare_version("0.1.2", "0.1.2"), 0);
CU_ASSERT_EQUAL(leetcode_165_compare_version("2", "2.3"), -1);
CU_ASSERT_EQUAL(leetcode_165_compare_version("2.0.1", "2"), 1);
CU_ASSERT_EQUAL(leetcode_165_compare_version(".1", ".2"), -1);
CU_ASSERT_EQUAL(leetcode_165_compare_version("..2", "..1"), 1);
CU_ASSERT_EQUAL(leetcode_165_compare_version("..2.3.4", "..2.3.1"), 1);
CU_ASSERT_EQUAL(leetcode_165_compare_version("1", "1.1"), -1);
}
static void _168_convert_to_title(void)
{
CU_ASSERT_PTR_NULL(leetcode_168_convert_to_title(-1));
CU_ASSERT_PTR_NULL(leetcode_168_convert_to_title(0));
CU_ASSERT_PTR_NOT_NULL(leetcode_168_convert_to_title(1));
CU_ASSERT_EQUAL(strcmp(leetcode_168_convert_to_title(1), "A"), 0);
CU_ASSERT_EQUAL(strcmp(leetcode_168_convert_to_title(2), "B"), 0);
CU_ASSERT_EQUAL(strcmp(leetcode_168_convert_to_title(3), "C"), 0);
CU_ASSERT_EQUAL(strcmp(leetcode_168_convert_to_title(26), "Z"), 0);
CU_ASSERT_EQUAL(strcmp(leetcode_168_convert_to_title(27), "AA"), 0);
CU_ASSERT_EQUAL(strcmp(leetcode_168_convert_to_title(28), "AB"), 0);
CU_ASSERT_EQUAL(strcmp(leetcode_168_convert_to_title(24568), "AJHX"), 0);
}
static void _169_majority_element(void)
{
int A[] = {3, 2, 3, 3, 1};
CU_ASSERT_EQUAL(leetcode_169_majority_element(A, ARRAY_NUM(A)), 3);
}
static void _170_two_sum(void)
{
#if 0
TwoSum* ts = NULL;
CU_ASSERT_PTR_NOT_NULL(ts = leetcode_170_two_sum());
ts->add(ts, 1);
ts->add(ts, 3);
ts->add(ts, 5);
CU_ASSERT_EQUAL(true, ts->find(ts, 4));
CU_ASSERT_EQUAL(false, ts->find(ts, 7));
CU_ASSERT_EQUAL(true, ts->find(ts, 6));
CU_ASSERT_EQUAL(false, ts->find(ts, 10));
ts->add(ts, 5);
CU_ASSERT_EQUAL(true, ts->find(ts, 10));
TwoSumFree(ts);
#endif
}
static void _171_title_to_number(void)
{
CU_ASSERT_EQUAL(leetcode_171_title_to_number("A"), 1);
CU_ASSERT_EQUAL(leetcode_171_title_to_number("B"), 2);
CU_ASSERT_EQUAL(leetcode_171_title_to_number("C"), 3);
CU_ASSERT_EQUAL(leetcode_171_title_to_number("Z"), 26);
CU_ASSERT_EQUAL(leetcode_171_title_to_number("AA"), 27);
CU_ASSERT_EQUAL(leetcode_171_title_to_number("AB"), 28);
CU_ASSERT_EQUAL(leetcode_171_title_to_number("AAA"), 703);
}
static void _172_trailing_zeroes(void)
{
CU_ASSERT_EQUAL(leetcode_172_trailing_zeroes(1), 0);
CU_ASSERT_EQUAL(leetcode_172_trailing_zeroes(5), 1);
CU_ASSERT_EQUAL(leetcode_172_trailing_zeroes(6), 1);
CU_ASSERT_EQUAL(leetcode_172_trailing_zeroes(20),4);
}
static void _179_largest_number(void)
{
int a0[] = {1, 2};
int a1[] = {2, 2};
int a2[] = {3, 30};
int a3[] = {3, 34};
int a4[] = {43, 435};
int a5[] = {0, 0};
int a6[] = {1, 2, 3, 4, 5, 6, 7, 8, 9, 0};
int a7[] = {0, 1};
int a8[] = {1, 0};
int a9[] = {7543,5328,9834,1940,9387,871,5208,7,543};
int a10[] = {3, 30, 34, 5, 9};
int a11[] = {883,8};
int a12[] = {1440,7548,4240,6616,733,4712,883,8,9576};
int a13[] = {3, 33, 32};
int a14[] = {3,43,48,94,85,33,64,32,63,66};
char* s = NULL;
s = leetcode_179_largest_number(a0, ARRAY_NUM(a0));
CU_ASSERT_EQUAL(0, strcmp(s, "21"));
s = leetcode_179_largest_number(a1, ARRAY_NUM(a1));
CU_ASSERT_EQUAL(0, strcmp(s, "22"));
s = leetcode_179_largest_number(a2, ARRAY_NUM(a2));
CU_ASSERT_EQUAL(0, strcmp(s, "330"));
s = leetcode_179_largest_number(a3, ARRAY_NUM(a3));
CU_ASSERT_EQUAL(0, strcmp(s, "343"));
s = leetcode_179_largest_number(a4, ARRAY_NUM(a4));
CU_ASSERT_EQUAL(0, strcmp(s, "43543"));
s = leetcode_179_largest_number(a5, ARRAY_NUM(a5));
CU_ASSERT_EQUAL(0, strcmp(s, "0"));
s = leetcode_179_largest_number(a6, ARRAY_NUM(a6));
CU_ASSERT_EQUAL(0, strcmp(s, "9876543210"));
s = leetcode_179_largest_number(a7, ARRAY_NUM(a7));
CU_ASSERT_EQUAL(0, strcmp(s, "10"));
s = leetcode_179_largest_number(a8, ARRAY_NUM(a8));
CU_ASSERT_EQUAL(0, strcmp(s, "10"));
s = leetcode_179_largest_number(a9, ARRAY_NUM(a9));
CU_ASSERT_EQUAL(0, strcmp(s, "9834938787177543543532852081940"));
s = leetcode_179_largest_number(a10, ARRAY_NUM(a10));
CU_ASSERT_EQUAL(0, strcmp(s, "9534330"));
s = leetcode_179_largest_number(a11, ARRAY_NUM(a11));
CU_ASSERT_EQUAL(0, strcmp(s, "8883"));
s = leetcode_179_largest_number(a12, ARRAY_NUM(a12));
CU_ASSERT_EQUAL(0, strcmp(s, "9576888375487336616471242401440"));
s = leetcode_179_largest_number(a13, ARRAY_NUM(a13));
CU_ASSERT_EQUAL(0, strcmp(s, "33332"));
printf("s = %s\n", s);
s = leetcode_179_largest_number(a14, ARRAY_NUM(a14));
CU_ASSERT_EQUAL(0, strcmp(s, "9485666463484333332"));
printf("s = %s\n", s);
}
unsigned hanming_dist(const unsigned char *vec1, const unsigned char *vec2, unsigned dim)
{
unsigned i = 0;
const unsigned char popCountTable[] =
{
0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5, 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6, 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7, 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8
};
unsigned dist_ = 0;
for(i = 0; i != dim; ++i)
{
dist_ += popCountTable[vec1[i] ^ vec2[i]];
}
return dist_;
}
int get_key_line_number(const char* file, const char* key, char* out)
{
FILE * pf = NULL;
char string[256] = {0};
size_t result = 0;
size_t index = 0;
size_t row = 0;
size_t col = 0;
size_t offset = 0;
char* pos = NULL;
char* p = NULL;
if((file == NULL) || (key == NULL))
{
return -1;
}
if((*file == '\0') || (*key == '\0'))
{
return -2;
}
pf = fopen(file , "r");
if(pf == NULL)
{
perror("Error opening file");
return -3;
}
do
{
memset(string, 0, sizeof(string));
result = fread(string, 1, sizeof(string) - 1, pf);
pos = strstr(string, key);
p = string;
offset = (size_t)(pos - string);
for(index = 0; (index < sizeof(string) - 1) && (*p != '\0'); index++)
{
if((pos != NULL) && (offset == index))
{
out += sprintf(out, "row:%d+col:%d ", row, col);
pos = strstr(string + offset + strlen(key), key);
offset = (size_t)(pos - string);
}
if(string[index] == (char)'\n')
{
row++;
col = 0;
}
else
{
col++;
}
p++;
}
}while(!feof(pf));
fclose (pf);
return 0;
}
static void puts_string_to_file(const char* string, const char* file)
{
FILE* fp = NULL;
if((string == NULL) || (file == NULL)) return;
if(*string == '\0' || (*file == '\0')) return;
fp = fopen(file, "w");
fwrite(string, 1, strlen(string), fp);
fclose(fp);
}
static void _998_get_string_line_number(void)
{
char out[1024] = {0};
const char* str1 = "456123\n123\n123123\n23\n13";
const char* key1 = "123";
const char* str2 = "456123\n123\n123123\n23\n13";
const char* key2 = "23";
memset(out, 0, sizeof(out));
puts_string_to_file(str1, "abc.txt");
CU_ASSERT_EQUAL(get_key_line_number("abc.txt", key1, out), 0);
CU_ASSERT_EQUAL(strcmp(out, "row:0+col:3 row:1+col:0 row:2+col:0 row:2+col:3 "), 0);
CU_ASSERT_EQUAL(remove("abc.txt"), 0);
memset(out, 0, sizeof(out));
puts_string_to_file(str2, "abc.txt");
CU_ASSERT_EQUAL(get_key_line_number("abc.txt", key2, out), 0);
}
static void _999_oj_binary_tree_serialization(void)
{
TreeNode* t1 = NULL;
TreeNode* t2 = NULL;
t1 = TreeNewByStringOJ("{1,2,3,#,#,4,#,#,5}");
t2 = TreeNewByString("1,2,#,#,3,4,#,5,#,#,");
CU_ASSERT_EQUAL(isSameTree(t1, t2), true);
t1 = TreeDestroy(t1);
t2 = TreeDestroy(t2);
}
/*****************************************************************************
* 注册测试用例.
****************************************************************************/
static CU_TestInfo g_leetcode_test_case[] =
{
{" 2:Add Two Numbers", _002_add_two_numbers},
{" 6:ZigZag Conversion", _006_convert},
{" 7:Reverse Intege", _007_reverse},
{" 8:String to Integer (atoi)", _008_atoi},
{" 9:Palindrome Number", _009_is_palindrome},
{" 13:Roman to Integer", _013_roman_to_int},
{" 14:Longest Common Prefix", _014_longest_common_prefix},
{" 19:Remove Nth Node From End of List", _019_remove_nth_node_from_end},
{" 20:Valid Parentheses", _020_is_valid},
{" 21:Merge Two Sorted Lists", _021_merge_two_sorted_lists},
{" 24:Swap Nodes in Pairs", _024_swap_pairs},
{" 26:Remove Duplicates from Sorted Array", _026_remove_duplicates},
{" 27:Remove Element", _027_remove_element},
{" 28:Implement strstr", _028_implement_strstr},
{" 36:Valid Sudoku", _036_is_valid_sudoku},
{" 38:Count and Say", _038_count_and_say},
{" 58:Length of Last Word", _058_length_of_last_word},
{" 61:Rotate List", _061_rotate_right},
{" 66:Plus One", _066_plus_one},
{" 67:Add Binary", _067_add_binary},
{" 70:Climbing Stairs", _070_climb_stairs},
{" 78:Subsets", _078_subsets},
{" 82:Remove Duplicates from Sorted List II", _082_delete_duplicates_ii},
{" 83:Remove Duplicates from Sorted List", _083_delete_duplicates},
{" 86:Partition List", _086_partition_list},
{" 88:Merge Sorted Array", _088_merge_sorted_array},
{" 92:Reverse Linked List II", _092_reverse_between},
{" 94:Binary Tree Inorder Traversal", _094_inorder_traversal},
{" 98:Validate Binary Search Tree", _098_is_valid_bst},
{"100:Same Tree", _100_same_tree},
{"101:Symmetric Tree ", _101_is_symmetric},
{"102:Binary Tree Level Order Traversal", _102_level_order},
{"104:Maximum Depth of Binary Tree", _104_max_depth},
{"107:Binary Tree Level Order Traversal II", _107_level_order_bottom},
{"110:Balanced Binary Tree ", _110_lbe_is_balanced},
{"111:Minimum Depth of Binary Tree", _111_min_depth},
{"112:Path Sum", _112_path_sum},
{"114:Flatten Binary Tree to Linked List", _114_flatten},
{"116:Populating Next Right Pointers in Each Node", _116_connect},
{"118:Pascal's Triangle", _118_generate},
{"119:Pascal's Triangle II", _119_get_row},
{"125:Valid Palindrome", _125_is_palindrome},
{"136:Single Number", _136_single_number},
{"137:Single Number II", _137_single_number_ii},
{"141:Linked List Cycle", _141_has_cycle},
{"142:Linked List Cycle II", _142_detect_cycle},
{"143:Reorder List", _143_reorder_list},
{"144:Binary Tree Preorder Traversal ", _144_preorder_traversal},
{"147:Insertion Sort List", _147_insertion_sort_list},
{"155:Min Stack", _155_min_stack},
{"160:Intersection of Two Linked Lists ", _160_intersection_linked_list},
{"165:Compare Version Numbers", _165_compare_version},
{"168:Excel Sheet Column Title", _168_convert_to_title},
{"169:Majority Element", _169_majority_element},
{"170:Two Sum III - Data structure design", _170_two_sum},
{"171:Excel Sheet Column Number", _171_title_to_number},
{"172:Factorial Trailing Zeroes", _172_trailing_zeroes},
{"179:Largest Number", _179_largest_number},
{"998:Get String Line Number", _998_get_string_line_number},
{"999:OJ's Binary Tree Serialization", _999_oj_binary_tree_serialization},
CU_TEST_INFO_NULL,
};
static CU_SuiteInfo suites[] =
{
{"leetcode", NULL, NULL, NULL, NULL, g_leetcode_test_case},
CU_SUITE_INFO_NULL,
};
int main(int argc, char* argv[])
{
if(CUE_SUCCESS != CU_initialize_registry())
{
return CU_get_error();
}
if(CU_register_suites(suites) != CUE_SUCCESS)
{
printf("suite registration failed - %s\n", CU_get_error_msg());
return CU_get_error();
}
CU_basic_set_mode(CU_BRM_VERBOSE);
CU_basic_run_tests();
CU_cleanup_registry();
return CU_get_error();
}
此处可能存在不合适展示的内容，页面不予展示。您可通过相关编辑功能自查并修改。
如您确认内容无涉及 不当用语 / 纯广告导流 / 暴力 / 低俗色情 / 侵权 / 盗版 / 虚假 / 无价值内容或违法国家有关法律法规的内容，可点击提交进行申诉，我们将尽快为您处理。
马建仓 AI 助手