검지offer 시리즈---2

1. 피보나치 수열의 N항을 구한다
이 문제는 매우 간단하다. 돌아가는 책에서 모두 이걸로 말한다. 그러나 면접을 볼 때 만약에 돌아가는 것을 쓰면 실망할 것이다. 왜냐하면 돌아가는 효율은 정말 하나의 문제이기 때문이다. 50을 입력하면 기본적으로 결과를 얻을 수 있는 시간은 네가 차를 한 잔 마시기에 충분하다.

#include <iostream>
using namespace std;

// ， 
/*int fabonacci1(int n)
{
	if(n <= 0)
		return 0;
	else if(n == 1)
		return 1;
	else return fabonacci1(n-1)+fabonacci1(n-2);
}*/

int fabonacci2(int n)
{
	int num1 = 0, num2 = 1, num3 = 0;
	int i = 2;
	while(i <= n)
	{
		num3 = num1+num2;
		num1 = num2;
		num2 = num3;
		i++;
	}
	return num3;
}

int main()
{
	int ret2 = fabonacci2(5);
	int ret1 = fabonacci1(5);
	cout<<ret2<<endl;
	cout<<ret1<<endl;
	return 0;
}

검지offer에 수학 공식도 열거해 놓았는데, 나는 파악할 필요가 없다고 생각하지만, 알고리즘을 하는 학우들은 그래도 가서 좀 알아야 한다
2. 정수를 입력하여 바이너리 표현에서 1의 개수를 출력합니다.
이 문제 는 우리 의 대위 연산 의 운용 을 고찰한 것 으로, 면접 문제 로서 당연히 우리 는 가장 좋은 해법 을 기억해야 한다
첫 번째: 직접 1과 연산, 최저위가 1이면 1을 증가한 다음에 전체 수를 오른쪽으로 한 자리를 옮기고 1과 연산을 한다. 이것이 바로 아래의 것이다.

/*int number_of1_in_binary(int m)
{
    int count = 0;
    while(m)
    {
        if(m&1)
            count++;
        m>>=1;
    }
    return count;
}*/

그런데 이렇게 단점이 하나 있는데, 입력한 수가 마이너스면 어떡하지?오른쪽으로 한 명 이동, 왼쪽의 가장 높은 자리에 1을 추가, 마지막에 0XFFFFFF가 되어 사순환에 빠집니다.
두 번째: 우리는 이동 1을 매번 비교한 후에 왼쪽으로 한 자리를 옮긴 다음에 연산을 할 수 있다. 바로 아래의 것이다.

/*int number_of1_in_binary(int m)
{
    int count = 0, flag = 1;
    while(flag)// flag ， 32 
    {
        if(m&flag)
            count++;
        flag = flag<<1;
    }
    return count;
}*/

그런데 이렇게 32번이나 움직였어요. 좀 많죠?다른 방법은 없습니까?
세 번째 방법: 한 수의 7, 2진법 111, 7-1=6의 2진법은 110이고, 그 다음에 &7=110은 6, 6-1=5의 2진법은 101이고, 그 다음에 &6=100은 4, 4-1=3의 2진법은 011이고, 그 다음에 &4=0이다. 우리는 매번 이 수를 -1로 하고 이 수를 얻으면 원래 이 수의 마지막 오른쪽의 1이 0으로 변하는 값을 발견한다. 이로써 우리는 다음과 같은 해법을 얻었다.

int number_of1_in_binary(int m)
{
    int count = 0;
    while(m)
    {
        ++count;
        m = (m-1)&m;
    }
    return count;
}

3. 라이브러리 함수 파워(double base, double exponent)를 실현하고 라이브러리 함수를 사용하지 않으며 대수 문제를 고려하지 않습니다.
만약 네가 붓을 한 번 휘두르면, 한 가지 안에 다음과 같은 코드를 쓴다. 그러면 너는 나와 같은 사람, 다른 사람의 offer 널뛰기를 하는 사람이다

double Power(double base, int exp)
{
    double ret = 1.0;
    while(exp)
    {   
        ret *= base;
        exp--;
    }   
    return ret;
}

1.지수가 마이너스면 어떡하죠?
2. 만약 지수가 마이너스이고 밑바닥이 0이라면 어떻게 합니까?0의 꼴찌는 의미가 없어요.
여기에 고려한 이 두 가지를 더하면, 우리는 우리의 코드를 보완할 것이다

bool flag = true;

bool equal(double m, double n)
{
	if(m-n > -0.000001 && m-n < 0.000001)
		return true;
	else
		return false;
}
double power(double base, double exp)
{
	double ret = 1.0;
	while(exp)
	{
		ret *= base;
		exp--;
	}
	return ret;
}

double Power(double base, int exp)
{
	if(equal(base, 0.0) && exp < 0)
	{
		flag  = false;
		return 0.0;
	}
	unsigned int temp = (unsigned int)exp;
	if(exp < 0)
		temp = 0-exp;
	double ret = power(base, temp);
	if(exp<0) return 1.0/ret;
	return ret;
}

여기에 이러한 미세한 프로그래밍 지식도 고찰하였는데, 부동점수가 어떻게 0과 비교되고, 오류가 어떻게 되돌아오는지에 대해 더욱 좋다
4. 숫자를 입력하여 1에서 최대 n자리 십진수를 인쇄한다. 예를 들어 3을 입력하고 1에서 999까지의 모든 숫자를 인쇄한다.
만약 우리가 반응이 빠르다면, 이 가장 큰 수를 먼저 구하고 인쇄할 수 있다는 것을 곧 생각할 수 있을 것이다.

