C language: summary of question brushing (1)

C Language learning has come to an end , This article is a summary of recent studies C Summary of language brush questions , Most of the questions come from Niuke & Power button .

Topic 1 ： Integer conversion

Title Description ： Write a function , Determine how many bits need to be changed to change the integer A Converted to an integer B.

Ideas ： In fact, this problem is actually to find A and B How many bits does each bit of the XOR result binary contain 1.

Implementation code ：

#include <stdio.h>

int convertInteger(int A, int B)
{
	int k = A ^ B;
	int sum = 0;
	int i = 0;
	for (i = 0; i < 32; i++)
	{
		if (((k >> i) & 1) == 1)
		{
			sum++;
		}
	}
	return sum;
}

int main()
{
	int A = 0;
	int B = 0;
	scanf("%d %d", &A, &B);
	int ret = convertInteger(A, B);
	printf("%d\n", ret);
	return 0;
}

Topic two ： Intersection of two arrays

Title Description ： Given two arrays nums1 and nums2 , Return their intersection . Each element of the output must be unique . Regardless of the order of the output results .

Ideas ： Traverse both arrays , If the two elements in two arrays are equal , Then save this number , Avoid iterating over the last element to find it repeatedly , Result in output error . that , Here you can define an array by storing the equivalent elements , The subscript of this array is the number of intersections of these arrays , The next time you visit the following table, you will not repeat the search .

Implementation code ：

#include <stdio.h>

int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize)
{
	static int arr[1000];
	int brr[1000] = { 0 };
	int i = 0;
	int j = 0;
	*returnSize = 0;
	for (i = 0; i < nums1Size; i++)
	{
		for (j = 0; j < nums2Size; j++)
		{
			if (nums1[i] == nums2[j])
			{
				if (brr[nums1[i]] == 0)
				{
					brr[nums1[i]] = 1;
					arr[*returnSize] = nums1[i];
					(*returnSize)++;
					break;
				}
			}
		}
	}
	return arr;
}

int main()
{
	int nums1[] = { 4,9,5 };
	int nums2[] = { 9,4,9,8,4 };
	int nums1Size = sizeof(nums1) / sizeof(nums1[0]);
	int nums2Size = sizeof(nums2) / sizeof(nums2[0]);
	int returnSize = 0;
	int* ret = intersection(nums1, nums1Size, nums2, nums2Size, &returnSize);
	for (int i = 0; i < returnSize; i++)
	{
		printf("%d ", *(ret + i));
	}
	return 0;
}

Topic three ： Sort strings

Title Description ： Input ："A" To "Z"、"a" To "z"、"0" To "9". Enter no more than... Letters or numbers 1024. Output in descending order .

Ideas ： Use qsort Function to sort strings . This function has been described in detail in the previous article , See the previous article for details .

Implementation code ：

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int cmp(const void* e1, const void* e2)
{
	return *(char*)e1 - *(char*)e2;
}

int main()
{
	char arr[1000] = { 0 };
	while (scanf("%s", arr) != EOF)
	{
		int sz = strlen(arr);
		qsort(arr, sz, sizeof(arr[0]), cmp);
		printf("%s\n", arr);
	}
	return 0;
}

Topic four ： Find the array center subscript

Title Description ： Give an array of integers  nums , Calculate the central subscript of the array .
                  1. The central subscript of the array is a subscript of the array , The sum of all elements on the left is equal to the sum of all elements on the right .
                  2. If the central subscript is at the leftmost end of the array , Then the sum of the numbers on the left is regarded as 0 , Because there is no element to the left of the subscript .
                  3. This also applies to the fact that the central subscript is at the rightmost end of the array .
                  4. If the array has multiple central subscripts , You should return to the one closest to the left . If the array does not have a central subscript , return - 1 .

Ideas ： In this topic, all the subscripts in the array may be the central subscript of the array , So you should traverse the entire array to find the central subscript , So for the case that the array has multiple central subscripts , You will find the center subscript of the leftmost array , among , In the loop that traverses all the subscripts of the array , Add up all the elements on the left and right of the subscript respectively , Until we find that the sum of the elements on the left is equal to the sum of the elements on the right , Returns the subscript .

Implementation code ：

#include <stdio.h>

