IT算法类面试题.docx

IT算法类面试题.docx最长回文字串 Longest Palindromic Substring
将字符串S反转得到V,求二者的最长公共子字符串；注意：求最长公共子字符串的过 程中要判断求得的公共串是否是回文，女0 S = "abacd馆dcabaj S' = 想出来。
采用后缀树也是可以的。
判断整数是否是回文 Determine whether an integer is a palindrome without extra space. 1・首先要考虑负数是否属于回文，这里假设不属于;
几种解法：一是将整数转化为字符形式，但需要额外空间；二是将数字逆转 得到另一个数，判断是否与原数相等，但有可能溢出；
乞…程迨娶衣旳方迭是丛数旳函遍回史回推进判軌…如担簣処弃搏苴星数壬
bool isPalindrome(int x) {
if (x < 0) retUTn false;
int div = 1; while (x / div >= 10) { div *二10; } //算数的量级
wh订e (x != 0) { //也可以用递归代替循环 int 1 二 x / div; //取首数字 int r = x % 10; //取尾数字 if (1 != r) retUTn false;
x = (x % div) / 10; //去除首尾 div /= 100;
}
retUTn true;
Implement regular expression matching with support for "・，and "*， ? Matches any single character.
Matches zero or more of the precedi ng element. 怎样 match *?
可以通过查找字符串中重复字符的个数，然后比较个数； 怎样 match".*"?
If the next character of p is NOT then it must match the current character
of s. Continue pattern matching with the next character of both s and p.
If the next character of p is then we do a brute force exhaustive matching
of 0, 1, or more repeats of current character of p.・・ Until we could not match any more characters.
bool isMatch(const char *s, const char *p) {
assert(s && p);
if (*p ==、0') return *s == '\0‘；
// next char is not must match current character
if (*(p+l) !='*') {
assert(*p !=
return ((*p == *s) II (*p == 7 && *s != '\0!)) && isMatch(s+l, p+1);
}
// next char is
while ((*p == *s) II (*p == 7 && *s != '\0!)) {
if (isMatch(s, p+2)) return true;
s++;
}
return isMatch(s, p+2);
}
Insert into a Cyclic Sorted
本体关键是考虑周全，找出所有caseo
Casel： the list is passed in as NULL
Then handle this special case by creating a new node pointing back to itself and return. Case2： prev^val W x W current^val:
Insert between prev and current.
Case3： x is the maximum or minimum value in the list:
Insert before the head, (ie, the head has the smallest value and its prev—val > head—val.
Case4： Traverses back to the starting point:
Insert befo