1. 一个数组中只有两个数字是出现一次,其他所有数字都出现了两次。找出这两个数字,编程实现。

使用位操作符:

首先把全部的数异或一遍,最后得到的是那两个只出现一次的数异或在一起的值。可知这两个数肯定不同,所以这个异或后的值32位中至少有一位是1。此时用1左移的方法找出最近第几位是1,然后可知在数组中,这一位是1的所有数全部异或在一起就是一个只出现一次的数,这一位是0的所有数异或在一起就是另一个只出现一次的数。

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

void find2NumsAppearOnce(int* arr, int size, int* num1, int* num2) {
    int tmp = 0;
    for (int i = 0; i < size; i++) {
        tmp ^= arr[i];
    }

    int one = 1;
    // 此时tmp等于num1异或num2
    for (int i = 0; i < 32; i++) {
        if ((tmp & one) == 1) {
            break;
        }
        else {
            one <<= 1;
        }
    }

    int tmp1 = 0, tmp2 = 0;
    for (int i = 0; i < size; i++) {
        if ((arr[i] & one) == 1) {
            tmp1 ^= arr[i];
        }
        else if ((arr[i] & one) == 0) {
            tmp2 ^= arr[i];
        }
    }

    *num1 = tmp1;
    *num2 = tmp2;
}

int main() {
    int arr[] = { 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 7 };
    int num1 = -1, num2 = -1;
    find2NumsAppearOnce(arr, 12, &num1, &num2);
    printf("%d %d\n", num1, num2);

    system("pause");
    return 0;
}

使用哈希表

把全部数据加入哈希表中,然后再依次在哈希表中查找哪个数只出现了一次

#define HTCAPACITY 5000

int hash(int key) {
    int index;

    index = key % HTCAPACITY;
    index = (index >= 0) ? index : index + HTCAPACITY;

    return index;
}

void hashInsert(int* value, int* status, int val) {
    int index = hash(val);

    while (status[index] != 0) {
        index++;
    }

    value[index] = val;
    status[index] = 1;
}

int isAppearOnce(int* value, int* status, int val) {
    int count = 0;
    int index = hash(val);

    while (status[index] != 0) {
        if (value[index] == val) {
            count++;
        }
        index++;
    }

    return (count == 1) ? 1 : 0;
}

void find2NumsAppearOnce_hash(int* arr, int size, int* num1, int* num2) {
    int value[HTCAPACITY] = { 0 };
    int status[HTCAPACITY] = { 0 };
    // memset(status, -1, sizeof(int) * HTCAPACITY);

    int count = 0;
    for (int i = 0; i < size; i++) {
        hashInsert(value, status, arr[i]);
    }

    for (int i = 0; i < size; i++) {
        if (isAppearOnce(value, status, value[i])) {
            if (!count) {
                *num1 = value[i];
                count++;
            }
            else {
                *num2 = value[i];
            }
        }
    }   
}

int main() {
    int arr[] = { 1, 2, 2, 3, 3, 4, 5, 5, 6, 6, 7, 7 };
    int num1 = -1, num2 = -1;
    find2NumsAppearOnce_hash(arr, 12, &num1, &num2);
    printf("%d %d\n", num1, num2);

    system("pause");
    return 0;
}

2. 喝汽水,1瓶汽水1元,2个空瓶可以换一瓶汽水,给20元,可以多少汽水。编程实现

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

int drink_soda(int money) {
    int bottle = money;
    int total = 0;
    int emptyBottle = 0;

    while (1) {
        // 喝完bottle瓶汽水
        emptyBottle += bottle;
        total += bottle;
        bottle = 0;

        if (emptyBottle < 2) {
            break;
        }
        // 用emptyBottle汽水换汽水
        bottle += emptyBottle / 2;
        emptyBottle %= 2;
    }

    return total;
}

int main() {
    printf("%d\n", drink_soda(20));

    system("pause");
    return 0;
}

3. 模拟实现strcpy

#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>

char* Strcpy(char* destination, const char* source) {
    assert(destination != NULL && source != NULL);

    int i;
    for (i = 0; source[i] != '\0'; i++) {
        destination[i] = source[i];
    }
    destination[i] = '\0';

    return destination;
}

int main() {
    char a[1024] = "Hello";
    char b[1024] = "hello, world";
    Strcpy(a, b);
    printf("%s\n", a);

    system("pause");
    return 0;
}

4. 模拟实现strcat

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

char* Strcat(char* destination, const char* source) {
    int destPtr = -1, srcPtr = 0;
    while (destination[++destPtr] != '\0');
    while (destination[destPtr++] = source[srcPtr++]);
    return destination;
}

int main() {
    char a[1024] = "Hello";
    char b[1024] = "hello, world";
    Strcat(a, b);
    printf("%s\n", a);

    system("pause");
    return 0;
}
Last modification:November 10th, 2019 at 10:20 am