程序员面试金典(二)C实现

像素反转

题目描述
有一副由NxN矩阵表示的图像，这里每个像素用一个int表示，请编写一个算法，在不占用额外内存空间的情况下(即不使用缓存矩阵)，将图像顺时针旋转90度。

给定一个NxN的矩阵，和矩阵的阶数N,请返回旋转后的NxN矩阵,保证N小于等于500，图像元素小于等于256。

测试样例：
[[1,2,3],[4,5,6],[7,8,9]],3
返回：[[7,4,1],[8,5,2],[9,6,3]]
此题最开始的实现是申请一个大小为N的数组，然后将第一行保存到中间数组，然后将第一列拷贝到第一行，然后将最后一行拷贝到第一列，然后再将最右边一列拷贝到最下一行，然后再把数组N中的值拷贝到最右一列，本题的唯一难度是下标运算，代码中添加了相应打印，能够清晰表示赋值过程。
下面的代码实现采用了一种较为巧妙的方式，无需中间数组，空间复杂度为O(1)

//
//  main.c
//  ctciprog
//
//  Created by 王传伟 on 2018/1/28.
//  Copyright © 2018年 王传伟. All rights reserved.
//

#include <stdio.h>
void rotate(int n,int (*arr)[n])
{
    for(int row = 0; row < n/2;row++)
    {
        for(int i = row;i < n-1-row;i++)
        {
            /*保存左上角的值*/
            int top = arr[row][i];
            /*左下-->左上*/
            arr[row][i] = arr[n-1-i][row];
            printf("[%d][%d] -->[%d][%d]\n",n-1-i,row,row,i);
            /*右下-->左下*/
            arr[n-1-i][row]=arr[n-1-row][n-1-i];
            printf("[%d][%d] -->[%d][%d]\n",n-1-row,n-1-i,n-1-i,row);
            /*右上-->右下*/
            arr[n-1-row][n-1-i]= arr[i][n-1-row];
            printf("[%d][%d] -->[%d][%d]\n",i,n-1-row,n-1-row,n-1-row);
            /*左上-->右上*/
            arr[i][n-1-row]= top;
            printf("[%d][%d] -->[%d][%d]\n",row,i,i,n-1-row);
        }
    }
    
}
void printarr(int n,int arr[n][n])
{
    for(int i= 0;i<n;i++)
    {
        for(int j=0;j<n;j++)
        {
            printf("%2d ",arr[i][j]);
        }
        printf("\n");
    }
}
int main(int argc, const char * argv[])
{
    int arr[3][3]={1,2,3,4,5,6,7,8,9};
    rotate(3,arr);
    printarr(3,arr);
    
    int str[4][4]={{1,2,3,4},{5,6,7,8},{9,10,11,12},{13,14,15,16}};
    rotate(4,str);
    printarr(4,str);
    
    int cool[5][5]={{1,2,3,4,5},{6,7,8,9,10},{11,12,13,14,15},{16,17,18,19,20},{21,22,23,24,25}};
    rotate(5,cool);
    printarr(5,cool);
    
    return 0;
}

清除行列

题目描述
请编写一个算法，若N阶方阵中某个元素为0，则将其所在的行与列清零。
测试样例：[[1,2,3],[0,1,2],[0,0,1]]
返回：[[0,0,3],[0,0,0],[0,0,0]]
此题书上说有空间复杂度小于O(MN)的算法，书上的例子还是老老实实的申请了两个数组，跟下面的实现并无差别。

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
void printarr(int m,int n,int arr[n][n])
{
    for(int i= 0;i<m;i++)
    {
        for(int j=0;j<n;j++)
        {
            printf("%5d ",arr[i][j]);
        }
        printf("\n");
    }
    printf("\n");
}
void clearzero(int m,int n,int (*str)[n])
{
    /*定义两个一维数组标识保存该行/列是否有零*/
    bool *row = (bool *)malloc(m * sizeof(bool));
    bool *col = (bool *)malloc(n * sizeof(bool));
    /*初始化*/
    /*此处如果不添加memset程序将出现错误*/
    memset(row, 0x0, m);
    memset(col, 0x0, n);
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            if(str[i][j] == 0)
            {
                row[i] = true;
                col[j] = true;
            }
        }
    }
    
    for(int i = 0; i < m; i++)
    {
        for(int j = 0; j < n; j++)
        {
            /*当前元素所在行/列为0，置元素为0*/
            if(row[i] || col[j])
            {
                str[i][j] = 0;
            }
        }
    }
    /*释放已申请内存*/
    free(row);
    row = NULL;
    
    free(col);
    col = NULL;
}
int main(int argc, const char * argv[])
{
    
    int str[3][3] = {{1,2,3},{0,1,2},{0,0,1}};
    clearzero(3,3,str);
    printarr(3,3,str);
    
    int cool[5][3] = {{1,2,3},{1,1,2},{0,2,1},{1,2,0},{2,3,4}};
    clearzero(5,3,cool);
    printarr(5,3,cool);
    
    return 0;
}

