Welcome to MDGSF's Blog!

This is my github blog

[算法学习][排列组合] N 皇后问题

2017-03-09

mdgsf

Art

用二维数组

#include <unistd.h>
#include <sys/types.h>
#include <sys/time.h>
#include <sys/resource.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <stack>
using namespace std;

#define N 8

int aiBoard[N][N] = {0};

int iCount = 0;

void vShowBoard()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            printf("%d ", aiBoard[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}

bool bIsValid(int iRow, int iCol)
{
    for (int i = 0; i < iRow; i++)
    {
        if( (aiBoard[i][iCol] == 1) ||
            ( ( iCol - (iRow - i) >= 0) && (aiBoard[i][ iCol - (iRow - i) ] == 1) ) ||
            ( ( iCol + (iRow - i) < N ) && (aiBoard[i][ iCol + (iRow - i) ] == 1) )
          )
        {
            return false;
        }
    }
    return true;
}

void vFunc(int iRow)
{
    if(iRow >= N)
    {
        vShowBoard();
        iCount++;
    }
    else
    {
        for (int iCol = 0; iCol < N; iCol++)
        {
            if(bIsValid(iRow, iCol))
            {
                aiBoard[iRow][iCol] = 1;
                vFunc(iRow+1);
                aiBoard[iRow][iCol] = 0;
            }
        }
    }
}

int main()
{
    vFunc(0);
    printf("iCount = %d\n", iCount);
    return 0;
}

用一维数组

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

#define N 8

//key: iRow,  value: iCol
int aiBoard[N] = {0};

int iCount = 0;

void vShowBoard()
{
    for (int i = 0; i < N; i++)
    {
        int j;
        for (j = 0; j < aiBoard[i]; j++) {
            printf("X ");
        }
        printf("Q ");
        for (j = aiBoard[i]+1; j < N; j++) {
            printf("X ");
        }

        printf("\n");
    }
    printf("\n");
}

bool bIsValid(int iRow, int iCol)
{
    for (int i = 0; i < iRow; i++)
    {
        if( (aiBoard[i] == iCol) || (abs(iRow - i) == abs(iCol - aiBoard[i])) )
        {
            return false;
        }
    }
    return true;
}

void vFunc(int iRow)
{
    if(iRow >= N)
    {
        vShowBoard();
        iCount++;
    }
    else
    {
        for (int iCol = 0; iCol < N; iCol++)
        {
            if(bIsValid(iRow, iCol))
            {
                aiBoard[iRow] = iCol;
                vFunc(iRow+1);
            }
        }
    }
}

int main()
{
    vFunc(0);
    printf("iCount = %d\n", iCount);
    return 0;
}

Read All

[C/C++] malloc 实现

2017-03-08

C/C++

C Strcat

摘自 FreeRTOS 的 heap5.c

#ifndef HEAP_HJ
#define HEAP_HJ

#include <stdio.h>
#include <stdint.h>

#define portBYTE_ALIGNMENT 8

#if portBYTE_ALIGNMENT == 8
    #define portBYTE_ALIGNMENT_MASK ( 0x0007U )
#endif

#if portBYTE_ALIGNMENT == 4
    #define portBYTE_ALIGNMENT_MASK ( 0x0003 )
#endif

#if portBYTE_ALIGNMENT == 2
    #define portBYTE_ALIGNMENT_MASK ( 0x0001 )
#endif

#if portBYTE_ALIGNMENT == 1
    #define portBYTE_ALIGNMENT_MASK ( 0x0000 )
#endif

#define configTOTAL_HEAP_SIZE 256*1024

#define configASSERT( x )

#define vTaskSuspendAll()
#define xTaskResumeAll()

#define mtCOVERAGE_TEST_MARKER()

typedef struct _SHeapRegion
{
    uint8_t * pucStartAddress;
    size_t xSizeInBytes;
}SHeapRegion;


void vPortDefineHeapRegions(const SHeapRegion * const pxHeapRegions);

void * pvPortMalloc(size_t xWantedSize);

void vPortFree(void * pv);

size_t xPortGetFreeHeapSize(void);

size_t xPortGetMinimumEverFreeHeapSize(void);

void dump_mem_block_list();

#endif

```cpp #include “heap.h”

/* Block sizes must not get too small. */ #define heapMINIMUM_BLOCK_SIZE ( (size_t) (uxHeapStructSize « 1) )

/* Assumes 8bit bytes! */ #define heapBITS_PER_BYTE ( (size_t) 8 )

/* Define the linked list structure. This is used to link free blocks in order

of their memory address. */ typedef struct _SBlock { struct _SBlock * pxNextFreeBlock; size_t xBlockSize; }SBlock;

static const uint32_t uxHeapStructSize = ( ( sizeof(SBlock) + (portBYTE_ALIGNMENT - 1) ) & ~portBYTE_ALIGNMENT_MASK );

static SBlock xStart; static SBlock * pxEnd = NULL;

static size_t xFreeBytesRemaining = 0; static size_t xMinimumEverFreeBytesRemaining = 0;

static size_t xBlockAllocatedBit = 0;

static uint8_t ucHeap[configTOTAL_HEAP_SIZE];

SHeapRegion xHeapRegions[] = { { ucHeap, sizeof(ucHeap) }, { NULL, 0 } // Terminates the array. };

static void s_vInsertBlockIntoFreeList(SBlock * pxBlockToInsert);

Read All

[算法学习][面试题] 2015华为校招机试

2017-03-06

mdgsf

Art

C String Permutation

http://blog.csdn.net/Hackbuteer1/article/details/39253767

第一题(60分)：按要求分解字符串，输入两个数M，N； M代表输入的M串字符串， N代表输出的每串字符串的位数，不够补0。例如：输入2,8， “abc” ，“123456789”，则输出为“abc00000”,“12345678“,”90000000”

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

void func(char * pcStr, int n)
{
    if(NULL == pcStr || n <= 0) {
        return ;
    }

    int iLen = strlen(pcStr);
    printf("##########%s %d\n", pcStr, iLen);

    int iCurCount = 0;
    for (int i = 0; i < iLen; i++)
    {
        printf("%c", pcStr[i]);
        iCurCount++;

        if(iCurCount == n)
        {
            iCurCount = 0;
            printf("\n");
        }
    }

    while (iCurCount < n)
    {
        printf("0");
        iCurCount++;
    }
    printf("\n");
}

int main()
{
    int m = 0;
    int n = 0;
    char acStr[1024] = {0};

    while (scanf("%d %d", &m, &n) != EOF)
    {
        for (int i = 0; i < m; i++)
        {
            scanf("%s", acStr);
            func(acStr, n);
        }
    }
    return 0;
}

第一题：拼音转数字输入是一个只包含拼音的字符串，请输出对应的数字序列。转换关系如下：描述：拼音 yi er san si wu liu qi ba jiu 阿拉伯数字 1 2 3 4 5 6 7 8 9 输入字符只包含小写字母，所有字符都可以正好匹配

运行时间限制：无限制内存限制：无限制输入：一行字符串，长度小于1000 输出：一行字符（数字）串样例输入： yiersansi 样例输出： 1234

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

typedef struct _STrieNode
{
    char m_c;
    int m_iNumber;
    int m_iLen;
    bool m_bIsEnd;
    struct _STrieNode * m_apstChild[26];
    _STrieNode()
    {
        m_iLen = 0;
        m_bIsEnd = false;
        memset(m_apstChild, 0, sizeof(m_apstChild));
    }
}STrieNode;

class CTrie
{
public:
    CTrie()
    {
    }

    int m_iInsert(const char * pcStr, int iNumber)
    {
        if(NULL == pcStr) {
            return EXIT_FAILURE;
        }

        int iLen = strlen(pcStr);
        STrieNode * pstCurNode = &m_stRoot;
        for (int i = 0; i < iLen; i++)
        {
            if(pstCurNode->m_apstChild[ pcStr[i]-'a' ] == NULL)
            {
                STrieNode * pstNewNode = (STrieNode*)malloc(sizeof(STrieNode));
                if(NULL == pstNewNode) {
                    return EXIT_FAILURE;
                }

                memset(pstNewNode, 0, sizeof(STrieNode));

                pstNewNode->m_c = pcStr[i];
                pstNewNode->m_bIsEnd = (i==iLen-1) ? true : false;
                pstCurNode->m_apstChild[ pcStr[i]-'a' ] = pstNewNode;
            }

            pstCurNode = pstCurNode->m_apstChild[ pcStr[i]-'a' ];

            if(i == iLen-1)
            {
                pstCurNode->m_iLen = iLen;
                pstCurNode->m_iNumber = iNumber;
            }
        }

        return EXIT_SUCCESS;
    }

    int m_iFind(const char * pcStr, int * piNumber, int * piLen)
    {
        if(NULL == pcStr || NULL == piNumber || NULL == piLen) {
            return EXIT_FAILURE;
        }

        int iStrLen = strlen(pcStr);
        STrieNode * pstCurNode = &m_stRoot;
        for (int i = 0; i < iStrLen; i++)
        {
            pstCurNode = pstCurNode->m_apstChild[ pcStr[i] - 'a' ];
            if(pstCurNode == NULL)
            {
                return EXIT_FAILURE;
            }

            if(pstCurNode->m_bIsEnd)
            {
                *piNumber = pstCurNode->m_iNumber;
                *piLen = pstCurNode->m_iLen;
                return EXIT_SUCCESS;
            }
        }

        return EXIT_FAILURE;
    }

private:
    STrieNode m_stRoot;
};

CTrie g_oTrieTree;

void func(const char * pcStr)
{
    if(NULL == pcStr) {
        return ;
    }

    int iStrLen = strlen(pcStr);
    const char * pcIndex = pcStr;
    while (*pcIndex != '\0' && iStrLen > 0)
    {
        int iNumber = 0;
        int iLen = 0;
        int iRet = g_oTrieTree.m_iFind(pcIndex, &iNumber, &iLen);
        if(iRet != EXIT_SUCCESS) {
            printf("func m_iFind failed\n");
            return ;
        }
        printf("%d", iNumber);
        pcIndex += iLen;
        iStrLen -= iLen;
    }

    printf("\n");
}


int main()
{
    g_oTrieTree.m_iInsert("yi", 1);
    g_oTrieTree.m_iInsert("er", 2);
    g_oTrieTree.m_iInsert("san", 3);
    g_oTrieTree.m_iInsert("si", 4);

    g_oTrieTree.m_iInsert("wu", 5);
    g_oTrieTree.m_iInsert("liu", 6);
    g_oTrieTree.m_iInsert("qi", 7);
    g_oTrieTree.m_iInsert("ba", 8);
    g_oTrieTree.m_iInsert("jiu", 9);

    char acStr[1024] = {0};

    while (scanf("%s", acStr) != EOF)
    {
        func(acStr);
    }
    return 0;
}

第二题：去除重复字符并排序运行时间限制：无限制内容限制：无限制输入：字符串输出：去除重复字符并排序的字符串样例输入： aabcdefff 样例输出： abcdef

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

void func(char * pcStr)
{
    if(NULL == pcStr) {
        return;
    }

    int iStrLen = strlen(pcStr);
    for (int i = 0; i < iStrLen; )
    {
        printf("%c", pcStr[i]);
        if(i == iStrLen - 1)
        {
            break;
        }

        int j;
        for (j = i+1; j < iStrLen; j++)
        {
            if(pcStr[i] != pcStr[j])
            {
                i = j;
                break;
            }
        }
        if(j == iStrLen)
        {
            break;
        }
    }
    printf("\n");
}

int main()
{
    char acStr[1024] = {0};

    while (scanf("%s", acStr) != EOF)
    {
        func(acStr);
    }
    return 0;
}

第三题：等式变换输入一个正整数X，在下面的等式左边的数字之间添加+号或者-号，使得等式成立。 1 2 3 4 5 6 7 8 9 = X 比如： 12-34+5-67+89 = 5 1+23+4-5+6-7-8-9 = 5 请编写程序，统计满足输入整数的所有整数个数。输入：正整数，等式右边的数字输出：使该等式成立的个数样例输入：5 样例输出：21

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <iostream>
#include <stack>
using namespace std;

int iInfixToPostfix(const char * pcInfix, char * pcPostfix)
{
    if(NULL == pcInfix || NULL == pcPostfix) {
        return EXIT_FAILURE;
    }

    stack<char> myStack;
    int iInfixLen = strlen(pcInfix);
    for (int i = 0; i < iInfixLen; i++)
    {
        char c = pcInfix[i];
        if(c >= '0' && c <= '9')
        {
            *pcPostfix++ = c;
        }
        else
        {
            switch(c)
            {
            case '+':
            case '-':
                {
                    while (!myStack.empty())
                    {
                        *pcPostfix++ = myStack.top();
                        myStack.pop();
                    }
                    myStack.push(c);
                }
                break;
            case '?':
                {
                    while (!myStack.empty())
                    {
                        if(myStack.top() == '?')
                        {
                            *pcPostfix++ = myStack.top();
                            myStack.pop();
                        }
                        else
                        {
                            break;
                        }
                    }
                    myStack.push(c);
                }
                break;
            default:
                printf("unknown c = %d\n", c);
                break;
            }
        }
    }

    while (!myStack.empty())
    {
        *pcPostfix++ = myStack.top();
        myStack.pop();
    }

    return EXIT_SUCCESS;
}


int iCalcPostfix(const char * pcPostfix, int * piResult)
{
    if(NULL == pcPostfix) {
        return EXIT_FAILURE;
    }

    stack<int> myStack;
    int iLen = strlen(pcPostfix);

    for (int i = 0; i < iLen; i++)
    {
        char c = pcPostfix[i];
        if(c >= '0' && c <= '9')
        {
            myStack.push(c - '0');
        }
        else
        {
            if(myStack.size() < 2) {
                return EXIT_FAILURE;
            }

            int iNum2 = myStack.top();
            myStack.pop();

            int iNum1 = myStack.top();
            myStack.pop();

            switch(c)
            {
            case '+':
                myStack.push(iNum1 + iNum2);
                break;
            case '-':
                myStack.push(iNum1 - iNum2);
                break;
            case '?':
                myStack.push(iNum1*10 + iNum2);
                break;
            default:
                printf("unknown c = %c\n", c);
                break;
            }
        }
    }

    if(myStack.size() != 1)
    {
        return EXIT_FAILURE;
    }

    *piResult = myStack.top();

    return EXIT_SUCCESS;
}

int iCount = 0;
char aiOpts[20] = {0};

void func(int n, int iCurNum, int iOptIdx)
{
    if(iCurNum == 10)
    {
        char acStr[1024] = {0};
        acStr[0] = '1';
        int iStrIdx = 1;
        for (int i = 0; i < iOptIdx; i++)
        {
            acStr[iStrIdx++] = aiOpts[i];
            acStr[iStrIdx++] = i + 2 + '0';
        }

        char acPostfix[1024] = {0};
        iInfixToPostfix(acStr, acPostfix);

        int iRet = 0;
        iCalcPostfix(acPostfix, &iRet);

        if(iRet == 5)
        {
            iCount++;
        }

        return ;
    }

    aiOpts[iOptIdx] = '+';
    func(n, iCurNum+1, iOptIdx+1);

    aiOpts[iOptIdx] = '-';
    func(n, iCurNum+1, iOptIdx+1);

    aiOpts[iOptIdx] = '?';
    func(n, iCurNum+1, iOptIdx+1);
}

int main()
{
    int n;
    while (scanf("%d", &n) != EOF)
    {
        iCount = 0;
        func(n, 2, 0);
        printf("iCount = %d\n", iCount);
    }
    return 0;
}

Read All

[openssl] 生成SSL证书

2017-03-03

mdgsf

openssl

Openssl Crt
openssl中有如下后缀名的文件

.key格式：私有的密钥

.csr格式：证书签名请求（证书请求文件），含有公钥信息，certificate signing request的缩写

.crt格式：证书文件，certificate的缩写

.crl格式：证书吊销列表，Certificate Revocation List的缩写

.pem格式：用于导出，导入证书时候的证书的格式，有证书开头，结尾的格式

CA根证书的生成步骤

生成CA私钥（.key）–>生成CA证书请求（.csr）–>自签名得到根证书（.crt）（CA给自已颁发的证书）。
```
# Generate CA private key
openssl genrsa -out ca.key 2048
# Generate CSR
openssl req -new -key ca.key -out ca.csr
# Generate Self Signed certificate（CA 根证书）
openssl x509 -req -days 365 -in ca.csr -signkey ca.key -out ca.crt
```
在实际的软件开发工作中，往往服务器就采用这种自签名的方式，因为毕竟找第三方签名机构是要给钱的，也是需要花时间的。

用户证书的生成步骤

生成私钥（.key）–>生成证书请求（.csr）–>用CA根证书签名得到证书（.crt）
```
# private key
$openssl genrsa -des3 -out server.key 1024
# generate csr
$openssl req -new -key server.key -out server.csr
# generate certificate
$openssl ca -in server.csr -out server.crt -cert ca.crt -keyfile ca.key
```
注意点

在执行$openssl ca -in server.csr -out server.crt -cert ca.crt -keyfile ca.key时可能会出错：

Using configuration from /usr/share/ssl/openssl.cfg I am unable to access the ./demoCA/newcerts directory ./demoCA/newcerts: No such file or directory

解决方法：
```
1)mkdir -p ./demoCA/newcerts
2)touch demoCA/index.txt
3)touch demoCA/serial
4)echo 01 > demoCA/serial
```
命令行：数字签名
```
To generate RSA private key, 2048 bit.
openssl genrsa -out privatekey.pem

