算法面试题整理

时间：2021-07-23 09:43:20

1. 给出一个正整数，将该整数分解成质因数相乘的形式，例如n=56，它的质因数相乘的结果是：2*2*2*7。

#include<iostream>
using namespace std;
int main() {
int n;
cin >> n;
while (n > 1) {
int i;
for (i = 2; i < n; i++) {
if (n%i == 0) {
cout << i << "*";
                n /= i;
break;
            }
        }
if (i == n) {
cout << n << endl;
break;
        }
    }
    system("pause");
return 0;
}

2. （1的变种）给出一个正整数，将该整数分解成质因数相乘的形式，例如n=56，它的质因数相乘的结果是：

算法面试题整理

#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<set>
#include<map>
#include<stack>
#include<string>
#include<queue>
#include<vector>
using namespace std;
string level1[] = { " - "," "," - " ," - " ," "," - "," - "," - "," - " ," - "," " };
string level2[] = { "| |"," |"," |" ," |" ,"| |","| ","| "," |","| |" ,"| |"," " };
string level3[] = { " "," "," - " ," - " ," - "," - "," - "," "," - " ," - "," * " };
string level4[] = { "| |"," |","| " ," |" ," |"," |","| |"," |","| |" ," |"," " };
string level5[] = { " - "," "," - " ," - " ," "," - "," - "," "," - " ," - "," " };

int main()
{
int n;
cin >> n;
vector<int> ans;
if (n == 1)
    {
        ans.push_back(1);
    }
else
    {
while (n > 1)
        {
for (int i = 2; i <= n; i++)
            {
if (n%i == 0)
                {
                    ans.push_back(i);
                    n /= i;
break;
                }
            }
        }
    }
int len = ans.size();
//level 1
for (int i = 0; i < len - 1; i++)
    {
int t = ans[i];
vector<int> tt;
while (t)
        {
            tt.push_back(t % 10);
            t /= 10;
        }
for (int k = tt.size() - 1; k >= 0; k--)
        {
cout << level1[tt[k]];
        }
cout << level1[10];
    }
int tmp = ans[len - 1];
vector<int> tt;
while (tmp)
    {
        tt.push_back(tmp % 10);
        tmp /= 10;
    }
for (int k = tt.size() - 1; k >= 0; k--)
    {
cout << level1[tt[k]];
    }
cout << endl;
//level 2
for (int i = 0; i < len - 1; i++)
    {
int t = ans[i];
vector<int> tt;
while (t)
        {
            tt.push_back(t % 10);
            t /= 10;
        }
for (int k = tt.size() - 1; k >= 0; k--)
        {
cout << level2[tt[k]];
        }
cout << level2[10];
    }
    tmp = ans[len - 1];
    tt.clear();
while (tmp)
    {
        tt.push_back(tmp % 10);
        tmp /= 10;
    }
for (int k = tt.size() - 1; k >= 0; k--)
    {
cout << level2[tt[k]];
    }
cout << endl;


//level 3
for (int i = 0; i < len - 1; i++)
    {
int t = ans[i];
vector<int> tt;
while (t)
        {
            tt.push_back(t % 10);
            t /= 10;
        }
for (int k = tt.size() - 1; k >= 0; k--)
        {
cout << level3[tt[k]];
        }
cout << level3[10];
    }
    tmp = ans[len - 1];
    tt.clear();
while (tmp)
    {
        tt.push_back(tmp % 10);
        tmp /= 10;
    }
for (int k = tt.size() - 1; k >= 0; k--)
    {
cout << level3[tt[k]];
    }
cout << endl;


//level 4
for (int i = 0; i < len - 1; i++)
    {
int t = ans[i];
vector<int> tt;
while (t)
        {
            tt.push_back(t % 10);
            t /= 10;
        }
for (int k = tt.size() - 1; k >= 0; k--)
        {
cout << level4[tt[k]];
        }
cout << level4[10];
    }
    tmp = ans[len - 1];
    tt.clear();
while (tmp)
    {
        tt.push_back(tmp % 10);
        tmp /= 10;
    }
for (int k = tt.size() - 1; k >= 0; k--)
    {
cout << level4[tt[k]];
    }
cout << endl;
//level 5
for (int i = 0; i < len - 1; i++)
    {
int t = ans[i];
vector<int> tt;
while (t)
        {
            tt.push_back(t % 10);
            t /= 10;
        }
for (int k = tt.size() - 1; k >= 0; k--)
        {
cout << level5[tt[k]];
        }
cout << level5[10];
    }
    tmp = ans[len - 1];
    tt.clear();
while (tmp)
    {
        tt.push_back(tmp % 10);
        tmp /= 10;
    }
for (int k = tt.size() - 1; k >= 0; k--)
    {
cout << level5[tt[k]];
    }
cout << endl;
    system("pause");
return 0;
}

