今天在做leetcode的Longest Increasing Subsequence题目时，需要用到二分查找，于是翻看了《STL源码剖析》这本书，发现map里面有lower_bound和upper_bound这两个函数。用法如下：
map<int,int> m;
int x=10;
map<int,int>::iterator ite;
ite=m.lower_bound(x);//返回比第一个大于或等于x的值的位置 ，当m为空时，返回m.begin()
ite=m.upper_bound(x);//返回比最后一个大于或等于x的值的位置
主要有两种思路：
一、
本题只需要判断能否到达最后一个数，那么可以采用贪心策略，到达某个位置i后，在直接在这个位置的基础上走nums[i]步，主要保证能一直前进，就能达到终点；
那么，什么时候才不能一直前进呢？
答案是，遇到0的时候，遇到nums[i]=0的时候，只要我们想办法跳过这个0，那么就可以确保我们可以继续前进。
所以遇到0时的处理方法是，往回搜索，设当前的位置为pos，即nums[pos]=0，一直搜索之前的数，判断nums[i]+i是否大于nums[pos]，大于则可以继续上述的贪心算法，假如一直跳不过0（即搜索到i=0仍跳不过pos），则return false。
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
For example:
A = [2,3,1,1,4], return true.
A = [3,2,1,0,4], return false.
Subscribe to see which companies asked this question
代码如下：
[c language=”++”]
class Solution {
public:
bool canJump(vector<int>& nums) {
if(nums.size()==1) return true;
int pos=0;
while(pos<nums.size()-1) { if(nums[pos]!=0) {//走最远的位置 pos=nums[pos]+pos; } else {//如果最远的位置为0 int now=pos; for(int i=pos;i>=0;i–)
{//找到能跳过0的位置
if(i+nums[i]>now)
{
pos=i+nums[i];
break;
}
}
if(pos==now)
{//找不到跳过0，则false
return false;
}
}
}
return true;
}
};
[/c]
1.看题目的例子会容易混淆，弄不清楚哪边是低位，哪边是高位，实际上(2 -> 4 -> 4) + (5 -> 6 -> 4) = (7 -> 0 -> 9)，即链表的头部是低位
2.这道题类似使用string存储的大整数相加，新增一个变量carry，代表进位，然后遍历链表即可
3.空间复杂度为O（1），时间复杂度为O（max（l1，l2）），即两个链表中最长的链表
4.注意(1)+(9->9->9->9->9->9)这样的情况，所以还是需要全部遍历一遍。
You are given two linked lists representing two non-negative numbers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.
Input: (2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 0 -> 8
AC代码：
[c language=”++”]
/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
//链表开头是个位
class Solution {
public:
ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
if(l1==NULL) return l2;
else if(l2==NULL) return l1;
ListNode* ans=l1;//以l1作为返回结果
ListNode* preL1=l1;
int c=0;//进位
while(l1!=NULL&&l2!=NULL)
{
int sum=c+l1->val+l2->val;
l1->val=sum%10;//求个位
c=sum/10;//求进位
preL1=l1;
l1=l1->next;//指向下一个
l2=l2->next;
}
if(l2!=NULL)//如果l2不为空，直接把l1接过去
{
preL1->next=l2;//当前的l1为空，所以要用前面的preL1指向l2
l1=preL1->next;
}
while(l1!=NULL&&c!=0)
{
int sum=c+l1->val;
l1->val=sum%10;
c=sum/10;
preL1=l1;
l1=l1->next;
}
if(c!=0)
{
ListNode* tmp=new ListNode(c);
preL1->next=tmp;
}
return ans;
}
};
[/c]
我们可以通过telnet来登录smtp服务器进行邮件的发送，下面的实践过程：
首先打开终端，输入telnet，如果没有该命令，需要在系统服务中启动telnet。
然后直接点击回车，输入open，再输入qq的smtp邮箱，注意加上端口号25：
然后输入helo XXX，再输入auth login进行验证登录。其中登录的时候需要QQ帐号的BASE64编码，这个可以网上找一个BASE64编码的网址进行编码。
然后接下来需要输入授权码的BAS64编码，详情可以查看QQ邮箱的帮助网页：
http://service.mail.qq.com/cgi-bin/help?subtype=1&&id=28&&no=1001256
注意获取的授权码并未进行BASE64编码，我们需要把获取的授权码进行一次BASE64编码。
最终的时间过程如下，有时候会提示命令错误，这是因为传输错误导致，重复多次输入即可，如下面的mail from命令，错误了三次：
