和完全背包问题类似
定义dp[i][j]为前i个硬币，能够组成价值为j时硬币数的最小值
if(coins[i]<=j)
dp[i+1][j] = min(dp[i][j],dp[i+1][j-coins[i]]+1)
else
dp[i+1][j]=dp[i][j]

You are given coins of different denominations and a total amount of money amount. Write a function to compute the fewest number of coins that you need to make up that amount. If that amount of money cannot be made up by any combination of the coins, return -1.

Example 1:
coins = [1, 2, 5], amount = 11
return 3 (11 = 5 + 5 + 1)

Example 2:
coins = [2], amount = 3
return -1.

Note:
You may assume that you have an infinite number of each kind of coin.

AC代码：

/*
和完全背包问题类似
定义dp[i][j]为前i个硬币，能够组成价值为j时硬币数的最小值


if(coins[i]<=j)
dp[i+1][j] = min(dp[i][j],dp[i+1][j-coins[i]]+1)
else
dp[i+1][j]=dp[i][j]
*/


class Solution {
public:
	int coinChange(vector<int>& coins, int amount) {

		vector<vector<int>> dp(coins.size() + 1, vector<int>(amount + 1, 1000000));
		//初始化边界条件
		for (int i = 0; i < coins.size(); i++)
		{
			if (coins[i] <= amount)
				dp[0][coins[i]] = 1;
		}
		//初始化边界条件
		for (int i = 0; i < dp.size(); i++)
		{
			dp[i][0] = 0;
		}

		//进行动态规划
		for (int i = 0; i<coins.size(); i++)
		{
			for (int j = 0; j <= amount; j++)
			{
				if (coins[i] <= j)
					dp[i + 1][j] = min(dp[i][j], dp[i + 1][j - coins[i]] + 1);
				else
					dp[i + 1][j] = dp[i][j];
			}
		}
		if (dp[coins.size()][amount] == 1000000) return -1;
		else return dp[coins.size()][amount];

	}
};

今天在做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.

代码如下：

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

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代码：

/**
 * 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;
    }
};

我们可以通过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命令，错误了三次：

在CentOS安装CMake

yum install -y gcc gcc-c++ make automake

yum install -y wget

wget http://www.cmake.org/files/v2.8/cmake-2.8.10.2.tar.gz

tar -zxvf cmake-2.8.10.2.tar.gz

cd cmake-2.8.10.2

./bootstrap

gmake

gmake install

题目：
1.把题目根据要求转化为拓扑排序求解。
2.首先遍历入度为0的节点，并把节点的病毒传递到其下一层的节点。
3.重复进行拓扑排序。
4.注意题目要求mod 142857

样例输入

4 4 1
1
1 2
1 3
2 3
3 4

样例输出

6

AC代码：

/*
题目：
1.把题目根据要求转化为拓扑排序求解。
2.首先遍历入度为0的节点，并把节点的病毒传递到其下一层的节点。
3.重复进行拓扑排序。
4.注意题目要求mod 142857
*/
/*
*/

#include<string>
#include <iomanip>
#include<fstream>
#include<set>
#include<queue>
#include<map>
//#include<unordered_set>
//#include<unordered_map>
//#include <sstream>
//#include "func.h"
//#include <list>
#include<stdio.h>
#include<iostream>
#include<string>
#include<memory.h>
#include<limits.h>
//#include<stack>
#include<vector>
#include <algorithm>
using namespace std;

struct vertex{
	unsigned long long virus;
	int degree;
	bool visited;
	vector<int> next;
	vertex() :virus(0), degree(0), visited(false), next(0){};
};

/*
函数名  ：main
函数功能：主函数
*/
int main(void)
{
	int n, m, k;
	cin >> n >> m >> k;

	//节点个数
	vector<vertex> v(n + 1);

	//感染病毒的节点
	for (int i = 0; i < k; i++)
	{
		int tmp;
		scanf("%d", &tmp);
		v[tmp].virus = 1;
	}

	//输入边关系
	for (int i = 0; i < m; i++)
	{
		int a, b;
		scanf("%d %d", &a, &b);
		v[a].next.push_back(b);
		v[b].degree++;
	}


	while (1)
	{
		bool change = false;
		for (int i = 1; i < v.size(); i++)
		{
			if (!v[i].visited && v[i].degree == 0)
			{
				change = true;
				v[i].visited = true;
				//需要MOD，避免后面溢出
				v[i].virus %= 142857;
				for (int j = 0; j < v[i].next.size(); j++)
				{
					//更新病毒和入度
					int l = v[i].next[j];
					v[l].degree--;
					v[l].virus += v[i].virus;
				}
			}
		}
		//如果没有变化，证明没有入度为0的节点了。
		if (!change) break;
	}

	unsigned long long  totalVirus = 0;
	for (int i = 1; i < v.size(); i++)
		totalVirus += v[i].virus;
	//根据答案要求进行MOD
	totalVirus %= 142857;
	cout << totalVirus << endl;

	return  0;
}

1.题目要求在给定的数组和target中，找出数组中的两个数a和b，使得a+b=target
2.遍历一次nums，利用map记录已经遍历过的nums[i]，并记录其index ：i+1
3.每次求出b=target-nums[i]，检测b是否在map中，如果在，则已经得到答案，否则，把nums[i]存到map里面

Given an array of integers, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.

You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int,int> exist;
        vector<int> ans(0);
        for(int i=0;i<nums.size();i++)
        {
            int b=target-nums[i];
            if(exist.find(b)!=exist.end())
            {//如果哈希表里面已经存在b，则压入ans中，并return，b先于nums[i]放入哈希表，所以b的index肯定小于nums[i]
                ans.push_back(exist[b]);
                ans.push_back(i+1);
                return ans;
            }
            else
            {//找不到，即和不为target，则把nums[i]放入哈希表
                exist[nums[i]]=i+1;
            }
        }

    }
};

/ :根分区，是必须要有的
/opt ：用于安装软件
/swap ：属于将换分区，相当于windows系统的虚拟内存，电脑物理内存不够用时，会调用swap分区
/boot ：用于引导系统的grub在这个分区中
/home ：给普通用户使用
/var ：是variable变量，有些软件工具在使用时的一些变量参数放在这
/usr ：用户数据存放点

使用的命令是 sudo yum install gcc-c++。