To generate RSA public key
openssl rsa -in privatekey.pem -pubout -out publickey.pem

chage private key to pkcs8 format:
openssl pkcs8 -topk8 -inform PEM -in privatekey.pem -outform PEM -nocrypt


To create a hex-encoded message digest of a file:
openssl dgst -md5 -hex file.txt

To sign a file using SHA-256 with binary file output:
openssl dgst -sha256 -sign privatekey.pem -out signature.sign file.txt

To verify a signature:
openssl dgst -sha256 -verify publickey.pem \
 -signature signature.sign \
 file.txt
```
Read All
[算法学习][leetcode] 342 Power of Four

2017-03-03

mdgsf

Art

Leetcode
https://leetcode.com/problems/power-of-four/description/

题目

Given an integer (signed 32 bits), write a function to check whether it is a power of 4.

Example: Given num = 16, return true. Given num = 5, return false.

Follow up: Could you solve it without loops/recursion?

题目翻译

题目解析

判断一个数是不是4的幂。

参考答案
```
class Solution {
public:
    bool isPowerOfFour(int num) {

        //2 8  32 false   2=0010  8=1000        32=0010,0000
        //4 16 64 true    4=0100  16=0001,0000  64=0100,0000

        //5=0101

        if(num <= 0) return false;

        return (((num&(num-1))==0) && (num&0x55555555));
    }
};
```
Read All

[算法学习][leetcode] 326 Power of Three

2017-03-03

mdgsf

Art

Leetcode

https://leetcode.com/problems/power-of-three/description/

题目

Given an integer, write a function to determine if it is a power of three.

Follow up: Could you do it without using any loop / recursion?

题目翻译

题目解析

判断一个数是不是3的幂。

参考答案

class Solution {
public:
    bool isPowerOfThree(int n) {
        if(n <= 0) return false;

        //3 9 27 81
        //big3 % n == 0
        //big3 = 3^k
        //k = log3(maxint);
        const int maxint = 0x7fffffff;
        int k = log(maxint)/log(3);
        int big3 = pow(3, k);

        return big3 % n == 0;
    }
};

Read All

61/97

Welcome to MDGSF's Blog!

[算法学习][排列组合] N 皇后问题

用二维数组

用一维数组

[C/C++] malloc 实现

[算法学习][面试题] 2015华为校招机试

[openssl] 生成SSL证书

openssl中有如下后缀名的文件

CA根证书的生成步骤

用户证书的生成步骤

注意点

命令行：数字签名

[算法学习][leetcode] 342 Power of Four

题目

题目翻译

题目解析

参考答案

[算法学习][leetcode] 326 Power of Three

题目

题目翻译

题目解析

参考答案