发表于 | 更新于 | 分类于

Description:

Given two binary trees, write a function to check if they are the same or not. Two binary trees are considered the same if they are structurally identical and the nodes have the same value. Example 1:

Input: 

1
2
3
4
5
6

    1         1
   / \       / \
  2   3     2   3

[1,2,3],   [1,2,3]

Output: true

Example 2:

1
2
3
4
5
6
Input:     
     1   1
    /     \
   2       2

 [1,2],     [1,null,2]

Output: false

Example 3:

Input:

1
2
3
4
5
   1    1
  / \  / \
 2   1 1   2

[1,2,1],   [1,1,2]

Output: false

解法：

相对而言比较简单的题，对于树做遍历，我这里采用的是按层遍历，对比每一个元素判断是否相同。采用的Java的队列，因为队列为空不好判断（下回用Stack可能会好一点），这里采用了虚拟节点（也算是撞对了吧0.0）。代码如下：

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
class Solution {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        Queue<TreeNode> queuep = new LinkedList<TreeNode>();
        Queue<TreeNode> queueq = new LinkedList<TreeNode>();
        queuep.offer(p);
        queueq.offer(q);
        while (queuep.peek() != null && queueq.peek() != null) {
            TreeNode tmp1 = queuep.poll();
            TreeNode tmp2 = queueq.poll();
            if (tmp1.val == tmp2.val) {
                if (tmp1.val == -32767) {
                    continue;
                } else {
                    if (tmp1.left != null) {
                        queuep.offer(tmp1.left);
                    } else {
                        queuep.offer(new TreeNode(-32767));
                    }
                    if (tmp1.right != null) {
                        queuep.offer(tmp1.right);
                    } else {
                        queuep.offer(new TreeNode(-32767));
                    }
                    if (tmp2.left != null) {
                        queueq.offer(tmp2.left);
                    } else {
                        queueq.offer(new TreeNode(-32767));
                    }
                    if (tmp2.right != null) {
                        queueq.offer(tmp2.right);
                    } else {
                        queueq.offer(new TreeNode(-32767));
                    }
                }


            } else {
                return false;
            }
        }
        if (queuep.peek() == null && queueq.peek() != null) {
            return false;
        } else if (queueq.peek() == null && queuep.peek() != null) {
            return false;
        } else {
            return true;
        }
    }
}

除了借用队列以外，其实还可以采用深度优先搜索的递归方法进行比较，代码如下：

1
2
3
4
5
6
7
8
class Solution {
public:
    bool isSameTree(TreeNode \*p, TreeNode \*q) {
        if (!p && !q) return true;
        if ((p && !q) || (!p && q) || (p->val != q->val)) return false;
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

发表于 | 更新于 | 分类于

Description:

Given a non-empty array of digits representing a non-negative integer, plus one to the integer. The digits are stored such that the most significant digit is at the head of the list, and each element in the array contain a single digit. You may assume the integer does not contain any leading zero, except the number 0 itself. Example 1:

Input: [1,2,3]
Output: [1,2,4]
Explanation: The array represents the integer 123.

Example 2:

Input: [4,3,2,1]
Output: [4,3,2,2]
Explanation: The array represents the integer 4321.

解法：

模拟加法运算题，注意进位问题，尤其是从如99到100的问题。实现起来还是比较简单的，具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int[] plusOne(int[] digits) {
        int[] tmp = new int[digits.length + 1];
        int jinwei = 1;
        for (int i = digits.length - 1; i >= 0; i--) {
            int d = digits[i] + jinwei;
            if (d == 10) {
                jinwei = 1;
                d = 0;
            } else {
                jinwei = 0;
            }
            tmp[i] = d;
        }
        if (jinwei == 1) {
            tmp[0] = 1;
            return tmp;
        }
        for (int i = 0; i < digits.length; i++) {
            digits[i] = tmp[i];
        }
        return digits;
    }
}

发表于 | 更新于 | 分类于

Description:

The count-and-say sequence is the sequence of integers with the first five terms as following:

1. 1
2. 11
3. 21
4. 1211
5. 111221

1 is read off as "one 1" or 11. 11 is read off as "two 1s" or 21. 21 is read off as "one 2, then one 1" or 1211. Given an integer _n_, generate the _n_th term of the count-and-say sequence. Note: Each term of the sequence of integers will be represented as a string.

Example 1:

Input: 1
Output: “1”

Example 2:

Input: 4
Output: “1211”

解法：

首先理解题意。简而言之，就是这一个数对应字符串的生成由前一个数的字符串决定。具体来说，从前一个字符串的第一个字符数起，数相同字符的个数，然后将个数与该字符存入本数对应的字符串，再继续扫描计数。比如，对于4而言，前一个数3的字符串为21，则4为1个2一个1，即1211。可以发现，每一个数与前一个数的结果有关，采用递归实现，代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public String countAndSay(int n) {
        if(n == 1){
            return "1";
        }
        String str = countAndSay(n-1) +'*';  //防止越界，方便计数
        char[] cstr = str.toCharArray();
        String result = "";
        int count = 1;
        for(int i = 0;i<cstr.length - 1;i++){
            if(cstr[i] == cstr[i+1]){
                count +=1;
            }
            else{
                result += (String.valueOf(count) + cstr[i]) ;
                count = 1;
            }
        }
        return result;
    }
}

