Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution and you may not use the same element twice.
classSolution { public: vector<int> twoSum(vector<int>& nums, int target){ vector<int> result; unordered_map<int, int> hash; for(int i = 0; i<nums.size(); i++){ int lag = target - nums[i]; if(hash.find(lag) != hash.end()){ result.push_back(hash[lag]); result.push_back(i); break; } hash[nums[i]] = i; } return result; } };
219. Contains Duplicate II
Description:
Given an array of integers and an integer k, find out whether there are two distinct indices i and j in the array such that nums[i] = nums[j] and the absolute difference between i and j is at most k.
Given a non-empty array of integers, return the third maximum number in this array. If it does not exist, return the maximum number. The time complexity must be in O(n).
Example 1:
1 2 3 4 5
Input: [3, 2, 1]
Output: 1
Explanation: The third maximum is 1.
Example 2:
1 2 3 4 5 6
Input: [1, 2]
Output: 2
Explanation: The third maximum does not exist, so the maximum (2) is returned instead.
Example 3:
1 2 3 4 5 6
Input: [2, 2, 3, 1]
Output: 1
Explanation: Note that the third maximum here means the third maximum distinct number. Both numbers with value 2 are both considered as second maximum.
Given an array of 2n integers, your task is to group these integers into n pairs of integer, say (a1, b1), (a2, b2), …, (an, bn) which makes sum of min(ai, bi) for all i from 1 to n as large as possible.
Example 1:
1 2 3 4 5
Input: [1,4,3,2]
Output: 4 Explanation: n is 2, and the maximum sum of pairs is 4 = min(1, 2) + min(3, 4).
Note:
n is a positive integer, which is in the range of [1, 10000].
All the integers in the array will be in the range of [-10000, 10000].
解题思路：总结规律，发现已排序数组的奇数项的和就是答案，这个可以通过反证法进行证明。代码如下：
1 2 3 4 5 6 7 8 9 10 11 12
classSolution { public: intarrayPairSum(vector<int>& nums){ sort(nums.begin(), nums.end()); int sum = 0; for(int i =0; i<nums.size();i+=2){ sum += nums[i]; } return sum; } };
Given an integer array, you need to find one continuous subarray that if you only sort this subarray in ascending order, then the whole array will be sorted in ascending order, too.
You need to find the shortest such subarray and output its length.
Example 1:
1 2 3 4
Input: [2, 6, 4, 8, 10, 9, 15] Output: 5 Explanation: You need to sort [6, 4, 8, 10, 9] in ascending order to make the whole array sorted in ascending order.
Note:
Then length of the input array is in range [1, 10,000].
The input array may contain duplicates, so ascending order here means <=.
classSolution { public: intfindUnsortedSubarray(vector<int>& nums){ int length = nums.size(); int beg = -1; int end = -2; int max = nums[0]; int min = nums[length-1]; for(int i=1; i<length; i++){ max = max<nums[i]?nums[i]:max; min = min>nums[length-i-1]?nums[length-i-1]:min; if(max>nums[i]) end=i; if(min<nums[length-i-1]) beg=length-i-1; } return end-beg+1; } };
66. Plus One
Description:
Given a non-negative integer represented as a non-empty array of digits, plus one to the integer.
You may assume the integer do not contain any leading zero, except the number 0 itself.
The digits are stored such that the most significant digit is at the head of the list.
Given two sorted integer arrays nums1 and nums2, merge nums2 into nums1 as one sorted array.
Note: You may assume that nums1 has enough space (size that is greater or equal to m + n) to hold additional elements from nums2. The number of elements initialized in nums1 and nums2 are m and n respectively.
解题思路：本题是两个有序的数组，我们要利用这一点，并且有个trick：反向计算。代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
classSolution{ public: voidmerge(vector<int>& nums1, int m, vector<int>& nums2, int n){ int i = m-1; int j = n-1; int k = m+n-1; while(i>=0 && j>=0){ if(nums1[i] > nums2[j]){ nums1[k--] = nums1[i--]; }else{ nums1[k--] = nums2[j--]; } } while(j>=0){ nums1[k--] = nums2[j--]; } } }
118. Pascal’s Triangle
Description:
Given numRows, generate the first numRows of Pascal’s triangle.
Say you have an array for which the ith element is the price of a given stock on day i.
If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.
Example 1:
1 2 3 4 5
Input: [7, 1, 5, 3, 6, 4] Output: 5
max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)
Example 2:
1 2 3 4
Input: [7, 6, 4, 3, 1] Output: 0
In this case, no transaction is done, i.e. max profit = 0.
classSolution { public: intmaxProfit(vector<int>& prices){ if(prices.size() < 2){ return0; } int result = 0; int min = 0; for(int i=0; i< prices.size()-1; i++){ if(prices[i+1] > prices[i]){ if(prices[i+1]-prices[min] > result){ result = prices[i+1]-prices[min]; } }else{ if(prices[i+1] < prices[min]){ min = i+1; } } } return result; } };
112. Best Time to Buy and Sell Stock II
Description:
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (i.e., buy one and sell one share of the stock multiple times).
Note: You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Example 1:
1 2 3 4 5
Input: [7,1,5,3,6,4] Output: 7 Explanation: Buy on day 2 (price = 1) and sell on day 3 (price = 5), profit = 5-1 = 4. Then buy on day 4 (price = 3) and sell on day 5 (price = 6), profit = 6-3 = 3.
Example 2:
1 2 3 4 5 6
Input: [1,2,3,4,5] Output: 4 Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
1 2 3
Input: [7,6,4,3,1] Output: 0 Explanation: In this case, no transaction is done, i.e. max profit = 0.
classSolution { public: intmaxProfit(vector<int>& prices){ if(prices.size() < 2) return0; int result = 0; for(int i=0; i<prices.size()-1; i++){ if(prices[i+1] > prices[i]){ result += prices[i+1]-prices[i]; } } return result; } };
123. Best Time to Buy and Sell Stock III
Description:
Say you have an array for which the ith element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete at most two transactions.
**Note: **You may not engage in multiple transactions at the same time (i.e., you must sell the stock before you buy again).
Example 1:
1 2 3 4
Input: [3,3,5,0,0,3,1,4] Output: 6 Explanation: Buy on day 4 (price = 0) and sell on day 6 (price = 3), profit = 3-0 = 3. Then buy on day 7 (price = 1) and sell on day 8 (price = 4), profit = 4-1 = 3.
Example 2:
1 2 3 4 5 6
Input: [1,2,3,4,5] Output: 4 Explanation: Buy on day 1 (price = 1) and sell on day 5 (price = 5), profit = 5-1 = 4. Note that you cannot buy on day 1, buy on day 2 and sell them later, as you are engaging multiple transactions at the same time. You must sell before buying again.
Example 3:
1 2 3
Input: [7,6,4,3,1] Output: 0 Explanation: In this case, no transaction is done, i.e. max profit = 0.
Suppose you have a long flowerbed in which some of the plots are planted and some are not. However, flowers cannot be planted in adjacent plots - they would compete for water and both would die.
Given a flowerbed (represented as an array containing 0 and 1, where 0 means empty and 1 means not empty), and a number n, return if n new flowers can be planted in it without violating the no-adjacent-flowers rule.
Example 1:
1 2 3
Input: flowerbed = [1,0,0,0,1], n = 1 Output: True
Example 2:
1 2 3
Input: flowerbed = [1,0,0,0,1], n = 2 Output: False
Note:
The input array won’t violate no-adjacent-flowers rule.
The input array size is in the range of [1, 20000].
n is a non-negative integer which won’t exceed the input array size.
解题思路：根据本题题意直接作答，代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
classSolution { public: boolcanPlaceFlowers(vector<int>& flowerbed, int n){ int count = 0; for(int i=0; i<flowerbed.size(); i++){ if(flowerbed[i] == 0){ int next = (i==flowerbed.size()-1) ? 0 : flowerbed[i+1]; int pre = (i==0) ? 0 : flowerbed[i-1]; if(next == 0 && pre == 0){ flowerbed[i] = 1; count++; } } } return count>=n; } };
189. Rotate Array
Description:Rotate an array of n elements to the right by k steps.
For example, with n = 7 and k = 3, the array [1,2,3,4,5,6,7] is rotated to [5,6,7,1,2,3,4].
Note: Try to come up as many solutions as you can, there are at least 3 different ways to solve this problem.
代码如下：
1 2 3 4 5 6 7 8 9 10 11
classSolution { public: voidrotate(vector<int>& nums, int k){ int n = nums.size(); for(int i=0; i<k;i++){ int temp = nums[n-1]; nums.pop_back(); nums.insert(nums.begin(), temp); } } };
35. Search Insert Position
Description:
Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order.
You may assume no duplicates in the array.
Here are few examples. [1,3,5,6], 5 → 2 [1,3,5,6], 2 → 1 [1,3,5,6], 7 → 4 [1,3,5,6], 0 → 0
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:
1 2 3 4 5
Input: [3, 1, 4, 1, 5], k = 2 Output: 2 Explanation: There are two 2-diff pairs in the array, (1, 3) and (3, 5). Although we have two 1s in the input, we should only return the number of unique pairs.
Example 2:
1 2 3 4
Input:[1, 2, 3, 4, 5], k = 1 Output: 4 Explanation: There are four 1-diff pairs in the array, (1, 2), (2, 3), (3, 4) and (4, 5).
Example 3:
1 2 3 4
Input: [1, 3, 1, 5, 4], k = 0 Output: 1 Explanation: There is one 0-diff pair in the array, (1, 1).
Note:
The pairs (i, j) and (j, i) count as the same pair.
The length of the array won’t exceed 10,000.
All the integers in the given input belong to the range: [-1e7, 1e7].
Description:Given an array consisting of n integers, find the contiguous subarray of given length k that has the maximum average value. And you need to output the maximum average value.
Example 1:
1 2 3 4
Input: [1,12,-5,-6,50,3], k = 4 Output: 12.75 Explanation: Maximum average is (12-5-6+50)/4 = 51/4 = 12.75
Note:
1 <= k <= n <= 30,000.
Elements of the given array will be in the range [-10,000, 10,000].
classSolution { public: doublefindMaxAverage(vector<int>& nums, int k){ int sum = 0; int max = 0; for(int i=0; i<nums.size(); i++){ if(i<k){ sum += nums[i]; max = sum; }else{ sum = sum+nums[i]-nums[i-k]; max = max > sum ? max : sum; } } return max/(float)k; } doublefindMaxAverage2(vector<int>& nums, int k){ int sum = 0; for (int i = 0; i < k; i++) sum += nums[i]; int max = sum; for (int i = k; i < nums.size(); i++) { sum += nums[i] - nums[i - k]; max = max > sum ? max : sum; } return max / 1.0 / k; } };
628. Maximum Product of Three Numbers
Description:
Given an integer array, find three numbers whose product is maximum and output the maximum product.
Example 1:
1 2 3
Input: [1,2,3] Output: 6
Example 2:
1 2 3
Input: [1,2,3,4] Output: 24
Note:
The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
Multiplication of any three numbers in the input won’t exceed the range of 32-bit signed integer.
代码如下：
1 2 3 4 5 6 7 8 9 10 11 12
classSolution { public: intmaximumProduct(vector<int>& nums){ sort(nums.begin(),nums.end()); int len = nums.size(); int temp1 = nums[len-1]*nums[0]*nums[1]; int temp2 = nums[len-1]*nums[len-2]*nums[len-3]; return temp1>temp2?temp1:temp2; } };
566. Reshape the Matrix
Description:
In MATLAB, there is a very useful function called ‘reshape’, which can reshape a matrix into a new one with different size but keep its original data.
You’re given a matrix represented by a two-dimensional array, and two positive integers r and c representing the row number and column number of the wanted reshaped matrix, respectively.
The reshaped matrix need to be filled with all the elements of the original matrix in the same row-traversing order as they were.
If the ‘reshape’ operation with given parameters is possible and legal, output the new reshaped matrix; Otherwise, output the original matrix.
Example 1:
1 2 3 4 5 6 7 8 9 10
Input: nums = [[1,2], [3,4]] r = 1, c = 4 Output: [[1,2,3,4]] Explanation: The row-traversing of nums is [1,2,3,4]. The new reshaped matrix is a 1 * 4 matrix, fill it row by row by using the previous list.
Example 2:
1 2 3 4 5 6 7 8 9 10 11
Input: nums = [[1,2], [3,4]] r = 2, c = 4 Output: [[1,2], [3,4]] Explanation: There is no way to reshape a 2 * 2 matrix to a 2 * 4 matrix. So output the original matrix.
Note:
The height and width of the given matrix is in range [1, 100].
classSolution { public: vector<vector<int>> matrixReshape(vector<vector<int>>& nums, int r, int c) { int row = nums.size(); int col = nums[0].size(); if(row*col != r*c){ return nums; } vector<vector<int>> result(r); for(int i=0; i<r;i++){ result[i].resize(c); } for(int i=0; i<row*col; i++){ result[i/c][i%c] = nums[i/col][i%col]; } //delete result; return result; } };
645. Set Mismatch
Description:The set S originally contains numbers from 1 to n. But unfortunately, due to the data error, one of the numbers in the set got duplicated to another number in the set, which results in repetition of one number and loss of another number.
Given an array nums representing the data status of this set after the error. Your task is to firstly find the number occurs twice and then find the number that is missing. Return them in the form of an array.
Example 1:
1 2 3
Input: nums = [1,2,2,4] Output: [2,3]
Note:
The given array size will in the range [2, 10000].
The given array’s numbers won’t have any order.
解题思路：代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14
classSolution { public: vector<int> findErrorNums(vector<int>& nums){ int[] res = newint[2]; for (int i : nums) { if (nums[Math.abs(i) - 1] < 0) res[0] = Math.abs(i); else nums[Math.abs(i) - 1] *= -1; } for (int i=0;i<nums.length;i++) { if (nums[i] > 0) res[1] = i+1; } return res; } };
106. Construct Binary Tree from Inorder and Postorder Traversal
Description:
Given inorder and postorder traversal of a tree, construct the binary tree.
Note: You may assume that duplicates do not exist in the tree.
#include<stdio.h> #include<vector> usingnamespace std; /** * Definition for a binary tree node.*/ structTreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; classSolution { public: TreeNode* buildTree(vector<int>& inorder, vector<int>& postorder){ //if(inorder.size()！=postorder.size()) return NULL; returntreeHelper(inorder,0,inorder.size()-1,postorder,0,postorder.size()-1); } TreeNode* treeHelper(vector<int> &in, int startIn, int endIn, vector<int> &post, int startPost, int endPost){ if(startIn>endIn ||startPost>endPost) returnNULL; if(startIn==endIn && startPost== endPost) returnnewTreeNode(in[startIn]); TreeNode* root = newTreeNode(post[endPost]); for(int i=startIn;i<=endIn; i++){ if(post[endPost]==in[i]){ root->left=treeHelper(in,startIn,i-1,post,startPost,startPost+i-startIn-1); root->right=treeHelper(in,i+1,endIn,post,startPost+i-startIn,endPost-1); } } return root; } };
108. Convert Sorted Array to Binary Search Tree
Description:
Given an array where elements are sorted in ascending order, convert it to a height balanced BST.
For this problem, a height-balanced binary tree is defined as a binary tree in which the depth of the two subtrees of every node never differ by more than 1.
Example:
1 2 3 4 5 6 7 8 9
Given the sorted array: [-10,-3,0,5,9],
One possible answer is: [0,-3,9,-10,null,5], which represents the following height balanced BST:
Given n non-negative integers a1, a2, …, *an *, where each represents a point at coordinate (i, ai). n vertical lines are drawn such that the two endpoints of line i is at (i, ai) and (i, 0). Find two lines, which together with x-axis forms a container, such that the container contains the most water.
**Note: **You may not slant the container and n is at least 2.
The above vertical lines are represented by array [1,8,6,2,5,4,8,3,7]. In this case, the max area of water (blue section) the container can contain is 49.
#include<stdio.h> #include<vector> #include<unordered_map> usingnamespace std; classSolution { public: intlongestConsecutive(vector<int>& nums){ int res=0; unordered_map<int, int> hash; for(int n : nums){ if(hash.find(n)==hash.end()){ int left = hash.find(n-1)!=hash.end()?hash[n-1]:0; int right = hash.find(n+1)!=hash.end()?hash[n+1]:0; int sum=left+right+1; res=max(res,sum); hash[n]=sum; hash[n-left]=sum; hash[n+right]=sum; } elsecontinue; } return res; } };
15. 3Sum
Description:
Given an array nums of n integers, are there elements a, b, c in nums such that a + b + c = 0? Find all unique triplets in the array which gives the sum of zero.
Note:
The solution set must not contain duplicate triplets.
Given an array nums of n integers and an integer target, find three integers in nums such that the sum is closest to target. Return the sum of the three integers. You may assume that each input would have exactly one solution.
Example:
1 2 3
Given array nums = [-1, 2, 1, -4], and target = 1.
The sum that is closest to the target is 2. (-1 + 2 + 1 = 2).
#include<stdio.h> #include<vector> usingnamespace std; classSolution { public: intthreeSumClosest(vector<int>& nums, int target){ int len = nums.size(); int gap=INT_MAX; int res = 0; if(len==0) return0; sort(nums.begin(),nums.end()); for(int i=0; i<len-2; i++){ if(i==0 || (i>0 && nums[i]!=nums[i-1])){ int lo=i+1, hi=len-1, sum=target-nums[i]; while(lo<hi){ if(nums[lo]+nums[hi]==sum) return target; elseif(nums[lo]+nums[hi]<sum){ if(abs(nums[lo]+nums[hi]-sum)<gap){ gap=abs(nums[lo]+nums[hi]-sum); res=target-gap; } lo++; }else{ if(abs(nums[lo]+nums[hi]-sum)<gap){ gap=abs(nums[lo]+nums[hi]-sum); res=target+gap; } hi--; } } } } return res; } };
18. 4Sum
Given an array nums of n integers and an integer target, are there elements a, b, c, and d in nums such that a + b + c + d = target? Find all unique quadruplets in the array which gives the sum of target.
Note:
The solution set must not contain duplicate quadruplets.
Example:
1 2 3 4 5 6 7 8
Given array nums = [1, 0, -1, 0, -2, 2], and target = 0.
A solution set is: [ [-1, 0, 0, 1], [-2, -1, 1, 2], [-2, 0, 0, 2] ]
Given an array nums of n integers where n > 1, return an array output such that output[i] is equal to the product of all the elements of nums except nums[i].
Example:
1 2 3
Input: [1,2,3,4] Output: [24,12,8,6]
**Note: **Please solve it without division and in O(n).
Follow up: Could you solve it with constant space complexity? (The output array does not count as extra space for the purpose of space complexity analysis.)
Given n non-negative integers representing an elevation map where the width of each bar is 1, compute how much water it is able to trap after raining.
The above elevation map is represented by array [0,1,0,2,1,0,1,3,2,1,2,1]. In this case, 6 units of rain water (blue section) are being trapped. Thanks Marcos for contributing this image!
Example:
1 2
Input: [0,1,0,2,1,0,1,3,2,1,2,1] Output: 6
代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
#include<stdio.h> #include<vector> usingnamespace std; classSolution { public: inttrap(vector<int>& height){ int l=0, r=height.size()-1; int lower=0, level=0; int water=0; while(l<r){ lower = height[height[l]<height[r]?l++:r--]; level=max(level,lower); water+=level-lower; } return water; } };
45. Jump Game II
Description:
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Your goal is to reach the last index in the minimum number of jumps.
Example:
1 2 3 4
Input: [2,3,1,1,4] Output: 2 Explanation: The minimum number of jumps to reach the last index is 2. Jump 1 step from index 0 to 1, then 3 steps to the last index.
Note:
You can assume that you can always reach the last index.
You are given an n x n 2D matrix representing an image.
Rotate the image by 90 degrees (clockwise).
Note:
You have to rotate the image in-place, which means you have to modify the input 2D matrix directly. DO NOT allocate another 2D matrix and do the rotation.
Example 1:
1 2 3 4 5 6 7 8 9 10 11 12 13 14
Given input matrix = [ [1,2,3], [4,5,6], [7,8,9] ],
rotate the input matrix in-place such that it becomes: [ [7,4,1], [8,5,2], [9,6,3] ]
Given an array of non-negative integers, you are initially positioned at the first index of the array.
Each element in the array represents your maximum jump length at that position.
Determine if you are able to reach the last index.
Example 1:
1 2 3 4
Input: [2,3,1,1,4] Output: true Explanation: Jump 1 step from index 0 to 1, then 3 steps to the last index.
Example 2:
1 2 3 4
Input: [3,2,1,0,4] Output: false Explanation: You will always arrive at index 3 no matter what. Its maximum jump length is 0, which makes it impossible to reach the last index.
代码如下：
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
#include<stdio.h> #include<vector> usingnamespace std; classSolution { public: boolcanJump(vector<int>& nums){ int len = nums.size(); int curMax=0, nextMax=0, i=0; while(curMax-i+1>0){ for(;i<=curMax;i++){ nextMax=max(nextMax,i+nums[i]); if(nextMax>=len-1) returntrue; } curMax=nextMax; } returnfalse; } };
56. Merge Intervals
Description:
Given a collection of intervals, merge all overlapping intervals.
Example 1:
1 2 3 4
Input: [[1,3],[2,6],[8,10],[15,18]] Output: [[1,6],[8,10],[15,18]] Explanation: Since intervals [1,3] and [2,6] overlaps, merge them into [1,6].
Example 2:
1 2 3
Input: [[1,4],[4,5]] Output: [[1,5]] Explanation: Intervals [1,4] and [4,5] are considerred overlapping.
Input: intervals = [[1,2],[3,5],[6,7],[8,10],[12,16]], newInterval = [4,8] Output: [[1,2],[3,10],[12,16]] Explanation: Because the new interval [4,8] overlaps with [3,5],[6,7],[8,10].
#include<stdio.h> #include<vector> usingnamespace std; classSolution { public: voidsetZeroes(vector<vector<int>>& matrix){ int rows = matrix.size(); int cols = matrix[0].size(); vector<vector<int>> tags; for(int i=0;i<rows;i++){ for(int j=0;j<cols;j++){ if(matrix[i][j]==0) tags.push_back(vector<int>{i,j}); } } for(int k=0;k<tags.size();k++){ int i=tags[k][0]; int j=tags[k][1]; for(int m=0;m<cols;m++) matrix[i][m]=0; for(int m=0;m<rows;m++) matrix[m][j]=0; } } voidsetZeroes2(vector<vector<int> > &matrix){ int col0 = 1, rows = matrix.size(), cols = matrix[0].size(); for (int i = 0; i < rows; i++) { if (matrix[i][0] == 0) col0 = 0; for (int j = 1; j < cols; j++) if (matrix[i][j] == 0) matrix[i][0] = matrix[0][j] = 0; } for (int i = rows - 1; i >= 0; i--) { for (int j = cols - 1; j >= 1; j--) if (matrix[i][0] == 0 || matrix[0][j] == 0) matrix[i][j] = 0; if (col0 == 0) matrix[i][0] = 0; } } };
75. Sort Colors
Description:
Given an array with n objects colored red, white or blue, sort them **in-place **so that objects of the same color are adjacent, with the colors in the order red, white and blue.
Here, we will use the integers 0, 1, and 2 to represent the color red, white, and blue respectively.
Note: You are not suppose to use the library’s sort function for this problem.
Example:
1 2
Input: [2,0,2,1,1,0] Output: [0,0,1,1,2,2]
Follow up:
A rather straight forward solution is a two-pass algorithm using counting sort. First, iterate the array counting number of 0’s, 1’s, and 2’s, then overwrite array with total number of 0’s, then 1’s and followed by 2’s.
Could you come up with a one-pass algorithm using only constant space?
#include<stdio.h> #include<vector> #include<unordered_map> usingnamespace std; classSolution { public: voidsortColors(vector<int>& nums){ unordered_map<int,int> hash; for(int n : nums){ hash[n]++; } int index=0; for(int i=0; i<3; i++){ while(hash[i]--){ nums[index++]=i; } } } voidsortColors(int A[], int n){ int second=n-1, zero=0; for (int i=0; i<=second; i++) { while (A[i]==2 && i<second) swap(A[i], A[second--]); while (A[i]==0 && i>zero) swap(A[i], A[zero++]); } } };
84. Largest Rectangle in Histogram
Description:
Given n non-negative integers representing the histogram’s bar height where the width of each bar is 1, find the area of largest rectangle in the histogram.
Above is a histogram where width of each bar is 1, given height = [2,1,5,6,2,3].
The largest rectangle is shown in the shaded area, which has area = 10 unit.