反转子串

题目描述
假定我们都知道非常高效的算法来检查一个单词是否为其他字符串的子串。请将这个算法编写成一个函数，给定两个字符串s1和s2，请编写代码检查s2是否为s1旋转而成，要求只能调用一次检查子串的函数。

给定两个字符串s1,s2,请返回bool值代表s2是否由s1旋转而成。字符串中字符为英文字母和空格，区分大小写，字符串长度小于等于1000。

测试样例：
"Hello world","worldhello "
返回：false
"waterbottle","erbottlewat"
返回：true
算法原理：
因为字符串是翻转过的，但是除了翻转点之外，其余的字母都是保留了原有的顺序，因此，我们假设xy为原串，那么翻转后的结果为yx，那么要证明yx是否由xy翻转过来？必然有yx是xyxy的子串，只要符合这点就可以知道yx由xy翻转过来。
具体的例子，以上面的测试样例：x是wat y是erbottle，反转后的字符串为yx为erbottlewat，如果要证明yx是否xy翻转的，只用证明yx是xyxy的子串，只要符合就可以证明yx由xy反转的。

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>
bool checkReverseEqual(char *src,char *dst)
{  
    /*src字符串长度*/
    unsigned long srclen = strlen(src);
    /*dst字符串长度*/
    unsigned long dstlen = strlen(dst);
    
    char *begin = NULL;
    if((srclen != dstlen)|| (srclen==0) ||(dstlen == 0))
        return false;
    /*多申请一个char，保存'\0'*/
    char *set = malloc((2 * srclen + 1) * sizeof(char));
    memset(set, 0x0, 2 * srclen + 1);
    /*假设src中字符串能按照xy模式反转成dst,set中保存的是xyxy*/
    snprintf(set, 2 * srclen + 1,"%s%s",src,src);

    begin = strstr(set,dst);
    if(begin == NULL)
    {
        /*释放分配的内存*/
        free(set);
        set = false;
        return false;
        
    }
    
    /*释放分配的内存*/
    free(set);
    set = false;
    return true;
}

int main(int argc, const char * argv[])
{
    char str1[100]="Helloworld";
    char str2[100]="Helloworld";
    printf("%d\n",checkReverseEqual(str1,str2));
    
    char str3[100]="worldHello";
    char str4[100]="Helloworld";
    printf("%d\n",checkReverseEqual(str3,str4));
    
    /*长度不一致*/
    char str5[100]="worldHelloworld";
    char str6[100]="Helloworld";
    printf("%d\n",checkReverseEqual(str5,str6));
    
    /*存在空串*/
    char str7[100]="worldHelloworld";
    char str8[100]="";
    printf("%d\n",checkReverseEqual(str7,str8));
    
    char str9[11]="worldHello";
    char str10[11]="Helloworld";
    printf("%d\n",checkReverseEqual(str9,str10));
    return 0;
}

链表中倒数第k个节点

题目描述
输入一个链表，输出该链表中倒数第k个结点。
单链表C 实现链表操作-C语言实现

//
//  main.c
//  ctciprog
//
//  Created by 王传伟 on 2018/1/31.
//  Copyright © 2018年 王传伟. All rights reserved.
//

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

typedef int ElemType;

/*定义结构体*/
typedef struct LNode
{
    struct LNode *next;
    ElemType num;
}LNode;

/*链表初始化*/
void initList(LNode ** head)
{
    if((*head = (LNode *)malloc(sizeof(LNode))) != NULL)
    {
        (*head)->next = NULL;
    }
}

/*打印链表中的全部元素*/
void printList(LNode *head)
{  
   if(head == NULL)
        return;
 /*每10个元素打印一行*/
    int cnt = 0;
    LNode *p = head;
    while(p->next != NULL)
    {
        p = p->next;
        printf("%d ",p->num);
        if(cnt % 9 == 0)
            printf("\n");
    }
        
}

