怒刷leetcode的标题（1）237、104、136、100

怒刷leetcode的题目（1）237、104、136、100

https://leetcode.com/problemset/algorithms/上面的题目，每天做几道题目，大体从准确率高至低做下去

编程语言为c语言，因为跑的最快…

237	Delete Node in a Linked List	47.8%	Easy

Write a function to delete a node (except the tail) in a singly linked list, given only access to that node.

Supposed the linked list is 1 -> 2 -> 3 -> 4 and you are given the third node with value 3, the linked list should become 1 -> 2 -> 4 after calling your function.

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
void deleteNode(struct ListNode* node) {
    if(node->next != NULL){
        node->val = node->next->val;
        node->next=node->next->next;   
    }
}

删除给定的节点，只需要将当前节点的val改成下个节点的值，这时候相当于有两个相同值的节点，再将当前节点的next指针指向下下个节点，也就是跳过第二个相同的节点就好了。

104	Maximum Depth of Binary Tree	45.1%	Easy

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.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */

 
int maxDepth(struct TreeNode* root) {
    if(root == NULL) // 递归出口  
        return 0;  
    int depthLeft = maxDepth(root->left);  
    int depthRight = maxDepth(root->right);  
    return depthLeft > depthRight ? (depthLeft + 1) : (depthRight + 1);  
}

求二叉树的深度，使用递归的思想，将root想做普通节点，任何节点的深度都是左右节点较深的那个值+1，除了树叶（深度为0，也是递归的结束条件）

136	Single Number	45.0%	Medium

Given an array of integers, every element appears twice except for one. Find that single one.

Note:
Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

int singleNumber(int* nums, int numsSize) {
        if (nums == 0 || numsSize < 1)  
            return 0;  
        int key = nums[0];  
        for (int i = 1; i < numsSize; ++i) {  
            key ^= nums[i];  
        }  
        return key;  
}

难点在于数组规模增大，运行时间只能线性增长。

将数组的所有元素进行异或运算，相同的元素异或等于0，唯一的元素与0异或等于自己。

100	Same Tree	41.5%	Easy

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.

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
bool isSameTree(struct TreeNode* p, struct TreeNode* q) {
    if(!p && !q) return true;  //NULL together, the same,skip the remaining code
    if(!p || !q) return false; //one is NULL but the other is not
    return (p->val == q->val) && isSameTree(p->left, q->left) && isSameTree(p->right, q->right);     
}

跟104题类似，使用递归的思想，二叉树相同，意味着从根节点开始，必须符合对应节点的值相同+左节点为根节点的树相同+右节点为根节点的树相同

先判断!p&&!q同时为树叶节点，两个为相同的树

如果不同时为树叶节点，则判断两者是否有一方是树叶节点，如果是，则他们不是一样的树

对根节点运行算法就可以得出结果

怒刷leetcode的标题（1）237、104、136、100

相关推荐