iyuwwy-CSDN博客

原创 const对象的成员不可修改，但const对象通过指针维护的对象却可以修改

const对象只能调用const成员函数是因为const函数不会改变成员对象，这点和const对象的本意是相同的，其他函数有可能会改变成员变量，所以编译器拒绝通过调用非const函数这里的转换是说，另建立了一个指针，而不是原来的东西，简单的来说就是通过copy，去掉了const属性（当然真实情况下并不是真正的copy），相当于创建了临时变量，而不再是原对象中的成员class Solution {public: void print(void) const { int*

2020-08-18 11:11:26 737

原创逻辑题 nim游戏

leetcode292你和你的朋友，两个人一起玩 Nim 游戏：桌子上有一堆石头，每次你们轮流拿掉 1 - 3 块石头。拿掉最后一块石头的人就是获胜者。你作为先手。你们是聪明人，每一步都是最优解。编写一个函数，来判断你是否可以在给定石头数量的情况下赢得游戏。如果数据量小的话，可以用dp解决。设每次最多拿k个石头，dp[n]表示剩下n块石头时自己先手能否获胜。那么自己拿完后对手状态为dp[n-i]如果dp[n-1],dp[n-2]…dp[n-k]都是True，说明无论自己拿几个石头对手都能获胜，

2020-07-30 15:36:53 557

原创 python中&,|和and, or区别

2020-07-27 16:07:27 328

原创字节三面

32位和64位区别，主要是内存范围以及运算速度不同运算速度不同。64位CPU GPRs(General-Purpose Registers，通用寄存器)的数据宽度为64位，64位指令集可以运行64位数据指令，也就是说处理器一次可提取64位数据(只要两个指令，一次提取8个字节的数据)，比32位(需要四个指令,一次提取4个字节的数据)提高了一倍，理论上性能会相应提升1倍。计算机寻址能力不同。64位处理器的优势还体现在系统对内存的控制上。由于地址使用的是特殊的整数，因此一个ALU(算术逻辑运算器)和寄存器可以

2020-07-26 21:14:27 1280

原创 heapq模块学习笔记

随学随记用heappush处理key-value键值对元素。heappush可以对key-value键值对格式排序，key-value序对必须是统一格式（比如都是list或都是tuple）heappush以key-value键值对的第一个元素为key进行排序，后面无论有多少个元素都视为value举例来说，from heapq import *list1 = [[1,2,3],[2,3],[3,4],[1,1]]list2 = []for i in range(len(list1)):

2020-07-23 15:05:02 177

原创阿里秋招一面

稍微记一下，面试有点硬核，简历讲了不到5分钟就开始做题了1.怎么判断一个数是2的倍数？要求两行代码两行代码开始没想出来，后来查了一下发现如果一个数是2的倍数，那么k &(k-1)一定为02.给出一个数组，要求找两数相减最大差值，条件是大数必须在小数右侧。有点类似买卖股票第一题股票最大利润，后来面试官说不用数据结构怎么做：从右往左遍历数组，更新最大值和最大差。因为从右往左遍历数组，所以当前找到的最大值一定在当前遍历值的右侧或自身位置，那么这样找到的最大差一定满足条件。（感觉从左往右找最小值好像

2020-07-21 20:12:23 121

转载医院候诊问题

医院候诊问题问题描述：医院某科室，有医生m名现有病人n名，每个病人看病时长已知。写一个函数，做医生和病人的分配，要求医生负载尽量均衡。代码改自医院排队候诊模型，对多线程不是很熟，只能写一点类伪码做个记录#include<thread> #include<cstdlib>#include<ctime>#include<mutex>#include<condition_variable>#include<iostream

2020-07-20 22:15:51 858

转载洗牌算法

来源：labuladong.github我知道大家会各种花式排序算法，但是如果叫你打乱一个数组，你是否能做到胸有成竹？即便你拍脑袋想出一个算法，怎么证明你的算法就是正确的呢？乱序算法不像排序算法，结果唯一可以很容易检验，因为「乱」可以有很多种，你怎么能证明你的算法是「真的乱」呢？所以我们面临两个问题：什么叫做「真的乱」？设计怎样的算法来打乱数组才能做到「真的乱」？这种算法称为「随机乱置算法」或者「洗牌算法」。本文分两部分，第一部分详解最常用的洗牌算法。因为该算法的细节容易出错，且存在好几种变体，

2020-07-19 23:19:27 207

原创阿里面试题1

对于在（0,231）内的任意整数x，有多组a,b（0≤a,b≤231）使x⊕a⊕b的值最大。求满足上述条件且|a-b|最小的a,b有多少组思路：很明显，对于一个32位无符号整数，最大值为0xffffffff。那么如果x⊕（a⊕b）最大（异或满足结合律），显而易见a⊕b=~x（32位下），此时x⊕a⊕b=0xffffffff。以100举例，bin(100)=1100100;则~100=0011011a和b在第m位的二进制数必须相同才能使在~x中的第m位为0,a和b在第n位的二进制数必须不同才能使在~

2020-07-17 20:35:03 188

原创已知链表中含有环，返回这个环的起始位置

简单写一下思路：已知链表中有环，用快慢指针法找到相遇点。因为慢指针走1步快指针走2步，那么当快慢指针相遇时，假设慢指针走了k步，那么快指针一定走了2k步，多出来的k步就是环的长度。也就是说环长度为k。此时假设相遇点距离环起点距离为m，那么环起点距离链表起点为k-m，这时发现相遇点已经距离环起点走出了m，那么环中剩下的路径长度也是k-m，因此在相遇点让一个指针指向链表起点，然后两个指针一起向前进，在走出k-m步后两者会相遇，此时相遇位置就是环的起点。...

2020-07-16 17:01:55 289

原创关于数位转换做点小记录

如何把一个负数直接转化成它二进制编码对应的整数（相当于有符号转无符号）python实现：用1去与这个数字的每一位，存储在一个数组中，每与一次原数字右移一位，直到为0，这样数组中就存储了整个二进制数，且位数与原二进制数对应（下标0是二进制最低位，下标1是二进制倒数第二位，以此类推）然后再用0依次与数组中每个数相或，然后0<<=1，就可以得到原数字（注意因为是左移一位，因此或的时候要从数组尾端开始循环）代码list1 = []a = 1b = -5888043print(bin(b))

2020-07-16 16:44:41 103

转载小数在内存中的存储表示

整数在内存中的存储方式比较简单，我们来看看小数在内存中的存储方式。首先，要学会十进制小数与二进制小数之间的转换。（1）二进制小数转化为十进制小数比如把二进制小数110.11转化为十进制小数，步骤如下：（2）十进制小数转化为二进制小数方法是这样的：先分别把十进制小数的整数部分和小数部分转化为二进制，然后合并即可。当然整数部分很简单，直接进行二进制转化，而小数部分就不一样了。具体做法是：用2乘十进制小数，可以得到积，将积的整数部分取出，再用2乘余下的小数部分，又得到一个积，再将积的整数部分取出，如此

2020-07-16 16:26:32 518

转载十进制浮点数转成二进制(IEEE 754 在线计算器)

IEEE 754 单精度浮点数转换在线计算器http://www.styb.cn/cms/ieee_754.php十进制小数的二进制表示：整数部分：除以2，取出余数，商继续除以2，直到得到0为止，将取出的余数逆序小数部分：乘以2，然后取出整数部分，将剩下的小数部分继续乘以2，然后再取整数部分，一直取到小数部分为零为止。如果永远不为零，则按要求保留足够位数的小数，最后一位做0舍1入。将取出的整数顺序排列。举例：22.8125 转二进制的计算过程：整数部分：除以2，商继续除以2，得到0为止，将余数

2020-07-16 16:16:56 8824

原创 isinstance() 函数

isinstance() 函数来判断一个对象是否是一个已知的类型，类似 type()。isinstance() 与 type() 区别：type() 不会认为子类是一种父类类型，不考虑继承关系。isinstance() 会认为子类是一种父类类型，考虑继承关系。如果要判断两个类型是否相同推荐使用 isinstance()。>>>a = 2>>> isinstance (a,int)True>>> isinstance (a,str)Fal

2020-07-16 10:32:11 1281

转载简单理解LSTM神经网络

递归神经网络在传统神经网络中，模型不会关注上一时刻的处理会有什么信息可以用于下一时刻，每一次都只会关注当前时刻的处理。举个例子来说，我们想对一部影片中每一刻出现的事件进行分类，如果我们知道电影前面的事件信息，那么对当前时刻事件的分类就会非常容易。实际上，传统神经网络没有记忆功能，所以它对每一刻出现的事件进行分类时不会用到影片已经出现的信息，那么有什么方法可以让神经网络能够记住这些信息呢？答案就是Recurrent Neural Networks（RNNs）递归神经网络。递归神经网络的结果与传统神经网络有

2020-07-14 12:03:41 504

转载详细介绍C++STL：unordered_map

成员函数：不得不提一下，hash_map未加入在C++11标准中。在VC中编译：1 #include <hash_map>2 using namespace stdext;3 hash_map<int ,int> myhash;在GCC中编译：1 #include <ext/hash_map>2 using namespace __gnu_cxx;3 hash_map<int ,int> myhash;既如此，还是用unordered_

2020-07-14 07:59:23 318

原创 python--lambda表达式在sort函数中的使用

lambda作为匿名函数，在python中有比较广泛的应用1.lambda表达式一般用法语法:lamda argument:expressionexample:add = lambda x, y: x+yprint(add(10, 20))#>> 302.lambda表达式在sort函数中的使用假如a是一个由元组构成的列表，对该列表进行排序时，我们需要用到参数key，也就是关键词，如下面代码所示，lambda是一个匿名函数，是固定写法；x表示匿名函数的输入，即列表中的一个元素，

2020-07-12 22:14:41 1595

原创 (int)(((int *)0)+4)的值是多少，为什么

突然有点晕这个问题，写点东西拎一下因为(int *)0是把有符号整数0强制为int *型指针这个指针的目标元素是int型，占4字节；也就是把占4字节的整数0转化成指针0x00000000。一个字节是8位2进制数，相当于2个16进制数（1个16进制数是4位2进制），即4字节占32位2进制，8位16进制。((int *)0)+4是“指针+整数”结构，这时的整数就被解释为元素个数，1个元素4字节，4个元素自然是16字节第一个指针占用0x00000000-0x00000003（一个字节8位2进制数，从00

2020-07-08 17:39:27 660

原创用最小堆找第k个数

用最小堆找第k个数，包含了堆的构建代码和寻找代码，但是效率比较低下，只能用于小规模数据建堆转自https://www.cnblogs.com/IronDukeLinux/p/10728513.htmldef sift(self,li,low,high): # low是根节点所在位置的下标，high是要调整的树的最后一个元素的下标（用于判断是否结束调整） tmp = li[low] # 根节点的值存起来 i = low # 根节点下标 j = 2 * i + 1 # 根节点

2020-07-08 12:32:44 218

原创判断一个链表是否是回文链表

题目描述：判断一个链表是否是回文链表（如何能达到时间复杂度为O(n)的同时空间复杂度为O(1)）方法：借鉴“判断链表是否有环”思想利用快慢指针法找到链表中点，然后以中点为新链表起点，将后半部分后半部分链表反转，分别再从头、中点遍历判断是否相等，该方法时间复杂度O(n)、空间复杂度O(1)。将整个过程分解成三个函数：查找链表中点函数、反转链表函数和比较函数...

2020-07-05 18:27:29 158

原创折木棍

在你的面前从左到右摆放着n根长短不一的木棍，你每次可以折断一根木棍，并将折断后得到的两根木棍一左一右放在原来的位置（即若原木棍有左邻居，则两根新木棍必须放在左邻居的右边，若原木棍有右邻居，新木棍必须放在右邻居的左边，所有木棍保持左右排列）。折断后的两根木棍的长度必须为整数，且它们之和等于折断前的木棍长度。你希望最终从左到右的木棍长度单调不减，那么你需要折断多少次呢？输入描述：第一行是一个数n，表示开始时有多少根木棍(1<=n<=3000)第二行有n个数，从第1个到第n个分别表示从左到右的木棍

2020-07-05 18:23:42 596

原创 100 盏灯，全部关闭，第一人全部打开（亮）

100 盏灯，全部关闭，第一人全部打开（亮），第二个人隔一个按开关（2、4、6、8、10），第三个人隔 2 个按开关（3、6、9、12），以此类推，第 100 人路过时有几盏灯亮着？根据题意简单实现。不知道对不对。。nums = [1 for _ in range(100)]mark = 1i = 2while i <=100: while mark<100: if nums[mark]:nums[mark]=0 else:nums[mark]

2020-07-05 12:20:21 579

原创找出字符串的所有子字符串

前缀树实现，遍历字符串。把字符串中的每一个字符都视为前缀，用一个前缀树保存以每一个字符为开头的字符串（举例为‘abbc’）。然后遍历前缀树，把每个子树的每一层都作为一个字符串输出即可。import copyclass TrieNode(object): def __init__(self,word): self.word = word self.dict1 = {}str1 = 'abbc'str1 = list(str1)root = TrieNode(N

2020-07-05 12:01:55 1557

转载面试题：第一行数字0 1 2...9，第二行数字分别是第一行数字在下面出现的次数

题目：0 1 2 3 4 5 6 7 8 9要求在横线上填入数字，使得每个数字分别是上面对应数字在下面出现的次数分析：设下面数字分别为 n0 n1 n2 n3…n9，表示对应数字出现的次数则n0 + n1 + n2+…+n9 = 10 A式（下面一行所有次数出现的和加起来要为10，因为总共只有10个横线）1n1 + 2n2 + 3n3+…+9n9 = 10 B式（k×nk表示第nk个数出现了k次，总共只有10个空间，因此出现次数加起来也要等于10.）由B式知：0<=n5~n9&lt

2020-07-05 11:31:00 1947

原创一个数组有正数有负数，调整数组中的数使得正负交替

一个数组有正数有负数，调整数组中的数使得正负交替例：[-3, 6, 7, -4] ->[6, -3, 7, -4]思路：采用两个指针，一个指向偶数位，记为a；一个指向奇数位，记为b；我们规定偶数位只能是正数，奇数位只能是负数；则当a指到负数时停下，b指到正数时停下，然后交换两者的值，在分别向后查找，直到有一个指针超出数组长度。则当原数组一定可以调整为正负交替的前提下，用双指针可以完成调整...

2020-07-05 11:27:14 2655 1

原创面试题：一副从1到n的牌，每次从牌堆顶取一张放桌子上，再取一张放牌堆底，直到手中没牌，最后桌子上的牌是从1到n有序，设计程序，输入n，输出牌堆的顺序数组

面试题：一副从1到n的牌，每次从牌堆顶取一张放桌子上，再取一张放牌堆底，直到手中没牌，最后桌子上的牌是从1到n有序，设计程序，输入n，输出牌堆的顺序数组思路如下：由题意可知存在两种操作，1.摸牌；2.放牌；且两种操作交替进行，直到手牌为空。因此可以将摸牌操作是为偶数，放牌操作视为奇数，设置一个标记量，当标记为偶数的时候摸牌，标记为奇数的时候放牌，从而有了大体的操作思路。我们假设现在拿到的是最开始时候的有序牌堆，用每张牌的位置为牌编号，即为1-n号牌（在程序中用0~n-1实现），然后设置刚才提到的标记量从

2020-07-04 19:43:12 1558

转载海量数据处理之Bloom Filter详解

前言本博客内曾已经整理过十道海量数据处理面试题与十个方法大总结。接下来，本博客内会重点分析那些海量数据处理的方法，并重写十道海量数据处理的面试题。如果有任何问题，欢迎不吝指正。谢谢。一、什么是Bloom FilterBloom Filter是一种空间效率很高的随机数据结构，它的原理是，当一个元素被加入集合时，通过K个Hash函数将这个元素映射成一个位阵列（Bit array）中的K个点，把它们置为1。检索时，我们只要看看这些点是不是都是1就（大约）知道集合中有没有它了：如果这些点有任何一个0，则被检索

2020-07-03 09:41:28 227

转载给40亿个不重复的unsigned int的整数，没排过序的，然后再给一个数，bitmap解法

总共有410^9个数字，如果直接放在内存中，需要的内存量是410^9*4bytes(一个unsigned int为4bytes) ~= 16GBytes内存,用bitmap表示就是4x10**9bits~=512MBytes=2^32 = 4 294 967 296 ，所以索性就分配512M内存，然后依次将这个40亿不重复的数字添加到bitmap中，默认为0，添加后为1。最后直接判断要查找的数字的bitmap值，如果为0，则表示没有，如果为1，则表示有。C++代码，用char型（每个char占用1字节

2020-07-02 16:50:28 639

原创将多个集合合并成没有交集的集合

方法：hash表+并查集建立一个hash表，key为集合元素，value为元素出现的集合，（或者用链表实现也可，因为链表构造比较麻烦所以偷懒了。）同时建立一个子hash，作用是建立当前元素所在集合与元素第一次出现的集合之间的关系，key为元素当前的集合，value为元素第一次出现的集合。这样通过遍历，就建立起了一个并查集结构，将所有有交集的元素指向同一个集合中。然后建立一个列表，列表下标为集合编号，下标对应元素为并查集的根集合。通过子hash，汇总各集合对应的根集合，并将其更新到列表中。然后根据列表记录

2020-07-02 16:50:19 667 2

原创快速排序代码备份

# def kuaipai(a,b):# if a>=b:return None# i = a# j = b# temp = list1[i]# while i!=j:# while list1[j]>=temp and i!=j:j-=1# list1[i],list1[j] = list1[j],list1[i]# while list1[i]<=temp and i!=j:i+=1

2020-07-02 16:50:13 58

原创从2.5亿个数字里面找出不重复的数字的个数的bitmap的解法思路

2.5E个整数（认为无符号，取值范围为0~232）一共需要232*2bit=1G内存。与40亿个数中找是否存在类似，40E题目是每个数占一个bit，一个字节可以放8个数，位置为value//8,偏移为value%8。因为重复与否需要2个bit位来表示，00表示未出现，01表示出现一次，10表示出现多次，11表示无意义。因此1个字节放4个数，位置为value//4，偏移为（value%4）x2（一个数需要2个bit位）按照40E题目中方法读入每个数进行处理，读入数字后先看高位，高位为1则跳过，高位为0则根

2020-07-02 16:49:53 644

weixin_43955216的博客