# 二维数组中的查找

## 源码

```public class Solution {
public boolean Find(int target, int [][] array) {
if(array.length==0 || array[0].length==0){
return false;
}

int row = 0,col = 0;
for(int i=0;i<array[0].length;i++){
if(array[0][i]<target){
col = i;
}else{
break;
}
}
for(int i=0;i<array.length;i++){
if(array[i][col]<target){
row = i;
}else{
break;
}
}
for(int i=row;i<array.length;i++){
for(int k=0;k<=col;k++){
if(array[i][k]==target){
return true;
}
}
}
return false;
}
}```

# 替换空格

## 源码

```public class Solution {
public String replaceSpace(StringBuffer str) {
int wsCnt = 0;
for(int i=0;i<str.length();i++){
if(str.charAt(i)==' '){
wsCnt++;
}
}
int oldLen = str.length();
str.setLength(wsCnt*2+str.length());
for(int i=oldLen-1;i>=0;i--){
if(str.charAt(i)!=' '){
str.setCharAt(i+wsCnt*2,str.charAt(i));
}else{
str.setCharAt(i+wsCnt*2,'0');
str.setCharAt(i+wsCnt*2-1,'2');
str.setCharAt(i+wsCnt*2-2,'%');
wsCnt--;
}
}
return str.toString();
}
}```

# 从尾到头打印链表

## 源码

```import java.util.ArrayList;
public class Solution {
ArrayList<Integer> list = new ArrayList<>();
if(listNode==null){
return list;
}
while(listNode!=null){
listNode=listNode.next;
}
return list;
}
}```

# 重建二叉树

## 源码

```/**
* Definition for binary tree
* public class TreeNode {
*     int val;
*     TreeNode left;
*     TreeNode right;
*     TreeNode(int x) { val = x; }
* }
*/
public class Solution {
public TreeNode subTree(int[] preOrder, int[] inOrder,
int preStart, int preEnd,
int inStart, int inEnd){
if(preStart>=preEnd){
return null;
}
// root val
TreeNode t = new TreeNode(preOrder[preStart]);
// find index of node value in inOrder array
int pos = 0;
for(int i=0;i<inOrder.length;i++){
if(inOrder[i]==preOrder[preStart]){
pos = i;
break;
}
}
// left and right
t.left = subTree(preOrder,inOrder,
preStart+1,preStart+1+(pos-inStart),
inStart,pos);
t.right = subTree(preOrder,inOrder,
preStart+1+(pos-inStart),preEnd,
pos+1,inEnd);
return t;
}

public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
return subTree(pre,in,0,pre.length,0,in.length);
}
}```

# 用两个栈实现队列

## 源码

```import java.util.Stack;

public class Solution {
Stack<Integer> stack1 = new Stack<Integer>();
Stack<Integer> stack2 = new Stack<Integer>();

public void push(int node) {
stack1.push(node);
}

public int pop() {
if(!stack2.isEmpty()){
return stack2.pop();
}else{
while(stack1.size()!=1){
int val = stack1.pop();
stack2.push(val);
}
return stack1.pop();
}
}
}```

# 旋转数组的最小数字

## 源码

```import java.util.ArrayList;
public class Solution {
public int minNumberInRotateArray(int [] array) {
if(array.length<=1){
return array.length;
}
for(int i=1;i<array.length;i++){
if(array[i]<array[0]){
return array[i];
}
}
return 0;
}
}```

# 斐波那契数列

## 源码

```public class Solution {
public int Fibonacci(int n) {
if(n<=1){
return n>=0?n:0;
}
int a = 0,b=1,c=1;
for(int i=2;i<=n;i++){
c = a+b;
a = b;
b = c;
}
return c;
}
}```

# 跳台阶

## 源码

```public class Solution {
public int JumpFloor(int target) {
int a=1,b=2,c=3;
if(target<=3){
return target>0?target:0;
}
for(int i=c;i<=target;i++){
c = a + b;
a = b;
b = c;
}
return c;
}
}```

# 变态跳台阶

## 源码

```public class Solution {
public int JumpFloorII(int target) {
return 1<<(target-1);
}
}```

# 矩形覆盖

## 源码

```public class Solution {
public int RectCover(int target) {
int a=1,b=2,c=3;
if(target<=3){
return target>0?target:0;
}
for(int i=c;i<=target;i++){
c = a + b;
a = b;
b = c;
}
return c;
}
}```