/*求链表中元素的个数*/
int ListLength(LNode *head)
{
    int length = 0;
    /*指针p指向头节点*/
    LNode *p = head;
    while(p->next != NULL)
    {
        length += 1;
        p = p->next;
    }
    
    return length;
}
/*插入成功return 1,失败return 0*/
/*i代表第i个元素后插入节点，节点num为x*/
int ListInsert(LNode *head,int i,ElemType x)
{
    LNode *p,*q;
    p = head;
    int j = -1;
    while((p->next != NULL)&&(j < i-1))
    {
        p = p->next;
        j += 1;
    }
    /*插入位置非法*/
    if(j!=i-1)
        return 0;
    if((q = (LNode *)malloc(sizeof(LNode))) == NULL)
    {
        /*分配内存失败*/
        printf("Malloc memory failed.\n");
        return 0;
    }
    /*x赋值*/
    q->num = x;
    
    /*插入到正确位置*/
    q->next = p->next;
    p->next = q;
    /*插入成功*/
    return 1;
}
/*删除链表中第i+1个元素，x保存删除节点的num*/
int ListDel(LNode *head,int i,ElemType *x)
{
    LNode *p = head;
    LNode *s = NULL;
    int j = -1;
    while((p->next != NULL)&&(j < i-1))
    {
        p = p->next;
        j++;
    }
    
    /*插入位置非法*/
    if(j != i-1)
        return 0;
    
    /*s指向待删元素*/
    s = p->next;
    /*待删除元素由x带回*/
    *x = s->num;
    p->next = p->next->next;
    
    /*释放待删除元素*/
    free(s);
    s = NULL;
    return 1;
}

/*销毁整个链表*/
void destoryList(LNode *head)
{
    LNode *p = head;
    LNode *s = NULL;
    if(head == NULL)
        return;
    while(p->next != NULL)
    {
        s = p->next;
        p->next = p->next->next;
        free(s);
        s = NULL;
    }
    
}
/*函数用于验证链表基本操作是否正确*/
void checkListValid()
{
    LNode *head = NULL;
    ElemType x = 0;
    /*链表初始化*/
    initList(&head);
    if(head == NULL)
        printf("Error.\n");
    
    /*元素个数为0*/
    if(ListLength(head) != 0)
        printf("Error.\n");
    
    /*插入10个元素*/
    for(int i = 0;i < 10;i++)
    {
        if(0 == ListInsert(head, i, i+1))
            printf("Error.\n");
    }
    destoryList(head);
    /*元素个数为0*/
    if(ListLength(head) != 0)
        printf("Error.\n");
    
    
    /*链表中无元素，删除元素非法*/
    if(ListDel(head,1,&x) != 0)
        printf("Error.\n");
    
    /*插入10个元素*/
    for(int i = 0;i < 10;i++)
    {
        if(0 == ListInsert(head, i, i+1))
            printf("Error.\n");
    }

    printList(head);
    
    /*删除10个元素*/
    for(int i = 0;i < 10;i++)
    {
        if(1 != ListDel(head, 0, &x)|| (x != i+1))
            printf("Error.\n");
    }
    printList(head);
    
    /*插入10个元素*/
    for(int i = 0;i < 10;i++)
    {
        if(0 == ListInsert(head, i, i+1))
            printf("Error.\n");
    }
    /*删除第4个元素，num为4*/
    if(1 != ListDel(head, 3, &x)|| (x != 4))
        printf("Error.\n");
    
    /*插入元素4，位置4*/
    if(0 == ListInsert(head, 3, 4))
        printf("Error.\n");
    
    printf("\n");
    printList(head);
    
    /*删除最后一个元素*/
    if(1 != ListDel(head, 9, &x)|| (x != 10))
        printf("Error.\n");
    
    /*删除最后一个元素8*/
    if(1 != ListDel(head, 8, &x)|| (x != 9))
        printf("Error.\n");
    
    /*删除第三个元素3*/
    if(1 != ListDel(head, 2, &x)|| (x != 3))
        printf("Error.\n");
    
    printf("\n");
    printList(head);
    
    /*销毁链表*/
    destoryList(head);
    
    printf("\n");
    printList(head);
}

