Welcome to MDGSF's Blog!

This is my github blog

[算法学习][leetcode] 53 Maximum Subarray

2016-12-21

mdgsf

Art

Leetcode
https://leetcode.com/problems/maximum-subarray/description/

题目

Find the contiguous subarray within an array (containing at least one number) which has the largest sum.

For example, given the array [-2,1,-3,4,-1,2,1,-5,4],

the contiguous subarray [4,-1,2,1] has the largest sum = 6.

题目翻译

题目解析

参考答案
```
int maxSubArray(int* nums, int numsSize) {
    int i;
    int iSum = 0;
    int iAns = -100000000;
    for (i = 0; i < numsSize; i++)
    {
        iSum += nums[i];
        if(iSum > iAns)
        {
            iAns = iSum;
        }

        if(iSum < 0)
        {
            iSum = 0;
        }
    }

    return iAns;
}
```
iSum 用来保存当前计算的子数组的和

iAns 用来保存最大的子数组的和

如果 iSum < 0, 则这个子数组必定不能作为其它子数组的前缀，所以直接抛弃。

假设 A 为 iSum < 0 的一个子数组， B 为 iSum >= 0 的一个子数组。

上图这种情况，B作为A的前缀，则B一定被先计算过。当A被抛弃时，B的结果已经被保存到iAns中过了。

而这种A作为B的前缀，在计算A的时候A就已经被抛弃了。
Read All

[算法学习][leetcode] 24 Swap Nodes in Pairs

2016-12-21

mdgsf

Art

Leetcode

https://leetcode.com/problems/swap-nodes-in-pairs/description/

题目

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.

题目翻译

题目解析

参考答案

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* swapPairs(struct ListNode* head) {
    if (NULL == head || NULL == head->next) {
        return head;
    }

    struct ListNode * pCur;
    struct ListNode * pNext;
    struct ListNode * pLastTail;

    pLastTail = head;
    pCur = head;
    pNext = pCur->next;
    while (pCur != NULL && pNext != NULL)
    {
        pCur->next = pNext->next;
        pNext->next = pCur;

        if(pCur == head)
        {
            head = pNext;
        }
        else
        {
            pLastTail->next = pNext;
        }

        pLastTail = pCur;
        pCur = pCur->next;
        pNext = pCur != NULL ? pCur->next : NULL;
    }

    return head;
}

Read All

[算法学习][leetcode] 21 Merge Two Sorted Lists

2016-12-21

mdgsf

Art

Leetcode

https://leetcode.com/problems/merge-two-sorted-lists/description/

题目

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.

题目翻译

题目解析

参考答案

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
struct ListNode* mergeTwoLists(struct ListNode* l1, struct ListNode* l2) {
    if(NULL == l1 && NULL == l2) {
        return NULL;
    }
    if(NULL == l1) {
        return l2;
    }
    if(NULL == l2) {
        return l1;
    }

    struct ListNode stDump;
    struct ListNode * pNewHead;
    pNewHead = &stDump;
    while (l1 != NULL && l2 != NULL)
    {
        if(l1->val < l2->val)
        {
            pNewHead->next = l1;
            l1 = l1->next;
        }
        else
        {
            pNewHead->next = l2;
            l2 = l2->next;
        }
        pNewHead = pNewHead->next;
    }


    if (l1 != NULL)
    {
        pNewHead->next = l1;
    }

    if(l2 != NULL)
    {
        pNewHead->next = l2;
    }

    return stDump.next;
}

Read All

[算法学习][leetcode] 19 Remove Nth Node From End of List

2016-12-21

mdgsf

Art

Leetcode

https://leetcode.com/problems/remove-nth-node-from-end-of-list/description/

题目

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.

题目翻译

题目解析