# 二进制中1的个数

## 源码

```class Solution {
public int NumberOf1(int n) {
int cnt = 0;
while(n!=0){
cnt++;
// 把一个整数减去1，再和原整数做与运算，会把该整数最右边一个1变成0
n = n&(n-1);
}
return cnt;
}
}```

# 数值的整数次方

## 源码

```public class Solution {
public double Power(double base, int exponent) {
boolean flag = false;
if(exponent==0 && base!=0){
return 1.0;
}
if(base==0){
return 0;
}

double res = 1.0;
for(int i=0;i<Math.abs(exponent);i++){
res *=base;
}
return exponent>0?res:1/res;
}
}```

# 调整数组顺序使奇数位于偶数前面

## 源码

```class Solution {
public:
void reOrderArray(vector<int> &array) {
int cnt = 0;
for(int i=0;i<array.size();i++){
if(array[i]%2==1){
int p = i;
while(p>cnt){
int t = array[p];
array[p]=array[p-1];
array[p-1]=t;
p--;
}
cnt++;
}
}
}
};```

# 链表中倒数第k个结点

## 源码

```/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
// 1-2-3-4
return nullptr;
}

int cnt = 0;
while(p2 && cnt<k){
p2 = p2->next;
cnt++;
}
if(cnt!=k){
return nullptr;
}

while(p2){
p1=p1->next;
p2=p2->next;
}
return p1;
}
};```

# 反转链表

## 源码

```/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
return nullptr;
}

}
}
};```

# 合并两个排序的链表

## 源码

```/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
// 1->2->3->5
// 2->3->4
return nullptr;
}

}else{
}
}else{
}
}
}
}
}

}
};```

# 树的子结构

## 源码

```/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;

public TreeNode(int val) {
this.val = val;

}

}
*/
public class Solution {
public boolean check(TreeNode a, TreeNode b){
if(b==null){
return true;
}
if(a==null){
return false;
}
if(a.val==b.val){
return check(a.left,b.left)&&check(a.right,b.right);
}
return false;
}

public boolean HasSubtree(TreeNode root1,TreeNode root2) {
if(root1 == null || root2 == null){
return false;
}
if(root1.val==root2.val){
boolean r = check(root1,root2);
if(r){
return true;
}
}

boolean res= HasSubtree(root1.left,root2);
if(res){
return true;
}
res = HasSubtree(root1.right,root2);
if(res){
return true;
}
return false;
}
}```

# 二叉树的镜像

## 源码

```/**
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;

public TreeNode(int val) {
this.val = val;
}
}
*/
public class Solution {
public void Mirror(TreeNode root) {
if(root==null){
return;
}
TreeNode a = root.left;
root.left = root.right;
root.right = a;
Mirror(root.left);
Mirror(root.right);
}
}```

# 顺时针打印矩阵

## 源码

```class Solution {
public:
vector<int> printMatrix(vector<vector<int> > matrix) {
vector<int> v;
if(matrix.size()==0||matrix[0].size()==0){
return v;
}
int i=0,j=0;
int cnt = 0;
int widthStart = 0;
int widthEnd = matrix[0].size();
int heightStart = 0;
int heightEnd = matrix.size();
while(cnt < matrix.size()*matrix[0].size()){
while(j<widthEnd){
v.push_back(matrix[i][j]);
j++;
cnt++;
}
j--;
i++;
if(i>=heightEnd){
break;
}
while(i<heightEnd){
v.push_back(matrix[i][j]);
i++;
cnt++;
}
i--;
j--;
if(j<widthStart){
break;
}
while(j>=widthStart){
v.push_back(matrix[i][j]);
j--;
cnt++;
}
j++;
i--;
if(i<heightStart){
break;
}
while(i>=heightStart+1){
v.push_back(matrix[i][j]);
i--;
cnt++;
}
i++;
j++;
widthEnd--;
widthStart++;
heightStart++;
heightEnd--;
}
return v;
}
};```

# 包含min函数的栈

## 源码

```class Solution {
public:
stack<int> s;
stack<int> aux;

void push(int value) {
s.push(value);
if(!aux.empty()){
int t = aux.top();
if(t>value){
aux.push(value);
}else{
aux.push(t);
}
}else{
aux.push(value);
}
}
void pop() {
s.pop();
aux.pop();
}
int top() {
return aux.top();
}
int min() {
return aux.top();
}
};```

