# LeetCodeTips1

### 1. Two Sum

``````给定 nums = [2,7,11,15], targe = 9,

``````

#### C语言版

``````/* Given nums = [2, 7, 11, 15], target = 9,
*
* Because nums[0] + nums[1] = 2 + 7 = 9,
* return [0, 1].
*/

#include <stdio.h>
#include <stdlib.h>

/**
* Note: The returned array must be malloced, assume caller calls free().
*/

int* twoSum(int* nums, int numsSize, int target) {
int i, j;

for (i = 0; i < numsSize; i++)
{
for(j = i+1; j < numsSize; j++)
{
if(nums[i] + nums[j] == target)
{
// Call malloc() for return value.
int* returnArray = malloc(2*sizeof(int));
returnArray[0] = i;
returnArray[1] = j;
return returnArray;
}
}
}
return NULL;
}

int main(void)
{
int nums[4] = {2, 7, 11, 15};

int *result = twoSum(nums, 4, 9);
if(result != NULL)
{
printf("result is %d, %d \n", result[0], result[1]);
}

// Call malloc in function twoSum(), so now will call free()
if(result != NULL)
{
free(result);
}
return 0;
}

``````

``````\$ valgrind -v --leak-check=full ./TwoSum
......
==3283== HEAP SUMMARY:
==3283==     in use at exit: 0 bytes in 0 blocks
==3283==   total heap usage: 2 allocs, 2 frees, 1,032 bytes allocated
==3283==
==3283== All heap blocks were freed -- no leaks are possible
==3283==
==3283== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
==3283== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
``````

http://stackoverflow.com/questions/1938735/does-freeptr-where-ptr-is-null-corrupt-memory

#### Python版

``````class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
returnvalue = []
for num in nums:
for left in nums[nums.index(num)+1:]:
if (num + left == target):
returnvalue.append(nums.index(num))
returnvalue.append(nums.index(left))
return returnvalue

print (Solution().twoSum([5, 4, 11, 17], 9))
``````

#### 引入的bug

``````class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
returnvalue = []
index = 0
for num in nums:
index += 1
for left in nums[index:]:
if (num + left == target):
returnvalue.append(nums.index(num))
returnvalue.append(nums[index:].index(left)+index)
return returnvalue

print (Solution().twoSum([0,4,3,0], 0))
``````

#### Python Hash

``````class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
# Use a dictionary for holding nums
num_dic = {}
for i in range(len(nums)):
if target - nums[i] in num_dic.keys():
return [num_dic[target - nums[i]],i]
else:
# directly put it into the num_dic
num_dic[nums[i]] = i
return []

print (Solution().twoSum([0,4,3,0], 0))
print (Solution().twoSum([3, 4, 2], 6))
``````

``````class Solution(object):
def twoSum(self, nums, target):
"""
:type nums: List[int]
:type target: int
:rtype: List[int]
"""
# Use a dictionary for holding nums
num_dic = {}
for i,v in enumerate(nums):
if v in num_dic.keys():
return [num_dic[v],i]
num_dic[target-v] = i

print (Solution().twoSum([0,4,3,0], 0))
print (Solution().twoSum([3, 4, 2], 6))
``````

Python里对于这个问题的优化大概就到这里了。可以看到，简单的问题也是需要认真思考了，认认真真的来 做leetcode吧。

``````给定两个用链表表示的非负数。数字存储是reverse order， 每个节点存有一个数字。将节点上的数字

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

Oct10晚上的测试框架写成这样：

``````/**
* struct ListNode {
*     int val;
*     struct ListNode *next;
* };
*/

#include <stdio.h>
#include <stdlib.h>

// Definition of the ListNode
struct ListNode {
int val;
struct ListNode *next;
};

// create_list()
struct ListNode* create_list(int val)
{
printf("\n Creating list with headnode as [%d]\n", val);
struct ListNode *ptr = (struct ListNode*)malloc(sizeof(struct ListNode));
if(NULL == ptr)
{
printf("\n Node creation failed \n");
return NULL;
}
ptr->val = val;
ptr->next = NULL;

return ptr;
}

// print the list
{

while(current != NULL)
{
printf("%d ->", current->val);
current = current->next;
}
printf("NULL\n");
}

int shiftnumber = 0;

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
printf("\nJust Called this function!\n");

struct ListNode* currentl1 = l1;
struct ListNode* currentl2 = l2;
// Holding the return value
struct ListNode* ptr = (struct ListNode*)malloc(sizeof(struct ListNode));
ptr->next = NULL;
shiftnumber = 0;

// First calculate the longest Linked List
int lenl1 = 0;
int lenl2 = 0;

while(currentl1 != NULL)
{
lenl1++;
currentl1 = currentl1->next;
}
while(currentl2 != NULL)
{
lenl2++;
currentl2 = currentl2->next;
}
printf("len1 is %d, len2 is %d\n", lenl1, lenl2);

currentl1 = l1;
currentl2 = l2;

// Get the largest length, thus we could do some tricks.
//
//
//
//
//
while((currentl1 != NULL) && (currentl2 != NULL))
{
ptr->val = (currentl1->val + currentl2->val)%10+shiftnumber;
shiftnumber = 0;
if((currentl1->val + currentl2->val)>=10)
{
shiftnumber = (currentl1->val + currentl2->val)/10;
}
//ptr->val = (currentl1->val + currentl2->val)%10;
if(currentl1->next != NULL)
{
ptr->next = (struct ListNode*)malloc(sizeof(struct ListNode));
ptr->next->next = NULL;
ptr = ptr->next;
}
// shiftnumber exists, so you should assign shiftnumber to the
// newnode
else
{
// Only check shiftnumber
if(shiftnumber != 0)
{
ptr->next = (struct ListNode*)malloc(sizeof(struct ListNode));
ptr->next->next = NULL;
ptr->next->val = shiftnumber;
}

}
currentl1 = currentl1->next;
currentl2 = currentl2->next;
}
}