发表于 | 更新于 | 分类于

Description:

A robot is located at the top-left corner of a _m_ x _n_ grid (marked ‘Start’ in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below). How many possible unique paths are there?

Above is a 7 x 3 grid. How many possible unique paths are there?

Note: _m_ and _n_ will be at most 100.

Example 1:

Input: m = 3, n = 2

Output: 3

Explanation: From the top-left corner, there are a total of 3 ways to reach the bottom-right corner: 1. Right -> Right -> Down 2. Right -> Down -> Right 3. Down -> Right -> Right

Example 2:

Input: m = 7, n = 3

Output: 28

解法：

此题同样用动态规划法，思路同Leetcode(63) Unique Paths II。代码如下：

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
class Solution {
    public int uniquePaths(int m, int n) {
        int[][] tmp = new int[m][n];
        if(m == 1 || n == 1){
            return 1;
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if(i == 0 && j == 0){
                    tmp[i][j] = 1;
                }
                else if (i == 0 && j > 0) {
                    tmp[i][j] = tmp[i][j - 1];
                }
                else if (j == 0 && i > 0) {
                    tmp[i][j] = tmp[i - 1][j];
                }
                else {
                    tmp[i][j] = tmp[i - 1][j] + tmp[i][j - 1];
                }
            }
        }
        return tmp[m-1][n-1];
    }
}

发表于 | 更新于 | 分类于

Description:

A robot is located at the top-left corner of a _m_ x _n_ grid (marked ‘Start’ in the diagram below). The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked ‘Finish’ in the diagram below). Now consider if some obstacles are added to the grids. How many unique paths would there be?

An obstacle and empty space is marked as 1 and 0 respectively in the grid.

Note: _m_ and _n_ will be at most 100.

Example 1: Input: [ [0,0,0], [0,1,0], [0,0,0] ] Output: 2

Explanation: There is one obstacle in the middle of the 3x3 grid above. There are two ways to reach the bottom-right corner: 1. Right -> Right -> Down -> Down 2. Down -> Down -> Right -> Right

解法：

