1. 不使用任何中间变量如何将a、b的值进行交换
-
方法一：加和再减
缺点是加减运算可能导致溢出
void swap(int &a, int &b) { a = a + b; b = a - b;//此时b已经获取了原来a的值 a = a - b;//加和减去原来的a值 } -
方法二：异或操作
void swap(int &a, int &b) { a = a ^ b; b = b ^ a;//此时a为异或的中间值，中间值异或b就得到a a = a ^ b;//中间值异或a(b的值就是原来的a)得到b(赋值给a) }
2. 求一个字符串最长回文子串
//马拉车算法
string longestPalindrome(string s) {
int n = s.size();
if (n < 2) return s;
string ss = "#";
for (auto c : s) {
ss += c;
ss += '#';
}
int nn = ss.size();
vector<int> dp(nn, 0);
int mid = 0, right = 0, maxMid = 0, maxLen = 0;
for (int i = 1; i < nn; i++) {
if (i < right) {
int j = 2 * mid - i;
if (j >= 0) {
dp[i] = min(right-i, dp[j]);
}
}
while (i-dp[i]-1 >= 0 && i+dp[i]+1 < nn && ss[i-dp[i]-1] == ss[i+dp[i]+1]) {
dp[i]++;
}
if (i + dp[i] > right) {
right = i + dp[i];
mid = i;
}
if (maxLen < dp[i]) {
maxLen = dp[i];
maxMid = i;
}
}
int start = (maxMid - maxLen) / 2;
return s.substr(start, maxLen);
}
3. 最长公共子序列
\[dp[i][j] = \begin{cases} 0 & 若i=0或j=0\\ dp[i-1][j-1]+1 & 若i,j>0且x_i = y_j \\ max(dp[i][j-1], dp[i-1][j]) & 若i,j > 0 且 x_i \ne y_j \end{cases}\]int longestCommonSubsequence(string text1, string text2) {
int m = text1.size();
int n = text2.size();
int dp[m+1][n+1];
bzero(dp, sizeof(dp));
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (text1[i] == text2[j]) {
dp[i+1][j+1] = dp[i][j] + 1;
} else {
dp[i+1][j+1] = max(dp[i][j+1], dp[i+1][j]);
}
}
}
return dp[m][n];
}
4. 编程实现strcpy函数
/**
* v5.6.3
* strcpy - Copy a %NUL terminated string
* @dest: Where to copy the string to
* @src: Where to copy the string from
*/
char *strcpy(char *dest, const char *src) {
char *tmp = dest;
while ((*dest++ = *src++) != '\0')
/* nothing */;
return tmp;
}
5. 编程实现strncpy函数
/**
* v5.6.3
* strncpy - Copy a length-limited, C-string
* @dest: Where to copy the string to
* @src: Where to copy the string from
* @count: The maximum number of bytes to copy
*
* The result is not %NUL-terminated if the source exceeds
* @count bytes.
*
* In the case where the length of @src is less than that of
* count, the remainder of @dest will be padded with %NUL.
*
*/
char *strncpy(char *dest, const char *src, size_t count) {
char *tmp = dest;
while (count) {
if ((*tmp = *src) != 0)
src++;
tmp++;
count--;
}
return dest;
}
6. 编程实现strcat函数
/**
* v5.6.3
* strcat - Append one %NUL-terminated string to another
* @dest: The string to be appended to
* @src: The string to append to it
*/
char *strcat(char *dest, const char *src) {
char *tmp = dest;
while (*dest)
dest++;
while ((*dest++ = *src++) != '\0')
;
return tmp;
}
7. 编程实现strncmp函数
/**
* v5.6.3
* strncmp - Compare two length-limited strings
* @cs: One string
* @ct: Another string
* @count: The maximum number of bytes to compare
*/
int strncmp(const char *cs, const char *ct, size_t count) {
unsigned char c1, c2;
while (count) {
c1 = *cs++;
c2 = *ct++;
if (c1 != c2)
return c1 < c2 ? -1 : 1;
if (!c1)
break;
count--;
}
return 0;
}
8. 编程实现memcpy函数
-
函数原型：
void *memcpy(void *dest, void *src, unsigned int count); -
参数说明：dest为目的字符串，src为源字符串，count为要拷贝的字节数。
-
所在库名：#include
-
函数功能：将字符串src中的前n个字节拷贝到dest中。
-
返回说明：src和dest所指内存区域不能重叠，函数返回void*指针。
-
//注意memcpy返回的是void*类型
/**
* v5.6.3
* memcpy - Copy one area of memory to another
* @dest: Where to copy to
* @src: Where to copy from
* @count: The size of the area.
*
* You should not use this function to access IO space, use memcpy_toio()
* or memcpy_fromio() instead.
*/
void *memcpy(void *dest, const void *src, size_t count) {
char *tmp = dest;
const char *s = src;
while (count--)
*tmp++ = *s++;
return dest;
}
9. 编程实现memmove函数
/**
*v5.6.3
* memmove - Copy one area of memory to another
* @dest: Where to copy to
* @src: Where to copy from
* @count: The size of the area.
*
* Unlike memcpy(), memmove() copes with overlapping areas.
*/
void *memmove(void *dest, const void *src, size_t count) {
char *tmp;
const char *s;
if (dest <= src) {
tmp = dest;
s = src;
while (count--)
*tmp++ = *s++;
} else {
tmp = dest;
tmp += count;
s = src;
s += count;
while (count--)
*--tmp = *--s;
}
return dest;
}
10. 编程实现memcmp函数
/**
* v5.6.3
* memcmp - Compare two areas of memory
* @cs: One area of memory
* @ct: Another area of memory
* @count: The size of the area.
*/
int memcmp(const void *cs, const void *ct, size_t count) {
const unsigned char *su1, *su2;
int res = 0;
for (su1 = cs, su2 = ct; 0 < count; ++su1, ++su2, count--)
if ((res = *su1 - *su2) != 0)
break;
return res;
}
11. 求完全二叉树的最后一个结点（快手一面）
完全二叉树只有最后一层结点可能不满，其它层的结点都是满的。如果最后一层结点也是满的，那就是满二叉树，满二叉树也是完全二叉树。
TreeNode *getLastNode(TreeNode *root) {
if(root == NULL || root->left == NULL) //递归出口，如果根为空，或者根为叶子节点。完全二叉树只需判定左儿子是否为空即可判定是否为叶子节点
return root;
int lh = getHeight(root->left); //左子树高度
int rh = getHeight(root->right); //右子树高度
if(lh > rh)
return getLastNode(root->left);
else
return getLastNode(root->right);
}
int getHeight(TreeNode *root) {
int res = 0;
while (root) {
++res;
root = root->left;
}
return res;
}
12. 求小数的循环节（快手一面）
两个整数相除，如果得到结果是无限循环小数，求出循环节。循环节是无限循环小数中循环出现的那一部分，比如 1 / 7 = 0.1428571428571428…，那么142857就是循环节；1 / 3 = 0.33333，3就是循环节。如果没有循环节，则返回0。
//参考：http://www.jeepxie.net/article/874643.html
string solve(int n, const int d) {
n %= d;
map<int, int> Pos; //记录每一次的 被除数 以及 被除数在循环小数中的位置
string ans; //保存除下来的小数
while (1) {
n *= 10;
if (Pos.find(n) != Pos.end()) { //被除数已经出现过，通过哈希表获取长度，返回循环节
int len = ans.size() - Pos[n];
return ans.substr(Pos[n], len);
}
Pos[n] = ans.size(); // 如果被除数没有出现过，则把 被除数的位置 更新为ans的长度
if (n < d) { //被除数 小于 除数的时候 ans补上字符 0
ans += "0";
continue;
}
ans += (char)(n / d + '0'); //整数转换成字符
n %= d;
if (n == 0) { //如果不是循环小数
break;
}
}
return "";
}