xswang’s gists

xswang / gist:8120851

Created December 25, 2013 06:59

leetcode Plus One 各位加1，注意进位，后面的就直接是进位与原始的数相加了。

	class Solution {
	public:
	vector<int> plusOne(vector<int> &digits) {
	int t = digits.size();
	reverse(digits.begin(), digits.end());
	int q = 0;
	int sum = 0;
	sum = digits[0] + 1;//第一位加1
	q = sum/10;//取得进位
	sum %= 10;//取余数。

xswang / gist:8119708

Last active January 1, 2016 08:39

leetcode Remove Duplicates from Sorted Array II

	递归代码：
	class Solution {
	public:
	int removeDuplicates(int A[], int n) {
	if(n <= 1) return n;//如果是空的或者只有一个元素，直接返回就行。
	int length = 1;//初始化总长度为1；
	int cnt = 1,i,j;//单个元素计数，初始化为1；
	for(i = 1,j = 1; j < n; j++){//从第二个元素开始比较；i作为指示某元素应该放的位置，j作为遍历到的元素的位置；
	if(A[j] == A[j-1]){//如果和前一个元素相同。用j指示。
	if(cnt >= 2) continue;//如果单个元素个数已经大于或者等于2，则跳过。

xswang / gist:7911010

Created December 11, 2013 14:08

UVAOJ 10603 - Fill

	#include <iostream>
	#include <cstring>
	#include <fstream>

	using namespace std;

	int state[3];//每个瓶子的状态。
	int vol[3];//每个瓶子里的水量
	bool vis[200][200][200];
	bool flag;

xswang / gist:7906396

Created December 11, 2013 07:36

UVAOJ10603 - Fill 这个题最开始卡在如何定义所有状态？虽然知道是暴力搜索遍历所有状态，但是所有状态是什么呢？不像之前的n个数全排列那样的问题，很清楚所有状态是什么。后来简单查了查，知道原来这个状态是要自己定义的。每个节点的出度可以有6个：从1倒向2,3；从2倒向1,3；从3倒向1,2；也就是每个节点都会有6个邻接点。

1

xswang / gist:7782648

Last active December 30, 2015 05:29

uvaoj 639 - Don't Get Rooked 和8皇后不同的地方：每行可以放多个。之前觉得递归cur+1的方法是不行的，因为有些行可能一个都不能放象棋。另外，在做冲突检测的时候，只做前向考虑，即只判断该位置之前是否会冲突。 dfs中有两个for循环，把每行能放的棋子先尽可能放完，然后再考虑下一行。注意和8皇后问题的区别。

	#include <iostream>
	#include <cstring>
	#include <fstream>
	#define N 4
	using namespace std;

	int board[N][N];
	int total;
	int maxm;

xswang / gist:7750343

Created December 2, 2013 14:34

216 Getting in Line: 这个题是做了差不多一天的。其中犯了不少错，主要是一些细节：比如 = 写成 == 。\n 另外，这里要用到排列生成，而不是用子集。这是我范的比较严重的错误，导致算法就错了。\n 另外，坐标是整数，而不是实数，我直接想当然给弄成了double了，导致一直WA，这就是不认真的后果。\n 做这个题最大的收获：1，信心越来越强了，之前没做过ACM的题，看到这么长的题，都不敢想象自己能做出来。从开始刷题到现在，已经完成了5个题，信心越来越强；2，端正了自己的态度，正确看待刷题这件事，我是一个很不喜欢做题的人，而且之前对ACM题有个误解，以为应该像写快排程序那样，时间不超过5分钟，代码不超过30行，哈哈，我之前真是又傻又天真。现在我知道了，刷题和我之前看论文…

	正确代码：
	#include <iostream>
	#include <cstring>
	#include <fstream>
	#include <algorithm>
	#include <vector>
	#include <cstdlib>
	#include <iomanip>
	#include <cmath>
	#define N 10

xswang / gist:7726805

Created December 1, 2013 00:20

uvaoj 10474 - Where is the Marble? 这个题是backtracking easy里的一个，不过也太easy了。这个题的思路，翻译成汉语就是：给定N个带有数字的球，可以有相同的数。再给定Q个query，也就是一个数字，问带有query数字的球在那一堆球种处于第几个position，下标从1开始的。先是一个非递归的代码1：首先对那堆球排序。然后从写有球数字的数组中查找。然后是递归版本的代码2：中间用到了回溯，其实就是：当能找到时，就不再继续往下找，而是return。这样比继续往下枚举节省很多时间。回溯和枚举的区别：枚举是要把所有情况都要列出来，即使中间找到了结果，也还继续。用来求多个解的问题。回溯是在递归枚举的基础上，只要找到一个解就停止。用来…

	代码1：1.128秒
	#include <iostream>
	#include <string.h>
	#include <fstream>
	#include <algorithm>
	using namespace std;

	int m[100],query;
	int main(){
	//ifstream fin;

xswang / gist:7719240

Last active December 29, 2015 19:48

UVaOJ 131 – The Psychic Poker Player 这题一开始以为是搞不定的。之前也没玩过什么扑克，一看这题叙述得这么多，感觉希望渺茫。解题过程中遇到几个误区，都是把问题想复杂了，也是因为没好好理解题意的原因吧。1，我以为，可以这样：对每一个example来说，先取桌上最顶部替换手中一张，下次可以再从桌上最顶部取一张换掉手中的任何一张（包括刚从桌上取到的），我当时想：我的天，这个怎么做，太复杂了！实际上，一次只能从桌上的顶部一次取0或几张，至于具体取几张，就要看替换手中牌之后那种情况最大。2，我以为：对于 33334,55552这样的情况，等级是不同的呢，我觉得，55552肯定大于33334吧，而实际上，它俩是同等级的。这样的话，问题又简单了很多，哈哈哈哈..…

	#include <iostream>
	#include <string.h>
	#include <fstream>
	#include <algorithm>
	using namespace std;

	int poker[10],suit[10];
	char temppoker[10],tempsuit[10];
	void print_result(int &res){
	cout<<"Hand: ";

xswang / gist:7678053

Created November 27, 2013 15:57

uvaoj 11205: 这个题做了差不多2个半天。主要思路是： led能亮的根数可以为1-p根，对于每一种情况（比如能亮2根的情况）枚举可能亮的位置。用sy数组存储。得到枚举的位置后，用sy与各个symbol求交集，也就是sy & symbol。相与的结果还是放在res矩阵中。相与之后，判断res中有没有相同的行，如果有相同的行，则表明不成立。最后，选取根数最小的数目。

	#include <iostream>
	#include <vector>
	#include <string.h>
	#include <fstream>
	using namespace std;

	void dfs(int *sy,vector<vector<int> > matrix,int n,int p,int cur,int &r){
	if(cur == p){//如果枚举到了i个。
	int res[n][p];
	memset(res, 0, sizeof(res));

xswang / gist:7641901

Last active December 29, 2015 08:18

UVAoj 10167: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=1108 这个是最简单的brute force，不过提交时也又是WA又是TLE的折磨了我好多次。要判断线两边的cherry个数是否相同，只需要判断:将cherry的坐标带入直线方程后，ax+by>0的个数与ax+by<0的个数是否相同即可。当时WA的地方在：flag的位置没放对，对每一次的枚举方程来说，都要将两边个数（分别用pos,neg表示）以及找到解的标志重新初始化。 TLE的地方：没有先把每次2n个数据放到内存中，而是读一个计算一个。可能是在IO时花费了不少时间。

	#include <stdio.h>
	#include <iostream>
	#include <vector>
	using namespace std;
	int main(){
	int n;
	while(scanf("%d",&n)){
	if(n == 0)break;
	int pos, neg, x, y, tag;
	vector<int> veca,vecb;