leetcode

some interesting code

Longest Palindromic Substring

Given a string s, find the longest palindromic substring in s. You may assume that the maximum length of s is 1000.

Example1:

1
2
3
Input: "babad"
Output: "bab"
Note: "aba" is also a valid answer.

Example2:

1
2
Input: "cbbd"
Output: "bb"

solution

Dynamic Programming

1
2
3
4
5
6
7
8
define P(i, j) = if S[i, j] is a palindrome ? true : false

Recursive:
P(i, j) = (P(i+1, j-1) and S[i] == S[j])

Base:
P(i,i) = true
P(i, i+1) = (S[i] == S[i+1])
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
public:
string longestPalindrome(string s) {
int size = s.size();
if (size < 2)
return s;

bool dp[size][size];

int maxLen = 1;
int pos = 0;

for (int j = 0; j < size; ++j) {
dp[j][j] = true;
for (int i = 0; i < j; ++i) {
if (j == i+1) {
dp[i][j]= (s[i] == s[j]);
} else {
dp[i][j] = ((s[i] == s[j]) && dp[i+1][j-1]);
}
int len = j - i + 1;
if (len > maxLen && dp[i][j]) {
maxLen = len;
pos = i;
}
}
}
return s.substr(pos, maxLen);
}
};

Kth Largest Element in an Array

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.

Example 1:

1
2
Input: [3,2,1,5,6,4] and k = 2
Output: 5

Example 2:

1
2
Input: [3,2,3,1,2,4,5,5,6] and k = 4
Output: 4

Note:
You may assume k is always valid, 1 ≤ k ≤ array’s length.

solution

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
class Solution {
public:
template<typename Comparator>
int partition(vector<int>& nums, int left, int right, Comparator cmp) {
int pivot = nums[left];
swap(nums[left], nums[right]);

int pos = left;
for (int i = left; i < right; ++i) {
if (cmp(nums[i], pivot)) {
swap(nums[i], nums[pos++]);
}
}
swap(nums[pos], nums[right]);
return pos;
}

int findKthLargest(vector<int>& nums, int k) {

int left = 0;
int right = nums.size() - 1;

while (left <= right) {
int idx = partition(nums, left, right, greater<>());
if (idx == k - 1)
return nums[idx];
else if (idx < k - 1)
left = idx + 1;
else
right = idx - 1;
}
return -1;
}
};

OR

1
2
3
4
5
6
7
class Solution {
public:
int findKthLargest(vector<int>& nums, int k) {
nth_element(nums.begin(), nums.end()-k, nums.end());
return nums[nums.size()-k];
}
};