liuchuo – 第251页 – 我不管，反正我最萌～

LeetCode 238. Product of Array Except Self

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].

Solve it without division and in O(n).

For example, given [1,2,3,4], return [24,12,8,6].

Follow up:
Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity analysis.)

class Solution {
public:
    vector<int> productExceptSelf(vector<int>& nums) {
        vector<int> v(nums.size());
        int right = 1;
        v[0] = 1;
        //左边所有数字的乘积
        for(int i = 1; i < nums.size(); i++) {
           v[i] = nums[i - 1] * v[i - 1]; 
        }
        for(int i = nums.size() - 2; i >= 0; i--) {
            right = right * nums[i + 1];
            v[i] = v[i] * right;
        }
        return v;
    }
};

class Solution {

public:

vector<int> productExceptSelf(vector<int>& nums) {

vector<int> v(nums.size());

int right = 1;

v[0] = 1;

//左边所有数字的乘积

for(int i = 1; i < nums.size(); i++) {

v[i] = nums[i - 1] * v[i - 1];

}

for(int i = nums.size() - 2; i >= 0; i--) {

right = right * nums[i + 1];

v[i] = v[i] * right;

}

return v;

}

};

LeetCode 121. Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int minvalue = 99999999;
        int ans = 0;
        for(int i = 0; i < prices.size(); i++) {
            if(minvalue > prices[i]) {
                minvalue = prices[i];
            }
            prices[i] = prices[i] - minvalue;
            if(ans < prices[i]) {
                ans = prices[i];
            }
        }
        return ans;
    }
};

class Solution {

public:

int maxProfit(vector<int>& prices) {

int minvalue = 99999999;

int ans = 0;

for(int i = 0; i < prices.size(); i++) {

if(minvalue > prices[i]) {

minvalue = prices[i];

}

prices[i] = prices[i] - minvalue;

if(ans < prices[i]) {

ans = prices[i];

}

return ans;

}

};

LeetCode 122. Best Time to Buy and Sell Stock II

Say you have an array for which the ith element is the price of a given stock on day i.

Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times). However, you may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).

分析：贪心算法，在每一小段上升序列中最大差值累加得到结果。就是说在股票价格处于上升期的时候，在最低点买入，在最高点卖出。而且可知，每一小段的最大差值就是这段序列的最后一个点的价格减去这段序列第一个点的价格，与每一次从第一个点与第二点的差值一直累加所得结果相同：ans += prices[i] – prices[i – 1];

class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int ans = 0;
        for(int i = 1; i < prices.size(); i++) {
            if(prices[i] > prices[i - 1])
                ans += prices[i] - prices[i - 1];
        }
        return ans;
    }
};

class Solution {

public:

int maxProfit(vector<int>& prices) {

int ans = 0;

for(int i = 1; i < prices.size(); i++) {

if(prices[i] > prices[i - 1])

ans += prices[i] - prices[i - 1];

}

return ans;

}

};

LeetCode 1. Two Sum

Given an array of integers, return indices of the two numbers such that they add up to a specific target.

You may assume that each input would have exactly one solution.

Example:
Given nums = [2, 7, 11, 15], target = 9,

Because nums[0] + nums[1] = 2 + 7 = 9,
return [0, 1].
UPDATE (2016/2/13):
The return format had been changed to zero-based indices. Please read the above updated description carefully.

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        vector<int> v(2);
        for(int i = 0; i < nums.size(); i++) {
            for(int j = i + 1; j < nums.size(); j++) {
                if(nums[i] + nums[j] == target) {
                    v[0] = i;
                    v[1] = j;
                }
            }
        }
        return v;
    }
};

class Solution {

public:

vector<int> twoSum(vector<int>& nums, int target) {

vector<int> v(2);

for(int i = 0; i < nums.size(); i++) {

for(int j = i + 1; j < nums.size(); j++) {

if(nums[i] + nums[j] == target) {

v[0] = i;

v[1] = j;

}

return v;

}

};

LeetCode 2. Add Two Numbers

You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        ListNode *h = new ListNode(0);
        ListNode *p = h;
        int temp = 0;
        while(l1 != NULL && l2 != NULL) {
            p->next = new ListNode((temp + l1->val + l2->val) % 10);
            temp = (temp + l1->val + l2->val) / 10;
            p = p->next;
            l1 = l1->next;
            l2 = l2->next;
        }
        while(l1 != NULL) {
            p->next = new ListNode((temp + l1->val) % 10);
            temp = (temp + l1->val) / 10;
            p = p->next;
            l1 = l1->next;
        }
        while(l2 != NULL) {
            p->next = new ListNode((temp + l2->val) % 10);
            temp = (temp + l2->val) / 10;
            p = p->next;
            l2 = l2->next;
        }
        if(temp) {
            p->next = new ListNode(1);
        }
        return h->next;
    }
};

/**

* Definition for singly-linked list.

* struct ListNode {

* int val;

* ListNode *next;

* ListNode(int x) : val(x), next(NULL) {}

* };

class Solution {

public:

ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {

ListNode *h = new ListNode(0);

ListNode *p = h;

int temp = 0;

while(l1 != NULL && l2 != NULL) {

p->next = new ListNode((temp + l1->val + l2->val) % 10);

temp = (temp + l1->val + l2->val) / 10;

p = p->next;

l1 = l1->next;

l2 = l2->next;

}

while(l1 != NULL) {

p->next = new ListNode((temp + l1->val) % 10);

temp = (temp + l1->val) / 10;

p = p->next;

l1 = l1->next;

}

while(l2 != NULL) {

p->next = new ListNode((temp + l2->val) % 10);

temp = (temp + l2->val) / 10;

p = p->next;

l2 = l2->next;

}

if(temp) {

p->next = new ListNode(1);

}

return h->next;

}

};

LeetCode 142. Linked List Cycle II

Given a linked list, return the node where the cycle begins. If there is no cycle, return null.

Note: Do not modify the linked list.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *detectCycle(ListNode *head) {
        if(head == NULL) {
            return NULL;
        }
        set<ListNode *> s;
        ListNode *p = head;
        int cnt = 0;
        while(p->next != NULL) {
            s.insert(p);
            if(cnt == s.size()) {
                return p;
            }
            cnt = s.size();
            p = p->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 *detectCycle(ListNode *head) {

if(head == NULL) {

return NULL;

}

set<ListNode *> s;

ListNode *p = head;

int cnt = 0;

while(p->next != NULL) {

s.insert(p);

if(cnt == s.size()) {

return p;

}

cnt = s.size();

p = p->next;

}

return NULL;

}

};