判断字符串是否为数字 

1
2
3
4
5
6
请实现一个函数用来判断字符串是否表示数值（包括整数和小数）。例如，字符串"+100"、"5e2"、"-123"、"3.1416"、"-1E-16"、"0123"都表示数值，但"12e"、"1a3.14"、"1.2.3"、"+-5"及"12e+5.4"都不是。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/biao-shi-shu-zhi-de-zi-fu-chuan-lcof
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37

// 编码没什么难度，难点在于归纳各种正确的情况
// ‘.’出现正确情况：只出现一次，且在e的前面
// ‘e’出现正确情况：只出现一次，且出现前有数字
// ‘+’‘-’出现正确情况：只能在开头和e后一位

class Solution {
    public boolean isNumber(String s) {
        if (s == null || s.length() == 0) return false;
        //去掉首位空格
        s = s.trim();
        boolean numFlag = false;
        boolean dotFlag = false;
        boolean eFlag = false;
        for (int i = 0; i < s.length(); i++) {
            //判定为数字，则标记numFlag
            if (s.charAt(i) >= '0' && s.charAt(i) <= '9') {
                numFlag = true;
                //判定为.  需要没出现过.并且没出现过e
            } else if (s.charAt(i) == '.' && !dotFlag && !eFlag) {
                dotFlag = true;
                //判定为e，需要没出现过e，并且出过数字了
            } else if ((s.charAt(i) == 'e' || s.charAt(i) == 'E') && !eFlag && numFlag) {
                eFlag = true;
                numFlag = false;//为了避免123e这种请求，出现e之后就标志为false
                //判定为+-符号，只能出现在第一位或者紧接e后面
            } else if ((s.charAt(i) == '+' || s.charAt(i) == '-') && (i == 0 || s.charAt(i - 1) == 'e' || s.charAt(i - 1) == 'E')) {

                //其他情况，都是非法的
            } else {
                return false;
            }
        }
        return numFlag;
    }
}

展开全文 >>

幸福的勇气 

1
如果你所理解的幸福就是什么不开心的事都尽量不发生，平安喜乐地过一辈子，那么多半你是要失望了。
1
真正的修行，首先是放下对于恒常的追求，坦然接受无常的发生。这种勇气，没有足够的智慧和福德，是难以拥有的。

展开全文 >>

判断二叉树是否平衡（简单题） 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
给定一个二叉树，判断它是否是高度平衡的二叉树。

本题中，一棵高度平衡二叉树定义为：

一个二叉树每个节点 的左右两个子树的高度差的绝对值不超过1。

示例 1:

给定二叉树 [3,9,20,null,null,15,7]

    3
   / \
  9  20
    /  \
   15   7
返回 true 。

示例 2:

给定二叉树 [1,2,2,3,3,null,null,4,4]

       1
      / \
     2   2
    / \
   3   3
  / \
 4   4
返回 false 。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/balanced-binary-tree
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public boolean isBalanced(TreeNode root) {
        return height(root) >= 0;
    }
     private int height(TreeNode root) {
        if(root == null)
            return 0;
        int lh = height(root.left), rh = height(root.right);
        if(lh >= 0 && rh >= 0 && Math.abs(lh - rh) <= 1) {
            return Math.max(lh, rh) + 1;
        } else {
            return -1;
        }
    }
}


展开全文 >>

盛水多的容器（动态规划中等题） 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0)。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。

说明：你不能倾斜容器，且 n 的值至少为 2。

 



图中垂直线代表输入数组 [1,8,6,2,5,4,8,3,7]。在此情况下，容器能够容纳水（表示为蓝色部分）的最大值为 49。

 

示例：

输入：[1,8,6,2,5,4,8,3,7]
输出：49

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/container-with-most-water
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