void print_to_max_number(int n)
{
    int m = 1;
    while(n)
    {   
        m *= 10; 
        n--;
    }   
    for(int i = 1; i < m; i++)
        cout<<i<<endl;
}

그러나 여기서 우리는 대수 문제를 고려하지 않았다. 만약 n이 크면 어떡하지?
대수 문제는 일반적으로 모두 수조나 문자열로 모든 사람을 저장하는데, 여기서 우리는 문자열을 사용한다

bool Increment(char *num)
{
	bool isOverFlow = false;
	int nTakeOver = 0;
	int len = strlen(num);
	int Num;

	for(int i = len-1; i >= 0; i--)
	{
		Num = num[i]-'0'+nTakeOver;
		if(i == len-1)
			Num++;
		if(Num >= 10)
		{
			if(i == 0)
				isOverFlow = true;
			else
			{
				Num -= 10;
				nTakeOver = 1;
				num[i] = Num + '0';
			}
		}
		else
		{
			num[i] = Num + '0';
			break;
		}
	}
	return isOverFlow;
}

void printnum(char *s)
{
	char *p = s;
	while(*p == '0') p++;
	cout<<p<<endl;
}

void print_to_max_number(int n)
{
	if(n <= 0)
		return;
	char *num = new char[n+1];
	memset(num, '0', n);
	num[n] = '\0';
	 
	while(!Increment(num))// ， 
		printnum(num);// 
	delete[] num;
}

5. 단일 체인 테이블의 헤드 포인터와 노드 포인터를 정하고 함수를 정의하여 O(1) 복잡도 내에서 이 노드를 삭제한다.
보통 우리의 사고방식은 반복해서 찾는 것이다. 시간의 복잡도는 O(n)이다. 이 노드의 앞 노드를 찾은 다음에 앞 노드의next를 이 노드의 다음 노드를 가리킨다.
지금 우리는 이미 이 노드를 정했다. 우리는 다른 사고방식으로 바꾸어 이 노드의 다음 노드의 값을 이 노드에 지불한 다음에 이 노드의next 바늘을 다음 노드의 다음 노드를 가리킨다. 이것은 다음 노드로 이 노드를 덮어쓰는 것과 같다. 이 사고방식은 O(1)시간의 복잡도 안에서 이 노드를 삭제할 수 있다.

typedef struct ListNode
{
	int data;
	struct ListNode *next;
}ListNode;

void DeleteNode(ListNode**head, ListNode *node)
{
	if(head == NULL || node == NULL)
		return;

	if(node->next != NULL)
	{
		ListNode *p = node->next;
		node->data = p->data;
		node->next = p->next;

		delete p;
		p = NULL;
	}
	else if(*head == *node)// 
	{
		delete node;
		node = NULL;
		*head = NULL;
	}
	else// 
	{
		ListNode *p = *head;
		while(p->next != node)
			p = p->next;
		p->next = NULL;
		delete node;
		node = NULL;
	}
}

주의해야 할 것은 만약 이 노드가 첫 번째 노드 또는 마지막 노드라면 어떻게 해야 하는가 하는 것이다
6. 하나의 수조를 입력하여 이 수조의 순서를 조정하여 홀수는 수조의 앞에 있고 짝수는 수조의 뒤에 있다
일반적인 사고방식은 뒤로 옮겨다니면서 짝수를 찾으면 이 수 뒤의 모든 수를 한 자리로 옮긴 다음에 이 수를 마지막 위치에 놓는다. 시간의 복잡도는
O(n2), 너무 높아서 문제를 푸는 사고방식이 시원한 지침법을 이용하여 앞뒤에 각각 지침을 하나씩 놓은 다음에 앞지침에서 찾은 짝수와 뒤지침에서 찾은 홀수를 교환하면 된다.
잡음은 O (n)

void ReorderArray(int a[], int len)
{
    if(a == NULL || len <= 0)
        return ;
    int *p = a, *q = a+len-1;
    int temp;
    while(p < q)
    {   
        while(p < q && (*p & 0x1))
            p++;
        while(p < q && !(*q & 0x1))
            q--;
        if(p < q)
        {   
            temp = *p; 
            *p = *q; 
            *q = temp;
        }   
    }   
}

쌍지침법의 응용은 종종 의외의 수확을 얻을 수 있다
7. 연쇄표를 입력하여 이 연쇄표의 밑에서 K번째 노드를 구한다
쌍지침법으로 하나는 첫 번째 노드를 가리키고 하나는 K번째 노드를 가리키며 동시에 뒤로 이동한다. 두 개의 차이는 K이고 하나는 마지막 노드에 도달할 때 다른 하나는 꼴찌의 K번째 노드이다.

SLnode getKnode(SLnode head, int k)
{
    if(head == NULL || head->next == NULL || k == 0)
        return NULL;

    SLnode node1 = head;
    SLnode node2 = head->next;
    while(k >= 1 && node1 != NULL)
    {   
        node1 = node1->next;
        k--;
    }   
    if(node1 == NULL)
        return NULL;
    
    while(node1->next != NULL)
    {   
        node1 = node1->next;
        node2 = node2->next;
    }   
    return node2;
}