linux shell 里面要加\的原因

在sed中。

 因为（） { } ？ + | 是在ERE里面的。所以需要加\( \)。

Linux-ABS-unsolved problem

1.作为子进程的运行的管道,不能够改变脚本的变量.
1 variable="initial_value"
2 echo "new_value" | read variable
3 echo "variable = $variable" #variable = initial_value

Win10 virtualbox高版本无法启动虚拟机

解决：
  点击启动，按住enter。尝试多次

[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;
}