发表于 | 分类于

Given a binary search tree (BST), find the lowest common ancestor (LCA) of two given nodes in the BST.

According to the definition of LCA on Wikipedia: “The lowest common ancestor is defined between two nodes v and w as the lowest node in T that has both v and w as descendants (where we allow a node to be a descendant of itself).”

___6__
/ \
_2 _8
/ \ / \
0 _4 7 9
/ \
3 5
For example, the lowest common ancestor (LCA) of nodes 2 and 8 is 6. Another example is LCA of nodes 2 and 4 is 2, since a node can be a descendant of itself according to the LCA definition.

解法1：Recursion

这题有一个很重要的前提是这是一棵BST。并且隐含条件是一定存在对于给点的两个node的LCA。
那么考虑两种情况，假设两个node的大小一个比root大一个比root小，则node分属于左右子树，LCA只可能是root
如果两个node同属一边，则问题也等价于在左子树（假设node的val比root的小），套用递归的思想解决即可。
C++

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if (root == p || root == q) {
            return root;
        }
        if (p->val < root->val && q->val > root->val) {
            return root;
        }
        if (p->val > root->val && q->val < root->val) {
            return root;
        }
        if (p->val < root->val) {
            return lowestCommonAncestor(root->left, p, q);
        }
        return lowestCommonAncestor(root->right, p, q);
    }
};

Java

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
public class Solution {
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {
        
        if (root == p || root == q) {
            return root;
        }
        
        if ((root.val < p.val && root.val > q.val) || (root.val > p.val && root.val < q.val)) {
            return root;
        }
        
        if (root.val < p.val && root.val < q.val) {
            return lowestCommonAncestor(root.right, p, q);
        }
        
        return lowestCommonAncestor(root.left, p, q);
        
    }
}

发表于 | 分类于

Write a program to check whether a given number is an ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 6, 8 are ugly while 14 is not ugly since it includes another prime factor 7.

Note that 1 is typically treated as an ugly number.

解法1：暴力法

按照题意，ugly number一定是1，2，3，5几个数的乘积。那么用number不停的去整除2，3，5，如果发现不能整除，则不是ugly，如果能整除则继续直到为1或者出现不能整除的数为止。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool isUgly(int num) {
        if (num <= 0) {
            return false;
        }
        while (num != 1) {
            if (num %2 == 0) {
                num /= 2;
            } else if (num % 3 == 0) {
                num /= 3;
            } else if (num % 5 == 0) {
                num /= 5;
            } else {
                return false;
            }
        }
        return true;
    }
};

Java

1

发表于 | 分类于

Reverse a linked list from position m to n. Do it in-place and in one-pass.

For example:
Given 1->2->3->4->5->NULL, m = 2 and n = 4,

return 1->4->3->2->5->NULL.

Note:
Given m, n satisfy the following condition:
1 ≤ m ≤ n ≤ length of list.

解法1：Two pointers, One Pass O(N)

题目要求只能走一遍，所以考虑用双指针。同时需要考虑到的是，等reverse结束，我们的head是不确定的，在这种情况下我们考虑使用dummy node，将dummy node指向head，最后不管其中怎么变化，我们一定是返回dummy.next
假设我们已经知道从node m 到node n需要reverse，那么reverse之后由于要并入原来的list，我们需要知道子list的head之前的那个node，以及子list的尾巴之后的那个node， 比如：
1->2->3->4->5, if m = 2, n = 4
那么我们需要记录指针位置1和指针位置5，当把2->3->4翻转过后把新的head和tail指向这两个节点就可以了。
实现上维护two pointers和一个计数器，当right pointer移动到子list的head的时候，left pointer就自然而然的指向了前面的那个node，把子list的head记录为newtail，因为当reverse之后他会变成tail。
然后开始reverse的过程，同时变更计数器，直到计数器等于n的值为止。这个时候我们就得到了新的head，记录下一个值便是我们要将newtail指向的位置。最后返回dummy.next
C++

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* reverseBetween(ListNode* head, int m, int n) {
        if (m == n) {
            return head;
        }
        ListNode* dummy = new ListNode(0);
        dummy->next = head;
        ListNode* ptr0 = dummy;
        ListNode* newhead = NULL;
        ListNode* newtail = NULL;
        int count = 1;
        while (count < m) {
            ptr0 = ptr0->next;
            head = head->next;
            ++count;
        }
        newtail = head;
        ListNode* prev = head;
        head = head->next;
        ++count;
        while (count <= n) {
            ListNode* temp = head->next;
            head->next = prev;
            prev = head;
            head = temp;
            ++count;
        }
        newhead = prev;
        ptr0->next = newhead;
        newtail->next = head;
        return dummy->next;
    }
};

