Colico‘s Blog


『流水很清楚惜花这个责任,真的身份不过送运。这趟旅行若算开心,亦是无负这一生。』

数据结构日常刷题

0 条评论 C语言 数据结构 XuanVI

算法

1.已知一个带有表头结点的单链表,结点结构为 |data|link| 假设该链表只给出了头指针list。在不改变链表的前提下,请设计一个尽可能高效的算法,查找链表中倒数第k个位置的结点(k位正整数)。若查找成功,算法输出该结点的data域的值,并返回1;否则,只返回0.要求:
1)描述算法的基本设计思想。
2)描述算法的详细实现步骤。
3)根据设计思想和实现步骤,采用程序设计语言描述算法,关键之处请给出简要注释。
typedef int Elemtype;
typedef struct LNode {
    Elemtype      data;  //结点数据
    struct LNode* link;  //结点链表指针
} LNode, *LinkList;

int Search_k( LinkList list, int k ) {
    LNode *p = list->link, *q = list->link;  //指针p、q指向首元结点
    int    count = 0;
    while ( p != NULL ) {  //遍历链表直到最后一个结点
        if ( count < k )
            count++;  //计数,若count<k只移动p
        else
            q = q->link;
        p = p->link;  //让p、q同步移动
    }
    if ( count > k )
        return 0;
    else {
        printf( "%d", q->data );
        return 1;
    }
}
设置了两个距离为k-1的指针p和q,p超前q的结点数为k-1,当p遍历到链表末尾时,则q指向的就是倒数第k个结点。
2.一个长度为L(L>=1)的升序序列S,处在第L/2个位置的数称为中位数。例如,若序列S1=(11,13,15,17,19),则S1的中位数是15,两个序列的中位数是含它们所有元素的升序序列的中位数,例如,若S2=(2,4,6,8,20),则S1和S2的中位数是11.现在两个等长升序序列A和B,试设计一个在时间和空间两方面都尽可能高效的算法,找出两个序列A和B的中位数。 分别求两个升序序列A、B的中位数,设为a和b。 1)若a=b,则a或b即为所求中位数,算法结束。 2)若ab,则舍弃序列A中较大的一半,同时舍弃序列B中较小的一半,要求两次舍弃的长度相等。 在保留的两个升序序列中,重复1)、2)、3),直到两个序列中均只含有一个元素时为止,较小者即为所求的中位数。
#include <stdio.h>

int Search_mid( int A[], int B[], int n ) {
    int s1 = 0, d1 = n - 1, m1, s2 = 0, d2 = n - 1, m2;
    while ( s1 != d1 || s2 != d2 ) {
        m1 = ( s1 + d1 ) / 2;
        m2 = ( s2 + d2 ) / 2;
        if ( A[ m1 ] == B[ m2 ] )
            return A[ m1 ];                //满足条件1
        if ( A[ m1 ] < B[ m2 ] ) {         //满足条件2
            if ( ( s1 + d1 ) % 2 == 0 ) {  //若元素个数为奇数
                s1 = m1;                   //舍弃A中间点以前的部分且保留中间点
                d2 = m2;                   //舍弃B中间点以后的部分且保留中间点
            }
            else {            //元素个数为偶数
                s1 = m1 + 1;  //舍弃A中间点及中间点以前部分
                d2 = m2;      //舍弃B中间点以后部分且保留中间点
            }
        }
        else {                             //满足条件3
            if ( ( s2 + d2 ) % 2 == 0 ) {  //若元素个数为奇数
                d1 = m1;                   //舍弃A中间点以后部分且保留中间点
                s2 = m2;                   //舍弃B中间点及中间点以前部分
            }
            else {            //元素个数为偶数
                d1 = m1;      //舍弃A中间点以后部分且保留中间点
                s2 = m2 + 1;  //舍弃B中间点及中间点以前部分
            }
        }
    }
    return A[ s1 ] < B[ s2 ] ? A[ s1 ] : B[ s2 ];
}

void main() {
    int A[] = { 11, 13, 15, 17, 19 };
    int B[] = { 2, 4, 6, 8, 20 };
    printf( "%d", Search_mid( A, B, 5 ) );
}

