Skip to content

Instantly share code, notes, and snippets.

View panyan928's full-sized avatar

panyan928

View GitHub Profile
@panyan928
panyan928 / MajorityNumber.cpp
Last active May 15, 2019 03:09
找数组中出现次数大于一半的数字
/*
快排的思想,找到中位数上的数字,当数字左边数均小于,右边数均大于,位置在中间时,则是majority
*/
class Solution {
public:
int majorityElement(vector<int>& nums) {
int length = nums.size();
int low = 0;
int high = length - 1;
while (low <= high) {
@panyan928
panyan928 / heap.py
Created May 13, 2019 12:49
最小堆排序找topK
# 构建小顶堆跳转
def sift(li, low, higt):
tmp = li[low]
i = low
j = 2 * i + 1
while j <= higt: # 情况2:i已经是最后一层
if j + 1 <= higt and li[j + 1] < li[j]: # 右孩子存在并且小于左孩子
j += 1
if tmp > li[j]:
li[i] = li[j]
@panyan928
panyan928 / leetcode4.c
Created May 9, 2019 13:47
median of two sorted array
/*
median of two sorted array
Example 1:
nums1 = [1, 3]
nums2 = [2]
The median is 2.0
Example 2:
@panyan928
panyan928 / 01knapsack.py
Created April 3, 2019 07:16
DynamicProgramming
va = '51 94 66 55 81 99 79 12 14 32 36 88 65 79 62 37 47 13 93 77 100 26 44 66 73 71 74 27 6 43 16 50 7 65 3 58 7 90 99 60 84 54 68 45 28 5 43 77 47 68 9 83 66 20 84 67 4 70 90 80 11 72 54 63 9 91 43 44 36 89 60 92 70 13 66 43 45 20 32 22 61 94 25 79 27'
wt = '6 89 12 23 22 72 2 25 47 40 51 93 15 49 85 43 88 75 96 72 72 26 90 46 17 69 74 73 7 25 35 27 7 19 77 53 11 21 20 32 39 45 24 19 54 94 85 9 38 19 40 37 40 53 62 32 47 20 19 51 90 5 89 50 68 63 59 8 64 16 24 51 13 37 76 63 68 32 12 18 12 60 45 39 64'
N = len(wt.split()) ## 物品数量
wt = list(map(int, wt.split())) # 重量
va = list(map(int, va.split())) # 价值
V = 50 # 背包最大容量
F = [0 for i in range(V+1)]
for i in range(N):
for v in range(V, 0, -1):
if wt[i] <= v:
@panyan928
panyan928 / micro4.py
Created April 2, 2019 07:58
microsoft_sample
class UserMainCode(object):
@classmethod
def series(cls, input1, input2, input3):
cls.count=0
def dfs(now, sum, num):
print(now)
if num == input2 - 1:
if now[-1] < input1 - sum <= now[-1] + input3:
print(now, sum, num)
cls.count += 1
@panyan928
panyan928 / snake.py
Created March 20, 2019 13:02
snake.py
#!/usr/bin/env python
# -*- coding:utf-8 -*-
import collections
line = 'xxsrR^Aas'
dic = collections.Counter(line)
print(dic)
start = 0
# Definition for a binary tree node.
# class TreeNode(object):
# def __init__(self, x):
# self.val = x
# self.left = None
# self.right = None
class Solution(object):
paths = list()
path = list()