# 栈的压入、弹出序列

## 源码

```class Solution {
public:
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
if(pushV.empty() || popV.empty()){
return false;
}

int start = 0;
int cnt =0;
stack<int> s;
while(cnt<popV.size()){
int p = popV[cnt];

if(!s.empty() && s.top()==p){
s.pop();
}else{
for(;start<pushV.size();start++){
s.push(pushV[start]);
if(pushV[start]==p){
start++;
break;
}
}
if(s.top()==p){
s.pop();
}else{
return false;
}
}

cnt++;
}
return true;
}
};```

# 从上往下打印二叉树

## 源码

```/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
vector<int> PrintFromTopToBottom(TreeNode* root) {
vector<int> vec;
if(root==nullptr){
return vec;
}
deque<TreeNode*> q;
q.push_back(root);
while(!q.empty()){
auto tmp = q.front();
q.pop_front();
vec.push_back(tmp->val);
if(tmp->left){
q.push_back(tmp->left);
}
if(tmp->right){
q.push_back(tmp->right);
}
}
return vec;
}
};```

# 二叉搜索树的后序遍历序列

## 源码

```class Solution {
public:
bool check(const vector<int>&seq,int start,int end){
if(start>=end){
return true;
}
int root = seq[end-1];
int right = start;
for(;right<end;right++){
if(seq[right]>root){
break;
}
}
for(int t=right;t<end;t++){
if(seq[t]<root){
return false;
}
}

return check(seq,start,right-1)&&check(seq,right,end-1);
}

bool VerifySquenceOfBST(vector<int> sequence) {
if(sequence.size()==0){
return false;
}
if(sequence.size()==1){
return true;
}

return check(sequence,0,sequence.size());
}
};```

# 二叉树中和为某一值的路径

## 源码

```/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
vector<vector<int>> paths;
vector<int> temp;

void dfs(TreeNode* root, int target){
if(target-root->val==0 && root->left==nullptr && root->right==nullptr){
temp.push_back(root->val);
paths.push_back(temp);
temp.pop_back();
return;
}

if(root->left){
temp.push_back(root->val);
dfs(root->left,target- root->val);
temp.pop_back();
}
if(root->right){
temp.push_back(root->val);
dfs(root->right,target- root->val);
temp.pop_back();
}
}

vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
if(root==nullptr){
return paths;
}
dfs(root,expectNumber);
return paths;
}
};```

# 复杂链表的复制

## 源码

```/*
struct RandomListNode {
int label;
struct RandomListNode *next, *random;
RandomListNode(int x) :
label(x), next(NULL), random(NULL) {
}
};
*/
class Solution {
public:
}
return copied;
}
int i=0;
do{
return i;
}
i++;
return i;
}
int s=0;
while(s<i){
s++;
}
}

return nullptr;
}
RandomListNode* t = copied;
while(t){
t->random = getNode(copied,pos);
t=t->next;
}

return copied;
}
};```

# 二叉搜索树与双向链表

## 源码

```/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
void listify(TreeNode* cur, TreeNode*& pre){
if(cur==nullptr){
return;
}
listify(cur->left,pre);
cur->left = pre;
if(pre){
pre->right = cur;
}
pre = cur;
listify(cur->right,pre);
}
TreeNode* Convert(TreeNode* pRootOfTree){
TreeNode* r = pRootOfTree;
if(r!=nullptr){
TreeNode* pre = nullptr;
listify(r,pre);
while(r->left){
r = r->left;
}
return r;
}
return r;
}
};```

# 字符串的排列

## 源码

```class Solution {
public:
set<string> all;

void dfs(string str,string a,vector<char> chars){
if(a.length()==str.length()){
all.insert(a);
return;
}
for(int i=0;i<chars.size();i++){
if(chars[i]!='\0'){
char c = chars[i];
chars[i]='\0';
dfs(str,a+c,chars);
chars[i] = c;
}
}
}

vector<string> Permutation(string str) {
if(str.length()==0){
return vector<string>();
}
vector<char> c;
for(char val:str){
c.push_back(val);
}
dfs(str,"",c);
vector<string> res;
for(const string &s:all){
res.push_back(s);
}
return res;
}
};```

# 数组中出现次数超过一半的数字

## 源码