首先考虑采用队列进行解题（毕竟迷宫地图类常用套路0.0），然而在矩阵较小时挺好，遇上大矩阵就超时了。以下为该方法代码：

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
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        Queue<pointposition> queue = new LinkedList<pointposition>();
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }
        if (row == 1 && col == 1) {
            return 1;
        }
        int result = 0;
        pointposition start = new pointposition(0, 0);
        pointposition end = new pointposition(row - 1, col - 1);
        queue.offer(start);
        while (queue.peek() != null) {
            pointposition now = queue.poll();
            if (now.equal(end)) {
                result += 1;
                continue;
            }
            pointposition next1 = new pointposition(now.posx + 1, now.posy);
            pointposition next2 = new pointposition(now.posx, now.posy + 1);
            if (judge(next1, row, col) && obstacleGrid[next1.posx][next1.posy] != 1) {
                queue.offer(next1);
            }
            if (judge(next2, row, col) && obstacleGrid[next2.posx][next2.posy] != 1) {
                queue.offer(next2);
            }
        }
        return result;
    }

    Boolean judge(pointposition x, int row, int col) {
        if (x.posx >= 0 && x.posx < row && x.posy >= 0 && x.posy < col) {
            return true;
        }
        return false;
    }
}

class pointposition {
    public int posx;
    public int posy;

    pointposition(int x, int y) {
        this.posx = x;
        this.posy = y;
    }

    boolean equal(pointposition x) {
        if (this.posx == x.posx && this.posy == x.posy) {
            return true;
        }
        return false;
    }
}

考虑到在这种情形下，无论从起点到终点还是从终点到起点，路径的数目是一样的。我们可以按照每一个点到起点的路径数逆推得到终点到起点的路径数。对于起点，起点到起点的路径数为1.对于其他点，它们到起点的路径数一定等于在它上方的点到起点的路径数与在它左方的点到起点的路径数之和，因为这个点只能通过它的上方和左方两个方向到达起点。简而言之，采用动态规划的方法解题，该问题的状态转移函数为：

1
nums(i , j) = nums(i , j-1) + nums(i-1 , j)

需要注意的是，本题中存在障碍物，对于障碍物的点，显然，它到起点的路径数为0。AC动态规划代码如下：

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
class Solution {
    public int uniquePathsWithObstacles(int[][] obstacleGrid) {
        int row = obstacleGrid.length;
        int col = obstacleGrid[0].length;
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }
        if (row == 1 && col == 1) {
            return 1;
        }
        int[][] tmp = new int[row][col];
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (obstacleGrid[i][j] == 1) {
                    tmp[i][j] = 0;
                } else if (i == 0 && j == 0) {
                    tmp[i][j] = 1;
                } else if (i == 0 && j > 0) {
                    tmp[i][j] = tmp[i][j - 1];
                } else if (j == 0 && i > 0) {
                    tmp[i][j] = tmp[i - 1][j];
                } else {
                    tmp[i][j] = tmp[i - 1][j] + tmp[i][j - 1];
                }
            }
        }
        return tmp[row - 1][col - 1];
    }
}

发表于 | 更新于 | 分类于

Description:

Given a sorted array and a target value, return the index if the target is found. If not, return the index where it would be if it were inserted in order. You may assume no duplicates in the array.

Example 1:

Input: [1,3,5,6], 5

Output: 2

Example 2:

Input: [1,3,5,6], 2

Output: 1

Example 3:

Input: [1,3,5,6], 7

Output: 4

Example 4:

Input: [1,3,5,6], 0

Output: 0

解法：

这题简单，从前往后扫描一遍数组，遇见大于或等于目标值的条目直接返回索引值即可，代码如下：

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int searchInsert(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] >= target) {
                return i;
            }
        }
        return nums.length;
    }
}

发表于 | 更新于 | 分类于

Description:

You are given a string, s, and a list of words, words, that are all of the same length. Find all starting indices of substring(s) in s that is a concatenation of each word in words exactly once and without any intervening characters.

Example 1:

Input: s = “barfoothefoobarman”, words = [“foo”,”bar”] Output: [0,9]

Example 2:

Input: s = “wordgoodstudentgoodword”, words = [“word”,”student”] Output: []

解法：

题意有点绕，意思是是给你一个字符串，和一个字符串的数组，需要返回一个该字符串的索引组成的数组，其中字符串数组中各成员长度要求一致，返回的索引有如下性质：