int main(void)
{
struct ListNode test1, test1_2, test1_3;
struct ListNode* p = &test1;
p->val = 2;
p->next = &test1_2;
p->next->val = 4;
p->next->next = &test1_3;
p->next->next->val = 4;
p->next->next->next = NULL;
printf("### List l1!\n");
print_list(p);

struct ListNode test2, test2_2, test2_3;
struct ListNode* q = &test2;
q->val = 5;
q->next = &test2_2;
q->next->val = 6;
q->next->next = &test2_3;
q->next->next->val = 7;
q->next->next->next = NULL;
printf("### List l2!\n");
print_list(q);

printf("\n *** Start testing addTwoNumbers! *** \n");
struct ListNode* r = addTwoNumbers(p, q);
print_list(r);
// Remember to free memory here
//while(r->next != NULL);
//{
//	printf("See if you could get the money?\n");
//	r = r->next;
//}

printf("\n *** Finished testing addTwoNumbers! *** \n");

return 0;
}
``````

``````int shiftnumber = 0;

struct ListNode* addTwoNumbers(struct ListNode* l1, struct ListNode* l2) {
struct ListNode* currentl1 = l1;
struct ListNode* currentl2 = l2;
// Holding the return value
struct ListNode* ptr = (struct ListNode*)malloc(sizeof(struct ListNode));
ptr->next = NULL;
shiftnumber = 0;

// First calculate the longest Linked List
int lenl1 = 0;
int lenl2 = 0;

while(currentl1 != NULL)
{
lenl1++;
currentl1 = currentl1->next;
}
while(currentl2 != NULL)
{
lenl2++;
currentl2 = currentl2->next;
}

currentl1 = l1;
currentl2 = l2;

// Get the largest length, thus we could use this number for controlling the
// return value.
{
int ValOfL1, ValOfL2 = 0;
ValOfL1 = (currentl1 == NULL)?0:currentl1->val;
ValOfL2 = (currentl2 == NULL)?0:currentl2->val;
ptr->val = ((ValOfL1 + ValOfL2)%10 + shiftnumber)%10;
if(((ValOfL1 + ValOfL2)%10 + shiftnumber) == 10)
{
shiftnumber = 1;
}
else{
shiftnumber = 0;
if((ValOfL1 + ValOfL2)>=10)
{
shiftnumber = (ValOfL1 + ValOfL2)/10;
}
}
// Allocate memory for new node. Only allocate (LinkedListLen - 1) times
{
ptr->next = (struct ListNode*)malloc(sizeof(struct ListNode));
ptr->next->next = NULL;
ptr = ptr->next;
}
// Switch to next node.
if(currentl1 != NULL)
{
currentl1 = currentl1->next;
}
if(currentl2 != NULL)
{
currentl2 = currentl2->next;
}
}
// If shiftnumber > 0, allocate a new node for holding it
if(shiftnumber != 0)
{
ptr->next = (struct ListNode*)malloc(sizeof(struct ListNode));
ptr->next->next = NULL;
ptr->next->val = shiftnumber;
}

}
``````

1，考虑到两个输入的链表长度可能不一样，因而先得到最长的链表长度，用这个最长的长度来做递归。
2, 是否有进位通过一个全局表两shiftnumber来hold. 如果相加到最后依然有进位，则在循环外开辟一块空间来存放这个进位。
3, 两个链表中的任何一个一旦走到了NULL指针，则其值用0来代替。
4, 三目运算符的使用。
5, `ptr->val = ((ValOfL1 + ValOfL2)%10 + shiftnumber)%10;`，这个是考虑到test case:

``````[9]
[1, 9]
``````

1, 对指针的使用要非常小心。
2, 就是凭直觉写出来的，算法很差, 代码可读性也很差。

### Longest substr

The sample code is listed, while to be optimized:

``````#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAXN 50000

// q should be longer than p
int comlen(char* p, char* q)
{
int i = 0;
while (*q && (*p++ == *q++))
{
i++;
}
return i;
}

int cstring_cmp(const void *a, const void *b)
{
const char **ia = (const char **)a;
const char **ib = (const char **)b;
return strcmp(*ia, *ib);
}

int lengthOfLongestSubstring(char* s) {
char c[MAXN];
char* a[MAXN];

// Create a new array which hold char *s
// Remove all of the duplicated items in array
// no_duplicated[]

char ch;
int n = 0;
for(n = 0; n < strlen(s); n++)
{
printf("%c ",s[n]);
a[n] = &c[n];
c[n] = s[n];
}
a[n] = 0;

qsort(a, n, sizeof(char*), cstring_cmp);

int maxlen = 0;
int len = 0;
int maxi = 0;
for (int i = 0; i < n - 1; i++)
{
len = comlen(a[i], a[i + 1]);
printf("len is %d\n", len);
if (len > maxlen)
{
maxlen = len;
maxi = i;
}
}

printf("maxlen:%d\tmax string:\t", maxlen);
char ch_tmp;
for (int i = 0; i < maxlen; i++)
{
ch_tmp = *(a[maxi] + i);
printf("%c", ch_tmp);
}
printf("\n");

return maxlen;
}

int main(void)
{
char s[100] = "abcabcccc";
char t[100] = "bbbbbbbbbbbb";
char k[100] = "pwwkew";
lengthOfLongestSubstring(s);
lengthOfLongestSubstring(t);
lengthOfLongestSubstring(k);
return 0;
}

``````