- 前言
- 只出现一次的数字
- 求众数
- 搜索二维矩阵 II
- 合并两个有序数组
- 验证回文串
- 有效的字母异位词
- 字符串中的第一个唯一字符
- 反转字符串
- 旋转数组
- 存在重复元素
- 移动零
- 两个数组的交集 II
- 数组中的第K个最大元素
- 数据流的中位数
- 环形链表
- 相交链表
- 反转链表
- 删除链表中的节点
- Excel表列序号
- 常数时间插入、删除和获取随机元素
- 寻找峰值
- 颠倒二进制位
- 位1的个数
- 缺失数字
- 3的幂
- 最小栈
- 前 K 个高频元素
- 二叉搜索树中第K小的元素
- 实现 Trie (前缀树)
- 打乱数组
- 递增的三元子序列
- 除自身以外数组的乘积
- 有序矩阵中第K小的元素
- 逆波兰表达式求值
- 复制带随机指针的链表
- 四数相加 II
- 寻找重复数
- 最长连续序列
- 无重复字符的最长子串
- 最长公共前缀
- 字符串相乘
- 翻转字符串里的单词
- 简化路径
- 最长连续递增序列
- 合并两个有序链表
- 两数相加
- 合并K个排序链表
- 计算二叉树的深度
- 两数之和
- 三数之和
- 有效的括号
- 删除排序数组中的重复项
- 盛最多水的容器
- 反转字符串中的单词 III
- 旋转链表
- 整数反转
- 回文数
- 2的幂
前言
以前从来没有刷过LeetCode，这段时间想刷一些题目锻炼一下算法能力，我会将题目分为四类：
- 看完题目之后就有思路能直接写出来的
- 看了别人的思路之后然后自己再写出来的
- 参考别人的代码才能写出来的
- 看了别人的代码花了很长时间才能理解的
这篇文章主要记录前两类题目，以及大概的解题思路，当然有些题目不是最优解，只是我觉得最容易想到和理解的解，但是肯定是通过了LeetCode所有测试用例的。
只出现一次的数字
给定一个非空整数数组，除了某个元素只出现一次以外，其余每个元素均出现两次。找出那个只出现了一次的元素。
说明： 你的算法应该具有线性时间复杂度。 你可以不使用额外空间来实现吗？
示例 1: 输入: [2,2,1] 输出: 1
示例 2: 输入: [4,1,2,1,2] 输出: 4
/* 思路：利用异或运算，两个相同的数异或之后为0，0与一个数异或还是它自己，
所以只需要将数组中的所有异或一次，最后得到的数就是那个只出现一次的数
*/
class Solution {
public:
int singleNumber(vector<int>& nums) {
int n = 0;
for(vector<int>::iterator iter = nums.begin(); iter != nums.end(); iter++)
{
n = n^(*iter);
}
return n;
}
};
求众数
给定一个大小为 n 的数组，找到其中的众数。众数是指在数组中出现次数大于 ⌊ n/2 ⌋ 的元素。
你可以假设数组是非空的，并且给定的数组总是存在众数。
示例 1:
输入: [3,2,3]
输出: 3
示例 2:
输入: [2,2,1,1,1,2,2]
输出: 2
/* 思路：遍历一遍数组放到map中计数，然后遍历map，找到众数，复杂度为O(n)
*/
class Solution {
public:
int majorityElement(vector<int>& nums) {
map<int,int> mapCount;
for(vector<int>::iterator iter = nums.begin(); iter != nums.end(); iter++)
{
map<int,int>::iterator iMap = mapCount.find(*iter);
if (iMap == mapCount.end())
{
mapCount[*iter] = 1;
}
else
{
iMap->second++;
}
}
for (map<int,int>::iterator iter = mapCount.begin(); iter != mapCount.end(); iter++)
{
if (iter->second > nums.size()/2)
return iter->first;
}
return 0;
}
};
搜索二维矩阵 II
编写一个高效的算法来搜索 m x n 矩阵 matrix 中的一个目标值 target。该矩阵具有以下特性：
每行的元素从左到右升序排列。
每列的元素从上到下升序排列。
示例:
现有矩阵 matrix 如下：
[
[1, 4, 7, 11, 15],
[2, 5, 8, 12, 19],
[3, 6, 9, 16, 22],
[10, 13, 14, 17, 24],
[18, 21, 23, 26, 30]
]
给定 target = 5，返回 true。
给定 target = 20，返回 false。
/* 思路：倒序遍历每一行，找到前一个数大于target，后一个数小于target的位置，
然后从这个位置开始在倒序遍历下一行，直到找到target。
*/
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
if (matrix.size() == 0)
return false;
vector<int> *pArray = &matrix[0];
int high = matrix.size();
int len = pArray->size();
if (len == 0)
return false;
int index = len - 1;
for (int i = 0; i < high; i++)
{
int j = index;
for (; j > 0; j--)
{
if(matrix[i][j] > target && matrix[i][j - 1] < target)
{
index = j - 1;
break;
}
if(matrix[i][j] == target)
return true;
}
if(matrix[i][j] == target)
return true;
}
return false;
}
};
合并两个有序数组
给定两个有序整数数组 nums1 和 nums2，将 nums2 合并到 nums1 中，使得 num1 成为一个有序数组。
说明:
初始化 nums1 和 nums2 的元素数量分别为 m 和 n。
你可以假设 nums1 有足够的空间（空间大小大于或等于 m + n）来保存 nums2 中的元素。
示例:
输入:
nums1 = [1,2,3,0,0,0], m = 3
nums2 = [2,5,6], n = 3
输出: [1,2,2,3,5,6]
class Solution {
public:
void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) {
vector<int> vecTemp = nums1;
int i = 0, j = 0, k = 0, z = 0;
z = m + n;
while(k < z)
{
if (j >= n || (i < m && vecTemp[i] < nums2[j]))
{
nums1[k] = vecTemp[i];
i++;
}
else
{
nums1[k] = nums2[j];
j++;
}
k++;
}
}
};
验证回文串
给定一个字符串，验证它是否是回文串，只考虑字母和数字字符，可以忽略字母的大小写。
说明：本题中，我们将空字符串定义为有效的回文串。
示例 1:
输入: “A man, a plan, a canal: Panama”
输出: true
示例 2:
输入: “race a car”
输出: false
/* 思路：先过滤无用字符并将所有小写字符转为大写，然后在判断回文串
*/
class Solution {
public:
bool isPalindrome(string s) {
string str2;
for (int i = 0; i < s.size(); i++)
{
if ((s[i] >= 'a' && s[i] <= 'z') || (s[i] >= 'A' && s[i] <= 'Z') || (s[i] >= '0' && s[i] <= '9'))
{
if (s[i] >= 'a' && s[i] <= 'z')
{
s[i] = s[i] + ('A' - 'a');
}
str2.append(&s[i], 1);
}
}
for (int i = 0; i < str2.size()/2; i++)
{
if (str2[i] != str2[str2.size() - 1 - i])
{
return false;
}
}
return true;
}
};
有效的字母异位词
给定两个字符串 s 和 t ，编写一个函数来判断 t 是否是 s 的字母异位词。
示例 1:
输入: s = “anagram”, t = “nagaram”
输出: true
示例 2:
输入: s = “rat”, t = “car”
输出: false
说明:
你可以假设字符串只包含小写字母。
进阶:
如果输入字符串包含 unicode 字符怎么办？你能否调整你的解法来应对这种情况？
/* 思路：将两个字符串分别遍历放到两个map中，然后遍历其中一个map，在另一个map中找有没有这个元素
*/
class Solution {
public:
bool isAnagram(string s, string t) {
if (s.size() != t.size())
return false;
map<char,int> mapS, mapT;
for(int i = 0; i < s.size(); i++)
{
mapS[s[i]]++;
mapT[t[i]]++;
}
if (mapS.size() != mapT.size())
return false;
for(auto iter = mapS.begin(); iter != mapS.end(); iter++)
{
auto iterT = mapT.find(iter->first);
if (iterT == mapT.end())
return false;
if (iterT->second != iter->second)
return false;
}
return true;
}
};
字符串中的第一个唯一字符
给定一个字符串，找到它的第一个不重复的字符，并返回它的索引。如果不存在，则返回 -1。
案例:
s = “leetcode”
返回 0.
s = “loveleetcode”,
返回 2.
注意事项：您可以假定该字符串只包含小写字母。
class Solution {
public:
int firstUniqChar(string s) {
unordered_map<char,int> mapCount;
for (int i = 0; i < s.size(); i++)
{
mapCount[s[i]]++;
}
for (int i = 0; i < s.size(); i++)
{
unordered_map<char,int>::iterator iter = mapCount.find(s[i]);
if (iter->second == 1)
{
return i;
}
}
return -1;
}
};
反转字符串
编写一个函数，其作用是将输入的字符串反转过来。输入字符串以字符数组 char[] 的形式给出。
不要给另外的数组分配额外的空间，你必须原地修改输入数组、使用 O(1) 的额外空间解决这一问题。
你可以假设数组中的所有字符都是 ASCII 码表中的可打印字符。
示例 1：
输入：[“h”,”e”,”l”,”l”,”o”]
输出：[“o”,”l”,”l”,”e”,”h”]
示例 2：
输入：[“H”,”a”,”n”,”n”,”a”,”h”]
输出：[“h”,”a”,”n”,”n”,”a”,”H”]
class Solution {
public:
void reverseString(vector<char>& s) {
int len = s.size();
for (int i = 0; i < len/2; i++)
{
char c = s[i];
s[i] = s[len - 1 - i];
s[len - 1 - i] = c;
}
}
};
旋转数组
给定一个数组，将数组中的元素向右移动 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]
示例 2:
输入: [-1,-100,3,99] 和 k = 2
输出: [3,99,-1,-100]
解释:
向右旋转 1 步: [99,-1,-100,3]
向右旋转 2 步: [3,99,-1,-100]
说明:
尽可能想出更多的解决方案，至少有三种不同的方法可以解决这个问题。
要求使用空间复杂度为 O(1) 的 原地 算法。
/* 思路：将K前面的所有元素反转，在将K后面的元素反转，然后反转这个数组
*/
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int len = nums.size();
if (len < 2 || k < 1 || k % len == 0) {
return;
}
if (k > len) {
k = k % len;
}
reverse(nums, len - k, len);
reverse(nums, 0, len - k);
reverse(nums, 0, len);
}
void reverse(vector<int>& s, int start, int end) {
for (int i = 0; i < (end - start)/2; i++)
{
int c = s[i + start];
s[i + start] = s[end - 1 - i];
s[end - 1 - i] = c;
}
}
};
存在重复元素
给定一个整数数组，判断是否存在重复元素。
如果任何值在数组中出现至少两次，函数返回 true。如果数组中每个元素都不相同，则返回 false。
示例 1:
输入: [1,2,3,1]
输出: true
示例 2:
输入: [1,2,3,4]
输出: false
示例 3:
输入: [1,1,1,3,3,4,3,2,4,2]
输出: true
class Solution {
public:
bool containsDuplicate(vector<int>& nums) {
set<int> setI;
for (int i = 0; i < nums.size(); i++)
{
auto iter = setI.find(nums[i]);
if(iter == setI.end())
{
setI.insert(nums[i]);
}
else
{
return true;
}
}
return false;
}
};
移动零
给定一个数组 nums，编写一个函数将所有 0 移动到数组的末尾，同时保持非零元素的相对顺序。
示例:
输入: [0,1,0,3,12]
输出: [1,3,12,0,0]
说明:
必须在原数组上操作，不能拷贝额外的数组。
尽量减少操作次数。
/* 思路：将所有非0元素移到前面来，然后将后面的元素都置为0
*/
class Solution {
public:
void moveZeroes(vector<int>& nums) {
int j = 0;
for(int i = 0; i < nums.size(); i++)
{
if (nums[i] != 0)
{
nums[j] = nums[i];
j++;
}
}
for(int i = j; i < nums.size(); i++)
{
nums[i] = 0;
}
}
};
两个数组的交集 II
给定两个数组，编写一个函数来计算它们的交集。
示例 1:
输入: nums1 = [1,2,2,1], nums2 = [2,2]
输出: [2,2]
示例 2:
输入: nums1 = [4,9,5], nums2 = [9,4,9,8,4]
输出: [4,9]
说明：
输出结果中每个元素出现的次数，应与元素在两个数组中出现的次数一致。
我们可以不考虑输出结果的顺序。
class Solution {
public:
vector<int> intersect(vector<int>& nums1, vector<int>& nums2) {
vector<int> result;
map<int,int> mapC;
for(int i = 0; i < nums1.size(); i++)
{
mapC[nums1[i]]++;
}
for(int i = 0; i < nums2.size(); i++)
{
auto iter = mapC.find(nums2[i]);
if(iter != mapC.end())
{
if (iter->second > 0)
{
result.push_back(nums2[i]);
iter->second--;
}
}
}
return result;
}
};
数组中的第K个最大元素
在未排序的数组中找到第 k 个最大的元素。请注意，你需要找的是数组排序后的第 k 个最大的元素，而不是第 k 个不同的元素。
示例 1:
输入: [3,2,1,5,6,4] 和 k = 2
输出: 5
示例 2:
输入: [3,2,3,1,2,4,5,5,6] 和 k = 4
输出: 4
说明:
你可以假设 k 总是有效的，且 1 ≤ k ≤ 数组的长度。
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
sort(nums.begin(), nums.end());
return nums[nums.size() - k];
}
};
数据流的中位数
中位数是有序列表中间的数。如果列表长度是偶数，中位数则是中间两个数的平均值。
例如：
[2,3,4] 的中位数是 3
[2,3] 的中位数是 (2 + 3) / 2 = 2.5
设计一个支持以下两种操作的数据结构：
void addNum(int num) - 从数据流中添加一个整数到数据结构中。
double findMedian() - 返回目前所有元素的中位数。
示例：
addNum(1)
addNum(2)
findMedian() -> 1.5
addNum(3)
findMedian() -> 2
/* 思路：使用两个堆，一个大顶堆，一个小顶堆，保证大顶堆中的数据都小于小顶堆，并且两个堆中的数据量最多相差一个。
*/
class MedianFinder {
public:
/** initialize your data structure here. */
std::priority_queue<int, std::vector<int>, std::greater<int> > minHeap;
std::priority_queue<int, std::vector<int>, std::less<int> > maxHeap;
MedianFinder() {
}
void addNum(int num) {
if(maxHeap.empty() || num <= maxHeap.top())
{
maxHeap.push(num);
}
else
{
minHeap.push(num);
}
if (maxHeap.size() - minHeap.size() == 2)
{
minHeap.push(maxHeap.top());
maxHeap.pop();
}
if (minHeap.size() - maxHeap.size() == 2)
{
maxHeap.push(minHeap.top());
minHeap.pop();
}
}
double findMedian() {
if (minHeap.size() == maxHeap.size())
{
return (minHeap.top() + maxHeap.top())/2.0;
}
if (minHeap.size() > maxHeap.size())
{
return minHeap.top();
}
else
{
return maxHeap.top();
}
}
};
环形链表
给定一个链表，判断链表中是否有环。
为了表示给定链表中的环，我们使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。 如果 pos 是 -1，则在该链表中没有环。
/* 思路：快慢指针，如果两个再次相遇说明有环
*/
/**
* 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) {
if (head == NULL)
return false;
ListNode *slow = head, *fast = head->next;
while(fast && fast->next)
{
if (slow == fast)
return true;
slow = slow->next;
fast = fast->next->next;
}
return false;
}
};
相交链表
编写一个程序，找到两个单链表相交的起始节点。
/* 思路：先计算两个链表的长度，将长链表先移动到和短链表一样长的位置，然后开始同时遍历两个链表，
如果两个节点相等，则找到相交节点
*/
/**
* 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 = 1, lenB = 1, step = 0;
ListNode *nodeA = headA, *nodeB = headB;
while(nodeA)
{
nodeA = nodeA->next;
lenA++;
}
while(nodeB)
{
nodeB = nodeB->next;
lenB++;
}
nodeA = headA;
nodeB = headB;
if (lenA > lenB)
{
step = lenA - lenB;
while(step)
{
nodeA = nodeA->next;
step--;
}
}
else
{
step = lenB - lenA;
while(step)
{
nodeB = nodeB->next;
step--;
}
}
while(nodeA != NULL && nodeB != NULL)
{
if (nodeA == nodeB)
return nodeA;
nodeA = nodeA->next;
nodeB = nodeB->next;
}
return NULL;
}
};
反转链表
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if (head == NULL || head->next == NULL)
return head;
ListNode *first = head;
ListNode *second = head->next;
head->next = NULL;
while (second != NULL)
{
ListNode *third = second->next;
second->next = first;
first = second;
second = third;
}
return first;
}
};
删除链表中的节点
请编写一个函数，使其可以删除某个链表中给定的（非末尾）节点，你将只被给定要求被删除的节点。
现有一个链表 – head = [4,5,1,9]，它可以表示为:
示例 1:
输入: head = [4,5,1,9], node = 5
输出: [4,1,9]
解释: 给定你链表中值为 5 的第二个节点，那么在调用了你的函数之后，该链表应变为 4 -> 1 -> 9.
示例 2:
输入: head = [4,5,1,9], node = 1
输出: [4,5,9]
解释: 给定你链表中值为 1 的第三个节点，那么在调用了你的函数之后，该链表应变为 4 -> 5 -> 9.
/* 思路：将当前节点的下一个节点赋值给当前节点，然后删除下一个节点
*/
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void deleteNode(ListNode* node) {
node->val = node->next->val;
ListNode *temp = node->next->next;
node->next = temp;
}
};
Excel表列序号
给定一个Excel表格中的列名称，返回其相应的列序号。
示例 1:
输入: “A”
输出: 1
示例 2:
输入: “AB”
输出: 28
示例 3:
输入: “ZY”
输出: 701
/* 思路：就是将26进制转换为10进制
*/
class Solution {
public:
int titleToNumber(string s) {
int ret = 0, j = 0;
for(int i = s.size() - 1; i >= 0; i--)
{
ret = ret + (s[i] - 'A' + 1) * pow(26, j);
j++;
}
return ret;
}
};
常数时间插入、删除和获取随机元素
设计一个支持在平均 时间复杂度 O(1) 下，执行以下操作的数据结构。
insert(val)：当元素 val 不存在时，向集合中插入该项。
remove(val)：元素 val 存在时，从集合中移除该项。
getRandom：随机返回现有集合中的一项。每个元素应该有相同的概率被返回。
/* 思路：一个map，一个数组，map中存放对应数字在数组中的位置
*/
class RandomizedSet {
public:
/** Initialize your data structure here. */
map<int, int> mapInt;
vector<int> verInt;
RandomizedSet() {
}
/** Inserts a value to the set. Returns true if the set did not already contain the specified element. */
bool insert(int val) {
auto iter = mapInt.find(val);
if (iter == mapInt.end())
{
verInt.push_back(val);
mapInt[val] = verInt.size() - 1;
return true;
}
return false;
}
/** Removes a value from the set. Returns true if the set contained the specified element. */
bool remove(int val) {
auto iter = mapInt.find(val);
if (iter == mapInt.end())
{
return false;
}
int a = verInt[verInt.size() - 1];
verInt[verInt.size() - 1] = verInt[iter->second];
verInt[iter->second] = a;
mapInt[a] = iter->second;
verInt.pop_back();
mapInt.erase(val);
return true;
}
/** Get a random element from the set. */
int getRandom() {
return verInt[random()%verInt.size()];
}
};
寻找峰值
峰值元素是指其值大于左右相邻值的元素。
给定一个输入数组 nums，其中 nums[i] ≠ nums[i+1]，找到峰值元素并返回其索引。
数组可能包含多个峰值，在这种情况下，返回任何一个峰值所在位置即可。
你可以假设 nums[-1] = nums[n] = -∞。
class Solution {
public:
int findPeakElement(vector<int>& nums) {
nums.push_back(INT_MIN);
for (int i = 1; i < nums.size(); i++)
{
if (nums[i-1] < nums[i] && nums[i] > nums[i+1])
{
return i;
}
}
return 0;
}
};
颠倒二进制位
颠倒给定的 32 位无符号整数的二进制位。
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t ret = 0;
for (int i = 0; i < 32; i++)
{
if (n & (1 << i))
ret = ret + (1 << (31 - i));
}
return ret;
}
};
位1的个数
编写一个函数，输入是一个无符号整数，返回其二进制表达式中数字位数为 ‘1’ 的个数（也被称为汉明重量）。
class Solution {
public:
int hammingWeight(uint32_t n) {
int count = 0;
for (int i = 0; i < 32; i++)
{
if (n & (1 << i))
count++;
}
return count;
}
};
缺失数字
给定一个包含 0, 1, 2, …, n 中 n 个数的序列，找出 0 .. n 中没有出现在序列中的那个数。
/* 思路：先计算n个数的和，然后减去数组中的所有数，剩下的就是缺失数
*/
class Solution {
public:
int missingNumber(vector<int>& nums) {
int sum = 0, i = 0, n = nums.size();
sum = (n * (n+1))/2;
while(i < n)
{
sum = sum - nums[i];
i++;
}
return sum;
}
};
3的幂
给定一个整数，写一个函数来判断它是否是 3 的幂次方。
class Solution {
public:
bool isPowerOfThree(int n) {
double i = n;
if (i <= 0)
return false;
while(i != 1)
{
i = i/3.0;
if (i < 1 && i > 0)
return false;
}
return true;
}
};
最小栈
设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) – 将元素 x 推入栈中。
pop() – 删除栈顶的元素。
top() – 获取栈顶元素。
getMin() – 检索栈中的最小元素。
/* 思路：开一个正常的栈，一个存放当前最小值的栈
*/
class MinStack {
public:
/** initialize your data structure here. */
stack<int> StackInt;
stack<int> minStack;
MinStack() {
minStack.push(INT_MAX);
}
void push(int x) {
StackInt.push(x);
if (x <= minStack.top())
{
minStack.push(x);
}
}
void pop() {
if (StackInt.top() == minStack.top())
{
minStack.pop();
}
StackInt.pop();
}
int top() {
return StackInt.top();
}
int getMin() {
return minStack.top();
}
};
前 K 个高频元素
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:
输入: nums = [1,1,1,2,2,3], k = 2
输出: [1,2]
示例 2:
输入: nums = [1], k = 1
输出: [1]
说明：
你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
你的算法的时间复杂度必须优于 O(n log n) , n 是数组的大小。
/* 思路：先用map统计所有数出现的次数，然后设置一个大小为K的小顶堆，遍历map以出现次数为key放入堆中
最后堆中的数据就是结果
*/
class Solution {
public:
vector<int> topKFrequent(vector<int>& nums, int k) {
map<int, int> mapCount;
priority_queue<int, vector<pair<int,int> >, greater<pair<int,int> > > minHeap;
vector<int> result;
for (auto iter : nums)
{
mapCount[iter]++;
}
for (auto iter : mapCount)
{
if (minHeap.size() < k)
{
minHeap.push(pair(iter.second, iter.first));
}
else if (minHeap.top().first < iter.second)
{
minHeap.pop();
minHeap.push(pair(iter.second, iter.first));
}
}
for (int i = 0; i < k; i++)
{
result.push_back(minHeap.top().second);
minHeap.pop();
}
return result;
}
};
二叉搜索树中第K小的元素
给定一个二叉搜索树，编写一个函数 kthSmallest 来查找其中第 k 个最小的元素。
说明：
你可以假设 k 总是有效的，1 ≤ k ≤ 二叉搜索树元素个数。
/* 思路：二叉树中序遍历可以得到一个有序数组，然后返回第K个元素
*/
/**
* 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:
void InOrderTraverse(TreeNode* root, vector<int> &vec)
{
if(root != NULL)
{
InOrderTraverse(root->left, vec);
vec.push_back(root->val);
InOrderTraverse(root->right, vec);
}
}
int kthSmallest(TreeNode* root, int k) {
vector<int> vec;
InOrderTraverse(root, vec);
return vec[k-1];
}
};
实现 Trie (前缀树)
实现一个 Trie (前缀树)，包含 insert, search, 和 startsWith 这三个操作。
class TrieNode{
public:
TrieNode* next[26];
bool isword;
TrieNode(){
memset(next,NULL,sizeof(next));
isword=false;
}
~TrieNode(){
for(int i=0;i<26;i++)if(next[i])delete next[i];
}
};
class Trie {
public:
/** Initialize your data structure here. */
TrieNode* root;
Trie() {
root=new TrieNode();
}
/** Inserts a word into the trie. */
void insert(string word) {
TrieNode *node = root;
for (int i = 0; i < word.length(); i++)
{
int pos = word[i] - 'a';
if (node->next[pos])
{
node = node->next[pos];
}
else
{
node->next[pos] = new TrieNode();
node = node->next[pos];
}
}
node->isword = true;
}
/** Returns if the word is in the trie. */
bool search(string word) {
TrieNode *node = root;
for (int i = 0; i < word.length(); i++)
{
int pos = word[i] - 'a';
if (node->next[pos])
{
node = node->next[pos];
}
else
{
return false;
}
}
return node->isword;
}
/** Returns if there is any word in the trie that starts with the given prefix. */
bool startsWith(string prefix) {
TrieNode *node = root;
for (int i = 0; i < prefix.length(); i++)
{
int pos = prefix[i] - 'a';
if (node->next[pos])
{
node = node->next[pos];
}
else
{
return false;
}
}
return true;
}
};
打乱数组
打乱一个没有重复元素的数组。
示例:
// 以数字集合 1, 2 和 3 初始化数组。
int[] nums = {1,2,3};
Solution solution = new Solution(nums);
// 打乱数组 [1,2,3] 并返回结果。任何 [1,2,3]的排列返回的概率应该相同。
solution.shuffle();
// 重设数组到它的初始状态[1,2,3]。
solution.reset();
// 随机返回数组[1,2,3]打乱后的结果。
solution.shuffle();
class Solution {
public:
vector<int> vecNums;
Solution(vector<int>& nums) {
vecNums = nums;
}
/** Resets the array to its original configuration and return it. */
vector<int> reset() {
return vecNums;
}
/** Returns a random shuffling of the array. */
vector<int> shuffle() {
vector<int> res = vecNums;
for(int i = 0; i < res.size(); i++)
{
int t = i + rand() % (res.size() - i);
swap(res[i], res[t]);
}
return res;
}
};
递增的三元子序列
给定一个未排序的数组，判断这个数组中是否存在长度为 3 的递增子序列。
数学表达式如下:
如果存在这样的 i, j, k, 且满足 0 ≤ i < j < k ≤ n-1，
使得 arr[i] < arr[j] < arr[k] ，返回 true ; 否则返回 false 。
说明: 要求算法的时间复杂度为 O(n)，空间复杂度为 O(1) 。
/* 思路：找到当前过的遍历数据中的最小数和第二小的数，然后接下来的数据有大于第二小的数则说明数组中有递增的三元子序列
*/
class Solution {
public:
bool increasingTriplet(vector<int>& nums) {
int min = INT_MAX, secondMin = INT_MAX;
for (int i = 0; i < nums.size(); i++)
{
if (nums[i] <= min)
min = nums[i];
else if (nums[i] < secondMin)
secondMin = nums[i];
else if (nums[i] > secondMin)
return true;
}
return false;
}
};
除自身以外数组的乘积
给定长度为 n 的整数数组 nums，其中 n > 1，返回输出数组 output ，其中 output[i] 等于 nums 中除 nums[i] 之外其余各元素的乘积。
示例:
输入: [1,2,3,4]
输出: [24,12,8,6]
说明: 请不要使用除法，且在 O(n) 时间复杂度内完成此题。
class Solution {
public:
vector<int> productExceptSelf(vector<int>& nums) {
int size = nums.size();
vector<int> res(size, 1);
int mul = 1;
for (int i = 1; i < size; i++)
{
mul = mul * nums[i - 1];
res[i] = mul;
}
mul = 1;
for (int i = size - 2; i >= 0; i--)
{
mul = mul * nums[i + 1];
res[i] = res[i] * mul;
}
for (auto i : res)
{
cout << i << endl;
}
return res;
}
};
有序矩阵中第K小的元素
给定一个 n x n 矩阵，其中每行和每列元素均按升序排序，找到矩阵中第k小的元素。 请注意，它是排序后的第k小元素，而不是第k个元素。
/* 用一个大顶堆存放二维数组中K个最小的元素 */
class Solution {
public:
int kthSmallest(vector<vector<int>>& matrix, int k) {
std::priority_queue<int, std::vector<int>, std::less<int> > maxHeap;
for (int i = 0; i < matrix.size(); i++)
for (int j = 0; j < matrix[i].size(); j++)
{
if (maxHeap.size() < k)
{
maxHeap.push(matrix[i][j]);
}
else if (maxHeap.top() > matrix[i][j])
{
maxHeap.pop();
maxHeap.push(matrix[i][j]);
}
}
return maxHeap.top();
}
};
逆波兰表达式求值
根据逆波兰表示法，求表达式的值。
有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
class Solution {
void getNum(int &num1, int &num2, stack<int> &stNums)
{
num1 = stNums.top();
stNums.pop();
num2 = stNums.top();
stNums.pop();
}
public:
int evalRPN(vector<string>& tokens) {
stack<int> stNums;
int num1,num2;
for (auto it : tokens)
{
if (it == "+")
{
getNum(num1, num2, stNums);
stNums.push(num1 + num2);
}
else if (it == "-")
{
getNum(num1, num2, stNums);
stNums.push(num2 - num1);
}
else if (it == "*")
{
getNum(num1, num2, stNums);
stNums.push(num1 * num2);
}
else if (it == "/")
{
getNum(num1, num2, stNums);
stNums.push(num2 / num1);
}
else
{
stNums.push(stoi(it));
}
}
return stNums.top();
}
};
复制带随机指针的链表
给定一个链表，每个节点包含一个额外增加的随机指针，该指针可以指向链表中的任何节点或空节点。
要求返回这个链表的深拷贝。
class Solution {
public:
Node* copyRandomList(Node* head) {
if (head == NULL)
return NULL;
Node *node = head;
Node *CopyHead = new Node(node->val, NULL, NULL);
Node *CopyNode = CopyHead;
map<Node*, Node*> mapRandom;
mapRandom[node] = CopyNode;
node = node->next;
while(node)
{
CopyNode->next = new Node(node->val, NULL, NULL);
CopyNode = CopyNode->next;
mapRandom[node] = CopyNode;
node = node->next;
}
CopyNode = CopyHead;
node = head;
while(node)
{
if (node->random != NULL)
{
auto iter = mapRandom.find(node->random);
CopyNode->random = iter->second;
}
CopyNode = CopyNode->next;
node = node->next;
}
return CopyHead;
}
};
四数相加 II
给定四个包含整数的数组列表 A , B , C , D ,计算有多少个元组 (i, j, k, l) ，使得 A[i] + B[j] + C[k] + D[l] = 0。
为了使问题简单化，所有的 A, B, C, D 具有相同的长度 N，且 0 ≤ N ≤ 500 。所有整数的范围在 -228 到 228 - 1 之间，最终结果不会超过 231 - 1 。
/* 先让前两个数组相加，将结果存放到map中，然后让后两个数组相加，得到的数取反在map中找，如果找到说明相加为0 */
class Solution {
public:
int fourSumCount(vector<int>& A, vector<int>& B, vector<int>& C, vector<int>& D) {
int res = 0;
map<int, int> sum;
for (int i = 0; i < A.size(); i++)
for (int j = 0; j < B.size(); j++)
{
sum[A[i]+B[j]]++;
}
for (int i = 0; i < C.size(); i++)
for (int j = 0; j < D.size(); j++)
{
int k = C[i]+D[j];
auto iter = sum.find(-k);
if (iter != sum.end())
{
res = res + iter->second;
}
}
return res;
}
};
寻找重复数
给定一个包含 n + 1 个整数的数组 nums，其数字都在 1 到 n 之间（包括 1 和 n），可知至少存在一个重复的整数。假设只有一个重复的整数，找出这个重复的数。
/* 思路：二分查找，判断数组中比中数小的有多少，如果小于等于说明重复数大于中数，
如果大于说明重复数小于中数
*/
class Solution {
public:
int findDuplicate(vector<int>& nums) {
int left = 1;
int right = nums.size();
while(left < right)
{
int mid = (left + right)/2;
int count = 0;
for (auto i : nums)
{
if (i <= mid)
count++;
}
if (count <= mid)
left = mid + 1;
else
right = mid;
}
return right;
}
};
最长连续序列
给定一个未排序的整数数组，找出最长连续序列的长度。要求算法的时间复杂度为 O(n)。
输入: [100, 4, 200, 1, 3, 2]
输出: 4
解释: 最长连续序列是 [1, 2, 3, 4]。它的长度为 4。
/* 首先先把所有num值放入HashSet，然后遍历整个数组，如果HashSet中存在该值，就先向下找到边界，
找的同时把找到的值一个一个从set中删去，然后再向上找边界，同样要把找到的值都从set中删掉。
*/
class Solution {
public:
int longestConsecutive(vector<int>& nums) {
set<int> setNum;
for(auto i : nums)
{
setNum.insert(i);
}
int res = 0;
for(auto i : nums)
{
int count = 1;
int high = i;
int low = i;
while(1)
{
high++;
auto iter = setNum.find(high);
if (iter != setNum.end())
{
count ++;
setNum.erase(high);
}
else
break;
}
while(1)
{
low--;
auto iter = setNum.find(low);
if (iter != setNum.end())
{
count ++;
setNum.erase(low);
}
else
break;
}
res = max(res,count);
}
return res;
}
};
无重复字符的最长子串
给定一个字符串，请你找出其中不含有重复字符的 最长子串 的长度。
/*
滑动窗口，用map存放对应字符的位置，遍历字符串如果在map中找到说明重复，
则从map中删除最左到该字符的所有字符。
*/
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_map<char, int> mapChar;
int maxLength = 0;
int i = 0, j = 0;
while (j < s.size())
{
auto iter = mapChar.find(s[j]);
if (iter != mapChar.end())
{
int k = i;
i = iter->second + 1;
for (; k < i; k++)
{
mapChar.erase(s[k]);
}
}
mapChar[s[j]] = j;
j++;
maxLength = max(maxLength, j - i);
}
return maxLength;
}
};
最长公共前缀
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀，返回空字符串 ““。
/*
以第一个字符为参考
*/
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
string res;
if (strs.size() == 0)
return res;
string firstStr = strs[0];
for(int j = 0; j < firstStr.length(); j++)
{
char c = firstStr[j];
for (int i = 1; i < strs.size(); i++)
{
if (strs[i][j] != c)
return res;
}
res = res + c;
}
return res;
}
};
字符串相乘
给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。
/*
模拟手工乘法
*/
class Solution {
public:
string multiply(string num1, string num2) {
if (num1 == "0" || num2 == "0")
return "0";
int len1 = num1.length();
int len2 = num2.length();
string res(len1 + len2, '0');
int len3 = len1 + len2 - 1;
for (int i = len1 - 1; i >= 0; i--)
{
for (int j = len2 - 1; j >= 0; j--)
{
int t = (num1[i] - '0') * (num2[j] - '0') + res[len3] - '0';
res[len3] = t % 10 + '0';
len3--;
res[len3] = res[len3] + t / 10;
}
len3 = (len1 + len2 - 1) - len1 + i;
}
if (res[0] == '0')
res.erase(0, 1);
return res;
}
};
翻转字符串里的单词
给定一个字符串，逐个翻转字符串中的每个单词。
class Solution {
public:
string reverseWords(string s) {
stack<string> stackStr;
string str;
for (int i = 0; i < s.length(); i++)
{
if (s[i] != ' ')
{
str = str + s[i];
}
else if (str.length() > 0)
{
stackStr.push(str);
str.clear();
}
}
if (str.length() > 0)
stackStr.push(str);
string res;
while (!stackStr.empty())
{
res = res + stackStr.top() + " ";
stackStr.pop();
}
if (res.length() > 0)
res.erase(res.length()-1, 1);
return res;
}
};
简化路径
以 Unix 风格给出一个文件的绝对路径，你需要简化它。或者换句话说，将其转换为规范路径。
在 Unix 风格的文件系统中，一个点（.）表示当前目录本身；此外，两个点 （..） 表示将目录切换到上一级（指向父目录）；两者都可以是复杂相对路径的组成部分。更多信息请参阅：Linux / Unix中的绝对路径 vs 相对路径
请注意，返回的规范路径必须始终以斜杠 / 开头，并且两个目录名之间必须只有一个斜杠 /。最后一个目录名（如果存在）不能以 / 结尾。此外，规范路径必须是表示绝对路径的最短字符串。
/* 用一个栈存放目录名 */
class Solution {
public:
string simplifyPath(string path) {
path = path + '/';
vector<string> vecStr;
string str;
string dot;
for (char c : path)
{
if (c != '/' && c != '.')
{
str = str + c;
}
else if (c == '/')
{
if (!str.empty())
{
if (!dot.empty())
str = dot + str;
vecStr.push_back(str);
str.clear();
}
else if (dot == ".." && !vecStr.empty())
{
vecStr.pop_back();
}
else if (dot.length() > 2)
{
vecStr.push_back(dot);
}
dot.clear();
}
else if (c == '.')
{
dot = dot + c;
}
}
str = string("/");
for (int i = 0; i < vecStr.size(); i++)
{
str = str + vecStr[i] + string("/");
}
if (str.length() > 1)
str.erase(str.length() - 1, 1);
return str;
}
};
最长连续递增序列
给定一个未经排序的整数数组，找到最长且连续的的递增序列。
class Solution {
public:
int findLengthOfLCIS(vector<int>& nums) {
if (nums.size() == 0)
return 0;
int res = 0, count = 0;
for (int i = 0; i < nums.size() - 1; i++)
{
if (nums[i] < nums[i + 1])
{
cout << count << endl;
count++;
}
else
{
res = max(res, count);
count = 0;
}
}
res = max(res, count) + 1;
return res;
}
};
合并两个有序链表
将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode *head;
if (l1 == NULL && l2 == NULL)
return NULL;
if ((l1 && l2 && l1->val <= l2->val) || (l2 == NULL && l1))
{
head = l1;
l1 = l1->next;
}
else
{
head = l2;
l2 = l2->next;
}
ListNode *res = head;
while(l1 || l2)
{
if ((l1 && l2 && l1->val <= l2->val) || (l2 == NULL && l1))
{
res->next = l1;
l1 = l1->next;
}
else
{
res->next = l2;
l2 = l2->next;
}
res = res->next;
}
return head;
}
};
两数相加
给出两个 非空 的链表用来表示两个非负的整数。其中，它们各自的位数是按照 逆序 的方式存储的，并且它们的每个节点只能存储 一位 数字。
如果，我们将这两个数相加起来，则会返回一个新的链表来表示它们的和。
您可以假设除了数字 0 之外，这两个数都不会以 0 开头。
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
ListNode *head = new ListNode(0);
ListNode *node = head;
int flag = 0;
while(l1 || l2)
{
int sum = 0;
if (l1 && l2)
{
sum = l1->val + l2->val + flag;
l2 = l2->next;
l1 = l1->next;
}
else if (l1)
{
sum = l1->val + flag;
l1 = l1->next;
}
else if(l2)
{
sum = l2->val + flag;
l2 = l2->next;
}
if (sum >= 10)
{
node->val = sum%10;
flag = 1;
}
else
{
node->val = sum;
flag = 0;
}
if (l1 || l2 || flag == 1)
{
node->next = new ListNode(1);
node = node->next;
}
}
return head;
}
};
合并K个排序链表
合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度。
/* 遍历所有链表的数据到multimap，然后遍历一遍multimap */
class Solution {
public:
ListNode* mergeKLists(vector<ListNode*>& lists) {
ListNode *head = NULL;
multimap<int, ListNode*> mapValue;
for (int i = 0; i < lists.size(); i++)
{
ListNode *node = lists[i];
while(node)
{
mapValue.insert(pair(node->val, node));
node = node->next;
}
}
if (mapValue.size() >= 1)
{
head = mapValue.begin()->second;
ListNode *node = head;
for (multimap<int, ListNode*>::iterator iter = mapValue.begin(); iter != mapValue.end(); )
{
iter++;
if (iter != mapValue.end())
{
node->next = iter->second;
node = node->next;
}
}
}
return head;
}
};
计算二叉树的深度
输入一棵二叉树，求该树的深度。从根结点到叶结点依次经过的结点（含根、叶结点）形成树的一条路径，最长路径的长度为树的深度。
/* 利用队列层序遍历，记录层数 */
class Solution {
public:
int TreeDepth(TreeNode* pRoot)
{
if (pRoot == NULL)
return 0;
queue<TreeNode*> que;
que.push(pRoot);
int depth = 0;
while(!que.empty())
{
depth++;
int count = 0;
int size = que.size();
while(count < size)
{
TreeNode* node = que.front();
if (node->left)
que.push(node->left);
if (node->right)
que.push(node->right);
count ++;
que.pop();
}
}
return depth;
}
};
两数之和
给定一个整数数组 nums 和一个目标值 target，请你在该数组中找出和为目标值的那 两个 整数，并返回他们的数组下标。你可以假设每种输入只会对应一个答案。但是，数组中同一个元素不能使用两遍。
func twoSum(nums []int, target int) []int {
mapValues := make(map[int]int)
result := make([]int, 2)
for i, v := range nums {
if j, ok := mapValues[v]; ok {
if target - v == v {
result[0] = i
result[1] = j
return result
}
} else {
mapValues[v] = i
}
}
for i, v := range nums {
if j, ok := mapValues[target - v]; ok {
if i != j {
result[0] = i
result[1] = j
return result
}
}
}
return result
}
三数之和
给你一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？请你找出所有满足条件且不重复的三元组。注意：答案中不可以包含重复的三元组。
// 排序加双指针
func threeSum(nums []int) [][]int {
sort.Ints(nums) // 排序
var result [][]int
length := len(nums)
for i := 0; i < length - 2; i++ {
left := i+1
right := length - 1
target := 0 - nums[i]
if i > 0 && nums[i] == nums[i-1] {
continue // 跳过重复元素
}
for left < right {
if nums[left] + nums[right] == target {
res := make([]int, 3)
res[0] = nums[i]
res[1] = nums[left]
res[2] = nums[right]
result = append(result,res)
for (left < right) && (nums[left] == nums[left+1]) {
left++ // 跳过重复元素
}
for (left < right) && (nums[right] == nums[right-1]) {
right-- // 跳过重复元素
}
left++
right--
} else if nums[left] + nums[right] < target {
left++
} else {
right--
}
}
}
return result
}
有效的括号
给定一个只包括 ‘(‘，’)’，’{‘，’}’，’[‘，’]’ 的字符串，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
class Solution {
public:
bool isValid(string s) {
vector<char> vecChar;
for (char c : s) {
if ((vecChar.size() > 0) &&
((vecChar[vecChar.size() - 1] == '(' && c == ')') ||
(vecChar[vecChar.size() - 1] == '{' && c == '}') ||
(vecChar[vecChar.size() - 1] == '[' && c == ']'))) {
vecChar.pop_back();
}
else
vecChar.push_back(c);
}
if (vecChar.size() == 0)
return true;
else
return false;
}
};
删除排序数组中的重复项
给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。 不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
// 双指针解法
func removeDuplicates(nums []int) int {
var count int = 0
for i := 0; i < len(nums); i++ {
if nums[count] != nums[i] {
count++
nums[count] = nums[i]
}
}
return count + 1
}
盛最多水的容器
给你 n 个非负整数 a1，a2，…，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
// 双指针解法
func min(x, y int) int {
if x < y {
return x
}
return y
}
func maxArea(height []int) int {
var result int = math.MinInt32
left := 0
right := len(height) - 1
for left < right {
t := min(height[left], height[right]) * (right - left)
if t > result {
result = t
}
if height[left] > height[right] {
right--
} else {
left++
}
}
return result
}
反转字符串中的单词 III
给定一个字符串，你需要反转字符串中每个单词的字符顺序，同时仍保留空格和单词的初始顺序。
示例 1:
输入: “Let’s take LeetCode contest”
输出: “s’teL ekat edoCteeL tsetnoc”
func Reverse(s string) string {
r := []rune(s)
for i, j := 0, len(r)-1; i < j; i, j = i+1, j-1 {
r[i], r[j] = r[j], r[i]
}
return string(r)
}
func reverseWords(s string) string {
var result string
items := strings.Split(s, " ")
for _, i := range items {
result = result + Reverse(i) + " "
}
return strings.TrimRight(result, " ")
}
旋转链表
给定一个链表，旋转链表，将链表每个节点向右移动 k 个位置，其中 k 是非负数。
示例 1:
输入: 1->2->3->4->5->NULL, k = 2
输出: 4->5->1->2->3->NULL
解释:
向右旋转 1 步: 5->1->2->3->4->NULL
向右旋转 2 步: 4->5->1->2->3->NULL
/**
* Definition for singly-linked list.
* type ListNode struct {
* Val int
* Next *ListNode
* }
* 双指针法
*/
func rotateRight(head *ListNode, k int) *ListNode {
if head == nil {
return head
}
var node *ListNode = head
var left *ListNode = head
var right *ListNode = head
var count int = 0
for node != nil { // 计算链表长度
node = node.Next
count++
}
k = k % count // 计算最小移动次数
if count == 1 || k == 0 { // 不需要移动
return head
}
for i := 0; i < k; i++ { // 计算位置K的节点
right = right.Next
}
for right.Next != nil { // 从位置K开始移动到链表末尾
left = left.Next
right = right.Next
}
right.Next = head // 将left到right这段截断，放在链表头部
head = left.Next
left.Next = nil
return head
}
整数反转
给出一个 32 位的有符号整数，你需要将这个整数中每位上的数字进行反转。
假设我们的环境只能存储得下 32 位的有符号整数，则其数值范围为 [−2^31, 2^31 − 1]。请根据这个假设，如果反转后整数溢出那么就返回 0。
func reverse(x int) int {
var result int
for x != 0 {
result = result * 10 + x % 10
x = x / 10
}
if result > math.MaxInt32 || result < math.MinInt32 {
result = 0
}
return result
}
回文数
判断一个整数是否是回文数。回文数是指正序（从左向右）和倒序（从右向左）读都是一样的整数。
func isPalindrome(x int) bool {
if x < 0 {
return false
}
y := x
var result int
for x != 0 { // 整数反转
result = result * 10 + x % 10
x = x / 10
}
if result == y {
return true
}
return false
}
2的幂
给定一个整数，编写一个函数来判断它是否是 2 的幂次方。
// 如果 n 为 2 的幂则满足 n & (n - 1) == 0
func isPowerOfTwo(n int) bool {
if n > 0 && n & (n - 1) == 0 {
return true
}
return false
}