/*找出单链表中倒数第k个节点*/
LNode * nthToLast(LNode *head,int k)
{
    LNode *ans = head;
    LNode *end = head;
    /*k小于0或链表长度小于k犯错*/
    if((k<= 0)||(ListLength(head)<k))
        return NULL;
    /*让end向前移动k个节点*/
    for(int i = 0;i < k-1;i++)
    {
        /*此处应该不用判断，因为前面有判断链表长度*/
        if(end == NULL)
            return NULL;
        end = end->next;
    }
    /*end指向最后时，ans恰好指向倒数第k个结点*/
    while((ans->next != NULL)&&(end->next != NULL))
    {
        ans = ans->next;
        end = end->next;
    }
    
    return ans;
}
int main(int argc, const char * argv[])
{
    
    //checkListValid();
    LNode *head = NULL;
    LNode *kthnode = NULL;
    /*链表初始化*/
    /*链表基本功能验证在checkListValid函数中*/
    initList(&head);

    /*插入10个元素*/
    for(int i = 0;i < 10;i++)
    {
        if(0 == ListInsert(head, i, i+1))
            printf("Error.\n");
    }
    /*验证函数基本功能*/
    for(int j = 1;j <= 10;j++)
    {
        kthnode = nthToLast(head, j);
        printf("%d\n",kthnode->num);
        kthnode = NULL;
    }
    /*验证异常情况*/
    kthnode = nthToLast(head, 0);
    if(kthnode != NULL)
       printf("Error.\n");
    
    /*验证异常情况*/
    kthnode = nthToLast(head, 11);
    if(kthnode != NULL)
        printf("Error.\n");
    
    /*销毁链表*/
    destoryList(head);
    return 0;
}

访问单个结点的删除

实现一个算法，删除单向链表中间的某个结点，假定你只能访问该结点。

给定带删除的节点，请执行删除操作，若该节点为尾节点，返回false，否则返回true

//
//  main.c
//  ctciprog
//
//  Created by 王传伟 on 2018/1/31.
//  Copyright © 2018年 王传伟. All rights reserved.
//

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

typedef int ElemType;

/*定义结构体*/
typedef struct LNode
{
    struct LNode *next;
    ElemType num;
}LNode;

/*链表初始化*/
void initList(LNode ** head)
{
    if((*head = (LNode *)malloc(sizeof(LNode))) != NULL)
    {
        (*head)->next = NULL;
    }
}

/*求链表中元素的个数*/
int ListLength(LNode *head)
{
    int length = 0;
    /*指针p指向头节点*/
    LNode *p = head;
    while(p->next != NULL)
    {
        length += 1;
        p = p->next;
    }
    
    return length;
}
/*插入成功return 1,失败return 0*/
/*i代表第i个元素后插入节点，节点num为x*/
int ListInsert(LNode *head,int i,ElemType x)
{
    LNode *p,*q;
    p = head;
    int j = -1;
    while((p->next != NULL)&&(j < i-1))
    {
        p = p->next;
        j += 1;
    }
    /*插入位置非法*/
    if(j!=i-1)
        return 0;
    if((q = (LNode *)malloc(sizeof(LNode))) == NULL)
    {
        /*分配内存失败*/
        printf("Malloc memory failed.\n");
        return 0;
    }
    /*x赋值*/
    q->num = x;
    
    /*插入到正确位置*/
    q->next = p->next;
    p->next = q;
    /*插入成功*/
    return 1;
}
/*删除链表中第i+1个元素，x保存删除节点的num*/
int ListDel(LNode *head,int i,ElemType *x)
{
    LNode *p = head;
    LNode *s = NULL;
    int j = -1;
    while((p->next != NULL)&&(j < i-1))
    {
        p = p->next;
        j++;
    }
    
    /*插入位置非法*/
    if(j != i-1)
        return 0;
    
    /*s指向待删元素*/
    s = p->next;
    /*待删除元素由x带回*/
    *x = s->num;
    p->next = p->next->next;
    
    /*释放待删除元素*/
    free(s);
    s = NULL;
    return 1;
}

/*销毁整个链表*/
void destoryList(LNode *head)
{
    LNode *p = head;
    LNode *s = NULL;
   if(head == NULL)
        return;    
    while(p->next != NULL)
    {
        s = p->next;
        p->next = p->next->next;
        free(s);
        s = NULL;
    }
    
}

/*打印链表中的全部元素*/
void printList(LNode *head)
{
   if(head == NULL)
        return;
    /*每10个元素打印一行*/
    int cnt = 0;
    LNode *p = head;
    while(p->next != NULL)
    {
        p = p->next;
        printf("%d ",p->num);
        if(cnt % 9 == 0)
            printf("\n");
    }
    
}

