当前位置： 代码迷 >> 综合 >> 程序员面试题(C++ 实现) - Day3
  详细解决方案

程序员面试题(C++ 实现) - Day3

热度：64   发布时间：2023-10-14 23:00:48.0

文章目录

    • 说明
    • 今日题目一览
      • 1. 数值的整数次方
      • 2. 调整数组顺序使奇数位于偶数前面
      • 3. 链表中倒数第 k 个结点
      • 4. 反转链表
      • 5. 合并两个排序的链表
    • 联系博主

说明

  • 以下题目均来自于牛客网
  • 以下代码用 C++11 编写
  • 以下代码均已编译通过(Compile by MINGW)
  • 以下代码均有测试案例(Main function)
  • 以下代码均已进行优化或部分优化(Optimize)
  • 以下代码均有注释(Comment)
  • 部分题目附有解析(Analysis)
  • 如有错误或侵权，请联系博主

今日题目一览

  1. 数值的整数次方
  2. 调整数组顺序使奇数位于偶数前面
  3. 链表中倒数第 k 个结点
  4. 反转链表
  5. 合并两个排序的链表

1. 数值的整数次方

问题描述

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

解析

主要用到以下知识点：

  • 基本运算：X1 = X， X2 = X1 * X1，…
  • 奇数次幂可以拆分成偶数次幂和奇数次幂的乘积
  • 负数次幂等于正数次幂的倒数
  • 应用迭代的思想

实现

/* 给定一个double类型的浮点数base和int类型的整数exponent。 求base的exponent次方。*/#include <iostream>using namespace std;double Power(double base, int exponent) {
    if(exponent > 0) {
    if(exponent == 1)return base;if(exponent % 2 == 0)return Power(base, exponent / 2) * Power(base, exponent / 2);elsereturn Power(base, exponent / 2) * Power(base, exponent / 2 + 1);} else if (exponent == 0) {
    return 1;} else {
    return 1 / Power(base, 0 - exponent);}
}int main(int argc, char const *argv[]) {
    //Testdouble PI = 3.1415926;cout << Power(PI, 0) << endl;cout << Power(PI, 1) << endl;cout << Power(PI, 2) << endl;return 0;
}

输出结果

1
3.14159
9.8696

2. 调整数组顺序使奇数位于偶数前面

问题描述

输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。

解析

这个暂且没有好的办法，下面两种方法都是直接遍历

然后第一种方法就是进行原地的奇偶交换

第二种方法就是新申请空间，然后将奇数或者偶数部分提取出来，然后进行合并

两种方法都差不多

实现

/* 输入一个整数数组，实现一个函数来调整该数组中数字的顺序， 使得所有的奇数位于数组的前半部分，所有的偶数位于数组的后半部分， 并保证奇数和奇数，偶数和偶数之间的相对位置不变。*/#include <iostream>
#include <vector>
#include <algorithm>using namespace std;// 方法一
void reOrderArray1(vector<int> &array) {
    for (int i = 0; i < array.size(); i++) {
    for (int j = array.size() - 1; j > i; j--) {
    if (array[j] % 2 == 1 && array[j - 1] % 2 == 0) {
     //前偶后奇交换swap(array[j], array[j - 1]);}}}
}// 方法二
void reOrderArray2(vector<int> &array) {
    vector<int> array_temp;vector<int>::iterator ib1, ie1;ib1 = array.begin();for (; ib1 != array.end();) {
     //遇见偶数，就保存到新数组，同时从原数组中删除if (*ib1 % 2 == 0) {
    array_temp.push_back(*ib1);ib1 = array.erase(ib1);} else {
    ib1++;}}vector<int>::iterator ib2, ie2;ib2 = array_temp.begin();ie2 = array_temp.end();for (; ib2 != ie2; ib2++) {
               //将新数组的数添加到老数组array.push_back(*ib2);}
}//奇数返回真
bool isOk(int n) {
    return ((n & 1) == 1);
}// 方法三
void reOrderArray3(vector<int> &array) {
    //用的STL　stable_partition 这个函数stable_partition(array.begin(), array.end(), isOk);
}int main(int argc, char const *argv[]) {
    //Testint array[8] = {
    1, 8, 2, 3, 7, 5, 6, 4};cout << "初始向量:\n18237564\n------\n";vector<int> vec1(array, array + 8);vector<int> vec2(array, array + 8);vector<int> vec3(array, array + 8);reOrderArray1(vec1);reOrderArray2(vec2);reOrderArray3(vec3);vector<int>::iterator it1 = vec1.begin();for(; it1 != vec1.end(); it1++)cout << *it1;cout << "\n------\n";vector<int>::iterator it2 = vec2.begin();for(; it2 != vec2.end(); it2++)cout << *it2;cout << "\n------\n";vector<int>::iterator it3 = vec3.begin();for(; it3 != vec3.end(); it3++)cout << *it3;return 0;
}

输出结果

初始向量:
18237564
------
13758264
------
13758264
------
13758264

3. 链表中倒数第 k 个结点

问题描述

输入一个链表，输出该链表中倒数第k个结点。

解析

建立两个指针，ptr1、ptr2，ptr 先指像第 k 个结点，然后同时移动两个指针，ptr1 走完时，ptr2即为所求结果

实现

/* 输入一个链表，输出该链表中倒数第k个结点。*/#include <iostream>
#include <stdlib.h>using namespace std;struct ListNode {
    int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {
    }
};struct ListNode *createList() {
    struct ListNode *head = new ListNode(0);struct ListNode *ret = head;for(int i = 1; i < 10; i++) {
    struct ListNode *p = new ListNode(i);ret->next = p;ret = ret->next;}return head;
}void deleteList(struct ListNode *list) {
    struct ListNode *p = list;while(p != NULL) {
    list = p->next;free(p);p = list;}free(p);
}void printList(ListNode *head) {
    while(head != NULL) {
    cout << head->val << " ";head = head->next;}cout << endl;
}ListNode *FindKthToTail(ListNode *p, unsigned int k) {
    //if(!p) return nullptr;ListNode *p1 = p;for(int i = 0; i != k; ++i)if(p1 == NULL)return NULL;elsep1 = p1->next;while(p1) {
    p1 = p1->next;p = p->next;}return p;
}int main(int argc, char const *argv[]) {
    //Teststruct ListNode *head = createList();printList(head);struct ListNode *tail = FindKthToTail(head, 3);printList(tail);deleteList(head);deleteList(tail);return 0;
}

