问题描述:

Given a sorted array, remove the duplicates in place such that each element appear only once and return the new length.

Do not allocate extra space for another array, you must do this in place with constant memory.

For example, Given input array nums = [1,1,2],

Your function should return length = 2, with the first two elements of nums being 1 and 2 respectively. It doesn’t matter what you leave beyond the new length.

对一个有序数组去重, 并且要求不使用额外的存储空间.

首先解决的是去重的问题, 如果没有额外空间的限制, 首先想到的是创建一个新的数组, 然后遍历nums, 大于新数组末尾的数则把当前的数加入新数组. 这里数组末尾的数其实就是已经遍历过的最大值, 因此可以用一个变量来保存.

接下来是存储空间的问题, 由于nums中每个数在遍历时的作用只是与当前遍历过的最大值比较, 而已经遍历过的数是没有什么作用的, 所以可以使用已经遍历过的nums数所占的空间.

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int num = 0, totalLen = nums.size(), curMax = INT_MIN;
        for(int i = 0, j = 0; i < totalLen; i++){
            if(nums[i] > curMax){
                curMax = nums[i];
                num++;
                nums[j++] = nums[i];
            }
        }
        return num;
    }
};

这段代码的Runtime是36毫秒, 但是许多AC代码的Runtime都在32ms, 说明这个程序还有一定的优化空间.

首先循环体内部的操作已经非常简洁, 应该很难有所作为, 所以优化的目标应该在循环次数上. 先将nums中最大的数保存下来, 当遍历到与该值相等的时候, 把这个数处理完后就可以退出循环了. 所以最终代码:

class Solution {
public:
    int removeDuplicates(vector<int>& nums) {
        int num = 0, totalLen = nums.size(), curMax = INT_MIN;
        int maxItem = nums.empty() ? 0 : nums.back();
        for(int i = 0, j = 0; i < totalLen; i++){
            if(nums[i] > curMax){
                curMax = nums[i];
                num++;
                nums[j++] = nums[i];
            }
            if(nums[i] == maxItem){
                break;
            }
        }
        return num;
    }
};

题目描述:

Given a linked list, reverse the nodes of a linked list k at a time and return its modified list.

If the number of nodes is not a multiple of k then left-out nodes in the end should remain as it is.

You may not alter the values in the nodes, only nodes itself may be changed.

Only constant memory is allowed.

For example, Given this linked list: 1->2->3->4->5

For k = 2, you should return: 2->1->4->3->5

For k = 3, you should return: 3->2->1->4->5

以k个节点为一组进行顺序颠倒. 首先实现一个从某个节点开始, 把包括它的接下来的k个节点的顺序颠倒的函数, 再不断迭代这个函数直到链表末尾. 由于如果链表长度不是k的整数倍的话, 最后的m(m<k)个元素不进行处理, 所以先计算出链表的总长度len, 在每次迭代时计算已经处理过的节点数reversedLen, 当reversedLen + k > len时结束循环.

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
    ListNode* reverse(ListNode* prev, int k){
        if(!prev->next) return nullptr;
        ListNode *tail = prev->next, *pPrev = tail, *pCur = pPrev->next;
        for(int i = 1; pCur && i < k; i++){
            ListNode *pNext = pCur->next;
            pCur->next = pPrev;
            pPrev = pCur;
            pCur = pNext;
        }
        prev->next = pPrev;
        tail->next = pCur;
        return tail;
    }
    
    int countListLength(ListNode *list){
        int len = 0;
        ListNode *p = list;
        while(p){
            len++;
            p = p->next;
        }
        return len;
    }

    ListNode* reverseKGroup(ListNode* head, int k) {
        if(head == nullptr || k <= 1)
            return head;
        ListNode *trueHead = new ListNode(0), *p = trueHead;
        trueHead->next = head;
        int listLen = countListLength(head);
        int reversedLen = 0;
        
        while(true){
            if(reversedLen + k > listLen) break;
            p = reverse(p, k);
            reversedLen += k;
        }
        return trueHead->next;
    }
};

题目描述:

Given a linked list, swap every two adjacent nodes and return its head.

For example, Given 1->2->3->4, you should return the list as 2->1->4->3.

Your algorithm should use only constant space. You may not modify the values in the list, only nodes itself can be changed.

交换链表相邻节点。

C++:

