其他

二进制中1的个数

题目

输入一个整数，输出该数二进制表示中1的个数。其中负数用补码表示。

思路

一个二进制数1100，从右边数起第三位是处于最右边的一个1。
减去1后，第三位变成0，它后面的两位0变成了1，而前面的1保持不变，因此得到的结果是1011.
我们发现减1的结果是把最右边的一个1开始的所有位都取反了。
这个时候如果我们再把原来的整数和减去1之后的结果做与运算，从原来整数最右边一个1那一位开始所有位都会变成0。
如1100&1011=1000.也就是说，把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0.
那么一个整数的二进制有多少个1，就可以进行多少次这样的操作。

代码

class Solution:
    def NumberOf1(self, n):
        # write code here
        count = 0
        if n<0:
            n = n & 0xffffffff
        while n:
            count += 1
            n = n & (n-1)
        return count

数值的整数次方

题目

给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。

保证base和exponent不同时为0

思路

当指数为负数的时候，可以先对指数求绝对值，然后算出次方的结果之后再取倒数。如果底数为0，则直接返回0。此时的次方在数学上是没有意义的。

除此之外，我们要注意：由于计算机表示小数（包括float和double型小数）都有误差，我们不能直接用等号（==）判断两个小数是否相等。如果两个小数的差的绝对值很小，比如小于0.0000001，就可以认为它们相等。

代码

class Solution:
    def Power(self, base, exponent):
        # write code here
        flag = 0
        result = 1
        if base == 0:
            return False
        if exponent < 0:
            flag = 1
        for i in range(abs(exponent)):
            result *= base
        if flag == 1:
            result = 1 / result
        return result

顺时针打印矩阵

题目

输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.

思路

将结果存入vector数组，从左到右，再从上到下，再从右到左，最后从下到上遍历。

代码

class Solution:
    # matrix类型为二维列表，需要返回列表
    def printMatrix(self, matrix):
        # write code here
        rows = len(matrix)
        cols = len(matrix[0])
        result = []
        if rows == 0 and cols == 0:
            return result
        left, right, top, buttom = 0, cols - 1, 0, rows - 1
        while left <= right and top <= buttom:
            for i in range(left, right+1):
                result.append(matrix[top][i])
            for i in range(top+1, buttom+1):
                result.append(matrix[i][right])
            if top != buttom:
                for i in range(left, right)[::-1]:
                    result.append(matrix[buttom][i])
            if left != right:
                for i in range(top+1, buttom)[::-1]:
                    result.append(matrix[i][left])
            left += 1
            top += 1
            right -= 1
            buttom -= 1
        return result
    
    def matrix(target):
        num = target ** 2
        left, right, top, bottom = 0, target-1, 0, target-1
        res = [ [0 for col in range(target)] for row in range(target)]
        each = 1
        while left <= right and top <= bottom and each <= num:
            for i in range(left, right+1):
                res[top][i] = each
                each += 1
            for i in range(top+1, bottom+1):
                res[i][right] = each
                each += 1
            if top != bottom:
                for i in range(left, right)[::-1]:
                    res[bottom][i] = each
                    each += 1
            if left != right and each <= num:
                for i in range(top+1, bottom)[::-1]:
                    res[i][left] = each
                    each += 1
            top += 1
            left += 1
            bottom -= 1
            right -= 1
        for i in range(len(res)):
            print("\t".join('%s' %id for id in res[i]))

最小的k个数

题目

输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4,。

思路

一种方法，用数组来存储排序的最小k个数

另一种方法是使用最大堆

代码

class Solution:
    # 用数组的方法, 用数组来存储排序的最小k个数，插入的时间复杂度比较大
    def GetLeastNumbers_Solution1(self, tinput, k):
        if len(tinput) < k:
            return []
        tmp = sorted(tinput[:k])
        for each in tinput[k:]:
            index = k - 1
            flag = False
            while index >= 0 and tmp[index] > each:
                index -= 1
                flag = True
            if flag == True:
                tmp.insert(index+1, each)
                tmp.pop()
        return tmp
    
    def HeadAdjust(self, input_list, parent, length):
        # 获取堆的根
        temp = input_list[parent]
        # 获取根孩子的坐标
        child = 2 * parent + 1
        while child < length:
            # 寻找最大孩子的坐标
            if child + 1 < length and input_list[child] < input_list[child+1]:
                child += 1
            # 如果入参的大根发现比他小的值，便停止搜索
            if temp >= input_list[child]:
                break
            # 如果当前根小于孩子节点
            # 将根节点换成孩子节点
            input_list[parent] = input_list[child]
            # 更新根节点位置
            parent = child
            # 更新孩子节点位置
            child = 2 * parent + 1
        input_list[parent] = temp
        
    def GetLeastNumbers_Solution(self, tinput, k):
        # write code here
        res = []
        length = len(tinput)
        change = True
        if length <= 0 or k <= 0 or k > length:
            return res
        res = tinput[:k]
         
        for i in range(k, length+1):
            if change == True:
                #将初始待排序关键字序列(R1,R2....Rn)构建成大顶堆，此堆为初始的无须区；
                #将堆顶元素R[1]与最后一个元素R[n]交换，此时得到新的无序区(R1,R2,......Rn-1)和新的有序区(Rn),
                #且满足R[1,2...n-1]<=R[n]; 
                #由于交换后新的堆顶R[1]可能违反堆的性质，因此需要对当前无序区(R1,R2,......Rn-1)调整为新堆，
                #然后再次将R[1]与无序区最后一个元素交换，得到新的无序区(R1,R2....Rn-2)和新的有序区(Rn-1,Rn)。
                #不断重复此过程直到有序区的元素个数为n-1，则整个排序过程完成。
                for j in range(0, k//2+1)[::-1]:
                    self.HeadAdjust(res, j, k)
                for j in range(1, k)[::-1]:
                    res[0], res[j] = res[j], res[0]
                    self.HeadAdjust(res, 0, j)
                chage = False
            if i != length and res[k-1] > tinput[i]:
                res[k-1] = tinput[i]
                chage = True
        return res

整数中1出现的次数

题目

求出1-13的整数中1出现的次数,并算出100-1300的整数中1出现的次数？为此他特别数了一下1-13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。

思路

设定整数点（如1、10、100等等）作为位置点i（对应n的各位、十位、百位等等），
分别对每个数位上有多少包含1的点进行分析。

根据设定的整数位置，对n进行分割，分为两部分，高位n/i，低位n%i
当i表示百位，且百位对应的数>=2,如n=31456,i=100，则a=314,b=56，此时百位为1的次数有a/10+1=32（最高两位0-31），
每一次都包含100个连续的点，即共有(a/10+1)*100个点的百位为1
当i表示百位，且百位对应的数为1，如n=31156,i=100，则a=311,b=56，此时百位对应的就是1，
则共有a/10(最高两位0-30)次是包含100个连续点，当最高两位为31（即a=311），本次只对应局部点00-56，共b+1次，
所有点加起来共有（a/10*100）+(b+1)，这些点百位对应为1
当i表示百位，且百位对应的数为0,如n=31056,i=100，则a=310,b=56，此时百位为1的次数有a/10=31（最高两位0-30
综合以上三种情况，当百位对应0或>=2时，有(a+8)/10次包含所有100个点，还有当百位为1(a%10==1)，需要增加局部点b+1

#之所以补8，是因为当百位为0，则a/10==(a+8)/10，当百位>=2，补8会产生进位位，效果等同于(a/10+1)

代码

class Solution:
    def NumberOf1Between1AndN_Solution(self, n):
        # write code here
        count = 0
        i = 1
        while i <= n:
            a = n / i
            b = n % i
            count += (a+8)/10 * i + (a%10 == 1)*(b+1)
            i *= 10
  
        return count

丑数

题目

把只包含质因子2、3和5的数称作丑数（Ugly Number）。例如6、8都是丑数，但14不是，因为它包含质因子7。 习惯上我们把1当做是第一个丑数。求按从小到大的顺序的第N个丑数。

思路

所谓的一个数m是另一个数n的因子，是指n能被m整除，也就是n%m==0。
根据丑数的定义，丑数只能被2、3和5整除。根据丑数的定义，丑数应该是另一个丑数乘以2、3或者5的结果（1除外）。
因此我们可以创建一个数组，里面的数字是排好序的丑数，每一个丑数都是前面的丑数乘以2、3或者5得到的。

这个思路的关键问题在于怎样保证数组里面的丑数是排好序的。对乘以2而言，肯定存在某一个丑数T2，
排在它之前的每一个丑数乘以2得到的结果都会小于已有最大的丑数，在它之后的每一个丑数乘以乘以2得到的结果都会太大。
我们只需要记下这个丑数的位置，同时每次生成新的丑数的时候，去更新这个T2。对乘以3和5而言，也存在着同样的T3和T5\

重点: 每种质因子的丑数乘以对应的质因子还是丑数

代码

class Solution:
    def GetUglyNumber_Solution(self, index):
        # write code here
        if index < 7:
            return index
        res = [1, 2, 3, 4, 5, 6]
        t2, t3, t5 = 3, 2, 1
        for i in range(6, index):
            res.append(min(res[t2] * 2, min(res[t3] * 3, res[t5] * 5)))
            while res[t2] * 2 <= res[i]:
                t2 += 1
            while res[t3] * 3 <= res[i]:
                t3 += 1
            while res[t5] * 5 <= res[i]:
                t5 += 1
        return res[index - 1]

和为S的两个数字

题目

输入一个递增排序的数组和一个数字S，在数组中查找两个数，使得他们的和正好是S，如果有多对数字的和等于S，输出两个数的乘积最小的。

思路

对于一个数组，我们可以定义两个指针，一个从左往右遍历（pleft），另一个从右往左遍历（pright）。首先，我们比较第一个数字和最后一个数字的和curSum与给定数字sum，如果curSum < sum，那么我们就要加大输入值，所以，pleft向右移动一位，重复之前的计算；如果curSum > sum，那么我们就要减小输入值，所以，pright向左移动一位，重复之前的计算；如果相等，那么这两个数字就是我们要找的数字，直接输出即可。

这么做的好处是，也保证了乘积最小。

代码

class Solution:
    def FindNumbersWithSum(self, array, tsum):
        # write code here
        if len(array) <= 1:
            return []
        left, right = 0, len(array)-1
        while left < right:
            if array[left] + array[right] == tsum:
                return array[left], array[right]
            elif array[left] + array[right] < tsum:
                left += 1
            else:
                right -= 1
        return []

扑克牌的顺子

题目

LL今天心情特别好,因为他去买了一副扑克牌,发现里面居然有2个大王,2个小王(一副牌原本是54张^_^)…他随机从中抽出了5张牌,想测测自己的手气,看看能不能抽到顺子,如果抽到的话,他决定去买体育彩票,嘿嘿！！“红心A,黑桃3,小王,大王,方片5”,“Oh My God!”不是顺子…..LL不高兴了,他想了想,决定大\小 王可以看成任何数字,并且A看作1,J为11,Q为12,K为13。上面的5张牌就可以变成“1,2,3,4,5”(大小王分别看作2和4),“So Lucky!”。LL决定去买体育彩票啦。 现在,要求你使用这幅牌模拟上面的过程,然后告诉我们LL的运气如何， 如果牌能组成顺子就输出true，否则就输出false。为了方便起见,你可以认为大小王是0。

思路

满足如下条件才可以认为是顺子：
输入数据个数为5；
输入数据都在0-13之间；
没有相同的数字；
最大值与最小值的差值不大于5。
PS：大小王可以当成任意数。

这里可以使用一个技巧，即利用一个flag记录每个数字出现的次数。

代码

class Solution:
    def IsContinuous(self, numbers):
        # write code here
        if len(numbers) != 5:
            return False
        max_num = None
        min_num = None
        # 用来保存所有数对应的 1<<num 结果
        flag = 0
        for number in numbers:
            if number < 0 or number > 13:
                return False
            # 如果是大小王不用统计
            if number == 0:
                continue
            # 如果数据重复，则直接返回False
            if (flag >> number) & 1 == 1:
                return False
            # 与当前flag想或，记录当前数的唯一标记
            flag |= 1 << number
            
            if number < min_num or max_num is None:
                min_num = number
            if number > max_num or max_num is None:
                max_num = number
            if max_num - min_num >= 5:
                return False
        return True

孩子们的游戏

题目

每年六一儿童节,牛客都会准备一些小礼物去看望孤儿院的小朋友,今年亦是如此。HF作为牛客的资深元老,自然也准备了一些小游戏。其中,有个游戏是这样的:首先,让小朋友们围成一个大圈。然后,他随机指定一个数m,让编号为0的小朋友开始报数。每次喊到m-1的那个小朋友要出列唱首歌,然后可以在礼品箱中任意的挑选礼物,并且不再回到圈中,从他的下一个小朋友开始,继续0…m-1报数….这样下去….直到剩下最后一个小朋友,可以不用表演,并且拿到牛客名贵的“名侦探柯南”典藏版(名额有限哦!!^_^)。请你试着想下,哪个小朋友会得到这份礼品呢？(注：小朋友的编号是从0到n-1)

如果没有小朋友，请返回-1

思路

用数学归纳法推导出递推公式，设有n个人（编号0-(n-1))，
从0开始报数，报到(m-1)的退出，剩下的人继续从0开始报数。
令f[i]表示i个人时最后胜利者的编号，则有递推公式：f[1]=0;
可用数学归纳求出递推公式F(N)=(F(N-1)+m)%n