```class Solution {
public:
int partition(vector<int> & arr, int left, int right){
int i = left;
int j = right;
int pivot = arr[left];
while(i<j){
while(i<j && arr[j]>pivot) j--;
if(i<j) arr[i++] = arr[j];
while(i<j && arr[i]<pivot) i++;
if(i<j) arr[j--] = arr[i];
}
arr[i] = pivot;
return i;
}

int MoreThanHalfNum_Solution(vector<int> numbers) {
int start=0,end = numbers.size()-1;
int index = partition(numbers,0,end);
while(index!=numbers.size()/2){
if(index>numbers.size()/2){
end = index -1;
index = partition(numbers,start,end);
}else{
start = index+1;
index = partition(numbers,start,end);
}
}
int cnt = 0;
for(int i=0;i<numbers.size();i++){
if(numbers[i]==numbers[index]){
cnt++;
}
}
return cnt>index?numbers[index]:0;
}
};```

# 最小的K个数

## 描述

```class Solution {
public:
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
if(input.size()==0||k<=0 || input.size()<k){
return vector<int>();
}
vector<int> v;
make_heap(input.begin(),input.end(),greater<int>());
for(int i=0;i<k;i++){
pop_heap(input.begin(),input.end(),greater<int>());
v.push_back(input[input.size()-1]);
input.pop_back();
}
return v;
}
};```

# 连续子数组的最大和

## 描述

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

```class Solution {
public:
int dp[1000]={0};

int FindGreatestSumOfSubArray(vector<int> array) {
if(array.size()==0){
return 0;
}
for(int i=0;i<array.size();i++){
dp[i+1] = dp[i]>0?array[i]+dp[i]:array[i];
}
int m=INT_MIN;
for(int i=1;i<=array.size();i++){
if(dp[i]>m){
m=dp[i];
}
}
return m;
}
};```

# 把数组排成最小的数

## 描述

```class Solution {
public:
static int cmp(int a,int b){
string str1,str2;
str1+=to_string(a);
str1+=to_string(b);
str2+=to_string(b);
str2+=to_string(a);
return str1<str2;
}
string PrintMinNumber(vector<int> numbers) {
sort(numbers.begin(),numbers.end(),cmp);
string result;
for(int i:numbers){
result+=to_string(i);
}
return result;
}
};```

# 丑数

## 源码

```class Solution {
public:
int findMin(int a,int b,int c){
int t = (a>b?b:a);
return (t>c?c:t);
}

int GetUglyNumber_Solution(int index){
if(index<=1){
return index;
}
int p2=0,p3=0,p5=0;
vector<int> v;
v.push_back(1);
while(v.size()<index){
int min = findMin(v[p2]*2,v[p3]*3,v[p5]*5);
if(v[p2]*2==min)p2++;
if(v[p3]*3==min)p3++;
if(v[p5]*5==min)p5++;
v.push_back(min);
}
return v[v.size()-1];
}
};```

# 第一个只出现一次的字符

## 源码

```class Solution {
public:
int FirstNotRepeatingChar(string str) {
map<char,int> m;
for(int i=0;i<str.length();i++){
m[str[i]]++;
}
for(int i=0;i<str.length();i++){
if(m[str[i]]==1){
return i;
}
}
return -1;
}
};```

# 数组中的逆序对

## 源码

```class Solution {
public:
int cnt;

void divide(vector<int> &arr,int start, int end){
if(start>=end){
return;
}
int mid = (start+end)>>1;
divide(arr,start,mid);
divide(arr,mid+1,end);
merge(arr,start,mid,end);
}

void merge(vector<int> &arr,int start, int mid, int end){
int* aux = new int[end-start+1];

int i=start,j=mid+1,k=0;
while(i<=mid && j<= end){
if(arr[i]<=arr[j]){
aux[k++]=arr[i++];
}else{
aux[k++]=arr[j++];
cnt += (mid-i+1);
cnt %= 1000000007;
}
}

while(i<=mid){
aux[k++]=arr[i++];
}
while(j<=end){
aux[k++]=arr[j++];
}
for(int i=0;i<end-start+1;i++){
arr[start+i]=aux[i];
}
delete[]aux;
}

int InversePairs(vector<int> data) {
cnt=0;
if(data.size()==0){
return cnt;
}
divide(data,0,data.size()-1);
return cnt;
}
};```

# 两个链表的第一个公共结点

## 源码