class Solution {
public:
    ListNode *swapPairs(ListNode *head) {
        if(head == NULL || head->next == NULL) return head;
        ListNode *first = head, *second = head->next, *prev = NULL;
        first->next = second->next;
        second->next = first;
        head = second;
        prev = first;
        first = first->next;
        while(first){
            second = first->next;
            if(second == NULL)break;
            first->next = second->next;
            second->next = first;
            prev->next = second;
            prev = first;
            first = first->next;
        }
        return head;
    }
};

时间4ms。

题目描述:

Merge k sorted linked lists and return it as one sorted list. Analyze and describe its complexity.

合并k个有序链表. 首先创建一个小顶堆(比较的是每个链表节点的值), 其中的元素是k个链表的头结点, 每次取出堆顶的节点, 加入到合并后的链表中, 然后将这个节点的后一个节点放入堆中, 如果是链表尾则不放入. 重复这个步骤直到堆为空.

由于建n个元素的堆的时间复杂度为O(n)(证明见: http://blog.csdn.net/anonymalias/article/details/8807895). 假设共有n个节点, 总的时间复杂度约为O(k)+O(nlogk)(我并不太会算复杂度, 这个也只是估计的…).

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
    ListNode* mergeKLists(vector<ListNode*>& lists) {
        auto comp = [=](ListNode *a, ListNode *b){
            return a->val <= b->val;
        };
        ListNode *head = new ListNode(0), *p = head;
        if(lists.empty()) return head->next;
        set<ListNode*, decltype(comp)> s(comp);
        for(int i = 0; i < lists.size(); i++){
            if(lists[i] != nullptr){
                s.insert(lists[i]);
            }
        }
        while(!s.empty()){
            ListNode *node = *(s.begin());
            s.erase(s.begin());
            if(node->next != nullptr) s.insert(node->next);
            p->next = node;
            p = p->next;
        }
        return head->next;
    }
};

题目描述:

Given n pairs of parentheses, write a function to generate all combinations of well-formed parentheses.

For example, given n = 3, a solution set is:

[
  "((()))",
  "(()())",
  "(())()",
  "()(())",
  "()()()"
]

题目要求输出n个括号的所有组合. 每个合法的字符串的长度都是2*n, 其中每个位置的字符有两种可能: 左括号和右括号. 因此循环2*n次, 每次对于结果集ret中的每个字符串末尾添加括号, 判断两种情况哪一种合法.或者两种都合法.

左括号合法的情况

字符串中出现的左括号总数没有超过n, 则在尾部添加左括号总是合法的.

右括号合法的情况

字符串中含有未配对的左括号. 注意: 如果左括号总数没有超过n, 那么该字符串添加左右括号都是合法的, 因此要在结果集末尾增加一条; 如果已经有了n个左括号, 那么只能添加右括号.

class Solution {
public:
    vector<string> generateParenthesis(int n) {
        vector<string> ret = {"("};
        vector<int> leftNum = {1};   //ret中每个字符串中左括号的数量
        vector<int> singleLeftNum = {1};  //ret中每个字符串中未配对的左括号数量
        int strLen = n * 2;
        for(int i = 1; i < strLen; i++){
            int len = ret.size();
            for(int j = 0; j < len; j++){
                if(singleLeftNum[j] > 0){
                    if(leftNum[j] == n){
                        ret[j].push_back(')');
                        singleLeftNum[j]--;
                    }
                    else{
                        ret.push_back(ret[j] + ")");
                        leftNum.push_back(leftNum[j]);
                        singleLeftNum.push_back(singleLeftNum[j] - 1);
                    }
                }
                if(leftNum[j] < n){
                    ret[j].push_back('(');
                    leftNum[j]++;
                    singleLeftNum[j]++;
                }
            }
        }
        return ret;
    }
};

Deque简介

deque(读作deck)是双向队列的缩写(double-ended queue), 它是可以在两端动态变更大小的顺序容器.

不同的库可能会以不同的方法来实现deque, 但不管怎样, 它们都允许通过随机访问迭代器访问特定元素, 并且根据需要自动管理存储空间.

deque提供与vector相似的功能, 但是允许首尾两端高效的插入删除元素而不是像vector一样只能在尾部. 但是, deque不像vector一样保证使用顺序存储空间来保存元素, 因此如果通过指针和偏移量访问deque中的另一个元素会引发未定义行为.