代码

class Solution:
    def LastRemaining_Solution(self, n, m):
        # write code here
        if n == 0:
            return -1
        s = 0
        for i in range(2, n+1):
            s = (s+m) % i
        return s

求1+2+3+….+n

题目

求1+2+3+…+n，要求不能使用乘除法、for、while、if、else、switch、case等关键字及条件判断语句（A?B:C）。

思路

递归

代码

class Solution:
    def Sum_Solution(self, n):
        # write code here
        ans = n
        return ans and ans + self.Sum_Solution(n-1)

不用加减乘除的加法

题目

写一个函数，求两个整数之和，要求在函数体内不得使用+、-、*、/四则运算符号。

思路

首先看十进制是如何做的： 5+7=12，

可以使用三步走：

第一步：相加各位的值，不算进位，得到2。
第二步：计算进位值，得到10. 如果这一步的进位值为0，那么第一步得到的值就是最终结果。
第三步：重复上述两步，只是相加的值变成上述两步的得到的结果2和10，得到12。

同样我们可以三步走的方式计算二进制值相加： 5-101，7-111

第一步：相加各位的值，不算进位，得到010，二进制每位相加就相当于各位做异或操作，101^111。
第二步：计算进位值，得到1010，相当于各位做与操作得到101，再向左移一位得到1010，(101&111)<<1。
第三步：重复上述两步， 各位相加 010^1010=1000，进位值为100=(010&1010)<<1。
继续重复上述两步：1000^100 = 1100，进位值为0，跳出循环，1100为最终结果。