Java

1

解法2：Two pointers, One Pass O(N)

解法1的思想比较直观，不过写起来比较繁琐。从discuss上看来的这个解法比较简洁。要注意的是其中有把一个子list反转的template需要记一下，很有用。

1
prev->A->B->C->res

对于上面这个list，要反转A到C，那么设start为A，then为B两个指针。
prev不移动而移动start和then，每一次把start向后移动一位，并且把then指向的node接到prev之后就可以达到效果。
代码是

1
2
3
4
5
6
for (int i = 0; i < n - ml; i++) {
  start.next = then.next;
  then.next = prev.next;
  prev.next = then;
  then = start.next;
}

完整的代码就简洁多了。
Java

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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public ListNode reverseBetween(ListNode head, int m, int n) {
        if (m == n || head == null) {
            return head;
        }
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        ListNode prev = dummy;
        for (int i = 0; i < m - 1; i++) {
            prev = prev.next;
        }
        // prev points to the m nodes
        ListNode start = prev.next;
        ListNode then = start.next;
        for (int i = 0; i < n - m; i++) {
            start.next = then.next;
            then.next = prev.next;
            prev.next = then;
            then = start.next;
        }
        return dummy.next;
    }
}

发表于 | 分类于

You are given a binary tree in which each node contains an integer value.

Find the number of paths that sum to a given value.

The path does not need to start or end at the root or a leaf, but it must go downwards (traveling only from parent nodes to child nodes).

The tree has no more than 1,000 nodes and the values are in the range -1,000,000 to 1,000,000.

Example:

root = [10,5,-3,3,2,null,11,3,-2,null,1], sum = 8

  10
 /  \
5   -3

/ \ \
3 2 11
/ \ \
3 -2 1

Return 3. The paths that sum to 8 are:

  1. 5 -> 3
  2. 5 -> 2 -> 1
  3. -3 -> 11

解法1：DFS / Recursion

这题考察DFS的基本知识。因为考虑的是每一个从上到下的path，那么应该要想到要用DFS。
对于每一个节点，如果包括自己，则可以递归运算left 和right，而要match的数则变成了sum - val。
如果不包括自己，则直接运算left和right，最后将两个情况相加就是结果。
实际上这里就是用了一个preorder遍历，回想一下preorder的算法：
visit root;
visit left;
visit right;
这里也一样：
visit root => compute number of paths with root (dfs(root, sum))
visit left => compute number of paths with left (pathSum(root->left, sum))
visit right => compute number of paths with right (pathSum(root->right, sum))

C++

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
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int pathSum(TreeNode* root, int sum) {
        if (root == NULL) {
            return 0;
        }
        int left = pathSum(root->left, sum);
        int right = pathSum(root->right, sum);
        return dfs(root, sum) + left + right;
    }
    int dfs(TreeNode* root, int sum) {
        int res = 0;
        if (root == NULL) {
            return res;
        }
        if (root->val == sum) {
            res++;
        }
        res += dfs(root->left, sum - root->val);
        res += dfs(root->right, sum - root->val);
        return res;
    }
};

Java

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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    public int pathSum(TreeNode root, int sum) {
        if (root == null) {
            return 0;
        }
        int left = pathSum(root.left, sum);
        int right = pathSum(root.right, sum);
        // Count the number of paths starting from the current root
        int startingFromThisRoot = dfs(root, sum);
        return startingFromThisRoot + left + right;
    }
    private int dfs(TreeNode root, int sum) {
        int res = 0;
        if (root == null) return res;
        if (root.val == sum) ++res;
        res += dfs(root.left, sum - root.val);
        res += dfs(root.right, sum - root.val);
        return res;
    }
}

发表于 | 分类于

A strobogrammatic number is a number that looks the same when rotated 180 degrees (looked at upside down).

Write a function to determine if a number is strobogrammatic. The number is represented as a string.

For example, the numbers “69”, “88”, and “818” are all strobogrammatic.

解法1：HashMap, Two pointers, O(N)

题目的意思是一个数倒过来之后和原数一样，那么满足这种性质的单个的数只有0，1，6，8，9. 其中6和9只能搭配使用.
本题用一个hashmap来存储对应的关系可以使解法变得比较干净. 6->9, 9->6, 0，1，8 对应自己。用两个指针，从两边往中间扫描，只有经过映射后的数值相等的情况下颠倒才能保持原数。
C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    bool isStrobogrammatic(string num) {
        unordered_map<char, char> map;
        map['0'] = '0';
        map['1'] = '1';
        map['6'] = '9';
        map['8'] = '8';
        map['9'] = '6';
        int left = 0, right = num.length() - 1;
        while (left <= right) {
            if (map[num[left]] != num[right]) {
                return false;
            }
            ++left;
            --right;
        }
        return true;
    }
};

