PZHU_CG_CSDN的博客

题目描述：　　在一个二维数组中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。思路：既然每一行是有序的，那么就遍历行(key 大于数组第一位小于最后一位，那么说明 key 可能在当前这一行中)，然后在当前行中二分查找 key，跑完整个过程如果没找到就证明不存在 k...

题目描述：HZ偶尔会拿些专业问题来忽悠那些非计算机专业的同学。今天测试组开完会后,他又发话了:在古老的一维模式识别中,常常需要计算连续子向量的最大和,当向量全为正数的时候,问题很好解决。但是,如果向量中包含负数,是否应该包含某个负数,并期望旁边的正数会弥补它呢？例如:{6,-3,-2,7,-15,1,2,2},连续子向量的最大和为8(从第0个开始,到第3个为止)。给一个数组，返回它的最大连续子序...

题目描述：数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。例如输入一个长度为9的数组{1,2,3,2,2,2,5,4,2}。由于数字2在数组中出现了5次，超过数组长度的一半，因此输出2。如果不存在则输出0。时间限制：1秒空间限制：32768K思路一：遍历整个数组记录当前元素出现的次数，并保存最大值，这样遍历一次数组在 O(n) 的复杂度下就可以得到答案。思路二：用 map ...

题目描述：      输入一个字符串,按字典序打印出该字符串中字符的所有排列。例如输入字符串abc,则打印出由字符a,b,c所能排列出来的所有字符串abc,acb,bac,bca,cab和cba。输入描述：输入一个字符串,长度不超过9(可能有字符重复),字符只包括大小写字母。时间限制：1秒空间限制：32768K思路一：在 C/C...

题目描述：     输入n个整数，找出其中最小的K个数。例如输入4,5,1,6,2,7,3,8这8个数字，则最小的4个数字是1,2,3,4。时间限制：1秒空间限制：32768K思路一：先进行排序，使序列有序，再取出对应的 K 位，时间复杂度O（nlogn）。思路二：TOP K 系列问题是数据结构堆的经典应用，堆是一种完全二叉树，最大堆：堆...

题目描述：　　输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历的结果。如果是则输出Yes,否则输出No。假设输入的数组的任意两个数字都互不相同。时间限制：1秒 空间限制：32768K思路： 根据题意，如果已知二叉搜索树的后序序列，那么其序列中最后一个元素必然是根节点 root ，从序列的头部开始以第一个比 root 大的节点分割，那么前面一部分就是 root 的左子树，后面...

题目描述：　　输入一个矩阵，按照从外向里以顺时针的顺序依次打印出每一个数字，例如，如果输入如下4 X 4矩阵： 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 则依次打印出数字1,2,3,4,8,12,16,15,14,13,9,5,6,7,11,10.时间限制：1秒 空间限制：32768K思路： 模拟整个过程，顺时针打印矩阵的顺序：先从左到右，再从上...

题目描述：　　输入一个复杂链表（每个节点中有节点值，以及两个指针，一个指向下一个节点，另一个特殊指针指向任意一个节点），返回结果为复制后复杂链表的head。（注意，输出结果中请不要返回参数中的节点引用，否则判题程序会直接返回空）时间限制：1秒 空间限制：32768K思路： 题目要求不能使用到原始链表节点的引用，那么，我们就必须得生成新的链表，将数据 copy 过来就好了，时间复杂度...

题目描述：　　输入两个单调递增的链表，输出两个链表合成后的链表，当然我们需要合成后的链表满足单调不减规则。时间限制：1秒 空间限制：32768K思路：分别去遍历两条链表，如果当前链表 p1 当前位置数据小于 p2 当前位置数据，那么就把 p1 当前位置的数据放到新的链表 p3 后面，让 p1 指向下一个地址，再次比较，哪一个小，就将其数据值保存到新链表 p3 中，然后指向下一个位置...

题目描述：定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1））。时间限制：1秒 空间限制：32768K思路：利用一个辅助栈来存放最小值，栈顶存放的就是当前数据栈中最小值。 　　 具体操作： 1、在向数据栈中 push 数据时，如果当前元素小于辅助栈栈顶元素，就将当前元素一并加到辅助栈中。 2、如果当前元素大于等于辅助栈栈顶元素...

题目描述：输入两个整数序列，第一个序列表示栈的压入顺序，请判断第二个序列是否可能为该栈的弹出顺序。假设压入栈的所有数字均不相等。例如序列1,2,3,4,5是某栈的压入顺序，序列4,5,3,2,1是该压栈序列对应的一个弹出序列，但4,3,5,1,2就不可能是该压栈序列的弹出序列。（注意：这两个序列的长度是相等的）时间限制：1秒 空间限制：32768K　　很经典的题型了，给出压入顺序，...

题目描述：输入一个链表，输出该链表中倒数第k个结点。时间限制：1秒 空间限制：32768K方法一：先求出链表总的节点个数 n，倒数第 k 个就是顺数第 n-k+1 个public class FindKthToTail { public ListNode FindKthToTail(ListNode head, int k) { ListNode tem...

题目描述：输入一个链表，反转链表后，输出新链表的表头。时间限制：1秒 空间限制：32768K方法一：先把所有节点全部取出来，再来重构链表。import java.util.ArrayList;import java.util.List;public class ReverseList { public ListNode ReverseList(ListNode...

题目描述输入一个链表，按链表值从尾到头的顺序返回一个ArrayList。思路： 　　先把链表里元素取出到 vector 容器，再将容器进行翻转。代码：vector<int> printListFromTailToHead(ListNode* head) { vector<int> a; while(head != NUL...

题目描述请实现一个函数，将一个字符串中的每个空格替换成“%20”。例如，当字符串为We Are Happy.则经过替换之后的字符串为We%20Are%20Happy。思路： 　　重新开辟一个新的字符数组，将旧数组的值以此拷贝过来，如果拷贝过程中遇到空格字符，就进行转换，最后将新数组赋值给旧数组。代码：void replaceSpace(char *str,int length...

题目描述：求出1-13的整数中1出现的次数,并算出100-1300的整数中1出现的次数？为此他特别数了一下1~13中包含1的数字有1、10、11、12、13因此共出现6次,但是对于后面问题他就没辙了。ACMer希望你们帮帮他,并把问题更加普遍化,可以很快的求出任意非负整数区间中1出现的次数（从1 到 n 中1出现的次数）。时间限制：1秒空间限制：32768K思路：题目要求求出1-n之间出现...