2018-11-06 面试手撕代码题
2018-11-07 本文已影响0人
囊萤映雪的萤
字符串变成整型数字
#include<iostream>
#include<string>
using namespace std;
int StrToInt(string str) {
if (!str.size()) return 0;
int s = 1;
long long res = 0;
if (str[0] == '-')
s = -1;
for (int i = (str[0] == '-' || str[0] == '+') ? 1 : 0; i < str.size(); ++i) {
if (!('0' <= str[i] && str[i] <= '9')) return 0;
res = res * 10 + str[i] - '0';
}
return res * s;
}
int main() {
string str;
getline(cin, str);
cout << StrToInt(str) << endl;
return 0;
}
取出字符串中连续重复的字符，只保留一个
#include<iostream>
#include<string>
using namespace std;
//输入一串字符串，将其中连续重复的字符保留其中一个，如aabbccbc，保留abcbc
string func(string arr) {
char* p1 = &arr[0];
char* p2 = &arr[1];
while (*p2 != '\0') {
if (*p2 == *p1) {
*p2 = '\0';
p2++;
}
else {
p1++;
*p1 = *p2;
*p2 = '\0';
p2++;
}
}
return arr;
}
int main() {
string str;
cin >> str;
cout << func(str);
system("pause");
return 0;
}
取出字符串中间的重复空格
#include <iostream>
using namespace std;
//输入"___a____b__c___"字符串，"_"代表空格
//将字符串前后的空格去掉，中间的空格保留一个，输出为"a_b_c"
char *deleteTheBlank(char str[]) {
if (str == NULL)
return NULL;
char *p1 = &str[0];
char *p2 = &str[0];
while (*p2 == ' ') {
p2++;
if (p2 == NULL)
return NULL;
}
*p1 = *(p2++);
while (*p2 != '\0') {
if (*p2 != *p1) {
p1++;
*p1 = *p2;
}
p2++;
}
if (*p1 == ' ') {
*p1 = '\0';
}
return str;
}
int main() {
char arr[] = " a b c ";
printf("%s", arr);
cout << "end" << endl;
char *arr_res = deleteTheBlank(arr);
printf("%s", arr_res);
system("pause");
return 0;
}
常见排序算法
三种简单排序：冒泡排序，插入排序，选择排序
这三种排序都是稳定的，时间复杂度是O(n^2)，空间复杂度是O(1)。
#include <iostream>
using namespace std;
//改进版冒泡排序
void bubble_sort(int a[], int len) {
int tmp{};
bool flag{};
for (int i = 0; i < len; i++) {
flag = 0;
for (int j = len - 1; j >= i; j--) {
if (a[j] < a[j - 1]) {
flag = 1;
tmp = a[j];
a[j] = a[j - 1];
a[j - 1] = tmp;
}
}
if (!flag) return;
}
}
//直接插入排序
void insert_sort(int a[], int n) {
int i, j, tmp;
for (i = 1; i < n; i++) {
tmp = a[i];
for (j = i - 1; j >= 0 && a[j] > tmp; j--) {
a[j + 1] = a[j];
}
a[j + 1] = tmp;
}
}
//选择排序
void select_sort(int a[], int len) {
for (int i = 0; i < len; i++) {
int k = i;
int tmp = a[i];
for (int j = i + 1; j < len; j++) {
if (a[j] < tmp) {
tmp = a[j];
k = j;
}
}
a[k] = a[i];
a[i] = tmp;
}
}
int main() {
int arr[10] = { 54,38,96,15,23,72,60,45,83,64 };
//冒泡排序
//bubble_sort(arr, 10);
//直接插入排序
//insert_sort(arr, 10);
//选择排序
select_sort(arr, 10);
for (int i = 0; i < 10; i++) {
cout << arr[i] << ' ';
}
system("pause");
return 0;
}
改进排序：快速排序，堆排序，归并排序，希尔排序，基数排序
快速排序
时间复杂度O(nlogn)，空间复杂度O(1)，不稳定
#include <iostream>
using namespace std;
//快速排序
void quick_sort(int a[], int left, int right) {
if (left >= right) return;
int i = left;
int j = right;
int tmp = a[left];
while (i < j) {
while (a[j] >= tmp && i<j) {
j--;
}
while (a[i] <= tmp && i < j) {
i++;
}
if (i < j) {
int t = a[i];
a[i] = a[j];
a[j] = t;
}
}
a[left] = a[i];
a[i] = tmp;
quick_sort(a, left, i - 1);
quick_sort(a, i + 1, right);
return;
}
int main() {
int arr[10] = { 54,38,96,15,23,72,60,45,83,64 };
//快速排序
quick_sort(arr, 0, 9);
for (int i = 0; i < 10; i++) {
cout << arr[i] << ' ';
}
system("pause");
return 0;
}
堆排序
时间复杂度O(nlogn)，空间复杂度O(1)，不稳定
#include <iostream>
using namespace std;
void swap(int &a, int &b) {
int tmp = a;
a = b;
b = tmp;
}
//最大堆调整
void maxHeapBuild(int arr[], int index, int end) {
int left = index * 2 + 1;
int right = left + 1;
int largest = index;
if ((left <= end) && (arr[largest] < arr[left])) {
largest = left;
}
if ((right <= end) && (arr[largest] < arr[right])) {
largest = right;
}
if (largest != index) {
swap(arr[index], arr[largest]);
maxHeapBuild(arr, largest, end);
}
}
void heap_sort(int arr[], int len) {
//将数组初始堆进行调整变为最大堆
for (int i = len / 2 - 1; i >= 0; i--) {
maxHeapBuild(arr, i, len - 1);
}
//依次交换第一个和最后一个未排序的数
for (int i = len - 1; i >= 0; i--) {
swap(arr[0], arr[i]);
maxHeapBuild(arr, 0, i - 1);
}
}
int main() {
int arr[10] = { 54,38,96,15,23,72,60,45,83,64 };
//最大堆排序
heap_sort(arr, 10);
for (int i = 0; i < 10; i++) {
cout << arr[i] << ' ';
}
system("pause");
return 0;
}
归并排序
时间复杂度O(nlogn)，空间复杂度O(n)，稳定
#include <iostream>
using namespace std;
void merge(int arr[], int tmp[], int left, int right, int r_end) {
int l_end = right - 1; //左区间终点
int tmp_index = left; //临时数组索引
int num = r_end - left + 1; //两部分区间总的元素个数
//依次比较两部分元素大小，较小的先放进tmp数组
while (left <= l_end && right <= r_end) {
if (arr[left] < arr[right]) {
tmp[tmp_index++] = arr[left++];
}
else {
tmp[tmp_index++] = arr[right++];
}
}
//左区间或者右区间可能还含有剩余元素
while (left <= l_end) {
tmp[tmp_index++] = arr[left++];
}
while (right <= r_end) {
tmp[tmp_index++] = arr[right++];
}
for (int i = 0; i < num; i++, r_end--) {
arr[r_end] = tmp[r_end];
}
}
void m_sort(int arr[], int tmp[], int low, int high) {
if (low >= high) return;
int mid = (low + high) / 2; //拆分点
m_sort(arr, tmp, low, mid); //对前半部分递归做归并排序
m_sort(arr, tmp, mid + 1, high);
merge(arr, tmp, low, mid + 1, high); //将两部分有序区间合并
}
//自顶向下归并排序
void merge_sort(int arr[], int len) {
int *tmp = NULL; //指针初始化指向NULL
tmp = new int[len]; //分配临时数组
if (tmp != NULL) {
m_sort(arr, tmp, 0, len-1);
delete []tmp;
}
}
int main() {
int arr[10] = { 54,38,96,15,23,72,60,45,83,64 };
merge_sort(arr, 10);
for (int i = 0; i < 10; i++) {
cout << arr[i] << ' ';
}
system("pause");
return 0;
}
希尔排序
时间复杂度O(nlogn)-O(n^2)，空间复杂度O(1)，不稳定。
#include <iostream>
using namespace std;
//希尔排序
void shell_sort(int a[], int n) {
int h, i, j, tmp;
for (h = n / 2; h > 0; h = h / 2) {
for (i = h; i < n; i++) {
tmp = a[i];
for (j = i - h; j >= 0 && a[j] > tmp; j-=h) {
a[j + h] = a[j];
}
a[j + h] = tmp;
}
}
}
int main() {
int arr[10] = { 54,38,96,15,23,72,60,45,83,64 };
shell_sort(arr, 10);
for (int i = 0; i < 10; i++) {
cout << arr[i] << ' ';
}
system("pause");
return 0;
}
字符串的复制和赋值
字符串复制
数组复制
void strcpy(char *des,char *src)
{
int i;
for(i=0;src[i]!='\0';i++)
{
des[i] = src[i];
}
des[i] = '\0';
}
指针复制
void strcpy(char *des,char *src)
{
while(*des++ = *src++) ;
}
字符串赋值
- 定义时初始化赋值
char buf[20]="hello world!";
char *str="hello world!"
- 先定义再初始化
char buf[20]; char*str;
buf = "I love china"; //错误，数组名是常量，不能被赋值
strcpy (buf, "I love china");
str = "I love china";
strcpy(str, "I love china"); //段错误，没有给str指针分配内存
- 上述最后一种方法的改正
str = (char *)malloc(sizeof(char)*20);
strcpy(str, "I love china");
链表翻转
struct node {
int val;
node *next;
};
//链表翻转
node *list_reverse(node *head) {
if (head->next = NULL) return;
node *p = head, *q = head, *r = head;
p = head->next;
q = p->next;
p->next = NULL;
while (q != NULL) {
r = q->next;
q->next = p;
p = q;
q = r;
}
head->next = p;
return head;
}
字符串反转
#include <iostream>
using namespace std;
void swap(char &a, char &b) {
char tmp = a;
a = b;
b = tmp;
}
//字符串反转
void reverse(char arr[]) {
int len = strlen(arr);
for (int i = 0; i < len/2; i++) {
swap(arr[i], arr[len - 1 - i]);
}
}
int main() {
char arr1[] = "goodboy";
reverse(arr1);
printf("%s\n", arr1);
system("pause");
return 0;
}
字符串反转可以用来进行循环移位
例如要对goodboy循环右移四位得到boygood，则可以先将字符串分割成前面四位good（即将被循环移位），和后面三位boy。这两部分先自己进行反转，得到doogyob。然后对这个字符串进行整体反转，就可以得到boygood了。怎么样，是不是很奇妙
数组反转
#include <iostream>
using namespace std;
void swap(int &a, int &b) {
int tmp = a;
a = b;
b = tmp;
}
//数组反转
void reverse(int arr[], int len) {
for (int i = 0; i < len / 2; i++) {
swap(arr[i], arr[len - 1 - i]);
}
}
void print_arr(int arr[],int len) {
for (int i = 0; i < len; i++) {
cout << arr[i] << ' ';
}
cout << endl;
}
int main() {
int arr2[] = { 0,1,2,3,4,5 };
int len = sizeof(arr2) / sizeof(arr2[0]);
reverse(arr2, len);
print_arr(arr2, len);
system("pause");
return 0;
}
