找凶手，定名次，字符串旋转，杨氏矩阵

1.找凶手问题：

//题目名称：
//猜凶手
//题目内容：
//日本某地发生了一件谋杀案，警察通过排查确定凶手必为4个嫌疑犯的一个。
//以下为4个嫌疑犯的供词：
//A说：不是我
//B说：是C
//C说：是D
//D说：C在胡说
//已知3个人说的是真话，1个人说的是假话。
//请根据这些信息，写一个程序来确定到底谁是凶手
代码实现：

#include<Stdio.h>
int main()
{
    char killer = 0;
    for(killer = 'a';killer<='d';killer++)//循环，将每个人都假设为一次凶手
    {
        if((killer!='a') + (killer=='c') + (killer=='d') + (killer!='d') ==3 )//有三个人说了真话，一个人说了假话，那么四句话加起来的结果应该是3（解题关键！！！）
        {
         printf("killer = %c\n",killer);//只有c满足以上条件，所以只有c是凶手
        }
    }
}

2.定名次：

//解题思路：穷举法，列出每一种可能后再筛选
#include<stdio.h>
int main()
{
    int a = 0;
    int b = 0;
    int c = 0;
    int d = 0;
    int e = 0;
    for(a = 1;a<=5;a++)
    {
        for(b = 1;b <= 5;b++)
        {
            for(c = 1;c<=5;c++)
            {
                for(d = 1;d<=5;d++)
                {
                    for(e = 1;e<=5;e++)
                    {
                         if((b==2)+(a==3)==1&&(b==2)+(e==4)==1&&(c==1)+(d==2)==1&&(c==5)+(d==3)==1&&(e==4)+(a==1)==1)//每个人的话都有一半是真的，所以每个人的两句话变为条件加起来的结果是1，且5个人的话都要实现
                         {
                             if(a*b*c*d*e==120)//必须满足5个人的名次的乘积为120，否则就出现并列的情况，不符合题目条件
                             {
                                 printf("a=%d b=%d c=%d d=%d e=%d\n",a,b,c,d,e);
                             }
                         }
                    }    
                }
            }
        }
    }
    
    
    
}

3.字符串旋转

//【题目名称】

//字符串左旋

//【题目内容】

//实现一个函数，可以左旋字符串中的k个字符。

//例如：

//ABCD左旋一个字符得到BCDA

//ABCD左旋两个字符得到CDAB

//方法1：暴力解题法
//解题思路：假设字符串为"abcdef",要实现1个左旋，则先把a提出来放到临时变量中，再把剩下的字符往前移动1个位置，最后再把最后一个字符的位置放上a，
//左旋2个，3个则依此类推

/*#include<stdio.h>
#include<string.h>
char* is_left_move(char*str,int k,int sz)
{
    int i = 0;
    char tmp = 0;
    for(i=0;i<k;i++)//k等于几就说明要进行几次移位
    {
        int j = 0;
        tmp = *str;//字符串的首字符，每次移位后都不一样，所以要放在循环外面
        for(j=0;j<sz-1;j++)
        {
            str[j] = str[j+1];//第一个字符取出，其余字符向前移动1位
        }
        j--;//最后一次循环结束时i++，这次++时多余的，如果不减去，则str[j+1]就变成了str[4],越界了
        str[j+1] = tmp;
    }
    
    return str;
}
int main()
{
    char arr[] = "ABCD";
    int k = 0;
    int sz = strlen(arr);
    scanf("%d",&k);//左旋k个字符
    is_left_move(arr,k,sz);//将arr与k传入函数
    printf("%s\n",arr);
    return 0;
}*/

4.【题目名称】

字符串旋转结果

【题目内容】

写一个函数，判断一个字符串是否为另外一个字符串旋转之后的字符串。

例如：给定s1 =AABCD和s2 = BCDAA，返回1

给定s1=abcd和s2=ACBD，返回0.

AABCD左旋一个字符得到ABCDA

