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?
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 | int singleNumber(int A[], int n) { int ones = 0;//记录只出现过1次的bits int twos = 0;//记录只出现过2次的bits int 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; } |
解析：
用3个整数来表示INT的各位的出现次数情况，one表示出现了1次，two表示出现了2次。当出现3次的时候该位清零。最后答案就是one的值。
ones 代表第ith 位只出现一次的掩码变量
twos 代表第ith 位只出现两次次的掩码变量
threes 代表第ith 位只出现三次的掩码变量
假设现在有一个数字1，那么我们更新one的方法就是‘亦或’这个1，则one就变成了1，而two的更新方法是用上一个状态下的one去‘与’上数字1，然后‘或’上这个结果，这样假如之前one是1，那么此时two也会变成1，这make sense，因为说明是当前位遇到两个1了；反之如果之前one是0，那么现在two也就是0。注意更新的顺序是先更新two，再更新one，不理解的话只要带个只有一个数字1的输入数组看一下就不难理解了。然后我们更新three，如果此时one和two都是1了，那么由于我们先更新的two，再更新的one，two为1，说明此时至少有两个数字1了，而此时one为1，说明了此时已经有了三个数字1，这块要仔细想清楚，因为one是要‘亦或’一个1的，值能为1，说明之前one为0，实际情况是，当第二个1来的时候，two先更新为1，此时one再更新为0，下面three就是0了，那么‘与’上three的相反数1不会改变one和two的值；那么当第三个1来的时候，two还是1，此时one就更新为1了，那么three就更新为1了，此时就要清空one和two了，让它们‘与’上three的相反数0即可，最终结果将会保存在one中。
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.
解析
定义一个全局的剩余油量total，定义一个 记录i到i+1是否可行（即加上在本加油站加油的数量-本加油站到下一加油站加油之前消耗的油量），定义一个站点的索引值index。我们注意到，如果sum<0，也就是说从第i到第i+1个点不可行，那肯定我们原先定义的那个index的位置是无法能够转完一圈的（因为在第i点和第i+1点这里断了）。我们就令sum=0，然后令index=i，相当于说从i+1个点开始了（所以在下面return的时候是Index+1），然后开始继续往下走，如果i还没有走到最后一个，sum又小于0了，那么与前面一样，肯定要从下一个点开始，假定为起点。当一直到最后一个sum都没有小于0的话，且total也大于等于0的话，那么自然从i+1开始往后到最后一个点，再从最后一个点到起点一直到i，再到i+1是可以构成一个圈。若total<0的话，则铁定i到i+1所用的油量无法用total补充回来，因此还是断开的，所以无法完成一圈，故返回-1。
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 | 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数组的最后一个值，就是整个数组是否可以拆分的布尔值了。
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 | 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]; } |
