题目描述小明很喜欢数学,有一天他在做数学作业时,要求计算出9~16的和,他马上就写出了正确答案是100。但是他并不满足于此,他在想究竟有多少种连续的正数序列的和为100(至少包括两个数)。没多久,他就得到另一组连续正数和为100的序列:18,19,20,21,22。现在把问题交给你,你能不能也很快的找出所有和为S的连续正数序列? Good Luck! 【题解】 利用一个sum数组，计算从1到i的和，然后计算sum[i]-sum[j]是否是target class Solution { public: vector<vector<int>> ans; vo...

题目描述输入一棵二叉搜索树，将该二叉搜索树转换成一个排序的双向链表。要求不能创建任何新的结点，只能调整树中结点指针的指向。 【题解】：先用一个vector存储中序遍历的结果，然后再根据vector重建双向链表 /* struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; TreeNode(int x) : val(x), left(NULL), right(NULL) { } };*/ class Solution { public: ...

题目描述牛客最近来了一个新员工Fish，每天早晨总是会拿着一本英文杂志，写些句子在本子上。同事Cat对Fish写的内容颇感兴趣，有一天他向Fish借来翻看，但却读不懂它的意思。例如，“student. a am I”。后来才意识到，这家伙原来把句子单词的顺序翻转了，正确的句子应该是“I am a student.”。Cat对一一的翻转这些单词顺序可不在行，你能帮助他么？ 题解：【直接从后往前遍历一遍，遇到空格就放单词】 class Solution { public: string ReverseSentence(string str) { string ans="";...

题目描述 给你一根长度为n的绳子，请把绳子剪成整数长的m段（m、n都是整数，n>1并且m>1），每段绳子的长度记为k[0],k[1],...,k[m]。请问k[0]xk[1]x...xk[m]可能的最大乘积是多少？例如，当绳子的长度是8时，我们把它剪成长度分别为2、3、3的三段，此时得到的最大乘积是18。 输入描述: 输入一个数n，意义见题面。（2 <= n <= 60） 【贪心】 只要想到状态转移方程，这题就解了， dp[i] = max ( dp[i-j]*(j), dp[i-j]*dp[j], (i-j)*dp[j...

题目描述地上有一个m行和n列的方格。一个机器人从坐标0,0的格子开始移动，每一次只能向左，右，上，下四个方向移动一格，但是不能进入行坐标和列坐标的数位之和大于k的格子。 例如，当k为18时，机器人能够进入方格（35,37），因为3+5+3+7 = 18。但是，它不能进入方格（35,38），因为3+5+3+8 = 19。请问该机器人能够达到多少个格子？ 【DFS】经典dfs： 先把不能走的格子标记为true class Solution { public: int n,m,k; bool f[1000][1000]; int ans=0; int dir[4][2...

【回溯法】 与力扣79题同理 class Solution { public: int dir[4][2]={{0,1},{0,-1},{1,0},{-1,0}}; int n,m; int len; bool f[10100]; bool dfs(char* matrix, int x, int y, char* str, int l) { if(x<0||x>n-1||y<0||y>m-1||f[x*m+y]||matrix[x*m+y]!=str[l]) return false; i...