[leetcode]148. Sort List

Problem
Sort a linked list in O(n log n) time using constant space complexity.

Solution

 MergeSort.

Code

class Solution {
public:
    ListNode* sortList(ListNode* head) {
        if (head == NULL || head->next == NULL) {
            return head;
        }
        ListNode *slow = head;
        ListNode *fast = head;
        while (fast->next && fast->next->next) {
            slow = slow->next;
            fast = fast->next->next;
        }
        fast = slow->next;
        slow->next = NULL;
        ListNode *h1 = sortList(head);
        ListNode *h2 = sortList(fast);
        return Merge(h1,h2);
    }
    
    ListNode* Merge(ListNode* h1,ListNode* h2) {
        ListNode *head = new ListNode(0);
        ListNode *tail = head;
        while (h1 || h2) {
            if (h1 && h2) {
                if (h1->val < h2->val) {
                    tail->next = h1;
                    h1 = h1->next;
                    tail = tail->next;
                }
                else {
                    tail->next = h2;
                    h2 = h2->next;
                    tail = tail->next;
                }
            }
            else {
                if (h1) {
                    tail->next = h1;
                    h1 = h1->next;
                    tail = tail->next;
                }
                if (h2) {
                    tail->next = h2;
                    h2 = h2->next;
                    tail = tail->next;
                }
            }
        }
        return head->next;
    }
};

Problem

   

Huffman Coding

Code

#include <stdio.h>
#include <iostream>
#include <queue>
#include <string>
using namespace std;

const int N = 110;
int n;
int freq[N];
struct Node {
 int val;
 int idx;
 Node *left,*right;
 Node() {
  left = right = NULL;
  idx = -1;
 }
 Node(int v) {
  val = v;
  left = right = NULL;
  idx = -1;
 }

};
struct cmp {
 bool operator() (Node *a,Node *b) {
  return a->val > b->val;
 }
};


priority_queue<Node*,vector<Node*>,cmp> que;

void dfs(Node *root,string pre) {
 if (root == NULL) return;
 if (root->left == NULL && root->right == NULL) {
  cout << root->idx << " " << pre << endl;
  return ;
 }
 if (root->left != NULL) {
  string nxt = pre + char('0');
  dfs(root->left,nxt);
 }
 if (root->right != NULL) {
  string nxt = pre + char('1');
  dfs(root->right,nxt);
 }
}
int main() {
 scanf("%d",&n);
 for (int i = 0;i < n;i ++) {
  scanf("%d",&freq[i]);
 }
 for (int i = 0;i < n;i ++) {
  Node *tmp = new Node(freq[i]);
  tmp->idx = i;
  que.push(tmp);
 }

 while (que.size() >= 2) {
  Node *left = que.top();
  que.pop();
  Node *right = que.top();
  que.pop();
  Node *root = new Node(left->val + right->val);
  root->left = left;
  root->right = right;
  que.push(root);
 }
 Node *root = que.top();
 que.pop();
 dfs(root,"");

 return 0;
}

Weighted Job Scheduling

Problem

Given N jobs where every job is represented by following three elements of it.

Start Time
Finish Time
Profit or Value Associated
Find the maximum profit subset of jobs such that no two jobs in the subset overlap.

Code

#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;

const int N = 110;
int n;
struct Job {
    int start;
    int end;
    int profit;
}job[N];
bool cmp(const Job & a,const Job & b) {
    return a.end < b.end;
}
int dp[N];

int search(int end,int pos) {
    if (job[0].end > end) {
        return -1;
    }
    int l = 0;
    int r = pos + 1;
    while (l < r) {
        int m = (l + r) / 2;
        if (job[m].end <= end) {
            l = m + 1;
        }
        else {
            r = m;
        }
    }
    return l - 1;
}

int main() {
 scanf("%d",&n);
 for (int i = 0;i < n;i ++) {
     scanf("%d%d%d",&job[i].start,&job[i].end,&job[i].profit);
 }
 sort(job,job + n,cmp);
 dp[0] = job[0].profit;
 for (int i = 1;i < n;i ++) {
     dp[i] = dp[i - 1];
     int pos = search(job[i].start,i - 1);
     if (pos != -1) {
         dp[i] = max(dp[i],dp[pos] + job[i].profit);
     }
 }
 cout << dp[n - 1] << endl;
 return 0;
}

