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

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。

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];
    }

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注