```/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};*/
class Solution {
public:
return nullptr;
}
stack<ListNode*> a,b;
while(t1){
a.push(t1);
t1=t1->next;
}
while(t2){
b.push(t2);
t2=t2->next;
}
while(!a.empty()&&!b.empty()){
t1=a.top();
t2=b.top();
if(t1!=t2){
return t1->next;
}
a.pop();
b.pop();
}
if(a.empty()&&!b.empty()){
return b.top()->next;
}else if(b.empty()&&!a.empty()){
return a.top()->next;
}else{
}
}
};```

# 数字在排序数组中出现的次数

## 源码

```class Solution {
public:
int GetNumberOfK(vector<int> data ,int k) {
auto pos = find(data.begin(),data.end(),k);
if(pos==data.end()){
return 0;
}
int cnt=0;
while(true){
if(*pos==k){
cnt++;
}else{
break;
}
pos++;
}
return cnt;
}
};```

# 二叉树的深度

## 源码

```/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};*/
class Solution {
public:
int max = 0;

void dfs(TreeNode* node,int depth){
if(!node){
if(depth>max){
max = depth;
}
return;
}
dfs(node->left,depth+1);
dfs(node->right,depth+1);
}

int TreeDepth(TreeNode* pRoot){
if(pRoot==nullptr){
return 0;
}
dfs(pRoot,0);
return max;

}
};```

# 平衡二叉树

## 源码

```class Solution {
public:
bool isBalanced=true;

int dfs(TreeNode* node){
if(!node){
return 0;
}
int a = dfs(node->left);
int b = dfs(node->right);
if(abs(a-b)>1){
isBalanced=false;
}
return a>b?a+1:b+1;
}
bool IsBalanced_Solution(TreeNode* pRoot) {
if(pRoot==nullptr){
return true;
}
dfs(pRoot);
return isBalanced;
}
};```

# 数组中只出现一次的数字

## 源码

```class Solution {
public:
void FindNumsAppearOnce(vector<int> data,int* num1,int *num2) {
map<int,int> m;
for(int i:data){
m[i]++;
}

bool first = true;
for(auto v:m){
if(v.second==1){
if(first){
*num1 = v.first;
first=false;
}else{
*num2=v.first;
}
}
}
}
};```

# 和为S的连续正数序列

## 源码

```class Solution {
public:
int calcSum(int start, int end){
return (start+end)*(end-start+1)/2;
}
vector<vector<int> > FindContinuousSequence(int sum) {
vector<vector<int>> res;
int start = 1;
int end = 2;
while(start<end){
if(calcSum(start,end)<sum){
end++;
}else if(calcSum(start,end)>sum){
start++;
}else{
vector<int> v;
for(int i=start;i<=end;i++){
v.push_back(i);
}
res.push_back(v);
start++;    // or end++;
}
}
return res;
}
};```

# 和为S的两个数字

## 源码

```class Solution {
public:
vector<int> FindNumbersWithSum(vector<int> array,int sum) {
int i=0;
for(;i<array.size();i++){
if(array[i]>=sum){
break;
}
}
vector<int> v;
int start  = 0;
int end = (i==array.size())?i-1:i;
while(start<end){
if(array[start]+array[end]==sum){
v.push_back(array[start]);
v.push_back(array[end]);
return v;
}else if(array[start]+array[end]>sum){
end--;
}else if(array[start]+array[end]<sum){
start++;
}
}
return v;
}
};```

# 左旋转字符串

## 源码

```class Solution {
public:
string LeftRotateString(string str, int n) {
string s;
for(int i=n;i<str.length();i++){
s+=str[i];
}
for(int i=0;i<n;i++){
s+=str[i];
}
return s;
}
};```

# 翻转单词顺序列

## 源码

```class Solution {
public:
void bitwise_reverse(string &str){
int cnt=0;
int last = 0;
while(cnt<=str.length()){
if(cnt==str.length() || str[cnt]==' '){
int left=last,right=cnt-1;
while(left<right){
char tmp = str[left];
str[left] = str[right];
str[right] = tmp;
left++;
right--;
}
last = cnt+1;
}
cnt++;
}
}

string ReverseSentence(string str) {
bitwise_reverse(str);
for(int i=0,j=str.length()-1;i<j;i++,j--){
char tmp = str[i];
str[i]=str[j];
str[j]=tmp;
}
return str;
}
};```

