leetcode简单题1

发表于   |   分类于   |  

Nim Game

You are playing the following Nim Game with your friend: There is a heap of stones on the table, each time one of you take turns to remove 1 to 3 stones. The one who removes the last stone will be the winner. You will take the first turn to remove the stones.

Both of you are very clever and have optimal strategies for the game. Write a function to determine whether you can win the game given the number of stones in the heap.

For example, if there are 4 stones in the heap, then you will never win the game: no matter 1, 2, or 3 stones you remove, the last stone will always be removed by your friend.

题意：写个程序判断你能否赢得比赛
规则：每次可以拿1，2，3个石子，谁能拿到最后一个石子，谁赢

思路：因为每个人都取不到4个，假设自己后走，要保证每轮自己和对方取得数量的和是4，这样就能确保每轮完后都有4的倍数个石头被取走。这样，如果我们先走的话，先把n除4的余数个石头拿走，这样不管怎样，到最后都会留4个下来，对方取1个你就取3个，对方取2个你就取2个，就必赢了。

1
2
3
4
5
6
public class Solution {
    public boolean canWinNim(int n) {
        // 如果一开始就是4的倍数，你就输了，因为对方可以用同样的策略
        return n % 4 != 0;
    }
}

Add Digits

Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.

For example:

Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.

Follow up:
Could you do it without any loop/recursion in O(1) runtime?

思路：怎么才能把复杂度降到O(1)呢，这一般都是用公式，这就要从中找到规律。我们列出前30个数据测试：
0 0
1 1
2 2
3 3
4 4
5 5
6 6
7 7
8 8
9 9
10 1
11 2
12 3
13 4
14 5
15 6
16 7
17 8
18 9
19 1
20 2
21 3
22 4
23 5
24 6
25 7
26 8
27 9
28 1
29 2
规律：(n-1)%9+1

1
2
3
4
5
6
7
class Solution {
public:
    int addDigits(int num) {
        return (num-1)%9+1;
        
    }
};

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.
求二叉树的高度

1
2
3
4
5
6
7
8
9
10
class Solution {
public:
    int maxDepth(TreeNode* root) {
        if(root==NULL)
        return 0;
        int left=maxDepth(root->left);
        int right=maxDepth(root->right);
        return max(left,right)+1;
    }
};

Invert Binary Tree

Invert a binary tree.
4
/ \
2 7
/ \ / \
1 3 6 9
to
4
/ \
7 2
/ \ / \
9 6 3 1

1
2
3
4
5
6
7
8
9
10
11
class Solution {
public:
    TreeNode* invertTree(TreeNode* root) {
        if(root==NULL)
        return NULL;
        TreeNode *temp=root->left;   //交换并递归
        root->left=invertTree(root->right);
        root->right=invertTree(temp);
        return root;
    }
};

Move Zeroes

Given an array nums, write a function to move all 0’s to the end of it while maintaining the relative order of the non-zero elements.

For example, given nums = [0, 1, 0, 3, 12], after calling your function, nums should be [1, 3, 12, 0, 0].

Note:
You must do this in-place without making a copy of the array.
Minimize the total number of operations.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    void moveZeroes(vector<int>& nums) {
        int len=nums.size();
        int count=0;
        for(int i=0;i<len;i++)
        {
            if(nums[i]==0)
            {
                count++;
            }
            else
            {
                swap(nums[i],nums[i-count]);  //和（当前）最前面的0交换，这样所有的0都会跑到最后面
            }
        }
    }
};

Intersection of Two Arrays

Given two arrays, write a function to compute their intersection.

Example:
Given nums1 = [1, 2, 2, 1], nums2 = [2, 2], return [2].
思路：一个map，遍历第二个数组时，出现则改为false

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:
    vector<int> intersection(vector<int>& nums1, vector<int>& nums2) {
        map<int,bool> M;
        int len1=nums1.size();
        int len2=nums2.size();
        vector<int> s;
        for(int i=0;i<len1;i++)
        {
            if(M[nums1[i]]==false)
            {
                M[nums1[i]]=true;
            }
        }
        for(int i=0;i<len2;i++)
        {
            if(M[nums2[i]])
            {
                s.push_back(nums2[i]);
                M[nums2[i]]=false;
            }
        }
        return s;
    }
};

Delete Node in a Linked List

单链表删除一个节点，只给出这个节点的指针

1
2
3
4
5
6
7
class Solution {
public:
    void deleteNode(ListNode* node) {
        node->val=node->next->val;
        node->next=node->next->next;
    }
};

Same Tree

Given two binary trees, write a function to check if they are equal or not.

Two binary trees are considered equal if they are structurally identical and the nodes have the same value.
判断两个二叉树是否相同

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

Excel Sheet Column Number

Given a column title as appear in an Excel sheet, return its corresponding column number.

For example:
A -> 1
B -> 2
C -> 3
…
Z -> 26
AA -> 27
AB -> 28
思路：26进制

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
public:
    int titleToNumber(string s) {
        int len=s.length();
        int temp=0;
        for(int i=0;i<len;i++)
        {
            temp=temp*26+s[i]-'A'+1;
        }
        return temp;
    }
};