【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)


相关推荐

  • 手眼标定Tsai方法的Matlab仿真分析

    手眼标定Tsai方法的Matlab仿真分析手眼标定方程推导手眼标定求解:Tsai方法

  • 请画出下面流程图对应的N-S图以及PAD图_N–S图

    请画出下面流程图对应的N-S图以及PAD图_N–S图在需求分阶段经常使用3种方法去剖析我们所面对的业务。程序流程图任何复杂的程序图都应由5种基本控制结构组成或嵌套而成。盒图(N-S图)Nassi和Scheiderman提出了一种符合结构化程序设计原则的图形描述工具,叫作盒图,也叫做N-S图。任何一个N-S图,都是下面5种PAD图PAD是ProblemAnalysisDiagram的缩写,它是日…

  • 黑盒测试用例设计方法详解

    黑盒测试用例设计方法详解黑盒测试用例设计方法包括等价类划分法、边界值分析法、错误推测法、因果图法、判定表驱动法、正交试验设计法、功能图法、场景图法等。(一)等价类划分法定义:等价类划分法是把所有可能输入的数据,即程序的输入域划分策划国内若干部分(子集),然后从每一个子集中选取少数具有代表性的数据作为测试用例。方法是一种重要的、常用的黑盒测试用例设计方法。等价类是指某个输入域的子集合。在该子集合中,各个输入数据…

  • js判断属性是否存在(javascript的特点)

    参考一:vararray=[{‘yaxis’:22,’lines’:true},{‘lines’:true}]varisTrue=array.some(val=>{returnval.yaxis})if(isTrue===true){console.log(‘数组对象里面存在属性yaxis’)}1.使用in关键字。该方法可…

  • pycharm使用技巧及常用快捷键_键盘怎么自定义改键

    pycharm使用技巧及常用快捷键_键盘怎么自定义改键PyCharm自身提供了大量实用的快捷键,但是由于自己之前其他软件的快捷键使用习惯与此不同,这就需要在PyCharm量身DIY属于自己的快捷键了。快来按照下面的流程操作吧!!!1、File—&gt;Settings【Settings的快捷键大家看到了嘛!!!Ctrl+Alt+S】2、Keymap—&gt;齿轮状设置—&gt;Duplicate建议在设置快捷键之前…

  • 算法练习:排列组合之组合和

    算法练习:排列组合之组合和

发表回复

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

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