How to print maximum number of A’s using given four keys

Problem

Key 1:  Prints 'A' on screen
Key 2: (Ctrl-A): Select screen
Key 3: (Ctrl-C): Copy selection to buffer
Key 4: (Ctrl-V): Print buffer on screen appending it
after what has already been printed. 

Solution
   a) For N < 7, the output is N itself. b) Ctrl V can be used multiple times to print current buffer (See last two examples above). The idea is to compute the optimal string length for N keystrokes by using a simple insight. The sequence of N keystrokes which produces an optimal string length will end with a suffix of Ctrl-A, a Ctrl-C, followed by only Ctrl-V's (For N > 6). //from geeks.

Code

#include <stdio.h>
#include <iostream>
using namespace std;

int T;
int n;
const int N = 85;
typedef long long ll;
ll dp[N];
int main() {
 for (int i = 1;i <= 6;i ++) {
     dp[i] = i;
 }
 for (int i = 7;i <= 75;i ++) {
     for (int j = 1;j <= i - 3;j ++) {
         dp[i] = max(dp[i],dp[j] * (1 + i - j - 2));
     }
 }
 scanf("%d",&T);
 while (T --) {
     scanf("%d",&n);
     cout << dp[n] << endl;
 }
 return 0;
}

Maximum profit by buying and selling a share at most twice

Problem

   In a daily share trading, a buyer buys shares in the morning and sells it on same day. If the trader is allowed to make at most 2 transactions in a day, where as second transaction can only start after first one is complete (Sell->buy->sell->buy). Given stock prices throughout day, find out maximum profit that a share trader could have made.

Code

#include <stdio.h>
#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;

const int N = 110;
int n;
int a[N];
int dp[N];
int main() {
    scanf("%d",&n);
    for (int i = 0;i < n;i ++) {
        scanf("%d",&a[i]);
    }
    memset(dp,0,sizeof(dp));
    int max_val = a[n - 1];
    for (int i = n - 2;i >= 0;i --) {
        dp[i] = max(dp[i + 1],max_val - a[i]);
        max_val = max(max_val,a[i]);
    }
    
    int min_val = a[0];
    for (int i = 1;i < n;i ++) {
        dp[i] = max(dp[i - 1],a[i] - min_val + dp[i]);
        min_val = min(min_val,a[i]);
    }
    cout << dp[n - 1] << endl;
}

Compute sum of digits in all numbers from 1 to n

Problem

   Given a number x, find sum of digits in all numbers from 1 to n.

Solution
     take 389 for example;
     count[1,299) + [300,389)'s 3 + [1,89)
Code

#include <stdio.h>
#include <iostream>
#include <cmath>
using namespace std;


int f(int n) {
    if (n < 10) {
        return n * (n + 1) / 2;
    }
    
    int d = log10(n);
    
    int a[15];
    a[1] = 45;
    for (int i = 2;i <= d;i ++) {
        a[i] = a[i - 1] * 10 + 45 * pow(10,i - 1);
    }
    int p = ceil(pow(10,d));
    
    int msd = n / p;
    
    int p1 = msd * a[d] + (msd * (msd - 1)) / 2 * p;
    //int p1 = f(msd * p - 1);
    int p2 = msd * (n % p + 1) + f(n % p);
    return p1 + p2;
}

int main() {
 //code
 cout << f(389) << endl;
 return 0;
}

Collect maximum points in a grid using two traversals

Problem

   Given a matrix where every cell represents points. How to collect maximum points using two traversals under following conditions?
1) The first traversal starts from top left corner, i.e., (0, 0) and should reach left bottom corner, i.e., (R-1, 0). The second traversal starts from top right corner, i.e., (0, C-1) and should reach bottom right corner, i.e., (R-1, C-1)/

2) From a point (i, j), we can move to (i+1, j+1) or (i+1, j-1) or (i+1, j)

3) A traversal gets all points of a particular cell through which it passes. If one traversal has already collected points of a cell, then the other traversal gets no points if goes through that cell again.

Solution
     check bound at first is much easier.
Code

#include <stdio.h>
#include <iostream>
#include <cstring>
using namespace std;
const int R = 55;
const int C = 55;
int dp[R][C][C];
int a[R][C] = {{3, 6, 8, 2},
         {5, 2, 4, 3},
         {1, 1, 20, 10},
         {1, 1, 20, 10},
         {1, 1, 20, 10},
         };
