怎么制作自己公司网站,租赁网站开发,designer怎么做网站,有没有可以免费的片第一阶段主要就是学习字符串的处理和二叉树的遍历。前一段时间学习了二叉树的遍历#xff0c;记忆还比较深刻#xff0c;这几个题还是比较轻松的做出来了#xff1b;但是像Longest Palindromic Substring这样的题除了简单的字符串处理#xff08;回文判断#xff09;…第一阶段主要就是学习字符串的处理和二叉树的遍历。前一段时间学习了二叉树的遍历记忆还比较深刻这几个题还是比较轻松的做出来了但是像Longest Palindromic Substring这样的题除了简单的字符串处理回文判断还要使用动态规划之类的算法很久以前简单学习了一下动态规划但一段时间不用很快就忘记了。这一题我尝试用暴力来解但很容易就超时了。周末找个时间重新好好学习一下dp
⚠️ 注代码我都是用js写的不是python
DAY 1
3. Longest Substring Without Repeating Characters (medium)
String | Sliding Window Hash Table
/*** param {string} s* return {number}*/
var lengthOfLongestSubstring function(s) {let start 0; // Start of the current windowlet maxLength 0; // Maximum length of substring found so farconst map {}; // Map to store the last index of each characterfor(let end 0; end s.length; end) {const currentChar s[end];// If the character is found in the map and is within the current window,// move the start to the next position after the last occurrence of currentCharif (map[currentChar] start) {start map[currentChar] 1;}// Update the last index of the current charactermap[currentChar] end;// Update maxLength if the current window size is largermaxLength Math.max(maxLength, end - start 1);}return maxLength;
};
5. Longest Palindromic Substring (medium)
勉强通过的brute-force
/*** param {string} s* return {string}*/const isPalindrome (s, l, r) {for (let i l, j r; i j; i, j--) {if(s[i] ! s[j]) return false;}return true;
}
var longestPalindrome function(s) {let longest ;for (let start 0; start s.length; start) {for (let end start; end s.length; end) {let substr s.substring(start, end 1); if (isPalindrome(s, start, end) substr.length longest.length) {longest substr;}}}return longest;
};8. String to Integer (atoi) (medium)
晕 _ 好难cover所有testcase
/*** param {string} s* return {number}*/
var myAtoi function(s) {let i 0, sign 1, result 0, INT_MAX 2**31 - 1, INT_MIN -(2**31);// Ignore leading whitespacewhile (s[i] ) i;// Handle signif (s[i] || s[i] -) {sign s[i] ? 1 : -1;i;}// Convert number and avoid non-digit characterswhile (i s.length s[i] 0 s[i] 9) {result result * 10 (s[i] - 0);i;}// Apply signresult * sign;// Clamp to 32-bit signed integer rangeif (result INT_MIN) return INT_MIN;if (result INT_MAX) return INT_MAX;return result;
};DAY 2
151. Reverse Words in a String (medium)
43. Multiply Strings (medium)
额(⊙﹏⊙)说实话没明白这题是啥意思。 不过题目说Note: You must not use any built-in BigInteger library or convert the inputs to integer directly. 之后再仔细研究一下这题
var multiply function(num1, num2) {return (BigInt(num1) * BigInt(num2)).toString();
};14. Longest Common Prefix (easy)
/*** param {string[]} strs* return {string}*/
var longestCommonPrefix function(strs) {if (strs.length 0) return ;for (let i 0; i strs[0].length; i) {let c strs[0][i];for (let j 1; j strs.length; j) {if (strs[j].length i || strs[j][i] ! c) {return strs[0].slice(0, i);// return strs[0].substring(0, i);}}}return strs[0];
};一点优化先将strs 排序然后直接选取第一个和最后一个比较。 时间复杂度O( m ∗ n m*n m∗n) -- O( n l o g n m nlog_nm nlognm)
var longestCommonPrefix function(strs) {if (strs.length 0) return ;strs.sort();for (let i 0; i strs[0].length; i) {let c strs[0][i];if(strs[0][i] ! strs[strs.length-1][i]) {return strs[0].substring(0, i);}}return strs[0];
};
DAY 3
144. Binary Tree Preorder Traversal (easy)
const traversal function (root, res) {if (root null) return ;res.push(root.val);traversal(root.left, res);traversal(root.right, res);
};var preorderTraversal function (root) {let res [];traversal(root, res);return res;
};94. Binary Tree Inorder Traversal (easy)
var inorderTraversal function(root) {let res [];traversal(root, res);return res;
};const traversal function (root, res) {if (root null) return;traversal(root.left, res);res.push(root.val);traversal(root.right, res);
};102. Binary Tree Level Order Traversal (medium)
用队列先进先出
const levelOrderTraversal function(root, res, queue) {if(root null) return [];queue.push(root);while(queue.length ! 0) {const length queue.length; // the length of root array: 7let level []; // store each level arrayfor(let i 0; i length; i) {let node queue.shift(); // take the first num, i.e. the root nodelevel.push(node.val); if(node.left) {queue.push(node.left);} if(node.right) {queue.push(node.right);}}res.push(level);}return res;
}var levelOrder function(root) {let res [], queue [];levelOrderTraversal(root, res, queue);return res;
};DAY 4
103. Binary Tree Zigzag Level Order Traversal (medium)
用层序遍历然后隔一行翻转
var zigzagLevelOrder function(root) {let res [], queue [];let zigzag 1if(root null) return [];queue.push(root);while(queue.length ! 0) {const length queue.length;let level [];for(let i 0; i length; i) {let node queue.shift();level.push(node.val); if(node.left) queue.push(node.left);if(node.right) queue.push(node.right);}if(zigzag 1) {res.push(level);}else {res.push(level.reverse());}zigzag -zigzag;}return res;
};236. Lowest Common Ancestor of a Binary Tree (medium)
自底向上查找 - 回溯 - 后序遍历左右中
var lowestCommonAncestor function(root, p, q) {function dfs(root, q, p) {if (root q || root p || root null) return root;let left dfs(root.left, q, p)let right dfs(root.right, q, p)if(left ! null right ! null) return root;else if(left ! null right null) return left;else if(left null right ! null) return right;else return null;}return dfs(root, q, p);
};104. Maximum Depth of Binary Tree (easy)
层序遍历求层数用dfs应该也能做…
var maxDepth function(root) {let queue [];let count 0;queue.push(root);if (root null) return count;while(queue.length ! 0) {let length queue.length;for(let i 0; i length; i){let node queue.shift();if(node.left) {queue.push(node.left);}if(node.right) {queue.push(node.right);}}count;}return count;
};
