第 k 大的数
Find the kth largest element in an unsorted array. Note that it is the kth largest element in the sorted order, not the kth distinct element.
For example,
Given [3,2,1,5,6,4] and k = 2, return 5.
Note:
You may assume k is always valid, 1 ≤ k ≤ array's length.
class Solution {
public:
inline int left(int idx) {
return (idx << 1) + 1;
}
inline int right(int idx) {
return (idx << 1) + 2;
}
void max_heapify(vector<int>& nums, int idx) {
int largest = idx;
int l = left(idx), r = right(idx);
if (l < heap_size && nums[l] > nums[largest]) largest = l;
if (r < heap_size && nums[r] > nums[largest]) largest = r;
if (largest != idx) {
swap(nums[idx], nums[largest]);
max_heapify(nums, largest);
}
}
void build_max_heap(vector<int>& nums) {
heap_size = nums.size();
for (int i = (heap_size >> 1) - 1; i >= 0; i--)
max_heapify(nums, i);
}
int findKthLargest(vector<int>& nums, int k) {
build_max_heap(nums);
for (int i = 0; i < k; i++) {
swap(nums[0], nums[heap_size - 1]);
heap_size--;
max_heapify(nums, 0);
}
return nums[heap_size];
}
private:
int heap_size;
}
找数组中出现次数超过一半的数字04.14
数组中有一个数字出现次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。
由于数字2在数组中出现了5次，超过数组长度一半，因此输出2
int findNumber(std::vector<int> v){
std::stack<int> stack = std::stack<int>();
for (int i = 0; i < v.size(); ++i) {
if (stack.empty() || stack.top() == v[i]) {
stack.push(v[i]);
}
else{
stack.pop();
}
}
return stack.top();
}
旋转数组求查找某个值是否存在04.12
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).
You are given a target value to search. If found in the array return its index, otherwise return -1.
You may assume no duplicate exists in the array.
public static int search(int n,int[] array){
int low = 0;
int high = array.length-1;
while(low<=high){
int middle = (low+high)/2;
if(array[middle]==n) return middle;
if(array[middle]>array[low]){ //left is order
if(n<=array[middle]&&n>=array[low]){
high = middle-1;
}else {
low = middle+1;
}
}else {
if(n>=array[middle]&&n<=array[high]){
low = middle+1;
}else {
high = middle-1;
}
}
}
return -1;
}
旋转数组求最小值04.10
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).
Find the minimum element.
You may assume no duplicate exists in the array.
int findMin(vector<int> &num) {
int start=0,end=num.size()-1;
while (start<end) {
if (num[start]<num[end])
return num[start];
int mid = (start+end)/2;
if (num[mid]>=num[start]) {
start = mid+1;
} else {
end = mid;
}
}
return num[start];
}
求两个不等长、有序数组的中位数04.09
There are two sorted arrays nums1 and nums2 of size m and n respectively.
Find the median of the two sorted arrays. The overall run time complexity should be O(log (m+n)).
Example:
nums1 = [1, 2]
nums2 = [3, 4]
The median is (2 + 3)/2 = 2.5
double findMedianSortedArrays(vector<int>& nums1, vector<int>& nums2) {
int N1 = nums1.size();
int N2 = nums2.size();
if (N1 < N2) return findMedianSortedArrays(nums2, nums1); // Make sure A2 is the shorter one.
if (N2 == 0) return ((double)nums1[(N1-1)/2] + (double)nums1[N1/2])/2; // If A2 is empty
int lo = 0, hi = N2 * 2;
while (lo <= hi) {
int mid2 = (lo + hi) / 2; // Try Cut 2
int mid1 = N1 + N2 - mid2; // Calculate Cut 1 accordingly
double L1 = (mid1 == 0) ? INT_MIN : nums1[(mid1-1)/2]; // Get L1, R1, L2, R2 respectively
double L2 = (mid2 == 0) ? INT_MIN : nums2[(mid2-1)/2];
double R1 = (mid1 == N1 * 2) ? INT_MAX : nums1[(mid1)/2];
double R2 = (mid2 == N2 * 2) ? INT_MAX : nums2[(mid2)/2];
if (L1 > R2) lo = mid2 + 1; // A1's lower half is too big; need to move C1 left (C2 right)
else if (L2 > R1) hi = mid2 - 1; // A2's lower half too big; need to move C2 left.
else return (max(L1,L2) + min(R1, R2)) / 2; // Otherwise, that's the right cut.
}
return -1;
}
实现简单的正则表达式匹配04.08
Implement regular expression matching with support for '.' and ''.
'.' Matches any single character.
'' Matches zero or more of the preceding element.
The matching should cover the entire input string (not partial).
class Solution {
public:
bool isMatch(string s, string p) {
int m = s.length(), n = p.length();
vector<vector<bool> > dp(m + 1, vector<bool> (n + 1, false));
dp[0][0] = true;
for (int i = 0; i <= m; i++)
for (int j = 1; j <= n; j++)
if (p[j - 1] == '*')
dp[i][j] = dp[i][j - 2] || (i > 0 && (s[i - 1] == p[j - 2] || p[j - 2] == '.') && dp[i - 1][j]);
else dp[i][j] = i > 0 && dp[i - 1][j - 1] && (s[i - 1] == p[j - 1] || p[j - 1] == '.');
return dp[m][n];
}
};
连续子数组的最大和04.07
Find the contiguous subarray within an array (containing at least one number) which has the largest sum.
For example, given the array [-2,1,-3,4,-1,2,1,-5,4],
the contiguous subarray [4,-1,2,1] has the largest sum = 6.
public int maxSubArray(int[] A) {
int n = A.length;
int[] dp = new int[n];//dp[i] means the maximum subarray ending with A[i];
dp[0] = A[0];
int max = dp[0];
for(int i = 1; i < n; i++){
dp[i] = A[i] + (dp[i - 1] > 0 ? dp[i - 1] : 0);
max = Math.max(max, dp[i]);
}
return max;
}
解题思路，从前往后的顺序，并不知道后面新加入的部分和是否会 >0，可以把这道动态规划的子问题的格式更改为：maxSubArray（int A []，int i）），这意味着A [0：i]的maxSubArray必须具有A [i]作为结束元素。我们可以判断知道A [i]之前连续元素的和的最大值。从而解决整个数组的连续子数组的最大和问题。
翻转字符串04.06
Given an input string, reverse the string word by word.
For example,Given s = "the sky is blue",return "blue is sky the".
void reverseWords(string &s) {
reverse(s.begin(), s.end());
int storeIndex = 0;
for (int i = 0; i < s.size(); i++) {
if (s[i] != ' ') {
if (storeIndex != 0) s[storeIndex++] = ' ';
int j = i;
while (j < s.size() && s[j] != ' ') { s[storeIndex++] = s[j++]; }
reverse(s.begin() + storeIndex - (j - i), s.begin() + storeIndex);
i = j;
}
}
s.erase(s.begin() + storeIndex, s.end());
}
字符串全排列04.05
Implement atoi to convert a string to an integer.consider all possible input cases.
用C++写一个函数, 如 Foo(const char *str), 打印出 str 的全排列, 如 abc 的全排列: abc, acb, bca, dac, cab, cab
思路：全排列就是从第一个数字起每个数分别与它后面的数字交换
#include <stdio.h>
#include <string.h>
void Swap(char *a, char *b)
{
char t = *a;
*a = *b;
*b = t;
}
//k表示当前选取到第几个数,m表示共有多少数.
void AllRange(char *pszStr, int k, int m)
{
if (k == m)
{
static int s_i = 1;
printf(" 第%3d个排列\t%s\n", s_i++, pszStr);
}
else {
for (int i = k; i <= m; i++) //第i个数分别与它后面的数字交换就能得到新的排列
{
Swap(pszStr + k, pszStr + i);
AllRange(pszStr, k + 1, m);
Swap(pszStr + k, pszStr + i);
}
}
}
void Foo(char *pszStr)
{
AllRange(pszStr, 0, strlen(pszStr) - 1);
}
int main()
{
printf(" 全排列的递归实现\n");
printf(" --by MoreWindows( http://blog.csdn.net/MoreWindows )--\n\n");
char szTextStr[] = "123";
printf("%s的全排列如下:\n", szTextStr);
Foo(szTextStr);
return 0;
}
输出：
123的全排列如下:
第 1个排列 123
第 2个排列 132
第 3个排列 213
第 4个排列 231
第 5个排列 321
第 6个排列 312
去掉重复的全排列的递归实现
思路：去重的全排列就是从第一个数字起每个数分别与它后面非重复出现的数字交换
//去重全排列的递归实现
#include <stdio.h>
#include <string.h>
void Swap(char *a, char *b)
{
char t = *a;
*a = *b;
*b = t;
}
//在pszStr数组中，[nBegin,nEnd)中是否有数字与下标为nEnd的数字相等
bool IsSwap(char *pszStr, int nBegin, int nEnd)
{
for (int i = nBegin; i < nEnd; i++)
if (pszStr[i] == pszStr[nEnd])
return false;
return true;
}
//k表示当前选取到第几个数,m表示共有多少数.
void AllRange(char *pszStr, int k, int m)
{
if (k == m)
{
static int s_i = 1;
printf(" 第%3d个排列\t%s\n", s_i++, pszStr);
}
else
{
for (int i = k; i <= m; i++) //第i个数分别与它后面的数字交换就能得到新的排列
{
if (IsSwap(pszStr, k, i))
{
Swap(pszStr + k, pszStr + i);
AllRange(pszStr, k + 1, m);
Swap(pszStr + k, pszStr + i);
}
}
}
}
void Foo(char *pszStr)
{
AllRange(pszStr, 0, strlen(pszStr) - 1);
}
int main()
{
printf(" 去重全排列的递归实现\n");
printf(" --by MoreWindows( http://blog.csdn.net/MoreWindows )--\n\n");
char szTextStr[] = "122";
printf("%s的全排列如下:\n", szTextStr);
Foo(szTextStr);
return 0;
}
[字符串转数字04.04]？(https://leetcode.com/problems/string-to-integer-atoi/#/description)
Implement atoi to convert a string to an integer.consider all possible input cases.
int myAtoi(string str) {
long result = 0;
int indicator = 1;
for(int i = 0; i<str.size();)
{
i = str.find_first_not_of(' ');
if(str[i] == '-' || str[i] == '+')
indicator = (str[i++] == '-')? -1 : 1;
while('0'<= str[i] && str[i] <= '9')
{
result = result*10 + (str[i++]-'0');
if(result*indicator >= INT_MAX) return INT_MAX;
if(result*indicator <= INT_MIN) return INT_MIN;
}
return result*indicator;
}
}
最长无重复子串04.03
Given a string, find the length of the longest substring without repeating characters.
int lengthOfLongestSubstring(string s) {
vector<int> dict(256, -1);
int maxLen = 0, start = -1;
for (int i = 0; i != s.length(); i++) {
if (dict[s[i]] > start)
start = dict[s[i]];
dict[s[i]] = i;
maxLen = max(maxLen, i - start);
}
return maxLen;
}
最长回文字符串04.02
Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.Example:Input: "babad" Output: "bab"
string longestPalindrome(string s) {
if (s.empty()) return "";
if (s.size() == 1) return s;
int min_start = 0, max_len = 1;
for (int i = 0; i < s.size();) {
if (s.size() - i <= max_len / 2) break;
int j = i, k = i;
while (k < s.size()-1 && s[k+1] == s[k]) ++k;
i = k+1;
while (k < s.size()-1 && j > 0 && s[k + 1] == s[j - 1]) { ++k; --j; }
int new_len = k - j + 1;
if (new_len > max_len) { min_start = j; max_len = new_len; }
}
return s.substr(min_start, max_len);
}
网友评论