AABCD左旋两个字符得到BCDAA

AABCD右旋一个字符得到DAABC

//解题思路：利用strncat函数（字符串拼接函数），将arr自身拷贝一份，然后再利用字符串查找函数strstr(找得到就返回子串的首字符地址,找不到就返回NULL)即可
#include<stdio.h>
#include<string.h>
int is_left_move(char*str1,char*str2)
{
    int len1 = strlen(str1);
    int len2 = strlen(str2);
    if(len1!=len2)//先判断两个字符串的长度是否相等，如果不想等，则一定不是子串
    {
        return 0;
    }
    strncat(str1,str1,6);//给arr1后面再加个arr1
    char*cy = strstr(str1,str2);//指针接收strstr返回的地址，若strstr没找到，则返回空指针，则说明不是子串
    if(cy==NULL)
    {
        return 0;
    }
    else
    return 1;
    
    
    
    
    
    
}
int main()
{
    char arr1[] = "ABCDEF";
    char arr2[] = "DEFABC";
    int ret = is_left_move(arr1,arr2);//将两个数组传到函数里面，返回值设置为整数
    if(ret == 1)
    {
        printf("Yes\n");//是子串
    }
    if(ret == 0)
    {
        printf("No\n");//不是子串
    }
}

5.1//题目名称：
//杨氏矩阵
//题目内容：
//有一个数字矩阵，矩阵的每行从左到右是递增的，矩阵从上到下是递增的，请编写程序在这样的矩阵中查找某i个数字不是矩阵中的数字
//要求：时间复杂度小于o（N）

//时间复杂度小于o（N）
//假设矩阵为：
//1 2 3
//3 4 5
//4 5 6
//想要找到数字6，那么至少得把数组遍历，则需要找9次，此时o（N）就等于9，所以这种算法不满足要求

//解题思路：观察矩阵的右上角数字3，是一行中最大的数，也是一列中最小的数，假设给一个数字k，若3<k,则一行中没有比k更大的数
//则跳到下一行，若3>k，则说明一列中没有比k更小的数，则跳到前一列，左下角的数字也可以以此类推

//1.利用右上角数字的解法
/*#include<Stdio.h>
int find(int arr[3][3],int row,int lin,int k)
{
    int x = 0;//右上角数字的行坐标
    int y = lin-1;//右上角数字的列坐标
    while(x<=2&&y>=0)//行坐标必须<=2(三行)，列坐标必须>=0
    {
            if(arr[x][y]<k)
    {
        x++;
    }
    else if(arr[x][y]>k)
    {
        y--;
    }
    else
    {
    return 1;    
    }
    
    }
    return 0;

}
int main()
{
    //int row = 3;
    //int lin = 3;
    int arr[3][3] = {{1,2,3},{3,4,5},{4,5,6}};
    int k = 0;
    scanf("%d",&k);
    int ret = find(arr,3,3,k);
    if(ret==1)
    {
        printf("找到了");
    }
    if(ret == 0 )
    {
        printf("找不到");
    }
    return 0;
}*/

5.2:

//2.利用左下角数字的解法
#include<Stdio.h>
int find(int arr[3][3],int row,int lin,int k)
{
    int x = row-1;//左下角数字的行坐标
    int y = 0;//左下角数字的列坐标
    while(x<=2&&y>=0)//行坐标必须<=2(三行)，列坐标必须>=0
    {
            if(arr[x][y]<k)
    {
        y++;
    }
    else if(arr[x][y]>k)
    {
        x--;
    }
    else
    {
    return 1;    
    }
    
    }
    return 0;

}
int main()
{
    int arr[3][3] = {{1,2,3},{3,4,5},{4,5,6}};
    int k = 0;
    scanf("%d",&k);
    int ret = find(arr,3,3,k);
    if(ret==1)
    {
        printf("找到了");
    }
    if(ret == 0 )
    {
        printf("找不到");
    }
    return 0;
}