这个题是http://blog.sina.com.cn/s/blog_672f71fc0101os5r.html
该题目的变形,只是把数组换成了单链表,在单链表查找的时候注意优化,每次二分之后head节点对于left来说依然是head,但是对right来说head节点要更新为mid的那个节点。不然会超时。
class Solution {
public:
ListNode * GetListNthNode(ListNode * h……
模拟题,迭代直到n即可。
class Solution {
public:
string SayStep(string str) {
string strstep = "";
int index = 0;
while(index < str.length()) {
char c = str[index];
int count_c = 1;
int i;
for(i =……
从前往后一个一个标记会超时,后来想了下 某些情况下复杂度是o(n^2)
但是从后往前标记,不一样,近似于o(n)
class Solution {
public:
void FindMin(int A[],int n,bool flag[]) {
if(n <= 0)return;
int min = 0xffff;
for(int i = n-1;i >= 0;i--) {
if(A[i] + i >=……
二分查找的变形,有序数组,允许重复数字,要求查找目标的区间,如果不存在目标,输出[-1,-1]。
class Solution {
public:
void bSearch(int A[],int left,int right,int target,int flag,int &val) {
if(left > right)return ;
int mid = (left + right) / 2;
if(A[mid] == target)……
http://blog.sina.com.cn/s/blog_672f71fc0101phtr.html 该题的变形。
允许重复数字,但是求得的子集中要去除重复子集。
开始超时,后来稍微优化了下,需要检验目前找到的子集中是否有当前需要插入的子集,从后往前,发现size不一样就可以停下了。
当然想的如果还超时就用map
int cmp(int a,int b) {
return a < ……
Unique Paths
http://blog.sina.com.cn/s/blog_672f71fc0101pf1c.html 的变形。加入障碍物,判断一下即可。
struct PPoint
{
int x;
int y;
};
class Solution {
public:
bool CheckIn(int x,int y,PPoint *p,int top)
{
for(int i = 0;i < top;i++)
{
if(x == p[i]……
给定一些字符串,求这些字符串的最长公共前缀。
一个一个比就行。
class Solution {
public:
bool EqualAll(vector<string>&strs,int k) {
for(int i = 1;i < strs.size();i++) {
if(strs[i][k] != strs[0][k])return false;
}
return true;
}
string lon……
给一个二叉树root和一个target值,求所有从根开始到叶节点的路径和等于target的路径。
class Solution {
public:
void MoveOnPath(TreeNode *node,int sum,int &val,vector<int>&item,vector<vector<int>>&ans) {
if(node == NULL)retur……
给定一个数组,比如{1,2,3,4} 求出 该集合的所有子集。
其中WA一次,因为要求升序排列。
搜索即可。
int cmp(int a,int b) {
return a < b;
}
class Solution {
public:
void AddItemStep(int i,int k,vector<int>&S,vector<vector<int>>&ans,vector<int>&item) {
……
输入一个字符串s,s由空格和字母构成,求最后一个单词的长度。单词定义为仅有字母构成。
class Solution {
public:
int lengthOfLastWord(const char *s) {
int length = strlen(s);
int index = length - 1;
while(s[index] == ' ')index--;
int ans = 0;
for(int i = ind……