int n,m;

int dfs(int row,int c1,int c2) {
    if (c1 < 0 || c1 >= m || c2 < 0 || c2 >= m) return -0x3f3f3f3f;
    if (row == n - 1 && c1 == 0 && c2 == m - 1) {
        return a[row][c1] + a[row][c2];
    }
    if (row == n - 1) return -0x3f3f3f3f;
    if (dp[row][c1][c2] != -1) return dp[row][c1][c2];
    int add = 0;
    if (c1 == c2) {
        add = a[row][c1];
    }
    else {
        add = a[row][c1] + a[row][c2]; 
    }
    
    int ans = -0x3f3f3f3f;
    ans = max(ans,add + dfs(row + 1,c1 - 1,c2 - 1));
    ans = max(ans,add + dfs(row + 1,c1 - 1,c2));
    ans = max(ans,add + dfs(row + 1,c1 - 1,c2 + 1));
    ans = max(ans,add + dfs(row + 1,c1,c2 - 1));
    ans = max(ans,add + dfs(row + 1,c1,c2));
    ans = max(ans,add + dfs(row + 1,c1,c2 + 1));
    ans = max(ans,add + dfs(row + 1,c1 + 1,c2 - 1));
    ans = max(ans,add + dfs(row + 1,c1 + 1,c2));
    ans = max(ans,add + dfs(row + 1,c1 + 1,c2 + 1));
    return dp[row][c1][c2] = ans;
}

int calc() {
    memset(dp,-1,sizeof(dp));
    return dfs(0,0,m - 1);
}

int main() {
    n = 5;
    m = 4;
    cout << calc() << endl;
 return 0;
}

Minimum Points To Reach Destination dp

Problem

   Given a grid with each cell consisting of positive, negative or no points i.e, zero points. We can move across a cell only if we have positive points ( > 0 ). Whenever we pass through a cell, points in that cell are added to our overall points. 

Solution
     use bottom-up is much easier than up-bottom;
     and pay attention to that the beginning should has at least 1 point.
Code

#include <stdio.h>
#include <iostream>
#include <cstring>
using namespace std;


const int N = 15;
int T;
int n,m;
int a[N][N];
int dp[N][N];
int main() {
    scanf("%d",&T);
    while (T --) {
        scanf("%d%d",&n,&m);
        for (int i = 1;i <= n;i ++) {
            for (int j = 1;j <= m;j ++) {
                scanf("%d",&a[i][j]);
            }
        }
        dp[n][m] = a[n][m] > 0 ? 1 : -a[n][m] + 1;
        for (int i = n;i >= 1;i --) {
            for (int j = m;j >= 1;j --) {
                if (i == n && j == m) continue;
                int mins = 0x3f3f3f3f;
                if (i + 1 <= n) {
                    mins = min(mins,dp[i + 1][j]);
                }
                if (j + 1 <= m) {
                    mins = min(mins,dp[i][j + 1]);
                }
                dp[i][j] = max(mins - a[i][j],1);
            }
        }
        cout << dp[1][1] << endl;
    }
}

Mobile Numeric Keypad Problem

