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 448是一对题目。 /* …

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-x); 要求in-place的做法的话，其实是若干长度为4的环，保护一个节点，然后顺次做就好了。 然后对于那些标记已经做过选旋转的问题，实际上没有必要进行标记。 对于偶数，只需要处理 左上角hf * hf个,奇数只需要处理左上角hf*(hf-1)个。 其中hf = …

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分05秒 File Name :54.cpp ************************************************ */ class Solution { …

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日 星期二 19时33分51秒 File Name :55.cpp …

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 …

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 ************************************************ */ class Solution { public: int …

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] …

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. 数字三角形。。。。从坐上到右下问最短路径。。每次只能向下或者向右。。。 wa了一次。。。是因为边界值赋值成了0.。。求最短路径显然因为赋值成inf才对orz..果然傻了。。 简单的dp我们简单的A. 顺便吐 …

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 …

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: …