111qqz的小窝

老年咸鱼冲锋!

leetcode 146. LRU Cache(list+unordered_map)

请实现最近最少使用缓存(Least Recently Used (LRU) cache)类,需要支持 get, set,操作。 get 操作,给出 key,获取到相应的 value (value 为非负数),如果不存在返

面试相关

随便记录一下面试中遇到的问题: 梯度下降和牛顿迭代的区别?为什么常用梯度下降? 根据wiki上的解释,从几何上说,牛顿法就是用一个二次曲面去拟合

leetcode162. Find Peak Element (O(lgn)复杂度寻找峰值)

A peak element is an element that is greater than its neighbors. Given an input array where num[i] ≠ num[i+1], find a peak element and return its index. The array may contain multiple peaks, in that case return the index to any one of the peaks is fine. You may imagine that num[-1] = num[n] = -∞. For example, in array [1, 2, 3, 1], 3 is a

leetcode 152. Maximum Product Subarray (最大连续子序列乘积,dp)

Find the contiguous subarray within an array (containing at least one number) which has the largest product. For example, given the array [2,3,-2,4], the contiguous subarray [2,3] has the largest product = 6. 思路:由于有正,有负,还有0.。。所以比最大子串之和要复杂一些。。。 dp[

leetcode 228. Summary Ranges

Given a sorted integer array without duplicates, return the summary of its ranges. For example, given [0,1,2,4,5,7], return ["0->2","4->5","7"]. 题意:把连续的数连续表示 思路:模拟。注意有负数,注意有-2147483648这种数据。 本来还想着,可能

leetcode 209. Minimum Size Subarray Sum (尺取法)

Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s. If there isn’t one, return 0 instead. For example, given the array [2,3,1,2,4,3] and s = 7, the subarray [4,3] has the minimal length under the problem constraint 思路:尺取即可。。好久没写,竟然

leetcode 229. Majority Element II (O(1)空间找出现次数大于n/3的元素)

Given an integer array of size n, find all elements that appear more than ⌊ n/3 ⌋ times. The algorithm should run in linear time and in O(1) space. 题意:给你n个数,要求找出出现此处大于n/3的。。。 思路:之前做过一个找出n个数出

leetcode 75. Sort Colors

Given an array with n objects colored red, white or blue, sort them so that objects of the same color are adjacent, with the colors in the order red, white and blue. Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively. 题意:一个数组,由0,1,2组成,现在

leetcode 11. Container With Most Water (two pointer)

Given n non-negative integers a1, a2, …, an, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water. Note: You may not slant the container and n is at least 2. 题意

leetcode 16. 3Sum Closest (k-sum问题,two pointer)

Given an array S of n integers, find three integers in S such that the sum is closest to a given number, target. Return the sum of the three integers. You may assume that each input would have exactly one solution. 思路: 排序,然后two pointer,复杂度 O(n^2) /* *********************************************** Author :111qqz Created Time

leetcode 18. 4Sum (k-sum问题,two pointer)

Given an array S of n integers, are there elements a, b, c, and d in S such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target. Note: The solution set must not contain duplicate quadruplets. 思路: O(n^2)枚举两个元素,变成2-

leetcode 15. 3Sum (k-sum问题,two pointer)

Given an array S of n integers, are there elements a, b, c in S such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero. Note: The solution set must not contain duplicate triplets. 思路:排序O(nlgn),然后枚举一个元素O(n

leetcode 216. Combination Sum III Add to List (枚举子集,限定集合大小,和为定值)

Find all possible combinations of k numbers that add up to a number n, given that only numbers from 1 to 9 can be used and each combination should be a unique set of numbers. 题意:1..9个数,从中选择k个,和为n,要求输出所有满足题意的集合。

leetcode 77. Combinations (枚举子集,限定集合大小)

Given two integers n and k, return all possible combinations of k numbers out of 1 … n. 思路:就是枚举子集,根据集合的大小剪枝。。。最后只要集合大小为k的集合 /* *********************************************** Author :111qqz Created Time :2017年04月13

leetcode 60. Permutation Sequence (求第k个排列)

The set [1,2,3,…,_n_] contains a total of n! unique permutations. By listing and labeling all of the permutations in order, We get the following sequence (ie, for n = 3): 1. `"123"` 2. `"132"` 3. `"213"` 4. `"231"` 5. `"312"` 6. `"321"` Given n and k, return the _k_th permutation sequence. Note: Given n will be between 1

leetcode 47. Permutations II (生成全排列,有重复元素)

Given a collection of numbers that might contain duplicates, return all possible unique permutations.__ 思路:和leet code 46 类似,最后用set去个重即可。。 /* *********************************************** Author :111qqz Created Time :2017年04月13日 星期四 15时00分48秒

leetcode 46. Permutations (生成全排列,无重复元素)

Given a collection of distinct numbers, return all possible permutations. 思路:调用n-1次 leetcode 31 解题报告 中提到的算法即可。。。 /* *********************************************** Author :111qqz Created Time :2017年04月13日 星期四 14时49分34秒 File Name :46.cpp ************************************************

leetcode 31. Next Permutation (in-place 生成下一个全排列)

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order). The replacement must be in-place, do not allocate extra memory. Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column. 1,2,3 → 1,3,2 3,2,1 → 1,2,3 1,1,5

leetcode 33. Search in Rotated Sorted Array (无重复数的旋转数组找定值)

Suppose an array sorted in ascending order is rotated at some pivot unknown to you beforehand. (i.e., 0 1 2 4 5 6 7 might become 4 5 6 7 0 1 2). You are given a target value to search. If found in the array return its index, otherwise return -1. You may assume no duplicate exists in the array. 思路:找规律。。。

leetcode 34. Search for a Range (二分,找到一段值为tar的区间)

Given an array of integers sorted in ascending order, find the starting and ending position of a given target value. Your algorithm’s runtime complexity must be in the order of O(log n). If the target is not found in the array, return [-1, -1]. For example, Given [5, 7, 7, 8, 8, 10] and target value 8, return [3, 4]. 思路:二分。。。 我好