杨辉三角
给定一个非负整数numRows,生成杨辉三角的前numRows行。
在杨辉三角中,每个树是它左上方和右上方的数的和。
class Solution{
public:
vector<vector<int>> generate(int numRows){
vector<vector<int>> ret(numRows);
for(int i=0; i<numRows; i++){
ret[i].resize(i+1);
ret[i][0] = ret[i][i] = 1;
for(int j=1; j<=i-1; j++){
ret[i][j] = ret[i-1][j-1] + ret[i-1][j];
}
}
return ret;
}
}
杨辉三角
给定一个非负索引rowIndex,返回杨辉三角的第rowIndex行。
class Solution {
public:
vector<int> getRow(int rowIndex) {
vector<vector<int>> ret(rowIndex+1);
for(int i=0; i<=rowIndex; i++){
ret[i].resize(i+1);
ret[i][0] = ret[i][i] = 1;
for(int j=1; j<=i-1; j++){
ret[i][j] = ret[i-1][j-1] + ret[i-1][j];
}
}
return ret[rowIndex];
}
};
买股票的最佳时机
给定一个数组prices,它的第i个元素表示一支给定股票的第i天的价格。
只能选择某一天买入,并在不一样的日子卖出,来获得最大利润。
暴力法,超时
class Solution {
public:
int maxProfit(vector<int>& prices) {
int res = 0;
int length = prices.size();
for(int i=0; i<length; i++){
for(int j=i+1; j<length; j++){
res = max(res, prices[j]-prices[i]);
}
}
return res;
}
};
一次遍历
假设给定数组为:[7,1,5,3,6,4];
如果我们在图表上绘制给定数组中的数字,我们将会得到:
在题目中,我们只要用一个变量记录一个历史最低价格minprice,假设股票是在那天买的,第i天卖出股票就能得到利润prices[i] - minprice。
验证回文串
将所有大写字符转换为小写字符,并移除所有非字母数字字符之后,短语正着读和反着读都一样。则可以认为该短语是一个回文串。
class Solution {
public:
bool isPalindrome(string s) {
int left = 0;
int right = s.size()-1;
while(left<right){
while(left<right && !isalnum(s[left])){
left++;
}
while(left<right && !isalnum(s[right])){
right--;
}
if(tolower(s[left]) != tolower(s[right])){
return false;
}
left++;
right--;
}
return true;
}
};
只出现一次的数字
给定一个非空整数数组nums,除了某个元素只出现一次意外,其余每个元素均出现2次,找到那个只出现一次的元素。
必须设计并实现线性时间复杂度的算法解决次问题,且算法只使用常量额外空间。
如何能做到线性时间复杂度和常数空间复杂度?
使用位运算
异或运算
数组中的全部元素的异或运算结果即为数组中只出现一次的数字。
class Solution {
public:
int singleNumber(vector<int>& nums) {
int sum = 0;
for(int i=0; i<nums.size(); i++){
sum ^= nums[i];
}
return sum;
}
};
环形链表
给一个链表的头节点head,判断链表中是否有环。
如果链表中有某个节点,可以通过连续跟踪next指针再次到达,则链表中存在环。
为了表示给定链表中的环,测评系统内部使用整数pos来表示链表尾连接到链表中的位置。
哈希表
最容易想到的方法就是遍历所有节点,每次遍历一个节点时,判断该节点此前是否被访问过。
使用哈希表存储已经访问过的节点。每次到达一个节点,如果该节点已经存在于哈希表中,则说明该链表是环形链表,否则就将该节点加入哈希表中。
/**
* 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<ListNode*> seen;
while(head != nullptr){
if(seen.count(head)){
return true;
}
seen.insert(head);
head = head->next;
}
return false;
}
};
快慢指针
乌龟和兔子在链表上移动,兔子跑得快,乌龟跑得慢。
若链表中没有环,兔子会一直处于乌龟前方。
若链表中有环,兔子会先于乌龟进入环,并且一直在环内移动,等乌龟进入环时,它们某一时刻一定相遇。
定义两个指针,慢指针每次移动一步,快指针每次移动两步。
初始时,慢指针在head,快指针在head.next,若在移动过程中,快指针反过来追上慢指针,说明链表是环形。
若快指针到达链表尾部,则不是。
class Solution{
public:
hasCycle(ListNode *head){
if(head==nullptr)
return false;
ListNode* slow = head;
ListNode* quick = head->next;
while(quick != nullptr){
if(quick == slow){
return true;
}
slow = slow->next;
quick = quick->next->next;
}
}
}
相交链表
判断两个链表是否相交,可以使用哈希集合存储链表节点。
首先遍历链表headA,并将链表headA中的每个节点加入哈希集合中。
然后遍历链表 headB\textit{headB}headB,对于遍历到的每个节点,判断该节点是否在哈希集合中:
如果当前节点不在哈希集合中,则继续遍历下一个节点;
如果当前节点在哈希集合中,则后面的节点都在哈希集合中,即从当前节点开始的所有节点都在两个链表的相交部分,因此在链表 headB\textit{headB}headB 中遍历到的第一个在哈希集合中的节点就是两个链表相交的节点,返回该节点。