Tag: LeetCode OJ

题目：https://leetcode.com/problems/same-tree/
分析：注意判断NULL情况，用递归做
代码：（秒AC有木有！）

/**
 * 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:
    bool isSameTree(TreeNode* p, TreeNode* q) {
        if(p == NULL && q == NULL)
            return true;
        if(p == NULL || q == NULL)
            return false;
        if(p->val != q->val)
            return false;
        return isSameTree(p->left, q->left) && isSameTree(p->right, q->right);
    }
};

题目：https://leetcode.com/problems/invert-binary-tree/
思路：这TM还要思路？
代码：

/**
 * 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* invertTree(TreeNode* root) {
        if(root == NULL)
            return root;
        TreeNode *tmpNode = root->right;
        root->right = root->left;
        root->left = tmpNode;
        if(root->left != NULL)
            invertTree(root->left);
        if(root->right != NULL)
            invertTree(root->right);
        return root;
    }
};

题目：https://leetcode.com/problems/delete-node-in-a-linked-list/
思路：
因为只给要删去节点的指针，所以就要想点歪办法。
假设我们有节点1,2,3,【4】,5,6，要删去4这个点，那其实只要把后序节点5的值复制给4，然后我们可以把后面原来那个5删掉，把原有的4节点链到6就行了~大致意思就是，通过往前复制一个值，构造出一个新的“4”的前序节点。

使用前：1,2,3,[4],5,6
拷贝值：1,2,3,5,[5],6
删去多于节点(将新的5节点链接到拷贝的5右边的6，删去老的5节点)：1,2,3,5,6

代码：

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    void deleteNode(ListNode* node) {
        ListNode* nextNode = node->next;
        node->val = nextNode->val; //Copy value
        ListNode* thirdNode = nextNode->next;
        node->next = thirdNode;
        delete nextNode;
    }
};

题目：https://leetcode.com/problems/maximum-depth-of-binary-tree/
思路：就是个树遍历的东西，很简单地可以用递归实现
代码：

/**
 * 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 maxDepth(TreeNode* root) {
        // Left - N - Right
        if(root == NULL) {
            return 0;
        } else {
            //Non-empty
            int leftDeep = 1 + maxDepth(root->left);
            int rightDeep = 1 + maxDepth(root->right);
            if(leftDeep > rightDeep)
                return leftDeep;
            else
                return rightDeep;
        }
    }
};

链接：https://leetcode.com/problems/add-two-numbers/
思路：
两条链表，从其中一段开始修改，直接在原有节点上做加法。碰到其中一条结束的时候，如果另一条还在继续，则把next指向另一条链表往后一个节点（感觉像是铁轨并轨一样）。
注意如果加起来还有多，要新建一个节点存放。
代码:

class Solution {
public:
	ListNode* addTwoNumbers(ListNode* l1, ListNode* l2) {
		ListNode* retNode = l1;
		ListNode* prevNode = NULL;
		int res = 0;
		while (l1 != NULL && l2 != NULL) {
			l1->val += (l2->val + res);
			res = 0;
			while (l1->val >= 10) {
				l1->val -= 10;
				res += 1;
			}
			prevNode = l1;
			l1 = l1->next;
			l2 = l2->next;
		}
		if (res == 0 && l1 == NULL && l2 == NULL)
			return retNode;
		ListNode* currNode = l1;
		if (l1 == NULL) {
		    prevNode->next = l2;
			currNode = l2;
		}
		while (currNode != NULL && res != 0) {
			currNode->val += res;
			res = 0;
			while (currNode->val >= 10) {
				currNode->val -= 10;
				res += 1;
			}
			prevNode = currNode;
			currNode = currNode->next;
		}
		if (res > 0) {
			//Add Node
			ListNode* endNode = new ListNode(res);
			prevNode->next = endNode;
		}
		return retNode;
	}
};

结果：

原题地址：https://leetcode.com/problems/nim-game/
思路：
这题目是个找规律的题，号称全OJ最简单….通过找规律可以发现，当n为4的倍数时，无论如何自己都赢不了…然后搞定了
代码：

class Solution {
public:
    bool canWinNim(int n) {
        if(n%4 == 0)
            return false;
        return true;
    }
};

恩，据说刷LeetCode比较好玩，于是乎从第一题开始吧。
题目：
Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.
Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2
思路：
这道题给的Hint是二叉树，我有点不太懂，用二叉树实现了一个版本，不过会超时。想了下还是用map的黑科技吧，反正没限制内存大小。（再黑科技一点可以直接用数组，就是数据多的话要找到最小/最大值做好映射）
代码：

class Solution {
private:
	map<int, int> valTable;
public:
	vector<int> twoSum(vector<int>& nums, int target) {
		for (int i = 0; i < nums.size(); i++) {
			int val = nums[i];
			valTable[val] = i + 1;
		}
		for (int i = 0; i < nums.size(); i++) {
			int ne = target - nums[i];
			map<int, int>::iterator result = valTable.find(ne);
			if (result != valTable.end()) {
				int nextIndex = result->second;
				int currIndex = i + 1;
				if (currIndex == nextIndex)
					continue;
				vector<int> retIndices;
				if (currIndex > nextIndex) {
					retIndices.push_back(nextIndex);
					retIndices.push_back(currIndex);
				}
				else {
					retIndices.push_back(currIndex);
					retIndices.push_back(nextIndex);
				}
				return retIndices;
			}
		}
	}
};

运行结果：
我只超过了30.19%的队友，哈哈~

 
 
2018 refined (beats 92.29%):

class Solution {
public:
    vector<int> twoSum(vector<int>& nums, int target) {
        unordered_map<int, size_t> num_indices; // <number, indices>
        for (size_t i = 0; i < nums.size(); ++i)
        {
            auto num = nums[i];
            if (num_indices.count(target - num) > 0)
            {
                return {num_indices[target - num], i};
            }
            num_indices[num] = i;
        }
        return {-1, -1};
    }
};