- Find Minimum in Rotated Sorted Array
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.
#include <bits/stdc++.h>
using namespace std;
/**
* 原题链接
* https://leetcode.com/problems/find-minimum-in-rotated-sorted-array/description/
*/
class Solution {
public:
int findMin(vector<int> &rotateArray) {
int left = 0, right = rotateArray.size() - 1;
while (left < right) {
int mid = (left + right) / 2;
if (rotateArray[mid] < rotateArray[right]) {
right = mid;
} else {
left = mid + 1;
}
}
return rotateArray[left];
}
};
- Find Minimum in Rotated Sorted Array II
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.The array may contain duplicates.
#include <bits/stdc++.h>
using namespace std;
/**
* 原题链接
* https://leetcode.com/problems/find-minimum-in-rotated-sorted-array-ii/description/
*/
class Solution {
public:
int findMin(vector<int> &nums) {
int m = nums.size();
int left = 0, right = m - 1;
while (left < right) {
int middle = (left + right) / 2;
if (nums[middle] < nums[right]) {
right = middle;
} else if (nums[middle] > nums[right]) {
left = middle + 1;
} else {
right--;
}
}
return nums[left];
}
};
- Largest Number
Given a list of non negative integers, arrange them such that they form the largest number.
#include <bits/stdc++.h>
using namespace std;
/**
* 原题链接
* https://leetcode.com/problems/largest-number/description/
*
*/
class Solution {
public:
string largestNumber(vector<int> &nums) {
sort(nums.begin(), nums.end(), [](int a, int b) {
string stra = to_string(a), strb = to_string(b);
return stra + strb > strb + stra;
});
int m = nums.size();
string res;
for (int i = 0; i < m; i++) {
res += to_string(nums[i]);
}
while (res[0] == '0' && res.size() > 1)
res.erase(0, 1);
return res;
}
};
- Repeated DNA Sequences
All DNA is composed of a series of nucleotides abbreviated as A, C, G, and T, for example: "ACGAATTCCG". When studying DNA, it is sometimes useful to identify repeated sequences within the DNA.Write a function to find all the 10-letter-long sequences (substrings) that occur more than once in a DNA molecule.
#include <bits/stdc++.h>
using namespace std;
/**
* 原题链接
* https://leetcode.com/problems/repeated-dna-sequences/description/
*/
class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
int m = s.size();
set<string> dir1, dir2;
vector<string> res;
for (int i = 0; i < m - 9; i++) {
string str = s.substr(i, 10);
if (!dir1.insert(str).second && dir2.insert(str).second) {
res.push_back(str);
}
}
return res;
}
};
- Rotate Array
Given an array, rotate the array to the right by k steps, where k is non-negative.
#include <bits/stdc++.h>
using namespace std;
/**
* 原题链接
* https://leetcode.com/problems/rotate-array/discuss/
*/
class Solution {
public:
void rotate(vector<int> &nums, int k) {
int m = nums.size();
k = k % m;
reverse(nums.begin(), nums.begin() + m - k);
reverse(nums.begin() + m - k, nums.end());
reverse(nums.begin(), nums.end());
}
};
- Reverse Bits
Reverse bits of a given 32 bits unsigned integer.
#include <bits/stdc++.h>
using namespace std;
/**
* 原题链接
* https://leetcode.com/problems/reverse-bits/description/
*/
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t res = 0;
for (int i = 0; i < 32; i++, n >>= 1) {
res <<= 1;
res |= (n & 1);
}
return res;
}
};
- Number of 1 Bits
Write a function that takes an unsigned integer and returns the number of '1' bits it has (also known as the Hamming weight).
#include <bits/stdc++.h>
using namespace std;
/**
* 原题链接
* https://leetcode.com/problems/number-of-1-bits/description/
*/
class Solution {
public:
int hammingWeight(uint32_t n) {
int res = 0;
while (n) {
n = n & (n - 1);
res++;
}
return res;
}
};
- House Robber
You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.
Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.
#include <bits/stdc++.h>
using namespace std;
/**
* 原题链接
* https://leetcode.com/problems/house-robber/description/
*/
class Solution {
public:
int rob(vector<int> &nums) {
int m = nums.size();
int pre = 0, cur = 0;
for (int i = 0; i < m; i++) {
int temp = cur;
cur = max(cur, pre + nums[i]);
pre = temp;
}
return cur;
}
};
- Binary Tree Right Side View
Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.
#include <bits/stdc++.h>
using namespace std;
/**
* 原题链接
* https://leetcode.com/problems/binary-tree-right-side-view/description/
*/
struct TreeNode {
int val;
TreeNode *left;
TreeNode *right;
TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
class Solution {
public:
vector<int> rightSideView(TreeNode *root) {
vector<int> res;
helper(root, 0, res);
return res;
}
void helper(TreeNode *root, int level, vector<int> &res) {
if (root == NULL)
return;
if (res.size() == level)
res.push_back(root->val);
helper(root->right, level + 1, res);
helper(root->left, level + 1, res);
}
};
- Number of Islands
Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
#include <bits/stdc++.h>
using namespace std;
/**
* 原题链接
* https://leetcode.com/problems/number-of-islands/description/
*/
class Solution {
public:
int numIslands(vector<vector<char>> &grid) {
if (grid.size() == 0)
return 0;
int m = grid.size(), n = grid[0].size(), res = 0;
vector<vector<bool>> visit(m, vector<bool>(n, false));
vector<vector<int>> direction = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (!visit[i][j] && grid[i][j] == '1') {
helper(i, j, visit, direction, grid);
res++;
}
}
}
return res;
}
void helper(int row, int col, vector<vector<bool>> &visit,
vector<vector<int>> &direction, vector<vector<char>> &grid) {
visit[row][col] = true;
for (int i = 0; i < 4; i++) {
int newRow = row + direction[i][0];
int newCol = col + direction[i][1];
if (newRow >= 0 && newRow < visit.size() && newCol >= 0 &&
newCol < visit[0].size() && !visit[newRow][newCol] &&
grid[newRow][newCol] == '1') {
helper(newRow, newCol, visit, direction, grid);
}
}
}
};