/*函数用于验证链表基本操作是否正确*/
void checkListValid()
{
    LNode *head = NULL;
    ElemType x = 0;
    /*链表初始化*/
    initList(&head);
    if(head == NULL)
        printf("Error.\n");
    
    /*元素个数为0*/
    if(ListLength(head) != 0)
        printf("Error.\n");
    
    /*插入10个元素*/
    for(int i = 0;i < 10;i++)
    {
        if(0 == ListInsert(head, i, i+1))
            printf("Error.\n");
    }
    destoryList(head);
    /*元素个数为0*/
    if(ListLength(head) != 0)
        printf("Error.\n");
    
    
    /*链表中无元素，删除元素非法*/
    if(ListDel(head,1,&x) != 0)
        printf("Error.\n");
    
    /*插入10个元素*/
    for(int i = 0;i < 10;i++)
    {
        if(0 == ListInsert(head, i, i+1))
            printf("Error.\n");
    }

    printList(head);
    
    /*删除10个元素*/
    for(int i = 0;i < 10;i++)
    {
        if(1 != ListDel(head, 0, &x)|| (x != i+1))
            printf("Error.\n");
    }
    printList(head);
    
    /*插入10个元素*/
    for(int i = 0;i < 10;i++)
    {
        if(0 == ListInsert(head, i, i+1))
            printf("Error.\n");
    }
    /*删除第4个元素，num为4*/
    if(1 != ListDel(head, 3, &x)|| (x != 4))
        printf("Error.\n");
    
    /*插入元素4，位置4*/
    if(0 == ListInsert(head, 3, 4))
        printf("Error.\n");
    
    printf("\n");
    printList(head);
    
    /*删除最后一个元素*/
    if(1 != ListDel(head, 9, &x)|| (x != 10))
        printf("Error.\n");
    
    /*删除最后一个元素8*/
    if(1 != ListDel(head, 8, &x)|| (x != 9))
        printf("Error.\n");
    
    /*删除第三个元素3*/
    if(1 != ListDel(head, 2, &x)|| (x != 3))
        printf("Error.\n");
    
    printf("\n");
    printList(head);
    
    /*销毁链表*/
    destoryList(head);
    
    printf("\n");
    printList(head);
}

/*找出单链表中倒数第k个节点*/
LNode * nthToLast(LNode *head,int k)
{
    LNode *ans = head;
    LNode *end = head;
    /*k小于0或链表长度小于k犯错*/
    if((k<= 0)||(ListLength(head)<k))
        return NULL;
    /*让end向前移动k个节点*/
    for(int i = 0;i < k-1;i++)
    {
        /*此处应该不用判断，因为前面有判断链表长度*/
        if(end == NULL)
            return NULL;
        end = end->next;
    }
    /*end指向最后时，ans恰好指向倒数第k个结点*/
    while((ans->next != NULL)&&(end->next != NULL))
    {
        ans = ans->next;
        end = end->next;
    }
    
    return ans;
}

/*删除单链表中第k个结点，限制条件只能访问第k个结点，不能删除第k个结点*/
bool deleteNode(LNode *head,int k)
{
    if((NULL == head)||(head->next == NULL))
        return false;
    /*指向要删除的结点*/
    LNode *ans = head;
    LNode *ans_next = head->next;
    int len = ListLength(head);
    /*长度不符合限制返回false*/
    if((k <= 0)||(k>len))
        return false;
    /*区分是否删除最后一个结点，如果删除最后一个结点，则只用置ans->next = NULL*/
    while(k>0 &&(ans->next != NULL)&&(ans_next->next != NULL))
    {
        ans = ans->next;
        ans_next = ans_next->next;
        k -= 1;
    }
    
    if(k == 0)
    {
        /*删除结点不是最后一个结点，将后一个结点的内容拷贝到ans->num,删除ans_next*/
        ans->num = ans_next->num;
        ans->next = ans_next->next;
        free(ans_next);
        ans_next = NULL;
    }
    else
    {
        /*删除的是最后一个元素*/
        free(ans_next);
        ans->next = NULL;
    }
    return true;
    
}

int main(int argc, const char * argv[])
{
    
    //checkListValid();
    LNode *head = NULL;
    /*链表初始化*/
    initList(&head);
    
    /*插入10个元素*/
    for(int i = 0;i < 10;i++)
    {
        if(0 == ListInsert(head, i, i+1))
            printf("Error.\n");
    }
    /*删除第最后一个元素10*/
    deleteNode(head,10);
    printList(head);
    
    /*删除第一个元素1*/
    deleteNode(head,1);
    printList(head);
    destoryList(head);
    return 0;
}