输出结果

0 1 2 3 4 5 6 7 8 9 
7 8 9

4. 反转链表

问题描述

输入一个链表，反转链表后，输出新链表的表头。

解析

这个请参考我的另外一篇博客：链表大全

主要是多个链表变量的重新指向。

实现

/* 输入一个链表，反转链表后，输出新链表的表头。*/#include <iostream>
#include <stack>
#include <stdlib.h>using namespace std;struct ListNode {
    int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {
    }
};struct ListNode *createList() {
    struct ListNode *head = new ListNode(0);struct ListNode *ret = head;for(int i = 1; i < 10; i++) {
    struct ListNode *p = new ListNode(i);ret->next = p;ret = ret->next;}return head;
}void deleteList(struct ListNode *list) {
    struct ListNode *p = list;while(p != NULL) {
    list = p->next;free(p);p = list;}free(p);
}void printList(ListNode *head) {
    while(head != NULL) {
    cout << head->val << " ";head = head->next;}cout << endl;
}ListNode *ReverseList1(ListNode *pHead) {
    if(pHead == NULL || pHead -> next == NULL)return pHead;ListNode *p = pHead;stack<ListNode * > s;while(p -> next) {
    s.push(p);p = p -> next;}ListNode *head = p;while(!s.empty()) {
    p -> next = s.top();p = p -> next;s.pop();}p -> next = NULL;return head;
}ListNode *ReverseList2(ListNode *pHead) {
    if(pHead == NULL || pHead -> next == NULL)return pHead;ListNode *p = pHead;ListNode *q = pHead -> next;ListNode *r = NULL;pHead -> next = NULL;while(q) {
    r = q -> next;q -> next = p;p = q;q = r;}return p;
}ListNode *ReverseList3(ListNode *pHead) {
    if(pHead == NULL || pHead -> next == NULL)return pHead;ListNode *p = pHead -> next;ListNode *q = NULL;while(p -> next) {
    q = p -> next;p -> next = q -> next;q -> next = pHead -> next;pHead -> next = q;}p -> next = pHead;pHead = p -> next -> next;p -> next -> next = NULL;return pHead;
}int main(int argc, char const *argv[]) {
    //Teststruct ListNode *head = createList();printList(head);struct ListNode *reverse1 = ReverseList1(head);printList(reverse1);deleteList(head);deleteList(reverse1);return 0;
}

输出结果

0 1 2 3 4 5 6 7 8 9
9 8 7 6 5 4 3 2 1 0

5. 合并两个排序的链表

问题描述

输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。

解析

这个请参考我的另外一篇博客：链表大全

这个想法类似与归并排序(Merge Sort)

注意：这是一个稳定的合并

实现

/* 输入两个单调递增的链表，输出两个链表合成后的链表， 当然我们需要合成后的链表满足单调不减规则。*/#include <iostream>
#include <stdlib.h>using namespace std;struct ListNode {
    int val;struct ListNode *next;ListNode(int x) :val(x), next(NULL) {
    }
};struct ListNode *createList() {
    struct ListNode *head = new ListNode(0);struct ListNode *ret = head;for(int i = 1; i < 10; i++) {
    struct ListNode *p = new ListNode(i);ret->next = p;ret = ret->next;}return head;
}void deleteList(struct ListNode *list) {
    struct ListNode *p = list;while(p != NULL) {
    list = p->next;free(p);p = list;}free(p);
}void printList(ListNode *head) {
    while(head != NULL) {
    cout << head->val << " ";head = head->next;}cout << endl;
}ListNode *Merge(ListNode *pHead1, ListNode *pHead2) {
    if(pHead1 == NULL)return pHead2;else if(pHead2 == NULL)return pHead1;ListNode *newhead = NULL;if(pHead1->val < pHead2->val) {
    newhead = pHead1;newhead->next = Merge(pHead1->next, pHead2);} else {
    newhead = pHead2;newhead->next = Merge(pHead1, pHead2->next);}return newhead;
}int main(int argc, char const *argv[]) {
    //Teststruct ListNode *head1 = createList();printList(head1);struct ListNode *head2 = createList();printList(head2);struct ListNode *head_merge = Merge(head1, head2);printList(head_merge);deleteList(head1);deleteList(head2);deleteList(head_merge);return 0;
}

输出结果

0  1  2  3  4  5  6  7  8  9
0  1  2  3  4  5  6  7  8  9
0  0  1  1  2  2  3  3  4  4  5  5  6  6  7  7  8  8  9  9

联系博主

邮箱：Neverland_LY@163.com

  相关解决方案

代码迷 - 您身边的软件异常，代码异常，编程异常助手（发现，解决，分享）
Copyright © 2009-2013 DAIMAMI.COM. All rights reserved.