LeeCode算法题

234.回文链表

判断一个链表是否为回文链表
实例1: 输入: 1->2
输出: false
实例2: 输入: 1->2->2->1
输出: true
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */


bool isPalindrome(struct ListNode* head){
    struct ListNode *fast = head,*slow = head,*prev = NULL;
    while(fast){
        slow = slow->next;
        fast = fast->next ? fast->next->next:fast->next;
    }
    while(slow){
        struct ListNode * temp = slow->next;
        slow->next = prev;
        prev = slow;
        slow = temp;
    }
    while(head && prev){
        if(head->val != prev->val){
            return false;
        }
        head = head->next;
        prev = prev->next;
    }
    return true;
}

逆さまの蝶

2 条评论 默认分类 歌词 XuanVI


作词 SNoW/山野英明
作曲 SNoW/进藤安三津
编曲 进藤安三津/藤田谦一
歌手 SNoW

いつか光(ひかり)に向(む)かう 逆(さか)さまの蝶(ちょう)
itsuka hikari ni mukau sakasama no chou

君(きみ)と髪(かみ)を切(き)る 镜(かがみ)の中(なか)
kimi to kami wo kiru kagami no naka

授业中(じゅぎょう)の廊下(ろうか) 响(ひびく)く足音(あしおと)
jyugyou chuu no rouka hibiku ashioto

绝(て)えず雨(あめ)の音(おと)がついてくるよ
taezu ame no otoga tsuite kuruyo

感(かん)じるままの形(かたち)は眩(まぶ)しい
kanjiru mama no katachi wa mabushii

甘(あま)い花(はな)になる 毒(どく)の実(み)にもなる
amai hana ni naru doku no mi ni mo naru

今日(きょう)も雨(あめ) あの日(ひ)と今(いま)を
kyou mo ame ano hito ima wo

空(そら)と空(そら)でつなぎたいの
sora to sora de tsunagitai no

In this Craziness, Uncertainty
一人一人(ひとりひとり)の思(おも)いを
hitori hitori no omoi wo

仆(ぼく)らはどこかに残(のこ)せるだろうか
bokura wa dokoka ni nokoseru darou ka

In this Craziness, You gave me life
ひとつの思(おも)いを
hitotsu no omoi wo

仆(ぼく)らはどこまで守(まも)れるだろうか
boku ra wa doko made mamoreru darou ka

君(きみ)は覚(おぼ)えているの 逆(さか)さまの蝶(ちょう)
kimi wa oboete iruno sakasama no chou

メールのやりとりは とりとめもない
meeru no yaritori wa toritome mo nai

流(なが)されていても 泳(およ)げればいい
nagasarete itemo oyogerebaii

绝(た)えず人の声(こえ)は波(なみ)のように
taezu hito no koe wa nami no youni

信(しん)じるままに 伝(つた)えるメロディ
shinjiru mama ni tsutaeru merodei

优(やさ)しいリズム 泣(な)き出(た)しそうになる
yasashii rizumu nakitashi sou ni naru

いつも雨(あめ) 今(いま)が未来(みらい)へと
itsumo ame ima ga mirai e to

つづく そう思(おも)いたいよ
tsuzuku sou omoitaiyo

