目录
力扣(LeetCode)定期刷题，每期10道题，业务繁重的同志可以看看我分享的思路，不是最高效解决方案，只求互相提升。
第1题：配对交换
试题要求如下：
解答思路：
分别取出num的偶数位与奇数位
然后让偶数位右移一位奇数位左移一位
让移位后的偶数与奇数异或即可得最终结果
回答（C语言）：
-
int exchangeBits(int num){
-
int even_number =
0xaaaaaaaa;
//1010 1010 ...... 取出偶数
-
int uneven_number =
0x55555555;
//0101 0101 ...... 取出奇数
-
-
even_number = num & even_number;
-
uneven_number = num & uneven_number;
-
-
even_number = even_number >>
1;
-
uneven_number = uneven_number <<
1;
-
-
return even_number | uneven_number;
-
}
运行效率如下所示：
第2题：比较字符串最小字母出现频次
试题要求如下：
解答思路：
回答（C语言）：
-
/**
-
* Note: The returned array must be malloced, assume caller calls free().
-
*/
-
#define NUM 26
-
int QureySmallWord (char *str, int *hash)
-
{
-
memset(hash,
0, NUM *
sizeof(
int));
-
int len =
strlen(str);
-
int res =
0;
-
for (
int i =
0; i < len; i++) {
-
// 统计字符串中各个字符出现的频次，已默认是字典序
-
hash[str[i] -
'a']++;
-
}
-
for (
int i =
0; i < NUM; i++) {
-
// 获取字符串中最小字母的出现频次，即hash表中第一个非零值
-
if (hash[i] >
0) {
-
res = hash[i];
-
break;
-
}
-
}
-
//printf("res %d\n", res);
-
return res;
-
}
-
int* numSmallerByFrequency(char ** queries, int queriesSize, char ** words, int wordsSize, int* returnSize){
-
int *array_q = (
int *)
malloc(queriesSize *
sizeof(
int));
-
int *array_w = (
int *)
malloc(wordsSize *
sizeof(
int));
-
int *hash = (
int *)
malloc(NUM *
sizeof(
0));
-
// queries各个字符串（按字典序比较）最小字母的出现频次
-
for (
int i =
0; i < queriesSize; i++) {
-
array_q[i] = QureySmallWord(queries[i], hash);
-
}
-
// words各个字符串（按字典序比较）最小字母的出现频次
-
for (
int i =
0; i < wordsSize; i++) {
-
array_w[i] = QureySmallWord(words[i], hash);
-
}
-
// 依次查找queries中字符串满足f(queries[i]) < f(W[0..j])的个数
-
int *res = (
int *)
malloc(queriesSize *
sizeof(
int));
-
int count =
0;
-
for (
int i =
0; i < queriesSize; i++) {
-
int temp =
0;
-
for (
int j =
0; j < wordsSize; j++) {
-
//printf("array_q[%d] %d array_w[%d] %d", i, array_q[i], j, array_w[j]);
-
if (array_q[i] < array_w[j]) {
-
temp++;
-
}
-
}
-
res[count++] = temp;
-
}
-
*returnSize = count;
-
return res;
-
}
运行效率如下所示：
第3题：交替位二进制
试题要求如下：
解答思路：
每次用 n&1 位运算取出最后一位，并与上一次取出的最后一位比较，一样的话返回false。
回答（C语言）：
-
bool hasAlternatingBits(int n){
-
int pre = n &
1;
-
n >>=
1;
-
-
while (n !=
0) {
-
if ((n &
1) == pre) {
-
return
false;
-
}
-
pre = n &
1;
-
n >>=
1;
-
}
-
-
return
true;
-
}
运行效率如下所示：
第4题：二进制间距
试题要求如下：
解答思路：
1、利用 1 与数字N进行&运算检查二进制第一位是否为1；
2、逐步将数字二进制值向右移动一位:N = N>>1；
3、N <= 0 时终止。
回答（C语言）：
-
int binaryGap(int N){
-
int distance =
0, max =
0,distanceon =
0;
-
-
while (N >
0){
-
if((N &
1) !=
0){
-
distanceon =
1;
-
-
if(distance > max){
-
max = distance;
-
}
-
-
distance =
0;
-
}
-
-
distance+=(distanceon);
-
N = N >>
1;
-
}
-
-
return max;
-
}
运行效率如下所示：
第5题：最后一块石头的重量
试题要求如下：
解答思路：
1、5个石头撞四次 6个石头撞5次 N个石头撞N-1次；
2、降序，撞前两个。得到的新石头放回去，空缺位置置0；
3、重复第二步；
4、最后剩下一个，就是答案。
回答（C语言）：
-
int Cmp(const void* a, const void* b)
-
{
-
return *(
int*)b - *(
int*)a;
-
}
-
-
int lastStoneWeight(int* stones, int stonesSize)
-
{
-
int time = stonesSize -
1;
-
int buf[
30] = {
0};
-
memcpy(buf, stones, stonesSize *
sizeof(
int));
-
-
while (time >
0) {
-
qsort(buf,
30,
sizeof(
int), Cmp);
-
buf[
0] -= buf[
1];
-
buf[
1] =
0;
-
time--;
-
}
-
-
return buf[
0];
-
}
运行效率如下所示：
第6题：旋转数字
试题要求如下：
解答思路：
遍历从 1 到 N 的每个数字 X，判断 X 是否为好数。如果 X 中存在 3、4、7 这样的无效数字，则 X 不是一个好数。如果 X 中不存在 2、5、6、9 这样的旋转后会变成不同的数字，则 X 不是一个好数。否则，X 可以旋转成一个不同的有效数字。
回答（C语言）：
-
/*
-
* 函数功能：检测是否是好数；是好数返回1，否则返回0
-
* 函数输入：当前检测的数num
-
* 函数返回值：0或1
-
*/
-
int CheckDigits(int num)
-
{
-
int rest;
-
int flag =
0;
-
-
while(num >
0) {
-
rest = num %
10;
-
/* 遇到垃圾数直接返回0 */
-
if (rest ==
3 || rest ==
4 || rest ==
7) {
-
return
0;
-
}
-
/* 遇到有可能存在的好数先标记一下 */
-
if (rest ==
2 || rest ==
5 || rest ==
6 || rest ==
9) {
-
flag =
1;
-
}
-
num = num /
10;
-
}
-
-
/* 如果不存在垃圾数，且有好数则统计加1 */
-
if (flag ==
1) {
-
return
1;
-
}
-
-
return
0;
-
}
-
int rotatedDigits(int N){
-
int ret =
0;
-
for (
int i =
1; i <= N; i++) {
-
/* 逐个检测，好数就加1 */
-
ret += CheckDigits(i);
-
}
-
return ret;
-
}
运行效率如下所示：
第7题：十进制整数的反码
试题要求如下：
解答思路：
举个例子 6是110 那么他的反码是他与111异或得到的001。所以找到比N大的每位都为1的数，与N进行异或。
回答（C语言）：
-
int bitwiseComplement(int N){
-
int num =
1;
-
-
while(num < N){
-
num = (num <<
1) +
1;
-
}
-
-
return N ^ num;
-
}
运行效率如下所示：
第8题：连续子数组的最大和
试题要求如下：
解答思路：
动态规划：
回答（C语言）：
-
int maxSubArray(int* nums, int numsSize){
-
int sum=nums[
0],max=nums[
0];
-
-
for(
int i=
1;i<numsSize;i++)
-
{
-
sum=(sum>
0)?(sum+nums[i]):nums[i];
-
max=(max>sum)?max:sum;
-
}
-
-
return max;
-
}
运行效率如下所示：
第9题：有序数组中出现次数超过25%的元素
试题要求如下：
回答（C语言）：
-
int findSpecialInteger(int* arr, int arrSize){
-
int i =
1,cou =
0;
-
int temp = arr[
0];
-
-
while(i < arrSize){
-
if(temp == arr[i]){
-
cou++;
-
-
if(cou*
4 >= arrSize){
-
break;
-
}
-
}
-
else{
-
cou =
0;
-
}
-
-
temp = arr[i];
-
i++;
-
}
-
-
return temp;
-
}
运行效率如下所示：
第10题：数组中字符串匹配
试题要求如下：
解答思路：
C语言使用strstr库函数来进行子字符串匹配。strstr(str1,str2) 函数用于判断字符串str2是否是str1的子串。如果是，则该函数返回 str1字符串从 str2第一次出现的位置开始到 str1结尾的字符串；否则，返回NULL。
回答（C语言）：
-
char ** stringMatching(char ** words, int wordsSize, int* returnSize){
-
if ((words ==
NULL) || (wordsSize <=
0)) {
-
*returnSize =
0;
-
return
NULL;
-
}
-
-
char** res = (
char**)
malloc(
sizeof(
char*) * wordsSize);
-
int index =
0;
-
-
for (
int i =
0; i < wordsSize; i++) {
-
for (
int j =
0; j < wordsSize; j++) {
-
if (i != j) {
-
if (
strstr(words[j], words[i])) {
-
res[index] = (
char*)
malloc(
sizeof(
char) * (
strlen(words[i]) +
1));
-
memcpy(res[index], words[i],
strlen(words[i]) +
1);
-
index++;
-
break;
-
}
-
}
-
}
-
}
-
-
*returnSize = index;
-
return res;
-
-
}
运行效率如下所示：
转载：https://blog.csdn.net/m0_38106923/article/details/106488259
查看评论