A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).
The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).
How many possible unique paths are there?
Above is a 3 x 7 grid. How many possible unique paths are there?
Note: m and n will be at most 100.
题目解析：
让找从起始点出发一共有多少路径到达终点。这也就是动态规划问题。到达(......
阅读全文
以下代码摘抄CSDN论坛：
源文连接在：点击打开链接
本人目的只在于收藏；
C方法：
[cpp] view plaincopy
void del_sp(char *src) // 删除C风格字符串中的空格
{
char * fp = src;
while (*src) {
if (*src != ' ') { // 如果不是空格就复制
*fp = *src;
fp++;
}
src++;
}
*fp = '\0' ; //封闭字符串
}
void del_sp(string &str) // 删除string字符串中的空格
{
// 因为str.c_str() 是const的，不能直接修改，
......
阅读全文
今天启动Android studio时启动不了adb,以为是端口被占用，但是看了下没有。后来在它的logs里发现了如下信息：
Please use SDK Manager and check if Android SDK platform-tools are installed.
adb: Unable to locate adb.
意思是Android SDK里没装Android SDK platform-tools。打开Android Manager一看Tools一栏里Android SDK platform-tools果然没有装，打上勾装上之后果然好了。
只是郁闷为毛昨天没装也能用adb。看来这东西果然还有不少BUG啊。
阅读全文
原题：
1) ZOJ: http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2136
2) POJ: http://poj.org/problem?id=2533
问题描述：
A numeric sequence of ai is ordered if a1 < a2 < ... < aN. Let the subsequence of
the given numeric sequence (a1, a2, ..., aN) be any sequence (ai1, ai2, ...,
aiK), where 1 <= i1 < i2 < ... < iK <= N. For example, the sequence
(1, 7, 3, 5, 9, 4, 8) has ordered subsequences, e.g., (1, 7), (3, 4, 8) and
many others. All l......
阅读全文
影响决策的条件有二：四个堆最顶端的糖的颜色，以及目前篮子里有什么颜色。
可以用四个指针，分别代表四个堆目前的位置。每次决策有四种：分别从四个堆的顶部取糖果。状态则可以设计成d(p1, p2, p3, p4)代表目前指针的位置为p1, p2, p3, p4，最多可以揣走多少糖果。同时用二进制表达来代表篮子里的糖果颜色种类
Run Time:0.369s
#define UVa "9-2.10118.cpp" //Free Candies
#include<cstdio>
#include<vector>
#include<cstring>
#include<string>
#include<algorithm>
#include<io......
阅读全文
HDU 4115 Eliminate the Conflict
题目链接
题意：Alice和Bob这对狗男女在玩剪刀石头布，已知Bob每轮要出什么，然后Bob给Alice一些限制，1表示i轮和j轮Alice必须出不一样的，0表示必须出一样的，如果Alice有一局输了就算输了，否则就是赢，问Alice是否能赢
思路：2-sat问题，已经Bob出什么，Alice要么就出赢的要么就出平的，然后加上m个约束就是2-sat问题了
代码：
#include <cstdio>
#include <cstring>
#include <vector>
using namespace std;
const int N = 10005;
int t, n, m, x[N], sn, S[N * 2]......
阅读全文
(一) 前言在手机联系人匹配时经常会遇到这样一个问题：比如我手机中存入的联系人是A，号码 1234567 ； 嗯，那么当07551234567这么一个电话进来的时候，我们肯定要通过07551234567这个号码找到A这个联系人。所以这里面的匹配过程肯定不是简单而粗暴的字符串比较过程，而是有一个设计在里面，ok，那么我们今天就来分析这个设计。(二) 设计思想首先我们要明白一点，就是我们的匹配都是从后往前计算的。为了解决这个问题，Google给出了一个最小匹配(min match)两个概念，嗯， 嘛意思呢。。?1. min match， 最小匹配，就是说让号码......
阅读全文
今天在CareerCup 看到一个Amazon的面试题：
Given 2 binary arrays A and B i.e. containing only 0s and 1s each of size N. Find indices i,j such that Sum of elements from i to j in both arrays is equal and j-i (i.e. the length of the set i,j) is the maximum
possible value.
链接：http://www.careercup.com/question?id=25036663
O(n2)的算法看到很好想啦，当时也想到建立两个前缀和，然后用window滑动来寻找合适的区间，但是想了下当 （i,j)的时候，怎么来决定下一步是(i+1,j) ，和(i,j-1)，然后好像没有比较好......
阅读全文
题目大意：河的两岸有两个不同的国家，一边是穷国，一边是富国，穷国和富国的村庄的标号是固定的，穷国要变富需要和富国进行交流，需要建桥，并且建的桥不能够有交叉。问最多可以建多少座桥。
思路：建路时如下图所示
当一边的点已经固定了的时候，另外一边按照从小到大的序列与当前的边连接，得到最少的交叉。
题目给的第二组测试数据，如果按照图一则可以建2座桥，图二建一座桥
3
1 2
2 3
3 1
图一 ......
阅读全文
命名空间：
(1)由于现在软件规模越来越大，不可避免由很多人合作开发，这样就必然会产生全局变量（函数，类等）命名冲突的问题。所以在C++等语言中引入了namespace解决这个问题。namespace允许像类，对象，函数聚集在一个名字下，从本质上来讲namespace是对全局作用域的细分，允许同名全局变量（函数，类等）的定义。
例如：
namespace first
{
int var = 5;
}
namespace second
{
double var = 3.1416;
}
int main () {
cout << first::var << endl;
cout << second::var << endl;
return 0;......
阅读全文
近期课程的作业需要用到RPC编程，除了课堂上学到的知识，还得亲自动手。打算先写个简单的HelloWorld练习一下，顺便复习一下学到的知识。
RPC意为远程过程调用协议（Remote Procedure Call Protocol）。编制好单机应用程序，然后划分为两个或多个程序片，加入通信协议使得每片可以在单独的计算机上运行。从一个程序片调用另一个程序片的过程称为远程过程调用，即RPC。它是一个C/S模型，调用程序称为rpc client，被调用程序片称为rpc server。
对于RPC的编程过程可以简化如下：
1.构建解决问题的常规应用程序；
2.选择......
阅读全文
Problem Description
为了训练小希的方向感，Gardon建立了一座大城堡，里面有N个房间(N<=10000)和M条通道(M<=100000)，每个通道都是单向的，就是说若称某通道连通了A房间和B房间，只说明可以通过这个通道由A房间到达B房间，但并不说明通过它可以由B房间到达A房间。Gardon需要请你写个程序确认一下是否任意两个房间都是相互连通的，即：对于任意的i和j，至少存在一条路径可以从房间i到房间j，也存在一条路径可以从房间j到房间i。
Input
输入包含多组数据，输入的第一行有两个数：N和M，接下来的M行每行有两个数a和b，表示了......
阅读全文