Monthly Archives: February 2017

LeetCode Search a 2D Matrix II

240. Search a 2D Matrix II 240. Search a 2D Matrix II

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted in ascending from left to right.
  • Integers in each column are sorted in ascending from top to bottom.

Example:

Consider the following matrix:

[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

Given target = 5, return true.

Given target = 20, return false. 240. Search a 2D Matrix II


LeetCode Search a 2D Matrix基础上改动了一点点,但是难度增加不少。这一次,每行和每列都是递增的,但是这一行的行首元素和上一行的行末元素没有大小关系,这种矩阵有点像从左上角递增到右下角的一个曲面,想象一下。 一种比较笨的办法就是对每一行或者每一列二分搜索,复杂度为O(mlgn)或O(nlgm)。 参考这位大神的介绍,有很多厉害的算法,具体看原博客,这里简单给出其前两个算法的C++实现。 算法1相当于对角二分搜索,是线性复杂度的。搜索从矩阵右上角开始,遇到比当前元素大时,递增行;遇到比当前元素小时,递减列;直到找到相等元素,或者到达矩阵左下角。最坏情况是从右上角走到了左下角,复杂度为O(m+n)。 这种思路的代码如下:

class Solution {
public:
    bool searchMatrix(vector<vector<int> >& matrix, int target)
    {
        if (matrix.size() == 0)
            return false;
        int m = matrix.size(), n = matrix[0].size();
        if (n == 0)
            return false;
        int i = 0, j = n – 1;
        while (i < m && j >= 0) {
            while (i < m && matrix[i][j] < target)
                ++i;
            if (i >= m)
                return false;
            while (j >= 0 && matrix[i][j] > target)
                –j;
            if (j < 0)
                return false;
            if (matrix[i][j] == target)
                return true;
        }
        return false;
    }
};

本代码提交AC,用时129MS。
算法2利用了分治法的思路。每次取矩阵中心元素,把矩阵分成4个小份。如果target大于中心元素,则左上角部分可以全部舍弃掉,因为矩阵的行列都是递增的,左上角元素肯定全部小于中心元素,不必再找。此时可以递归的在剩余的3个小矩阵里查找。比如下图中心元素为9,如果要找26,则可以递归的在其右上角、左下角和右下角三个小矩阵中查找。

时间复杂度公式为T(n)=3T(n/2)+c,c为target和中心元素比较的时间。使用主方法可以算到T(n)=O(n1.58)。
分治法思路代码如下:

class Solution {
public:
    bool quadPart(vector<vector<int> >& matrix, int left, int top, int right, int bottom, int target)
    {
        if (left > right || top > bottom)
            return false;
        if (target < matrix[left][top] || target > matrix[right][bottom])
            return false;
        int midrow = left + (right - left) / 2, midcol = top + (bottom - top) / 2;
        if (target == matrix[midrow][midcol])
            return true;

        //if (target > matrix[midrow][midcol]) { // 抛弃左上角
        //	return quadPart(matrix, left, midcol + 1, midrow - 1, bottom, target) || // 右上角
        //		quadPart(matrix, midrow + 1, top, right, midcol - 1, target) || // 左下角
        //		quadPart(matrix, midrow, midcol, right, bottom, target); // 右下角
        //}
        //else {
        //	return quadPart(matrix, left, midcol + 1, midrow - 1, bottom, target) || // 右上角
        //		quadPart(matrix, midrow + 1, top, right, midcol - 1, target) || // 左下角
        //		quadPart(matrix, left, top, midrow, midcol, target); //左上角
        //}

        if (target > matrix[midrow][midcol]) { // 抛弃左上角
            return quadPart(matrix, left, midcol + 1, midrow, bottom, target) || // 右上角
                quadPart(matrix, midrow + 1, top, right, midcol, target) || // 左下角
                quadPart(matrix, midrow + 1, midcol + 1, right, bottom, target); // 右下角
        }
        else {
            return quadPart(matrix, left, midcol, midrow - 1, bottom, target) || // 右上角
                quadPart(matrix, midrow, top, right, midcol - 1, target) || // 左下角
                quadPart(matrix, left, top, midrow - 1, midcol - 1, target); //左上角
        }
    }
    bool searchMatrix(vector<vector<int> >& matrix, int target)
    {
        if (matrix.size() == 0)
            return false;
        int m = matrix.size(), n = matrix[0].size();
        if (n == 0)
            return false;
        return quadPart(matrix, 0, 0, m - 1, n - 1, target);
    }
};

本代码提交AC,用时168MS。
注意代码中注释掉的部分是错误代码,因为其在右下角或者左上角搜索时可能会进入死循环。比如要在上图搜索30,当搜索到右下角深色部分的小矩阵时,中心元素是17,本该搜索更小的矩阵30,但是根据注释代码中第一个if搜索右下角的代码,新的矩阵(右下角)的左上角坐标还是17,因为其坐标是(midrow, midcol),无论递归多少次,右下角的矩阵没有变小,所以进入了死循环。
正确的方法是把涉及到中点的两条边分配到不同的小矩阵里,必须使得每个小矩阵的左上角或右下角坐标有变化。

LeetCode Search a 2D Matrix

74. Search a 2D Matrix

Write an efficient algorithm that searches for a value in an m x n matrix. This matrix has the following properties:

  • Integers in each row are sorted from left to right.
  • The first integer of each row is greater than the last integer of the previous row.

Example 1:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 3
Output: true

Example 2:

Input:
matrix = [
  [1,   3,  5,  7],
  [10, 11, 16, 20],
  [23, 30, 34, 50]
]
target = 13
Output: false

给定一个矩阵,每行升序排列,并且下一行的最小值大于上一行的最大值,也就是说如果把矩阵按行展开,就是一个递增序列。问矩阵中是否存在一个数target。 很明显是二分搜索,先把每个行首元素看成一个新的有序数组,进行二分查找,确定所在行midr。然后在这一行进行二分搜索,查找target。 完整代码如下:

class Solution {
public:
    bool searchMatrix(vector<vector<int> >& matrix, int target)
    {
        if (matrix.size() == 0)
            return false;
        int m = matrix.size(), n = matrix[0].size();
        if (n == 0)
            return false;
        int l = 0, r = m – 1, midr = 0, midc = 0;
        while (l <= r) {
            midr = (l + r) / 2;
            if (target >= matrix[midr][0]) {
                if (target <= matrix[midr][n – 1])
                    break;
                l = midr + 1;
            }
            else
                r = midr – 1;
        }
        l = 0, r = n – 1;
        while (l <= r) {
            midc = (l + r) / 2;
            if (target == matrix[midr][midc])
                return true;
            if (target > matrix[midr][midc])
                l = midc + 1;
            else
                r = midc – 1;
        }
        return false;
    }
};

本代码提交AC,用时9MS。

二刷。更加规范的代码。首先找到目标数字所在的行,即找每一行开头数字中第一个大于目标数字的行,则前一行即为该数字所在的行,也就是l-1。为什么是l-1而不是r+1呢?这样想象:我们要找比target大的行首元素,如果mid一直小于target的话,则l会一直进行mid+1操作,直到l指向的元素大于target,此时前一行即为target所在行。不过要注意判断前一行是否存在的情况。

class Solution {
public:
	bool BinarySearch(vector<int>& vec, int target) {
		int l = 0, r = vec.size() - 1;
		while (l <= r) {
			int mid = l + (r - l) / 2;
			if (vec[mid] == target)return true;
			if (vec[mid] < target)l = mid + 1; 
			else r = mid - 1;
		}
		return false;
	}
	bool searchMatrix(vector<vector<int>>& matrix, int target) {
		int m = matrix.size();
		if (m == 0)return false;
		int n = matrix[0].size();
		if (n == 0)return false;

		int l = 0, r = m - 1;
		while (l <= r) {
			int mid = l + (r - l) / 2;
			if (matrix[mid][0] == target)return true;
			if (matrix[mid][0] < target)l = mid + 1; 
			else r = mid - 1;
		}
		if (l < 1)return false;
		return BinarySearch(matrix[l - 1], target);
	}
};

本代码提交AC,用时16MS。

LeetCode Find Peak Element

162. Find Peak Element

A peak element is an element that is greater than its neighbors.

Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that nums[-1] = nums[n] = -∞.

Example 1:

Input: nums = [1,2,3,1]
Output: 2
Explanation: 3 is a peak element and your function should return the index number 2.

Example 2:

Input: nums = [1,2,1,3,5,6,4]
Output: 1 or 5 
Explanation: Your function can return either index number 1 where the peak element is 2, 
             or index number 5 where the peak element is 6.

Note:

Your solution should be in logarithmic complexity.


要求在一个数组中找一个局部峰值的下标,局部峰值就是大于其左右相邻的两个元素。
暴力方法就是线性查找。更好一点的方法就是二分查找。如果中值nums[m]正好大于其左右相邻的元素,则返回m;如果nums[m]<nums[m-1],则在左边查找,因为nums[m-1]已经大于其右半边了,所以左边很有希望找到峰值,如果nums[m-1]>nums[m-2]也成立,则nums[m-1]就是峰值;否则继续往左边找,因为nums[-1]=-∞,所以肯定能找到一个局部峰值。右边也是类似。
代码如下:

class Solution {
public:
    int findPeakElement(vector<int>& nums)
    {
        int n = nums.size();
        if (n == 1)
            return 0;
        int l = 0, r = n – 1, m = 0;
        while (l <= r) {
            m = (l + r) / 2;
            if ((m == 0 || nums[m] > nums[m – 1]) && (m == n – 1 || nums[m] > nums[m + 1]))
                return m;
            if (m > 0 && nums[m] < nums[m – 1])
                r = m – 1;
            else
                l = m + 1;
        }
        return m;
    }
};

本代码提交AC,用时6MS。

二刷。相同思路,不同代码:

class Solution {
public:
	int findPeakElement(vector<int>& nums) {
		int n = nums.size();
		if (n == 1)return 0;
		if (n == 2)return nums[0] > nums[1] ? 0 : 1;

		int l = 0, r = n - 1;
		while (l <= r) {
			if (r - l <= 1)return nums[l] > nums[r] ? l : r;

			int mid = l + (r - l) / 2;
			if (nums[mid] > nums[mid - 1] && nums[mid] > nums[mid + 1])return mid;
			if (nums[mid] < nums[mid - 1]) {
				r = mid - 1;
			}
			else {
				l = mid + 1;
			}
		}
		return 0;
	}
};

本代码提交AC,用时12MS。

LeetCode Arranging Coins

LeetCode Arranging Coins You have a total of n coins that you want to form in a staircase shape, where every k-th row must have exactly k coins. Given n, find the total number of full staircase rows that can be formed. n is a non-negative integer and fits within the range of a 32-bit signed integer. Example 1:

n = 5
The coins can form the following rows:
¤
¤ ¤
¤ ¤
Because the 3rd row is incomplete, we return 2.
Example 2:
n = 8
The coins can form the following rows:
¤
¤ ¤
¤ ¤ ¤
¤ ¤
Because the 4th row is incomplete, we return 3.

问n个硬币最多能摆成多少级台阶,每级台阶的硬币数是以1为步长递增的。其实就是求1+2+…+k<=n的最大的k。当然最简单的方法是暴力枚举[1,n]之间的k。 O(lgn)的方法是二分搜索满足上述不等式的最大的k。代码如下: [cpp] class Solution { public: int arrangeCoins(int n) { long long l = 0, r = n; while (l <= r) { long long m = (l + r) / 2; long long sum = (1 + m)*m / 2; if (n < sum)r = m – 1; else l = m + 1; } return r; } }; [/cpp] 本代码提交AC,用时35MS。 参考:http://bookshadow.com/weblog/2016/10/30/leetcode-arranging-coins/ P.S.感觉二分搜索的代码边界条件很麻烦。。。]]>

LeetCode UTF-8 Validation

LeetCode UTF-8 Validation A character in UTF8 can be from 1 to 4 bytes long, subjected to the following rules:

  1. For 1-byte character, the first bit is a 0, followed by its unicode code.
  2. For n-bytes character, the first n-bits are all one’s, the n+1 bit is 0, followed by n-1 bytes with most significant 2 bits being 10.
This is how the UTF-8 encoding would work:
   Char. number range  |        UTF-8 octet sequence
      (hexadecimal)    |              (binary)
   --------------------+---------------------------------------------
   0000 0000-0000 007F | 0xxxxxxx
   0000 0080-0000 07FF | 110xxxxx 10xxxxxx
   0000 0800-0000 FFFF | 1110xxxx 10xxxxxx 10xxxxxx
   0001 0000-0010 FFFF | 11110xxx 10xxxxxx 10xxxxxx 10xxxxxx
Given an array of integers representing the data, return whether it is a valid utf-8 encoding. Note: The input is an array of integers. Only the least significant 8 bits of each integer is used to store the data. This means each integer represents only 1 byte of data. Example 1:
data = [197, 130, 1], which represents the octet sequence: 11000101 10000010 00000001.
Return true.
It is a valid utf-8 encoding for a 2-bytes character followed by a 1-byte character.
Example 2:
data = [235, 140, 4], which represented the octet sequence: 11101011 10001100 00000100.
Return false.
The first 3 bits are all one's and the 4th bit is 0 means it is a 3-bytes character.
The next byte is a continuation byte which starts with 10 and that's correct.
But the second continuation byte does not start with 10, so it is invalid.

给定一个数组,问这个数组是否能表示正确的UTF8字符。UTF8格式在题目中有详细的说明,字节数为1-4个字节,1字节的UTF8第一个bit为0,n字节的UTF8,前n-bits为1,后面跟一个0bit,后面n-1字节前两个bit为10。 解法为我们依次取出字节的前1,3,4,5bits,看是否是1-4字节的UTF8,检查完第一个字节后,根据字节数检查后面的n-1字节。 注意UTF8字节数只可能是1-4,如果发现第一个字节的前5个及以上的bit都是1,直接返回false。代码如下: [cpp] class Solution { public: bool validUtf8(vector<int>& data) { vector<int> mask1 = { 0x80,0xe0,0xf0,0xf8 }; vector<int> first = { 0x0,0xc0,0xe0,0xf0 }; int mask2 = 0xc0, second = 0x80; int i = 0, j = 0; while (i < data.size()) { for (j = 0; j < 4; ++j) { if ((data[i] & mask1[j]) == first[j]) { while (j–) { if (++i >= data.size())return false; if ((data[i] & mask2) != second)return false; } break; } } if (j >= 4)return false; ++i; } return true; } }; [/cpp] 注意位运算的优先级小于判等运算,所以一定记得加括号,要不然WA。。。 本代码提交AC,用时16MS。]]>

