lintcode部分刷题代码

lintcode部分刷题代码

lintcode

字符串查找

下面展示一些 内联代码片。

class Solution:"""@param source: @param target: @return: return the index"""def strStr(self, source, target):# write your code hereindex = 0if len(source) < len(target):return -1if source is None or target is None:return -1if source == target:return 0while index <= len(source)-len(target):if source[index:index+len(target)] == target:return indexif index == len(source)-len(target) and source !=target:return -1index +=1

二分查找

class Solution:"""@param nums: The integer array.@param target: Target to find.@return: The first position of target. Position starts from 0."""def binarySearch(self, nums, target):# write your code herej =-1for i in range (len(nums)):if nums[i] == target:j=ibreakif j!=-1:return jelse:return -1

数组划分

class Solution:"""@param nums: The integer array you should partition@param k: An integer@return: The index after partition"""def partitionArray(self, num, k):# write your code herei=0j=len(num)-1while i<j:while i<=j and num[j]>=k:j -= 1while i<=j and num[i]<k:i += 1if i<j:temp = num[i]num[i]=num[j]num[j]=tempi+=1j-=1return i

5. 第k大元素

下面展示一些 内联代码片。

class Solution:"""@param n: An integer@param nums: An array@return: the Kth largest element"""def kthLargestElement(self, k, nums):nums.sort()return nums[-k]

76. 最长上升子序列

中文English
给定一个整数序列，找到最长上升子序列（LIS），返回LIS的长度。

class Solution:"""@param nums: An integer array@return: The length of LIS (longest increasing subsequence)"""def longestIncreasingSubsequence(self, nums):# write your code hereif not nums:return 0dp = [1]*len(nums)for i in range(len(nums)):for j in range(i):if nums[j]<nums[i]:dp[i] = max(dp[i], dp[j]+1)return max(dp)

4. 丑数 II

设计一个算法，找出只含素因子2，3，5 的第 n 小的数

class Solution:def nthUglyNumber(self, n):# write your code hereif n<7:return ns = [1]index2 = 0index3 = 0index5 = 0while True:num = min(2 * s[index2], 3 * s[index3], 5 * s[index5])if num == 2 * s[index2]:index2 += 1if num == 3 * s[index3]:index3 += 1if num == 5 * s[index5]:index5 += 1s.append(num)if len(s) == n:return num

// An highlighted block
var foo = 'bar';

// An highlighted block
var foo = 'bar';

// An highlighted block
var foo = 'bar';

// An highlighted block
var foo = 'bar';