↓ 跳过正文
111qqz的小窝
111qqz的小窝
  1. Posts/

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

·333 字·1 分钟
ACM 二分 Leetcode

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.

好像阿里一面的时候问过。。。

思路：肯定是二分。。。不过由于有重复元素。。。所以很恶心。。。

总的思路是。。。当发现重复元素。。并且该重复元素不是target的时候。。。缩小范围。。。

 1/* ***********************************************
 2Author :111qqz
 3Created Time :2017年04月05日 星期三 20时26分25秒
 4File Name :81.cpp
 5************************************************ */
 6
 7
 8
 9class Solution {
10
11public:
12
13    bool search(vector<int>& nums, int target) {
14	int siz = nums.size();
15	if (siz==0) return false;
16	int l = 0 ;
17	int r = siz-1;
18	while (l<=r)
19	{
20	    int mid = (l+r)>>1;
21	    if (nums[mid]==target)  return true;
22	    if (nums[l]<nums[mid])
23	    {
24		if (nums[l]<=target&&target<nums[mid])
25		    r = mid - 1;
26		else
27		    l = mid + 1;
28	    }
29	    else if (nums[mid]<nums[r])
30	    {
31		if (nums[mid]<target&&target<=nums[r]) l = mid + 1;
32		else r = mid -1;
33	    }
34	    else if (nums[l]==nums[mid]) l++;
35	    else if (nums[mid]==nums[r]) r--;   //nums[l]或nunms[r] is not the target,so remove it..重复元素最烦人了。。。
36	}
37
38	return false;
39
40    }
41
42};

相关文章

leetcode 74. Search a 2D Matrix

·183 字·1 分钟
ACM 二分 Leetcode
题目链接 题意：给一个二维数组。。。每一行每一列都分别递增。。问某个value是否出现过。。。 思路：单调。。显然二分。。。唯一的技巧是从右上角开始搜。 1/* *********************************************** 2Author :111qqz 3Created Time :2017年03月09日 星期四 19时03分07秒 4File Name :74.cpp 5************************************************ */ 6class Solution { 7 8public: 9 10 bool searchMatrix(vector<vector<int>>& matrix, int target) { 11 12 int n = matrix.size(); 13 if (n==0) return false; 14 int m = matrix[0].size(); 15 if (m==0) return false; 16 int row = 0 ; 17 int col = m-1; 18 while (col>=0&&row<n) 19 { 20 if (matrix[row][col]==target) return true; 21 else 22 if (matrix[row][col]>target) col--; 23 else row++; 24 } 25 return false; 26 27 } 28 29};

leetcode 289. Game of Life (模拟)

·1065 字·3 分钟
ACM Leetcode
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.

leetcode 90. Subsets II (枚举子集)

·266 字·1 分钟
ACM 枚举子集 Leetcode
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的。。

106. Construct Binary Tree from Inorder and Postorder Traversal(根据中序和后序遍历构建二叉树)

·206 字·1 分钟
ACM Leetcode
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};