参考答案

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *removeNthFromEnd(ListNode *head, int n) {
        int iLen = 0;
        ListNode * p = head;
        while(p != NULL)
        {
            iLen++;
            p = p->next;
        }

        p = head;
        for (int i=0; i<iLen-n-1; i++)
        {
            p = p->next;
        }

        if((p == head) && (n == iLen))
        {
            head = p->next;
            delete p;
            return head;
        }

        ListNode * pstDel = p->next;
        if(pstDel->next == NULL)
        {
            p->next = NULL;
        }
        else
        {
            p->next = pstDel->next;
        }
        delete pstDel;
        return head;
    }
};

这个方法遍历的2遍。

如果要遍历1遍，则需要拿一个指针p1指向head，p1先向前走n步，然后再拿一个指针p2指向head，p1和p2同时向前，p1走到尾部时，p2就指向了要删除的节点。

Read All

[C/C++] 无符号数和有符号数的二进制图

2016-12-21

C/C++

C

Read All

[C/C++] 数组哨兵

2016-12-21

C/C++

在pcFindNormal()函数中，每次循环比较了 i<iLen 和 pcStr[i] == c 。

而在pcFindSentry()函数中，每次循环只比较了pcStr[i] == c。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <sys/time.h>

#define BUF_SIZE 100000000

char *pcFindNormal(char *pcStr, char c)
{
    int iLen = strlen(pcStr);
    for (int i=0; i<iLen; i++)
    {
        if(pcStr[i] == c)
        {
            return &pcStr[i];
        }
    }
    return NULL;
}

char *pcFindSentry(char *pcStr, char c)
{
    int iLen = strlen(pcStr);
    if(pcStr[iLen-1] == c)
    {
        return &pcStr[iLen-1];
    }

    char cHold = pcStr[iLen-1];
    pcStr[iLen-1] = c;
    int i;
    for (i=0; ; i++)
    {
        if(pcStr[i] == c)
        {
            break;
        }
    }
    pcStr[iLen-1] = cHold;

    return (i<iLen-1) ? (&pcStr[i]) : NULL;
}

int main()
{
    char *pcStr = (char*)malloc(sizeof(char)*BUF_SIZE);
    if(pcStr == NULL)
    {
        printf("malloc errorn");
    }

    for (int i=0; i<BUF_SIZE; i++)
    {
        pcStr[i] = '2';
    }
    pcStr[BUF_SIZE-3] = '1';

    struct timeval stStart;
    struct timeval stEnd;
    struct timezone stZone;

    gettimeofday(&stStart, &stZone);
    char *pcRet = pcFindNormal(pcStr, '1');
    if(pcRet == NULL)
    {
        printf("pcFindNormal errorn");
    }
    gettimeofday(&stEnd, &stZone);
    printf("normal spend time: %ldmsn",
            (stEnd.tv_sec-stStart.tv_sec)*1000+(stEnd.tv_usec-stStart.tv_usec)/1000);

    memset(&stStart, 0, sizeof(stStart));
    memset(&stEnd, 0, sizeof(stEnd));
    memset(&stZone, 0, sizeof(stZone));

    gettimeofday(&stStart, &stZone);
    pcRet = pcFindSentry(pcStr, '1');
    if(pcRet == NULL)
    {
        printf("pcFindSentry errorn");
    }
    gettimeofday(&stEnd, &stZone);
    printf("Sentry spend time: %ldmsn",
            (stEnd.tv_sec-stStart.tv_sec)*1000+(stEnd.tv_usec-stStart.tv_usec)/1000);

    free(pcStr);
    return 0;
}

Read All

70/97

Welcome to MDGSF's Blog!

[算法学习][leetcode] 53 Maximum Subarray

题目

题目翻译

题目解析

参考答案

[算法学习][leetcode] 24 Swap Nodes in Pairs

题目

题目翻译

题目解析

参考答案

[算法学习][leetcode] 21 Merge Two Sorted Lists

题目

题目翻译

题目解析

参考答案

[算法学习][leetcode] 19 Remove Nth Node From End of List

题目

题目翻译

题目解析

参考答案

[C/C++] 无符号数 和 有符号数 的二进制图

[C/C++] 数组哨兵

[C/C++] 无符号数和有符号数的二进制图