代码

class Solution:
    def Add(self, num1, num2):
        # write code here

        MAX = 0x7fffffff
        mask = 0xffffffff
        while num2 != 0:
            num1, num2 = (num1 ^ num2), ((num1 & num2) << 1)
            num1 = num1 & mask
            num2 = num2 & mask
        return num1 if num1 <= MAX else ~(num1 ^ mask)

字符流中的第一个不重复字符

题目

请实现一个函数用来找出字符流中第一个只出现一次的字符。例如，当从字符流中只读出前两个字符”go”时，第一个只出现一次的字符是”g”。当从该字符流中读出前六个字符“google”时，第一个只出现一次的字符是”l”。

思路

这道题还是很简单的。将字节流保存起来，通过哈希表统计字符流中每个字符出现的次数，
顺便将字符流保存在string中，然后再遍历string，从哈希表中找到第一个出现一次的字符

代码

class Solution:
    def __init__(self):
        self.s = ''
        self.count = {}
    # 返回对应char
    def FirstAppearingOnce(self):
        # write code here
        length = len(self.s)
        for i in range(length):
            if self.count[self.s[i]] == 1:
                return self.s[i]
        return '#'
    def Insert(self, char):
        # write code here
        self.s += char
        if char not in self.count:
            self.count[char] = 1
        else:
            self.count[char] += 1

