leetcode Question 65: Pascal's Triangle II

Pascal's Triangle II

Given an index k, return the k^th row of the Pascal's triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?

Analysis:
This can be solved in according to the formula to generate the kth element in nth row of Pascal's Triangle:

r(k) = r(k-1) * (n+1-k)/k,

where r(k) is the kth element of nth row. The formula just use the previous element to get the new one. The start point is 1.

Once get the formula, it is easy to generate the nth row.

But be careful !!!

If you have an int*int when the value of int*int  is out of the bound of int data type (while is signed: -2147483648 to 2147483647, unsigned: 0 to 4294967295 ), there will be an ERROR result!!!

And also NOTE that:
If you define   "int a;  double d = a*a;", it still meets wrong value! because the * is called the operator function: "int::operator *(const &int )".

So the better way is to do type casting before the manipulation.
double d = double(a)*double(a);


Code:

class Solution {
public:
    vector<int> getRow(int rowIndex) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<int> res;
        res.push_back(1);
        int n = (rowIndex)/2;
        for (int i=1;i<=n;i++){
            double r = double(res[i-1]) * (double(rowIndex)+1-double(i))/double(i);
            res.push_back(r);
        }
        
        if (rowIndex%2==1){
            int sz = res.size();
            for (int i=sz-1;i>=0;i--){
                res.push_back(res[i]);
            }
        }else{
            int sz = res.size();
            for (int i=sz-2;i>=0;i--){
                res.push_back(res[i]);
            }
        }
        return res;
        
    }
};

leetcode Question 64: Pascal's Triangle I

Pascal's Triangle I:

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,
Return

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

Analysis:
In each row, the first and last element are 1. And the other element is the sum of the two elements in the previous row. e.g.

   1 3 3 1   Previous row
1 1+3 3+3 3+1 1   Next row

   1 4 6 4 1 Previous row
1 1+4 4+6 6+4 4+1 1 Next row

So the idea is simple:
(1) Add 1 to current row.
(2) Get the previous line. Sum every two elements and add to current row.
(3) Add 1 to current row.
(4) Go fill the next row


Code ( updated 2013.08 ):

class Solution {
public:
    vector<vector<int> > generate(int numRows) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        vector<vector<int> > res;
        if (numRows==0){return res;}
        vector<int> r;
        r.push_back(1);
        res.push_back(r);
        if (numRows==1){return res;}
        r.push_back(1);
        res.push_back(r);
        if (numRows==2){return res;}
        
        for (int i=2;i<numRows;i++){
            vector<int> c(i+1,1);
            for (int j=1;j<i;j++){
                c[j]= res[i-1][j]+res[i-1][j-1];
            }
            res.push_back(c);
        }
        return res;
    }
};

leetcode Question 63: Partition List

Partition List:

Given a linked list and a value x, partition it such that all nodes less than x come before nodes greater than or equal tox.

You should preserve the original relative order of the nodes in each of the two partitions.

For example,
Given 1->4->3->2->5->2 and x = 3,
return 1->2->2->4->3->5.

Analysis:
Simple idea but be careful with the operation of pointers.
The idea is:   first get the last element and the length of the list (1 while loop)
                    Then scan the whole list, if current node value < x, then go to the next node.
                                                          if current node value >=x, then move this node to the end of the list.
                    until  meet the length of the original list.


Code:

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *partition(ListNode *head, int x) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        ListNode *p= new ListNode(0);
        p->next = head;
        head = p; // used to save the result head.
        ListNode *last=head; // used to get the last node
        
        if (head==NULL){return NULL;}
        if (head->next==NULL){return head->next;}
        
        int n=0; //length of the list
        while (last->next!=NULL){ last=last->next; n++; } //get the length and last node
        
        while (n>0){  // in case  of non-stop loop, count n.
            if (p->next->val < x){  // val<x keep the node
                p=p->next;
                n--;
            }else{                  // val>=x move to last
                last->next = new ListNode(p->next->val);    // add node to the last
                last = last->next;
                p->next = p->next->next;                    //delete current node
                n--;
            }
        }
        return head->next;  //the 1st node is elmininated 
    }
};

leetcode Question 71: Plus One

Plus One
Given a number represented as an array of digits, plus one to the number.
Analysis:
This problem is pretty easy.
Just consider two special cases:
(1) last digit is 9: need a carry
(2) All the digits are 9 just return 100000... number of 0s is the length of the vector.


Code:

class Solution {
public:
    vector<int> plusOne(vector<int> &digits) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        if (digits[digits.size()-1]!=9){
            digits[digits.size()-1]++;
            return digits;
        }else{
            digits[digits.size()-1]=0;
            int carry=1;
            
            for (int i=digits.size()-2;i>=0;i--){
                if (digits[i]!=9){
                    digits[i]++;
                    return digits;
                }else{
                    digits[i]=0;
                }
            }
            vector<int> res(digits.size()+1,0);
            res[0]=1;
            return res;
        }
    }
};

leetcode Question 85: Reverse Linked List II

Reverse Linked List II

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ? m ? n ? length of list.

Analysis:

In this problem, do not think it too hard, reverse the linked list here is just reverse the value of node.
So the idea is to scan the linked list once, if not meet the reverse sublist, keep going, if reverse done(here the position is the middle of the sublist which needed to be reversed), return, because the latter list do not need any change. While in the sublist, for each element, (1)find the node to be swapped, (2) swap the values.
In the code below, note that,
(1) the stop condition is the middle of the reversed sublist (m+(n-m)/2)
(2) for each element in the sublist, the swapping element is the next (n-m-(i-m)*2) element.
     e.g.
    1-2-3-4-5-6-7-8-9-10-null
        |                        |
      m=2                  n=9
   for 2, just get the next (n-m) element.


    1-9-3-4-5-6-7-8-2-10-null
            |                |
          i=3          idx=8

   next element 3, the swapping element is 8.

Code(updated 201309):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        ListNode* h=head;
        for (int i=0;i<n-m;i++){
            int k1=m+i;
            int k2=n-i;
            if (k1>=k2){return head;}
            ListNode* p = h;
            ListNode* q = h;
            while (k1-1>0){p=p->next;k1--;}
            while (k2-1>0){q=q->next;k2--;}
            int tmp=p->val;
            p->val=q->val;
            q->val=tmp;
        }
        return head;
    }
};

Code(old version):

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode *reverseBetween(ListNode *head, int m, int n) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        ListNode* p=head;
        int i=1;
        while (p!=NULL){
            if (i>(m+int((n-m)/2))) {return head;}
            if (i<m) {i++;p=p->next;}
            else{
                ListNode* q = p;
                for (int j=0;j<(n-m-(i-m)*2);j++){
                    q=q->next;
                }
                int tmp = p->val;
                p->val = q->val;
                q->val=tmp;
                i++;
                p=p->next;
            }
        }
        return head;
    }
};