豌豆

在我之前的一篇博客里介绍了 对称加密的模式 . 这里主要聊一聊如何使用 openssl 来进行 AES 加密 .

一. OPENSSL crypto API

openssl 加密 API 分两个部分: High Level and Low Level . 对于大部分人来说，使用 High Level 就够用了， 这些 API 被冠以 EVP (Envelope) ，表示对 Low Level 的封装。High Level API 提供了包括 对称/非对称加解密 ， 签名, 验证, 哈希，MAC 等一系列组件，屏蔽了 Low Level API 的复杂逻辑，使用起来安全高效。对于除非有需要进行加密算法级别的改进，否则不建议使用 Low Level API.
大部分 EVP API 有一个 int 型返回值 ，用来表示操作是否成功：1 表示成功， 0 表示失败。但有些时候也会返回 -1 ，表达如内存分配或者其他什么错误。官方指导代码如下:

二. 使用 EVP API 进行 AES 加解密

对于 AES 加解密，EVP API 分为两种，EVP_Encrypt / EVP_Decryp 系列 和 EVP_Cipher 系列。后者是对前者进一步的封装。它们具体使用的套路都是一样的：

1. 创建加解密上下文 EVP_CIPHER_CTX
2. 调用 xxxInit() 函数，使用 key(密钥)、iv(前置向量) 和 cipher(算法) 对上下文初始化
3. 调用 xxxUpdate() 函数进行加解密。该函数支持流式操作。即对于一段明文来说，分成多组按顺序进行加密，和一次性全部加密，不影响其生成的密文的正确性。
4. 调用 xxxFinal() 函数获取上下文中遗留的信息
5. 释放上下文， 完成加解密。

继续阅读

一 链表倒置

链表倒置是链表的基本操作之一。

题目 一 Reverse Linked List

LeetCode 206 Reverse Linked List

Reverse a singly linked list.
Example:
Input: 1->2->3->4->5->NULL
Output: 5->4->3->2->1->NULL
Follow up:
A linked list can be reversed either iteratively or recursively. Could you implement both?

题目提示可以用 迭代 或 递归 两种方法来解。

• 迭代方法
  如图： 两个指针 head p 分别指向 表头，欲倒置的元素. 为了使下一个欲倒置的元素不会 野 掉， 还需要一个指针 tmp 来保护它
  1. p->next 指向 head
  2. head->next 指向 tmp
  3. head = p, p = tmp, tmp 保护下一个欲倒置的元素

  代码：

  class Solution { public: ListNode* reverseList(ListNode* head) { if(!head) return NULL; if(!head->next) return head; ListNode *p,*tmp; p = head->next; tmp = p->next; head->next = NULL; while(p1){ p->next = head; head = p; p = tmp; if(tmp) tmp = tmp->next; } return head; } };

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22

  class Solution { public:     ListNode* reverseList(ListNode* head) {         if(!head) return NULL;         if(!head->next) return head;           ListNode *p,*tmp;         p = head->next;         tmp = p->next;         head->next = NULL;           while(p1){             p->next = head;             head = p;             p = tmp;             if(tmp)                 tmp = tmp->next;         }           return head;     } };

• 递归方法
  思想和上面一样，只不过代码的写法不同：
  class Solution { public: ListNode* reverseList(ListNode* head) { if(!head || !head->next){ return head; } ListNode* p = reverseList(head->next); head->next->next = head; head->next = NULL; return p; } };

  1 2 3 4 5 6 7 8 9 10 11 12 13

  class Solution { public:     ListNode* reverseList(ListNode* head) {         if(!head || !head->next){             return head;         }           ListNode* p = reverseList(head->next);         head->next->next = head;         head->next = NULL;         return p;     } };

  

  递归的方法代码简洁高效，在很多链表题目中都会用到它，所以特别重要。例如下一题

继续阅读

例题 一 : Triangle

LeetCode 120. Triangle

Given a triangle, find the minimum path sum from top to bottom. Each step you may move to adjacent numbers on the row below.
For example, given the following triangle

[
[2],
[3,4],
[6,5,7],
[4,1,8,3]
]

The minimum path sum from top to bottom is 11 (i.e., 2 + 3 + 5 + 1 = 11).

分析：

设三角形共有 $N$ 行， $r$ 为三角形的行， $c$ 为三角形的列。从点 $P(r,c)$ 出发，每向下走一步有两个点$P_1(r+1,c), P_2(r+1, c+1)$ 可以选择 ,如果每次都选值小的点$min(P1, P2)$，则最后得到的点的值之和即是最优解。令 $M(r,c)$ 为从 $P(r,c)$ 开始到下面的列的各条路径中，最佳路径的数字之和。

解法一：

这是一个典型的递归问题。

$$M(r,c) = \begin{cases}  P(r,c), & \text{if r = N }\\  min(M(r+1,c), M(r+1,c+1)) + P(r,c),& \text{others}\\ \end{cases}$$

由此写出代码：

代码没有问题，在 "Run Code" 时可以得出正确的结果。但是 "Submit" 却会给出 "Time Limit Exceeded",超时！

如果我们推算这个解法的时间复杂度的话，可以得到 $O(2^n)$ .这不超时就有鬼了。我们需要改进这个算法。

继续阅读