Java

1

发表于 | 分类于

Given a list, rotate the list to the right by k places, where k is non-negative.

For example:
Given 1->2->3->4->5->NULL and k = 2,
return 4->5->1->2->3->NULL.

解法1：Two pointers, O(N)

这题考的是Linkedlist的基本操作。可以容易看到只要把最后k个元素作为字串挪到list的头部即可。
实际操作可以维护两个指针，同时向右移动，让左指针指向新的头部，右指针指向衔接的地方。
要注意的操作就是k可能会大于linkedlist的长度，那么需要多一个取余操作。
还有对输入的数据范围也需要进行判断，NULL linkedlist直接返回，取余后为0的k也直接返回原list。
C++

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        int len = getLength(head);
        k = k % len;
        ListNode left = head;
        ListNode right = head;
        int count = 0;
        while (count < k) {
            right = right->next;
            ++count;
        }
        while (right->next != NULL) {
            left = left->next;
            right = right->next;
        }
        ListNode* res = left->next;
        left->next = NULL;
        right->next = head;
        return res;
    }
    int getLength(ListNode* head) {
        int count = 0;
        while (head != NULL) {
            ++count;
            head = head->next;
        }
        return count;
    }
};

Java

1

发表于 | 分类于

Write an algorithm to determine if a number is “happy”.

A happy number is a number defined by the following process: Starting with any positive integer, replace the number by the sum of the squares of its digits, and repeat the process until the number equals 1 (where it will stay), or it loops endlessly in a cycle which does not include 1. Those numbers for which this process ends in 1 are happy numbers.

Example: 19 is a happy number

12 + 92 = 82
82 + 22 = 68
62 + 82 = 100
12 + 02 + 02 = 1

解法1：hashmap

这里需要判断重复的情况，想到用hashmap来存储已经计算过的值。对每一个未访问过的数值，计算位数的平方和。
C++

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
class Solution {
public:
    bool isHappy(int n) {
        if (n <= 0) {
            return false;
        }
        if (n == 1) {
            return true;
        }
        unordered_map<int, bool> map;
        while (n != 1) {
            map[n] = true;
            int temp = digitSquareSum(n);
            if (map[temp]) {return false;}
            n = temp;
        }
        return true;
    }
    int digitSquareSum(int n) {
        if (n == 0 || n == 1) {
            return n;
        }
        int sum = 0;
        while (n != 0) {
            int digit = n % 10;
            sum += digit * digit;
            n /= 10;
        }
        return sum;
    }
};

Java

1

解法2：观察规律

看到别人的解法里有这么一个巧妙的方法：可以试试几个会出现loop的数，最后都会出现4。结论是：所有最终会有4的都不是happy number，这样我们就可以把额外的空间要求去除了。
例子如下：
1^2 + 1^2 = 2
2^2 = 4
4^2 = 16
1^2 + 6^2 = 37
3^2 + 7^2 = 58
5^2 + 8^2 = 89
8^2 + 9^2 = 145
1^2 + 4^2 + 5^2 = 42
4^2 + 2^2 = 20
2^2 + 0^2 = 4

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
public:
    bool isHappy(int n) {
        while (n != 1 && n != 4) {
            int t = 0;
            while (n) {
                t += (n % 10) * (n % 10);
                n /= 10;
            }
            n = t;
        }
        return n == 1;
    }
};

发表于 | 分类于

Given an integer, write a function to determine if it is a power of three.

Follow up:
Could you do it without using any loop / recursion?

解法1：Loop

C++

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
public:
    bool isPowerOfThree(int n) {
        if (n < 1) return false;
        while ( n >= 3) {
            if (n % 3 != 0) {
                return false;
            }
            n  = n / 3;
        }
        if (n == 1) {
            return true;
        }
        return false;
    }
};

Java

1

解法2：Follow up

如果一个数是3^x，那么以3为底数做log，结果一定是整数。运用log3(x) = log10(x) / log10(3)
C++

1
2
3
4
5
6
7
class Solution {
public:
    bool isPowerOfThree(int n) {
      double res = log10(n) / log10(3);
      return (res - (int)res) == 0;
    }
};

发表于 | 分类于

You are given two linked lists representing two non-negative numbers. The most significant digit comes first and each of their nodes contain a single digit. Add the two numbers and return it as a linked list.