// Area = Max(min(height[i], height[j]) * (j-i)) {其中0 <= i < j < height,size()}
// 这里用到了动态规划，基本的表达式: area = min(height[i], height[j]) * (j - i) 使用两个指针，
// 值小的指针向内移动，这样就减小了搜索空间 因为面积取决于指针的距离与值小的值乘积，
// 如果值大的值向内移动，距离一定减小，而求面积的另外一个乘数一定小于等于值小的值，
// 因此面积一定减小，而我们要求最大的面积，因此值大的指针不动，而值小的指针向内移动遍历
    public int maxArea(int[] height) {
        int i = 0, j = height.length - 1;
        int result = 0;
        while (i < j) {
            int h = Math.min(height[i], height[j]);
            result = Math.max(result, h * (j - i));
            if (height[i] < height[j]) {
                i++;
            } else {
                j--;
            }
        }
        return result;


    }

展开全文 >>

涂色问题（简单题） 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

有一幅以二维整数数组表示的图画，每一个整数表示该图画的像素值大小，数值在 0 到 65535 之间。

给你一个坐标 (sr, sc) 表示图像渲染开始的像素值（行 ，列）和一个新的颜色值 newColor，让你重新上色这幅图像。

为了完成上色工作，从初始坐标开始，记录初始坐标的上下左右四个方向上像素值与初始坐标相同的相连像素点，接着再记录这四个方向上符合条件的像素点与他们对应四个方向上像素值与初始坐标相同的相连像素点，……，重复该过程。将所有有记录的像素点的颜色值改为新的颜色值。

最后返回经过上色渲染后的图像。

示例 1:

输入: 
image = [[1,1,1],[1,1,0],[1,0,1]]
sr = 1, sc = 1, newColor = 2
输出: [[2,2,2],[2,2,0],[2,0,1]]
解析: 
在图像的正中间，(坐标(sr,sc)=(1,1)),
在路径上所有符合条件的像素点的颜色都被更改成2。
注意，右下角的像素没有更改为2，
因为它不是在上下左右四个方向上与初始点相连的像素点。
注意:

image 和 image[0] 的长度在范围 [1, 50] 内。
给出的初始点将满足 0 <= sr < image.length 和 0 <= sc < image[0].length。
image[i][j] 和 newColor 表示的颜色值在范围 [0, 65535]内。

简单题不好不差

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
class Solution {
    public int[][] floodFill(int[][] image, int sr, int sc, int newColor) {
        int color = image[sr][sc];
        boolean flag[][]=new boolean[image.length][image[0].length];//遍历标识位
        flag[sr][sc]=true;
        image[sr][sc] = newColor;
        fill(image, sr, sc, newColor, color,flag);

        return image;
    }
    static int road[][]={{0,1},{1,0},{0,-1},{-1,0}};//上右下左

    public void fill(int[][] image, int sr, int sc, int newColor,int color,boolean flag[][]){

            image[sr][sc] = newColor;
            flag[sr][sc]=true;
            for (int i = 0; i < 4; i++) {//遍历上右下左四个方向
                int x=sr + road[i][0];
                int y=sc + road[i][1];
                if ( x< image.length && y < image[0].length && x >= 0 && y >= 0){
                    if(image[x][y]==color){
                        if(flag[x][y]){//已经遍历过
                            continue;
                        }
                        fill(image, x,y, newColor, color,flag);
                    }
                } 

            }
    }
}

展开全文 >>

正则匹配（困难题） 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
给你一个字符串 s 和一个字符规律 p，请你来实现一个支持 '.' 和 '*' 的正则表达式匹配。

'.' 匹配任意单个字符
'*' 匹配零个或多个前面的那一个元素
所谓匹配，是要涵盖 整个 字符串 s的，而不是部分字符串。

说明:

s 可能为空，且只包含从 a-z 的小写字母。
p 可能为空，且只包含从 a-z 的小写字母，以及字符 . 和 *。
示例 1:

输入:
s = "aa"
p = "a"
输出: false
解释: "a" 无法匹配 "aa" 整个字符串。
示例 2:

输入:
s = "aa"
p = "a*"
输出: true
解释: 因为 '*' 代表可以匹配零个或多个前面的那一个元素, 在这里前面的元素就是 'a'。因此，字符串 "aa" 可被视为 'a' 重复了一次。
示例 3:

输入:
s = "ab"
p = ".*"
输出: true
解释: ".*" 表示可匹配零个或多个（'*'）任意字符（'.'）。
示例 4:

输入:
s = "aab"
p = "c*a*b"
输出: true
解释: 因为 '*' 表示零个或多个，这里 'c' 为 0 个, 'a' 被重复一次。因此可以匹配字符串 "aab"。
示例 5:

输入:
s = "mississippi"
p = "mis*is*p*."
输出: false

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/regular-expression-matching
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

leetcode官方动态规划解题思路

上面的思路不易理解

学习别人写的好理解的思路

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36

public class Regex_ {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        String s = sc.next();
        String p = sc.next();
        System.out.println(isMatch(s, p));
        //        s = "mississippi"
        //        p = "a*mis*is*p*."

        //        aaca
        //        ab*a*c*a

        //        aaa
        //        a*a

        //        "aaa"
        //        "ab*a*c*a"
    }


    public static boolean isMatch(String s, String p) {
        if (0==p.length()) return 0==s.length();//如果都为空，则匹配，否则不匹配

        boolean first_match = 0!=s.length() && (s.charAt(0) == p.charAt(0) || p.charAt(0) == '.');//如果s不为空，并且s的第一个字符与p的第一个字符相同或者p的第一个字符是.

        if (p.length() >= 2 && p.charAt(1) == '*') {//如果p的长度大于2，并且第二个（从0开始第一个）字符是*
            //*是0个前一个字符，判断后面是否匹配||第一个字符匹配，*是n个前一个字符，判断是否匹配
            return isMatch(s, p.substring(2,p.length())) || (first_match && isMatch(s.substring(1,s.length()), p));
        } else {
            //p和s第一个字符匹配，并且后面的字符也匹配
            return first_match && isMatch(s.substring(1,s.length()), p.substring(1,p.length()));
        }
    }
}

展开全文 >>

括号匹配（简单题） 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
注意空字符串可被认为是有效字符串。

示例 1:

输入: "()"
输出: true
示例 2:

输入: "()[]{}"
输出: true
示例 3:

输入: "(]"
输出: false
示例 4:

输入: "([)]"
输出: false
示例 5:

输入: "{[]}"
输出: true

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/valid-parentheses
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

我的辣鸡解法，暴力栈

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42


public static void main(String[] args) {
    String s = "(((()))";
    System.out.println(isValid(s));
}
public static boolean isValid(String s) {
    Stack stack = new Stack();
    char[] arr = s.toCharArray();

    for (int i = 0; i < s.length(); i++) {
        if (stack.empty()) {
            stack.push(arr[i]);
        } else {
            if (isMatch((char) stack.peek(), arr[i])) {
                stack.pop();
            } else {
                stack.push(arr[i]);
            }
        }
    }

    if (stack.empty()) {
        return true;
    } else {
        return false;
    }
}


public static boolean isMatch(char left, char right) {
    if (left == '(' && right == ')') {
        return true;
    } else if (left == '[' && right == ']') {
        return true;
    } else if (left == '{' && right == '}') {
        return true;
    } else {
        return false;
    }

}

优美的解法：遇到左括号向栈加右括号，如果不是左括号则弹出栈中的右括号，如果不和栈顶元素相同，则括号不匹配

1
2
3
4
5
6
7
8
9
10
11
public static boolean isValid(String s) {
    Stack<Character>stack = new Stack<Character>();
    for(char c: s.toCharArray()){
        if(c=='(')stack.push(')');
        else if(c=='[')stack.push(']');
        else if(c=='{')stack.push('}');
        else if(stack.isEmpty()||c!=stack.pop())return false;
    }
    return stack.isEmpty();
}

展开全文 >>

大数相乘学习（中等题）

43. 字符串相乘

难度：中等

给定两个以字符串形式表示的非负整数 num1 和 num2，返回 num1 和 num2 的乘积，它们的乘积也表示为字符串形式。

示例 1:

1
2
输入: num1 = "2", num2 = "3"
输出: "6"