int pivotIndex(int* nums, int numsSize)
{
	int i = 0;
	int j = 0;
	for (i = 0; i < numsSize; i++)
	{
		int sum1 = 0;
		int sum2 = 0;
		for (j = 0; j < numsSize; j++)
		{
			if (j < i)
			{
				sum1 += nums[j];
			}
			else if (j > i)
			{
				sum2 += nums[j];
			}
		}
		if (sum1 == sum2)
		{
			return i;
		}
	}
	return -1;
}

int main()
{
	int nums[] = { -1,-1,-1,-1,-1,0 };
	int numsSize = sizeof(nums) / sizeof(nums[0]);
	int ret = pivotIndex(nums, numsSize);
	printf("%d\n", ret);
	return 0;
}

Topic 5 ： Statistics of the number of characters

Title Description ： Enter a line of string without spaces . The range in the output input string is (0~127, Include 0 and 127) Number of characters .

Ideas ： Traverse each character of the input string , Create another array , Set the character as the index of the array , To determine whether the character has appeared before , Then we can judge the number of characters . The general idea is similar to the method of finding whether the intersection of the two arrays is repeated .

Implementation code ：

#include <stdio.h>

int Count(char* ch)
{
	int count = 0;
	char arr[128] = { 0 };
	while (*ch != '\0')
	{
		if (arr[*ch] != 1)
		{
			count++;
		}
		arr[*ch] = 1;
		ch++;
	}
	return count;
}

int main()
{
	char ch[500] = { 0 };
	scanf("%s", ch);
	int ret = Count(ch);
	printf("%d\n", ret);
	return 0;
}

Topic 6 ： Find most elements in array

Title Description ： Given a size of n Array of , Find most of them . Most elements refer to the number of occurrences in an array Greater than n/2 The elements of . Suppose the array is not empty , And there are always many elements in a given array .

Ideas ： A number in an array appears more than n/2 , From 0 Character start , Suppose it's the highest number , If the same number is encountered, it will be counted
Count +1 , In case of different, count -1 , In fact, they consume each other , Wait until the count is 0 When , It means that the mutual spelling is completed , Reopen from the next character
Initial mutual splicing , But in the final analysis, the number of occurrences is greater than n/2 The number is more , Therefore, it is also the last reserved character .

Implementation code ：

#include <stdio.h>

int majorityElement(int* nums, int numsSize)
{
	int count = 1;
	int tmp = nums[0];
	int i = 1;
	for (i = 1; i < numsSize; i++)
	{
		if (tmp == nums[i])
		{
			count++;
		}
		else
		{
			count--;
			if (count == 0)
			{
				tmp = nums[i + 1];
			}
		}
	}
	return tmp;
}

int main()
{
	int nums[] = { 1,2,2,2,3 };
	int numsSize = sizeof(nums) / sizeof(nums[0]);
	int ret = majorityElement(nums, numsSize);
	printf("%d\n", ret);
	return 0;
}

Topic 7 ： Self divisor

Title Description ： A self divisor is a number that can be divided by every digit it contains . Given two integers left and right , Return a list , The elements of the list are ranges [left, right] All the self dividers in .

Ideas ： Traverse left and right The number in the middle , Loop through the numbers , Every time I die 10（ That is, the last digit of this number is taken out every time ）, Judge it , And define an array to store these self divisors .

Implementation code ：

#include <stdio.h>

int* selfDividingNumbers(int left, int right, int* returnSize)
{
	static int arr[10000] = { 0 };
	*returnSize = 0;
	int i = 0;
	for (i = left; i <= right; i++)
	{
		int j = i;
		int jude = 1;
		while (j)
		{
			int n = j % 10;
			if (n == 0)
			{
				jude = 0;
				break;
			}
			if (i % n != 0)
			{
				jude = 0;
				break;
			}
			j = j / 10;
		}
		if (jude == 1)
		{
			arr[*returnSize] = i;
			(*returnSize)++;
		}
	}
	return arr;
}

int main()
{
	int left = 47;
	int right = 85;
	int returnSize = 0;
	int* ret = selfDividingNumbers(left, right, &returnSize);
	int i = 0;
	for (i = 0; i < returnSize; i++)
	{
		printf("%d ", *(ret + i));
	}
	return 0;
}