You may assume the two numbers do not contain any leading zero, except the number 0 itself.

Follow up:
What if you cannot modify the input lists? In other words, reversing the lists is not allowed.

Example:

Input: (7 -> 2 -> 4 -> 3) + (5 -> 6 -> 4)
Output: 7 -> 8 -> 0 -> 7

解法1：Reverse + 两数相加

因为list的头是最高位，我们要相加是从最低位开始加，所以如果能先反转的话比较容易做。分别reverse再求和，最后把结果list再reverse一下就可以了。
C++

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
66
67
68
69
70
71
72
73
74
75
76
77
78
79
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        if (l1 == NULL) {
            return l2;
        }   
        if (l2 == NULL) {
            return l1;
        }
        l1 = reverse(l1);
        l2 = reverse(l2);
        // normal algorithm
        ListNode* dummy = new ListNode(0);
        ListNode* tail = dummy;
        int carry = 0;
        while (l1 != NULL && l2 != NULL) {
            int temp = l1->val + l2->val + carry;
            int digit = temp % 10;
            carry = temp / 10;
            ListNode* node = new ListNode(digit);
            tail->next = node;
            tail = tail->next;
            l1 = l1->next;
            l2 = l2->next;
        }
        while (l1 != NULL) {
            int temp = l1->val + carry;
            ListNode* node = new ListNode(temp % 10);
            carry = temp / 10;
            tail->next = node;
            tail = tail->next;
            l1 = l1->next;
        }
        while (l2 != NULL) {
            int temp = l2->val + carry;
            ListNode* node = new ListNode(temp % 10);
            carry = temp / 10;
            tail->next = node;
            tail = tail->next;
            l2 = l2->next;
        }
        if (carry != 0) {
            ListNode* node = new ListNode(carry);
            tail->next = node;
            tail = tail->next;
        }
        // reverse back
        ListNode* res = reverse(dummy->next);
        delete dummy;
        return res;
    }
    ListNode* reverse(ListNode* head) {
        ListNode* prev = NULL;
        while (head != NULL) {
            ListNode* temp = head->next;
            head->next = prev;
            prev = head;
            head = temp;
        }
        return prev;
    }
};

Java

1

解法2： Follow up O(N) Time and Space

从list的最后加，如果不能反转，需要想到有一种数据结构是可以从后往前存储的，那就是stack。
用两个stack保存每一个队列的node，然后往回加。
C++

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
66
67
68
69
70
71
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
        stack<ListNode*> left;
        stack<ListNode*> right;
        while (l1 != NULL) {
            left.push(l1);
            l1 = l1->next;
        }
        while (l2 != NULL) {
            right.push(l2);
            l2 = l2->next;
        }
        int carry = 0;
        ListNode* res = NULL;
        while (!left.empty() && !right.empty()) {
            ListNode* leftnode = left.top();
            ListNode* rightnode = right.top();
            int temp = leftnode->val + rightnode->val + carry;
            int digit = temp % 10;
            carry = temp / 10;
            ListNode* node = new ListNode(digit);
            node->next = res;
            res = node;
            left.pop();
            right.pop();
        }
        while (!left.empty()) {
            ListNode* leftnode = left.top();
            int temp = leftnode->val + carry;
            int digit = temp % 10;
            carry = temp / 10;
            ListNode* node = new ListNode(digit);
            node->next = res;
            res = node;
            left.pop();
        }
        while (!right.empty()) {
            ListNode* rightnode = right.top();
            int temp = rightnode->val + carry;
            int digit = temp % 10;
            carry = temp / 10;
            ListNode* node = new ListNode(digit);
            node->next = res;
            res = node;
            right.pop();
        }
        if (carry != 0) {
            ListNode* node = new ListNode(carry);
            node->next = res;
            res = node;
        }
        return res;
    }
};

发表于 | 分类于

Given a sorted linked list, delete all duplicates such that each element appear only once.

For example,
Given 1->1->2, return 1->2.
Given 1->1->2->3->3, return 1->2->3.

Hide Tags

解法1：Two pointers O(N)

用双指针，比较两node的值，如果相等，则前面的指针跳过下一个node（删除后一个node）。如果不相等，则两个指针同时向后移动直到尾部。
C++

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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if (head == NULL || head->next == NULL) {
            return head;
        }
        ListNode* res = head;
        ListNode* ptr = head->next;
        while (ptr != NULL) {
            if (head->val == ptr->val) {
                ListNode* temp = ptr;
                head->next = ptr->next;
                delete temp;
                ptr = head->next;
            } else {
                head = head->next;
                ptr = ptr->next;
            }
        }
        return res;
    }
};

Java

1