leetcode简单题3

发表于   |   分类于   |  

Lowest Common Ancestor of a Binary Search Tree

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).”

1
2
3
4
5
6
7
     _______6______
    /              \
 ___2__          ___8__
/      \        /      \
0      _4       7       9
      /  \
     3    5

此题求最近的祖先，因为是二叉排序树，所以如果a< root < b,则root为最近的祖先，如果root< min(a,b),则a,b的祖先在root的右子树上。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
public:
    TreeNode* lowestCommonAncestor(TreeNode* root, TreeNode* p, TreeNode* q) {
        if(p==NULL||q==NULL||root==NULL)
        {
            return NULL;
        }
        if(p->val< root->val&&q->val< root->val)
        {
            return lowestCommonAncestor(root->left,p,q);
        }
        if(p->val>root->val&&q->val>root->val)
        {
            return lowestCommonAncestor(root->right,p,q);
        }
        else
        {
            return root;
        }
    }
};

Sum of Two Integers

alculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example:
Given a = 1 and b = 2, return 3.

不用+ - 来做加运算

可以通过“与” 和“异或” 来代替加运算
如3+2，可以先进行^操作，
1 0
1 1
====异或
0 1
此时，只有进位的元素没有进行相加，没有进位的元素都进行了相加，我们可以用此值与进位的元素再&操作
先计算进位元素的值
1 0
1 1
====与
1 0
再往左移动一位，即进位，变为1 0 0
0 1
1 0 0
======异或
1 0 1
为最终值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
public:
   int getSum(int a, int b) {
	int cur = a^b;
	int carry = (a&b) << 1;
	int result = cur;
	while (carry != 0)
	{
		result = cur^carry;
		carry = (cur&carry) << 1;
		cur=result;
	}
	return result;
}
};

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
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==1)
            return true;
        int temp=num;
        while(num!=1)
        {
            if(temp%2==0)
                temp/=2;
            if(temp%3==0)
                temp/=3;
            if(temp%5==0)
                temp/=5;
            if(temp==num) //此轮没变化，即没有除以2，3，5，则不是丑数
                return false;
            num=temp;
        }
        return true;
    }
};

Remove Duplicates from Sorted List

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    ListNode* deleteDuplicates(ListNode* head) {
        if(head==NULL)
            return NULL;
        if(head->next==NULL)
            return head;
        ListNode* p=head;
        while(p->next!=NULL)
        {
            if(p->val==p->next->val)
            {
                p->next=p->next->next;
            }
            else
            {
                p=p->next;
            }
        }
        return head;
    }
};

Climbing Stairs

You are climbing a stair case. It takes n steps to reach to the top.

Each time you can either climb 1 or 2 steps. In how many distinct ways can you climb to the top?

斐波那契数列问题，这里为了降低迭代次数和多余的重复节点的计算，采用了非递归版本

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
public:
    int climbStairs(int n) {
        if(n==0||n==1||n==2)
            return n;
        int pre=1;
        int p=2;
        int sum=p;
        for(int i=3;i<=n;i++)
        {
            sum=pre+p;
            pre=p;
            p=sum;
        }
        return sum;
    }
};

Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:

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

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
public:
    int maxProfit(vector<int>& prices) {
        int len=prices.size();
        if(len==0||len==1)
            return 0;
        int min=prices[0];
        int sum=0;
        for(int i=1;i<len;i++)
        {
            if(prices[i]<min)
                min=prices[i];
            else if(prices[i]>min)
            {
                int temp=prices[i]-min;
                if(temp>sum)
                    sum=temp;
            }
        }
        return sum;
    }
};

Linked List Cycle

Given a linked list, determine if it has a cycle in it.

Follow up:
Can you solve it without using extra space?

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:
    bool hasCycle(ListNode *head) {
        if(head==NULL||head->next==NULL)
            return false;
        ListNode* slow=head;
        ListNode* fast=head->next;
        while(slow!=NULL&&fast!=NULL)
        {
            if(slow==fast)
            {
                return true;
            }
            if(fast->next!=NULL&&fast->next->next!=NULL)
            {
                fast=fast->next->next;
                slow=slow->next;
            }
            else
                return false;
                
        }
        return false;
    }
};