_Song_-CSDN博客

原创 ZJU PTA ds 7-1 Hashing - Hard Version

However, now you are asked to solve the reversed problem: reconstruct the input sequence from the given status of the hash table. Whenever there are multiple choices, the smallest number is always taken.

2022-01-12 17:24:40 932

原创 ZJU PTA ds 6-1 Iterative Mergesort

How would you implement mergesort without using recursion?

2022-01-12 17:13:45 627

原创 ZJU PTA ds 6-1 Strongly Connected Components

Write a program to find the strongly connected components in a digraph.

2022-01-12 17:03:35 1880

原创 ZJU PTA ds 7-1 Hamiltonian Cycle

The "Hamilton cycle problem" is to find a simple cycle that contains every vertex in a graph. Such a cycle is called a "Hamiltonian cycle".

2022-01-12 15:43:43 973

原创 ZJU PTA ds 6-1 Is Topological Order

Write a program to test if a give sequence Seq is a topological order of a given graph Graph.

2022-01-12 15:32:07 720

原创 ZJU PTA ds 7-1 File Transfer

7-1 File TransferWe have a network of computers and a list of bi-directional connections. Each of these connections allows a file transfer from one computer to another. Is it possible to send a file from any computer on the network to any other?

2022-01-12 15:21:09 329

原创 ZJU PTA ds 7-1 Complete Binary Search Tree

7-1 Complete Binary Search TreeA Binary Search Tree (BST) is recursively defined as a binary tree which has the following properties:The left subtree of a node contains only nodes with keys less than the node’s key.The right subtree of a node contains

2022-01-12 14:55:14 496

原创 ZJU PTA ds 6-1 Percolate Up and Down

Percolate Up and DownWrite the routines to do a “percolate up” and a “percolate down” in a binary min-heap.Format of functions:void PercolateUp( int p, PriorityQueue H );void PercolateDown( int p, PriorityQueue H );where int p is the position of the

2022-01-12 14:43:37 923

原创 ZJU PTA ds 7-1 Pop Sequence

7-1 Pop SequenceGiven a stack which can keep M numbers at most. Push N numbers in the order of 1, 2, 3, …, N and pop randomly. You are supposed to tell if a given sequence of numbers is a possible pop sequence of the stack. For example, if M is 5 and N is

2022-01-12 14:36:37 252

原创 ZJU PTA 6-1 Add Two Polynomials

6-1 Add Two Polynomials (10 point(s))Write a function to add two polynomials. Do not destroy the input. Use a linked list implementation with a dummy head node. Note: The zero polynomial is represented by an empty list with only the dummy head node.Forma

2022-01-12 14:33:39 735

原创浙大大学 PTA C语言程序设计链表逆置

6-7 链表逆置 (20 point(s))本题要求实现一个函数，将给定单向链表逆置，即表头置为表尾，表尾置为表头。链表结点定义如下：struct ListNode {int data;struct ListNode *next;};函数接口定义：struct ListNode *reverse( struct ListNode *head );其中head是用户传入的链表的头指针；函数reverse将链表head逆置，并返回结果链表的头指针。裁判测试程序样例：#include &l.

2021-03-25 22:25:41 1100

原创浙大大学 PTA 奇数值结点链表

6-5 奇数值结点链表 (20 point(s))本题要求实现两个函数，分别将读入的数据存储为单链表、将链表中奇数值的结点重新组成一个新的链表。链表结点定义如下：struct ListNode {int data;ListNode *next;};函数接口定义：struct ListNode *readlist();struct ListNode *getodd( struct ListNode **L );函数readlist从标准输入读入一系列正整数，按照读入顺序建立单链表。当读到.

2021-03-25 21:55:04 704

原创浙大大学 PTA 单链表结点删除

6-6 单链表结点删除 (20 point(s))本题要求实现两个函数，分别将读入的数据存储为单链表、将链表中所有存储了某给定值的结点删除。链表结点定义如下：struct ListNode {int data;ListNode *next;};函数接口定义：struct ListNode *readlist();struct ListNode *deletem( struct ListNode *L, int m );函数readlist从标准输入读入一系列正整数，按照读入顺序建立单链.

2021-03-25 16:34:30 1737

原创浙大大学 PTA 6-4 链表拼接

6-4 链表拼接 (20 point(s))本题要求实现一个合并两个有序链表的简单函数。链表结点定义如下：struct ListNode {int data;struct ListNode *next;};函数接口定义：struct ListNode *mergelists(struct ListNode *list1, struct ListNode *list2);其中list1和list2是用户传入的两个按data升序链接的链表的头指针；函数mergelists将两个链表合并成一个.

2021-03-25 15:44:34 1308

原创浙江大学 PTA 6-8 十进制转换二进制

6-8 十进制转换二进制本题要求实现一个函数，将正整数n转换为二进制后输出。函数接口定义：void dectobin( int n );函数dectobin应在一行中打印出二进制的n。建议用递归实现。裁判测试程序样例：#include <stdio.h>void dectobin( int n );int main(){ int n; scanf("%d", &n); dectobin(n); return 0;}/*.

2021-03-06 10:58:29 1087

原创浙江大学 PTA 递归实现顺序输出整数

6-5 递归实现顺序输出整数 (15 point(s))本题要求实现一个函数，对一个整数进行按位顺序输出。函数接口定义：void printdigits( int n );函数printdigits应将n的每一位数字从高位到低位顺序打印出来，每位数字占一行。裁判测试程序样例：#include <stdio.h>void printdigits( int n );int main(){ int n; scanf("%d", &n); p.

