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.
1[ 2 [0,0,0], 3 [0,1,0], 4 [0,0,0] 5] The total number of unique paths is 2.
题意：从左上到右下的方案数，有些点不能走。
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..果然傻了。。
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?
直接放常数空间的做法。
这道题面hypereal的时候遇到过，基本思路就是用已经确定是0的位置来存储其他行和列的信息。
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 analysis.)
先来个O(n)空间的无脑解法。。。一个前缀积一个后缀积就好了。。。
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即可。记得要回溯一下…
代码实现 1/* *********************************************** 2Author :111qqz 3Created Time :2017年04月07日 星期五 14时32分54秒 4File Name :79.cpp 5************************************************ */ 6class Solution { 7 8public: 9 10 int n,m; 11 const int dx4[4]={1,-1,0,0}; 12 const int dy4[4]={0,0,-1,1}; 13 bool vis[1005][1005]; 14 int len; 15 16 bool yes( int x,int y) 17 { 18 if (x>=0&&x<=n-1&&y>=0&&y<=m-1) return true; 19 return false; 20 } 21 22 bool dfs( int x,int y,int cur,vector<vector<char> > & maze,string & st) 23 { 24// printf("x:%d y:%d cur : %d\n",x,y,cur); 25 if (cur>=len) return true; 26 for ( int i = 0 ; i < 4 ; i++) 27 { 28 int nx = x + dx4[i]; 29 int ny = y + dy4[i]; 30 if (!yes(nx,ny)) continue; 31 if (vis[nx][ny]) continue; 32 if (maze[nx][ny]!=st[cur]) continue; 33 vis[nx][ny] = true; 34 bool res = dfs(nx,ny,cur+1,maze,st); 35 if (res) return true; 36 vis[nx][ny] = false ;//好像还要回溯一下啊？ 37 } 38 return false; 39 } 40 41 bool exist(vector<vector<char>>& board, string word) { 42 n = board.size(); 43 if (n==0) return false; 44 m = board[0].size(); 45 if (m==0) return false; 46 len = word.length(); 47 cout<<"len:"<<len<<endl; 48 char beg = word[0]; 49 for ( int i = 0 ; i < n ; i++) 50 for ( int j = 0 ; j < m ; j++) 51 if (board[i][j]==beg) 52 { 53 memset(vis,false,sizeof(vis)); 54 //起点忘记打标记了。。。智力-2.。。 55 vis[i][j] = true; 56 bool ok = dfs(i,j,1,board,word); 57 cout<<"ok:"<<ok<<endl; 58 if (ok) return true; 59 } 60 return false; 61 62 63 } 64 65};
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.
题意：一个有序数组，每个元素最多出现两次，如果大于两次，把多的去掉，返回去掉后的数组长度len，以及要求数组前len是去掉那些元素之后的元素。//语死早。。看原题好了。。
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.
好像阿里一面的时候问过。。。
思路：肯定是二分。。。不过由于有重复元素。。。所以很恶心。。。
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 live cell with fewer than two live neighbors dies, as if caused by under-population. 2. Any live cell with two or three live neighbors lives on to the next generation. 3. Any live cell with more than three live neighbors dies, as if by over-population.. 4. Any dead cell with exactly three live neighbors becomes a live cell, as if by reproduction. Write a function to compute the next state (after one update) of the board given its current state.
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:
1[ 2 [2], 3 [1], 4 [1,2,2], 5 [2,2], 6 [1,2], 7 [] 8] 思路：
复习（？）一下 枚举子集的三种写法
（还有种更飘逸的…先不写了orz
这道题我用位向量法A的。。
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 `O(n2)`. 4. There is only one duplicate number in the array, but it could be repeated more than once. 思路：O(n^2)的复杂度暴力即可，说个O(n)复杂度的解法。
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:
1Input: [3, 1, 4, 1, 5], k = 2 2Output: 2 3Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5). 4Although we have two 1s in the input, we should only return the number of unique pairs. Example 2:
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] 思路：由于元素大小有限制，是在1..n之间。
#1197 : Give My Text Back # 时间限制：10000ms
单点时限：1000ms
内存限制：256MB
描述 # To prepare for the English exam Little Ho collected many digital reading materials. Unfortunately the materials are messed up by a malware.