1032.进制转换
定义一个函数h2i,将一个字符串表示的16进制数转换成一个10进制数。
//********** Specification of hex2int **********
unsigned h2i(char s[]);
/* PreCondition:
s is a string consisting of 0~9,A-F or a-f with at most 8 characters
PostCondition:
return a decimal number equivalent to s
Examples: "100" ==> 256 ; "a" ==> 10 ; "0"==> 0
*/
/***************************************************************/
/* */
/* DON'T MODIFY main function ANYWAY! */
/* */
/***************************************************************/
#include <stdio.h>
#define N 8
//********** Specification of hex2int **********
unsigned h2i(char s[])
/*
PreCondition:
s is a string consisting of 0~9,A-F or a-f with at most 8 characters
PostCondition:
return a decimal number equivalent to s
Examples: "100"==>256 ; "a"==> 10 ; "0"==> 0
*/
{
//TODO: your function definition
}
/***************************************************************/
int main()
{
char s[N+1];
scanf("%s",s);
//********** hex2int is called here ****************
printf("%u\n",h2i(s));
//**************************************************
return 0;
}
样例
Input |
---|
100 |
Output |
---|
256 |
题解:
正序遍历,核心代码为sum = sum*16 + temp;
代码:
#include<stdio.h>
#define N 8
unsigned h2i(char s[]){
int length = 0;
unsigned int sum = 0;
int temp;
while(s[length]!='\0'){
if(s[length]<='9' && s[length]>='0')
temp = s[length]-'0';
else{
if(s[length]>='a' && s[length]<='f')
temp = s[length]-'a'+10;
else
temp = s[length]-'A'+10;
}
sum = sum*16 + temp;
length++;
}
return sum;
}
int main(){
char s[N+1];
scanf("%s",s);
printf("%u\n",h2i(s));
}
1033.查找字符串
定义一个函数strReverseIndex(s,t),返回t在s中最右边出现的位置(s中的第1个字符的位置为0),找不到时返回-1。
//********** Specification of strrindex**********
int strReverseIndex(char s[],char t[ ]);
/* precondition: NULL
postcondition: return index of t in s from right to left, -1 if none
*/
/***************************************************************/
/* */
/* DON'T MODIFY main function ANYWAY! */
/* */
/***************************************************************/
#include <stdio.h>
int strReverseIndex(char s[],char t[])
/* precondition: NULL
postcondition: return index of t in s from right to left, -1 if none
*/
{
//TODO: your function definition
}
/***************************************************************/
#define N 80
int main()
{
char s[N+1],t[N+1];
scanf("%s%s",s,t);
//********** strReverseIndex is called here ********************
printf("%d\n",strReverseIndex(s,t));
//**************************************************
return 0;
}
题解:
两种思路,模式匹配算法和KMP算法,但是KMP我不会写,就用模式匹配了,哈哈。 模式匹配算法: 长串s和短串t,遍历长串s,可以任意顺序,如本题中就是倒序遍历。将s中的字符与t中的第一个字符比较,如果相同,那么比较s中的下一个字符和t的第二个字符,如此往复,直到比较次数大于t的长度,那么就找到了。如果没找到,跳出,继续将s的下一个字符与t第一个字符比较,如此往复。
代码:
#include <stdio.h>
#define N 80
int strReverseIndex(char s[], char t[]){
int found = 0;
int length_s = 0, length_t = 0;
while (t[length_t] != '\0')length_t++;
while (s[length_s] != '\0')length_s++;
for (int i = length_s-1; i >= 0; i--){
int j = 0;int temp = i;
while (s[temp] == t[j] && temp < length_s){
temp++; j++;
if (j == length_t)
found = 1;
}
if (found)
return i;
}
return -1;
}
int main(){
char s[N + 1], t[N + 1];
scanf("%s%s", s, t);
printf("%d\n", strReverseIndex(s, t));
return 0;
}
1034.字符串的旋转
国外某知名 IT 企业有一个招聘题 :
Enter two strings, s1 and s2, with length no more than 80, write code to check if s1 is a rotation of s2.
输入2个字符串,以1个空格分隔。
在一行中输出相关判断结果。
例如:
输入:waterbottle erbottlewat
输出:"waterbottle" is a rotation of "erbottlewat"
又如:
输入:water erbottlewat
输出:"water" is NOT a rotation of "erbottlewat"
/***************************************************************/
/* */
/* DON'T MODIFY main function ANYWAY! */
/* */
/***************************************************************/
#include <stdio.h>
#include <string.h>
int isRotation(char s1[],char s2[])
/* PreCondition: s1和s2是长度不超80的两个字符串
PostCondition: s2可以是s1经过循环移动后得到时返回1,否则0
*/
{
//TODO: your function definition
}
/***************************************************************/
#define N 80
int main()
{
char s[N+1],t[N+1];
scanf("%s%s",s,t);
//********** isRotation is called here *************
if(isRotation(s,t)) printf("\"%s\" is a rotation of \"%s\"\n",s,t);
else printf("\"%s\" is NOT a rotation of \"%s\"\n",s,t);
//**************************************************
return 0;
}
题解:
两种思路:
1.循环链表
我这里用的就是循环链表的方法,具体什么是循环链表,可以自己百度。
2.字符数组模拟循环链表
创建index代表数组下标,模拟指针,根据数组长度,令index=index%length
。特殊情况需要单独判断。
代码:
#include <stdio.h>
#include <string.h>
#define N 80
typedef struct LinkedList{
char ch;
struct LinkedList *next;
} link;
void add(link *head, char x){
link *p = head;
while (p->next)
p = p->next;
p->next = (link *)malloc(sizeof(link));
p = p->next;
p->ch = x;
p->next = NULL;
}
int isRotation(char s1[], char s2[]){
if (strlen(s1) != strlen(s2))
return 0;
int flag = 1;
for(int i = 0; i < strlen(s1);i++){
if(s1[i]!=s2[i]){
flag = 0;
break;
}
}
if(flag) return 1;
link *head = (link *)malloc(sizeof(link));
head->ch = '\0';
head->next = NULL;
for (int i = 0; i < strlen(s1); i++)
add(head, s1[i]);
link *p = head;
while (p->next)
p = p->next;
p->next = head->next;
p = head->next;
link *pp = p->next;
while (pp != p){
int flag = 1;
link *temp = pp;
for (int i = 0; i < strlen(s2); i++){
if (temp->ch != s2[i]){
flag = 0;
break;
}
else
temp = temp->next;
}
if (flag == 0)
pp = pp->next;
else
return flag;
}
return 0;
}
int main(){
char s[N+1],t[N+1];
scanf("%s%s",s,t);
//********** isRotation is called here *************
if(isRotation(s,t)) printf("\"%s\" is a rotation of \"%s\"\n",s,t);
else printf("\"%s\" is NOT a rotation of \"%s\"\n",s,t);
//**************************************************
return 0;
}
1035.二分查找
Write a function binarySearch(a, n, x) that searches x integer array a of length n, and returns the index of a (-1 if x can not be found in a).
Assume elements of a are entered in descending order, and the value of evey element is unique.
Write a program to call binarySearch(a, n, x).
/***************************************************************/
/* */
/* DON'T MODIFY main function ANYWAY! */
/* */
/***************************************************************/
#include <stdio.h>
int binarySearch(int a[], int n, int x) {
// TODO: your function definition
}
/***************************************************************/
#define N 100000
int a[N];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
//********** binarySearch is called here *************
int q, x;
scanf("%d", &q);
for (int i = 0; i < q; i++) {
scanf("%d", &x);
printf("%d\n", binarySearch(a, n, x));
}
//**************************************************
return 0;
}
题解:
这题我踩雷了,数组是按照降序排列的,一定要看清楚。二分查找算法不必细说,注意分开处理奇偶情况的二分(c特性)。
代码:
#include <stdio.h>
int binarySearch(int *a, int n, int x){
int mid;
int left = 0;
int right = n-1;
while(left<=right){
if ((right + left) % 2 != 0)
mid = (right + left) / 2 + 1;
else
mid = (right + left) / 2;
if (a[mid] == x) return mid;
else if(a[mid] < x) right = mid-1;
else left = mid+1;
}
return -1;
}
#define N 100000
int a[N];
int main() {
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
//********** binarySearch is called here *************
int q, x;
scanf("%d", &q);
for (int i = 0; i < q; i++) {
scanf("%d", &x);
printf("%d\n", binarySearch(a, n, x));
}
//**************************************************
return 0;
}