Posts

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.

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.

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?

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

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.

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.

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).

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

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/* *********************************************** 2Author :111qqz 3Created Time :2017年04月05日 星期三 16时49分57秒 4File Name :106.cpp 5************************************************ */ 6/** 7 * Definition for a binary tree node. 8 * struct TreeNode { 9 * int val; 10 * TreeNode *left; 11 * TreeNode *right; 12 * TreeNode(int x) : val(x), left(NULL), right(NULL) {} 13 * }; 14 */ 15class Solution { 16public: 17 TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder) { 18 int siz = inorder.size(); 19 if (siz==0) return NULL; 20 int rt = postorder[siz-1]; 21 int pos = -1; 22 for ( int i = 0 ; i < siz; i++) 23 { 24 if (inorder[i]==rt) 25 { 26 pos = i ; 27 break; 28 } 29 } 30 TreeNode *head = new TreeNode(rt); 31 vector<int>in,post; 32 for ( int i = 0 ; i < pos ; i++) 33 { 34 in.push_back(inorder[i]); 35 post.push_back(postorder[i]); 36 } 37 head->left = buildTree(in,post); 38 in.clear(); 39 post.clear(); 40 for ( int i = pos + 1 ; i < siz ; i++) 41 { 42 in.push_back(inorder[i]); 43 post.push_back(postorder[i-1]); 44 } 45 head->right = buildTree(in,post); 46 return head; 47 } 48};

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.

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.

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.

2748: [HAOI2012]音量调节 # Time Limit: 3 Sec Memory Limit: 128 MB Submit: 1814 Solved: 1148 [Submit][Status][Discuss]

2257: [Jsoi2009]瓶子和燃料 # Time Limit: 10 Sec Memory Limit: 128 MB Submit: 1246 Solved: 756 [Submit][Status][Discuss]

1012: [JSOI2008]最大数maxnumber # Time Limit: 3 Sec Memory Limit: 162 MB Submit: 9717 Solved: 4244 [Submit][Status][Discuss]

#1197 : Give My Text Back # 时间限制：10000ms

….拿到offer结果被人同情得问…“你怎么这么惨”…还不止被一个人这样说………

头条校招（今日头条2017秋招真题） 题目描述 头条的2017校招开始了！为了这次校招，我们组织了一个规模宏大的出题团队。每个出题人都出了一些有趣的题目，而我们现在想把这些题目组合成若干场考试出来。在选题之前，我们对题目进行了盲审，并定出了每道题的难度系数。一场考试包含3道开放性题目，假设他们的难度从小到大分别为a, b, c，我们希望这3道题能满足下列条件：

给定 x, k ，求满足 x + y = x | y 的第 k 小的正整数 y 。 | 是二进制的或(or)运算，例如 3 | 5 = 7。