去哪儿网笔试题

朴灿烈づ我的快乐病毒、 2022-08-07 07:53 183阅读 0赞

一、循环数组查找特定值

解决此问题的难点就是要找到此循环数组的分界点，

如\{23,34,41,52,4,8,13,20\}这个数组的分界点就是数组下标为3的这个位置。

找到分界点后，再看要找的目标值是在分界点的左边还是右边，再用折半查找法就可以解决问题了。

#include<stdio.h>
    int indexOf(int a[], int target, int len)
    {
    	int i = 0;
    	int left = 0;    //left是数组最左边的index
    	int right = len - 1;   //right是一个分段上最右边的index 
    	int mid = (left + right) / 2;   
    	if (!(a[left] <= a[mid] && a[mid] <= a[right]))   //不要!,说明这是正常的顺序递增数组 
    	{
    		for (i; i < len - 1; i++)
    		{
    			if (a[i] < a[i+1])
    			{
    				i++;     //记录分界点位置 
    			}
    			else
    			{
    				break;
    			} 
    		}
    	
    		if (target >= a[left] && target <= a[i])
    		{
    			right = i;	
    		}
    		else{
    			left = i + 1;
    			right = len - 1;
    		}
    	}	
    	
    	//二分法查找
    	while(left <= right)
    	{
    		mid = (left + right) / 2;
    		if (target < a[mid])
    		{
    			right = mid - 1;	
    		}
    		else if (target > a[mid])
    		{
    			left = mid + 1;	
    		}
    		else{
    		
    			return mid;
    		}
    	} 
    	return -1;
    }
    int main()
    {
    	int a[9] = {7, 8, 9, 1, 2, 3, 4, 5, 6};
    
    	int len = sizeof(a) / sizeof(a[0]);
    	printf("%d\n", indexOf(a, 4, len));
    	
    	return 0;
    }

二、将ab2c3sb4you2转变为ababcccsbsbsbsbyouyou

#include<stdio.h>
    #include<string.h>
    int main()
    {
    	char str[] = "ab2c3sb4you2";
    	char end[100] = {'\0'};     //转变后的字符串
    	char temp[100] = {'\0'};    //具体数组大小视情况而定
    	int i;
    	int n = 0;
    	for (i = 0; str[i] != '\0'; i++)
    	{
    		if (str[i] >= '1' && str[i] <= '9')
    		{
    			int m = 0;
    			for (m; m < (str[i] - '0'); m++)
    			{
    				strcat(end, temp);
    			}
    			memset(temp, '\0', sizeof(temp));    //清空这个temp数组
    			n = 0;
    			
    		}
    		else
    		{
    			temp[n] = str[i];
    			n++;
    		}
    	
    	}
    	puts(end);
    	return 0;
    }