示例 2:

1
2
输入: num1 = "123", num2 = "456"
输出: "56088"

说明：

  1. num1 和 num2 的长度小于110。
  2. num1 和 num2 只包含数字 0-9。
  3. num1 和 num2 均不以零开头，除非是数字 0 本身。
  4. 不能使用任何标准库的大数类型（比如 BigInteger）或直接将输入转换为整数来处理。

优美的解题方式：

Start from right to left, perform multiplication on every pair of digits, and add them together. Let’s draw the process! From the following draft, we can immediately conclude:

num1[i] * num2[j] will be placed at indices [i + j, i + j + 1]
3Xwq1.md.png

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47

public String multiply(String num1, String num2) {
    /**
     num1的第i位(高位从0开始)和num2的第j位相乘的结果在乘积中的位置是[i+j, i+j+1]
     例: 123 * 45,  123的第1位 2 和45的第0位 4 乘积 08 存放在结果的第[1, 2]位中
     index:    0 1 2 3 4

         1 2 3
     *     4 5
     ---------
           1 5
         1 0
       0 5
     ---------
       0 6 1 5
         1 2
       0 8
     0 4
     ---------
     0 5 5 3 5
     这样我们就可以单独都对每一位进行相乘计算把结果存入相应的index中
     **/

    int n1 = num1.length()-1;
    int n2 = num2.length()-1;
    if(n1 < 0 || n2 < 0) return "";
    int[] mul = new int[n1+n2+2];

    for(int i = n1; i >= 0; --i) {
        for(int j = n2; j >= 0; --j) {
            int bitmul = (num1.charAt(i)-'0') * (num2.charAt(j)-'0');
            bitmul += mul[i+j+1]; // 先加低位判断是否有新的进位

            mul[i+j] += bitmul / 10;
            mul[i+j+1] = bitmul % 10;
        }
    }

    StringBuilder sb = new StringBuilder();
    int i = 0;
    // 去掉前导0
    while(i < mul.length-1 && mul[i] == 0)
        i++;
    for(; i < mul.length; ++i)
        sb.append(mul[i]);
    return sb.toString();
}

展开全文 >>

迷宫问题 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

给定一个二维的矩阵，包含 'X' 和 'O'（字母 O）。

找到所有被 'X' 围绕的区域，并将这些区域里所有的 'O' 用 'X' 填充。

示例:

X X X X
X O O X
X X O X
X O X X
运行你的函数后，矩阵变为：

X X X X
X X X X
X X X X
X O X X
解释:

被围绕的区间不会存在于边界上，换句话说，任何边界上的 'O' 都不会被填充为 'X'。 任何不在边界上，或不与边界上的 'O' 相连的 'O' 最终都会被填充为 'X'。如果两个元素在水平或垂直方向相邻，则称它们是“相连”的。

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/surrounded-regions
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

走迷宫问题，思路是遍历四个边，如果边上的O可达里面的O，所有可达的O都不能消除
如果边上的O不可达里面的O，那么里面的O都可以被消除。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65

