3.数组中重复的数字
一个长度为n的数组，它的所有数字都在0~n-1之中，寻找数组中重复的数字。
算法一
题目说明
输入：长度为n的数组中所有数字在0~n-1之内
思路：如果数组中没有重复的数字，那么元素i将会在下标为i的位置中，对于数组中的每一个元素m，比较该元素与它的下标，如果相等，则继续遍历下一个元素；如果不相等，比较m与nums[m]，如果两者相等，则说明m重复，返回m，否则交换m与nums[m]，然后继续遍历下一个元素。
缺点：这个算法修改了数组本身。
算法如下：1
2
3
4
5
6
7
8
9
10
11
12
13从头到尾扫描整个数组numbers，下标为i：
if numbers[i] < 0 or numbers[i] > length - 1:
return -1;
//要一直在循环中寻找
if(numbers[i] != i):
m = array[i];
if m == array[m]:
//找到重复数字
return m;
else:
swap(m,array[m]);
//第一层循环结束，没有找到重复的数字
return -1;
leetcode面试题03.数组中重复的数字
1 | class Solution { |
算法二
输入：长度为n+1的数组所有数字都在1~n之间。
不修改数组numbers本身，使用二分查找
数组：1
2
3
4
5
6
7
8
9
10
11
12
13
14start = 1;
end = length - 1;
while(start <= end){
mid = (start + end) / 2;
统计numbers中元素值在start和mid之间的元素个数为count
if(start == end) //最后只剩一个数字了,如果书中中有重复的数字，那就是这个数字了
if(count > 1)
return start;
else
return -1;
if count > mid: //说明重复数字的范围在start~mid之间
end = mid;
else: //说明数字在mid+1 ~ end之间
start = mid + 1;
4.二维数组中的查找
题目说明
在一个二维数组中，每一行和每一列的数字都是升序排列，判断给定数字是否在这个二维数组中。
输入：二维数组matrix，行rows，列columns，数字number。
思路：充分利用每行每列都是升序排列，每次比较右上角的数字target与目标数字number是否相等，如果target==number，则返回true；如果右上角的数字比目标数字大，则说明该数字不会在target所在的那一列中，剔除这一列；如果target<number，则说明该数字不会在target所在的那一行中，剔除这一行。1
2
3
4
5
6
7
8
9
10
11
12
13
14row = 0;
column = columns - 1;
while(row < rows && column >= 0)
target = matrix[row][column];
if target == number:
return true;
else if target < number:
//剔除column这一列
column--;
else：
//剔除row这一行
row++;
//执行完while循环仍然没有找到
return false;
leetcode面试题04. 二维数组中的查找
1 | class Solution { |
5.替换空格
题目说明
将字符串中的空格替换为“%20”
输入：str，length
计算替换后的新长度，设置两个指针，new_idx和old_idx，new_idx指向新长度的末尾，old_idx指向旧长度的末尾，从尾到投开始替换。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15统计字符串中空格的数目为space_num
newlength = length - 1 + space_num * 2
if newlength < length：
return
int new_idx = newlength - 1;
int old_idx = length - 1;
while(old_idx >= 0): //从末尾开始遍历字符串
if 遇到的字符不是空格：
str[new_idx--] = str[old_idx--];
else:
str[new_idx--] = '0';
str[new_idx--] = '2';
str[new_idx--] = '%';
old_idx--;
return;
leetcode面试题05. 替换空格
使用c++可以不用那么麻烦，因为string可以连接：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
string replaceSpace(string s) {
if(s.length() == 0)
return s;
string res;
for(int i=0;i<s.length();i++){
if(s[i] == ' '){
res += "%20";
}
else
res += s[i];
}
return res;
}
};
链表末尾添加节点
1 | void AddToTail(ListNode** pHead,int value){ |
链表中删除节点
删除链表中的指定节点value.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28void RemoveNode(ListNode** pHead,int value){
//先判断头结点为空，再判断链表第一个节点为空
if(pHead == nullptr || *pHead == nullptr)
return;
ListNode *pToDeleted = nullptr;
//被删除节点是头结点
if((*pHead)->m_Value == value){
pToDeleted = *pHead;
*pHead = (*pHead)->m_Next;
}
else{
ListNode* pNode = *pHead;
//跳过不是value的节点
while(pNode->m_Next != nullptr && pNode->m_Next->m_Value != value){
pNode = pNode->m_Next;
}
//遍历结束 or 找到是value的节点
if(pNode->m_Next != nullptr && pNode->m_Next->m_Value == value){
pToDeleted = pNode->m_Next;
pNode->m_Next = pNode->m_Next->m_Next;
}
}
if(pToDeleted != nullptr){
delete pToDeleted;
pToDeleted = nullptr;
}
return;
}
6.逆序打印链表
算法一
从头到尾遍历链表，将链表压入栈中，然后依次弹出栈中链表的数值。1
2
3建立一个栈；
遍历链表，将value压入栈中；
将栈中的值弹出top();然后pop();
算法二（递归）
1 | PrintListReversingly_Recursively: |
7.重建二叉树
算法说明
根据前序遍历和中序遍历的结果，重建二叉树。
前序遍历：先根节点，然后左子节点，再右子节点
中序遍历：先左子节点，然后根节点，再右子节点
后序遍历：先左子节点，然后右子节点，再根节点
思路如下：1
2
3
4前序遍历的第一个节点是根节点，找到根节点
在中序遍历中找到根节点，将中序遍历的序列划分为左子树和右子树
在前序遍历中找到左子树的位置，重建左子树；
在前序遍历中找到右子树的位置，重建右子树。
leetcode 105
1 | /** |
8.二叉树的下一个节点
给定二叉树和其中一个节点，找出中序遍历（先左子节点，再根节点，最后左子节点）序列的下一个节点。思路如下：1
2如果该节点有右子树，一直找到右子树的左子节点；
如果该节点没有右子树，沿着父节点向上遍历，寻找父节点是左子树的节点，下一个节点是这个节点的父节点。
注意循环中的判断方法：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23BinaryTreeNode* GetNext(BinaryTreeNode* pNode)
{
if(pNode == nullptr)
return nullptr;
BinaryTreeNode *pNext = nullptr;
if(pNode ->m_pRight != nullptr){ //右子树不为空，找到左子节点
BinaryTreeNode* pRight = pNode->m_pRight;
while(pRight->m_pLeft != nullptr){ //判断条件是左子树不为空
pRight = pRight->m_pLeft; //循环遍历左子树
}
pNext = pRight; //遍历到左叶子节点，跳出循环，即目标节点
}
else{ //右子树为空，沿着父节点向上遍历，找到一个节点，该节点是左子树，下一个节点就是它的父节点
BinaryTreeNode* pParent = pNode->m_pParent; //记录父节点
BinaryTreeNode* pCurrent = pNode; //记录当前节点
while(pParent != nullptr && pCurrent == pParent->m_pRight){//判断条件是节点是右子树
pCurrent = pParent;
pParent = pParent->m_pParent;
}
pNext = pParent; //找到一个父节点的左子树，下一个节点就是这个节点的父节点
}
return pNext;
}
9.栈与队列
栈：先进后出
队列：先进先出
用两个栈实现队列
思路如下：1
2
3
4
5初始化两个栈stack1和stack2
push：数据压入stack1
pop:如果stack2不为空，则弹出stack2的栈顶元素；否则将stack1的元素压入stack2，弹出stack2的栈顶元素
peek(返回队列首部元素)：如果stack2不为空，则返回stack2的栈顶元素；否则将stack1的元素压入stack2，返回stack2的栈顶元素
empty()：如果stack1和stack2均为空，则返回true；否则返回false
leetcode 232题解如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70class MyQueue {
public:
/** Initialize your data structure here. */
stack<int> stack1;
stack<int> stack2;
MyQueue() {
}
/** Push element x to the back of queue. */
void push(int x) {
stack1.push(x);
}
/** Removes the element from in front of queue and returns that element. */
int pop() {
int res;
if(!stack2.empty()){
res = stack2.top();
stack2.pop();
return res;
}
while(!stack1.empty()){
int data = stack1.top();
stack1.pop();
stack2.push(data);
}
res = stack2.top();
stack2.pop();
return res;
}
/** Get the front element. */
int peek() {
int res;
if(!stack2.empty()){
res = stack2.top();
return res;
}
while(!stack1.empty()){
int data = stack1.top();
stack1.pop();
stack2.push(data);
}
res = stack2.top();
return res;
}
/** Returns whether the queue is empty. */
bool empty() {
if(stack1.empty() && stack2.empty())
return true;
else
return false;
}
};
/**
* Your MyQueue object will be instantiated and called as such:
* MyQueue* obj = new MyQueue();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->peek();
* bool param_4 = obj->empty();
*/
用两个队列实现栈
思路如下：1
2
3
4push():将元素压入queue1
pop():将queue1的前n-1个元素加入到queue2中，把queue1的最后一个元素弹出,再把queue2的元素转移到queue1中
top():将queue1的前n个元素加入到queue2中，把最后一个数返回，再把queue2的元素转移到queue1中。
empty():queue1不为空且queue2不为空
leetcode 225题解如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70class MyStack {
public:
/** Initialize your data structure here. */
queue<int> q1;
queue<int> q2;
MyStack() {
}
/** Push element x onto stack. */
void push(int x) {
q1.push(x);
}
/** Removes the element on top of the stack and returns that element. */
int pop() {
int data,res;
if(!q1.empty() && q2.empty()){
while(q1.size()>1){
data = q1.front();
q1.pop();
q2.push(data);
}
res = q1.front();
q1.pop();
while(!q2.empty()){
data = q2.front();
q2.pop();
q1.push(data);
}
}
return res;
}
/** Get the top element. */
int top() {
int data,res;
if(!q1.empty() && q2.empty()){
while(!q1.empty()){
data = q1.front();
q1.pop();
q2.push(data);
}
res = data;
while(!q2.empty()){
data = q2.front();
q2.pop();
q1.push(data);
}
}
return res;
}
/** Returns whether the stack is empty. */
bool empty() {
if(q1.empty() && q2.empty())
return true;
else
return false;
}
};
/**
* Your MyStack object will be instantiated and called as such:
* MyStack* obj = new MyStack();
* obj->push(x);
* int param_2 = obj->pop();
* int param_3 = obj->top();
* bool param_4 = obj->empty();
*/
10.斐波那契数列
f(n) = f(n-1) + f(n-2)
解法一(递归)
1 | class Solution { |
解法二(动态规划)
注意变量类型是long long int，每次结果都要取模。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
int fib(int n) {
long long fib1 = 1;
long long fib2 = 0;
long long fibn = 0;
if(n <= 0)
return fib2;
if(n == 1)
return fib1;
for(int i=2;i<=n;i++){
fibn = (fib1 + fib2) % 1000000007;
fib2 = fib1;
fib1 = fibn;
}
return fibn;
}
};
11.旋转数组的最小数字
12.矩阵中的路径
给定一个矩阵和字符串，判断矩阵中是否包含一条该字符串所有字符的路径。
思路如下：1
2
3
4
5
6visited数组记录矩阵中的字符是否走过
pathlength记录走过的路径长度，如果str[pathlength] = '\0'，说明已经走完整个字符串，return true.
按行优先遍历数组中的每个元素，如果元素等于str[pathlength++]，对于每个元素进行上下左右的判断：
如果下一个字符等于str[pathlength]，则pathlength++，return true;
如果四个方向的字符均不等于str[pathlength],则return false.
leetcode题解
1 | class Solution { |
13.机器人的运动范围
给定一个m行n列的二维数组，机器人从(0,0)开始移动，可以上下左右移动，但是不能进入格子的数位相加大于k的格子，判断机器人可以到达多少个格子。
思路如下：1
2
3
4
5使用visited来记录是否走过这个格子，避免重复记录
如果当前格子小于k：
visited[row*cols+col] = 1;
count = 1 + 上 + 下 + 左 + 右; //递归
return count;
leetcode题解如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44class Solution {
public:
int movingCount(int m, int n, int k) {
if(k < 0 || m <= 0 || n <= 0)
return 0;
bool* visited = new bool[m*n];
memset(visited,0,m*n);
int count = movingCountCore(m,0,n,0,k,visited);
return count;
}
int movingCountCore(int rows,int row, int cols, int col, int k, bool* visited){
if(row < 0 || row >= rows || col < 0 || col >= cols || visited[row*cols+col])
return 0;
int count = 0;
if(checkNum(rows,row,cols,col,k,visited)){
visited[row*cols+col] = 1;
count = 1 + movingCountCore(rows,row-1,cols,col,k,visited)
+ movingCountCore(rows,row+1,cols,col,k,visited)
+ movingCountCore(rows,row,cols,col-1,k,visited)
+ movingCountCore(rows,row,cols,col+1,k,visited);
}
return count;
}
bool checkNum(int rows, int row, int cols, int col, int k, bool* visited){
if(row >= rows || row < 0 || col >= cols || col < 0 || visited[row*cols+col])
return false;
if(getDigitSum(row)+getDigitSum(col) <= k)
return true;
return false;
}
int getDigitSum(int num){
int res = 0;
while(num){
res += num % 10;
num = num / 10;
}
return res;
}
};
14.剪绳子
给定一根长度为n的绳子，将其剪成m段，求k[0]*k[1]*k[2]*…k[m]的乘积最大值
解法1（动态规划）
f(n)记作长度为n的绳子剪断后的乘积最大值，则f(n) = max(f(i) * f(n-i))。1
2
3
4f(0) = f(1) = 0;
f(2) = 1;
f(3) = 2;
f(n) = max(f(i)*f(n-i))(i=2,3,4,....,n/2)
注意当n<=3和n>=4是两种情况，当n<=3时，可以直接返回；当n>=4时，需要计算
leetcode题解如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27class Solution {
public:
int cuttingRope(int n) {
if(n <= 1)
return 0;
if(n == 2)
return 1;
if(n == 3)
return 2;
int fn[n+1];
//n>=4的情况，当长度为4的绳子分为1和3时，3无需再分，因为3只能分成1和2，乘积最大为2，不如不分最大为3
fn[0] = 0;
fn[1] = 0;
fn[2] = 2;
fn[3] = 3;
int max = 0;
for(int i=4;i<=n;i++){ //依次计算f(i)
for(int j=1;j<=i/2;j++){ //因为要剪两段，一段是j，一段是i-j，所以1<j<i/2
if(fn[j] * fn[i-j] > max)
max = fn[j] * fn[i-j];
}
fn[i] = max;
max = 0;
}
return fn[n];
}
};
解法二（贪婪算法）
当n>=5时，3(n-3)> 2(n-2)；应该尽量剪长度为3的绳子
当n=4时，22 > 13；当绳子为4时，剪成2段长度为2的绳子
当n=3时，最大为2；
当n=2时，最大为1；
当n<2时，不能剪乘积为0
leetcode题解如下，当n<4时在函数起始部分处理；
当n>4时，尽量剪成长度为3的段，剩下的绳子当n=4时，恰好f(4)=22=4，n<4就直接不剪了，所以无需对剪成长度的3的绳子剩下的部分做额外处理，直接res\n%1000000007即可。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18class Solution {
public:
int cuttingRope(int n) {
if(n < 2)
return 0;
if(n == 2)
return 1;
if(n == 3)
return 2;
long long int res = 1;
while(n > 4){
res = res * 3 % 1000000007;
n -= 3;
}
res = res * n % 1000000007; // left <= 4
return res;
}
};
15.二进制中1的个数
给定一个整数n，判断整数中二进制形式中1的个数
解法1
直接去判断n&0x1是否不为0，注意每次判断后，不要用n/=2，要用n = n >> 1进行n的移位，提高效率。
leetcode 题解如下：1
2
3
4
5
6
7
8
9
10
11
12class Solution {
public:
int hammingWeight(uint32_t n) {
int res = 0;
while(n){
if(n & 0x1)
res += 1;
n = n >> 1;
}
return res;
}
};
解法2
只要整数n不为0，那么它二进制形式中一定至少有1个1，n-1在二进制形式中相当于将最右边的1变为了0，低位由0变为了1；
(n-1)&n的结果会将最右边的1变为0，如果(n-1)&n的结果还不为0，说明n中还有1，能做多少次（n-1）&n的操作，就相当于有多少个1.
leetcode 题解如下：1
2
3
4
5
6
7
8
9
10
11
12class Solution {
public:
int hammingWeight(uint32_t n) {
int res = 0;
while(n){
res++;
n = (n - 1) & n ;
}
return res;
}
};
16.数值的整数次方
实现函数double Power(double x, int n)，底数和指数都有可能是正数、负数和0.
有一个边界的测试用例，n = -2147483648，int的范围是-2147483648~2147483647，如果指数为负数，将指数转化为正数，当指数为-2147483648时就会溢出。所以考虑递归实现，n是负数时，移位操作后还是负数，在函数起始时加一个判断。
再就是res的平方的问题，x*x的n次方就等于x的n次方的平方了。
注意如果n是奇数，平方相当于少算了一次x，需要再乘一次x。
leetcode 题解如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class Solution {
public:
double myPow(double x, int n){
if(n == 0)
return 1;
if(n == 1)
return x;
if(n == -1)
return 1/x;
if(n & 0x1)
return myPow(x*x, n>>1) * x;
else
return myPow(x*x, n>>1);
}
};
17.打印从1到最大的n位数
给定n，打印出从1到最大的n位的十进制数，注意是从1开始。
方法一
比较简单的方法是先计算最小的n+1位数，然后循环输出从1到n位十进制数。
leetcode 题解：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15class Solution {
public:
vector<int> printNumbers(int n) {
int num = 1;
vector<int> res;
for(int i=0;i<n;i++){
num *= 10;
}
for(int i=1;i<num;i++){
res.push_back(i);
}
return res;
}
};
方法二(大数加法)
1 | class Solution { |
18.删除链表的节点
给定链表和一个节点，在链表中删除这个节点，链表保证节点不重复。
算法一
leetcode给定的是一个值，而不是一个节点，所以不能用剑指offer里的算法。所以只能遍历链表，找到那个值，然后删除节点。
leetcode题解如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteNode(ListNode* head, int val) {
if(!head)
return NULL;
if(head->val == val)
return head->next;
ListNode* cur_node = head;
ListNode* pre_node = NULL;
while(cur_node != NULL && cur_node->val != val){
pre_node = cur_node;
cur_node = cur_node->next;
}
if(cur_node != NULL){ //找到被删除的节点
pre_node->next = cur_node->next;
}
return head;
}
};
算法二（leetcode 237）
给定一个节点，这道题目限制了删除的节点不是尾节点，所以可以直接将待删除节点的next的val赋值到该节点上，然后删除next，注意不能直接删除node->next，另外delete之后要置空。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
void deleteNode(ListNode* node) {
if(!node)
return;
ListNode* next_node = node->next;
node->val = next_node->val;
node->next = next_node->next;
delete next_node;
next_node = NULL;
return;
}
};
补充
在此基础上增加删除的节点是头节点、尾节点的情况：
删除排序链表中的重复节点
leetcode 83(删除重复部分，保留一个节点)
1 | /** |
leetcode 82(不保留重复节点)
这道题的坑是在循环删除时不能用DeleteNode->val ==Node->val，因为Node已经被删除了。nextNode代表着与Node不重复的下一个节点，prevNode表示与Node不重复的上一个节点。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* deleteDuplicates(ListNode* head) {
if(!head || head->next==NULL)
return head;
ListNode* Node = head;
ListNode* prevNode = NULL;
while(Node!=NULL){
ListNode* nextNode = Node->next;
bool needDelete = false;
if(nextNode != NULL && nextNode->val == Node->val)
needDelete = true;
if(!needDelete){
prevNode = Node;
Node = Node->next;
}
else{
ListNode* DeleteNode = Node;
int deleteVal = Node->val;
while(DeleteNode && (DeleteNode->val == deleteVal)){
nextNode = DeleteNode->next;
delete DeleteNode;
DeleteNode = NULL;
DeleteNode = nextNode;
}
//重复的节点是头节点
if(prevNode == NULL)
head = nextNode;
else
prevNode->next = nextNode;
}
Node = nextNode;
}
return head;
}
};
21.调整数组顺序使奇数位于偶数前面
使用两个指针，i从0开始，j从末尾开始，i先找到第一个偶数，j找到第一个奇数，然后两个数字交换，继续遍历。
还要注意一下代码中运算符的优先级，！>关系运算符>逻辑运算符>&&>||>条件运算符>赋值运算符
leetcode题解如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class Solution {
public:
vector<int> exchange(vector<int>& nums) {
if(nums.size()==0)
return nums;
int i = 0;
int j = nums.size() - 1;
while(i<=j){
while(i<nums.size() && (nums[i]&0x1))
i++;
while(j>=0 && !(nums[j]&0x1))
j--;
if(i<j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
return nums;
}
};
剑指offer上说要增加算法通用性，把判断是否为偶数单独设为一个函数：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25class Solution {
public:
vector<int> exchange(vector<int>& nums) {
if(nums.size()==0)
return nums;
int i = 0;
int j = nums.size() - 1;
while(i<=j){
while(i<nums.size() && !isEven(nums[i]))
i++;
while(j>=0 && isEven(nums[j]))
j--;
if(i<j){
int temp = nums[i];
nums[i] = nums[j];
nums[j] = temp;
}
}
return nums;
}
bool isEven(int n){
return (n&0x1)==0;
}
};
22.链表中倒数第k个节点
首先找到倒数第k个节点：
准备两个指针，slow_node指向头节点，fast_node先走k-1步；
然后两个指针同时先前遍历，当fast_node到达链表最后一个节点时，slow_node恰好指向的就是倒数第k个节点。
leetcode题解如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* getKthFromEnd(ListNode* head, int k) {
if(!head || k == 0)
return NULL;
ListNode* fastNode = head;
ListNode* slowNode = head;
for(int i=0;i<k-1;i++){
if(fastNode==NULL)
return NULL;
fastNode = fastNode->next;
}
while(fastNode->next!=NULL){
slowNode = slowNode->next;
fastNode = fastNode->next;
}
return slowNode;
}
};
leetcode 19（删除链表倒数第k个节点）
因为还要删除节点，所以遍历时还要准备一个prev_node，删除slow_node，注意倒数第k个节点是head的情况。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* removeNthFromEnd(ListNode* head, int n) {
if(!head || n == 0)
return NULL;
ListNode* fastNode = head;
ListNode* slowNode = head;
for(int i=0;i<n-1;i++){
if(fastNode==NULL)
return NULL;
fastNode = fastNode->next;
}
ListNode* prevNode = NULL;
while(fastNode->next!=NULL){
prevNode = slowNode;
slowNode = slowNode->next;
fastNode = fastNode->next;
}
if(prevNode==NULL){
head = head->next;
}
else
prevNode->next = slowNode->next;
delete slowNode;
slowNode = NULL;
return head;
}
};
23.链表中环的入口节点
描述：链表中存在环，找到环的入口节点。
leetcode 141(判断是否有环)
准备慢指针和快指针两个，如果存在环的话，快指针会和慢指针相遇。注意一下快指针和慢指针的初始值以及循环的判断条件。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
bool hasCycle(ListNode *head) {
if(!head)
return false;
ListNode* slowNode = head->next;
if(slowNode==NULL)
return false;
ListNode* fastNode = slowNode->next;
while(fastNode && slowNode){
if(fastNode == slowNode)
return true;
slowNode = slowNode->next;
fastNode = fastNode->next;
if(fastNode)
fastNode = fastNode->next;
}
return false;
}
};
leetcode 142(找到环的入口节点)
先利用141的算法判断是否有环，找到环中的任意一个节点，如果有环的话，利用环中的任意一个节点统计环中节点数目n；
然后设置快指针和慢指针，快指针先向前走n步，然后两个指针同时向前遍历，如果两指针相遇，则找到了入口节点，因为在环内有n个节点，入口节点与它的上一个节点距离n-1个位置，所以快指针要先走n步。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *detectCycle(ListNode *head) {
if(!head)
return NULL;
if(head->next==NULL)
return NULL;
ListNode* meetNode = hasCycle(head);
if(!meetNode)
return NULL;
//计算环中的节点数目
int cycleNum = 1;
ListNode* node = meetNode;
while(node->next != meetNode){
node = node->next;
cycleNum++;
}
ListNode* slowNode = head;
ListNode* fastNode = head;
for(int i=0;i<cycleNum;i++)
fastNode = fastNode->next;
while(fastNode !=slowNode){
fastNode = fastNode->next;
slowNode = slowNode->next;
}
return fastNode;
}
ListNode* hasCycle(ListNode *head) {
if(!head)
return NULL;
ListNode* slowNode = head->next;
if(slowNode==NULL)
return NULL;
ListNode* fastNode = slowNode->next;
while(fastNode && slowNode){
if(fastNode == slowNode)
return fastNode;
slowNode = slowNode->next;
fastNode = fastNode->next;
if(fastNode)
fastNode = fastNode->next;
}
return NULL;
}
};
24.反转链表
注意链表为空和链表只有一个节点的情况。
设置三个指针，分别记录prev_node，cur_node和next_node，因为将当前节点指向prev_node之后，这个链表相当于断开了，所以需要一个next_node指针记录。
leetcode题解如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode* reverseList(ListNode* head) {
if(!head)
return NULL;
if(head->next==NULL)
return head;
ListNode* prevNode = head;
ListNode* Node = head->next;
head->next = NULL;
ListNode* nextNode;
while(Node->next!=NULL){
nextNode = Node->next;
Node->next = prevNode;
prevNode = Node;
Node = nextNode;
}
Node->next = prevNode;
return Node;
}
};
25.合并两个排序的链表
解法一(迭代)
1 | /** |
解法二(递归)
1 | /** |
26.树的子结构
输入两棵二叉树A和B，判断B是不是A的子结构。(约定空树不是任意一个树的子结构)。如果B是A的子结构，则A中出现与B中相同的节点和数值。
如果根节点相同，则继续比较A和B的左子树、右子树。
如果根节点不同，则比较A的左子树和B；
如果A的左子树和B不同，则比较A的右子树和B。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSubStructure(TreeNode* A, TreeNode* B) {
if(!A && !B)
return true;
if((A && !B) || (!A && B))
return false;
bool res = false;
if(A-> val == B->val)
res = hasTree(A, B);
if(!res)
res = isSubStructure(A->left, B);
if(!res)
res = isSubStructure(A->right, B);
return res;
}
bool hasTree(TreeNode* A, TreeNode* B){
if(!B)
return true;
if(!A)
return false;
if(A->val == B->val){
return hasTree(A->left, B->left) && hasTree(A->right, B->right);
}
return false;
}
};
27.二叉树的镜像
求一个二叉树的镜像。
交换它的左子节点和右子节点。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
TreeNode* mirrorTree(TreeNode* root) {
if(!root)
return NULL;
if(root->left==NULL && root->right==NULL)
return root;
TreeNode* node = root->left;
root->left = root->right;
root->right = node;
if(root->left)
mirrorTree(root->left);
if(root->right)
mirrorTree(root->right);
return root;
}
};
28.对称的二叉树
判断二叉树是不是对称的，如果二叉树和它的镜像是一样的，则二叉树就是对称的。
如果按照两种遍历顺序它们是相同的，则这棵树就是对称的二叉树。
根节点->左子树->右子树
根节点->右子树->左子树1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isSymmetric(TreeNode* root) {
return helper(root, root);
}
bool helper(TreeNode* root1, TreeNode* root2){
if(!root1 && !root2)
return true;
if(!root1 || !root2)
return false;
if(root1->val == root2->val)
return helper(root1->left, root2->right) && helper(root1->right, root2->left);
else
return false;
}
};
29.顺时针打印矩阵
给定一个矩阵，从外向里顺时针打印矩阵里的元素。一圈有四个方向，主要有以下关键：
每一圈的起点start的row==col，然后终止条件是start*2 < rows 和start*2 < cols，每一圈endX = rows-start-1,endY = cols - start - 1。
第一步从左到右：从(start, start) -> (start, endY)，保证 endY >= start，至少有1列;
第二步从上到下：从(start+1,endY) -> (endX, endY), 保证endX>start，至少有2行。
第三步从右向左：从(endX, endY-1) -> (endX, start),保证endX>start, endY>start，至少有2行2列。
第四步从下到上：从(endX-1,start) -> (start+1,start),保证endX-1>start，endY>start，至少有3行2列。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33class Solution {
public:
vector<int> spiralOrder(vector<vector<int>>& matrix) {
vector<int> res;
if(matrix.size()==0)
return res;
int rows = matrix.size();
int cols = matrix[0].size();
int start = 0;
while(start*2 < rows && start*2 < cols){
int endX = rows - start - 1;
int endY = cols - start - 1;
if(endY >= start){
for(int i=start;i<=endY;i++)
res.push_back(matrix[start][i]);
}
if(endX > start){
for(int i=start+1;i<=endX;i++)
res.push_back(matrix[i][endY]);
}
if(endX > start && endY > start){
for(int i=endY-1;i>=start;i--)
res.push_back(matrix[endX][i]);
}
if(endX-start > 1 && endY > start){
for(int i=endX-1;i>start;i--)
res.push_back(matrix[i][start]);
}
start++;
}
return res;
}
};
30.包含min函数的栈
定义栈的数据结构，实现一个能够得到栈的最小元素的 min 函数，再这个栈中调用 min、push 及 pop 的时间复杂度都是 O(1)。
增加一个辅助栈，辅助栈里记录了当前栈的最小值，调用min函数时直接返回辅助栈的栈顶元素。每次将数据压入数据栈时，比较当前辅助栈的栈顶元素和该数据的大小，更新最小元素。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49class MinStack {
public:
/** initialize your data structure here. */
MinStack() {
}
stack<int> dataStack;
stack<int> minStack;
void push(int x) {
dataStack.push(x);
if(!minStack.empty()){
int min_num = minStack.top();
if(min_num > x)
minStack.push(x);
else
minStack.push(min_num);
}
else
minStack.push(x);
}
void pop() {
if(!dataStack.empty()){
dataStack.pop();
minStack.pop();
}
}
int top() {
assert(!dataStack.empty());
return dataStack.top();
}
int min() {
assert(!dataStack.empty());
return minStack.top();
}
};
/**
* Your MinStack object will be instantiated and called as such:
* MinStack* obj = new MinStack();
* obj->push(x);
* obj->pop();
* int param_3 = obj->top();
* int param_4 = obj->min();
*/
31.栈的压入、弹出序列
遍历出栈序列，维护一个栈模拟压栈序列，如果当前栈为空或栈顶数值不等于popped[i]时，则按照压栈序列将数值压入栈中，直至入栈序列全部压入栈中或当前栈顶等于popped[i]。注意一些判断条件。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
if(pushed.size()==0 && popped.size()==0)
return true;
if(pushed.size() != popped.size())
return false;
stack<int> s1;
int j = 0,i = 0;
for(i=0;i<popped.size();i++){
if(s1.empty() || s1.top() != popped[i]){
while(j < pushed.size()){
s1.push(pushed[j++]);
if(s1.top() == popped[i])
break;
}
if(j==pushed.size() && s1.top() != popped[i])
return false;
}
s1.pop();
}
if(s1.empty() && i == popped.size())
return true;
else
return false;
}
};
32.从上到下打印二叉树
不分行从上到下打印二叉树
从上到下打印出二叉树的每个节点，同一层的节点按照从左到右的顺序打印。
维护一个队列保存当前节点的左子节点和右子节点。将父节点压入res之后，再从队列中依次取出左子节点和右子节点。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> levelOrder(TreeNode* root) {
vector<int> res;
deque<TreeNode*> dtree;
if(!root)
return res;
dtree.push_back(root);
while(!dtree.empty()){
TreeNode* node = dtree.front();
dtree.pop_front();
res.push_back(node->val);
if(node->left)
dtree.push_back(node->left);
if(node->right)
dtree.push_back(node->right);
}
return res;
}
};
分行从上到下打印二叉树
从上到下按层打印二叉树，同一层的节点按从左到右的顺序打印，每一层打印到一行。
主要是控制好level这个变量就可以，注意vector的resize操作。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> res;
vector<vector<int>> levelOrder(TreeNode* root) {
if(!root)
return res;
helper(root, 0);
return res;
}
void helper(TreeNode* root, int level){
if(!root)
return;
if(res.size()<level+1)
res.resize(level+1);
res[level].push_back(root->val);
if(root->left)
helper(root->left, level+1);
if(root->right)
helper(root->right, level+1);
}
};
之字形打印二叉树
第一行按照从左到右的顺序打印，第二层按照从右到左的顺序打印，第三行再按照从左到右的顺序打印，其他行以此类推。
维护一个current栈和一个next栈，如果当前打印的层数为偶数（0，2，4…），下一层需要从右到左打印，则先将左子节点压栈，然后将右子节点压栈；反之，下一层需要从左到右打印，先将右子节点压栈，然后将左子节点压栈。根据current栈为空的条件来控制res。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> levelOrder(TreeNode* root) {
vector<vector<int>> res;
stack<TreeNode*> s[2];
if(!root)
return res;
int current = 0;
int next = 1;
int level = 0;
s[current].push(root);
while(!s[0].empty() || !s[1].empty()){
TreeNode* node = s[current].top();
s[current].pop();
if(res.size()<level+1)
res.resize(level+1);
res[level].push_back(node->val);
if(current == 0){
if(node->left)
s[next].push(node->left);
if(node->right)
s[next].push(node->right);
}
else{
if(node->right)
s[next].push(node->right);
if(node->left)
s[next].push(node->left);
}
if(s[current].empty()){
level++;
next = 1 - next;
current = 1 - current;
}
}
return res;
}
};
33.二叉搜索树的后序遍历序列
输入一个整数数组，判断该数组是不是某二叉搜索树的后序遍历结果。
后序遍历的最后一个节点是根节点。然后前面的数可以分为两部分，比根节点小的是左子树部分，比根节点大的是右子树部分。
首先获得根节点，然后从头遍历找到左子树部分（比根节点小的），递归检查左子树；然后检查右子树部分是否都比根节点大，如果符合，则递归检查右子树，否则则返回false。
注意将vector转成数组指针作为参数，需要将第一个元素的地址传入。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29class Solution {
public:
bool verifyPostorder(vector<int>& postorder) {
if(postorder.size()<=0)
return true;
int length = postorder.size();
return helper(&postorder[0], length);
}
bool helper(int* postorder, int length){
if(length <= 0)
return false;
int root = postorder[length-1];
int i = 0;
for(;i<length-1;i++)
if(postorder[i] > root)
break;
for(int j=i;j<length-1;j++)
if(postorder[j] < root)
return false;
bool left = true;
if(i > 0)
left = helper(&postorder[0], i);
bool right = true;
if(length - i - 1 > 0)
right = helper(&postorder[i], length-i-1);
return (left&&right);
}
};
34.二叉树中和为某一值的路径
给定一个数值和一个二叉树，输出二叉树中和为该值的所有路径，从树的根节点开始往下一直到叶节点所经过的节点形成一条路径。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<vector<int>> res;
vector<int> path;
vector<vector<int>> pathSum(TreeNode* root, int sum) {
if(!root)
return res;
helper(root, sum, 0);
return res;
}
void helper(TreeNode* root, int sum, int cursum){
cursum += root->val;
path.push_back(root->val);
if(root->left == NULL && root->right == NULL){
if(cursum == sum)
res.push_back(path);
}
if(root->left){
helper(root->left, sum, cursum);
}
if(root->right)
helper(root->right, sum, cursum);
path.pop_back();
}
};
35.复杂链表的复制
在复杂链表中，除了指向下一个节点外，还有一个指针指向链表中的任意节点或NULL。
第一个想到的方法就是先复制链表中的每一个节点，并链接起来，然后再遍历链表，修复其random指针，由于寻找每一个random指向的节点都需要遍历一遍这个链表，因此时间复杂度为o(n^2)。
思路分为三个部分：
第一步复制原始链表中的每一个节点N，并创建新的节点N’，N指向N’。
第二步修复新链表上面的random指针。
第三步将两个链表拆开。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60/*
// Definition for a Node.
class Node {
public:
int val;
Node* next;
Node* random;
Node(int _val) {
val = _val;
next = NULL;
random = NULL;
}
};
*/
class Solution {
public:
Node* copyRandomList(Node* head) {
if(!head)
return NULL;
cloneList(head);
addRondom(head);
Node* copyhead = NULL;
Node* pNode = head;
Node* copyNode = NULL;
if(pNode){
copyhead = pNode->next;
copyNode = pNode->next;
pNode->next = copyNode->next;
pNode = pNode->next;
}
while(pNode){
copyNode->next = pNode->next;
copyNode = pNode->next;
pNode->next = copyNode->next;
pNode = pNode->next;
}
return copyhead;
}
void addRondom(Node* head){
Node* pNode = head;
while(pNode){
Node* newNode = pNode->next;
if(pNode->random)
newNode->random = pNode->random->next;
pNode = newNode->next;
}
}
void cloneList(Node* head){
Node* pNode = head;
while(pNode){
Node* newNode = new Node(pNode->val);
newNode->next = pNode->next;
pNode->next = newNode;
pNode = newNode->next;
}
}
};
36. 二叉搜索树与双向链表
给定一个二叉搜索树，将其转化为一个排序的双向链表。全局变量LastNode记录上一个节点，采用中序遍历二叉树，因为为二叉搜索树左子节点的值小于根节点的值，右子节点的值大于根节点的值，因此中序遍历的顺序恰好是从小到大的顺序。
将二叉搜索树看作三个部分，一个是左子树，一个是根节点，一个是右子树，根节点的left在双向链表中指向它左子树的最右叶子节点，根节点的right指向它的右子树的最左的叶子节点。
convertNode得到的双向链表的头节点和尾节点还没有调整，因此需要调整头节点的left和尾节点的right。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52/*
// Definition for a Node.
class Node {
public:
int val;
Node* left;
Node* right;
Node() {}
Node(int _val) {
val = _val;
left = NULL;
right = NULL;
}
Node(int _val, Node* _left, Node* _right) {
val = _val;
left = _left;
right = _right;
}
};
*/
class Solution {
public:
Node* LastNode = NULL;
Node* treeToDoublyList(Node* root) {
if(!root)
return NULL;
convertNode(root);
Node* head = root;
while(head->left)
head = head->left;
LastNode->right = head;
head->left = LastNode;
return head;
}
void convertNode(Node* root){
if(!root)
return;
Node* pcurrent = root;
if(pcurrent->left)
convertNode(pcurrent->left);
pcurrent->left = LastNode;
if(LastNode)
LastNode->right = pcurrent;
LastNode = pcurrent;
if(pcurrent->right)
convertNode(pcurrent->right);
}
};
37.序列化二叉树
38.字符串的排列
39.数组中出现次数超过一半的数字
数组中有一个数字出现的次数超过数组长度的一半，请找出这个数字。假设数组是非空的，而且这个数一定存在。
解法一
如果这个数字出现的次数超过一半，遍历nums，统计它出现的次数，遇到不等于它的数字，则次数-1，那么到最后它的次数一定是大于0的，因为它出现的次数大于一半，减的次数小于一半。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
int majorityElement(vector<int>& nums) {
int time = 1;
int curnum = nums[0];
for(int i=1;i<nums.size();i++){
if(nums[i] == curnum)
time++;
else
time--;
if(time == 0){
curnum = nums[i];
time = 1;
}
}
return curnum;
}
};
解法二
还是利用快排的思想，将其排序后，中位数就是出现次数超过一半的那个数字。但这样会超时。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33class Solution {
public:
int majorityElement(vector<int>& nums) {
int left = 0;
int right = nums.size()-1;
int middle = nums.size() / 2;
while(left < right){
int index = partition(nums, left, right);
if(index == middle)
break;
else if(index < middle)
left = index + 1;
else
right = index - 1;
}
return nums[middle];
}
int partition(vector<int>& nums, int left, int right){
int base = nums[left];
while(left < right){
while(left < right && nums[right] >= base)
right--;
nums[left] = nums[right];
while(left < right && nums[left] <= base)
left++;
nums[right] = nums[left];
}
nums[left] = base;
return left;
}
};
直接调用c++内置的sort函数，然后返回中间的元素。1
2
3
4
5
6
7class Solution {
public:
int majorityElement(vector<int>& nums) {
sort(nums.begin(), nums.end());
return nums[nums.size()/2];
}
};
40.最小的k个数
给定数组，找出最小的k个数。
解法一
维护一个长度为k的容器：
当容器内的数字个数小于k时，取nums[i]压入容器；
如果容器内的数字个数大于等于k个时，则取出容器中最大的数与nums[i]比较，如果nums[i]较大，则i++继续遍历；否则将容器中最大的数字弹出，然后将nums[i]压入该容器中。
c++语言中，multiset是1
2
3
4
5
6
multiset<int> s; //默认从小到大排序
multiset<int, greater<int>> s1; //从大到小排序
s.insert(nums[i]);//插入
min_num = s.begin();
s.erase(c);//将c指向的元素删除
leetcode题解如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
vector<int> res;
if(arr.size()<=0 || k > arr.size())
return res;
if(arr.size() == k)
return arr;
multiset<int, greater<int>> s;
for(int i=0;i<arr.size();i++){
if(s.size()< k)
s.insert(arr[i]);
else{
int max_num = *(s.begin());
if(max_num > arr[i]){
s.erase(s.begin());
s.insert(arr[i]);
}
}
}
multiset<int, greater<int>>::iterator si;
for(si=s.begin();si!=s.end();si++)
res.push_back(*si);
return res;
}
};
解法二（面试题 17.14. 最小K个数）
利用快速排序中切分的思想选取一个分割点，如果k个比它小的数字都在它的左边，则直接返回前k个数就可以。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34class Solution {
public:
vector<int> getLeastNumbers(vector<int>& arr, int k) {
vector<int> res;
if(arr.size() <= 0 || k > arr.size())
return res;
if(k == arr.size())
return arr;
int index = partition(arr, 0, arr.size()-1);
while(index != k){
if(index < k)
index = partition(arr, index+1, arr.size()-1);
if(index > k)
index = partition(arr, 0, index-1);
}
for(int i=0;i<k;i++)
res.push_back(arr[i]);
return res;
}
int partition(vector<int>& nums, int left, int right){
int base = nums[left];
while(left < right){
while(left < right && nums[right] >= base)
right--;
nums[left] = nums[right];
while(left < right && nums[left] <= base)
left++;
nums[right] = nums[left];
}
nums[left] = base;
return left;
}
};
41.数据流中的中位数
42. 连续子数组的最大和
数组中的一个或连续多个整数组成一个子数组。求所有子数组的和的最大值。要求时间复杂度为o(n)。
动态规划的思想，假设cursum是以i-1为末尾的连续子数组的最大和，如果cursum<0，则cursum+nums[i]<nums[i]，所以还不如不加前面的子数组，当前最大和更新为nums[i]。另外要实时维护一个maxsum，因为抛弃的cursum可能是最大的和。
leetcode题解如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
int maxSubArray(vector<int>& nums) {
if(nums.size()<=0)
return 0;
int cursum = nums[0];
int maxsum = cursum;
for(int i=1;i<nums.size();i++){
if(cursum < 0)
cursum = nums[i];
else
cursum += nums[i];
if(cursum > maxsum)
maxsum = cursum;
}
return maxsum;
}
};
43.1~n整数中1出现的次数
方法一
统计每个数字中1出现的个数，然后相加，但是会超时。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
int countDigitOne(int n) {
int res = 0;
for(int i=1;i<=n;i++)
res += helper(i);
return res;
}
int helper(int n){
int res = 0;
while(n){
if(n % 10 == 1)
res += 1;
n = n / 10;
}
return res;
}
};
方法二
待补充
44.数字序列中某一位的数字
根据不同位数的数字的1的个数来计算，比如一位数有10个（0-9），二位数有90个（10-99），三位数有900个（100-999）.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37class Solution {
public:
int findNthDigit(int n) {
long long int digits = 1;
while(true){
long long int numbers = countOfIntegers(digits);
if(n < digits * numbers)
return digitIndex(n, digits);
n = n - numbers * digits;
digits++;
}
}
int countOfIntegers(int index){
if(index == 1)
return 10;
return pow(10, index-1) * 9;
}
int digitIndex(int num, int digits){
int number = beginOfnumber(digits) + num / digits;
int index = digits - num % digits;
int res = 0;
while(index){
res = number % 10;
number /= 10;
index--;
}
return res;
}
int beginOfnumber(int index){
if(index == 1)
return 0;
return pow(10, index-1);
}
};
45.把数组排成最小的数
对数组排序，对于两个数m和n来说，如果m<n,则mn<nm；否则nm<mn。n和m按照排成最小数的升序排列。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19class Solution {
public:
string minNumber(vector<int>& nums) {
sort(nums.begin(), nums.end(), compfunc);
string s = "";
for(int i=0;i<nums.size();i++)
s += std::to_string(nums[i]);
return s;
}
static bool compfunc(int num1, int num2){
string s1 = std::to_string(num1) + std::to_string(num2);
string s2 = std::to_string(num2) + std::to_string(num1);
if(s1 < s2)
return true;
else
return false;
}
};
46.把数字翻译成字符串
给定一个数字，我们按照如下规则把它翻译为字符串：0 翻译成 “a” ，1 翻译成 “b”，……，11 翻译成 “l”，……，25 翻译成 “z”。一个数字可能有多个翻译。
可以把单个数字进行翻译，也可以连起来一起翻译。
为了避免重复，从末尾开始计算，使用数组nums[i]记录从末尾到i的不同翻译的次数，首先考虑自己单独进行翻译，那么count[i] = count[i+1]；然后考虑和i+1进行翻译，那么count[i] += count[i+2]，但是要注意边界，还要注意两个连续数字一起翻译时转化成的数字要有意义，两位数就要在10~25之间，因为是从0开始。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27class Solution {
public:
int translateNum(int num) {
string s = std::to_string(num);
int length = s.length();
vector<int> nums(length, 0);
for(int i=length-1;i>=0;--i){
int count = 0;
if(i < length-1)
count = nums[i+1];
else
count = 1;
if(i < length - 1){
int digit = (s[i]-'0')*10 + (s[i+1]-'0');
if(digit >= 10 && digit <= 25){
if(i < length -2)
count += nums[i+2];
else
count += 1;
}
}
nums[i] = count;
}
return nums[0];
}
};
47.礼物的最大价值
设max_values[i][j]是从起点到(i, j)礼物的最大值，那么max_values[i][j] = grid[i][j] + max(max_values[i-1][j], max_values[i][j-1])1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
public:
int rows, cols;
int maxValue(vector<vector<int>>& grid) {
if(grid.size()==0)
return 0;
rows = grid.size();
cols = grid[0].size();
vector<vector<int>> max_values(rows, vector<int>(cols, 0));
for(int i=0;i<rows;i++){
for(int j=0;j<cols;j++){
int left = 0;
int up = 0;
if(i-1>=0)
up = max_values[i-1][j];
if(j-1>=0)
left = max_values[i][j-1];
max_values[i][j] = max(up, left) + grid[i][j];
}
}
return max_values[rows-1][cols-1];
}
};
48.最长不含重复字符的子字符串
使用一个数组记录当前字符上一次出现的位置，比较当前长度和当前字符与上一次出现的距离d的大小，如果d>cur_len，说明上一个字符不在当前最大字串内，可以加上现在这个字符；如果d<=cur_len，说明上一个字符在当前最大字串内，以当前字符的最大子字符串的长度是d，更新cur_len。每次处理完一个字符之后都更新max_len。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21class Solution {
public:
int lengthOfLongestSubstring(string s) {
if(s.length()==0)
return 0;
vector<int> pos(256, -1);
int max_len = 0, cur_len = 0;
for(int i=0;i<s.length();i++){
int prev_idx = pos[s[i]-'\0'];
if(prev_idx == -1 || i - prev_idx > cur_len)
cur_len++;
else{
max_len = max(max_len, cur_len);
cur_len = i - prev_idx;
}
pos[s[i]-'\0'] = i;
max_len = max(max_len, cur_len);
}
return max_len;
}
};
49. 丑数
只包含因子2，3，5的数字叫做丑数。
因为较大的丑数必然是较小的丑数的倍数，每个丑数都会从(uglys[idx2]2, uglys[idx3]3, uglys[idx5]5)中产生，使用idx2,idx3和idx5记录一个位置，就是uglys[idx2]\2就会超过当前丑数的最大值。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29class Solution {
public:
int nthUglyNumber(int n) {
if(n <= 0)
return 0;
if(n == 1)
return 1;
vector<long long int> uglys(n);
uglys[0] = 1;
int next = 1;
int idx2=0, idx3=0, idx5=0;
while(next < n){
uglys[next] = my_min(uglys[idx2]*2, uglys[idx3]*3, uglys[idx5]*5);
while(uglys[idx2]*2 <= uglys[next])
idx2++;
while(uglys[idx3]*3 <= uglys[next])
idx3++;
while(uglys[idx5]*5 <= uglys[next])
idx5++;
next++;
}
return uglys[n-1];
}
long long int my_min(long long int n1, long long int n2, long long int n3){
return min(min(n1, n2), min(n2, n3));
}
};
50. 只出现一次的字符
比较简单，根据下标统计就可以。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16class Solution {
public:
char firstUniqChar(string s) {
char res = ' ';
if(s == "")
return res;
vector<int> cnt(256, 0);
for(int i=0;i<s.length();i++){
cnt[s[i]-'\0'] += 1;
}
for(int i=0;i<s.length();i++)
if(cnt[s[i]-'\0'] == 1)
return s[i];
return res;
}
};
51.数组中的逆序对
在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。输入一个数组，求出这个数组中的逆序对的总数。
思路：把数组分割成两个子数组，下统计子数组内部的逆序对，然后再统计两个数组间的逆序对。1
2
52.两个链表的第一个公共节点
只要链表有一个公共节点，在这个节点之后，它们的节点都是公共的。
方法一：把两个链表的节点值都压入栈中，然后比较两个栈中的数值，如果相同则继续比较，返回最后一个相同的节点值。
方法二：统计两个链表的长度k1，k2，找到较长的那个链表，遍历时先在较长链表上走|k2 - k1|步，然后同时遍历，直到找到第一个节点值相同的节点，返回该节点。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45/**
* Definition for singly-linked list.
* struct ListNode {
* int val;
* ListNode *next;
* ListNode(int x) : val(x), next(NULL) {}
* };
*/
class Solution {
public:
ListNode *getIntersectionNode(ListNode *headA, ListNode *headB) {
int l1 = get_list_length(headA);
int l2 = get_list_length(headB);
ListNode* long_node = headA;
ListNode* short_node = headB;
int len = l1 - l2;
if(len < 0){
len = -len;
long_node = headB;
short_node = headA;
}
for(int i=0;i<len;i++){
long_node = long_node->next;
}
while(long_node && short_node && long_node != short_node){
long_node = long_node->next;
short_node = short_node->next;
}
if(short_node == NULL || long_node == NULL)
return NULL;
else
return short_node;
}
int get_list_length(ListNode* head){
int length = 0;
ListNode* node = head;
while(node){
length++;
node = node->next;
}
return length;
}
};
53.在排序数组中查找数字
题目一：数字在排序数组中出现的次数
方法一，o(n)
使用map统计数组每个元素出现的次数，然后根据target返回对应的次数。时间复杂度为o(n)。1
2
3
4
5
6
7
8
9
10
11class Solution {
public:
int search(vector<int>& nums, int target) {
map<int,int> count;
for(int i=0;i<nums.size();i++){
count[nums[i]] += 1;
}
return count[target];
}
};
方法二，o(log(n))
利用二分查找寻找target在数组中第一次和最后依次出现的位置，从而得到出现的次数。注意没找到的话要返回0.1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51class Solution {
public:
int search(vector<int>& nums, int target) {
int res = 0;
int first = get_first(nums, target, 0, nums.size()-1);
int last = get_last(nums, target, 0, nums.size()-1);
if(first != -1 && last != -1)
res = last - first + 1;
return res;
}
int get_first(vector<int>& nums, int target, int left, int right){
if(left > right)
return -1;
int midIndex = (left + right) >> 1;
int midData = nums[midIndex];
if(left <= right){
if(midData == target)
if((midIndex > 0 && nums[midIndex-1] != target) || midIndex == 0) //表示target只出现了一次
return midIndex;
else
right = midIndex - 1;
else if(midData > target)
right = midIndex - 1;
else
left = midIndex + 1;
}
return get_first(nums, target, left, right);
}
int get_last(vector<int>& nums, int target, int left, int right){
if(left > right)
return -1;
int midIndex = (left + right) >> 1;
int midData = nums[midIndex];
if(left <= right){
if(midData == target)
if(midIndex < nums.size()-1 && nums[midIndex+1] != target || midIndex == nums.size()-1) //表示target只出现了一次
return midIndex;
else
left = midIndex + 1;
else if(midData > target)
right = midIndex - 1;
else
left = midIndex + 1;
}
return get_last(nums, target, left, right);
}
};
0~n-1中缺失的数字
还是利用二分查找，比较nums[i]和i的关系：
如果中间元素midData==midIndex，则只需在后半部分查找即可；
如果midData!=midIndex, 但是它的前一个元素的数值和坐标相等，说明这个中间元素就是第一个数值与坐标不相等的元素，返回该元素；
如果midData!=midIndex, 但是它的前一个元素的数值和坐标不相等，则需要在前半部分继续查找。
要注意一些特殊用例，比如[0], [1]，[1, 2]这种。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23class Solution {
public:
int missingNumber(vector<int>& nums) {
if(nums[0] != 0)
return 0;
return search(nums, 0, nums.size()-1);
}
int search(vector<int>& nums, int left, int right){
if(left > right)
return nums.size();
int midIndex = (left + right) >> 1;
int midData = nums[midIndex];
if(midIndex == midData)
left = midIndex + 1;
else
if(midIndex > 0 && nums[midIndex-1] == midIndex -1)
return midIndex;
else
right = midIndex - 1;
return search(nums, left, right);
}
};
54.二叉搜索树的第k大节点
中序遍历一棵二叉搜索树，得到的就是节点值从小到大排序。我的方法是先将其按照中序遍历将其存储在一个数组中，然后返回第k大节点。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> nums;
int kthLargest(TreeNode* root, int k) {
helper(root);
return nums[nums.size()-k];
}
void helper(TreeNode *root){
if(!root)
return;
if(root->left)
helper(root->left);
nums.push_back(root->val);
if(root->right)
helper(root->right);
}
};
其他解法
采用二分法，先统计右子树的节点个数r_num，如果r_num == k-1，说明root真好是第k大节点；如果r_num > k-1,说明第k大节点在右子树中，递归右子树；如果r_num < k - 1,则说明第k大节点在左子树中，因为只在左子树中寻找，所以应该减去根节点和r_num，寻找第k-1-r_num大节点。它在左子树中排第k-1-r_num，但它在整个二叉树中排第k个。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
int numRoot(TreeNode *root){
if(root==NULL) return 0;
return 1+numRoot(root->right)+numRoot(root->left);
}
class Solution {
public:
int kthLargest(TreeNode* root, int k) {
int r_num=numRoot(root->right);
if(r_num==k-1) return root->val;
else if(r_num>k-1) return kthLargest(root->right,k);
else return kthLargest(root->left,k-1-r_num);
}
};
55.二叉树的深度
题目一
深度：从根节点到叶节点依次经过的节点构成一条树的路径，最长路径的长度就是树的深度。
leetcode题解如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
int maxDepth(TreeNode* root) {
if(root == NULL)
return 0;
int left = maxDepth(root->left);
int right = maxDepth(root->right);
return 1 + max(left, right);
}
};
题目二
判断一棵树是否为平衡二叉树。
平衡二叉树：二叉树中的任意节点的左右子树的深度相差不超过1.
方法：后序遍历，先遍历子节点，然后遍历根节点，计算左右子树的深度差，如果不超过1，则更新以当前节点为根节点的深度，如果每个节点的左右子树深度相差都不超过1，则返回true，否则返回false。这个depth就是记录以当前节点为根节点的深度，为了避免重复遍历，采用后序遍历。
leetcode题解如下：1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
bool isBalanced(TreeNode* root) {
int Depth = 0;
return helper(root, Depth);
}
bool helper(TreeNode* root, int &Depth){
if(!root){
Depth = 0;
return true;
}
int left,right;
if(helper(root->left, left) && helper(root->right, right)){
int diff = left - right;
if(diff >= -1 && diff <= 1){
Depth = 1 + max(left, right);
return true;
}
}
return false;
}
};
56.数组中数字出现的次数
题目一
找到数组中只出现一次的两个数字，除了这两个数字之外，其他数字都出现了两次。
首先将所有的数字进行异或，因为其他数字都出现了两次，所以异或后得到的结果是只出现一次的两个数字异或的结果。
因为两个数字不同，所以找到结果从低位起第一个为1的位置，将数组分为两个子数组，因为分组标准是某一位是否为1，所以只出现一次的两个数字被分到了两个子数组中，出现两次的数字根据某一位是否为1都在一个子数组中。然后分别对两个子数组进行异或，两个子数组异或的结果就是只出现一次的两个数字。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32class Solution {
public:
vector<int> singleNumbers(vector<int>& nums) {
vector<int> res;
int n = 0;
for(int i=0;i<nums.size();i++){
n ^= nums[i];
}
int pos = findBit(n);
int n1=0,n2=0;
for(int i=0;i<nums.size();i++){
if((nums[i] >> pos) & 0x1)
n1 = n1 ^ nums[i];
else
n2 = n2 ^ nums[i];
}
res.push_back(n1);
res.push_back(n2);
return res;
}
int findBit(int n){
int res = 0;
while(n){
if(n & 0x1 == 1)
return res;
n = n >> 1;
res++;
}
return res;
}
};
题目二
在一个数组 nums 中除一个数字只出现一次之外，其他数字都出现了三次。请找出那个只出现一次的数字。
将每个数字按照位相加求和，如果一个数在数组中出现了3次，则它的位相加三次之后能被3整除，所以按位求和之后，再按位对3取余，得到的数字就是只出现了一次的数字。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution {
public:
int singleNumber(vector<int>& nums) {
int res = 0;
int bitmask[32] = {0};
for(int i=0;i<nums.size();i++){
int n = nums[i];
int k = 31;
while(n){
bitmask[k--] += n & 0x1;
n = n >> 1;
}
}
for(int i=0;i<32;i++){
res = res << 1;
res += bitmask[i] % 3;
}
return res;
}
};
57.和为s的数字
题目一（和为s的两个数字）
两个指针，分别从起始和末尾开始比较，类似于二分查找。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22class Solution {
public:
vector<int> twoSum(vector<int>& nums, int target) {
vector<int> res;
if(nums.size() <= 1)
return res;
int start = 0;
int end = nums.size()-1;
while(start < end){
if(nums[start] + nums[end] == target){
res.push_back(nums[start]);
res.push_back(nums[end]);
break;
}
else if(nums[start] + nums[end] < target)
start++;
else
end--;
}
return res;
}
};
题目二（和为s的连续正数序列）
维护一个small和big，如果当前cur_sum>target,则减去当前的small并更新small的大小。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29class Solution {
public:
vector<vector<int>> findContinuousSequence(int target) {
vector<vector<int>> res;
int small = 1;
int mid = (target + 1) >> 1;
int big = 2;
int cur_sum = small + big;
while(small < mid){
while(cur_sum > target && small < mid){
cur_sum -= small;
small++;
}
if(cur_sum == target)
res.push_back(push_res(small, big));
big++;
cur_sum += big;
}
return res;
}
vector<int> push_res(int start, int end){
vector<int> res;
for(int i=start;i<=end;i++)
res.push_back(i);
return res;
}
};
58.翻转字符串
题目一
单词内部顺序不变，翻转所有的单词顺序。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37class Solution {
public:
string reverseWords(string s) {
string ss = "";
if(s.length()==0)
return ss;
int start = 0;
int end = 0;
string s1 = reverse(s, 0, s.length()-1);
while(end < s.length()){
if(s1[start] == ' '){
start++;
end++;
}
else if(s1[end] == ' ' || end == s1.length()-1){
if(end == s1.length()-1 && s1[end] != ' ')
end += 1;
ss += reverse(s1, start, end-1) + ' ';
end++;
start = end;
}
else
end++;
}
if(ss.length() > 0)
ss[ss.length()-1] = '\0';
return ss;
}
string reverse(string s, int start, int end){
string res = "";
while(end>=start){
res += s[end--];
}
return res;
}
};
题目二（左旋字符串）
字符串的左旋转操作是把字符串前面的若干个字符转移到字符串的尾部。
根据n将字符串分为两部分，首先分别翻转这两个部分，然后将字符串整体翻转：1
2输入: s = "abcdefg", k = 2
输出: "cdefgab"
先各自翻转，得到“bagfedc”，然后翻转整个字符串，得到“cdefgab”。1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20class Solution {
public:
string reverseLeftWords(string s, int n) {
reverse(s, 0, n-1);
reverse(s, n, s.length()-1);
reverse(s, 0, s.length()-1);
return s;
}
void reverse(string &s, int start, int end){
while(start < end){
char temp = s[start];
s[start] = s[end];
s[end] = temp;
start++;
end--;
}
}
};