catalogue
Introduction (counting method and counting array)
Find all missing numbers in the array
Check that all characters appear the same number of times
The first unique character in the string
Introduction (counting method and counting array)
We often use an odd element to count the number of elements
If we count the number of people with IQ over 163, we can use a counting method
int func(int *iq, int size) {
int cnt = 0;
for(i = 0; i < size; ++i) {
if(iq[i] > 163) {
++cnt;
}
}
return cnt;
}
If we want to know the distribution of iq, we can use a count array. We can map the value of iq to the subscript of the count array, and its corresponding value is the number of occurrences of this element
int *func(int *iq, int size, int IQMax) { // (1) * iq is his array element, size is the length of this element, and iqmax is the upper limit of iq
int i;
int *cnt = (int *)malloc( sizeof(int) * (IQMax+1) ); // (2) Get an array of counts, the maximum value of which is iqmax+1, because it is mapped to the subscript of the array
memset(cnt, 0, sizeof(int) * (IQMax+1)); // (3) Initialize him, assign a value of 0, and carry out subsequent operations
for(i = 0; i < size; ++i) {
++cnt[ iq[i] ]; // (4) / / assign the iq value to the subscript of cnt and traverse cnt later
}
return cnt; // (5)
}
Sum of unique elements
Give you an array of integers nums . The only elements in the array are those that only appear Exactly Once Element.
Please return to num Sum of unique elements in .
Example 1:
Input: num = [1,2,3,2] Output: 4 Explanation: the only elements are [1,3], and 4.
Example 2:
Input: num = [1,1,1,1,1] Output: 0 Explanation: there is no unique element, and is 0.
Example 3:
Input: num = [1,2,3,4,5] Output: 15 Explanation: the only element is [1,2,3,4,5], and is 15.
Tips:
- 1 <= nums.length <= 100
- 1 <= nums[i] <= 100
int sumOfUnique(int* nums, int numsSize)
{
int cnt[101];//Since the upper limit of num [i] is 100, the maximum value defined by the subscript of his counting array is 101,
memset(cnt,0,sizeof(cnt));//Assign him 0
int i=0;
int sum=0;
for(i=0;i<numsSize;i++)
{
++cnt[nums[i]];//Count array
}
for(i=0;i<101;i++)
{
if(cnt[i]==1)//If it only appears once, add up his subscripts
{
sum+=i;
}
}
return sum;
}Find all missing numbers in the array
Find all missing numbers in the array
Give you an array nums containing N integers, where nums[i] is in the interval [1, n]. Please find all numbers in the range of [1, n] but not in nums, and return the results in the form of an array.
Example 1:
Input: num = [4,3,2,7,8,2,3,1] Output: [5,6]
Example 2:
Input: num = [1,1] Output: [2]
Tips:
- n == nums.length
- 1 <= n <= 105
- 1 <= nums[i] <= n
The original elements in an array with n elements should be 1 to n. We need to find the elements that do not appear
/**
* Note: The returned array must be malloced, assume caller calls free().
*/
int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize)
{
int cnt[numsSize+1];//Define the count array. The maximum element should be mapped to n, so + 1
memset(cnt,0,sizeof(cnt));//Initialize it to 0, then fill the count array, and find the one with 0 occurrences
int i=0;
for(i=0;i<numsSize;i++)
{
cnt[nums[i]]++;
}
int j=0;
for(i=1;i<numsSize+1;i++)//Because i=0, 0 only appears 0 times, but the problem requires us to start from 1, so i starts from 1
{
if(cnt[i]==0)
{
j++;//Because we want malloc to create an array to receive elements that only appear once, we need to calculate how many elements are in that array
}
}
int *ret=(int *)malloc(sizeof(int)*j);
int k=0;
for(i=1;i<numsSize+1;i++)
{
if(cnt[i]==0)
{
ret[k++]=i;//Give ret what only appears once
}
}
*returnSize=j;
return ret;//Returns an array of that element
}Number of good pairs
Give you an integer array nums.
If a set of numbers (i,j) satisfies nums[i] == nums[j] and I < J, it can be considered as a set of good number pairs.
Returns the number of good pairs.
Example 1:
Input: num = [1,2,3,1,1,3] Output: 4 Explanation: there are 4 groups of good number pairs, which are (0,3), (0,4), (3,4), (2,5), and the subscript starts from 0
Example 2:
Input: num = [1,1,1,1] Output: 6 Explanation: each group of numbers in the array is a good number pair
Example 3:
Input: num = [1,2,3] Output: 0
Tips:
- 1 <= nums.length <= 100
- 1 <= nums[i] <= 100
If an element appears 3 times, its logarithm is 3, and if an element appears 4 times, its logarithm is 6, then we can receive it with a count array. If the value of the count array is greater than 1, its logarithm is Cn2,
int consist(int n,int m)//Count the logarithm of this number greater than 1
{
int sum1=1;
int sum2=1;
int sum;
int i=n;
int j=1;
for(j=1;j<=m;j++)
{
sum1*=j;
}
while(m--)
{
sum2*=i;
i--;
}
sum=sum2/sum1;
return sum;
}
int numIdenticalPairs(int* nums, int numsSize)
{
int n=numsSize;
int cnt[101];
memset(cnt,0,sizeof(cnt));
int i=0;
for(i=0;i<n;i++)
{
++cnt[nums[i]];
}
int flag=1;
int sum=0;
for(i=1;i<101;i++)
{
if(cnt[i]!=0&&cnt[i]!=1)
{
sum+=consist(cnt[i],2);
}
}
return sum;
}Check that all characters appear the same number of times
Check that all characters appear the same number of times
Give you a string s ， If s It's a good idea String, please return true ， Otherwise, return false .
If s In the past All characters appear the same number of times ， Then we call the string s Yes character string.
Example 1:
Input: s = "abacbc" Output: true Explanation: the characters that have appeared in s are 'a', 'b' and 'c'. All characters in s appear twice.
Example 2:
Input: s = "aaabb" Output: false Explanation: the characters that have appeared in s are 'a' and 'b'. 'a' appeared 3 times and 'b' appeared 2 times, with different times.
Tips:
- 1 <= s.length <= 1000
- s Contains only lowercase English letters.
bool areOccurrencesEqual(char * s)
{
int cnt[26];//Because every element in it is lowercase
memset(cnt,0,sizeof(cnt));
int len=strlen(s);
int i=0;
for(i=0;i<len;i++)
{
++cnt[s[i]-'a'];//-'a', if 'a' - 'a' = 0;, the letter is mapped to the subscript
}
int flag=1;
for(i=0;i<len-1;i++)
{
if(cnt[s[i]-'a']!=cnt[s[i+1]-'a'])//The number of occurrences is factored by s[i]. If the corresponding occurrence times are different, it is wrong. All elements can always be compared before and after
{
return false;
}
}
return true;
}The first unique character in the string
The first unique character in the string
Given a string, find its first non repeating character and return its index. If it does not exist, return - 1.
Example:
s = "leetcode" Return 0 s = "loveleetcode" Return 2
int firstUniqChar(char * s)
{
int len=strlen(s);
int cnt[26];
memset(cnt,0,sizeof(cnt));
int i=0;
for(i=0;i<len;i++)
{
++cnt[s[i]-'a'];
}
for(i=0;i<len;i++)
{
if(cnt[s[i]-'a']==1)
{
return i;//Return when the first one appears only once
}
}
return -1;//If none of the loop is found, it returns - 1
}