前言
最近在leetcode上做算法题，记录一下心得
（我的答案是用js写的）
由易至难
第一题：104 Maximum Depth of Binary Tree
Given a binary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
解
var maxDepth = function(root) {
if(!root){return 0;}
return Math.max(maxDepth(root.left),maxDepth(root.right))+1;
};
第二题 226. Invert Binary Tree
Invert a binary tree.
4 / \ 2 7 / \ / \ 1 3 6 9 to
4 / \ 7 2 / \ / \ 9 6 3 1
Trivia:
``
This problem was inspired by this original tweet by Max Howell:
Google: 90% of our engineers use the software you wrote (Homebrew), but you can’t invert a binary tree on a whiteboard so fuck off.
``
解
var invertTree = function(root) {
if (!root) {
return root;
}
const { right, left } = root;
root.left = invertTree(right);
root.right = invertTree(left);
return root;
};
###第三题 695. Max Area of Island
Given a non-empty 2D array grid of 0’s and 1’s, an island is a group of 1’s (representing land) connected 4-directionally (horizontal or vertical.) You may assume all four edges of the grid are surrounded by water.
Find the maximum area of an island in the given 2D array. (If there is no island, the maximum area is 0.)
Example 1: ` [[0,0,1,0,0,0,0,1,0,0,0,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,1,1,0,1,0,0,0,0,0,0,0,0], [0,1,0,0,1,1,0,0,1,0,1,0,0], [0,1,0,0,1,1,0,0,1,1,1,0,0], [0,0,0,0,0,0,0,0,0,0,1,0,0], [0,0,0,0,0,0,0,1,1,1,0,0,0], [0,0,0,0,0,0,0,1,1,0,0,0,0]] `
Given the above grid, return 6. Note the answer is not 11, because the island must be connected 4-directionally.
Example 2:
`[[0,0,0,0,0,0,0,0]]
` >Given the above grid, return 0.
Note: The length of each dimension in the given grid does not exceed 50.
译
给定一个二维数组，计算其中最大岛屿的面积。 （注意形成岛屿的规则）
解
var maxAreaOfIsland = function(grid) {
var max = 0;
if(grid == null && grid.length == 0){
return max;
}
var m = grid.length;
var n = grid[0].length;
for(var i = 0;i < m;i++){
for(var j = 0;j < n;j++){
if(grid[i][j] == 1){ // 值为1时遍历相加
var area = deps(grid,i,j,m,n,0); // 递归调用
max = Math.max(max,area); // 取最大值
}
}
}
return max;
};
function deps (grid,i,j,m,n,area){
// 数组越界以及grid[i][j] 为0时返回area
if(i<0 || j< 0 || i>=m || j>=n ||grid[i][j] == 0 ){
return area;
}
// else grid[i][j] == 1 时，
grid[i][j] = 0; // 这一步使其为0，防止多次递归。
area ++; // 面积加 1
// 递归调用
area = deps(grid,i-1,j,m,n,area);
area = deps(grid,i,j-1,m,n,area);
area = deps(grid,i+1,j,m,n,area);
area = deps(grid,i,j+1,m,n,area);
return area;
}
`
思考
这个题目算是简单中的比较难得题目了，主要是判断条件比较多而且遍历循环比较复杂。
思路上无非是先循环遍历二维数组，遇到为1的情况，计算其上下左右是否为1，为1则面积加1，此时需要判断数组是否越界， 以及将当前数组位置的grid[i][j] 置为 0 ，这样可以避免循环遍历，使用递归遍历其上下左右的值。
###第四题 744. Find Smallest Letter Greater Than Target
Given a list of sorted characters letters containing only lowercase letters, and given a target letter target, find the smallest element in the list that is larger than the given target.
Letters also wrap around. For example, if the target is target = ‘z’ and letters = [‘a’, ‘b’], the answer is ‘a’.
Examples:
Input:
letters = ["c", "f", "j"]
target = "a"
Output: "c"
Input:
letters = ["c", "f", "j"]
target = "c"
Output: "f"
Input:
letters = ["c", "f", "j"]
target = "d"
Output: "f"
Input:
letters = ["c", "f", "j"]
target = "g"
Output: "j"
Input:
letters = ["c", "f", "j"]
target = "j"
Output: "c"
Input:
letters = ["c", "f", "j"]
target = "k"
Output: "c"
Note:
-
letters has a length in range [2, 10000].
-
letters consists of lowercase letters, and contains at least 2 unique letters.
-
target is a lowercase letter.
题目简析
这道题是一道比较简单的问题，需要注意的问题是
-
数组是有序的
-
找不到返回第一个
解
var nextGreatestLetter = function(letters, target) {
for (var i = 0; i < letters.length; i++) {
// 遍历整个数组
var c = letters[i];
if (c > target){return c;}
}
//如果遍历完都没有返回，就返回第一个元素
return letters[0];
};
第五题 520. Detect Capital
Given a word, you need to judge whether the usage of capitals in it is right or not.
We define the usage of capitals in a word to be right when one of the following cases holds:
All letters in this word are capitals, like “USA”. All letters in this word are not capitals, like “leetcode”. Only the first letter in this word is capital if it has more than one letter, like “Google”. Otherwise, we define that this word doesn’t use capitals in a right way.
Example 1:
Input: "USA"
Output: True **Example 2:**
Input: "FlaG"
Output: False
Note: The input will be a non-empty word consisting of uppercase and lowercase latin letters.
题目简析
合法情况：
-
全部都是大写；
-
全部都是小写；
-
首字母大写其余为小写。
#### low解 （判断所有合法情况）
var detectCapitalUse = function(word) {
function isUpper(c){
if(c>='A' && c<='Z'){
return true;
}
return false;
}
// 正确的结果 1.全部都是大写；2.全部都是小写；3.首字母大写其余为小写。
let isUpper_0 = isUpper(word[0]);
if(word.length ==1){
return true;
}
if(isUpper_0){ // 首字母大写
if(word.length > 2){
if(isUpper(word[1])){ // 第二个字母大写
for(var i = 2;i<word.length;i++){
if(!isUpper(word[i])){
return false
}
}
}
else{ // 第二个字母小写
for(var i = 2;i<word.length;i++){
if(isUpper(word[i])){
return false
}
}
}
}
}
else{ // 首字母小写
for(var i = 1;i<word.length;i++){
if(isUpper(word[i])){
return false
}
}
}
return true;
};
另一种解法 （判断非法情况）
-
word大于 2
-
首字母大写，后面有大写有小写
-
首字母小写，有大写
var detectCapitalUse = function(word) {
function isUpper(c){
if(c>='A' && c<='Z'){
return true;
}
return false;
}
// 非法 情况 1.首字母大写其余为有大写有小写 2.首字母小写其余有大写
if(word && word.length ==1){
return true;
}
let isUpper_0 = isUpper(word[0]);
if(isUpper_0){ // 首字母大写其余为有大写有小写
let isUpper_1 = isUpper(word[1]);
for(let i=2;i<word.length;i++){
if( isUpper_1 != isUpper(word[i])){
return false;
}
}
}
else{ // 首字母小写其余有大写
for(let i=1;i<word.length;i++){
if(isUpper(word[i])){
return false;
}
}
}
return true;
};
优化解
-
全为大写，或者全为小写 word === uppered word === lowered - 首字母为大写，其余为小写
word[0] === uppered[0] && word.slice(1) === lowered.slice(1);
var detectCapitalUse = function(word) {
if (!word) {
return true;
}
var uppered = word.toUpperCase(), lowered = word.toLowerCase();
return word === uppered || word === lowered || word[0] === uppered[0] && word.slice(1) === lowered.slice(1);
};
正则表达式解
var detectCapitalUse = function(word) {
var regex = /(^[A-Z]+$)|(^[a-z]+$)|(^[A-Z][a-z]*$)/
return regex.test(word)
};
696. 第六题 Count Binary Substrings
Give a string s, count the number of non-empty (contiguous) substrings that have the same number of 0’s and 1’s, and all the 0’s and all the 1’s in these substrings are grouped consecutively.
Substrings that occur multiple times are counted the number of times they occur.
Example 1:
Input: "00110011"
Output: 6
Explanation: There are 6 substrings that have equal number of consecutive 1's and 0's: "0011", "01", "1100", "10", "0011", and "01".
Notice that some of these substrings repeat and are counted the number of times they occur.
Also, “00110011” is not a valid substring because all the 0’s (and 1’s) are not grouped together.
Example 2:
Input: "10101"
Output: 4
Explanation: There are 4 substrings: “10”, “01”, “10”, “01” that have equal number of consecutive 1’s and 0’s.
Note:
s.length will be between 1 and 50,000. s will only consist of “0” or “1” characters.
思路
思路：使用2个变量来存储当前数字前的数字连续次数pre以及当前数字的连续次数cur。如果当前数字与前一个数字连续，则计算出当前数字连续的次数cur， 否则统计当前数字之前的数字连续次数pre并令当前数字连续次数cur为1。接着通过判断统计子数组的个数，如果这时该数字之前的数字连续次数pre大于等于 当前数字连续次数cur，则令子数组个数res加1。
解
var countBinarySubstrings = function(s) {
let res = 0,cur=1,pre=0;
for(let i=1;i<s.length;i++){
if (s[i] == s[i - 1]) {
cur++;
}
else {
pre = cur;
cur = 1;
}
if (pre >= cur)
res++;
}
return res;
};
