本文共 2048 字，大约阅读时间需要 6 分钟。
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. 解题思路 从右上角开始查找。矩阵中的一个数，它左边的数都比它小，下边的数都比它大。因此，从右上角开始查找，就可以根据 target 和当前元素的大小关系来缩小查找区间。复杂度：O(M + N) + O(1)
class Solution {public: bool Find(int target, vector > array) { if(array.size()==0||array[0].size()==0){ return false; } int rows = array.size(); int cols = array[0].size(); int r = 0;int c = cols-1; while(r =0){ int temp = array[r][c]; if(target==temp) return true; else if(target 2.替换空格
题目描述 将一个字符串中的空格替换成 “%20”。Input:
“We Are Happy”Output:
“We%20Are%20Happy” 解题思路 在字符串尾部填充任意字符，使得字符串的长度等于替换之后的长度。因为一个空格要替换成三个字符（%20），因此当遍历到一个空格时，需要在尾部填充两个任意字符。令 P1 指向字符串原来的末尾位置，P2 指向字符串现在的末尾位置。P1 和 P2 从后向前遍历，当 P1 遍历到一个空格时，就需要令 P2 指向的位置依次填充 02%（注意是逆序的），否则就填充上 P1 指向字符的值。
从后向前遍是为了在改变 P2 所指向的内容时，不会影响到 P1 遍历原来字符串的内容。
class Solution {public: void replaceSpace(char *str,int length) { int p1 = length-1; int j = 0,count = 0; for(int i = 0;i =0&&p2>p1){ if(str[p1]==' '){ str[p2--]='0'; str[p2--]='2'; str[p2--]='%'; } else{ str[p2--]=str[p1]; } p1--; } }}; 3.从尾到头打印链表
题目描述 输入链表的第一个节点，从尾到头反过来打印出每个结点的值。 解题思路 使用栈/*** struct ListNode {* int val;* struct ListNode *next;* ListNode(int x) :* val(x), next(NULL) {* }* };*/class Solution {public: vector printListFromTailToHead(ListNode* head) { stack arr; vector listRe; ListNode *p = head; while(p!=NULL){ arr.push(p->val); p = p->next; } int len = arr.size(); for(int i = 0;i 转载地址：http://akhci.baihongyu.com/