# 孩子们的游戏(圆圈中最后剩下的数)

## 源码

```class Solution {
public:
// https://blog.csdn.net/byn12345/article/details/79487253
int LastRemaining_Solution(int n, int m){
if(n==0){
return -1;
}

int cur=0;
for(int i=2;i<=n;i++){
cur = (cur+m)%i;
}
return cur;
}
};```

# 求1+2+3+...+n

## 源码

```class Solution {
public:
int Sum_Solution(int n) {
return (int)(n+std::pow(n,2))>>1;
}
};```

# 不用加减乘除做加法

## 源码

```class Solution {
public:
return std::plus<>{}(num1,num2);
}
};```

# 把字符串转换成整数

## 源码

```class Solution {
public:
int StrToInt(string str) {
if(str.length()==0){
return 0;
}

int start = 0;
if(str[0]=='+'|| str[0]=='-'){
start=1;
}
int res = 0;
for(int i=start;i<str.length();i++){
if(str[i]<'0'||str[i]>'9'){
return false;
}else{
res = res*10 + (str[i]-'0');
}
}
return str[0]=='-'?-res:res;
}
};```

# 数组中重复的数字

## 源码

```class Solution {
public:
// Parameters:
//        numbers:     an array of integers
//        length:      the length of array numbers
//        duplication: (Output) the duplicated number in the array number
// Return value:       true if the input is valid, and there are some duplications in the array number
//                     otherwise false
bool duplicate(int numbers[], int length, int* duplication) {
if(numbers==nullptr||length<=0){
return false;
}
for(int i=0;i<length;i++){
if(numbers[i]<0|| numbers[i]>length-1){
return false;
}
}

for(int i=0;i<length;i++){
while(numbers[i]!=i){
if(numbers[i]!=numbers[numbers[i]]){
std::swap(numbers[i],numbers[numbers[i]]);
}else{
*duplication=numbers[i];
return true;
}

}
}
return false;
}
};```

# 构建乘积数组

## 源码

```class Solution {
public:
vector<int> multiply(const vector<int>& A) {
vector<int> b(A.size());
if(A.size()==0){
return b;
}
b[0]=1;
for(int i=1;i<A.size();i++){
b[i] = b[i-1]*A[i-1];
}
int t = 1;
for(int i=A.size()-2;i>=0;i--){
t = t*A[i+1];
b[i] *= t;
}
return b;
}
};```

# 正则表达式匹配

## 源码

```class Solution {
public:
bool matchImpl(char* str, char* pattern){
if(*str!='\0' && *pattern=='\0'){
return false;
}
if(*pattern=='\0' && *str=='\0'){
return true;
}

// 如果是重复匹配
if(*(pattern+1)=='*'){
if(*str==*pattern || *pattern=='.' && *str!='\0'){
return matchImpl(str+1,pattern+2)||
matchImpl(str+1,pattern)||
matchImpl(str,pattern+2);
}else{
return matchImpl(str,pattern+2);
}
}
// 如果是任意匹配
if(*pattern=='.'&&*str!='\0'){
return matchImpl(str+1,pattern+1);
}
// 如果是普通字符和数字
if(*pattern==*str){
return matchImpl(str+1,pattern+1);
} else{
return false;
}
}

bool match(char* str, char* pattern){
if(str==nullptr||pattern==nullptr)
return false;
return matchImpl(str,pattern);
}
};```

# 表示数值的字符串

## 源码

```class Solution {
public:
bool modeDecimal(char* string){
while(*string){
if(*string=='e'||*string=='E'){
string++;
return modeScientific(string);
}

if(*string<'0'||*string>'9' ){
return false;
}
string++;
}
return true;
}

bool modeScientific(char *string){
// e后部分
if(*string=='+'||*string=='-'){
string++;
}
// e后至少一个数
if(*string=='\0'){
return false;
}
while(*string){
if(*string<'0'||*string>'9' ){
return false;
}
string++;
}
return true;
}
bool isNumeric(char* string){
if(string==nullptr){
return false;
}
bool isDigit = true;
if(*string=='+'||*string=='-'){
string++;
}
// 整数部分
while(*string){
if(*string=='.'){
string++;
return modeDecimal(string);
}

if(*string=='e'||*string=='E'){
string++;
return modeScientific(string);
}

if(*string<'0'||*string>'9'){
return false;
}
string++;
}
return true;
}

};```