3. 一楼道有N个台阶，上楼每一步可以跨1个台阶或者2个台阶，求走到楼顶总共多少种走法？

#include <iostream>
#include <string>
using namespace std;
int main() {

int n;
cin >> n;
if (n == 1) {
cout << 1 << endl;
    }
else if (n == 2) {
cout << 2 << endl;
    }
int ans1 = 1, ans2 = 2, ans;
for (int i = 3; i <= n; i++) {
        ans = ans1 + ans2;
        ans1 = ans2;
        ans2 = ans;
    }
cout << ans << endl;
    system("pause");
return 0;
}

4. 假设某个链表中只有一个环，请求出环的入口点。

算法面试题整理

typedef struct node {
    char val;
    struct node* next;
}Node;

Node* findEntry(Node * &head) {
if (head == NULL || head->next == NULL) {
return NULL;
    }
    Node *p1 = head;
    Node *p2 = head->next;
    Node *pre = head;
//利用快慢指针找到环所在地，并在环中某点相遇
while (p1 != p2 && p2->next != NULL && p2->next->next != NULL) {
        p1 = p1->next;
        p2 = p2->next->next;
        pre = pre->next->next;
    }
//链表无环存在
if (p1 != p2) {
return NULL;
    }
//此时链表有环存在，并且p1,p2相交，pre为相交点的前驱
    pre->next = NULL;
//此时已经破坏环结构，链表成 Y 形, 计算两个链表长度
    int n = 0, m = 0;
    pre = head;
while (pre != NULL)
    {
        n++;
        pre = pre->next;
    }
while (p2 != NULL) {
        m++;
        p2 = p2->next;
    }
//找出交点
    pre = head;
    p2 = p1;
if (n > m) {
        int k = n - m;
while (k > 0) {
            k--;
            pre = pre->next;
        }
    }
if (m > n) {
        int k = m - n;
while (k > 0) {
            k--;
            p2 = p2->next;
        }
    }
while (pre != NULL && pre != p2) {
        pre = pre->next;
        p2 = p2->next;
    }
return pre;
}

5. 求一个数组在某一滑动窗口内的最大值和最小值之差。（如果写出如下答案，可继续问程序能否有改进的空间，改进的地方在判断最大值和最小值的地方，如果是最大值就没必要判断是否为最小值，这样能减少判断次数）。

改进部分代码：
if (ivec[i] > max) {
        max = ivec[i];
    }
else if (ivec[i] < min)
    {
        min = ivec[i];
}

正式答案：
#include<iostream>
#include<vector>
using namespace std;
int main() {
int n, m;
cin >> n >> m;
//这种情况不存在，输出no
if (m > n) {
cout << "no" << endl;
    }
vector<int> ivec(n);
for (int i = 0; i < n; i++) {
cin >> ivec[i];
    }
int max = ivec[0];
int min = ivec[0];
for (int i = 1; i < m; i++) {
if (ivec[i] > max) {
            max = ivec[i];
        }
if (ivec[i] < min) {
            min = ivec[i];
        }
    }
cout << max - min << " ";
for (int i = m; i < n;i++) {
if (ivec[i] > max) {
            max = ivec[i];
        }
if (ivec[i] < min) {
            min = ivec[i];
        }
cout << max - min << " ";
    }
cout << endl;
    system("pause");
return 0;
}

6. 对一个包含1-n的n个元素的乱序数组，要求将其排成有序数组，时间复杂度O(n)，空间复杂度O(1)。不允许采用直接赋值的方式

void sortArray(int a[],int n) { 
    for (int i = 1; i <= n;i++) {
if (a[i] != i) {
            int tmp = a[i];
a[i] = a[a[i]];
a[a[i]] = tmp;
        }
    }
}

未完待续。。。
标签：

相关文章