华为提纲
递归
70. 爬楼梯
class Solution {
public:
int climbStairs(int n) {
vector<int> vec(n+1,0);
vec[0] = 1;
vec[1] = 1;
for(int i = 2; i <= n; i++){
vec[i] = vec[i-1] + vec[i-2];
}
return vec[n];
}
};
112. 路径总和
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode() : val(0), left(nullptr), right(nullptr) {}
* TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
* TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
* };
*/
class Solution {
public:
int sum = 0;
bool flag = false;
void tracking(TreeNode* root, int targetSum){
if(!root){
return ;
}
sum+=root->val;
if(!root->left && !root->right && sum == targetSum){
flag = true;
return ;
}
if(root->left){
tracking(root->left, targetSum);
if(flag) return;
sum -= root->left->val;
}
if(root->right){
tracking(root->right, targetSum);
if(flag) return;
sum -= root->right->val;
}
}
bool hasPathSum(TreeNode* root, int targetSum) {
tracking(root, targetSum);
return flag;
}
};
509. 斐波那契数
/*
* @lc app=leetcode.cn id=509 lang=cpp
*
* [509] 斐波那契数
*/
// @lc code=start
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int fib(int n) {
if (n<2)
{
return n;
}
vector<int> path(n+1,0);
path[1] = 1;
for (int i = 2; i <=n; i++)
{
path[i] = path[i-1] + path[i-2];
}
return path[n];
}
};
// @lc code=end
分治
23. 合并 K 个升序链表
class Solution {
public:
//正常合并两个链表
ListNode* mergeTwoLists(ListNode *a, ListNode *b) {
if ((!a) || (!b)) return a ? a : b;
ListNode *head = new ListNode(0), *tail = head, *aPtr = a, *bPtr = b;
while (aPtr && bPtr) {
if (aPtr->val < bPtr->val) {
tail->next = aPtr; aPtr = aPtr->next;
} else {
tail->next = bPtr; bPtr = bPtr->next;
}
tail = tail->next;
}
tail->next = (aPtr ? aPtr : bPtr);
return head->next;
}
ListNode* merge(vector <ListNode*> &lists, int l, int r) {
if (l == r) return lists[l];
if (l > r) return nullptr;
int mid = (l + r) >> 1;
return mergeTwoLists(merge(lists, l, mid), merge(lists, mid + 1, r));
}
ListNode* mergeKLists(vector<ListNode*>& lists) {
return merge(lists, 0, lists.size() - 1);
}
};
合并两个有序链表的函数：
ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
ListNode* mergedList = new ListNode(0); // 创建一个新的链表作为合并后的链表
ListNode* current = mergedList; // 用于遍历合并后的链表
while (l1 && l2) {
if (l1->val < l2->val) {
current->next = l1; // 将l1节点连接到合并后的链表
l1 = l1->next; // l1指针向后移动
} else {
current->next = l2; // 将l2节点连接到合并后的链表
l2 = l2->next; // l2指针向后移动
}
current = current->next; // current指针向后移动
}
// 将剩余的非空链表连接到合并后的链表末尾
if (l1) {
current->next = l1;
} else {
current->next = l2;
}
return mergedList->next; // 返回合并后的链表的头节点
}
169. 多数元素
class Solution {
public:
int majorityElement(vector<int>& nums) {
unordered_map<int,int> map;
for(int num : nums){
map[num]++;
}
int lim = nums.size()/2;
for(auto it = map.begin();it != map.end(); it++){
if(it->second > lim){
return it->first;
};
}
return 0;
}
};
240. 搜索二维矩阵 II
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
bool searchMatrix(vector<vector<int>>& matrix, int target) {
int m = matrix.size(),n = matrix[0].size();
for (int i = 0; i < m; i++)
{
if(matrix[i][0] > target || matrix[i][n-1] < target){
continue;
}
int left = 0,right = n-1;
while (left <= right)
{
int mid = (right - left) /2 + left;
if(matrix[i][mid] == target){
return true;
}else if (matrix[i][mid] < target)
{
left = mid +1;
}else {
right = mid - 1;
}
}
}
return false;
}
};
单调栈
84. 柱状图中最大的矩形
// 版本一
class Solution {
public:
int largestRectangleArea(vector<int>& heights) {
int result = 0;
stack<int> st;
heights.insert(heights.begin(), 0); // 数组头部加入元素0
heights.push_back(0); // 数组尾部加入元素0
st.push(0);
// 第一个元素已经入栈，从下标1开始
for (int i = 1; i < heights.size(); i++) {
if (heights[i] > heights[st.top()]) { // 情况一
st.push(i);
} else if (heights[i] == heights[st.top()]) { // 情况二
st.pop(); // 这个可以加，可以不加，效果一样，思路不同
st.push(i);
} else { // 情况三
while (!st.empty() && heights[i] < heights[st.top()]) { // 注意是while
int mid = st.top();
st.pop();
if (!st.empty()) {
int left = st.top();
int right = i;
int w = right - left - 1;
int h = heights[mid];
result = max(result, w * h);
}
}
st.push(i);
}
}
return result;
}
};
739. 每日温度
#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <stack>
using namespace std;
class Solution {
public:
vector<int> dailyTemperatures(vector<int>& temperatures) {
stack<int>st;
int n = temperatures.size();
st.push(0);
vector<int> result(n,0);
for (int i = 1; i < n; i++)
{
if (temperatures[i] <= temperatures[st.top()])
{
st.push(i);
}else{
while (!st.empty()&&temperatures[i] > temperatures[st.top()])
{
int len = i - st.top();
result[st.top()] = len;
st.pop();
}
st.push(i);
}
}
return result;
}
};
下一个更大元素 I
#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <stack>
using namespace std;
class Solution {
public:
vector<int> nextGreaterElement(vector<int>& nums1, vector<int>& nums2) {
unordered_map<int,int> map;
vector<int> vec(nums1.size(),0);
vector<int> result(nums1.size(),-1);
stack<int> st;
for (int i = 0; i < nums1.size(); i++)
{
map[nums1[i]] = i;
}
st.push(nums2[0]);
for (int i = 1; i < nums2.size(); i++)
{
if (nums2[i] < st.top())
{
st.push(nums2[i]);
}else{
while (!st.empty() && nums2[i] > st.top())
{
int tmp = st.top();
if (map.find(tmp) != map.end())
{
int pos = map[tmp];
result[pos] = nums2[i];
}
st.pop();
}
st.push(nums2[i]);
}
}
return result;
}
};
503. 下一个更大元素 II
#include <iostream>
#include <vector>
#include <string>
#include <unordered_set>
#include <unordered_map>
#include <stack>
using namespace std;
class Solution {
public:
vector<int> nextGreaterElements(vector<int>& nums) {
vector<int> result(nums.size(),-1);
stack<int> st;
st.push(0);
for (int i = 1; i < nums.size() * 2; i++)
{
int index = i % nums.size();
if (nums[index] <= nums[st.top()])
{
st.push(index);
}else{
while (!st.empty() && nums[index] > nums[st.top()])
{
result[st.top()] = nums[index];
st.pop();
}
st.push(index);
}
}
return result;
}
};
并查集
547. 省份数量
使用深度优先搜索和广度优先搜索还有并查集
深度优先搜索：
class Solution {
public:
void dfs(vector<vector<int>>& isConnected, vector<int>& visited, int cities, int i) {
for (int j = 0; j < cities; j++) {
if (isConnected[i][j] == 1 && !visited[j]) {
visited[j] = 1;
dfs(isConnected, visited, cities, j);
}
}
}
int findCircleNum(vector<vector<int>>& isConnected) {
int cities = isConnected.size();
vector<int> visited(cities);
int provinces = 0;
for (int i = 0; i < cities; i++) {
if (!visited[i]) {
dfs(isConnected, visited, cities, i);
provinces++;
}
}
return provinces;
}
};
广度优先搜索：
class Solution {
public:
int findCircleNum(vector<vector<int>>& isConnected) {
int n = isConnected.size();
int result = 0;
vector<bool> check(n,false);
queue<int> que;
for (int i = 0; i < n; i++)
{
if(!check[i]){
que.push(i);
while (!que.empty())
{
int tmp = que.front();
que.pop();
check[tmp] = true;
for (int j = 0; j < n; j++)
{
if(isConnected[tmp][j] && !check[j]){
que.push(j);
}
}
}
result++;
}
}
return result;
}
};
200. 岛屿数量
class Solution {
public:
vector<vector<bool>> check;
void dfs(vector<vector<char>>& grid,int x,int y){
int n = grid.size();
int m = grid[0].size();
if(x >= n || x < 0 || y <0 || y>=m ||check[x][y] == true || grid[x][y] == '0'){
return;
}
check[x][y] = true;
dfs(grid,x+1,y);
dfs(grid,x-1,y);
dfs(grid,x,y+1);
dfs(grid,x,y-1);
}
int numIslands(vector<vector<char>>& grid) {
int n = grid.size();
int m = grid[0].size();
check = vector<vector<bool>>(n,vector<bool>(m,false));
int result = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if(grid[i][j] == '1' && check[i][j] == false){
result++;
dfs(grid,i,j);
}
}
}
return result;
}
};
684. 冗余连接
滑动窗口
209. 长度最小的子数组
class Solution {
public:
int minSubArrayLen(int target, vector<int>& nums) {
int fast = 0,slow = 0;
int result = __INT_MAX__;
int n = nums.size();
int sum = 0;
while (fast < n)
{
sum += nums[fast];
while (sum >= target)
{
int len = fast - slow + 1;
result = result > len ? len : result;
sum -= nums[slow++];
}
fast++;
}
return result;
}
};
3. 无重复字符的最长子串
class Solution {
public:
int lengthOfLongestSubstring(string s) {
unordered_set<char> set;
int slow = 0;
int fast = 0;
int result = 0;
while(fast < s.size()){
while(set.find(s[fast]) != set.end()){
set.erase(s[slow]);
slow++;
}
if(set.find(s[fast]) == set.end()){
set.insert(s[fast]);
fast++;
}
result = max(result,fast - slow);
}
return result;
}
};
1004. 最大连续1的个数 III
class Solution {
public:
int longestOnes(vector<int>& nums, int k) {
int slow = 0, fast = 0;
int result = 0,cnt = 0;
while(fast < nums.size()){
if(nums[fast++] == 0) {
cnt++;
}
while(cnt > k){
if(nums[slow] == 0){
cnt--;
}
slow++;
}
result = max(result,fast - slow);
}
return result;
}
};
1208. 尽可能使字符串相等
class Solution {
public:
int equalSubstring(string s, string t, int maxCost) {
vector<int> dif(s.size(),0);
for (int i = 0; i < s.size(); i++)
{
dif[i] = abs(s[i] - t[i]);
}
int sum = 0;
int result = -1;
int slow = 0;
for (int i = 0; i < s.size(); i++)
{
sum += dif[i];
while(sum > maxCost){
sum -= dif[slow++];
}
result = max(result,i-slow+1);
}
return result;
}
};
前缀和
724.寻找数组的中心下标
class Solution {
public:
int pivotIndex(vector<int>& nums) {
int sum = 0;
for(int num : nums){
sum+=num;
}
int path = 0;
for(int i = 0; i < nums.size(); i++){
bool flag = ((sum - nums[i]) % 2) == 0;
int tmp = (sum - nums[i])/2;
if(flag){
if(path == tmp ){
return i;
}
}
path += nums[i];
}
return -1;
}
};
#include <iostream>
#include <vector>
using namespace std;
class Solution {
public:
int pivotIndex(vector<int>& nums) {
vector<int> presum(nums.size()+1);
presum[0] = nums[0];
int sum = nums[0];
for (int i = 1; i < nums.size(); i++)
{
presum[i] = presum[i - 1] + nums[i];
sum += nums[i];
}
if(sum == nums[0]) return 0;
for (int i = 1; i < nums.size(); i++)
{
if(2 * presum[i-1] + nums[i] == sum){
return i;
}
}
return -1;
}
};
560. 和为 K 的子数组
class Solution {
public:
//int preSum[20010];
//该函数计算前缀和
void init(const vector<int>& v,vector<int> &preSum) {
for (int i = 0; i < v.size(); i++) {
preSum[i + 1] = preSum[i] + v[i];
}
return;
}
int subarraySum(vector<int>& nums, int k) {
//初始化前缀和.
vector<int> preSum(nums.size() + 1);
init(nums,preSum);
//开启哈希表 哈希表的记录意义是 记录等于key的前缀和有多少个
unordered_map<int, int> mm;
//记录 前缀和的首个元素
mm[0]=1;
int ans = 0;
//遍历前缀和 假设sum[x]已经得到了， 我们查找 sum[x]-sum[y] =K中的sum[y]
for (int i = 1; i <= nums.size(); i++) {
//将 sum[x]-sum[y] =K方程变换一下 也就是要找sum[y] = sum[x]-k
//也就是 要找preSum[i]-k;
int find = preSum[i] -k;
//直接从哈希表中 有没有记录匹配这个find值的前缀和
if (mm.count(find) != 0) {
//如果有 就记录
//也就是记录 有几个匹配 Presum[i] - find = K
ans += mm[find];
}
//遍历的过程中 遍历完的前缀和元素要记录进哈希表
mm[preSum[i]]++;
}
return ans;
}
};
437. 路径总和 III
1248. 统计「优美子数组」
差分
1094. 拼车
class Solution {
public:
bool carPooling(vector<vector<int>>& trips, int capacity) {
vector<int> dif(1001,0);
vector<int> presum(1001,0);
int n = trips.size();
for (int i = 0; i < n; i++)
{
dif[trips[i][1]] += trips[i][0];
dif[trips[i][2]] -= trips[i][0];
}
presum[0] = dif[0];
if(presum[0] > capacity) return false;
for (int i = 1; i < 1001; i++)
{
presum[i] = presum[i-1] + dif[i];
if (presum[i] > capacity)
{
return false;
}
}
return true;
}
};
121. 买卖股票的最佳时机
122. 买卖股票的最佳时机 II
拓扑排序
210. 课程表 II
字符串
5. 最长回文子串
class Solution {
public:
string longestPalindrome(string s) {
int n = s.size();
vector<vector<bool>> dp(n,vector<bool>(n,false));
int len = -1;
pair<int,int> path;
for (int i = n-1; i > -1; i--)
{
for (int j = i; j < n; j++)
{
if (s[i] == s[j])
{
if (j-i <= 1)
{
dp[i][j] = true;
}else
{
if (dp[i+1][j-1] == 1)
{
dp[i][j] = true;
}
}
}
if (dp[i][j])
{
if (j-i+1 > len)
{
len = j - i + 1;
path.first = i;
path.second = len;
}
}
}
}
string str;
str = s.substr(path.first,path.second);
return str;
}
};
20. 有效的括号
#include <string>
#include <stack>
using namespace std;
class Solution {
public:
bool isValid(string s) {
stack<char> st;
if (s.size() % 2 != 0)
{
return false;
}
for (int i = 0; i < s.size(); i++)
{
if (s[i] == '(')
{
st.push(')');
}else if (s[i] == '{')
{
st.push('}');
}else if (s[i] == '[')
{
st.push(']');
}else if (st.empty() || s[i] != st.top())
{
return false;
}else
{
st.pop();
}
}
return st.empty();
}
};
43. 字符串相乘
93. 复原 IP 地址
二分查找
33. 搜索旋转排序数组
class Solution {
public:
int search(vector<int>& nums, int target) {
int n = (int)nums.size();
if (!n) {
return -1;
}
if (n == 1) {
return nums[0] == target ? 0 : -1;
}
int l = 0, r = n - 1;
while (l <= r) {
int mid = (l + r) / 2;
if (nums[mid] == target) return mid;
if (nums[0] <= nums[mid]) {
if (nums[0] <= target && target < nums[mid]) {
r = mid - 1;
} else {
l = mid + 1;
}
} else {
if (nums[mid] < target && target <= nums[n - 1]) {
l = mid + 1;
} else {
r = mid - 1;
}
}
}
return -1;
}
};
二分查找可以用来作为分割点，来分割相关的矩阵
34. 在排序数组中查找元素的第一个和最后一个位置
class Solution {
public:
int searchleft(vector<int>& nums, int target){
int left = 0, right = nums.size()-1;
while (left <= right)
{
int mid = (left + right) /2 ;
if (nums[mid] < target)
{
left = mid + 1;
}
else if (nums[mid] >= target)
{
right = mid - 1;
}
}
return right;
}
int searchright(vector<int>& nums, int target){
int left = 0, right = nums.size()-1;
while (left <= right)
{
int mid = (left + right)/2;
if (nums[mid] > target)
{
right = mid - 1;
}
else if (nums[mid] <= target)
{
left = mid + 1;
}
}
return left;
}
vector<int> searchRange(vector<int>& nums, int target) {
int leftboard = -1;
int rightboard = -1;
leftboard = searchleft(nums,target);
rightboard = searchright(nums,target);
if (rightboard - leftboard > 1)
{
return {leftboard+1,rightboard-1};
}
return {-1,-1};
}
};
BFS
127. 单词接龙
class Solution {
public:
bool isstr(string Word1,string Word2){
int n = Word1.size();
int sum = 0;
for(int i = 0; i < n; i++){
if(Word1[i] != Word2[i]){
sum++;
}
}
return sum == 1;
}
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
queue<string> que;
int len =wordList.size();
// unordered_map<string,int> check;
vector<bool> check(len,false);
bool flag = false;
int result = 0;
que.push(beginWord);
while(!que.empty()){
int size = que.size();
for(int k = 0; k < size; k++){
string tmp = que.front();
que.pop();
for(int i = 0; i < len; i++){
if(isstr(tmp, wordList[i]) && !check[i]){
check[i] = true;
que.push(wordList[i]);
if(wordList[i] == endWord){
flag = true;
break;
}
}
}
if(flag) break;
}
result++;
if(flag) return result+1;
}
return 0;
}
};
class Solution {
public:
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
// 将vector转成unordered_set，提高查询速度
unordered_set<string> wordSet(wordList.begin(), wordList.end());
// 如果endWord没有在wordSet出现，直接返回0
if (wordSet.find(endWord) == wordSet.end()) return 0;
// 记录word是否访问过
unordered_map<string, int> visitMap; // <word, 查询到这个word路径长度>
// 初始化队列
queue<string> que;
que.push(beginWord);
// 初始化visitMap
visitMap.insert(pair<string, int>(beginWord, 1));
while(!que.empty()) {
string word = que.front();
que.pop();
int path = visitMap[word]; // 这个word的路径长度
for (int i = 0; i < word.size(); i++) {
string newWord = word; // 用一个新单词替换word，因为每次置换一个字母
for (int j = 0 ; j < 26; j++) {
newWord[i] = j + 'a';
if (newWord == endWord) return path + 1; // 找到了end，返回path+1
// wordSet出现了newWord，并且newWord没有被访问过
if (wordSet.find(newWord) != wordSet.end()
&& visitMap.find(newWord) == visitMap.end()) {
// 添加访问信息
visitMap.insert(pair<string, int>(newWord, path + 1));
que.push(newWord);
}
}
}
}
return 0;
}
};
139. 单词拆分
class Solution {
public:
bool wordBreak(string s, vector<string>& wordDict) {
unordered_set<string> set(wordDict.begin(),wordDict.end());
int n = s.size();
vector<int> dp(n+1,0);
dp[0] = 1;
for(int i = 1; i <= n; i++){
for(int j = 0; j < i; j++){
string sub = s.substr(j,i-j);
if(dp[j] && set.find(sub) != set.end()){
dp[i] = 1;
}
}
}
return dp[n] == 1;
}
};
简单的动态规划习题~
130. 被围绕的区域
class Solution {
public:
int n, m;
void dfs(vector<vector<char>>& board, int x, int y) {
if (x < 0 || x >= n || y < 0 || y >= m || board[x][y] != 'O') {
return;
}
board[x][y] = 'A';
dfs(board, x + 1, y);
dfs(board, x - 1, y);
dfs(board, x, y + 1);
dfs(board, x, y - 1);
}
void solve(vector<vector<char>>& board) {
n = board.size();
if (n == 0) {
return;
}
m = board[0].size();
//只遍历边界的节点，其它都不需要遍历
for (int i = 0; i < n; i++) {
dfs(board, i, 0);
dfs(board, i, m - 1);
}
for (int i = 1; i < m - 1; i++) {
dfs(board, 0, i);
dfs(board, n - 1, i);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < m; j++) {
if (board[i][j] == 'A') {
board[i][j] = 'O';
} else if (board[i][j] == 'O') {
board[i][j] = 'X';
}
}
}
}
};
529. 扫雷游戏
815.公交路线
DFS
200. 岛屿数量
class Solution {
public:
vector<vector<bool>> check;
void dfs(vector<vector<char>>& grid,int x,int y){
int n = grid.size();
int m = grid[0].size();
if(x >= n || x < 0 || y <0 || y>=m ||check[x][y] == true || grid[x][y] == '0'){
return;
}
check[x][y] = true;
dfs(grid,x+1,y);
dfs(grid,x-1,y);
dfs(grid,x,y+1);
dfs(grid,x,y-1);
}
int numIslands(vector<vector<char>>& grid) {
int n = grid.size();
int m = grid[0].size();
check = vector<vector<bool>>(n,vector<bool>(m,false));
int result = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if(grid[i][j] == '1' && check[i][j] == false){
result++;
dfs(grid,i,j);
}
}
}
return result;
}
};
695. 岛屿的最大面积
class Solution {
public:
vector<vector<bool>> check;
int path = 0 ;
void dfs(vector<vector<int>>& grid,int x,int y){
int n = grid.size();
int m = grid[0].size();
if(x >= n || x < 0 || y <0 || y>=m || check[x][y] == true || grid[x][y] == 0){
return ;
}
check[x][y] = true;
path++;
dfs(grid,x+1,y);
dfs(grid,x-1,y);
dfs(grid,x,y+1);
dfs(grid,x,y-1);
}
int maxAreaOfIsland(vector<vector<int>>& grid) {
int n = grid.size();
int m = grid[0].size();
check = vector<vector<bool>>(n,vector<bool>(m,false));
int result = 0;
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if(grid[i][j] == 1 && check[i][j] == false){
dfs(grid,i,j);
result = max(result,path);
path = 0;
}
}
}
return result;
}
};
934. 最短的桥
先DFS找到一个岛屿，然后将岛屿中的坐标扔到队列里面，最后做一个BFS。
#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
using namespace std;
class Solution {
public:
queue<pair<int,int>> que;
vector<vector<bool>> check;
vector<vector<int>> dirs;
int n,m;
void dfs(vector<vector<int>>& grid,int x,int y){
if(x < 0 || x >= n || y < 0|| y >= m || grid[x][y] == 0 || check[x][y] == true){
return;
}
check[x][y] = true;
que.push({x,y});
dfs(grid,x+1,y);
dfs(grid,x-1,y);
dfs(grid,x,y+1);
dfs(grid,x,y-1);
}
int bfs(vector<vector<int>>& grid){
int result1 = 0;
while (!que.empty())
{
int size = que.size();
for (int i = 0; i < size; i++)
{
pair<int,int> tmp = que.front();
que.pop();
for (int k = 0; k < 4; k++)
{
int x = tmp.first + dirs[k][0];
int y = tmp.second + dirs[k][1];
// if ( x >= 0 && y >= 0 && x < n && y <m)
// {
// if(check[x][y] == true) continue;
// if(grid[x][y] == 1){
// return result1;
// }else{
// que.push({x,y});
// check[x][y] = true;
// }
// }
if (x < 0 || x >= n || y < 0|| y >= m || check[x][y] == true)
{
continue;
}
if (grid[x][y] == 1)
{
return result1;
}
que.push({x,y});
check[x][y] = true;
}
}
result1++;
}
return result1;
}
int shortestBridge(vector<vector<int>>& grid) {
n = grid.size();
m = grid[0].size();
int result ;
dirs = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
check = vector<vector<bool>>(n,vector<bool>(m,false));
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
if(grid[i][j] == 1){
// check[i][j] = true;
dfs(grid,i,j);
result = bfs(grid);
return result;
}
}
}
return -1;
}
};
685. 冗余连接 II
1102. 得分最高的路径
531. 孤独像素 I
533. 孤独像素 II
113. 路径总和 II.
332. 重新安排行程
337. 打家劫舍 III
动态规划
213. 打家劫舍 II
123. 买卖股票的最佳时机 III
62. 不同路径
class Solution {
public:
int uniquePaths(int m, int n) {
vector<vector<int>> dp(m,vector<int>(n,0));
dp[0][0] = 1;
for(int i =1; i < m;i++){
dp[i][0] = 1;
}
for(int i =1; i < n;i++){
dp[0][i] = 1;
}
for(int i = 1; i < m; i++){
for(int j = 1; j < n; j++){
dp[i][j] =dp[i-1][j]+dp[i][j-1];
}
}
return dp[m-1][n-1];
}
};
63. 不同路径 II
class Solution {
public:
int uniquePathsWithObstacles(vector<vector<int>>& obstacleGrid) {
int n = obstacleGrid.size();
int m = obstacleGrid[0].size();
vector<vector<int>> dp(n,vector<int>(m,0));
for (int i = 0; i < n; i++)
{
if(obstacleGrid[i][0] == 1) break;
dp[i][0] = 1;
}
for (int i = 0; i < m; i++)
{
if(obstacleGrid[0][i]== 1) break;
dp[0][i] = 1;
}
for (int i = 1; i < n; i++)
{
for (int j = 1; j < m; j++)
{
if(obstacleGrid[i][j] == 1){
// dp[i][j] = 0;
continue;
}
dp[i][j] = dp[i-1][j]+dp[i][j-1];
}
}
return dp[n-1][m-1];
}
};
361. 轰炸敌人
1230. 抛掷硬币
贪心算法
55. 跳跃游戏
class Solution {
public:
bool canJump(vector<int>& nums) {
int rowboard = 0;
for (int i = 0; i < nums.size(); i++)
{
if(i <= rowboard){
rowboard = max(rowboard,i+nums[i]);
if(rowboard >= nums.size()-1){
return true;
}
}
}
return false;
}
};
435. 无重叠区间
621. 任务调度器
452. 用最少数量的箭引爆气球
字典树
820. 单词的压缩编码
208. 实现 Trie (前缀树)
648. 单词替换