2021-03-05 12:38:43 1200 2

原创力扣（LeetCode）142.环形链表二（Linked List Cycle two）

142. Linked List Cycle II没看题解时，我想到的是配合141题的查找是否有环，如果有，再遍历每个元素。依据是：如果有一个环，将快慢指针设置在入环处，那么快慢指针下一个（或者N次）相遇必定也在入环处。于是开始写出来的是时间复杂度比较差的算法。bool hasCycle(struct ListNode *head) { if(head == NULL) return false; struct ListNode *slow = head, *fast.

2021-02-22 15:23:07 91

原创力扣（LeetCode）141.环形链表（Linked List Cycle）

Given head, the head of a linked list, determine if the linked list has a cycle in it.There is a cycle in a linked list if there is some node in the list that can be reached again by continuously following the next pointer. Internally, pos is used to deno

2021-02-19 15:33:58 105

原创力扣（LeetCode）206. 反转链表（Reverse Linked List）

206. 反转链表（Reverse Linked List）

2021-02-18 16:24:17 138

原创力扣（LeetCode）59. Spiral Matrix II(螺旋矩阵2)

/** * Return an array of arrays of size *returnSize. * The sizes of the arrays are returned as *returnColumnSizes array. * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free(). */int** generateMatrix(int n, int

2021-02-17 19:06:43 91

原创力扣（LeetCode）209 长度最小的子数组 Minimum Size Subarray Sum

209 长度最小的子数组 Minimum Size Subarray Sum看完这个题直接想到的是三层循环，先固定长度，再遍历，原谅我的愚蠢，我内心也觉得这个很可怕，然后写出来超时了。然后看了有n的平方，然后想到可以先固定起始位置，再遍历，边遍历边检验：int minSubArrayLen(int target, int* nums, int numsSize){ int i, sum, j, minSublen = numsSize+1; for(i = 0; i < nu.

2021-02-15 22:12:04 164

原创浙江大学 PTA 数据结构与算法最大子列和问题

7-1 最大子列和问题 (20 point(s))给定K个整数组成的序列{ N1 , N2 , …, NK }，“连续子列”被定义为{ Ni , Ni+1 , …, Nj }，其中 1≤i≤j≤K。“最大子列和”则被定义为所有连续子列元素的和中最大者。例如给定序列{ -2, 11, -4, 13, -5, -2 }，其连续子列{ 11, -4, 13 }有最大的和20。现要求你编写程序，计算给定整数序列的最大子列和。本题旨在测试各种不同.

2021-02-04 16:21:06 348

原创浙大大学 PTA 数据结构和算法顺序表操作集

6-2 顺序表操作集 (20 point(s))本题要求实现顺序表的操作集。函数接口定义：List MakeEmpty();Position Find( List L, ElementType X );bool Insert( List L, ElementType X, Position P );bool Delete( List L, Position P );其中List结构定义如下：typedef int Position;typedef struct LNode List;st

2021-02-03 18:19:56 1028

原创数据结构和算法之最大子列和问题

最大子列和问题/*算法一:暴力穷举*/int MaxSubseqSum1( int A[] , int N ){ int ThisSum,MaxSum = 0; int i,j,k; for( i= 0;i<N;i++) for(j=i;j<N;j++){ ThisSum = 0; for(k=i;k<=j;k++) ThisSum+=A[k]; .

2021-02-02 17:04:22 77

原创 C语言计算给定多项式在给定点x的值

计算给定多项式在给定点x的值对比所用的两种方法double f1(double a[],int n,double x){ double result; result=a[0]; int i; for(i=1;i<n;i++){ result+=a[i]*power(x,i); } return result; }/////***************************////////double f2(do.

2021-02-01 21:15:13 1520

原创 C语言统计输入的单词数与字符数

统计输入的单词数与字符数#include<stdio.h>#define IN 1 //在单词内#define OUT 0 //在单词外//统计输入的单词数与字符数int main(void){ char c; int state=OUT; int numb_row=0,numb_char=0,numb_word=0; while((c=getchar())!='\n'){ numb_char++; if(.

2021-01-29 21:08:18 476

原创 C语言练习连续的多个空格用一个空格代替

编写一个将输入复制到输出的程序，并将其中连续的多个空格用一个空格代替#include<stdio.h>int main(void){ char c; while((c=getchar())!=EOF){ if(c==' '){ //在读入到空格的时候，后面的空格就可以忽略，所以在if条件下while循环（可能有多个空格） putchar(c); while((c=getchar())==' '){

2021-01-29 20:28:43 3018

原创浙江大学 PTA C语言-实验12-综合程序设计 7-1 自动售货机

7-1 自动售货机 (30point(s))如图所示的简易自动售货机，物品架1、2上共有10样商品，按顺序进行编号分别为1－10，标有价格与名称，一个编号对应一个可操作按钮，供选择商品使用。如果物架上的商品被用户买走，储物柜中会自动取出商品送到物架上，保证物品架上一定会有商品。用户可以一次投入较多钱币，并可以选择多样商品，售货机可以一次性将商品输出并找零钱。用户购买商品的操作方法是：（1）从“钱币入口”放入钱币，依次放入多个硬币或纸币。钱币可支持1元（纸币、硬币）、2元（纸币）、5元（纸币）、10元

2021-01-14 19:21:37 1217

空空如也

空空如也