## single-number-ii

Given an array of integers, every element appears three times except for one. Find that single one.

Note:

Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory? ​

int singleNumber(int A[], int n) {int ones = 0;//记录只出现过1次的bitsint twos = 0;//记录只出现过2次的bitsint threes = 0;for(int i = 0; i < n; i++){ twos |= ones&A[i];//要在更新ones前面更新twos ones ^= A[i]; threes = ones&twos;//ones和twos中都为1即出现了3次 ones &= ~threes;//抹去出现了3次的bits twos &= ~threes; }return ones;}

ones 代表第ith 位只出现一次的掩码变量

twos 代表第ith 位只出现两次次的掩码变量

threes 代表第ith 位只出现三次的掩码变量

## gas station

There are N gas stations along a circular route, where the amount of gas at station i isgas[i]. You have a car with an unlimited gas tank and it costscost[i]of gas to travel from station i to its next station (i+1). You begin the journey with an empty tank at one of the gas stations. Return the starting gas station’s index if you can travel around the circuit once, otherwise return -1.

Note: The solution is guaranteed to be unique.

int canCompleteCircuit(vector<int> &gas, vector<int> &cost) { int total=0; int sum=0; int index=-1; for(int i=0;i<gas.size();i++) { sum+=gas[i]-cost[i]; total+=gas[i]-cost[i]; if(sum<0) { sum=0; index=i; } } return (total>=0)?index+1:-1;}

## word break

Given a string s and a dictionary of words dict, determine if s can be segmented into a space-separated sequence of one or more dictionary words.

For example, given s =”leetcode”, dict =[“leet”, “code”]. Return true because”leetcode”can be segmented as”leet code”. 题解：这个题其实就是可以用动态规划来进行解决，简单来说：就是将字符串分为0~j和j~i， 其中范围 [0, j) 就是dp[j]，范围 [j, i) 就是s.substr(j, i-j)，其中dp[j]是之前的状态，我们已经算出来了，可以直接取，只需要在字典中查找s.substr(j, i-j)是否存在了，如果二者均为true，将dp[i]赋为true，并且break掉，此时就不需要再用j去分[0, i)范围了，因为[0, i)范围已经可以拆分了。最终我们返回dp数组的最后一个值，就是整个数组是否可以拆分的布尔值了。

bool wordBreak(string s, unordered_set<string> &dict) { int len = s.size(); if(len == 0 || dict.size() == 0) return false; vector<bool> isright(len+1,false);//表示字符串s[0~i-1]是否可分的bool值 isright[0] = true;//空串的情况 //将字符串分为0~j,和j~i；然后不断递归细分，不断细分之后再从最小的开始判断 //再恢复回来。类似于归并排序（去学算法里面的矩阵连乘） for(int i = 1;i <= len; i++) { for(int j = i-1; j >= 0; j--) { if(isright[j] && dict.find(s.substr(j,i-j))!= dict.end()) //substr第二个参数表示有多少个 { isright[i] = true;//若可分，则当前位置设为true， break; } } } return v[len]; }