Problem
   Given the mobile numeric keypad. You can only press buttons that are up, left, right or down to the current button. You are not allowed to press bottom row corner buttons (i.e. * and # ).
Given a number N, find out the number of possible numbers of given length.
Solution
   dynamic programming

Code

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <string>
using namespace std;

char board[4][3] = {
  {'1','2','3'},
  {'4','5','6'},
  {'7','8','9'},
  {'*','0','#'}
};

const int N = 110;
int dp[N][12];
int dir[5][2] = {0,0,1,0,-1,0,0,1,0,-1};
int main() {
 memset(dp,0,sizeof(dp));
 for (int i = 0;i <= 9;i ++) {
     dp[0][i] = 0;
     dp[1][i] = 1;
 }
 
 for (int i = 2;i <= 100;i ++) {
     for (int j = 0;j < 4;j ++) {
         for (int k = 0;k < 3;k ++) {
             if (board[j][k] == '*' || board[j][k] == '#') continue;
             int num = board[j][k] - '0';
             for (int t = 0;t < 5;t ++) {
                 int dx = j + dir[t][0];
                 int dy = k + dir[t][1];
                 if (dx < 0 || dy < 0 || dx >= 4 || dy >= 3) continue;
                 if (board[dx][dy] == '*' || board[dx][dy] == '#') continue;
                 int nxtnum = board[dx][dy] - '0';
                 dp[i][num] += dp[i - 1][nxtnum]; 
             }
         }
     } 
 }
 
 int n;
 while (cin >> n) {
     int sum = 0;
     for (int i = 0;i <= 9;i ++) {
         sum += dp[n][i];
     }
     cout << sum << endl;
 }
    return 0;
}

[leetcode weekly contest]390. Elimination Game

Problem
   There is a list of sorted integers from 1 to n. Starting from left to right, remove the first number and every other number afterward until you reach the end of the list.

Repeat the previous step again, but this time from right to left, remove the right most number and every other number from the remaining numbers.

We keep repeating the steps again, alternating left to right and right to left, until a single number remains.

Find the last number that remains starting with a list of length n.

Solution
   recursive, assume you know the answer of f(i) i < n, and you try to calculate the answer of f(n);

Code

class Solution {
public:
    int f(int n,int dir) {
        if (n == 1) return 1;
        if (n % 2 == 0 && dir == -1) {
            int ans = f(n / 2,-dir);
            return ans + (ans - 1);
        }
        else if (n % 2 == 0 && dir == 1) {
            int ans = f(n / 2,-dir);
            int tmp = ans + ans;
            return tmp;
        }
        else if (n % 2 == 1 && dir == 1) {
            int ans = f(n / 2,-dir);
            return ans + ans;
        }
        else if (n % 2 == 1 && dir == -1) {
            int ans = f(n / 2,-dir);
            return ans + ans;
        }
        return 0;
    }
    int lastRemaining(int n) {
        return f(n,1);
    }
};

[leetcode weekly contest]391. Perfect Rectangle

Problem
   Given N axis-aligned rectangles where N > 0, determine if they all together form an exact cover of a rectangular region.

Each rectangle is represented as a bottom-left point and a top-right point. For example, a unit square is represented as [1,1,2,2]. (coordinate of bottom-left point is (1, 1) and top-right point is (2, 2)).

Code

const int MAXN = 110000;
int sum[MAXN * 4 + 110];
int cover[MAXN * 4 + 110];
int x[MAXN];
struct Seg {
    int l,r,h;
    int flag;
    Seg() {}
    Seg(int a,int b,int c,int d) {
        l = a;
        r = b;
        h = c;
        flag = d;
    }
    bool operator< (const Seg &b) const {
  if (h != b.h)
        return h < b.h;
  return flag < b.flag;
    }
}seg[MAXN];

class Solution {
public:
 
    void update(int L,int R,int val,int l,int r,int rt) {
        if (L <= l && r <= R) {
            cover[rt] += val;
            sum[rt] = x[r + 1] - x[l];
            return ;
        }
        int m = (l + r) >> 1;
        if (cover[rt] > 0) {
            cover[rt << 1] = cover[rt << 1 | 1] = cover[rt];
            cover[rt] = 0;
            sum[rt << 1] = x[m + 1] - x[l];
            sum[rt << 1 | 1] = x[r + 1] - x[m + 1];
        }
  
  if (L <= m)  {
   update(L,R,val,l,m,rt << 1);
  }
  if (m < R) {
      update(L,R,val,m + 1,r,rt << 1 | 1);
  }
        sum[rt] = sum[rt << 1] + sum[rt << 1 | 1];
    }
    bool isRectangleCover(vector<vector<int>>& rectangles) {
        int m = 0;
        int n = rectangles.size();
        for (int i = 0;i < n;i ++) {
            x[m] = rectangles[i][0];
            seg[m] = Seg(rectangles[i][0],rectangles[i][2],
                         rectangles[i][1],1);
            m ++;
            x[m] = rectangles[i][2];
            seg[m] = Seg(rectangles[i][0],rectangles[i][2],
                         rectangles[i][3],-1);
   m ++;
        }
        sort(x,x + m);
        sort(seg,seg + m);
        int tot = 1;
        for (int i = 1;i < m;i ++) {
            if (x[i] != x[i - 1]) {
                x[tot ++ ] = x[i];
            }
        }
        memset(cover,0,sizeof(cover));
        memset(sum,0,sizeof(sum));
        int totarea = 0;
        for (int i = 0;i < m - 1;i ++) {
            int l = lower_bound(x,x + tot,seg[i].l) - x ;
            int r = lower_bound(x,x + tot,seg[i].r) - x - 1;
            if (l <= r) {
                update(l,r,seg[i].flag,0,tot - 1,1);
            }
            totarea += sum[1] * (seg[i + 1].h - seg[i].h);
        }


  int area3 = 0;
  vector<pair<int,int> > vec;
  for (int i = 0;i < n;i ++) {
   vec.push_back(make_pair(rectangles[i][0],rectangles[i][1]));
   vec.push_back(make_pair(rectangles[i][2],rectangles[i][3]));
   area3 += (rectangles[i][2] - rectangles[i][0]) * (rectangles[i][3] - rectangles[i][1]);
  }
  sort(vec.begin(),vec.end());
  int curarea = (vec[n * 2 - 1].first - vec[0].first) * (vec[n * 2 - 1].second - vec[0].second);
  return totarea == curarea && totarea == area3;
    }
};

[leetcode weekly contest]389. Find the Difference

Problem
   Given two strings s and t which consist of only lowercase letters.

String t is generated by random shuffling string s and then add one more letter at a random position.

Find the letter that was added in t.

Code

class Solution {
public:
    char findTheDifference(string s, string t) {
        vector<int> c1(27,0);
        vector<int> c2(27,0);
        for (int i = 0,sz = s.size();i < sz;i ++) {
            c1[s[i] - 'a'] ++;
        }
        for (int i = 0,sz = t.size();i < sz;i ++) {
            c2[t[i] - 'a'] ++;
        }
        for (int i = 0;i < 26;i ++) {
            if (c1[i] < c2[i]) {
                return char(i + 'a');
            }
        }
        return 'a';
    }
};

Shortest Common Supersequence

Problem
   Given two strings str1 and str2, find the shortest string that has both str1 and str2 as subsequences.

Solution
   str1len + str2len - lcs

Code

#include <stdio.h>
#include <iostream>
using namespace std;
const int N = 110;
int dp[N][N];
string a,b;
int main() {
    cin >> a >> b;
 int n = a.size();
 int m = b.size();
 dp[0][0] = 0;
 for (int i = 1;i <= n;i ++) {
     for (int j = 1;j <= m;j ++) {
         if (a[i] == b[j]) {
             dp[i][j] = dp[i - 1][j - 1] + 1;
         }
         else {
             dp[i][j] = max(dp[i][j - 1],dp[i - 1][j]);
         }
     }
 }
 cout << n + m - dp[n][m] << endl;
 return 0;
}

Consecutive 1's not allowed

Problem
   Count number of binary strings without consecutive 1’s.

Solution
 a[i] means string ends with 0 && not contains  11;
 b[i] means string ends with 1 && not contains 11;
 c[i] means string ends with 11 or contains 11;

Code

#include <stdio.h>
#include <iostream>
using namespace std;
const int N = 75;
long long a[N],b[N],c[N];
int T;
int n;
const int mod = 1e9 + 7;
int main() {
 a[1] = 1;
 b[1] = 1;
 c[1] = 0;
 for (int i = 2;i <= 70;i ++) {
     a[i] = (a[i - 1] + b[i - 1]) % mod;
     b[i] = a[i - 1] % mod;
     c[i] = (2 * c[i - 1] + b[i - 1]) % mod;
 }
 cin >> T;
 int n;
 while (T --) {
     cin >> n;
     cout << (a[n] + b[n]) % mod << endl;
 }
 return 0;
}

Optimal Binary Search Tree

Problem
   Given a sorted array keys[0.. n-1] of search keys and an array freq[0.. n-1] of frequency counts, where freq[i] is the number of searches to keys[i]. Construct a binary search tree of all keys such that the total cost of all the searches is as small as possible.

Solution
    dp[i][j] = min(dp[i][k - 1] + dp[k + 1][j]) + sum[i->j];

Code
   

#include <stdio.h>
#include <cstring>
#include <iostream>
using namespace std;

const int N = 260;
int n;
int a[N];
int sum[N];
int dp[N][N];
int main() {
    while (scanf("%d",&n) != EOF) {
        for (int i = 1;i <= n;i ++) {
            scanf("%d",&a[i]);
        }
        memset(dp,0x3f,sizeof(dp));
        sum[0] = 0;
        for (int i = 1;i <= n;i ++) {
            sum[i] = sum[i - 1] + a[i];
        }

        for (int i = 1;i <= n;i ++) {
            dp[i][i] = 0;
        }
        for (int len = 2;len <= n;len ++) {
            for (int i = 1;i + len - 1 <= n;i ++) {
                int j = i + len - 1;
                for (int k = i;k <= j;k ++) {
                    int tmp = 0;
                    tmp += sum[j] - sum[i - 1] - a[k];
                    tmp += k - 1 >= i ? dp[i][k - 1] : 0;
                    tmp += k + 1 <= j ? dp[k + 1][j] : 0;
                    dp[i][j] = min(dp[i][j],tmp);
                }
            }
        }
        cout << dp[1][n] << endl;

    }
    return 0;
}

Longest Palindromic Substring vs Longest Palindromic Subsequence

Longest Palindromic Substring
      f[i][j] means string[i...j] is palindromic.
        thus, f[i][j] = true if str[i] == str[j] && f[i + 1][j - 1] = true

Longest Palindromic Subsequence
        g[i][j] means the maximum length of palindromic subsequence in string[i...j]
        thus, g[i][j] = max(g[i + 1][j - 1] + 1 (if str[i] == str[j]),
                                     g[i + 1][j],
                                     g[i][j - 1]);

Maximum size square sub-matrix with all 1s

Solution
  dp[i][j] means the maximum size that ends with arr[i][j]
   dp[i][j] = min(dp[i][j-1], dp[i-1][j], dp[i-1][j-1]) + 1

[leetcode]132. Palindrome Partitioning II

Problem
Given a string s, partition s such that every substring of the partition is a palindrome.

Return the minimum cuts needed for a palindrome partitioning of s.

For example, given s = "aab",
Return 1 since the palindrome partitioning ["aa","b"] could be produced using 1 cut.

Solution

enumerate the length of the last part partition which is a palindrome.

If we pre-calculate the array f[i][j] which means whether string[i...j] is a palindrome. 

    f[i][j] = f[i + 1][j - 1] && str[i] == str[j] where len >= 2

    f[i][j] = str[i] == str[j] where len < 2

let dp[i] means the mininum cuts of string[0...i], thus 

    dp[i] = 0 if string[0...i] is a palindrome itself.

    dp[i] = min(dp[j] + 1) where 1 <= j <= i   and string[i...j] is a palindrome.

Code

class Solution {
public:
 int minCut(string s) {
        int n = s.size();
        vector > f(n + 1,vector(n + 1,false));
        for (int len = 1;len <= n;len ++) {
            for (int i = 0;i + len - 1 < n;i ++) {
                int j = i + len - 1;
                if (s[i] == s[j] && (len <= 2 || f[i + 1][j - 1])) {
                    f[i][j] = true;
                }
                else {
                    f[i][j] = false;
                }
            }
        }
        cout << f[0][1] << endl;
        vector dp(n + 1,0x3f3f3f3f);
        for (int i = 0;i < n;i ++) {
            if (f[0][i]) dp[i] = 0;
            else {
                for (int j = 1;j <= i;j ++) {
                    if (f[j][i]) {
                        dp[i] = min(dp[i],dp[j - 1] + 1);
                    }
                }
            }
        }
        return dp[n - 2];
 }
};

Longest Bitonic Subsequence

Problem
    Longest Bitonic Subsequence

Examples:

Input arr[] = {1, 11, 2, 10, 4, 5, 2, 1};
Output: 6 (A Longest Bitonic Subsequence of length 6 is 1, 2, 10, 4, 2, 1)

Input arr[] = {12, 11, 40, 5, 3, 1}
Output: 5 (A Longest Bitonic Subsequence of length 5 is 12, 11, 5, 3, 1)

Input arr[] = {80, 60, 30, 40, 20, 10}
Output: 5 (A Longest Bitonic Subsequence of length 5 is 80, 60, 30, 20, 10)

Solution
    max(lis[i] + rds[i] - 1) 1 <= i <= n

Tips
   lis[i] >= 1 && rds[i] >= 1 where i between 1 and n

Cutting a Rod

Problem

    give a rob of length n inches, try to split into several pieces. And try to max the total value.

length   | 1   2   3   4   5   6   7   8  
--------------------------------------------
price    | 1   5   8   9  10  17  17  20

Solution
    try to enumerate the length of the last piece.

Egg Dropping Puzzle

Problem

     Egg Dropping Puzzle

Solution

     maxmin

Code

#include <cstring>
#include <stdio.h>
#include <iostream>
using namespace std;

int T;
const int N = 55;
const int M = 1010;
int dp[N][M];
//dp[i][j] = min(max(dp[i - 1][x - 1],dp[i][j - x]));
int main() {
    scanf("%d",&T);
    memset(dp,0x3f,sizeof(dp));
    for (int i = 0;i <= 50;i ++) {
        dp[i][0] = 0;
        dp[i][1] = 1;
    }
    for (int j = 1;j <= 1000;j ++) {
        dp[1][j] = j;
    }

    for (int i = 2;i <= 50;i ++) {
        for (int j = 2;j <= 1000;j ++) {
            for (int k = 1;k <= j;k ++) {
                dp[i][j] = min(dp[i][j],max(dp[i - 1][k - 1],dp[i][j - k]) + 1);
            }
        }
    }
    while (T --) {
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        printf("%d %d\n",a,dp[b][c]);
    }
}

longest increasing subsequence VS strictly longest increasing subsequence

longest increasing subsequence

int n;
vector vec;
const int MAXN = 100010;
const int INF = 0x3f3f3f3f;
int dp[MAXN];
int main() {
    cin >> n;
    for (int i = 0;i < n;i ++) {
        int tmp;
        scanf("%d",&tmp);
        vec.push_back(tmp);
    }
    fill(dp,dp + n,INF);
    int len = vec.size();
    for (int i = 0; i < len;i ++) {
        *upper_bound(dp,dp + n,vec[i]) = vec[i];
    }
    int ans = lower_bound(dp,dp + n,INF) - dp;
    cout << ans << endl;
}

strictly longest increasing subsequence

int n;
vector vec;
const int MAXN = 100010;
const int INF = 0x3f3f3f3f;
int dp[MAXN];
int main() {
    cin >> n;
    for (int i = 0;i < n;i ++) {
        int tmp;
        scanf("%d",&tmp);
        vec.push_back(tmp);
    }
    fill(dp,dp + n,INF);
    int len = vec.size();
    for (int i = 0; i < len;i ++) {
        *lower_bound(dp,dp + n,vec[i]) = vec[i];
    }
    int ans = lower_bound(dp,dp + n,INF) - dp;
    cout << ans << endl;
}

[leetcode]229. Majority Element II

Problem

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space.

Code

class Solution {
public:
    vector majorityElement(vector& nums) {
        int cnt1 = 0;
        int cnt2 = 0;
        int p1 = 0;
        int p2 = 0;
        int n = nums.size();
        for (int i = 0;i < n;i ++) {
            if (nums[i] == p1 || nums[i] == p2) {
                if (nums[i] == p1) cnt1 ++;
                if (nums[i] == p2) cnt2 ++;
            }
            else if (cnt1 == 0 || cnt2 == 0) {
                if (cnt1 == 0) {
                    cnt1 ++;
                    p1 = nums[i];
                }
                else {
                    cnt2 ++;
                    p2 = nums[i];
                }
            }
            else  {
                cnt1 --;
                cnt2 --;
            }
        }
    
    
        int a1 = 0;
        int a2 = 0;
        for (int i = 0;i < n;i ++) {
            if (nums[i] == p1) a1 ++;
            if (nums[i] == p2) a2 ++;
        }
        vector ans;
        if (a1 > n / 3) ans.push_back(p1);
        if (a2 > n / 3 && p1 != p2) ans.push_back(p2);
        return ans;
    }
};

[leetcode]386. Lexicographical Numbers

Problem

Given an integer n, return 1 - n in lexicographical order.

For example, given 13, return: [1,10,11,12,13,2,3,4,5,6,7,8,9].

Please optimize your algorithm to use less time and space. The input size may be as large as 5,000,000.

Solution

  use pre-order tree travel algorithm.

Code

class Solution {
public:
    void dfs(int x,int n,vector &ans) {
        if (x != 0) {
            ans.push_back(x);
        }
        for (int i = 0;i <= 9;i ++) {
            if (x * 10 + i > 0 && x * 10 + i <= n) {
                dfs(x * 10 + i,n,ans);
            }
        }
    }
    vector lexicalOrder(int n) {
        vector ans;
        dfs(0,n,ans);
        return ans;
    }
};

  

test

test