1. Find the first character in the string that appears only once: The first character that appears only once_ Niuke Tiba_ Niuke (nowcoder.com)
Since the characters in the computer are ultimately represented by the asker code, you can create an array, and the number of times each character appears will be placed in the subscript position corresponding to the asker code in the array. At that time, start searching from the subscript of the asker code corresponding to the first character, and the character whose first element is 1 is the character you want to find.
Note: in the second for loop, in the created table array, the order in which characters appear is found in the array according to the order in which characters appear. To obtain the occurrence times of each character stored in the array, you can also traverse from 1 to 128 in turn, but these two methods may have different effects in different topics, which should be paid attention to when doing questions. For example, if you look at this question from 1 to 128, you can indeed find the character that appears only once, but this character does not necessarily appear first in the string. It is only the character that appears first and only once in the asker code.
int FirstNotRepeatingChar(char* str)
{
char table[128] = { 0 };
int len = strlen(str);
for (int i = 0; i < len; i++)//Traverse the entire string
{
table[str[i]] = table[str[i]] + 1;//Every time a character is read, the asker code of this character in the table array will be
//The element + 1 in the corresponding position, that is, there is another character corresponding to the asker code corresponding to this subscript number. The characters corresponding to different subscripts in the string may be the same. In this case, str[i] may be equal to str[j], and table[str[i]] and table[str[j]] correspond to the same position in the table array.
}
for (int j = 0; j < len; j++)
{//str[j] is originally a character, that is, the j + 1st character in the string, but when the character str[j] appears in the parentheses of the array table
//When in, it changes from a character to the asker code value corresponding to the character.
if (table[str[j]] == 1)//If this character appears only once
{
return j;
}
}
return-1;
}
2. Determine whether the characters in the string are unique: Interview question 01.01 Determine whether the character is unique - LeetCode (LeetCode CN. Com)
This question is similar to the previous one. The only difference is that question 6 looks at which element in the table array is equal to 1, while this question looks at whether any element in the table array is greater than 1.
Note: for this question, the two traversal methods mentioned in question 1 can be used. (it can be understood that the requirements of this question are relatively few and not hypocritical)
bool isUnique(char* astr)
{
char table[128]={0};
int i=0;
int sz=strlen(astr);
for(i=0;i<sz;i++)
{
table[astr[i]]=table[astr[i]]+1;
}
int j=0;
for(j=0;j<sz;j++)
{
if(table[astr[j]]>1)
{
return false;
}
}
return true;
}
3. Given two strings, judge whether one string can become another string after rearrangement.
The core ideas of these three questions are the same. This question is equivalent to using the same idea twice, finding out the number of each element in the two strings, and then comparing the two.
bool CheckPermutation(char*s1,char*s2)
{
int table1[128]={0},table2[128]={0};
int len1=strlen(s1);
int len2=strlen(s2);
if(len1!=len2)
{
return false;
}
int i=0;
int j=0;
while(i<len1)
{
table1[s1[i]]+=1;
i++;
}
while(j<len2)
{
table2[s2[j]]+=1;
j++;
}
for(int m=0;m<128;m++)
{
if(table1[m]!=table2[m])
{
return false;
}
}
return true;
}
4. Judge whether the string constitutes palindrome arrangement:
Interview question 01.04 Palindrome arrangement - LeetCode (LeetCode CN. Com)
The key idea of solving this problem is the same as the above three problems. The specific idea is that if a string can be arranged into palindromes after rearrangement, there are two cases: even characters in the string and odd characters in the string. When there are an even number of characters, each character in the string needs to appear an even number of times. If a character in an even character string appears odd times, then at least another character must appear odd times. When there are even characters in the string, only one character needs to appear odd times. When this happens, all other characters must appear even times. Comprehensive analysis of the above two cases, in the string composed of even characters, the character with odd number of times does not exist. (at this time, it is palindrome structure, and in the string composed of even characters, as long as one element has odd number of times, the string must not be palindrome structure.) in the string composed of even characters, one pair, two pairs... Do not appear again, but in the string composed of odd characters, If the character with odd number of times does not appear again, (this is the palindrome structure. It should be noted that there can be no character with odd number of times in the string composed of odd number of characters) if it does not appear three or five times... Then after summarizing the rules, I don't need to consider whether there are odd or even characters in the string, I only need to calculate the number of characters that appear odd times in the string. As long as it is less than once, whether it is 1 or 0 times, it must be a palindrome structure. As long as it is greater than once, it must not be a palindrome structure.
bool canPermutePalindrome(char* s)
{
int table[128] = { 0 };
int sz = strlen(s);
int i = 0;
for (i = 0; i < sz; i++)
{
table[s[i]] += 1;
}
int m = 0;
int n = 0;
for (m = 0; m < 128; m++)
{
if (table[m] % 2 != 0)
{
n++;
}
if (n > 1)
{
return false;
}
}
return true;
}
Note: for this problem, using traversal according to the order in which characters appear in the string will cause problems. When multiple elements appear repeatedly in the string, such as aaa, because a appears three times, the corresponding end of a in the table array will be 3. At this time, the program will enter the penultimate if statement three times. No matter which character appears odd times, it will add 1 to n, The original intention of designing this program was to count the number of different types of characters that appear odd times. However, according to the following program, as long as it runs to the characters that appear odd times, it will lead to n plus 1. There will be an error.
for (m = 0; m < sz - 1; m++)
{
if (table[s[m]] % 2 != 0)
{
n++;
}
if (n > 1)
{
return false;
}
}