C语言:杨氏矩阵、杨氏三角、单身狗1与单身狗2

简介: C语言:杨氏矩阵、杨氏三角、单身狗1与单身狗2

下面介绍四道题目和解法


1.杨氏矩阵

算法:右上角计算

题目:有一个数字矩阵,矩阵的每行从左到右是递增的,矩阵从上到下是递增的,请编写程序在这样的矩阵中查找某个数字是否存在。

要求:时间复杂度小于O(N);

代码:

#include<stdio.h>
int Find_arr(int arr[3][3],int r, int c, int k)
{
  int x = 0;
  int y = c - 1;
  while (x<r&&y>=0)
  {
    if (arr[x][y] < k)
    {
      x++;
    }
    else if (arr[x][y] > k)
    {
      y--;
    }
    else
      return 1;
  }
  return 0;
}
int main()
{
  int arr[3][3] = {1,2,3,4,5,6,7,8,9};
  int k = 0;
  printf("输入需要查找的数字:");
  scanf("%d",&k);
  int ret = 0;
  ret=Find_arr(arr,3,3,k);
  if (ret == 1)
    printf("找到了\n");
  else
    printf("找不到\n");
  return 0;
}

【关键代码部分解析】

杨氏矩阵的特点:矩阵的每行从左到右是递增的,矩阵从上到下是递增的

代码思路:从右上角或者左下角开始遍历,我们这里从右上角开始

假设要找的值是5

第一次遍历:与右上角的元素比较,也就是与3比较。

第二次遍历:与4比较。

第三次遍历:与5比较,相等,得出结果。

【第二种代码】

要求找到了并且返回该元素的下标:

返回双参数代码写法:

#include<stdio.h>
#include<assert.h>
int Find_arr(int arr[3][3], int* px, int* py, int k)
{
  assert(px&&py);
  int x = 0;
  int y = *py-1;
  while (x<*px&&*py>=0)
  {
    if (arr[x][y] < k)
    {
      x++;
    }
    else if (arr[x][y] > k)
    {
      y--;
    }
    else
    {
      *px = x;
      *py = y;
      return 1;
    }
      
  }
  *px = -1;
  *py = -1;
  return 0;
}
int main()
{
  int arr[3][3] = { 1,2,3,4,5,6,7,8,9 };
  int k = 0;
  printf("输入需要查找的数字:");
  scanf("%d", &k);
  int ret = 0;
  int x = 3;
  int y = 3;
  ret = Find_arr(arr, &x,&y, k);
  if (ret == 1)
  {
    printf("找到了\n");
    printf("下标是:%d %d\n", x, y);
  }
  else
  {
    printf("找不到\n");
    printf("下标是:%d %d\n", x, y);
  }
  return 0;
}

返回双参数思路:

将下标的地址作为参数,不需要返回两个下标即可达到带回参数的目的。

2.杨辉三角

我们想要打印出下面的图案,并且符号性质,需要怎么做呢?

(1)图形讲解

我们可以创建一个二维数组,刚开始都赋值0。

然后可以打印出下半部分就行。

代码:

#include<stdio.h>
int main()
{
  int arr[10][10] = { 0 };//创建二维数组并初始化成0
  //打印下半部分
  int i = 0;
  for (i=0;i<10;i++)
  {
    int j = 0;
    for (j=0;j<=i;j++)//打印三角形的关键
    {
      printf("%d ",arr[i][j]);
    }
    printf("\n");
  }
  return 0;
}

运行结果:

(2)赋值讲解

现在知道了杨辉三角的形状是怎么样打印出来的,接下来需要对其赋值,成为真正的杨辉三角。

杨辉三角:从第三行和第二列开始,每个数字的值=其上方的数字+左上角的数字 (空白的默认为0),其他部分默认赋值1。

代码:

#include<stdio.h>
int main()
{
  int arr[10][10] = { 0 };//创建二维数组并初始化成0
  //对杨辉三角赋值(二维数组)
  int i = 0;
  for (i = 0; i < 10; i++)
  {
    int j = 0;
    for (j = 0; j <= i; j++)
    {
      if (j == 0 || i == j)
        arr[i][j] = 1;
      if (i >= 2 && j >= 1)//第三行和第二列开始
        //关系
        arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];
    }
  }
  //打印下半部分
  i = 0;
  for (i=0;i<10;i++)
  {
    int j = 0;
    for (j=0;j<=i;j++)//打印三角形的关键
    {
      printf("%5d ",arr[i][j]);
    }
    printf("\n");
  }
  return 0;
}

运行结果:

赋值解析:

其实这就是杨辉三角了,要是打出类似等腰三角形的性质,则需要控制打印的格式,属于打印的知识,这里暂时不介绍

等腰三角的杨辉三角:暂时不做解析

#include<stdio.h>
int main()
{
  int arr[10][10] = { 0 };
  //初始化
  int i = 0;
  for (i = 0; i < 10; i++)
  {
    int j = 0;
    for (j = 0; j <= i; j++)
    {
      if (j == 0 || i == j)
        arr[i][j] = 1;
      if (i >= 2 && j >= 1)//第三行和第二列开始
        arr[i][j] = arr[i - 1][j - 1] + arr[i - 1][j];
    }
  }
  //打印
  i = 0;
  int k = 10;
  for (i = 0; i < 10; i++)
  {
    for (int k = 0; k < 26 - (6 * i / 2); k++)//打印一行前面的空格
    {
      printf(" ");
    }
    int j = 0;
    for (j = 0; j <= i; j++)
    {
      printf("%5d ", arr[i][j]);
    }
    printf("\n");
  }
  return 0;
}

运行结果:

3.单身狗1

题目:一个数组中只有一个数字单独出现,其他的数字都成对出现,请找出这个单身狗

