面试题34：丑数
我们把只包含因子2，3，5的数称为丑数。求按从小到大排列的第1500个丑数。例如，6，8都是丑数，但是14不是。习惯上，我们把1当做第一个丑数。
leetcode链接 https://leetcode-cn.com/problems/chou-shu-lcof/class Solution { public: int min(int a, int b, int c) { int tmp; if (a > b) {tmp = b;} else {tmp = a;} if (c < tmp) { tmp = c; } return tmp; } int nthUglyNumber(int n) { if (n <= 0) { return 0; } int result[n]; result[0] = 1; int index = 1; int* T2 = result; int* T3 = result; int* T5 = result; while(index < n) { result[index] = min(2*(*T2), 3*(*T3), 5*(*T5)); while(2*(*T2) <= result[index]) { T2++; } while(3*(*T3) <= result[index]) { T3++; } while(5*(*T5) <= result[index]) { T5++; } ++index; } return result[n-1]; } };
解题思路：第一种思路遍历，判断每个数是不是丑数。会超时
class Solution {
public:
bool checkUgly(int i)
{
while(i % 2 == 0)
{
i = i / 2;
}
while(i % 3 == 0)
{
i = i / 3;
}
while(i % 5 == 0)
{
i = i / 5;
}
return i == 1;
}
int nthUglyNumber(int n) {
int result = 0;
int i = 1;
while(result < n)
{
if (checkUgly(i))
{
// cout << i << endl;
result++;
}
i++;
}
return --i;
}
};
解题思路二：根据丑数的定义，丑数应该是另一个数*2，*3或*5的结果。因此只要创建一个数组，里面的数字是排好序的丑数，每一个丑数都是前面丑数*2，*3，*5获得即可。因此重点在于怎么排好序。
我们首先考虑数组中已经有若干排好序的数组，，并将最大的丑数记录为M，接下来我们将分析如何生成下一个丑数。改丑数一定是前面某一个丑数*2, *3, *5的结果，因此我们先考虑将所有丑数都*2。这样一定会有若干小于M的结果和若干大于M的结果。由于是按照顺序生成的，小于M的结果一定已经在数组中，可以忽略，在若干大于M的数中，我们只取第一个大于M的结果称为M2，因为数组是按由小到大顺序生成的，其他更大的结果以后再说。同理我们可以找到M3，M5，并从M2，M3，M5中选取最小值，作为下一个丑数。
前面分析的时候，将已有所有丑数都进行*2操作，但是其实这个是没有必要的。因为数组中的数是按大小排序的，一定存在某一个丑数T2，其前面每个丑数乘2后小于M，后面每个都大于M，我们只需要记下这个丑数的位置，每次生成新的丑数的时候，去更新T2的位置。同理T3和T5。
class Solution {
public:
int min(int a, int b, int c)
{
int tmp;
if (a > b) {tmp = b;}
else {tmp = a;}
if (c < tmp) { tmp = c; }
return tmp;
}
int nthUglyNumber(int n) {
if (n <= 0)
{
return 0;
}
int result[n];
result[0] = 1;
int index = 1;
int* T2 = result;
int* T3 = result;
int* T5 = result;
while(index < n)
{
result[index] = min(2*(*T2), 3*(*T3), 5*(*T5));
while(2*(*T2) <= result[index])
{
T2++;
}
while(3*(*T3) <= result[index])
{
T3++;
}
while(5*(*T5) <= result[index])
{
T5++;
}
++index;
}
return result[n-1];
}
};
解题思路：先遍历一遍，用hash表记录每个字符出现次数。然后遍历第二遍，遍历时判断出现次数是1，返回字符，程序结束。书中用了256的int数组，每个位置存字符出现次数模拟hash表，不明白为什么不用map。然后自己尝试了下，发现map时间会长好多。面试题35：第一个只出现一次的字符
在字符串中找到第一个只出现一次的字符。如输入"abaccdeff",输出b。
leetcode链接 https://leetcode-cn.com/problems/di-yi-ge-zhi-chu-xian-yi-ci-de-zi-fu-lcof/class Solution { public: char firstUniqChar(string s) { int arr[256]; for(int i = 0; i < 256; i++) { arr[i] = 0; } for(int i = 0; i < s.length(); i++) { arr[s[i] - '0']++; } for(int i = 0; i < s.length(); i++) { if (arr[s[i] - '0'] == 1) { return s[i]; } } char result = ' '; return result; /* map map<char, int> sNum; for(int i = 0; i < s.length(); i++) { sNum[s[i]]++; } for(int i = 0; i < s.length(); i++) { if (sNum[s[i]] == 1) { return s[i]; } } char result = ' '; return result; */ } };
map和数组模拟
本题扩展：考虑如果字符换成汉字，有成千上万个，怎么解决
答：我感觉，用map吧，不用考虑预留空间问题。确定字符种类是的就用数组模拟hash，否则就用map。
相关题目：定义一个函数，输入两个字符串，从第一个字符串删除在第二个字符串中出现的所有字符。
int main() { string a = "aabbcde"; string b = "aac"; map<char, int> bMap; for(int i = 0; i < b.length(); i++) { bMap[b[i]]++; } string result = ""; for(int i = 0; i < a.length(); i++) { if (bMap[a[i]] == 0) { result += a[i]; } } a = result; cout << a << endl; }
解题思路：用hash表存储第二个字符串，判断是不是在hash表中即可。如果第一个字符串长度是n，则时间复杂度o(n)
相关题目：定义一个函数，删除其中重复出现的字符
int main() { string a = "aabbcde"; string b = "aac"; map<char, int> bMap; for(int i = 0; i < b.length(); i++) { bMap[b[i]]++; } string result = ""; for(int i = 0; i < b.length(); i++) { if (bMap[b[i]] == 1) { result += b[i]; } } cout << result; }
解题思路：把出现过元素存入hash表，初始化将所有元素设为false，遍历每个元素进行判断，第一次出现改为true，若再次遇到发现是true，则删除。时间复杂度o(n)
相关题目：在英语中，如果两个单词出现的字母相同，并且每个字母出现的次数也相同，那么这两个单词互为变位词。写一个函数，判断两个字符串是不是互为变位词。
leetcode链接 https://leetcode-cn.com/problems/valid-anagram/class Solution { public: bool isAnagram(string s, string t) { int sHash[256], tHash[256]; if (s.length() != t.length()) { return false; } for(int i = 0; i < 256; i++) { sHash[i] = 0; tHash[i] = 0; } for(int i = 0; i < s.length(); i++) { sHash[s[i]]++; } for(int i = 0; i < t.length(); i++) { tHash[t[i]]++; } for(int i = 0; i < 256; i++) { if (sHash[i] != tHash[i]) { return false; } } return true; } };
解题思路：先判断长度是否相等，不相等false。第一个串遍历，建立hash表。第二个串遍历，相同元素hash值-1，若有元素数量不够-1，则返回false。
解题思路：将数组分成子数组，统计子数组内部逆序对的数目，然后再统计相邻子数组之间逆序对的数目。在统计逆序对的过程中，还需要对数组进行排序。其实就是归并排序的变种。面试题36:数组中的逆序对
在数组中的两个数字，如果前面一个数大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求其中逆序对的总数。
leetcode链接 https://leetcode-cn.com/problems/shu-zu-zhong-de-ni-xu-dui-lcof/
判断逆序对过程
面试题37:两个链表的第一个公共结点
输入两个链表，找到他们的第一个公共节点。
leetcode链接 https://leetcode-cn.com/problems/liang-ge-lian-biao-de-di-yi-ge-gong-gong-jie-dian-lcof//** * Definition for singly-linked list. * struct ListNode { * int val; * ListNode *next; * ListNode(int x) : val(x), next(NULL) {} * }; */ class Solution { public: ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) { stack<ListNode*> stackA, stackB; while(headA != NULL) { stackA.push(headA); headA = headA->next; } while(headB != NULL) { stackB.push(headB); headB = headB->next; } ListNode* result = NULL; while(!stackA.empty() && !stackB.empty()) { if (stackA.top() != stackB.top()) { break; } result = stackA.top(); stackA.pop(); stackB.pop(); } return result; } };
解题思路：
思路1：考虑两个链表有公共节点，则两个链表尾节点一定相同，找到链表尾节点，往前回溯，即可找到公共节点。考虑链表只能从前往后，而从尾节点往前回溯是相反的，因此用栈结构进行存储
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
stack<ListNode*> stackA, stackB;
while(headA != NULL)
{
stackA.push(headA);
headA = headA->next;
}
while(headB != NULL)
{
stackB.push(headB);
headB = headB->next;
}
ListNode* result = NULL;
while(!stackA.empty() && !stackB.empty())
{
if (stackA.top() != stackB.top())
{
break;
}
result = stackA.top();
stackA.pop();
stackB.pop();
}
return result;
}
};
思路2：不使用辅助内存。先遍历两个链表，求得其长度相差p。将指向较长链表指针先移动p步，之后两个链表指针一起移动，相遇即为公共节点。
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int lenA = 0, lenB = 0;
ListNode* tmpA = headA;
ListNode* tmpB = headB;
while(tmpA != NULL)
{
tmpA = tmpA->next;
lenA++;
}
while(tmpB != NULL)
{
tmpB = tmpB->next;
lenB++;
}
if (lenA > lenB)
{
while(lenA != lenB)
{
headA = headA->next;
lenA--;
}
}
if (lenB > lenA)
{
while(lenA != lenB)
{
headB = headB->next;
lenB--;
}
}
while(headA != NULL && headB != NULL)
{
if (headB == headA)
{
return headA;
}
headA = headA->next;
headB = headB->next;
}
return NULL;
}
};
相关题目：求二叉树中两个叶子节点的最近公共祖先
leecode链接 https://leetcode-cn.com/problems/er-cha-shu-de-zui-jin-gong-gong-zu-xian-lcof//** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode *right; * TreeNode(int x) : val(x), left(NULL), right(NULL) {} * }; */ class Solution { public: TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) { // 1.递归法 遍历树，找到p和q分布在其左右两个子树中的节点，即为最近公共祖先 // 简洁写法，每次都不能第一时间转过来 if (root == NULL || root == p || root == q) { return root; } TreeNode* left = lowestCommonAncestor(root->left, p, q); TreeNode* right = lowestCommonAncestor(root->right, p, q); if (left == NULL) { return right; } if (right == NULL) { return left; } return root; } };
思路1：如果二叉树中有指向根节点的指针，这个和上面那个链表题是完全一样的。观察下图，二叉树就是两个公共节点链表旋转90度
有公共节点的链表
思路2：遍历，当两个叶子节点分散在某个根节点的左右子树中。当前根节点就是最近的公共祖先。但是这个方法，每次需要遍历每个节点左子树和右子树，存在很大冗余。https://www.jianshu.com/p/68de70bbf8eb
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool findNode(TreeNode* root, TreeNode* tmp)
{
// 匹配那个繁琐写法的
if (root == NULL)
{
return false;
}
if (root == tmp)
{
return true;
}
// cout << root->val << endl;
bool left = findNode(root->left, tmp);
bool right = findNode(root->right, tmp);
return left || right;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
// 1.递归法 遍历树，找到p和q分布在其左右两个子树中的节点，即为最近公共祖先
// 简洁写法，每次都不能第一时间转过来
if (root == NULL || root == p || root == q)
{
return root;
}
TreeNode* left = lowestCommonAncestor(root->left, p, q);
TreeNode* right = lowestCommonAncestor(root->right, p, q);
if (left == NULL)
{
return right;
}
if (right == NULL)
{
return left;
}
return root;
/* 繁琐但是好理解的写法
// 需要写一个函数，传入根节点，判断p和q是否在其子树中
if (root == NULL)
{
return NULL;
}
if (findNode(p, q))
{
return p;
}
if (findNode(q, p))
{
return q;
}
bool pFindRight = findNode(root->right, p);
bool qFindRight = findNode(root->right, q);
bool pFindLeft = findNode(root->left, p);
bool qFindLeft = findNode(root->left, q);
// cout << "pFindRight: " << pFindRight << " qFindRight: " << qFindRight << " pFindLeft: " << pFindLeft << " qFindLeft: " << qFindLeft << endl;
if (pFindRight && qFindRight)
{
return lowestCommonAncestor(root->right, p, q);
}
else if (pFindLeft && qFindLeft)
{
return lowestCommonAncestor(root->left, p, q);
}
else if ((pFindLeft && qFindRight) || (pFindRight && qFindLeft))
{
return root;
}
else {
return NULL;
}
return NULL;
*/
}
};
思路3：将节点1和节点2的路径用栈记录下来，然后回溯栈。这样遍历一遍树结构就可以了。
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int pn = 0;
int qn = 0;
void searchTree(TreeNode* root, TreeNode* p, TreeNode* q, stack<TreeNode*>& resultP, stack<TreeNode*>& resultQ, stack<TreeNode*>& tmp)
{
if (root == NULL)
{
return;
}
if (!resultP.empty() && !resultQ.empty())
{
return;
}
if (root == p)
{
stack<TreeNode*> a = tmp;
resultP.push(root);
while(!a.empty())
{
pn++;
resultP.push(a.top());
a.pop();
}
pn++;
}
if (root == q)
{
qn++;
stack<TreeNode*> a = tmp;
resultQ.push(root);
while(!a.empty())
{
qn++;
resultQ.push(a.top());
a.pop();
}
}
tmp.push(root);
searchTree(root->left, p, q, resultP, resultQ, tmp);
searchTree(root->right, p, q, resultP, resultQ, tmp);
tmp.pop();
return;
}
TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
// 用栈记录遍历路径，并把有两个根节点的路径保存起来
stack<TreeNode*> resultP, resultQ, tmp;
searchTree(root, p, q, resultP, resultQ, tmp);
TreeNode* pre = NULL;
TreeNode* result = NULL;
while(!resultP.empty() && !resultQ.empty())
{
// cout << "q: " << resultQ.top()->val << " " << endl;
// cout << "p: " << resultP.top()->val << " " << endl;
if(resultP.top() != resultQ.top())
{
break;
}
result = resultP.top();
resultQ.pop();
resultP.pop();
}
return result;
}
};
思路二和思路三
网友评论