很早就想在上面刷题,但是后来路偏了,跑去弄公众号了。现在借着考研来刷题,顺便提前温习一下数据结构的一些算法和C++的用法。
20200402
给定一个整数数组nums
和一个目标值target
,请你在该数组中找出和为目标值的那两个整数,并返回他们的数组下标。
你可以假设每种输入只会对应一个答案。但是,你不能重复利用这个数组中同样的元素。
示例:
给定 nums = [2, 7, 11, 15], target = 9
因为 nums[0] + nums[1] = 2 + 7 = 9
所以返回 [0, 1]
class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
int len = nums.size();
for(int i=0;i < len - 1;i++)
{
for(int j = i+1;j < len;j++)
{
if(nums[i]+nums[j]==target)
return {i,j};
}
}
return {};
}
};
20200404
给定 n 个非负整数表示每个宽度为 1 的柱子的高度图,计算按此排列的柱子,下雨之后能接多少雨水。
上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表示的高度图,在这种情况下,可以接 6 个单位的雨水(蓝色部分表示雨水)。
示例:
输入: [0,1,0,2,1,0,1,3,2,1,2,1]
输出: 6
class Solution {
public:
int trap(vector<int>& height) {
int sum = 0;
int size = height.size();
for(int i = 1;i < size - 1;i++)
{
int max_left = 0,max_right = 0;
for(int j = i;j >= 0;j--)
{
max_left = max(max_left,height[j]);
}
for(int m = i;m < size;m++)
{
max_right = max(max_right,height[m]);
}
sum+=min(max_left,max_right)-height[i];
}
return sum;
}
};
20200405
给出一个 32 位的有符号整数,你需要将这个整数中每位上的数字进行反转。
示例:
输入: 123
输出: 321
输入: -123
输出: -321
输入: 120
输出: 21
class Solution {
public:
int reverse(long int x) {
int y = 0;
int i = 1;
if(x < 0)
{
i = -1;
}
int m = abs(x);
if(m >= 10)
{
while(m >= 10)
{
int b = 0;
b = m%10;
m = (m-b)/10;
y = y*10 + b;
}
y = y*10+m;
}
else
{
y=m;
}
return i*y;
}
};
20200407
判断一个整数是否是回文数。回文数是指正序(从左向右)和倒序(从右向左)读都是一样的整数。
示例 1:
输入: 121
输出: true
示例 2:
输入: -121
输出: false
解释: 从左向右读, 为 -121 。 从右向左读, 为 121- 。因此它不是一个回文数。
示例 3:
输入: 10
输出: false
解释: 从右向左读, 为 01 。因此它不是一个回文数。
class Solution {
public:
bool isPalindrome(int x) {
int m = x;
long long n = 0;
if(x < 0)
return false;
else
while(m!=0)
{
n = m%10 + n*10;
m = (m-m%10)/10;
}
if(n == x)
return true;
else
return false;
}
};
20200412
罗马数字包含以下七种字符: I
,V
,X
,L
,C
,D
和 M
。
字符 数值
I 1
V 5
X 10
L 50
C 100
D 500
M 1000
例如, 罗马数字 2 写做II
,即为两个并列的 1。12 写做XII
,即为X + II
。 27 写做XXVII
, 即为XX + V + II
。
通常情况下,罗马数字中小的数字在大的数字的右边。但也存在特例,例如 4 不写做IIII
,而是IV
。数字 1 在数字 5 的左边,所表示的数等于大数 5 减小数 1 得到的数值 4 。同样地,数字 9 表示为IX
。这个特殊的规则只适用于以下六种情况:
I 可以放在 V (5) 和 X (10) 的左边,来表示 4 和 9。
X 可以放在 L (50) 和 C (100) 的左边,来表示 40 和 90。
C 可以放在 D (500) 和 M (1000) 的左边,来表示 400 和 900。
给定一个罗马数字,将其转换成整数。输入确保在 1 到 3999 的范围内。
示例 1:
输入: "III"
输出: 3
示例 2:
输入: "IV"
输出: 4
示例 3:
输入: "IX"
输出: 9
示例 4:
输入: "LVIII"
输出: 58
解释: L = 50, V= 5, III = 3.
示例 5:
输入: "MCMXCIV"
输出: 1994
解释: M = 1000, CM = 900, XC = 90, IV = 4.
class Solution {
public:
int value = 0;
int num(int a)
{
switch(a)
{
case 'I':value=1;break;
case 'V':value=5;break;
case 'X':value=10;break;
case 'L':value=50;break;
case 'C':value=100;break;
case 'D':value=500;break;
case 'M':value=1000;break;
default :break;
}
return value;
}
int romanToInt(string s) {
int add = 0,sub = 0;
for(int i = 0;i < s.size()-1;++i)
{
if(num(s[i]) < num(s[i+1]))
sub-=num(s[i]);
else
add+=num(s[i]);
}
add+=num(s.back());
return add+sub;
}
};
20200413
编写一个函数来查找字符串数组中的最长公共前缀。
如果不存在公共前缀,返回空字符串 ""。
示例 1:
输入: ["flower","flow","flight"]
输出: "fl"
示例 2:
输入: ["dog","racecar","car"]
输出: ""
解释: 输入不存在公共前缀。
说明:
所有输入只包含小写字母 a-z 。
class Solution {
public:
string longestCommonPrefix(vector<string>& strs) {
if(strs.size()==0) return "";
for(int i=0;i<strs[0].size();i++)
for(int j=1;j<strs.size();j++)
if(strs[0][i] != strs[j][i])
return strs[0].substr(0,i);
return strs[0];
}
};
20200418
给定一个只包括 '(',')','{','}','[',']' 的字符串,判断字符串是否有效。
有效字符串需满足:
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。
示例 1:
输入: "()"
输出: true
示例 2:
输入: "()[]{}"
输出: true
示例 3:
输入: "(]"
输出: false
示例 4:
输入: "([)]"
输出: false
示例 5:
输入: "{[]}"
输出: true
class Solution {
public:
bool isValid(string s) {
stack<char> st;
for(int i=0;i < s.size();i++)
{
if(st.empty()&&(s[i] == ')' || s[i] == '}' || s[i] == ']'))
return false;
else if(s[i] == ')' || s[i] == '}' || s[i] == ']')
{
if(s[i]-st.top()==1||s[i]-st.top() == 2) //ASCII码相差1或2
st.pop();
else
return false;
}
else
st.push(s[i]);
}
return st.empty();
}
};
20200420
将两个升序链表合并为一个新的升序链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
示例:
输入:1->2->4, 1->3->4
输出:1->1->2->3->4->4
class Solution {
public:
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
if(l1 == NULL)
return l2;
if(l2 == NULL)
return l1;
if(l1->val <= l2->val)
{
l1->next = mergeTwoLists(l1->next,l2);
return l1;
}
l2->next = mergeTwoLists(l1,l2->next);
return l2;
}
};
给定一个排序数组,你需要在 原地 删除重复出现的元素,使得每个元素只出现一次,返回移除后数组的新长度。
不要使用额外的数组空间,你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。
示例 1:
给定数组 nums = [1,1,2],
函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,0,1,1,1,2,2,3,3,4],
函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。
你不需要考虑数组中超出新长度后面的元素。
class Solution {
public:
int removeDuplicates(vector<int>& nums) {
if(!nums.size()) return 0;
int index = 0;
for(int i = 0;i < nums.size();i++)
{
if(nums[index]!=nums[i])
nums[++index] = nums[i];
}
return index+1;
}
};
给你一个数组 nums 和一个值 val,你需要 原地 移除所有数值等于 val 的元素,并返回移除后数组的新长度。
不要使用额外的数组空间,你必须仅使用 O(1) 额外空间并 原地 修改输入数组。
元素的顺序可以改变。你不需要考虑数组中超出新长度后面的元素。
示例 1:
给定 nums = [3,2,2,3], val = 3,
函数应该返回新的长度 2, 并且 nums 中的前两个元素均为 2。
你不需要考虑数组中超出新长度后面的元素。
示例 2:
给定 nums = [0,1,2,2,3,0,4,2], val = 2,
函数应该返回新的长度 5, 并且 nums 中的前五个元素为 0, 1, 3, 0, 4。
注意这五个元素可为任意顺序。
你不需要考虑数组中超出新长度后面的元素。
class Solution {
public:
int removeElement(vector<int>& nums, int val) {
int index = 0;
if(!nums.size()) return 0;
for(int i = 0;i < nums.size();i++)
{
if(nums[i] != val)
{
nums[index] = nums[i];
index++;
}
}
return index;
}
};
20200421
实现 strStr() 函数。
给定一个 haystack 字符串和一个 needle 字符串,在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在,则返回 -1。
示例 1:
输入: haystack = "hello", needle = "ll"
输出: 2
示例 2:
输入: haystack = "aaaaa", needle = "bba"
输出: -1
class Solution {
public:
int strStr(string haystack, string needle) {
if(needle.empty()) return 0;
int i = 0,j=0;
while(haystack[i] != '\0' && needle[j] != '\0')
{
if(haystack[i] == needle[j])
{
i++;
j++;
}
else
{
i = i-j+1;
j=0;
}
}
if(needle[j]=='\0')
return i-j;
return -1;
}
};
给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。
你可以假设数组中无重复元素。
示例 1:
输入: [1,3,5,6], 5
输出: 2
示例 2:
输入: [1,3,5,6], 2
输出: 1
示例 3:
输入: [1,3,5,6], 7
输出: 4
示例 4:
输入: [1,3,5,6], 0
输出: 0
class Solution {
public:
int searchInsert(vector<int>& nums, int target) {
int i=0;
for(i ;i < nums.size();i++)
{
if(nums[i] >= target)
return i;
}
return i;
}
};
「外观数列」是一个整数序列,从数字 1 开始,序列中的每一项都是对前一项的描述。前五项如下:
- 1
- 11
- 21
- 1211
- 111221
1 被读作 "one 1" ("一个一") , 即 11。 - 被读作 "two 1s" ("两个一"), 即 21。
- 被读作 "one 2", "one 1" ("一个二" , "一个一") , 即 1211。
给定一个正整数 n(1 ≤ n ≤ 30),输出外观数列的第 n 项。
注意:整数序列中的每一项将表示为一个字符串。
示例 1:
输入: 1
输出: "1"
解释:这是一个基本样例。
示例 2:
输入: 4
输出: "1211"
解释:当 n = 3 时,序列是 "21",其中我们有 "2" 和 "1" 两组,"2" 可以读作 "12",也就是出现频次 = 1 而 值 = 2;类似 "1" 可以读作 "11"。所以答案是 "12" 和 "11" 组合在一起,也就是 "1211"。
class Solution {
public:
string countAndSay(int n) {
string result = "1";
for(int i=1;i<n;i++)
{
result = add(result);
}
return result;
}
string add(string s)
{
int num = 1;
string str1 = "\0";
for(int i = 0;i<s.size();i++)
{
if(s[i]==s[i+1])
num++;
else
{
str1+= num+'0';
str1+= s[i];
num=1;
}
}
return str1;
}
};
20200422
给定一个整数数组 nums ,找到一个具有最大和的连续子数组(子数组最少包含一个元素),返回其最大和。
示例:
输入: [-2,1,-3,4,-1,2,1,-5,4],
输出: 6
解释: 连续子数组 [4,-1,2,1] 的和最大,为 6。
class Solution {
public:
int maxSubArray(vector<int>& nums) {
int max = INT_MIN;
for(int i = 0;i<nums.size();i++)
{
int sum = 0;
for(int j = i;j<nums.size();j++)
{
sum+=nums[j];
if(sum > max)
max = sum;
}
}
return max;
}
};
给定一个仅包含大小写字母和空格 ' ' 的字符串 s,返回其最后一个单词的长度。如果字符串从左向右滚动显示,那么最后一个单词就是最后出现的单词。
如果不存在最后一个单词,请返回 0 。
说明:一个单词是指仅由字母组成、不包含任何空格字符的 最大子字符串。
示例:
输入: "Hello World"
输出: 5
class Solution {
public:
int lengthOfLastWord(string s) {
int sum = 0;
int len = s.size();
for(int i = len-1;i>=0;i--)
{
if(s[i]!=' ')
sum++;
else
if(sum!=0)
return sum;
}
return sum;
}
};
给定一个由整数组成的非空数组所表示的非负整数,在该数的基础上加一。
最高位数字存放在数组的首位, 数组中每个元素只存储单个数字。
你可以假设除了整数 0 之外,这个整数不会以零开头。
示例 1:
输入: [1,2,3]
输出: [1,2,4]
解释: 输入数组表示数字 123。
示例 2:
输入: [4,3,2,1]
输出: [4,3,2,2]
解释: 输入数组表示数字 4321。
class Solution {
public:
vector<int> plusOne(vector<int>& digits) {
for(int i = digits.size()-1;i>=0;i--)
{
digits[i]++;
if(digits[i]!=10)
return digits;
else
digits[i]=0;
}
digits.insert(digits.begin(),1);
return digits;
}
};
20200423
给你两个二进制字符串,返回它们的和(用二进制表示)。
输入为 非空 字符串且只包含数字 1 和 0。
示例 1:
输入: a = "11", b = "1"
输出: "100"
示例 2:
输入: a = "1010", b = "1011"
输出: "10101"
class Solution {
public:
string addBinary(string a, string b) {
int lena = a.size();
int lenb = b.size();
while(lena < lenb)
{
a = '0'+a;
lena++;
}
while(lenb< lena)
{
b = '0'+b;
lenb++;
}
for(int i = lena-1;i>0;i--)
{
a[i] = a[i] - '0' + b[i];
if(a[i] >= '2')
{
a[i] = (a[i] - '0')%2 + '0';
a[i-1]=a[i-1]+1;
}
}
a[0] = a[0] - '0' + b[0];
if(a[0] >= '2')
{
a[0] = (a[0] - '0')%2 + '0';
a = '1'+a;
}
return a;
}
};
20200424
假设你正在爬楼梯。需要 n 阶你才能到达楼顶。
每次你可以爬 1 或 2 个台阶。你有多少种不同的方法可以爬到楼顶呢?
注意:给定 n 是一个正整数。
示例 1:
输入: 2
输出: 2
解释: 有两种方法可以爬到楼顶。
- 1 阶 + 1 阶
- 2 阶
示例 2:
输入: 3
输出: 3
解释: 有三种方法可以爬到楼顶。
- 1 阶 + 1 阶 + 1 阶
- 1 阶 + 2 阶
2 阶 + 1 阶
class Solution {
public:int climbStairs(int n) { long long sum[] = {1,1,0}; for(int i = 1;i <= n;i++) { sum[2] = sum[1] + sum[0]; sum[0] = sum[1]; sum[1] = sum[2]; } return sum[0]; }
};
给定一个排序链表,删除所有重复的元素,使得每个元素只出现一次。
示例 1:
输入: 1->1->2
输出: 1->2
示例 2:
输入: 1->1->2->3->3
输出: 1->2->3
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
ListNode* i = head;
ListNode* j = head;
if(head==NULL) return 0;
while(j!=NULL)
{
if(i->val!=j->val)
{
i->next=j;
i=i->next;
}
j = j->next;
}
i->next = NULL;
return head;
}
};
给你两个有序整数数组 nums1 和 nums2,请你将 nums2 合并到 nums1 中,使 nums1 成为一个有序数组。
说明:
初始化 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) {
int i = nums1.size()-1;
m--;
n--;
while(n>=0)
{
while(m>=0 && nums1[m]>nums2[n])
{
swap(nums1[i--],nums1[m--]);
}
swap(nums2[n--],nums1[i--]);
}
}
};
20200425
给定两个二叉树,编写一个函数来检验它们是否相同。
如果两个树在结构上相同,并且节点具有相同的值,则认为它们是相同的。
示例 1:
输入:
1 1
/ \ / \
2 3 2 3
[1,2,3], [1,2,3]
输出: true
示例 2:
输入:
1 1
/ \
2 2
[1,2], [1,null,2]
输出: false
示例 3:
输入:
1 1
/ \ / \
2 1 1 2
[1,2,1], [1,1,2]
输出: false
/**
* 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 isSameTree(TreeNode* p, TreeNode* q) {
if(!p&&!q) return true;
if(!p || !q) return false;
return (p->val == q->val)&&(isSameTree(p->left,q->left))&&(isSameTree(p->right,q->right));
}
};
给定一个二叉树,检查它是否是镜像对称的。
例如,二叉树 [1,2,2,3,4,4,3] 是对称的。
1
/ \
2 2
/ \ / \
3 4 4 3
但是下面这个 [1,2,2,null,3,null,3] 则不是镜像对称的:
1
/ \
2 2
\ \
3 3
/**
* 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 isSymmetric(TreeNode* root) {
if(!root) return true;
return (down(root->left,root->right));
}
private:
bool down(TreeNode* root1,TreeNode* root2)
{
if(!root1 && !root2) return true;
if(!root1 || !root2) return false;
if(root1->val != root2->val) return false;
return (down(root1->left,root2->right)&&down(root1->right,root2->left));
}
};
给定一个二叉树,找出其最大深度。
二叉树的深度为根节点到最远叶子节点的最长路径上的节点数。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回它的最大深度 3 。
/**
* 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 maxDepth(TreeNode* root) {
if(!root) return 0;
return max(maxDepth(root->left),maxDepth(root->right))+1;
}
};
20200426
给定一个二叉树,返回其节点值自底向上的层次遍历。 (即按从叶子节点所在层到根节点所在的层,逐层从左向右遍历)
例如:
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回其自底向上的层次遍历为:
[
[15,7],
[9,20],
[3]
]
/**
* 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:
vector<vector<int>> levelOrderBottom(TreeNode* root) {
vector<vector<int>> res;
getres(root,0,res);
reverse(res.begin(),res.end());
return res;
}
void getres(TreeNode* node,int level,vector<vector<int>>& res)
{
if(!node) return;
if(res.size()==level) res.push_back({});
res[level].push_back(node->val);
if(node->left) getres(node->left,level+1,res);
if(node->right) getres(node->right,level+1,res);
}
};
20200427
将一个按照升序排列的有序数组,转换为一棵高度平衡二叉搜索树。
本题中,一个高度平衡二叉树是指一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过 1。
示例:
给定有序数组: [-10,-3,0,5,9],
一个可能的答案是:[0,-3,9,-10,null,5],它可以表示下面这个高度平衡二叉搜索树:
0
/ \
-3 9
/ /
-10 5
/**
* 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* sortedArrayToBST(vector<int>& nums) {
if(nums.size()==0) return NULL;
if(nums.size()==1) return new TreeNode(nums[0]);
int mid = (nums.size())/2;
TreeNode* node = new TreeNode(nums[mid]);
vector<int> nums_left(nums.begin(),nums.begin()+mid);
node->left=sortedArrayToBST(nums_left);
vector<int> nums_right(nums.begin()+mid+1,nums.end());
node->right=sortedArrayToBST(nums_right);
return node;
}
};
20200429
给定一个二叉树,判断它是否是高度平衡的二叉树。
本题中,一棵高度平衡二叉树定义为:
一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。
示例 1:
给定二叉树 [3,9,20,null,null,15,7]
3
/ \
9 20
/ \
15 7
返回 true 。
示例 2:
给定二叉树 [1,2,2,3,3,null,null,4,4]
1
/ \
2 2
/ \
3 3
/ \
4 4
返回 false 。
class Solution {
public:
bool isBalanced(TreeNode* root) {
if(!root) return true;
int d = abs(deepth(root->left)-deepth(root->right));
return (d<=1)&&isBalanced(root->left)&&isBalanced(root->right);
}
int deepth(TreeNode* root)
{
if(!root) return 0;
return max(deepth(root->left),deepth(root->right))+1;
}
};
20200430
给定一个二叉树,找出其最小深度。
最小深度是从根节点到最近叶子节点的最短路径上的节点数量。
说明: 叶子节点是指没有子节点的节点。
示例:
给定二叉树 [3,9,20,null,null,15,7],
3
/ \
9 20
/ \
15 7
返回它的最小深度2.
class Solution {
public:
int minDepth(TreeNode* root) {
if(!root) return 0;
int level=1;
if(!root->left && !root->right) return level;
if(!root->right) return minDepth(root->left)+level;
if(!root->left) return minDepth(root->right)+level;
return min(minDepth(root->left),minDepth(root->right))+level;
}
};