Best Time to Buy and Sell Stock
"""扫描，time n, space 1 9 ms, beats 10.54% """
class Solution {
public:
int maxProfit(vector<int>& prices) {
int small_id = 0;
int value = 0;
for (int i=0; i<prices.size(); i++){
if(prices[i] < prices[small_id])
small_id = i;
value = max(value, prices[i] - prices[small_id]);
}
return value;
}
};Best Time to Buy and Sell Stock II
"""略。 """Valid Palindrome
"""细节比较麻烦 """
class Solution {
public:
bool isAlpha(char c){
return ((c>='a' && c<='z') || (c>='A' && c<='Z'));
}
bool isNumeric(char c){
return (c>='0' && c<= '9');
}
int isAlphanumeric (char c){
if(isAlpha(c))
return 1;
if(isNumeric(c))
return 2;
return 0;
}
bool isPalindrome(string s) {
if(s.size() == 0)
return true;
int j = s.size()-1;
for(int i=0; i<s.size(); i++){
if(j <= i)
return true;
int temp = isAlphanumeric(s[i]);
if(temp){
while(!isAlphanumeric(s[j]) && j>=i)
j--;
if(isAlphanumeric(s[j]) != temp)
return false;
if(s[i] != s[j] && s[i] != s[j] - 'A' + 'a' && s[i] != s[j] - 'a' + 'A')
return false;
j--;
}
}
return true;
}
};Single Number
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?
"""有难度。 """Linked List Cycle
"""Two Pointers """
/** * 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) {
ListNode *fast = head;
ListNode *slow = head;
while(fast){
if(fast->next){
fast = fast->next->next;
slow = slow->next;
if(slow == fast)
return true;
}
else
return false;
}
return false;
}
};
Min Stack
"""数据结构。两个栈实现。 """
class MinStack {
public:
/** initialize your data structure here. */
MinStack() {}
void push(int x) {
s1.push(x);
if(s2.empty() || x<=s2.top()) s2.push(x);
}
void pop() {
if(s1.top() == s2.top()) s2.pop();
s1.pop();
}
int top() {
return s1.top();
}
int getMin() {
return s2.top();
}
private:
stack <int> s1, s2;
};"""一个栈。 """
class MinStack {
public:
/** initialize your data structure here. */
MinStack() {
min_ = INT_MAX;
}
void push(int x) {
if(x<=min_){
s1.push(min_);
min_ = x;
}
s1.push(x);
}
void pop() {
if(s1.top()==min_){
s1.pop();
min_ = s1.top();
s1.pop();
}
else
s1.pop();
}
int top() {
return s1.top();
}
int getMin() {
return min_;
}
private:
stack <int> s1;
int min_;
};Intersection of Two Linked Lists
"""和前面Linked List Cycle很像。 """
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
ListNode *pA = headA;
ListNode *pB = headB;
bool temp1 = true;
bool temp2 = true;
if(pA == NULL || pB == NULL)
return NULL;
while (true){
if(pA==NULL && temp1){
pA = headB;
temp1 = false;
}
else if(pA==NULL)
return NULL;
if(pB==NULL && temp2){
pB = headA;
temp2 = false;
}
else if(pB==NULL)
return NULL;
if(pA == pB)
return pA;
pA = pA->next;
pB = pB->next;
}
}
};Two Sum II - Input array is sorted
"""熟题。利用sorted，可以节省构建哈希表的空间。 """
class Solution {
public:
vector<int> twoSum(vector<int>& numbers, int target) {
vector<int> re;
int i =0;
int j = numbers.size()-1;
while(true){
if(numbers[i] + numbers[j] == target){
re.push_back(i+1);
re.push_back(j+1);
return re;
}
if(numbers[i] + numbers[j] > target)
j--;
else
i++;
}
}
};Excel Sheet Column Title
""" """
class Solution {
public:
string convertToTitle(int n) {
string re="";
while(n){
n -= 1;
char temp = n%26 + 'A';
re = temp + re;
n /= 26;
}
return re;
}
};Majority Element
"""sol列出了多种方法。我们复习一下hash法，不是最优的。 time n space n """
class Solution {
public:
int majorityElement(vector<int>& nums) {
unordered_map<int, int> map;
int max_count = 0;
int max_id = 0;
for(int i=0; i<nums.size(); i++){
if(map.find(nums[i]) != map.end())
map[nums[i]] ++;
else
map.insert({nums[i],1});
}
for(auto j: map)
if(j.second>max_count){
max_count = j.second;
max_id = j.first;
}
return max_id;
}
};Excel Sheet Column Number
""" """
class Solution {
public:
int titleToNumber(string s) {
int num = 0;
for(int i=0; i<s.size(); i++){
num *= 26;
num += (s[i]-'A'+1);
}
return num;
}
};Factorial Trailing Zeroes
""" """
class Solution {
public:
int trailingZeroes(int n) {
return n == 0 ? 0 : n/5 + trailingZeroes(n/5);
}
};