LeetCode Binary Tree Right Side View

199. Binary Tree Right Side View

Given a binary tree, imagine yourself standing on the right side of it, return the values of the nodes you can see ordered from top to bottom.

Example:

Input: [1,2,3,null,5,null,4]
Output: [1, 3, 4]
Explanation:

   1            <---
 /   \
2     3         <---
 \     \
  5     4       <---

给定一棵二叉树,问从树的右边往左看,从上往下,看到的数组是什么。很有意思哈,一棵树变着花样出题。
想到的话,其实很简单,从右边看到的数是每一层最右边的数(好像是废话),所以我们可以对树层次遍历,取出每层最右边的数,构成的数组就是答案。完整代码如下:

class Solution {
public:
    vector<int> rightSideView(TreeNode* root)
    {
        vector<int> ans;
        if (root == NULL)
            return ans;
        queue<TreeNode*> q;
        q.push(root);
        while (!q.empty()) {
            ans.push_back(q.back()->val);
            int n = q.size();
            for (int i = 0; i < n; ++i) {
                TreeNode* tmp = q.front();
                q.pop();
                if (tmp->left)
                    q.push(tmp->left);
                if (tmp->right)
                    q.push(tmp->right);
            }
        }
        return ans;
    }
};

本代码提交AC,用时3MS。