如:1,2,3,4,5,1,2,3,4,只有5只出现了一次,所以需要找出5

【思路】

(1)利用异或操作符^:(二进制对应位)相同为0,相异为1。

(2)如:a^a=0,a^0=0。

(3)并且支持交换律,所以我们可以将所有的数据和0异或在一起,最终的结果就是“单身狗”。

代码解法:

#include<stdio.h>
int Find_dog_arr(int arr[],int sz)
{
  int tmp = 0;
  int i = 0;
  for (i = 0; i < sz; i++)
  {
    tmp = tmp ^ arr[i];//全部异或在一起
  }
  return tmp;
}
int main()
{
  int arr[] = { 1,2,3,4,5,1,2,3,4 };
  int sz = sizeof(arr) / sizeof(arr[0]);
  int ret=Find_dog_arr(arr,sz);
  printf("%d\n",ret);
  return 0;
}

tmp的最终结果就是5。

4.单身狗2

题目:

一个数组中只有两个数字是出现一次,其他所有数字都出现了两次。

编写一个函数找出这两个只出现一次的数字。

例如:

有数组的元素是:1,2,3,4,5,1,2,3,4,6

只有5和6只出现1次,要找出5和6。

【思路】

(1)这是单身狗1的升级版,显然直接异或是不行的。

(2)所以我们可以先进行分类,将两个单身狗分在两个不同的组,再进行异或操作。

(3)怎么分类:找出分类依据。

  利用异或操作分类,将所有数字异或起来的结果其实就是两个单身狗异或起来的结果;再根据结果的二进制,也就是根据某一位二进制是否为1进行分类。(两个单身狗肯定有不同的二进制位,结果肯定为1)

【分类操作】

void Find_dog2_arr(int arr[], int sz, int* p1, int* p2)
{
  int tmp = 0;
  int i = 0;
  //1.全部异或在一起,结果为两个单身狗异或在一起的结果
  for (i = 0; i < sz; i++)
  {
    tmp ^= arr[i];
  }
  //2.找出分组的依据
  i = 0;
  int r = 0;
  for (i = 0; i < 32; i++)
  {
    r = arr[i];
    if ((tmp >> i) & 1 == 1)
    {
      r = i;
    }
  }
}

(1)tmp是两个单身狗异或在一起的结果

(2)(tmp>>i)&1==1的意思是找出tmp的二进制位为1的位,也就是分组的关键

【思路刨析】

【整体代码】

#include<stdio.h>
void Find_dog2_arr(int arr[], int sz, int* p1, int* p2)
{
  int tmp = 0;
  int i = 0;
  //1.全部异或在一起,结果为两个单身狗异或在一起的结果
  for (i = 0; i < sz; i++)
  {
    tmp ^= arr[i];
  }
  //2.找出分组的依据
  i = 0;
  int r = 0;
  for (i = 0; i < 32; i++)
  {
    r = arr[i];
    if ((tmp >> i) & 1 == 1)
    {
      r = i;
    }
  }
  //3.分组
  int u1 = 0;
  int u2 = 0;
  for (i = 0; i < sz; i++)
  {
    if ((arr[i] >> r) & 1 == 1)//按位与
    {
      u1 ^= arr[i];
    }
    else
    {
      u2 ^= arr[i];
    }
  }
  *p1 = u1;
  *p2 = u2;
}
int main()
{
  int arr[] = { 1,2,3,4,5,1,2,3,4,10 };
  int sz = sizeof(arr) / sizeof(arr[0]);
  int s1 = 0;
  int s2 = 0;
  Find_dog2_arr(arr, sz, &s1, &s2);
  printf("单身狗1:%d\n单身狗2:%d", s1, s2);
  return 0;
}

相关文章
|
14天前
|
C语言
C语言——oj刷题——找单身狗1
C语言——oj刷题——找单身狗1
|
14天前
|
C语言
C语言——oj刷题——找单身狗2
C语言——oj刷题——找单身狗2
14 0
|
14天前
|
算法 C语言
C语言——oj刷题——杨氏矩阵
C语言——oj刷题——杨氏矩阵
|
30天前
|
C语言
C语言进阶21收尾(编程练习)(atoi,strncpy,strncat,offsetof模拟实现+找单身狗+宏交换二进制奇偶位)(下)
C语言进阶21收尾(编程练习)(atoi,strncpy,strncat,offsetof模拟实现+找单身狗+宏交换二进制奇偶位)
24 0
|
30天前
|
C语言
C语言进阶21收尾(编程练习)(atoi,strncpy,strncat,offsetof模拟实现+找单身狗+宏交换二进制奇偶位)(上)
C语言进阶21收尾(编程练习)(atoi,strncpy,strncat,offsetof模拟实现+找单身狗+宏交换二进制奇偶位)
60 0
|
30天前
|
算法 C语言
C语言进阶⑫(指针下)(指针和数组笔试题解析)(杨氏矩阵)(下)
C语言进阶⑫(指针下)(指针和数组笔试题解析)(杨氏矩阵)
11 0
|
30天前
|
C语言
C语言进阶⑫(指针下)(指针和数组笔试题解析)(杨氏矩阵)(中)
C语言进阶⑫(指针下)(指针和数组笔试题解析)(杨氏矩阵)
25 0
|
30天前
|
C语言
C语言进阶⑫(指针下)(指针和数组笔试题解析)(杨氏矩阵)(上)
C语言进阶⑫(指针下)(指针和数组笔试题解析)(杨氏矩阵)
26 0
|
1月前
|
机器学习/深度学习 存储 C语言
【C语言】找单身狗问题
【C语言】找单身狗问题
21 0
|
1月前
|
C语言
C语言--杨氏矩阵
C语言--杨氏矩阵
14 0