从每个索引开始，长度为L的字串需要精确包含字符串数组中的所有字符串（不多不少）。L 为字符串数组中所有字符串长度之和。

思路是：先用一个Map结构，记录字符串数组中各个字符串出现的个数，用于之后判断子串中各字符串是否出现够数，之后，从头开始遍历字符串，找和字符串数组中的字符串相同的字串，找到后map中的值减一，否则重新初始化map，从下一个字符开始遍历。如果map中所有的值都为0，则找到了一个符合条件的子串，索引压入数组。

代码如下：

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
class Solution {
    public List<Integer> findSubstring(String s, String[] words) {
        Map<String, Integer> wordcount = new HashMap<String, Integer>();
        List<Integer> result = new ArrayList<Integer>();
        if(s == "" || words.length == 0){
            return result;
        }
        int wordlen = words[0].length();
        int word_count = words.length;
        for (String word : words) {
            if(word.length()!=wordlen){
                return result;
            }
            if (!wordcount.containsKey(word)) {
                wordcount.put(word, 1);
            } else {
                wordcount.put(word, wordcount.get(word) + 1);
            }
        }

        for (int i = 0; i <= s.length() - wordlen; i++) {
            String tmpsub = s.substring(i, i + wordlen);
            Map<String, Integer> tmpmap = new HashMap<>();
            tmpmap.putAll(wordcount);
            if (!tmpmap.containsKey(tmpsub)) {
                continue;
            } else {
                int remain_word_count = word_count;
                int j = i;
                while (remain_word_count > 0) {
                    if (tmpmap.get(tmpsub) > 0) {
                        tmpmap.put(tmpsub, tmpmap.get(tmpsub) - 1);
                        j += wordlen;
                        remain_word_count -= 1;
                        if(j>s.length() - wordlen){
                            break;
                        }
                        tmpsub = s.substring(j, j + wordlen);
                        if (!tmpmap.containsKey(tmpsub)){
                            break;
                        }
                    } else {
                        break;
                    }
                }
                if(remain_word_count == 0){
                    result.add(i);
                }

            }
        }
        return result;
    }
}

发表于 | 更新于 | 分类于

Description:

Given two integers dividend and divisor, divide two integers without using multiplication, division and mod operator. Return the quotient after dividing dividend by divisor. The integer division should truncate toward zero.

Example 1:

Input: dividend = 10, divisor = 3

Output: 3

Example 2:

Input: dividend = 7, divisor = -3

Output: -2

Note:

  • Both dividend and divisor will be 32-bit signed integers.
  • The divisor will never be 0.
  • Assume we are dealing with an environment which could only store integers within the 32-bit signed integer range: [−231, 231 − 1]. For the purpose of this problem, assume that your function returns 231 − 1 when the division result overflows.

解法：

除法可以采用减法实现，未避免减法次数过多，采用二分法可减少运算次数。 不难想到用除数的2^31,2^30,…,2^2,2^1,2^0倍尝试去减被除数，如果减得动，则把相应的倍数加到商中；如果减不动，则依次尝试更小的倍数。这样就可以快速逼近最终的结果。 2的i次方其实就相当于左移i位，为什么从31位开始呢？因为int型数据最大值就是2^31啊。 注：左移x位相当于乘2的x次方，右移x位相当于除2的x次方 代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int divide(int dividend, int divisor) {
        if (divisor == 0 || (dividend == Integer.MIN_VALUE && divisor == -1)) return Integer.MAX_VALUE;
        long a = dividend > 0 ? dividend : -(long) dividend;
        long b = divisor > 0 ? divisor : -(long) divisor;
        if (b == 1) {
            return divisor == 1 ? dividend : -dividend;
        }
        int result = 0;
        for (int i = 31; i >= 0; i--) {
            if ((a >> i) >= b) {
                result += (1 << i);
                a = a - (b << i);
            }
        }
        if ((dividend ^ divisor) < 0) {
            result = -result;
        }
        return result;
    }
}

