youngyangyang04 / leetcode-master Goto Github PK
View Code? Open in Web Editor NEW《代码随想录》LeetCode 刷题攻略:200道经典题目刷题顺序,共60w字的详细图解,视频难点剖析,50余张思维导图,支持C++,Java,Python,Go,JavaScript等多语言版本,从此算法学习不再迷茫!🔥🔥 来看看,你会发现相见恨晚!🚀
《代码随想录》LeetCode 刷题攻略:200道经典题目刷题顺序,共60w字的详细图解,视频难点剖析,50余张思维导图,支持C++,Java,Python,Go,JavaScript等多语言版本,从此算法学习不再迷茫!🔥🔥 来看看,你会发现相见恨晚!🚀
1、判断==的地方需要改成equals比较内容是否相同
2、isOpe函数可以加一行注释解释为什么需要判断length==1,因为有负数这样的例子,比如-11,不能算作运算符。
这个网页已经做得非常棒了,非常精美了,如果能够点击链接直接跳转的话就更好啦😁
原版代码跑完提交失败,应该是return的位置错了,更改后提交成功
class Solution(object):
def restoreIpAddresses(self, s):
ans = []
path = []
def backtrack(path, startIndex):
if len(path) == 4:
if startIndex == len(s):
ans.append(".".join(path[:]))
return # 更改此处
for i in range(startIndex, min(startIndex+4, len(s)+1)): # 剪枝
string = s[startIndex:i+1]
if not 0 <= int(string) <= 255:
continue
if not string == "0" and not string.lstrip('0') == string:
continue
path.append(string)
backtrack(path, i+1)
path.pop()
backtrack(s, 0)
return ans
难道两个链表最终会共用交叉节点吗?
为什么示意图的两个链表的最后一个node居然会不一样?一个2一个4?
究竟为什么会出现两次 sum = 0???
class Solution {
public:
int minSubArrayLen(int s, vector& nums) {
int result = INT32_MAX; // 最终的结果
int sum = 0; // 子序列的数值之和
int subLength = 0; // 子序列的长度
for (int i = 0; i < nums.size(); i++) { // 设置子序列起点为i
sum = 0;
动态规划的空间代价应该是可以优化至O(n)的,因为障碍物矩阵没有修改,只修改了dp数组
个人感觉这个也不完全是后序遍历,因为每到一棵树上,都会先判断根节点的值是否相等,是否可以理解为是一种先序遍历和剪枝的操作
期待回溯框架解地图问题的模板
通过交换指针位置来让指针达到同一个位置
public class Solution {
public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
if (headA == null || headB == null) return null;
ListNode pA = headA;
ListNode pB = headB;
while (true) {
if (pA == null && pB == null) return null;
if (pA == null) {
pA = headB;
}
if (pB == null) {
pB = headA;
}
if (pA == pB) return pB;
pA = pA.next;
pB = pB.next;
}
}
}
这样做能达到目的的原因是:当我们先将身高从低到高排序,任意元素往后移动,并不会影响后面元素的合理性。
并且,不需要额外空间存储,也就不需要是用链表。空间复杂度是O(1)
class Solution {
static bool peopleCompare(vector<int>& pre, vector<int>& next) {
if (pre[0] != next[0]) return pre[0] < next[0];
else
{
return pre[1] > next[1];
}
}
public:
vector<vector<int>> reconstructQueue(vector<vector<int>>& people) {
sort(people.begin(), people.end(), peopleCompare);
int preHeight = people[people.size() - 1][0];
for (int i = people.size() - 1; i >= 0; i--) {
int swapTime = people[i][1];
for (int j = 0; j < swapTime; j++) {
swap(people[i + j], people[i + j + 1]);
}
}
return people;
}
};
您好,能出一个位运算专栏嘛!
class Solution {
public:
int combinationSum4(vector& nums, int target) {
vector dp(target+1, 0);
for (int t = 0; t < target + 1; ++ t) {
for (int x : nums) {
if (t >=x && dp[t] <= INT_MAX - dp[t-x]) {
if (t > x) dp[t] += dp[t-x];
if (t == x && dp[t] <= INT_MAX - 1) {
dp[t] += 1; //当前这个数字可以组成一个集合 满足target
}
}
}
}
return dp[target];
}
};
个人感觉还可以进一步优化,有错望指正,力扣已AC。
class Solution {
public int maxProfit(int k, int[] prices) {
if(prices.length==0)return 0;
int[] res=new int[2*k+1];
for (int i = 1; i <2*k ; i+=2) {
res[i]=-prices[0];
}
for (int i = 0; i <prices.length ; i++) {
for (int j = 1; j <2*k ; j+=2) {
res[j]=Math.max(res[j],res[j-1]-prices[i]);
res[j+1]=Math.max(res[j+1],res[j]+prices[i]);
}
}
return res[2*k];
}
}
大神,你好。readme里面的“各个类型的经典题目刷题顺序”内容看不到。请问是什么回事呢?
C++的题解在测试样例
[1000000000, 1000000000, 1000000000, 1000000000]
0
LeetCode会报错溢出Int,
所以需要用(long long)作类型转换
博主,你好。
看了你一系列的算法文章介绍,发现你缺少DFS和BFS的介绍,希望可以补充,谢谢!
word1[i]!=word2[j]时只要考虑两种情况
dp[i-1][j-1]+2包含在上述情况中了
if(word1[i]==word2[j]){
dp[i][j]=dp[i-1][j-1];
}
else{
dp[i][j]=min(dp[i-1][j],dp[i][j-1])+1;
}
原作的写法感觉比较偏Java,其中部分语法不符合Python的新特性。为了凸显Python语法的简便性,附上改写后的Python代码。
# Definition for singly-linked list.
# class ListNode:
# def __init__(self, val=0, next=None):
# self.val = val
# self.next = next
class Solution:
def removeElements(self, head: ListNode, val: int) -> ListNode:
dummy_head = ListNode(0, head)
cur = dummy_head
while cur.next:
if cur.next.val == val:
cur.next = cur.next.next
else:
cur = cur.next
return dummy_head.next
解数独问题可以看成每次递归解决一个空格,也就是从1-9中选择一个输入填入当前空格,然后递归进去下一个空格。判断行列小正方格中是否出现也可以使用3个二维数组解决,避免使用for循环。代码如下:
// #37 解数独
class Solution {
private:
vector<vector<int>> usedRowNum = vector<vector<int>>(9, vector<int>(9));
vector<vector<int>> usedColNum = vector<vector<int>>(9, vector<int>(9));
vector<vector<int>> usedQurNum = vector<vector<int>>(9, vector<int>(9));
vector<vector<char>> result;
bool solveSudoIter(vector<vector<char>>& board, int curRow, int curCol) {
if (curRow == 9)
{
result = board;
return true;
}
if (board[curRow][curCol] != '.') {
return solveSudoIter(board, curRow + (curCol + 1) / 9, (curCol + 1) % 9);
}
for (int num = 0; num < 9; num++) {
if (usedRowNum[curRow][num] == 1) continue;
if (usedColNum[curCol][num] == 1) continue;
int curQur = 3 * (curRow / 3) + curCol / 3;
if (usedQurNum[curQur][num] == 1) continue;
//push
usedRowNum[curRow][num] = 1;
usedColNum[curCol][num] = 1;
usedQurNum[curQur][num] = 1;
board[curRow][curCol] = '1' + num;
// iter
bool ifFound = solveSudoIter(board, curRow + (curCol + 1) / 9, (curCol + 1) % 9);
if (ifFound) return true;
//pop back
usedRowNum[curRow][num] = 0;
usedColNum[curCol][num] = 0;
usedQurNum[curQur][num] = 0;
board[curRow][curCol] = '.';
}
return false;
}
public:
void solveSudoku(vector<vector<char>>& board) {
for (int row = 0; row < 9; row++) {
for (int col = 0; col < 9; col++)
{
if (board[row][col] == '.') continue;
int curNum = board[row][col] - '1';
usedRowNum[row][curNum] = 1;
usedColNum[col][curNum] = 1;
int curQur = 3 * (row / 3) + col/3;
usedQurNum[curQur][curNum] = 1;
}
}
solveSudoIter(board, 0, 0);
}
};
对于 0-1 背包问题上的滑动数组写法时,我有一个自己的理解,不知道是否正确。
假设有物体 j 个,每个物体的价值为value[j],重量为weight[ j ],那么对于一个背包 dp[ i ]
可以知道
dp[ i ] = max{dp[ i ], dp[ i - weight[ j ] + value[ j ]]}
相当于是说,这个背包可以由多个小背包推导出来,由哪几个小背包推导出来?就是 i - weight[ i ] 的这几个小背包,然后在里面挑选一个最大的值,初始化的过程应该也是相似的,即 dp[0] = 0;然后如果 i - weight[ i ] <= 0 说明没有这种小背包,直接continue;
您觉得这样理解可以吗~
https://github.com/youngyangyang04/leetcode-master/blame/master/problems/0925.%E9%95%BF%E6%8C%89%E9%94%AE%E5%85%A5.md#L73
while(j < typed.size() && typed[j] == typed[j - 1]) j++; if (name[i] == typed[j]) { // j跨越重复项之后再次和name[i]匹配 j++; i++; // 相同则同时向后匹配
测试用例为name:"kikcxmvzi" typed:"kiikcxxmmvvzz"
执行完 while循环后j= 13,再执行下一行代码python会报边界溢出,C++代码却没报错???
class Solution {
public:
int dirs[4][2] = {{0,1}, {1,0}, {0,-1},{-1,0}};
vector<vector<int>> generateMatrix(int n) {
vector<vector<int>> M;
M.resize(n, vector<int>(n, 0));
int final_num = n*n;
int start = 1;
int i = 0;
int r,c;
r=c=0;
while(start <= final_num){
M[r][c] = start++;
if(r + dirs[i][0] < n &&
c + dirs[i][1] < n &&
r + dirs[i][0] >= 0 &&
c + dirs[i][1] >= 0 &&
M[r + dirs[i][0]][c + dirs[i][1]] == 0){
r = r + dirs[i][0];
c = c + dirs[i][1];
}else{
i = (i+1) % 4;
r = r + dirs[i][0];
c = c + dirs[i][1];
}
}
return M;
}
};
完全没有必要将null添加到栈中,因为执行过if中的语句后,下一次循环必然执行else中的语句。
所以可以将代码放到一次循环中。
class Solution {
public List<Integer> preorderTraversal(TreeNode root) {
List<Integer> res = new ArrayList<>();
if(root==null) return res;
Deque<TreeNode> deque = new LinkedList<>();
TreeNode cur = root;
deque.push(cur);
while (!deque.isEmpty()){
cur = deque.peek();
if (cur!=null){
deque.pop();
if (cur.right!=null) deque.push(cur.right);
if (cur.left!=null) deque.push(cur.left);
deque.push(cur);
cur = deque.peek();
deque.pop();
if (cur != null) res.add(cur.val);
}
}
return res;
}
}
链接:https://github.com/youngyangyang04/leetcode-master/blob/master/problems/0063.%E4%B8%8D%E5%90%8C%E8%B7%AF%E5%BE%84II.md
这一块的Java代码,可以使用我这个,和你的比较贴合,也对容易进坑的地方加了注释
public int uniquePathsWithObstacles(int[][] obstacleGrid) {
//起点可能就是障碍物,所以要特判,不特判也可以,看下面
// if (obstacleGrid[0][0] == 1){
// return 0;
// }
int m = obstacleGrid.length, n = obstacleGrid[0].length;
int[][] dp = new int[m][n];
//遇到障碍了,下面的就不用执行了
for (int i = 0; i < m && obstacleGrid[i][0] == 0; i++) {
dp[i][0] = 1;
}
//因为dp[0][0]上一个已经赋值了,所以这里要从1开始(这里也从0开始,就不需要特判)
for (int i = 0; i < n && obstacleGrid[0][i] == 0; i++) {
dp[0][i] = 1;
}
for (int i = 1; i < m; i++) {
for (int j = 1; j < n; j++) {
//如果这里是障碍物,就取0
//因为默认就是0,所以可以不赋值,节省时间
// dp[i][j] = obstacleGrid[i][j] == 1 ? 0 : dp[i - 1][j] + dp[i][j - 1];
if (obstacleGrid[i][j] == 1) {
continue;
}
dp[i][j] = dp[i - 1][j] + dp[i][j - 1];
}
}
return dp[m - 1][n - 1];
}
问题在于intervals排序中if判断条件错误,应该对o1[1]和o2[1]进行判断,而不是o1[0]和o2[0]。
修改后可以通过所有测试,
class Solution {
public int eraseOverlapIntervals(int[][] intervals) {
if (intervals.length < 2) return 0;
Arrays.sort(intervals, new Comparator<int[]>() {
@Override
public int compare(int[] o1, int[] o2) {
if (o1[1] != o2[1]) {
return Integer.compare(o1[1],o2[1]);
} else {
return Integer.compare(o2[0],o1[0]);
}
}
});
int count = 0;
int edge = intervals[0][1];
for (int i = 1; i < intervals.length; i++) {
if (intervals[i][0] < edge) {
count++;
} else {
edge = intervals[i][1];
}
}
return count;
}
}
您好,您的项目非常的棒。我想问一下刷题的顺序是从哪里看。是problems文件夹下面开始吗。我看了下,里面都是按照leetcode的顺序排列而已,以组合的题为例子,应该是先放组合77这道题,可是在刷的过程中39就先出现了。有点困惑
先做141 再来142好些吧
翻转二叉树可用中序遍历来做,只是翻转之后依然进入左子树递归
class Solution {
public:
void invert (TreeNode* cur){
if (cur!=nullptr){
invert(cur->left);
swap(cur->left, cur->right);
invert(cur->left);
}
}
TreeNode* invertTree(TreeNode* root) {
invert(root);
return root;
}
};
if判断的内容里应该在最后加上break;因为到这里就有结果了,否则浪费时间
修正为return list(result_set)
在left = ...,right =... ,格式中,判断是否是平衡树时,是可以提前结束的,不需要遍历整个二叉树呀。
class Solution {
public boolean canConstruct(String ransomNote, String magazine) {
if(magazine.length()==0) return ransomNote.length==0;
int[] leter = new int[26];
for(char c:magazine.toCharArray()){
leter[c-'a'] += 1;
}
for(char a:ransomNote.toCharArray()){
leter[a-'a'] -= 1;
if(leter[a-'a']<0)
return false;
}
return true;
}
}
最近按照大佬的思路刷题进步很快,但是重新刷到编辑距离的时候我的理解有出入,希望大佬指正
操作一:word1增加一个元素,使其word1[i - 1]与word2[j - 1]相同,那么就是以下标i-2为结尾的word1 与 j-1为结尾的word2的最近编辑距离 加上一个增加元素的操作。
即 dp[i][j] = dp[i - 1][j] + 1;
这里dp[i - 1][j]表示以下标i - 2结尾的word1已经变换为以j - 1为结尾的word2的最近编辑距离,由于word1的i - 1下标元素与word2的j -1元素不等,所以需要删除word1中i - 1位置的元素,即word1删除一个元素
操作二:word2添加一个元素,使其word1[i - 1]与word2[j - 1]相同,那么就是以下标i-1为结尾的word1 与 j-2为结尾的word2的最近编辑距离 加上一个增加元素的操作。
即 dp[i][j] = dp[i][j - 1] + 1;
同理,因为word1中到i - 1位置的全部元素已经变换为了以j - 2为下标的word2,由于word1中i - 1位置的元素和word2中j - 1位置的元素不相等,所以需要对word1增加word2中j - 1位置的元素,即word1增加一个元素或者word2减少一个元素
我个人感觉单词拆分归到背包问题里有点牵强?
其实直接用dp去解释更直观一些
如果两个皇后位于某条斜线,那么只有两种情况:1.两个皇后的行-列的差相等。2.两个皇后的行+列的和相等,根据这个特性,不难写出如下代码:
// #51 N皇后问题
class Solution {
vector<vector<string>> result;
vector<string> curPath;
void solveNQueensIter(int curRow, int targetRow, vector<int>& usedCol, unordered_set<int>& usedDiff, unordered_set<int>& usedSum) {
if (curRow == targetRow) {
result.emplace_back(curPath);
return;
}
for (int curCol = 0; curCol < targetRow; curCol++) {
if (usedCol[curCol] == 1) continue;
if (usedDiff.find(curRow - curCol) != usedDiff.end()) continue;
if (usedSum.find(curRow + curCol) != usedSum.end()) continue;
string path(targetRow, '.' );
path[curCol] = 'Q';
curPath.emplace_back(path);
usedCol[curCol] = 1;
usedDiff.insert(curRow - curCol);
usedSum.insert(curRow + curCol);
solveNQueensIter(curRow + 1, targetRow, usedCol, usedDiff, usedSum);
usedDiff.erase(curRow - curCol);
usedSum.erase(curRow + curCol);
usedCol[curCol] = 0;
curPath.pop_back();
}
}
public:
vector<vector<string>> solveNQueens(int n) {
vector<int> usedCol(n, 0);
unordered_set<int> usedDiff, usedSum;
solveNQueensIter(0, n, usedCol, usedDiff, usedSum);
return result;
}
};
测试样例中
[100]
-200,
int size = (target + sum) / 2;
在这里应该判断下size是否小于0
int[] dp = new int[size + 1];
感觉卡尔哥那里的解法有点抽象,可以看看我的,应该好理解一些
int minCostClimbingStairs(vector& cost) {
int n = cost.size();
//递归只需要前面两个台阶,所以长度为2的数组就足够了。
int dp[2];
dp[0] = 0;
dp[1] = 0;
//题目说了要爬到顶,也就是离开最高的台阶,所以我们就要爬到循环到=n,加上初始化的两次也就是多一次,正好跳出台阶
for(int i = 2; i <= n; ++i)
{
int tmp = dp[1];
//可以从前一个台阶花费前一个台阶的价格爬一步,也可以从前面第二个台阶花费它的价格爬两部。
dp[1] = min(dp[1] + cost[i-1], dp[0] + cost[i-2]);
dp[0] = tmp;
}
//dp[1]永远是最高的台阶,直接返回即可
return dp[1];
}
希望能更一下图论算法的解题技巧,最近一直摸不到头难,辛苦Carl了!!
A declarative, efficient, and flexible JavaScript library for building user interfaces.
🖖 Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.
TypeScript is a superset of JavaScript that compiles to clean JavaScript output.
An Open Source Machine Learning Framework for Everyone
The Web framework for perfectionists with deadlines.
A PHP framework for web artisans
Bring data to life with SVG, Canvas and HTML. 📊📈🎉
JavaScript (JS) is a lightweight interpreted programming language with first-class functions.
Some thing interesting about web. New door for the world.
A server is a program made to process requests and deliver data to clients.
Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.
Some thing interesting about visualization, use data art
Some thing interesting about game, make everyone happy.
We are working to build community through open source technology. NB: members must have two-factor auth.
Open source projects and samples from Microsoft.
Google ❤️ Open Source for everyone.
Alibaba Open Source for everyone
Data-Driven Documents codes.
China tencent open source team.