In this Craziness, Uncertainty
一人一人(ひとりひとり0の形(かたち)を
hitori hitori no katachi wo

仆(ぼく)らはどこかに残(のこ)せるだろうか
bokura wa doko ka ni nokoseru darou ka

In this Craziness, You gave me life
それぞれの形(かたち)を
sorezore no katachi wo

仆(ぼく)らはどこまで守(まも)れるだろうか
bokura wa doko made mamoreru darou ka

言叶(ことば)になりたがらない気持(きも)ちがあります
kotoba ni narita garanai kimochi ga arimasu

人がいくら手(て)を伸(の)ばしても 人(ひと)の中(なか)に届(とど)かない场所(ばしょ)がある
hito ga ikura te wo nobashitemo hito no naka ni todoka nai basho ga aru

声(こえ)にならない一人一人(ひとりひとり)の思(おも)いが好(す)きだから
koe ni naranai hitori hitori no omoi ga suki dakara

何(なに)かにならなくてもいつの日(ひ)でもかわらず
nani ka ni naranakute mo itsu no hi demo kawarazu

In this Craziness, Uncertainty
一人一人(ひとりひとり)の思(おも)いを
hitori hitori no omoi wo

仆(ぼく)らはどこかに残(のこ)せるだろうか
bokura wa doko ka ni nokoseru darou ka

In this Craziness, You gave me life
ひとつの思(おも)いを
hitotsu no omoi wo

仆(ぼく)らはどこまで守(まも)れるだろうか
bokura wa doko made mamoreru darou ka

In this Craziness, Uncertainty
一人一人(ひとりひとり)の形(かたち)を
hitori hitori no katachi wo

仆らはどこかに残(のこ)せるだろうか
bokura wa doko kani nokoseru darou ka

In this Craziness, You gave me life
それぞれの形(かたち)を
sorezore no katachi wo

仆らはどこまで守(まも)れるだろうか
bokura wa doko made mamoreru darou ka

In this Craziness, Uncertainty
一人一人(ひとりひとり)のあこがれ
hitori hitori no akogare

In this Craziness, You gave me life
ひとつの辉(かがや)き
hitotsu no kagayaki

In this Craziness, Uncertainty
一人一人(ひとりひとり)のときめき
hitori hitori no tokimeki

In this Craziness, You gave me life
ひとつの感动(がんどう)
hitotsu no kandou

In this Craziness, Uncertainty
一人一人(ひとりひとり)のまなざし
hitori hitori no manazashi

In this Craziness, You gave me life
ひとつの偶然(ぐうぜん)
hitotsu no guuzen

In this Craziness, Uncertainty
一人一人(ひとりひとり)のぬくもり
hitori hitori no nukumori

In this Craziness, You gave me life
ひとつの约束(やくそく)
hitotsu no yakusoku


小程序

0 条评论 Python 无标签 XuanVI

黑客帝国数字雨

小时候对黑客帝国中的『数字雨』感到非常酷炫。 现在所选择的专业终于能完成小时候的梦想了。 PS : 虽然感觉技术含量不是很高。 XD
import random
import pygame

WIDTH = 1024
HEIGHT = 800

FONT_WIDTH = 15
pygame .init()
winSur = pygame.display.set_mode((WIDTH,HEIGHT))
font = pygame.font.SysFont("font",25,True)
bg_suface = pygame.Surface((WIDTH,HEIGHT),flags=pygame.SRCALPHA)

pygame.Surface.convert(bg_suface)

bg_suface.fill(pygame.Color(0,0,0,28))
winSur.fill((0,0,0))
letter = ['R','A','I','N']
texts = [font.render(str(letter[i]),
                         True,
                         (random.randint(0,255),
                          random.randint(0,225),
                          random.randint(0,255)))for i in range(4)]

column = int(WIDTH / FONT_WIDTH)

drops = [0 for i in range(column)]

while True:
    for event in pygame.event.get():
        if event.type == pygame.QUIT:
            exit()

    pygame.time.delay(30)
    winSur.blit(bg_suface,(0,0))

    for i in range(len(drops)):
        text = random.choice(texts)
        winSur.blit(text,(i * FONT_WIDTH,drops[i] * FONT_WIDTH))

        drops[i] += 1

        if drops[i] * 10 > HEIGHT or random.random() > 0.95:
            drops[i] = 0

    pygame.display.flip()

数字雨

虽然不难,但是粗心的毛病还是导致出现了好几处小问题:

  1. pygame.Surface.convert(bg_suface)直接把convert打少一个t,开幕雷击。
  2. 第二处的 random.randint(0,225) 更是把random错打成了ramdom,梅开二度。
  3. 最后一行的 pygame.display.flip()flip也是错打成了filp

C语言作业记录

0 条评论 C语言 无标签 XuanVI

2020/3/17

  • 从键盘输入一个字符串,判断是否为对称字符串,若是输出「YES」,若不是输出「NO」
    #include<stdio.h>
    #include<string.h>
    int main()
    {
     char  a[ 10 ];
     char* p;
     int   i, x, y, z;
     p = &a[ 0 ];
     for ( i = 0; i < 10; i++ )
         a[ i ] = '\0';
     gets( a );
     x = 0;
     y = strlen( a );
     for ( i = 0; i < y / 2; i++ )
         if ( *( p + i ) != *( p + y - i - 1 ) )
         {
             x = 1;
             break;
         }
     if (x == 0)
         printf( "YES\n" );
     else
         printf( "NO\n" );
     return 0;
    }
  • 用指针方法,在一个一维数组 int a[10] 的元素中,查找给定的数,若找到则输出该数,若没找到,输出「NO」。
    #include <stdio.h>
    #include <string.h>
    int main()
    {
     int n, i;
     int a[ 10 ];
     int *p = a;
     for ( i = 0; i < 10; i++)
     {
         scanf( "%d", &a[ i ] );
     }
     scanf( "%d", &n );
     for ( i = 0;; i++)
     {
         if(n==*(p+i))
         {
             printf( "%d\n", *( p + i ) );
             break;
         }
         if(i==9)
         {
             printf( "NO\n" );
             break;
         }
     }
     return 0;
    }
  • 编写函数 scomp(char *s1,char *s2),将两个字符串s1和s2进行比较,要求若s1= s2,函数返回值为0;若s1≠s2,返回它们二者第一个不同字符的 ASCII 码差值(如:「BOY」与「BAD」,第2个字母不同,「O」与「A」之差为 79-65=14 ), 即s1> s2,函数返回值为正数;若s1< s2,函数返回值为负数。在主函数调用 scomp 函数并输出返回值。
    #include <stdio.h>
    #include <string.h>
    int main()
    {
     int scomp( char* s1, char* s2 );
     char s1[ 10 ];
     char s2[ 10 ];
     int  n;
     puts( "Please enter string s1:\n" );
     gets( s1 );
     puts( "Please enter string s2:\n" );
     gets( s2 );
     printf( "%d", scomp( s1, s2 ) );
     return 0;
    }
    int scomp( char* s1, char* s2 )
    {
     int i;
     while((*s1==*s2)&&*s1)
     {
         s1++;
         s2++;
     }
     i = *s1 - *s2;
     return i;
    }

C语言tips【更新ing】

0 条评论 C语言 无标签 XuanVI

  • 注意赋值问题

eg.

#include <stdio.h>
int main()
{
    int i,j,sum;
    for(i=3;i>=1;i--)
    {
        sum=0;
        for(j=1;j<=i;j++)
            sum+=i*j;
    }
    printf("%d\n",sum);
}

内循环每执行完一次就会对 sum 重新赋值;这个问题我朋友坑过我 LuXts

  • 编写一个布尔函数 int is_leap_year(int year),判断参数 year 是否为闰年。
    需要弄清楚声明变量和定义变量
#include <stdio.h>
#include <math.h>
int is_leap_year(int year)
{
    if(((year%4==0)&&(year%100!=0)||(year%400==0))
    {
        return 1;
    }
    else
    {
        return 0;
    }
}
int main()
{
    int year=0;
    printf("请输入要判断的年份\n");
    scanf("%d",&year);
    if(is_leap_year(year))
    {
        printf("是闰年\n");
    }
    else
    {
        printf("不是闰年\n");
    }
    return 0;
}
  • 数组

    #include <stdio.h>
    int main()
    {
     int count1[4]={3,2,1,0};
     int count2[4];
     int i;
     for(i=0;i<4;i++)
     {
         count2[i]=count1[i];
         printf("count2[%d]=%d",i,count[i]);
     }
     return 0;
    }

    从一个数组数值拷贝到另一个,但是需要注意此时传递的不是数组类型的参数,而是指针类型的参数

  • 传递数组

    int fun(int a[],int l)

    一维数组传入为a[],l为长度;二维数组则为a[][确定的值]

  • 输入

    for(i=0;i<10;i++)
     scanf("%d",&a);

    在循环中,由于 %d 之后没有「,」所以只能用空格或者回车隔开。


等待更新……