# 字符流中第一个不重复的字符

## 源码

```class Solution
{
public:
string sub;
map<char,int> m;

//Insert one char from stringstream
void Insert(char ch){
m[ch]++;
sub+=ch;
}
//return the first appearence once char in current stringstream
char FirstAppearingOnce(){
for(int i=0;i<sub.length();i++){
if(m[sub[i]]==1){
return sub[i];
}
}
return '#';
}

};```

# 链表中环的入口结点

## 源码

```/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
ListNode* fast = slow->next;

while(fast!=nullptr && slow!=nullptr){
if(fast==slow){
return fast;
}
slow = slow->next;
fast  =fast ->next;
if(fast!=nullptr){
fast = fast->next;
}else{
return nullptr;
}
}
return nullptr;
}
// 两个节点无法组成换
return nullptr;
}
// 确认有环
if(!join){
return nullptr;
}
// 找到环的节点数
int cnt = 1;
ListNode* circleStart = join->next;
while(circleStart!=join){
circleStart=circleStart->next;
cnt++;
}

// 找到入口
for(int i=0;i<cnt;i++){
fast=fast->next;
}
while(slow!=fast){
slow=slow->next;
fast=fast->next;
}
return slow;
}
};```

# 删除链表中重复的结点

## 源码

```/*
struct ListNode {
int val;
struct ListNode *next;
ListNode(int x) :
val(x), next(NULL) {
}
};
*/
class Solution {
public:
return true;
}
return false;
}

ListNode* duplicatedTail = nullptr;
// 删除重复序列
while(true){
if(current->next &&
current->val==current->next->val){
ListNode* tmp = current;
current = current->next;
delete tmp;
continue;
}
break;
}
duplicatedTail = current->next;
delete current;

return duplicatedTail;
}

return nullptr;
}

// 如果发现有重复的元素序列
// 删除重复序列

// 调整链表的链
// 注意这里用conitnue而不是继续是因为有可能由于两个连续
// 的重复序列： 1->2->3->3->4->4->5
continue;
}
}
}
};```

# 二叉树的下一个结点

## 源码

```/*
int val;

this.val = val;
}
}
*/
public class Solution {
{
if(pNode==null){
return null;
}

if(pNode.right!=null){
while(temp.left!=null && temp.right!=null){
temp = temp.left;
}
return temp;
}else if(pNode.right ==null){
if(pNode.next!=null){
// 如果父节点不为空，且当前节点是父节点的左节点
if(pNode.next.left==pNode){
return pNode.next;
}else{
// 如果父节点不为空，且当前节点是父节点的右节点
while(t.next!=null && t.next.left!=t){
t=t.next;
}
return t.next;
}
}else{
return null;
}
}else{
return null;
}
}
}```

# 对称的二叉树

## 源码

```/*
public class TreeNode {
int val = 0;
TreeNode left = null;
TreeNode right = null;

public TreeNode(int val) {
this.val = val;

}

}
*/
public class Solution {
boolean check(TreeNode a,TreeNode b){
if(a==null||b==null)
return a==b?true:false;

if(a.val==b.val){
return check(a.left,b.right)&&check(a.right,b.left);
}else{
return false;
}

}

boolean isSymmetrical(TreeNode pRoot){
if(pRoot==null){
return true;
}
return check(pRoot.left,pRoot.right);
}
}```

# 按之字形顺序打印二叉树

## 源码

```/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int> > res;
if(pRoot==nullptr){
return res;
}

stack<TreeNode*> sk1,sk2;
sk1.push(pRoot);
while(!sk1.empty() || !sk2.empty()){
vector<int> v;

if(!sk1.empty()){
while(!sk1.empty()){
TreeNode *t = sk1.top();
v.push_back(t->val);
sk1.pop();
if(t->left)sk2.push(t->left);
if(t->right)sk2.push(t->right);
}
}else{
while(!sk2.empty()){
TreeNode*t = sk2.top();
v.push_back(t->val);
sk2.pop();
if(t->right)sk1.push(t->right);
if(t->left)sk1.push(t->left);
}
}

res.push_back(v);
}
return res;
}

};```

# 把二叉树打印成多行

## 源码