Vector与deque提供相似的接口并且可以用于相似的用途, 但它们的内部实现确完全不同. Vector使用一个在元素数量增长时偶尔需要重新分配空间的数组, 而deque中的元素可以分散存储在内存中的不同位置, deque容器内部通过保存必要的信息来提供在常数时间内访问任意元素的功能, 并且通过迭代器提供一个统一的顺序访问接口. 因此, deque的内部实现比vector要复杂, 但是这使得它在特定情况下可以更高效的增长, 比如在序列非常长时, 重新分配空间会非常耗时.

对于需要在首尾以外的位置频繁插入删除的操作来说, deque比list和forward list表现要差.

容器属性

顺序

顺序容器中的元素都遵循严格的线性序列, 每个元素都可以通过他们在序列中的位置来访问.

动态数组

通常实现类似于动态数组, 提供随机访问序列中任意元素的能力并且提供在序列首尾高效插入/删除的操作.

Allocator-aware[?]

容器使用一个allocator对象来动态管理存储空间.

部分常用函数

一些常用的函数比如size, back, push_back, pop_back, push_front, pop_front等我就不再赘述了

构造函数

默认构造函数 Default constructor

explicit deque (const allocator_type& alloc = allocator_type());

创建一个空容器.

填充构造函数 Fill constructor

explicit deque (size_type n);
         deque (size_type n, const value_type& val,
                const allocator_type& alloc = allocator_type());

创建一个有n个元素的容器, 如果提供了val, 则n个元素的值都为val.

范围构造函数 Range constructor

template <class InputIterator>
  deque (InputIterator first, InputIterator last,
         const allocator_type& alloc = allocator_type());

构建一个数量与[first, last)相同的容器, 以与之相同的顺序初始化每个元素.

拷贝构造函数

deque (const deque& x);
deque (const deque& x, const allocator_type& alloc);

创建一个以x中的元素的拷贝组成的容器.

移动构造函数 Move constructor

deque (deque&& x);
deque (deque&& x, const allocator_type& alloc);

创建一个由从x中取得的元素组成的容器, 下面这句话我没有太看懂:

If alloc is specified and is different from x’s allocator, the elements are moved. Otherwise, no elements are constructed (their ownership is directly transferred).

x会保持一个未定义但合法的状态.

初始化列表构造函数

deque (initializer_list<value_type> il,
       const allocator_type& alloc = allocator_type());

以il中元素的顺序用每个元素的拷贝创建一个容器.

例子

// code url: http://www.cplusplus.com/reference/deque/deque/deque/
// constructing deques
#include <iostream>
#include <deque>

int main ()
{
    unsigned int i;

    // constructors used in the same order as described above:
    std::deque<int> first;                                // empty deque of ints
    std::deque<int> second (4,100);                       // four ints with value 100
    std::deque<int> third (second.begin(),second.end());  // iterating through second
    std::deque<int> fourth (third);                       // a copy of third

    // the iterator constructor can be used to copy arrays:
    int myints[] = {16,2,77,29};
    std::deque<int> fifth (myints, myints + sizeof(myints) / sizeof(int) );

    std::cout << "The contents of fifth are:";
    for (std::deque<int>::iterator it = fifth.begin(); it!=fifth.end(); ++it)
        std::cout << ' ' << *it;

    std::cout << '\n';

    return 0;
}

输出

The contents of fifth are: 16 2 77 29

deque::assign

range (1)

template <class InputIterator>
void assign (InputIterator first, InputIterator last);

fill (2)

void assign (size_type n, const value_type& val);

initializer list (3)

void assign (initializer_list<value_type> il);

重新配置deque中的内容, 并相应地调整大小. 使用方法类似于相应的构造函数.

deque::clear

void clear() noexcept;

清空容器中的所有元素.

时间复杂度: 与size有关的线性(因为要执行元素的析构函数).

deque::max_size

size_type max_size() const noexcept;

返回deque容器所能保存的最大元素数量. 但是deque不保证一定能达到这个数量.

问题描述:

Merge two sorted linked lists and return it as a new list. The new list should be made by splicing together the nodes of the first two lists.

简单的链表操作。

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if(l1 == NULL && l2 == NULL)return NULL;
        if(l1 == NULL)return l2;
        if(l2 == NULL)return l1;
        ListNode *head = new ListNode(0), *l1Node = l1, *l2Node = l2, *p = head;
        while(l1Node || l2Node){
            if(!l1Node){
                p->next = l2Node;
                break;
            }
            else if(!l2Node){
                p->next = l1Node;
                break;
            }
            else{
                if(l1Node->val < l2Node->val){
                    p->next = l1Node;
                    l1Node = l1Node->next;
                }
                else{
                    p->next = l2Node;
                    l2Node = l2Node->next;
                }
            }
            p = p->next;
        }
        return head->next;
    }
};

