不要小看简单题-华为面试题库简单题一题多解整理
华为面试题库刷题第二次整理，这次整理的都是简单题的多解法，大部分都是用了巧妙方法使空间复杂度位O(1)，简单题也有它的魅力和价值。
个人博客的链接：flamsteed
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明：
你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
解法：要求时间复杂度O(N)，空间复杂度O(1)，讲道理，想不出来，只相处一种排序之后遍历一遍得出答案的方法，时间复杂度O(N*log(N))，空间复杂度O(1)。
排序排序后遍历，没有出现两次就是答案
代码：
class Solution {
public:
int singleNumber(vector& nums) {
sort(nums.begin(),nums.end());
int res = INT_MAX;
for(int i=0; i<nums.size();i+=2)
if(i+1<nums.size() && nums[i]!=nums[i+1]){
res = nums[i];
break;
}
if(res==INT_MAX) res = nums[nums.size()-1];
return res;
}
};
集合
集合可以自动去重，然后求和乘2再减去原来的和就是答案，时间复杂度O(N)，空间复杂度O(N)。
代码：
class Solution {
public:
int singleNumber(vector& nums) {
set s;
int sum1(0),sum2(0);
for(auto x:nums){
s.insert(x);
sum1 += x;
}
for(auto x:s){
sum2 += x;
}
return (sum2*2-sum1);
}
};
位运算
又是位运算，这东西是真的骚，反正没做过基本想不出来，不过这次做过了以后就不能忘了。
根据位运算异或的性质，可以得到以下的规律：
所以，根据以上的规律，所有数字异或一边，就会剩下答案。
代码：
class Solution {
public:
int singleNumber(vector& nums) {
int res = 0;
for(auto x:nums)
res ^= x;
return res;
}
};
189. 旋转数组
给定一个数组，将数组中的元素向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: [1,2,3,4,5,6,7] 和 k = 3
输出: [5,6,7,1,2,3,4]
解释:
向右旋转 1 步: [7,1,2,3,4,5,6]
向右旋转 2 步: [6,7,1,2,3,4,5]
向右旋转 3 步: [5,6,7,1,2,3,4]
说明:
尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
要求使用空间复杂度为O(1)的原地算法。
解法：最朴素的k次移动一位的方法爆了，上了出题者的鬼当，只能O(N)做的话，只能想出来用数组占存一部分，移动好了再填进去。
额外数组存储方法代码：
class Solution {
public:
void rotate(vector& nums, int k) {
if(nums.empty()) return;
int l = nums.size();
k = k % l;
if(k==0) return;
vector a;
for(int i=l-k; i=k; i--)
nums[i] = nums[i-k];
for(int i=0; i<a.size(); i++)
nums[i] = a[i];
return;
}
};
本地直接交换
题目的正解很巧妙，根据下标i%k的值进行移动，遍历一遍，O(N)解法，而且无额外空间。
代码：
class Solution {
public:
void rotate(vector& nums, int k) {
if(nums.empty()) return;
int l = nums.size();
k = k % l;
if(k==0) return;
int count(0);
int p = 0;
int current = 0;
int pre = nums[0];
while(count<l){
do{
int next = (current+k) % l;
int t = nums[next];
nums[next] = pre;
pre = t;
current = next;
count++;
}while(current!=p);
current = ++p;
pre = nums[p];
}
return;
}
};
234. 回文链表
请判断一个链表是否为回文链表。
示例 1:
输入: 1->2
输出: false
进阶：
你能否用 O(n) 时间复杂度和 O(1) 空间复杂度解决此题？
解法：这题O(N)很简单，但是O(1)空间就有点难了。
存进数组大部分解法就是存进数组，然后用正常的方法判断回文。
代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
vector a;
ListNode* p{head};
while(p){
a.push_back(p->val);
p = p->next;
}
bool f = true;
for(int i=0; i<a.size()/2; i++){
if(a[i]!=a[a.size()-i-1]){
f = false;
break;
}
}
return f;
}
};
反转后一半
利用快慢指针找到中间点，然后把后面一半的链表反转一下，然后顺序比较。
代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool isPalindrome(ListNode* head) {
if(!head) return true;
ListNode* firstend = secondHalf(head);
ListNode* Second = reverseList(firstend->next);
ListNode* p1 = head;
ListNode* p2 = Second;
bool f = true;
while(f && p2){
if(p1->val != p2->val) f = false;
p1 = p1->next;
p2 = p2->next;
}
return f;
}
ListNode* reverseList(ListNode* head){//反转
ListNode* prev = NULL;
ListNode* curr = head;
while(curr){
ListNode* t = curr->next;
curr->next = prev;
prev = curr;
curr = t;
}
return prev;
}
ListNode* secondHalf(ListNode* head){//寻找中间点
ListNode* slow{head};
ListNode* fast{head};
while(fast->next && fast->next->next){
slow = slow->next;
fast = fast->next->next;
}
return slow;
}
};
160. 相交链表
编写一个程序，找到两个单链表相交的起始节点。
输入：intersectVal = 8, listA = [4,1,8,4,5], listB = [5,0,1,8,4,5], skipA = 2, skipB = 3
输出：Reference of the node with value = 8
输入解释：相交节点的值为 8 （注意，如果两个列表相交则不能为 0）。从各自的表头开始算起，链表 A 为 [4,1,8,4,5]，链表 B 为 [5,0,1,8,4,5]。在 A 中，相交节点前有 2 个节点；在 B 中，相交节点前有 3 个节点。
注意：
如果两个链表没有交点，返回 null.
在返回结果后，两个链表仍须保持原有的结构。
可假定整个链表结构中没有循环。
程序尽量满足 O(n) 时间复杂度，且仅用 O(1) 内存。
解法：
双向指针A的指针遍历完A 接着从headB开始遍历
B的指针遍历完B 接着从headA开始遍历
两个指针都最多走m + n + 1步。
当两个指针同时为空时，表示不相交；当两个都非空且相等时，表示相交
时间复杂度O(m + n) 空间复杂度O(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) {
if(!headA||!headB) return nullptr;
ListNode* curr_a = headA;
ListNode* curr_b = headB;
while(curr_a!=curr_b){
curr_a = (!curr_a) ? headB : curr_a->next;
curr_b = (!curr_b) ? headA : curr_b->next;
}
return curr_a;
}
};
哈希表法
使用一个hash set 遍历一个链表，set中存放其所有指针， 遍历另一个链表，去set中找相同指针
时间复杂度O(m + n) 空间复杂度O(m) 或 O(n)
代码：
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
unordered_set s;
ListNode* curr_a{headA};
while(curr_a){
s.insert(curr_a);
curr_a = curr_a->next;
}
ListNode* curr_b{headB};
while(curr_b){
if(s.find(curr_b)!=s.end())
return curr_b;
curr_b = curr_b->next;
}
return nullptr;
}
};
暴力法有丶傻，不写了。
141. 环形链表给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
示例 1：
输入：head = [3,2,0,-4]
输出：true
解释：链表中有一个环，其尾部连接到第二个节点。
解法：
哈希表法和上一题的哈希表法大同小异，只不过这回是边存边判断。
代码：
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
unordered_set s;
ListNode* t = head;
while(t){
if(!s.empty() && s.find(t)!=s.end())
return true;
s.insert(t);
t = t->next;
}
return false;
}
};
双指针法
如果存在环路，那么快指针一定会追上慢指针，所以设置两个快慢指针就行了，很巧妙，空间复杂度O(1)。
代码：
class Solution {
public:
bool hasCycle(ListNode *head) {
if(!head || !head->next) return false;
ListNode* slow = head;
ListNode* fast = head->next;
while(fast!=slow){
if(!fast || !fast->next) return false;
slow = slow->next;
fast = fast->next->next;
}
return true;
}
};
作者：oimonster
