111qqz的小窝

老年咸鱼冲锋!

leetcode 442. Find All Duplicates in an Array(找出出现两次的元素)

Given an array of integers, 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements that appear twice in this array. Could you do it without extra space and in O(n) runtime? 思路:还是一个映射,如果某个位置要映射的时候已经为负

leetcode 48. Rotate Image (旋转方阵(in place))

You are given an n x n 2D matrix representing an image. Rotate the image by 90 degrees (clockwise). Follow up: Could you do this in-place? 题意:给一个n*n的方阵,要求顺时针旋转90度。 思路:(x,y)->(y,n-1-

leetcode 54. Spiral Matrix (矩阵蛇形取数)

Given a matrix of m x n elements (m rows, n columns), return all elements of the matrix in spiral order. 思路:。。。再次让我回想起高一的暑假。。。。 /* *********************************************** Author :111qqz Created Time :2017年04月11日 星期二 19时42分

leetcode 55. Jump Game (dp)

Given a collection of intervals, merge all overlapping intervals. For example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18]. 思路:dp[i]表示能否到达位置i…无脑dp即可。。。 /* *********************************************** Author :111qqz Created Time :2017年04月11日 星期二

leetcode 56. Merge Intervals (模拟,求相交区间)

Given a collection of intervals, merge all overlapping intervals. For example, Given [1,3],[2,6],[8,10],[15,18], return [1,6],[8,10],[15,18]. 思路:扫一遍即可。。 /* *********************************************** Author :111qqz Created Time :2017年04月11日 星期二 19时15分30秒 File Name :56.cpp ************************************************ */ /** * Definition for an interval. * struct Interval {

leetocde 59. Spiral Matrix II (模拟)

Given an integer n, generate a square matrix filled with elements from 1 to _n_2 in spiral order. 思路:仿佛回到高一的那个暑假。。。 /* *********************************************** Author :111qqz Created Time :2017年04月11日 星期二 18时52分15秒 File Name :59.cpp ************************************************ */

leetocde 63. Unique Paths II

Follow up for “Unique Paths”: Now consider if some obstacles are added to the grids. How many unique paths would there be? An obstacle and empty space is marked as 1 and 0 respectively in the grid. For example, There is one obstacle in the middle of a 3x3 grid as illustrated below. [ [0,0,0], [0,1,0], [0,0,0] ] The total number of unique paths is 2. 题意:从

leetcode 64. Minimum Path Sum (二维dp)

Given a m x n grid filled with non-negative numbers, find a path from top left to bottom right which minimizes the sum of all numbers along its path. Note: You can only move either down or right at any point in time. 数字三角形。。。。从坐上到右下问最短路径。。每次只能向

leetcode 73. Set Matrix Zeroes (矩阵置0,乱搞)

Given a m x n matrix, if an element is 0, set its entire row and column to 0. Do it in place. click to show follow up. **Follow up:**Did you use extra space? A straight forward solution using O(m__n) space is probably a bad idea. A simple improvement uses O(m + n) space, but still not the best solution. Could you devise a constant space solution? 直接放

leetcode 238. Product of Array Except Self (乱搞)

Given an array of n integers where n > 1, nums, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i]. Solve it without division and in O(n). For example, given [1,2,3,4], return [24,12,8,6]. Follow up: Could you solve it with constant space complexity? (Note: The output array does not count as extra space for the purpose of space complexity

leetcode 79. Word Search (dfs)

Given a 2D board and a word, find if the word exists in the grid. The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once. 思路:dfs即可。记得要回溯一下…

leetcode 80 Remove Duplicates from Sorted Array II (有序数组去除重复元素)

Follow up for “Remove Duplicates”: What if duplicates are allowed at most twice? For example, Given sorted array nums = [1,1,1,2,2,3], Your function should return length = 5, with the first five elements of nums being 1, 1, 2, 2 and 3. It doesn't matter what you leave beyond the new length. Subscribe to see which companies asked this question. 题意:一个有序数组,

leetcode 81. Search in Rotated Sorted Array II (有重复元素的旋转数组找给定值)

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). Write a function to determine if a given target is in the array. The array may contain duplicates. 好像阿里一面的时候问过。。。 思路:肯定

leetcode 289. Game of Life (模拟)

According to the Wikipedia's article: “The Game of Life, also known simply as Life, is a cellular automaton devised by the British mathematician John Horton Conway in 1970.” Given a board with m by n cells, each cell has an initial state live (1) or dead (0). Each cell interacts with its eight neighbors (horizontal, vertical, diagonal) using the following four rules (taken from the above Wikipedia article): 1. Any

leetcode 90. Subsets II (枚举子集)

Given a collection of integers that might contain duplicates, nums, return all possible subsets. Note: The solution set must not contain duplicate subsets. For example, If nums = [1,2,2], a solution is: [ [2], [1], [1,2,2], [2,2], [1,2], [] ] 思路: 复习(?)一下 枚举子集的三种写法 (还有种更飘逸的&he

leetcode 287. Find the Duplicate Number (floyd判圈算法找重复元素)

Given an array nums containing n + 1 integers where each integer is between 1 and n (inclusive), prove that at least one duplicate number must exist. Assume that there is only one duplicate number, find the duplicate one. Note: 1. You **must not** modify the array (assume the array is read only). 2. You must use only constant, _O_(1) extra space. 3. Your runtime complexity should be less than

leetcode 532. K-diff Pairs in an Array (找差为k的数对)

Given an array of integers and an integer k, you need to find the number of unique k-diff pairs in the array. Here a k-diff pair is defined as an integer pair (i, j), where i and j are both numbers in the array and their absolute difference is k. Example 1: Input: [3, 1, 4, 1, 5], k = 2 Output: 2 Explanation: There are two 2-diff pairs in

leetcode 448. Find All Numbers Disappeared in an Array(寻找所有消失的元素)

Given an array of integers where 1 ≤ a[i] ≤ n (n = size of array), some elements appear twice and others appear once. Find all the elements of [1, n] inclusive that do not appear in this array. Could you do it without extra space and in O(n) runtime? You may assume the returned list does not count as extra space. Example: Input: [4,3,2,7,8,2,3,1] Output: [5,6] 思路: