2019-04-03  272 views 评论

# leetcode之single-number-ii、Gas station、word break

标签：

## 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? ​

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.

## 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数组的最后一个值，就是整个数组是否可以拆分的布尔值了。