数据流中的中位数

题目

如何得到一个数据流中的中位数？如果从数据流中读出奇数个数值，那么中位数就是所有数值排序之后位于中间的数值。如果从数据流中读出偶数个数值，那么中位数就是所有数值排序之后中间两个数的平均值。我们使用Insert()方法读取数据流，使用GetMedian()方法获取当前读取数据的中位数。

思路

先排序在返回

代码

class Solution:
    def __init__(self):
        self.nums = []
    def Insert(self, num):
        self.nums.append(num)
    def GetMedian(self, fuck):
        self.nums.sort()
        if len(self.nums) % 2 == 1:
            return self.nums[(len(self.nums) - 1) / 2]
        else:
            return (self.nums[len(self.nums) / 2] + self.nums[len(self.nums) / 2 - 1]) / 2.0

滑动窗口的最大值

题目

给定一个数组和滑动窗口的大小，找出所有滑动窗口里数值的最大值。例如，如果输入数组{2,3,4,2,6,2,5,1}及滑动窗口的大小3，那么一共存在6个滑动窗口，他们的最大值分别为{4,4,6,6,6,5}； 针对数组{2,3,4,2,6,2,5,1}的滑动窗口有以下6个： {[2,3,4],2,6,2,5,1}， {2,[3,4,2],6,2,5,1}， {2,3,[4,2,6],2,5,1}， {2,3,4,[2,6,2],5,1}， {2,3,4,2,[6,2,5],1}， {2,3,4,2,6,[2,5,1]}。

思路

我们可以用STL中的deque来实现，接下来我们以数组{2,3,4,2,6,2,5,1}为例，来细说整体思路。

数组的第一个数字是2，把它存入队列中。第二个数字是3，比2大，所以2不可能是滑动窗口中的最大值，

因此把2从队列里删除，再把3存入队列中。第三个数字是4，比3大，同样的删3存4。
此时滑动窗口中已经有3个数字，而它的最大值4位于队列的头部。

第四个数字2比4小，但是当4滑出之后它还是有可能成为最大值的，所以我们把2存入队列的尾部。
下一个数字是6，比4和2都大，删4和2，存6。就这样依次进行，最大值永远位于队列的头部。

但是我们怎样判断滑动窗口是否包括一个数字？应该在队列里存入数字在数组里的下标，
而不是数值。当一个数字的下标与当前处理的数字的下标之差大于或者相等于滑动窗口大小时，
这个数字已经从窗口中滑出，可以从队列中删除。

代码

class Solution:
    def maxInWindows(self, num, size):
        # 如果数组 num 不存在，则返回 []
        if not num:
            return []
        # 如果滑动窗口的大小大于数组的大小，或者 size 小于 0，则返回 []
        if size > len(num) or size <1:
            return []

        # 如果滑动窗口的大小为 1 ，则直接返回原始数组
        if size == 1:
            return num

        # 存放最大值，次大值的数组，和存放输出结果数组的初始化
        temp = [0]
        res = []

        # 对于数组中每一个元素进行判断
        for i in range(len(num)):
            # 首先判断当前最大的元素是否过期
            if i -temp[0] > size-1:
                temp.pop(0)
            # 将第 i 个元素与 temp 中的值比较，将小于 i 的值都弹出
            while (len(temp)>0 and num[i] >= num[temp [-1]]):
                temp.pop()
            # 如果现在 temp 的长度还没有达到最大规模，将元素 i 压入
            if len(temp)< size-1:
                temp.append(i)
            # 只有经过一个完整的窗口才保存当前的最大值
            if i >=size-1:
                res.append(num[temp [0]])
        return res