题意： 树的层次遍历，基础数据结构题。 代码 struct TreeNode { int val; TreeNode *left; TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) {} }; struct Node { TreeNode *TN; int L; Node(TreeNode *t, int i) :TN(t), L(i) {}; }; vector<vector<int>> levelOrder(TreeNode* root) { list&lt...

题意： 判断一颗二叉树是否对称 代码： bool comp(TreeNode* l, TreeNode* r) { if (l == NULL&&r == NULL) return true; if (l == NULL||r == NULL) return false; if (l->val != r->val) return false; return comp(l->left, r->right) && comp(l->right, r->left); } bool isSymmetric(...

题意： 判断一个数是否是二叉搜索树。 思路： 二叉排序树的任意一个节点的左节点比其小，右节点比其大，那么中序遍历会得到一个有序数组。利用非递归遍历，每次的数都应该比上次的大，否则就不是BST。 bool isValidBST(TreeNode* root) { if (!root) return true; if (!(root->right || root->left)) return true; TreeNode* p = root; int flag = 1; int last; stack<TreeNode*> s; while (...

题意： 非递归中序遍历。 树的先序遍历 vector<int> preorderTraversal(TreeNode* root) { stack<TreeNode*> s; vector<int> res; TreeNode *p = root; while (p || !s.empty()) { while (p) { s.push(p); //res.push_back(p->val); p = p->left; } if (!s.empty()) { p = s.top(); s.p...

题意: 给一个由数字组成的非空字符串，1对应A，2对应B，… ，26对应Z，问这个字符串可以转换成多少种编码。 思路：动态规划 与跳台阶题的思想类似，但是对于跳一阶和跳两阶加了条件。 dp[i]表示s[0]~s[i-1]的可编码个数。 若s[i-1]属于1~9，dp[i]+=dp[i-1] 所s[i-2] s[i-1]属于1~26，dp[i]+=dp[i-2] int numDecodings(string s) { if (s.empty() || s[0] == '0') return 0; if (s.size() == 1) return 1; vector&l...

题意： 给两个已排序数组，合成一个已排序数组。 简单题 没什么好说的 代码： void merge(vector<int>& nums1, int m, vector<int>& nums2, int n) { nums1.resize(m + n); int i = m - 1, j = n - 1, k = m + n - 1; while (k) nums1[k--] = i >= 0 && nums1[i] > nums2[j] ? nums1[i--] : nums2[j--]; }

题意 给一个包含n个非负数的数组，表示n个宽度为1的直方柱，求可以用长方形圈出来的最大面积。 思路1： 以上图为例，我们用一个res表示目前得到的最大面积，首先第一次扫描数组，获得最矮直方体1，res=1*6。 然后若获得比这个面积大的面积，肯定是要剔除该高度为1的直方柱。故求1左面和1右面，递归。 int func(vector<int>& heights, int left, int right) { if (left == right) return heights[left]; if (left > right) return 0; int ...

1. vector vector与数组array十分相似，但array是静态空间，而vector是动态空间，可以通过内部机制自行扩充空间，具有很好的灵活性。 其实现的关键在于对大小的控制和重新配置时的数据移动效率。 vector的型别定义如下: template <class T, class Alloc = alloc> class vector{ // ... public: typedef T value_type; typedef value_type* pointer; typedef value_type* iterator; ty...

题意： 在一个二维数组中是否可以匹配到一个字符串，这个字符串在二维数组中可以拐弯，但必须连续。 思路：深搜+回溯 遍历数组，若数组中元素等于字符串第一个字符进入深搜。 深搜中有一个参数k，表示已经匹配的字符数，若k==word.size()，则表示字符串完全匹配成功。 有一个二维数组参数flag，flag[i][j]表示i j位置是否已经被划入匹配范围，若flag[i][j]=0，则表示已匹配，后面不能再使用这个字符。 在每次dfs开始时需将对应位置置0，然后在结束时需要将对应位置置1. bool dfs(vector<vector<char>>& bo...

题意： 给一个包含多个数字的数组，返回这些数字组成的所有的子数组的集合。 思路：dfs 每遇到一个数均有两个选择：①将其加入子数组 ②跳过这个数。 当遍历到数组末尾的时候，将得到的子数组加入结果集。 void dfs(vector<int>& nums, vector<int> &cur, vector<vector<int>> &res, int i) { if (i == nums.size()) { res.push_back(cur); return; } dfs(nums, cur, res...

转载地址：http://www.cnblogs.com/gw811/archive/2012/10/25/2738929.html C++模板   模板是C++支持参数化多态的工具，使用模板可以使用户为类或者函数声明一种一般模式，使得类中的某些数据成员或者成员函数的参数、返回值取得任意类型。   模板是一种对类型进行参数化的工具；   通常有两种形式：函数模板和类模板；   函数模板针对仅参数类型不同的函数；   类模板针对仅数据成员和成员函数类型不同的类。   使用模板的目的就是能够让程序员编写与类型无关的代码。比如编写了一个交换两个整型int 类型的swap...

题意: 给两个字符串s和t,在s中寻找包含t中全部字符的最短子串. 滑动窗算法: https://blog.csdn.net/haolexiao/article/details/54781671 滑动窗方法算是解决数组或者字符串中，处理连续的字符串段应该想到的一种方法，这里面有变长滑动窗，和定长滑动窗。滑动窗问题总共要处理两个方面，一个是新加入点和处理和移除滑动窗点点的处理。 void slidingwindows(vector<int> nums,int k){ 先预处理 然后进行滑动窗的循环，一般是个while循环，同时实现定义好滑动窗的起点和终点，同时...

题目： 一个数组包含0，1，2，对他们进行排序 思路1： two-pass 大家都能想到的，对0 1 2进行计数，然后重新调整数组，共遍历两次 void sortColors(vector<int>& nums) { //two-pass int red = 0, white = 0, blue = 0; for_each(nums.begin(), nums.end(), [&](int &n) { switch (n) { case 0:++red; case 1:++white; case 2:++blue; bre...

题意： 一个m * n数组若一个数为0，则将其所在的行、列所有数都设置为0，要求使用In-Place 算法。 In-Place 在原数组空间进行操作，即使空间复杂度为O（1）。 思路1：空间复杂度O（mn） void setZeroes(vector<vector<int>>& matrix) {//O(mn) if (matrix.empty() || matrix[0].empty()) return; int m = matrix.size(), n = matrix[0].size(); vector<pair<int, in...