小奥的学习笔记

  • Home
  • Learning & Working
    • Speech Enhancement Notes
    • Programming language
    • Computer & DL
    • MOOC
  • Life
    • Life Time
    • Thinking & Comprehension
    • Volunteer
    • Plan
    • Travel
  • Footprints
  • GuestBook
  • About
    • About Me
    • 个人履历
    • 隐私策略
  1. 首页
  2. Study-notes
  3. Programming language
  4. Algorithm
  5. Leetcode
  6. 正文

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

2019年4月3日 1098点热度 0人点赞 0条评论

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];
    }
本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: leetcode 算法
最后更新:2019年4月3日

davidcheung

这个人很懒,什么都没留下

打赏 点赞
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

搜索
欢迎关注我的个人公众号
最新 热点 随机
最新 热点 随机
DEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架 奥地利匈牙利九日游旅程 论文阅读之Study of the General Kalman Filter for Echo Cancellation 小奥看房之鸿荣源珈誉府 杭州往返旅途及西溪喜来登和万怡的体验报告 2022年的第一篇碎碎念
奥地利匈牙利九日游旅程小奥看房之鸿荣源珈誉府论文阅读之Study of the General Kalman Filter for Echo CancellationDEEPFILTERNET:一种基于深度滤波的全频带音频低复杂度语音增强框架
华为软件上机笔试(2019年8月7日)题目解答(部分) 使用 WordPress 页面模板 2019 CFA CUP QUARTER FINAL: SHANDONG LUNENG TAISHAN F.C VS BEIJING SINOBO GUOAN F.C Happy New Year for Tiger! Leetcode题目解析(191121):105&114 随机漫步模型之python实现
标签聚合
Java 鸟哥的linux私房菜 学习 算法 生活 Python leetcode linux python学习 高中
最近评论
davidcheung 发布于 5 个月前(02月09日) The problem has been fixed. May I ask if you can s...
tk88 发布于 5 个月前(02月07日) Hmm is anyone else having problems with the pictur...
cuicui 发布于 8 个月前(10月20日) :wink:
niming 发布于 10 个月前(09月19日) 同级校友,能刷到太巧了
davidcheung 发布于 2 年前(08月16日) 我得找一下我之前整理的word文档看一下,如果找到了我就更新一下这篇文章。
Nolan 发布于 2 年前(07月25日) 您的笔记非常有帮助。贴图不显示了,可以更新一下吗?
davidcheung 发布于 3 年前(06月19日) 到没有看webrtc的代码。现在主要在看我们公司的代码了。。。只是偶尔看一看webrtc的东西。。。
aobai 发布于 3 年前(03月13日) gain_change_hangover_ 应该是每三个block 只能够调整一次,这样保证每帧...
匿名 发布于 5 年前(12月30日) 烫
小奥 发布于 5 年前(12月12日) webRTC里面的NS本身我记得就是在C++里面呀

COPYRIGHT © 2025 小奥的学习笔记. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

陕ICP备19003234号-1

鲁公网安备37120202000100号