Skip to content

Instantly share code, notes, and snippets.

@xswang
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
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
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
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
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
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
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
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
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
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;