【LeetCode】Agorithms 题集(一)

【LeetCode】Agorithms 题集(一)

大家好,又见面了,我是全栈君。

Single Number

题目

     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?

思路:

      为了满足时间和空间复杂度,必须利用异或的性质。

      异或: 1 XOR 1 = 0     0 XOR 0 = 0     1 XOR 0 = 1    0 XOR 1 = 1      即同样为 0。不同为1

      依据异或性质,有例如以下等式: 对随意整数。a b c ,  a XOR a = 0    a XOR b XOR a = b

      即随意两个同样的数异或一定得 0, 若是一堆数,除了一个数,其它都是成对出现,则将全部数异或起来,剩下的就是我们要找的数。

复杂度为 O(n)

代码:

class Solution{
public:
    int singleNumber(int A[], int n) {
        int ans;
        for(int i = 0; i < n;++i)
            ans ^= A[i];
        return ans;
    }
};

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 就是根的高度,递归下去即可。

代码

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    int maxDepth(TreeNode *root) {
        if(root == NULL) return 0;

        int ans = 1;
        int l = maxDepth(root->left);
        int r = maxDepth(root->right);

        ans += max(l,r);

        return ans;
    }
};

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.

思路:

      考察递归。

推断两棵树相等,仅仅要递归推断两棵树的结构和值。所以遇到一个指针为空的时候,还有一个指针一定要为空。不为空的时候,两个指针的值必须相等。

再递归左右子树是否相等。

代码:

/**
 * Definition for binary tree
 * 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) {
		bool flag = true;

		/* 当中一个为空,则肯定结束 */
		if(p == NULL || q == NULL)
		{
			/* 两个都为空才是相等的 */
			if(p == NULL && q == NULL)
				return true;
			return false;
		}

		/* 两个节点的值不等则 false */
		if(p->val != q->val) return false;

		/* 递归推断左子树 */
		flag = flag & isSameTree(p->left,q->left);

		/* 递归推断右子树 */
		flag = flag & isSameTree(p->right,q->right);

		return flag;
    }
};

Reverse Integer

题意:

     Reverse digits of an integer.

     Example1: x = 123, return 321
     Example2: x = -123, return -321

思路:

     把整数倒转。非常easy。仅仅要先推断是否负数,存起来。

之后取绝对值,把绝对值倒转后再决定是否是负数。

代码:

class Solution {
public:
    int reverse(int x) {
		bool neg = (x < 0);

		x = abs(x);

		int ans = 0;

		while(x)
		{
			int t = x%10;
			ans = ans*10 + t;
			x = x/10;
		}

		if(neg) ans = -ans;

		return ans;
    }
};

Binary Tree Preorder Traversal

题意:

Given a binary tree, return the preorder traversal of its nodes’ values.

For example:
Given binary tree {1,#,2,3},

   1
    \
     2
    /
   3

return [1,2,3].

Note: Recursive solution is trivial, could you do it iteratively?

思路:

    写个非递归的前序遍历,用 stack.

代码:

/**
 * Definition for binary tree
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode(int x) : val(x), left(NULL), right(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> preorderTraversal(TreeNode *root) {
        vector<int> ans;
        stack<TreeNode *> s;
        TreeNode *p = root;
        while(p != NULL || !s.empty())
        {
            while(p != NULL)
            {
                ans.push_back(p->val);
                s.push(p);
                p = p->left;
            }
            if(!s.empty())
            {
                p = s.top();
                s.pop();
                p = p->right;
            }
        }
        return ans;
    }
};

版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。

发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/115491.html原文链接:https://javaforall.cn

【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛

【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...

(0)


相关推荐

  • Linux环境编程

    Linux环境编程IPC共享内存出处:http://blog.csdn.net/lijun538/article/details/52549159共享内存区是可用IPC形式里面最快的。共享内存允许多个进程同时访问同一内存区,进程会将内存区映射到自己的地址空间中。这样进程间数据的传递不再涉及内核,减少了数据复制的动作。例如一个客户从服务器读的操作,使用管道消息队列等形式的话,需要内核将数据复制到进

  • maven-porm.xml详解

    maven-porm.xml详解什么是POM?POM是项目对象模型(ProjectObjectModel)的简称,它是Maven项目中的文件,使用XML表示,名称叫做pom.xml。作用类似ant的build.xml文件,功能更强大。该文件用于管理:源代码、配置文件、开发者的信息和角色、问题追踪系统、组织信息、项目授权…

  • CF B. Kolya and Tandem Repeat

    CF B. Kolya and Tandem Repeat

  • unity开发微信小游戏1[通俗易懂]

    unity开发微信小游戏1[通俗易懂]unity开发微信小游戏

  • win10怎么安装python3.8_win10怎么安装python

    win10怎么安装python3.8_win10怎么安装python更新提醒:本文已过期,PyTorch0.4.0已经有官方的Windows支持,Windows下安装最新的PyTorch0.4.0请移步本人另一篇博客:Windows下安装PyTorch0.4.0。2017年1月18日,周董生日这一天,facebook下的torch7团队宣布Pytorch开源,官网地址:pytorch。pytorch是一个python优先的深度学习框架,是一个和tensorfl…

  • pycharm安装教程(非常详细)_扶梯安装步骤

    pycharm安装教程(非常详细)_扶梯安装步骤Pycharm安装+Anconda环境配置,需要下载软件的请访问​​​​​​(75条消息)Python软件.zip(pycharm安装包Anconda安装包)-Python文档类资源-CSDN文库(免费下载免费下载免费下载免费下载免费下载免费下载),没有安装Ancondade小伙伴可以访问Anconda安装(超详细)写文章-CSDN博客https://mp.csdn.net/mp_blog/creation/editor/120982868…

发表回复

您的电子邮箱地址不会被公开。

关注全栈程序员社区公众号