LeetCode Populating Next Right Pointers in Each Node II

117. Populating Next Right Pointers in Each Node II

Given a binary tree

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Follow up:

  • You may only use constant extra space.
  • Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem.

Example 1:

Input: root = [1,2,3,4,5,null,7]
Output: [1,#,2,3,#,4,5,7,#]
Explanation: Given the above binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Constraints:

  • The number of nodes in the given tree is less than 6000.
  • -100 <= node.val <= 100

本题在LeetCode Populating Next Right Pointers in Each Node的基础上,扩展了二叉树的形式,并不要求二叉树一定是满二叉树(题中的完全二叉树),而是一个一般的二叉树。 这个时候就会遇到一些问题,比如下面的二叉树。

         1
       /  \
      2    3
     / \    \
    4   5    7
   /          \
  8            9

如果还按原来的先左孩子后右孩子的DFS,则第一次深度遍历完之后是这样的:

         1
       /  \
      2 -> 3
     / \    \
    4 ->5    7
   /          \
  8            9

此时要找8的next时就比较麻烦,因为在上一层到5时断了,没有5->7,所以找不到9号节点。所以需要修改为先对右孩子遍历,再对左孩子遍历,这样父亲一层的next就都完备了。 另外代码中还统一了child是左孩子和右孩子的代码,都是在父亲一层不断找next,直到找到合法next或者NULL。不过针对右孩子时,需要注意,为了不让其next指向左兄弟,增加了tmp != parent的约束。 完整代码如下:

class Solution {
public:
    void dfs(TreeLinkNode* child, TreeLinkNode* parent)
    {
        if (child == NULL)
            return;
        if (parent) {
            TreeLinkNode* tmp = parent;
            while (tmp) {
                if (tmp != parent && tmp->left && child != tmp->left) {
                    child->next = tmp->left;
                    break;
                }
                if (tmp->right && child != tmp->right) {
                    child->next = tmp->right;
                    break;
                }
                tmp = tmp->next;
            }
        }
        dfs(child->right, child);
        dfs(child->left, child);
    }
    void connect(TreeLinkNode* root) { dfs(root, NULL); }
};

本代码提交AC,用时32MS。

二刷。简单易懂但是比较啰嗦的代码:

class Solution {
public:
	void point2right(Node* par, Node* cur) {
		if (cur == NULL)return;

		if (par != NULL) {
			if (cur == par->left) {
				if (par->right != NULL) {
					cur->next = par->right;
				}
				else {
					Node* tmp = par->next;
					while (tmp != NULL) {
						if (tmp->left != NULL) {
							cur->next = tmp->left;
							break;
						}
						else if (tmp->right != NULL) {
							cur->next = tmp->right;
							break;
						}
						tmp = tmp->next;
					}
				}
			}
			else {
				// 和上面一段是一样的
				Node* tmp = par->next;
				while (tmp != NULL) {
					if (tmp->left != NULL) {
						cur->next = tmp->left;
						break;
					}
					else if (tmp->right != NULL) {
						cur->next = tmp->right;
						break;
					}
					tmp = tmp->next;
				}
			}
		}
		point2right(cur, cur->right);
		point2right(cur, cur->left);
	}
	Node* connect(Node* root) {
		if (root == NULL || (root->left == NULL && root->right == NULL))return root;
		point2right(NULL, root);
		return root;
	}
};

这一题的关键是要先递归右子树,再递归左子树。本代码提交AC,用时16MS。

LeetCode Populating Next Right Pointers in Each Node

116. Populating Next Right Pointers in Each Node

You are given a perfect binary tree where all leaves are on the same level, and every parent has two children. The binary tree has the following definition:

struct Node {
  int val;
  Node *left;
  Node *right;
  Node *next;
}

Populate each next pointer to point to its next right node. If there is no next right node, the next pointer should be set to NULL.

Initially, all next pointers are set to NULL.

Follow up:

  • You may only use constant extra space.
  • Recursive approach is fine, you may assume implicit stack space does not count as extra space for this problem.

Example 1:

Input: root = [1,2,3,4,5,6,7]
Output: [1,#,2,3,#,4,5,6,7,#]
Explanation: Given the above perfect binary tree (Figure A), your function should populate each next pointer to point to its next right node, just like in Figure B. The serialized output is in level order as connected by the next pointers, with '#' signifying the end of each level.

Constraints:

  • The number of nodes in the given tree is less than 4096.
  • -1000 <= node.val <= 1000

本题要给二叉树的每个节点添加next指针,指向它的右兄弟,如果没有右兄弟,则为NULL。 本题使用层次遍历可以很容易解决,但是需要使用额外的空间,不符合题目要求。 根据题目中的示意图,很明显如果节点是父亲的左孩子,则其next指向父亲的右孩子;但是如果节点是父亲的右孩子,则next指向需要跨界,不太好办,经题解提示,这种情况下,next指向父亲的next的左孩子,真是巧妙呀。所以可以用DFS完成本题,代码如下:

class Solution {
public:
    void dfs(TreeLinkNode* child, TreeLinkNode* parent)
    {
        if (child == NULL)
            return;
        if (parent) {
            if (child == parent->left)
                child->next = parent->right;
            else if (parent->next)
                child->next = parent->next->left;
        }
        dfs(child->left, child);
        dfs(child->right, child);
    }
    void connect(TreeLinkNode* root) { dfs(root, NULL); }
};

本代码提交AC,用时26MS。

LeetCode Reverse Words in a String

151. Reverse Words in a String

Given an input string, reverse the string word by word.

Example 1:

Input: "the sky is blue"
Output: "blue is sky the"

Example 2:

Input: "  hello world!  "
Output: "world! hello"
Explanation: Your reversed string should not contain leading or trailing spaces.

Example 3:

Input: "a good   example"
Output: "example good a"
Explanation: You need to reduce multiple spaces between two words to a single space in the reversed string.

Note:

  • A word is defined as a sequence of non-space characters.
  • Input string may contain leading or trailing spaces. However, your reversed string should not contain leading or trailing spaces.
  • You need to reduce multiple spaces between two words to a single space in the reversed string.

Follow up:

For C programmers, try to solve it in-place in O(1) extra space.


对一个字符串,以单词为单位进行逆序。注意字符串中可能会有多个连续的空格,还可能在首尾有空格。 如果允许使用额外的空间,那就好办,先把字符串分词,然后逆序拼接。代码如下:

class Solution {
public:
    void reverseWords(string& s)
    {
        string ans = "";
        int start = 0, end = 0, n = s.size();
        while (true) {
            while (start < n && s[start] == ‘ ‘)
                ++start;
            if (start >= n)
                break;
            end = start + 1;
            while (end < n && s[end] != ‘ ‘)
                ++end;
            if (end >= n)
                break;
            ans = s.substr(start, end – start) + " " + ans;
            start = end + 1;
        }
        if (end > start)
            ans = s.substr(start, end – start) + " " + ans;
        s = ans.substr(0, ans.size() – 1);
    }
};

本代码提交AC,用时9MS。

如果不借助额外空间,则只能在原字符串上进行逆序了,有意思。我们可以进行两次翻转,第一次对整个字符串翻转,然后遍历新字符串,对每个单词进行翻转。比如原字符串是”the sky is blue”,第一次翻转之后就是”eulb si yks eht”,再依次对每个单词翻转,就变成了”blue is sky the”。
我们知道对一个字符串进行翻转可以使用首尾指针的方法in-place实现,代码中为了可读性,直接调用了STL的reverse函数。

class Solution {
public:
    void reverseWords(string& s)
    {
        reverse(s.begin(), s.end()); 
        //i,j为新字符串每个单词的首尾位置,u,v为旧字符串每个单词的首尾位置
        int i = 0, j = 0, u = 0, v = 0, n = s.size();
        while (true) {
            while (u < n && s[u] == ‘ ‘)
                ++u;
            if (u >= n)
                break;
            v = u;
            while (v < n && s[v] != ‘ ‘)
                s[j++] = s[v++];
            reverse(s.begin() + i, s.begin() + j);
            if (v >= n)
                break;
            s[j++] = ‘ ‘;
            i = j;
            u = v;
        }
        if (j == 0)
            s = "";
        else if (s[j – 1] == ‘ ‘)
            s.resize(j – 1);
        else
            s.resize(j);
    }
};

本代码提交AC,用时6MS。虽然第二种方法更快,也更省空间,但是有很多边界条件很容易出错,我还是觉得第一种方法安全。
参考:http://www.cnblogs.com/grandyang/p/4606676.html

LeetCode Reverse Vowels of a String

LeetCode Reverse Vowels of a String Write a function that takes a string as input and reverse only the vowels of a string. Example 1: Given s = “hello”, return “holle”. Example 2: Given s = “leetcode”, return “leotcede”. Note: The vowels does not include the letter “y”.


把字符串中的所有元音字母逆序。简单题,使用首尾两个指针i,j,找到元音后交换,直到i>j。 完整代码如下: [cpp] class Solution { public: string reverseVowels(string s) { unordered_set<char> vowels = { ‘a’,’e’,’i’,’o’,’u’,’A’,’E’,’I’,’O’,’U’ }; int i = 0, j = s.size() – 1; while (i < j) { while (i < j&&vowels.find(s[i]) == vowels.end())++i; if (i >= j)break; while (i < j&&vowels.find(s[j]) == vowels.end())–j; if (i >= j)break; swap(s[i++], s[j–]); } return s; } }; [/cpp] 本代码提交AC,用时52MS。]]>