大家好,又见面了,我是全栈君。
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账号...