```/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
vector<vector<int> > Print(TreeNode* pRoot) {
vector<vector<int>> vec;
if(pRoot==nullptr){
return vec;
}
deque<TreeNode*> q;
q.push_back(pRoot);
q.push_back(nullptr);
while(!q.empty() && q.front()!=nullptr){
auto r = q.front();
q.pop_front();
vector<int> v;
while(r!=nullptr){
v.push_back(r->val);
if(r->left){
q.push_back(r->left);
}
if(r->right){
q.push_back(r->right);
}
r=q.front();
q.pop_front();
}
vec.push_back(v);
q.push_back(nullptr);;
}
return vec;
}

};```

# 二叉搜索树的第k个结点

## 源码

```/*
struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
TreeNode(int x) :
val(x), left(NULL), right(NULL) {
}
};
*/
class Solution {
public:
int cnt = 0;
TreeNode* result=nullptr;

void traverse(TreeNode* t,int target){
if(t){
traverse(t->left,target);
cnt++;
if(cnt==target){
result = t;
return;
}
traverse(t->right,target);
}
}

TreeNode* KthNode(TreeNode* pRoot, int k){
if(k==0||pRoot==nullptr){
return nullptr;
}
traverse(pRoot,k);
return result;
}

};```

# 数据流中的中位数

## 源码

```class Solution {
public:
priority_queue<int, vector<int>, less<int> > max;
priority_queue<int, vector<int>, greater<int> > min;
int cnt=0;

void Insert(int num){
if(cnt%2){
max.push(num);
min.push(max.top());
max.pop();
}else{
min.push(num);
max.push(min.top());
min.pop();
}
cnt++;
}

double GetMedian(){
return cnt%2!=0?max.top():(max.top()+min.top())/2.0;
}

};```

# 滑动窗口的最大值

## 源码

```class Solution {
public:
vector<int> maxInWindows(const vector<int>& num, unsigned int size){
vector<int> vec;
if(num.size()<size || size==0){
return vec;
}
deque<int> q;
for(int i=0;i<num.size();i++){
while(!q.empty() && num[q.back()]<=num[i]){
q.pop_back();
}
while(!q.empty() && i-q.front()+1>size){
q.pop_front();
}
q.push_back(i);
if(i+1>=size){
vec.push_back(num[q.front()]);
}
}
return vec;
}
};```

# 矩阵中的路径

## 源码

```class Solution {
public:
bool correctPath(char* matrix, int rows, int cols, char* str,
int i, int k,int *visited, int step){
if(i<0 || k<0 || i>=rows || k>= cols){
return false;
}
if(visited[i*cols+k] ||
str[step]!=matrix[i*cols+k]){
return false;
}

if(step == strlen(str)-1){
return true;
}

visited[i*cols+k] = true;
if(correctPath(matrix,rows,cols,str,i,k+1,visited,step+1)||
correctPath(matrix,rows,cols,str,i,k-1,visited,step+1)||
correctPath(matrix,rows,cols,str,i-1,k,visited,step+1)||
correctPath(matrix,rows,cols,str,i+1,k,visited,step+1)){
return true;
}
visited[i*cols+k]=false;

return false;
}

bool hasPath(char* matrix, int rows, int cols, char* str){
int * visited = new int[rows*cols];
memset(visited,0,sizeof(int)*rows*cols);

for(int i=0;i<rows;i++){
for(int k=0;k<cols;k++){
if(correctPath(matrix,rows,cols,str,i,k,visited,0)){
delete visited;
return true;
}
}
}

delete visited;
return false;
}

};```

# 机器人的运动范围

## 源码

```int visited[100][100];

class Solution {
public:
int sumDigit(int num){
int res = 0;
while(num){
res += (num%10);
num /= 10;
}
return res;
}

int dfs(int rows, int cols, int i,int k,int threshold){
if(i<0 || k <0 || i>=rows || k>=cols || visited[i][k]){
return 0;
}
if(sumDigit(i)+sumDigit(k)>threshold){
return 0;
}

visited[i][k]=true;
int a = 1 + dfs(rows,cols,i,k+1,threshold)
+ dfs(rows,cols,i,k-1,threshold)
+ dfs(rows,cols,i-1,k,threshold)
+ dfs(rows,cols,i+1,k,threshold);
return a;
}

int movingCount(int threshold, int rows, int cols){
int max=0;
memset(visited,0,10000*sizeof(int));

return dfs(rows,cols,0,0,threshold);
}
};```

75 篇文章12 人订阅

0 条评论