发表于 | 更新于 | 分类于

正则表达式

单个字符的正则匹配：

字符 匹配
. 匹配除了‘\n’以外的任意单个字符
[…] 匹配字符集中的任意字符（即两个中括号表示字符集）.如[a-z]匹配任意一个小写字母，[ab]匹配a或b，[a-zA-Z]匹配任意字母
\d 匹配任意一个数字
\D 匹配任意一个非数字
\s 匹配空白字符
\S 匹配非空白字符
\w 匹配一个单词字符，即[a-zA-Z0-9]
\W 匹配一个非单词字符

多个字符的匹配（与单个字符相结合使用）：

字符 匹配
* 匹配前一个字符0到无限次
+ 匹配前一个字符1到无限次
? 匹配前一个字符0次或1次
{m} 匹配前一个字符m次
{m,n} 匹配前一个字符m次到n次
*? 非贪婪地进行匹配，对于则最少匹配0次，如1[a-z]?匹配1a时只匹配到1
+? 非贪婪地进行匹配，对+则最少匹配一次
?? 非贪婪地进行匹配，对?则最少匹配0次

边界匹配：

字符 匹配
^ 匹配字符串的开头
$ 匹配字符串的结尾
\A 指定的字符串必须出现在开头，如\Ahzh[\w]*匹配以hzh开头的任意字符串
\Z 指定的字符串必须出现在结尾

分组匹配：

字符 匹配
\ 匹配左右任意一个表达式，相当与或

发表于 | 更新于 | 分类于

Description:

Implement strStr(). Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = “hello”, needle = “ll”

Output: 2

Example 2:

Input: haystack = “aaaaa”, needle = “bba”

Output: -1

解法：

首先做特别判断，如果needle的长度大于haystack，不可能匹配，返回-1，如果needle为空，返回0。然后我们开始遍历母字符串，我们并不需要遍历整个母字符串，而是遍历到剩下的长度和子字符串相等的位置即可，这样可以提高运算效率。然后对于每一个字符，我们都遍历一遍子字符串，一个一个字符的对应比较，如果对应位置有不等的，则跳出循环，如果一直都没有跳出循环，则说明子字符串出现了，则返回起始位置即可，代码如下：

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
class Solution:
    def strStr(self, haystack, needle):
        """
        :type haystack: str
        :type needle: str
        :rtype: int
        """
        p = 0;
        q = 0;
        if(len(needle)>len(haystack)):
            return -1;
        if(len(needle) == 0):
            return 0;
        while(p<len(haystack)-len(needle)+1):
            if(haystack[p] == needle[0]):
                q = p;
                flag = 1;
                for x in needle:
                    if(x == haystack[q]):
                        q+=1;
                    else:
                        flag = 0;
                        break;
                if(flag == 1):
                    return p;
            p+=1;
        return -1;

更好写的递归的算法：

判断节点的数量是否构成一组，如果不够，直接返回head，如果够，则将当前组反转，之后的链表变为当前问题的子问题，递归即可，然后再把这两部分连接起来。

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseKGroup(ListNode head, int k) {
        if(head == null || head.next == null || k == 1){
            return head;
        }
        ListNode tmp = head;
        int step = 1;
        while(tmp != null && step < k) {
            tmp = tmp.next;
            step++;
        }
        if(tmp == null) {
            return head;
        }
        else{
            ListNode t2 = tmp.next;
            tmp.next = null;
            ListNode newhead =  reverseList(head);
            ListNode newtmp = reverseKGroup(t2,k);
            head.next = newtmp;
            return newhead;
        }
        
    }
    ListNode reverseList(ListNode head) {
        if (head == null) {
            return head;
        }
        if (head.next == null) {
            return head;
        }
        ListNode res = reverseList(head.next);
        head.next.next = head;
        head.next = null;
        return res;
    }
}