题目描述:

Given a string containing just the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’, determine if the input string is valid.

The brackets must close in the correct order, “()” and “()[]{}” are all valid but “(]” and “([)]” are not.

要求判断输入字符串中的括号是否正确匹配, 因为括号要正确闭合, 因此使用计数器来记录左右括号数量是不行的. 我用栈来保存所有的左括号, 每遇到一个右括号就与栈顶端的左括号匹配, 不匹配则返回false, 匹配则将栈顶括号出栈. 循环过程中如果出现栈为空, 或者循环结束后栈不为空则返回false. 其他情况返回true.

class Solution {
public:
    bool isValid(string s) {
        vector<char> bracket;
        for(auto i : s){
            if(i == '(' || i == '[' | i == '{')
                bracket.push_back(i);
            else{
                if(bracket.empty())
                    return false;
                else if( (i == ')' && bracket.back() == '(') || (i == ']' && bracket.back() == '[') || (i == '}' && bracket.back() == '{'))
                    bracket.pop_back();
                else
                    return false;
            }
        }
        
        return bracket.empty() ? true : false;
    }
};

题目描述:

Given a linked list, remove the n^th node from the end of list and return its head.

For example,

Given linked list: 1->2->3->4->5, and n = 2.

After removing the second node from the end, the linked list becomes 1->2->3->5.

Note:

Given n will always be valid.

Try to do this in one pass.

要求删除链表从后往前数第n个节点, 并且只遍历一次. 所以我采用一个vector来保存每个节点的指针, 遍历一次后从vector中找到倒数第n个节点并删除之.

/**
* Definition for singly-linked list.
* struct ListNode {
*     int val;
*     ListNode *next;
*     ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
    ListNode* removeNthFromEnd(ListNode* head, int n) {
        vector<ListNode*> listPointer;
        ListNode* p = head;
        while(p != nullptr){
            listPointer.push_back(p);
            p = p->next;
        }
        
        int len = listPointer.size(), toDeleteIndex = len - n;
        ListNode* toDelete = listPointer[toDeleteIndex];
        if(toDeleteIndex == 0){
            return head->next;
        }
        else{
            ListNode* prev = listPointer[toDeleteIndex - 1];
            prev->next = toDelete->next;
            return head;
        }
    }
};

题目描述:

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.

Note: The solution set must not contain duplicate quadruplets.

For example, given array S = [1, 0, -1, 0, -2, 2], and target = 0.

A solution set is:
[
  [-1,  0, 0, 1],
  [-2, -1, 1, 2],
  [-2,  0, 0, 2]
]

这道题可以继续使用2Sum, 3Sum题目的方法, 在3Sum外面再增加一次处理. 还有另外一种使用HashMap的方法, 但是我现在还没有完全实现它, 主要问题在于最后的去重. 更多的信息可以参考这里:http://www.sigmainfy.com/blog/summary-of-ksum-problems.html.

我的代码, 效率并不高:

class Solution {
    vector<vector<int>> fourSumRet;
public:
    vector<vector<int>> fourSum(vector<int>& nums, int target) {
        sort(nums.begin(), nums.end());
        for(int i = 0; i < nums.size(); i++){
            if(i >= 1 && nums[i] == nums[i - 1]) continue;
            if(target > 0 && nums[i] > target) break;
            threeSum(nums, target - nums[i], i + 1, nums.size());
        }
        return fourSumRet;
    }
    
    void threeSum(vector<int>& nums, int target, int left, int right) {
        for(int i = left; i < right; i++){
            if(i >= left + 1 && nums[i] == nums[i - 1]) continue;
            twoSum(nums, target - nums[i], i + 1, right, left - 1);
        }
    }
    
    void twoSum(vector<int>& nums, int target, int left, int right, int fourSumIndex) {
        int l = left, r = right - 1;
        while(l < r){
            int sum = nums[l] + nums[r];
            if(sum == target){
                vector<int> t = {nums[fourSumIndex], nums[left - 1], nums[l], nums[r]};
                fourSumRet.push_back(t);
                do{r--;}while(nums[r] == nums[r + 1]);
                do{l++;}while(nums[l] == nums[l - 1]);
            }
            else if(sum > target){
                r--;
            }
            else{
                l++;
            }
        }
    }
};