class Solution {
    public void solve(char[][] board) {
        if(board.length==0){
            return;
        }
        boolean[][] flags = new boolean[board.length][board[0].length];//是否可达标志
        boolean[][] flags_repeat = new boolean[board.length][board[0].length];//重复走标志
        int width = board[0].length - 1, height = board.length - 1;

        //固定第一维，遍历第二维的第一行和最后一行
        for (int i = 0; i < board.length; i++) {
            if (board[i][0] == 'O') {
                flags[i][0] = true;
                walk(board, i, 0, flags, flags_repeat);
            }
            if (board[i][width] == 'O') {
                flags[i][width] = true;
                walk(board, i, width, flags, flags_repeat);

            }
        }
        //固定第二维，遍历第一维的第一列和最后一列
        for (int j = 0; j < board[0].length; j++) {
            if (board[0][j] == 'O') {
                flags[0][j] = true;
                walk(board, 0, j, flags, flags_repeat);

            }
            if (board[height][j] == 'O') {
                flags[height][j] = true;
                walk(board, height, j, flags, flags_repeat);
            }
        }

        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                if (!flags[i][j]) {//如果是内部的O那么它不可达，就更改为X
                    board[i][j] = 'X';
                }
            }
        }
    }

    public static void walk(char[][] board, int i, int j, boolean[][] flags, boolean[][] flags_repeat) {
        flags_repeat[i][j] = true;//已经走过了
        if (i - 1 >= 0 && board[i - 1][j] == 'O' && !flags_repeat[i - 1][j]) {//左边的一格，如果是O并且没有被访问过
            flags[i - 1][j] = true;
            walk(board, i - 1, j, flags, flags_repeat);
        }
        if (j - 1 >= 0 && board[i][j - 1] == 'O' && !flags_repeat[i][j - 1]) {//下边的一格，如果是O并且没有被访问过
            flags[i][j - 1] = true;
            walk(board, i, j-1, flags, flags_repeat);
        }
        if (i + 1 < board.length && board[i + 1][j] == 'O' && !flags_repeat[i + 1][j]) {//右边的一格，如果是O并且没有被访问过
            flags[i+1][j] = true;
            walk(board, i + 1, j, flags, flags_repeat);
        }
        if (j + 1 < board[0].length && board[i][j + 1] == 'O' && !flags_repeat[i][j + 1]) {//上边的一格，如果是O并且没有被访问过
            flags[i][j+1] = true;
            walk(board, i, j+1, flags, flags_repeat);
        }
    }
}

展开全文 >>

原地删除数组元素（简单题） 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
给定一个排序数组，你需要在 原地 删除重复出现的元素，使得每个元素只出现一次，返回移除后数组的新长度。

不要使用额外的数组空间，你必须在 原地 修改输入数组 并在使用 O(1) 额外空间的条件下完成。

 

示例 1:

给定数组 nums = [1,1,2], 

函数应该返回新的长度 2, 并且原数组 nums 的前两个元素被修改为 1, 2。 

你不需要考虑数组中超出新长度后面的元素。
示例 2:

给定 nums = [0,0,1,1,1,2,2,3,3,4],

函数应该返回新的长度 5, 并且原数组 nums 的前五个元素被修改为 0, 1, 2, 3, 4。

你不需要考虑数组中超出新长度后面的元素。
 

说明:

为什么返回数值是整数，但输出的答案是数组呢?

请注意，输入数组是以「引用」方式传递的，这意味着在函数里修改输入数组对于调用者是可见的。

你可以想象内部操作如下:

// nums 是以“引用”方式传递的。也就是说，不对实参做任何拷贝
int len = removeDuplicates(nums);

// 在函数里修改输入数组对于调用者是可见的。
// 根据你的函数返回的长度, 它会打印出数组中该长度范围内的所有元素。
for (int i = 0; i < len; i++) {
    print(nums[i]);
}

简单题没有弯弯绕绕。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class RemoveDuplicates {
    public static void main(String[] args) {
        Scanner sc=new Scanner(System.in);
        List<Integer> list=new ArrayList<>();
        while(sc.hasNext()){
            int num=sc.nextInt();
            if(num==-1){
                break;
            }
            list.add(num);
        }
        int nums[]=new int[list.size()];
        for(int i=0;i<list.size();i++){
            nums[i]=list.get(i);
        }
        int left=removeDuplicates(nums);
        for(int i=0;i<left;i++){
            System.out.println(nums[i]);
        }


    }
    
    public static int removeDuplicates(int[] nums) {
        int cur=0;//当前的指针
        for(int i=0;i<nums.length-1;i++){
            if(nums[cur]!=nums[i+1]){//如果当前的和后面的某个不同（第一个不同的）
                cur++;//则指针后移
                nums[cur]=nums[i+1];//修改指针所指的内容（是与nums[cur-1]重复的元素）
            }
        }
        cur++;//最后一个元素没修改，指针后移一个到达结尾
        return cur;
    }
}



展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

我是一只<br>又水又笨又菜的<br>菜狗子<br>希望有一天被领走