二维数组中的查找
选右上角出发，循环找出。
bool Find(int target, vector<vector<int> > array) {
int row = array.size();
int col = array[0].size();
int i = 0;
int j = col -1;
while(i<row&&j>=0){
if(target==array[i][j]) return true;
if(target>array[i][j]) i++;
else j--;
}
return false;
}
替换空格
弄转换后的数组，然后重新赋值。
void replaceSpace(char *str,int length) {
vector<char> result;
char *p=str;
int cou =0;
while(cou<=length){
if(*p!=' ') result.push_back(*p);
else {
result.push_back('%');
result.push_back('2');
result.push_back('0');
}
p++;
cou++;
}
for(char s : result){
*str = s;
str++;
}
}
算出调整后的位置，然后从后面赋值
void replaceSpace(char *str,int length) {
int num = 0 ;
for(int i =0;i<length;i++){
if(str[i]==' '){num++;}
}
int nowl = length -1+num*2;
for(int i = length -1 ; i >=0; i--){
if(str[i] !=' '){
str[nowl--] = str[i];
}
else{
str[nowl--] = '0';
str[nowl--] = '2';
str[nowl--] = '%';
num--;
}
}
}
从尾到头打印链表
我的：
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> temp;
vector<int> result;
if(head==NULL) return result;
while(head!=NULL){
temp.push_back(head->val);
head=head->next;
}
int length = temp.size();
for(int i = length-1 ;i>=0;i--){
result.push_back(temp[i]);
}
return result;
}
剑指上的：
使用栈，或者递归（也是一种栈）
//栈
vector<int> printListFromTailToHead(ListNode* head) {
vector<int> result;
if(head==NULL) return result;
stack<int> temp;
while(head!=NULL){
temp.push(head->val);
head=head->next;
}
while(!temp.empty()){
result.push_back(temp.top());
temp.pop();
}
return result;
}
//递归
vector<int> result;
vector<int> printListFromTailToHead(ListNode* head) {
if(head==NULL) return result;
else{
if(head->next!=NULL) printListFromTailToHead(head->next);
result.push_back(head->val);
}
return result;
}
重建二叉树
递归左右子树，返回根，我的方法忘了。结果1：注意vector复制的区间是左闭右开的，而且end（）指向的时最后一个元素的后面一个虚拟元素，所以你想把*a = [0,1,2,3]复制给vector的时候得vector b(a,a+4)而不是vector b(a,a+4-1)。
过几天重新写。
我的：
//方法1：
TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> vin) {
if(pre.size()==0) return NULL;
TreeNode* root = new TreeNode(pre[0]);
int flag = 0;
for(int i = 0;i<vin.size();i++){
if(vin[i]==pre[0]){
flag = i;
break;
}
}
vector<int> lvin(vin.begin(),vin.begin()+flag); //超出的size是0
vector<int> lpre(pre.begin()+1, pre.begin()+flag+1);
vector<int> rpre(pre.begin()+flag+1, pre.end());
vector<int> rvin(vin.begin()+flag+1, vin.end());
root->left = reConstructBinaryTree(lpre, lvin);
root->right = reConstructBinaryTree(rpre, rvin);
return root;
}
//方法2：
struct TreeNode* reConstructBinaryTree(vector<int> pre,vector<int> in) {
int inlen=in.size();
if(inlen==0)
return NULL;
vector<int> left_pre,right_pre,left_in,right_in;
//创建根节点，根节点肯定是前序遍历的第一个数
TreeNode* head=new TreeNode(pre[0]);
//找到中序遍历根节点所在位置,存放于变量gen中
int gen=0;
for(int i=0;i<inlen;i++)
{
if (in[i]==pre[0])
{
gen=i;
break;
}
}
//对于中序遍历，根节点左边的节点位于二叉树的左边，根节点右边的节点位于二叉树的右边
//利用上述这点，对二叉树节点进行归并
for(int i=0;i<gen;i++)
{
left_in.push_back(in[i]);
left_pre.push_back(pre[i+1]);//前序第一个为根节点
}
for(int i=gen+1;i<inlen;i++)
{
right_in.push_back(in[i]);
right_pre.push_back(pre[i]);
}
//和shell排序的思想类似，取出前序和中序遍历根节点左边和右边的子树
//递归，再对其进行上述所有步骤，即再区分子树的左、右子子数，直到叶节点
head->left=reConstructBinaryTree(left_pre,left_in);
head->right=reConstructBinaryTree(right_pre,right_in);
return head;
}
//方法3：
public TreeNode reConstructBinaryTree(int [] pre,int [] in) {
return reConBTree(pre,0,pre.length-1,in,0,in.length-1);
}
public TreeNode reConBTree(int [] pre,int preleft,int preright,int [] in,int inleft,int inright){
if(preleft > preright || inleft> inright)//当到达边界条件时候返回null
return null;
//新建一个TreeNode
TreeNode root = new TreeNode(pre[preleft]);
//对中序数组进行输入边界的遍历
for(int i = inleft; i<= inright; i++){
if(pre[preleft] == in[i]){
//重构左子树，注意边界条件
root.left = reConBTree(pre,preleft+1,preleft+i-inleft,in,inleft,i-1);
//重构右子树，注意边界条件
root.right = reConBTree(pre,preleft+i+1-inleft,preright,in,i+1,inright);
}
}
return root;
}
剑指：
用两个栈实现队列
我的
void push(int node) {
stack1.push(node);
}
int pop() {
int temp;
if(stack1.empty()&&stack2.empty()) return temp;
if(stack2.empty()){
while(!stack1.empty()){
stack2.push(stack1.top());
stack1.pop();
}
}
temp = stack2.top();
stack2.pop();
return temp;
}
注意pop的栈没空的时候不能加入新数据，会覆盖掉。
剑指的方法一样的
旋转数组的最小数字
我的O（N）不行
//方法1：
int minNumberInRotateArray(vector<int> rotateArray) {
if(rotateArray.size()==0) return 0;
int temp = INT_MAX;
for(int i : rotateArray){
temp = min(temp,i);
}
return temp;
}
//方法2：
int minNumberInRotateArray(vector<int> rotateArray) {
if(rotateArray.size()==0) return 0;
for(int i =0;i<rotateArray.size()-1;i++){
if(rotateArray[i]>rotateArray[i+1]){
return rotateArray[i+1];
}
}
return rotateArray[0];
}
剑指的 二分查找：
int todo(vector<int> rotateArray){
for(int i = 0; i <rotateArray.size()-1;i++){
if(rotateArray[i+1]-rotateArray[i]<0){
return rotateArray[i+1];
}
}
return rotateArray[0];
}
int minNumberInRotateArray(vector<int> rotateArray) {
if(rotateArray.size()==0) return 0;
int left = 0;
int right = rotateArray.size()-1;
while(rotateArray[left]>=rotateArray[right]){
int mid = (right-left)/2+left;
if(rotateArray[left]==rotateArray[mid]&&rotateArray[right]==rotateArray[mid]){
return todo(rotateArray);
}
if(rotateArray[left]<=rotateArray[mid]){
left = mid;
}
if(rotateArray[right]>=rotateArray[mid]){
right = mid;
}
if(right-left<=1){
return rotateArray[right];
}
}
return rotateArray[left];
}
斐波那契数列
F(1)=1，F(2)=1, F(n)=F(n-1)+F(n-2)（n>=3，n∈N*）
我的:
//方法1：
int Fibonacci(int n) {
if(n==1) return 1;
if(n==2) return 1;
return Fibonacci(n-1)+Fibonacci(n-2);
}
//方法2：
int Fibonacci(int n) {
vector<int> result={0,1};
if(n<=1) return result[n];
for(int i = 0;i<n-1;i++){
result.push_back(result[i]+result[i+1]);
}
return result[result.size()-1];
}
剑指：
跟我方法2一样
讨论改进版：
int Fibonacci(int n) {
int first = 0;
int second = 1;
int result = n;
for(int i = 2; i<=n; i++){
result = first + second;
first = second;
second = result;
}
return result;
}
跳台阶
我的：
//方法1： 时间太大
void todo(int now,int &sum) {
if(now == 0)
{
sum++;
return ;
}
if(now<0) return;
todo(now-1,sum);
todo(now-2,sum);
}
int jumpFloor(int number) {
int sum = 0;
todo(number, sum);
return sum ;
}
//方法2：上面的改进版，时间大
int jumpFloor(int number) {
if(number==1) return 1;
if(number==2) return 2;
int sum = 0;
sum = jumpFloor(number-1);
if(number-2>0) sum +=jumpFloor(number-2);
return sum ;
}
//方法3：分析规律，跟上面的一样
int jumpFloor(int number) {
int first = 1;
int second = 2;
int result = number;
for(int i = 2; i<number; i++){
result = first + second;
first = second;
second = result;
}
return result;
}
//方法4：
剑指：斐波那契数列
变态跳台阶
我的：
//方法1：
int jumpFloorII(int number) {
int sum = 1;
for(int i = 1;i<number;i++){
sum*=2;
}
return sum ;
}
//方法2：
int jumpFloorII(int number) {
if(number == 0) return 1;
int sum = 0;
for(int i = 1;i<=number;i++){
sum+=jumpFloorII(number-i);
}
return sum ;
}
//方法3：
int jumpFloorII(int number) {
if(number <= 1) return number;
int sum = 0;
sum = 2*jumpFloorII(number-1);
return sum ;
}
剑指：方法1
矩形覆盖
我的：
n台阶，跳1或者2一样
int rectCover(int number) {
if(number<3) return number;
int f = 1;
int s = 1;
int result = 2;
for(int i = 1;i<number-1;i++){
s = result;
result = f+result;
f = s;
}
return result;
}
剑指：斐波那契数列
二进制中1的个数
我的：
//方法1：
int NumberOf1(int n) {
int num = 0;
if(n<0) {
num++;
n=n&0x7FFFFFFF;
}
while(n!=0){
if(n%2==1) num++;
n=n/2;
}
return num;
}
//方法2：
int NumberOf1(int n) {
int num = 0;
if(n<0) {
num++;
n=n&0x7FFFFFFF;
}
while(n!=0){
if(n&1) num++;
n=n>>1;
}
return num;
}
剑指：
int NumberOf1(int n) {
int num = 0;
unsign int flag = 1；
while(flag){
if(n&flag){
num++;
}
flag = flag <<1;
}
return num;
}
//--------------------最优解----------------------------
public static int NumberOf1(int n) {
int count = 0;
while (n != 0) {
++count;
n = (n - 1) & n;
}
return count;
}
数值的整数次方
我的：
//方法1：
double Power(double base, int exponent) {
int temp = abs(exponent);
if(exponent == 0) return 1;
double result = base;
for(int i = 1 ;i<temp;i++){
result*=base;
}
return result=exponent>0?result:1/result;
}
剑指：
image.png
/*剑指书中细节：
*1.当底数为0且指数<0时
*会出现对0求倒数的情况，需进行错误处理，设置一个全局变量；
*2.判断底数是否等于0
*由于base为double型，不能直接用==判断
*3.优化求幂函数
*当n为偶数，a^n =（a^n/2）*（a^n/2）
*当n为奇数，a^n = a^[(n-1)/2] * a^[(n-1)/2] * a
*时间复杂度O(logn)
*/
double Power(double base, int exponent) {
int temp = abs(exponent);
if(exponent == 0) return 1;
if(exponent == 1) return base;
double result = Power(base, temp>>1);
result*=result;
if(temp&1==1)
result*=base;
return result=exponent>0?result:1/result;
}
调整数组顺序使奇数位于偶数前面
我的：
//方法1：
void reOrderArray(vector<int> &array) {
int le = array.size();
if(le == 0) return;
vector<int> even;
vector<int> odd;
for(int i = 0;i<le;i++){
if(array[i]&1==1) odd.push_back(array[i]);
else even.push_back(array[i]);
}
int even_length = even.size();
int odd_length = odd.size();
for(int i = 0;i<odd.size();i++){
array[i] = odd[i];
}
for(int i = odd.size();i<le;i++){
array[i] = even[i-odd_length];
}
}
//方法2：冒泡
void reOrderArray(vector<int> &array) {
int le = array.size();
if(le == 0) return;
for(int i = 0;i<le-1;i++){
for(int j = 0;j<le-1-i;j++){
if((array[j]%2==0)&&(array[j+1]%2==1)){
int temp = array[j];
array[j] = array[j+1];
array[j+1] = temp;
}
}
}
}
为什么任何数&1==0不会返回1？？？
因为&的优先级没有==高需要（n&1）==0括号起来。
剑指：双指针，前后遍历双单交换，没保证顺序没变。
链表中倒数第k个结点
我的：
//方法1：
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
ListNode* pre = pListHead;
ListNode* result = pListHead;
if(k<=0||pListHead==NULL) return NULL;
int temp = k-1;
int le = 1;
while(pre->next!=NULL){
pre=pre->next;
le++;
}
if(k>le) return NULL;
pre = pListHead;
while(temp>0){
if(pre == NULL) return NULL;
pre=pre->next;
temp--;
}
while(pre->next!=NULL){
pre=pre->next;
result = result->next;
}
return result;
}
//方法2：
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
ListNode* pre = pListHead;
ListNode* result = pListHead;
if(k<=0||pListHead==NULL) return NULL;
int temp = k-1;
int le = 1;
while(temp>0){
if(pre->next == NULL&&temp>0) return NULL;
pre=pre->next;
temp--;
}
while(pre->next!=NULL){
pre=pre->next;
result = result->next;
}
return result;
}
剑指：
ListNode* FindKthToTail(ListNode* pListHead, unsigned int k) {
if(k<=0||pListHead==NULL) return NULL;
ListNode* pre = pListHead;
ListNode* result = pListHead;
for(int i = 0 ;i<k-1;i++){
if(pre->next != NULL) pre=pre->next;
else return NULL;
}
while(pre->next!=NULL){
pre=pre->next;
result = result->next;
}
return result;
}
PS：指针问题，一个指针遍历不能解决问题的时候，两个指针，然后一个走快点，或者它先走若干步。
反转链表
我的：
//方法1：
ListNode* ReverseList(ListNode* pHead) {
if(pHead==NULL||pHead->next==NULL){
return pHead;
}
vector<ListNode*> temp;
while(pHead!=NULL){
temp.push_back(pHead);
pHead = pHead->next;
}
for(int i = temp.size()-1;i>0;i--){
temp[i]->next = temp[i-1];
}
temp[0]->next=NULL;
return temp[temp.size()-1];
}
//方法2： 三指针按操作
ListNode* ReverseList(ListNode* pHead) {
if(pHead==NULL||pHead->next==NULL){
return pHead;
}
ListNode* pre =NULL;
ListNode* next = pHead;
ListNode* temp = pHead->next;
while(next->next!=NULL){
next->next = pre;
pre = next;
next = temp;
temp = temp->next;
}
next->next = pre;
return next;
}
剑指：
ListNode* ReverseList(ListNode* pHead) {
ListNode* pre =NULL;
ListNode* node = pHead;
ListNode* result = NULL;
while(node!=NULL){
ListNode*pNext = node->next;
if(pNext == NULL)
result = node;
node->next = pre;
pre = node;
node = pNext;
}
return result;
}
//递归：
ListNode* ReverseList(ListNode* pHead) {
//如果链表为空或者链表中只有一个元素
if(pHead==NULL||pHead->next==NULL) return pHead;
//先反转后面的链表，走到链表的末端结点
ListNode* pReverseNode=ReverseList(pHead->next);
//再将当前节点设置为后面节点的后续节点
pHead->next->next=pHead;
pHead->next=NULL;
return pReverseNode;
}
合并两个排序的链表
我的：
//方法1：
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
ListNode* p1=pHead1;
ListNode* p2=pHead2;
ListNode* temp = new ListNode(0);
ListNode* result = temp;
while(p1!=NULL&&p2!=NULL){
if(p1->val<=p2->val) {
temp->next = p1;
p1 = p1->next;
}
else {
temp->next = p2;
p2 = p2->next;
}
temp = temp->next;
}
while(p1!=NULL){
temp->next = p1;
p1 = p1->next;
temp = temp->next;
}
while(p2!=NULL){
temp->next = p2;
p2 = p2->next;
temp = temp->next;
}
return result->next;
}
//方法2：
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
if(!pHead1)
return pHead2;
if(!pHead2)
return pHead1;
ListNode* Head;
ListNode* p;
//取较小值作头结点
if(pHead1->val<=pHead2->val){
Head=pHead1;
pHead1=pHead1->next;
}
else{
Head=pHead2;
pHead2=pHead2->next;
}
//开始遍历合并
p=Head;
//p为合并后的链表的工作指针
while(pHead1&&pHead2){ //当有一个链表到结尾时，循环结束
if(pHead1->val<=pHead2->val){ //如果链表1的结点小于链表2的结点
p->next=pHead1; //取这个结点加入合并链表
pHead1=pHead1->next; //链表1后移一位
p=p->next; //工作指针后移一位
}
else{ //否则取链表2的结点
p->next=pHead2;
pHead2=pHead2->next;
p=p->next;
}
}
if(pHead1 == NULL) //链表1遍历完了
p->next = pHead2; //如果链表2也遍历完了，则pHead2=NULL
if(pHead2 == NULL) //链表2遍历完了
p->next = pHead1; ///如果链表1也遍历完了，则pHead1=NULL
return Head;
}
剑指：
ListNode* Merge(ListNode* pHead1, ListNode* pHead2)
{
if(pHead1 == NULL) return pHead2;
if(pHead2 == NULL) return pHead1;
ListNode* result = NULL;
if(pHead1->val<=pHead2->val){
result = pHead1;
result->next = Merge(pHead1->next,pHead2);
}else{
result = pHead2;
result->next = Merge(pHead1,pHead2->next);
}
return result;
}
树的子结构
我的：
//方法1：
bool judge(TreeNode* pRoot1, TreeNode* pRoot2){
if(pRoot2==NULL) return true;
if(pRoot1==NULL) return false;
if(pRoot1->val == pRoot2->val){
return judge(pRoot1->left, pRoot2->left)
&& judge(pRoot1->right, pRoot2->right);
}else return false;
}
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
if(pRoot1==NULL||pRoot2==NULL) return false;
queue<TreeNode*> temp;
temp.push(pRoot1);
bool flag = false;
while(!temp.empty()){
int le = temp.size();
for(int i = 0; i<le;i++){
TreeNode* node = temp.front();
cout<<node->val<<endl;
if(node->val==pRoot2->val)
{
flag = judge(node,pRoot2);
if(flag) return true;
}
temp.pop();
if(node->left)temp.push(node->left);
if(node->right)temp.push(node->right);
}
}
return flag;
}
//方法2：
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
if(pRoot2 == NULL || pRoot1 == NULL){
return false;
}else{
return isSubtree(pRoot1, pRoot2) || HasSubtree(pRoot1->left, pRoot2) || HasSubtree(pRoot1->right, pRoot2) ;
}
}
bool isSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
if(pRoot2 == NULL){ return true;}
if(pRoot1 == NULL){ return false;}
if(pRoot2->val == pRoot1->val){
return isSubtree(pRoot1->left, pRoot2->left) && isSubtree(pRoot1->right, pRoot2->right);
}else {return false;}
}
剑指：
bool judge(TreeNode* pRoot1, TreeNode* pRoot2){
if(pRoot2==NULL) return true;
if(pRoot1==NULL) return false;
if(pRoot1->val == pRoot2->val){
return judge(pRoot1->left, pRoot2->left)
&& judge(pRoot1->right, pRoot2->right);
}else return false;
}
bool HasSubtree(TreeNode* pRoot1, TreeNode* pRoot2)
{
bool result = false;
if(pRoot1!=NULL&&pRoot2!=NULL) {
if(pRoot1->val == pRoot2->val) result = judge(pRoot1,pRoot2);
if(!result) result = HasSubtree(pRoot1->left,pRoot2);
if(!result) result = HasSubtree(pRoot1->right,pRoot2);
}
return result;
}
二叉树的镜像
我的：
//方法1：
void change(TreeNode* node){
if(node==NULL) return;
TreeNode* temp = node->left;
node->left = node->right;
node->right = temp;
if(node->left!=NULL) change(node->left);
if(node->right!=NULL) change(node->right);
}
void Mirror(TreeNode *pRoot) {
if(pRoot==NULL) return;
change(pRoot);
}
//方法2：
void Mirror(TreeNode *pRoot) {
if(pRoot==NULL){
return;
}
TreeNode *tmp = pRoot->left;
pRoot->left = pRoot->right;
pRoot->right = tmp;
Mirror(pRoot->left);
Mirror(pRoot->right);
}
PS：
由于计算机表示小数（float和double）都有误差，不能直接用等号（==）判断两个小数是不是相等，得根据两个小数的差的绝对值很小，比如小于0.0000001，六个0，就可以认为他们相等。
bool Equal(){
if((num1-num2>-0.0000001)&&(num1-num2<0.0000001))
return true;
else
return false;
}
剑指的：
void Mirror(TreeNode *pRoot) {
if(pRoot==NULL) return;
if(pRoot->left==NULL&&pRoot->right==NULL) return;
TreeNode * temp = pRoot->left;
pRoot->left = pRoot->right;
pRoot->right = temp;
if(pRoot->left!=NULL) Mirror(pRoot->left);
if(pRoot->right!=NULL) Mirror(pRoot->right);
}
顺时针打印矩阵
我的：
还是有点不熟，注意一行，一列的情况
//方法1：
vector<int> printMatrix(vector<vector<int> > matrix) {
vector<int> result;
int col = matrix.size();
int row = matrix[0].size();
if(col == 0||row==0) return result;
int top = 0;
int bottom = col -1;
int left = 0 ;
int right = row -1;
while(top<=bottom&&left<=right){
for(int i = left ;i<=right;i++){
result.push_back(matrix[top][i]);
}
top++;
for(int i = top ;i<=bottom;i++){
result.push_back(matrix[i][right]);
}
right--;
if(top<=bottom){
for(int i = right ;i>=left;i--){
result.push_back(matrix[bottom][i]);
}
bottom--;
}
if(left<=right){
for(int i = bottom ;i>=top;i--){
result.push_back(matrix[i][left]);
}
left++;
}
}
return result;
}
//方法2：
vector<int> printMatrix(vector<vector<int> > matrix) {
int row = matrix.size();
int col = matrix[0].size();
vector<int> res;
// 输入的二维数组非法，返回空的数组
if (row == 0 || col == 0) return res;
// 定义四个关键变量，表示左上和右下的打印范围
int left = 0, top = 0, right = col - 1, bottom = row - 1;
while (left <= right && top <= bottom)
{
// left to right
for (int i = left; i <= right; ++i) res.push_back(matrix[top][i]);
// top to bottom
for (int i = top + 1; i <= bottom; ++i) res.push_back(matrix[i][right]);
// right to left
if (top != bottom)
for (int i = right - 1; i >= left; --i) res.push_back(matrix[bottom][i]);
// bottom to top
if (left != right)
for (int i = bottom - 1; i > top; --i) res.push_back(matrix[i][left]);
left++,top++,right--,bottom--;
}
return res;
}
剑指的：
/*
* 1.选坐标为(0,0),(1,1)...的点记为(start,start)为开始坐标,下一圈开始坐标为(start+1,start+1)
* 2.判断是否进入下一圈(即是否打印完成)的条件是row>start*2 && column>start*2
* 3.打印一圈的左上角坐标为(start,start)，右下角的坐标为(column-start-1,row-start-1)
* 4.根据一圈左上角和右下角坐标判断“从左到右”，“从上到下”，“从右到左”，“从下到上”哪些用打印，哪些不用
*/
class Solution {
public:
vector<int> printMatrix(vector<vector<int> > matrix) {
if (matrix.empty()) {
return matrix[0];
}
int row = static_cast<int>(matrix.size()) ;
int column = static_cast<int>(matrix[0].size()) ;
int start = 0;
vector<int> result;
result.clear();
while (column > start*2 && row > start*2) {
int endX = column - 1 - start;
int endY = row - 1 - start;
//从左到右打印一行
for (int i=start; i<=endX; i++) {
result.push_back(matrix[start][i]);
}
//从上到下打印一行
if (start <endY) {
for (int i=start+1; i<=endY; i++) {
result.push_back(matrix[i][endX]);
}
}
//从右到左打印一行
if (start < endX && start < endY) {
for (int i=endX-1; i>=start; i--) {
result.push_back(matrix[endY][i]);
}
}
//从下到上打印一行
if (start<endX && start<endY-1) {
for (int i=endY-1; i>=start+1; i--) {
result.push_back(matrix[i][start]);
}
}
start++;
}
return result;
}
};
包含min函数的栈
我的：
stack<int> mystack;
stack<int> mymin;
void push(int value) {
mystack.push(value);
if(mymin.empty()) mymin.push(value);
else{
if(mymin.top()>=value) mymin.push(value);
}
}
void pop() {
if(mymin.top()==mystack.top()){
mymin.pop();
}
mystack.pop();
}
int top() {
return mystack.top();
}
int min() {
return mymin.top();
}
剑指：
/*
* 1.dataStack为存储数据的栈，minStack为存储最小值的栈；
* 2.push的时候将value值与minStack中的top值比较，小则minStack push value，大则push top值
*/
class Solution {
public:
stack<int> dataStack, minStack;
void push(int value) {
dataStack.push(value);
if (minStack.empty()) {
minStack.push(value);
}
else{
int min = minStack.top();
value<=min?minStack.push(value):minStack.push(min);
}
}
void pop() {
dataStack.pop();
minStack.pop();
}
int top() {
return dataStack.top();
}
int min() {
return minStack.top();
}
};
栈的压入、弹出序列
我的：
//方法1：模拟，找规律
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
stack<int> temp;
int p = 0;
for(int i = 0 ;i<pushV.size();i++){
temp.push(pushV[i]);
while(!temp.empty()&&popV[p]==temp.top()) {
temp.pop();
p++;
}
}
return p==pushV.size();
}
//方法2：
bool IsPopOrder(vector<int> pushV,vector<int> popV) {
stack<int> myvt3;
int n = 0;
for(int i = 0 ; i<pushV.size();i++){
myvt3.push(pushV[i]);
if(popV[n] == myvt3.top()){
myvt3.pop();
n++;
}
}
while(!myvt3.empty()){
if(myvt3.top()==popV[n]){
myvt3.pop();
n++;
}else return false;
}
return true;
}
剑指：
从上往下打印二叉树
我的：
//非递归
vector<int> PrintFromTopToBottom(TreeNode* root) {
queue<TreeNode*> nodes;
vector<int> result;
if(root == NULL) return result;
nodes.push(root);
while(!nodes.empty()){
int le = nodes.size();
for(int i = 0;i<le;i++){
TreeNode* temp = nodes.front();
nodes.pop();
result.push_back(temp->val);
if(temp->left!=NULL) nodes.push(temp->left);
if(temp->right!=NULL) nodes.push(temp->right);
}
}
return result;
}
剑指：使用deque双端一样的实现
二叉搜索树的后序遍历序列
我的：分成左右子树，左子树都小于，右子树都大于。
//方法1：
bool judge(vector<int> sequence, int start,int end){
if(start >= end) return true;
int temp = sequence[end];
int flag = start;
for(int i = end;i>=start;i--){
if(sequence[i]<temp) {
flag = i;
break;
}
}
for(int i = start;i<flag;i++){
if(sequence[i]>temp) {
return false;
}
}
// for(int i = flag+1;i<end;i++){
// if(sequence[i]<temp) {
// return false;
// }
// }//可以去掉 因为我们从后面往前走，就是保证了后面的大于了
return judge(sequence,start,flag)&& judge(sequence,flag+1,end-1);
}
bool VerifySquenceOfBST(vector<int> sequence) {
if(sequence.size()==0) return false;
return judge(sequence,0,sequence.size()-1);
}
剑指：差不多
二叉树中和为某一值的路径
我的：
//方法1： 但是没排序
vector<vector<int> > result;
void BFS(vector<int> temp,int sum,TreeNode* root,int expectNumber){
temp.push_back(root->val);
sum += root->val;
if(root->left==NULL&&root->right==NULL){
if(sum == expectNumber)
result.push_back(temp);
}else{
if(root->left!=NULL) BFS(temp, sum, root->left, expectNumber);
if(root->right!=NULL) BFS(temp, sum, root->right, expectNumber);
}
}
vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
if(root==NULL) return result;
vector<int> temp;
BFS(temp, 0, root, expectNumber);
return result;
}
//方法2：
vector<vector<int> >allRes;
vector<int> tmp;
void dfsFind(TreeNode * node , int left){
tmp.push_back(node->val);
if(left-node->val == 0 && !node->left && !node->right)
allRes.push_back(tmp);
else {
if(node->left) dfsFind(node->left, left-node->val);
if(node->right) dfsFind(node->right, left-node->val);
}
tmp.pop_back();
}
public:
vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
if(root) dfsFind(root, expectNumber);
return allRes;
}
PS：
如果传下去的值是传地址的，那么回溯的时候得删除，不然穿变量不用回溯删除，因为是临时的。
剑指：差不多
class Solution {
vector<vector<int> >allRes;
vector<int> tmp;
void dfsFind(TreeNode * node , int left){
tmp.push_back(node->val);
if(left-node->val == 0 && !node->left && !node->right)
allRes.push_back(tmp);
else {
if(node->left) dfsFind(node->left, left-node->val);
if(node->right) dfsFind(node->right, left-node->val);
}
tmp.pop_back();
}
public:
vector<vector<int> > FindPath(TreeNode* root,int expectNumber) {
if(root) dfsFind(root, expectNumber);
return allRes;
}
复杂链表的复制
我的：第一时间分析不清楚，环，random？？
random指向链表中的某一个，然后拆开来得每个链表都拆完。
按分解的3步走：复制，复制random，拆解
RandomListNode* Clone(RandomListNode* pHead)
{
if(pHead==NULL) return pHead;
RandomListNode* ptemp = pHead;
while(ptemp!=NULL){
RandomListNode* temp = new RandomListNode(ptemp->label);
temp->next = ptemp->next;
ptemp->next = temp;
ptemp= temp->next;
}
ptemp = pHead;
while(ptemp!=NULL){
if(ptemp->random!=NULL){
ptemp->next->random = ptemp->random->next;
}
ptemp = ptemp->next->next;
}
ptemp = pHead;
RandomListNode* temp;
RandomListNode* newHead = ptemp->next;
while(ptemp->next!=NULL){
temp = ptemp->next;
ptemp->next = ptemp->next->next;
ptemp = temp;
}
return newHead;
}
//方法2：换一种写法
/*
1、复制每个节点，如：复制节点A得到A1，将A1插入节点A后面
2、遍历链表，A1->random = A->random->next;
3、将链表拆分成原链表和复制后的链表
*/
RandomListNode* Clone(RandomListNode* pHead)
{
if(!pHead) return NULL;
RandomListNode *currNode = pHead;
while(currNode){
RandomListNode *node = new RandomListNode(currNode->label);
node->next = currNode->next;
currNode->next = node;
currNode = node->next;
}
currNode = pHead;
while(currNode){
RandomListNode *node = currNode->next;
if(currNode->random){
node->random = currNode->random->next;
}
currNode = node->next;
}
//拆分
RandomListNode *pCloneHead = pHead->next;
RandomListNode *tmp;
currNode = pHead;
while(currNode->next){
tmp = currNode->next;
currNode->next =tmp->next;
currNode = tmp;
}
return pCloneHead;
}
};
剑指：差不多
二叉搜索树与双向链表
我的：排序+二叉搜索树=中序遍历，记录前一个值，修改左右指针。
//方法1：
TreeNode* pre = NULL;
void toList(TreeNode* pRootOfTree){
if(pRootOfTree==NULL) return;
toList(pRootOfTree->left);
if(pre==NULL){
pre = pRootOfTree;
}else{
pre->right = pRootOfTree;
pRootOfTree->left = pre;
pre = pRootOfTree;
}
toList(pRootOfTree->right);
}
TreeNode* Convert(TreeNode* pRootOfTree)
{
if(pRootOfTree==NULL){
return pRootOfTree;
}
toList(pRootOfTree);
while(pRootOfTree->left!=NULL){
pRootOfTree=pRootOfTree->left;
}
return pRootOfTree;
}
剑指：差不多
字符串的排列
我的：
//方法1：形参
vector<string> result;
void todo(string temp, int start, int end){
if(start == end) {
result.push_back(temp);
return;
}
for(int i = start;i<=end;i++){
if(i>start&&temp[i]==temp[start]) continue;
swap(temp[start], temp[i]);
todo(temp, start+1, end);
}
}
vector<string> Permutation(string str) {
if(str.size()==0) return result;
sort(str.begin(),str.end());
todo(str, 0, str.size()-1);
sort(result.begin(),result.end());
return result;
}
//方法2：实参改变，推荐，模板，但是不能解决leetcode的Permutations II
vector<string> result;
void myswap(char& a, char& b){
char temp = b;
b = a;
a = temp;
}
void todo(string &temp, int start, int end){
if(start == end) {
result.push_back(temp);
return;
}
for(int i = start;i<=end;i++){
if(i>start&&temp[i]==temp[start]) continue;
myswap(temp[start], temp[i]);
todo(temp, start+1, end);
myswap(temp[start], temp[i]);
}
}
vector<string> Permutation(string str) {
if(str.size()==0) return result;
sort(str.begin(),str.end());
todo(str, 0, str.size()-1);
sort(result.begin(),result.end());
return result;
}
//方法3：所有问题都能解决，推荐记住
vector<string> result;
void myswap(char& a, char& b){
char temp = b;
b = a;
a = temp;
}
void todo(string &temp, int start, int end){
if(start == end) {
result.push_back(temp);
return;
}
for(int i = start;i<=end;i++){
int j = i - 1;
while (j >= start && temp[j] != temp[i]) --j;
if (j != start - 1) continue;
myswap(temp[start], temp[i]);
todo(temp, start+1, end);
myswap(temp[start], temp[i]);
}
}
vector<string> Permutation(string str) {
if(str.size()==0) return result;
sort(str.begin(),str.end());
todo(str, 0, str.size()-1);
sort(result.begin(),result.end());
return result;
}
剑指的：没去重
数组中出现次数超过一半的数字
我的：
//方法1：
int MoreThanHalfNum_Solution(vector<int> numbers) {
int le = numbers.size();
if(le==0) return 0;
if(le == 1) return numbers[0];
sort(numbers.begin(), numbers.end());
int flag =le/2;
int count = 1;
for(int i =1;i<le;i++){
if(numbers[i]==numbers[i-1]){
count++;
if(count>flag) return numbers[i];
}else{
count = 1;
}
}
return 0;
}
//方法2：两两抵消
//思路二：如果有符合条件的数字，则它出现的次数比其他所有数字出现的次数和还要多。
//在遍历数组时保存两个值：一是数组中一个数字，一是次数。遍历下一个数字时，若它与之前保存的数字相同，则次数加1，否则次数减1；若次数为0，则保存下一个数字，并将次数置为1。遍历结束后，所保存的数字即为所求。然后再判断它是否符合条件即可。
参考代码如下：
int MoreThanHalfNum_Solution(vector<int> numbers)
{
if(numbers.empty()) return 0;
// 遍历每个元素，并记录次数；若与前一个元素相同，则次数加1，否则次数减1
int result = numbers[0];
int times = 1; // 次数
for(int i=1;i<numbers.size();++i)
{
if(times == 0)
{
// 更新result的值为当前元素，并置次数为1
result = numbers[i];
times = 1;
}
else if(numbers[i] == result)
{
++times; // 相同则加1
}
else
{
--times; // 不同则减1
}
}
// 判断result是否符合条件，即出现次数大于数组长度的一半
times = 0;
for(int i=0;i<numbers.size();++i)
{
if(numbers[i] == result) ++times;
}
return (times > numbers.size()/2) ? result : 0;
}
PS：
C++的sort是理解成快排，但是量少的时候用插入
C++的sort()则是改进的快排算法时间复杂度o(nlogn)。
bool compare(int a,int b)
{
return a<b; //升序排列，如果改为return a>b，则为降序
}
sort(a,a+20,compare);
剑指：
//方法1：快排，然后取中间，检验
//方法2：两两抵消，一样
最小的K个数
我的：
//方法1：
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int> result;
if(input.empty()||k>input.size()) return result;
sort(input.begin(), input.end());
for(int i = 0;i<k;i++){
result.push_back(input[i]);
}
return result;
}
//方法2：大根堆
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
priority_queue<int> pq; //定义优先队列
vector<int> res;
if(input.empty() || input.size() < k || k <= 0) return res;
for(int i = 0; i < input.size(); ++i){
if(pq.size() < k){
pq.push(input[i]);
}else if(input[i] < pq.top()){
pq.pop(); // 将元素出队
pq.push(input[i]); // 入队
}
}
// 取出优先队列中的元素
while(!pq.empty()){
res.push_back(pq.top());
pq.pop();
}
return res;
}
PS：掌握插入排序，冒泡排序，归并排序，快速排序等不同算法的的优劣，从额外空间的消耗，平均时间复杂度和最差时间复杂度，稳定性等比较，熟练掌握快速排序的写法。
//快速排序：
我写的：
void myswap(int &a, int &b){
int temp = a;
a = b;
b = temp;
}
void QuickSort(vector<int> &input, int start, int end){
if(start == end) return;
int key = input[start];
int i = start;
int j = end;
while(i<j){
while(j>i&&input[j]>=key){
j--;
}
myswap(input[i], input[j]);
while(j>i&&input[i]<key){
i++;
}
myswap(input[i], input[j]);
}
QuickSort(input,start,i);
QuickSort(input,j+1,end);
}
标准的：
void Qsort(int arr[], int low, int high){
if (high <= low) return;
int i = low;
int j = high + 1;
int key = arr[low];
while (true)
{
/*从左向右找比key大的值*/
while (arr[++i] < key)
{
if (i == high){
break;
}
}
/*从右向左找比key小的值*/
while (arr[--j] > key)
{
if (j == low){
break;
}
}
if (i >= j) break;
/*交换i,j对应的值*/
int temp = arr[i];
arr[i] = arr[j];
arr[j] = temp;
}
/*中枢值与j对应值交换*/
int temp = arr[low];
arr[low] = arr[j];
arr[j] = temp;
Qsort(arr, low, j - 1);
Qsort(arr, j + 1, high);
}
image.png
剑指：
//快排的想法：：利用快速排序中的获取分割（中轴）点位置函数getPartitiion。 基于数组的第k个数字来调整，使得比第k个数字小的所有数字都位于数组的左边，比第k个数字大的所有数字都位于数组的右边。调整之后，位于数组左边的k个数字就是最小的k个数字（这k个数字不一定是排序的）。O(N)
public:
void swap(int &fir,int &sec)
{
int temp = fir;
fir = sec;
sec = temp;
}
int getPartition(vector<int> &input,int start,int end)
{
if(input.empty() || start>end) return -1;
int temp = input[end];
int j = start - 1;
for(int i=start;i<end;++i)
{
if(input[i]<=temp)
{
++j;
if(i!=j) swap(input[i],input[j]);
}
}
swap(input[j+1],input[end]);
return (j+1);
}
vector<int> GetLeastNumbers_Solution(vector<int> input, int k)
{
vector<int> result;
if(input.empty() || k>input.size() || k<=0) return result;
int start = 0;
int end = input.size()-1;
int index = getPartition(input,start,end);
while(index != (k-1))
{
if(index > (k-1))
{
end = index - 1;
index = getPartition(input,start,end);
}
else
{
start = index + 1;
index = getPartition(input,start,end);
}
}
for(int i=0;i<k;++i)
{
result.push_back(input[i]);
}
return result;
}
//实现2：
vector<int> GetLeastNumbers_Solution(vector<int> input, int k) {
vector<int> res;
int length = input.size();
// 特殊情况判断！！！超时的原因在这
if(input.empty() || k > length || k<=0) return res;
int start = 0, end = length - 1;
int index = Partition(input, start, end); // 对数组进行划分
// 有点类似于二分的思想，再次划分
while(index != k - 1){
if(index > k - 1){
end = index - 1;
index = Partition(input, start, end);
}else{
start = index + 1;
index = Partition(input, start, end);
}
}
for(int i=0; i < k; i++){
res.push_back(input[i]);
}
return res;
}
// 需要修改传递的数组，使用引用形式(超时)
int Partition(vector<int> &input, int start, int end){
int pivot = input[start];
// 将比枢轴小的数调整到数组前面，比枢轴大的数调整到数组后面
while(start < end){
while(start < end && pivot <= input[end])
end--;
input[start] = input[end];
while(start < end && pivot >= input[start])
start++;
input[end] = input[start];
}
input[start] = pivot;
return start;
}
// 划分函数的另一种写法
int Partition(vector<int> &input, int start, int end){
int index = start; // 枢轴
//int index = RandInRange(start, end); // 随机选择一个数作为枢轴
swap(input[index], input[end]);
int small = start - 1;
for(index = start; index < end; ++index){
if(input[index] <= input[end]){
++small;
if(small != index)
// 将小于枢轴的数交换到前面
swap(input[small], input[index]);
}
}
++small;
swap(input[small], input[end]);
return small; // 最后返回枢轴的位置
}
// 生成随机的枢轴
int RandInRange(int a, int b){
int c;
c = a + rand()%(b - a + 1);
return c;
}
void swap(int &fir, int &sec){
int temp;
temp = fir;
fir = sec;
sec = temp;
}
连续子数组的最大和
我的：看到串想到双指针，想不出来
，参考答案
//方法1：动态规划
int le = array.size();
int sum = array[0];
int mx = array[0];
for(int i = 1 ; i < le; i++){
sum = max(sum+array[i],array[i]);
mx = max(sum,mx);
}
return mx;
//方法2：暴力，滑动窗口
int FindGreatestSumOfSubArray(vector<int> array) {
int m = INT_MIN;
for(int i = 1;i<array.size()+1;i++){ //长度
for(int j = 0;j<array.size()+1-i;j++){ //起始点
int now=0;
for(int k =0;k<i;k++){ //尾部
now += array.at(j+k);
}
m = max(now,m);
}
}
return m;
}
//方法3：容易理解
int FindGreatestSumOfSubArray(vector<int> array) {
int le = array.size();
int sum = 0;
int mx = INT_MIN;
for(int i = 0 ; i < le; i++){
if(sum<=0){
sum = array[i];
}else
sum += array[i];
mx = max(sum,mx);
}
return mx;
}
剑指：
//丢去没有的累积
public int FindGreatestSumOfSubArray(int[] array) {
if (array.length==0 || array==null) {
return 0;
}
int curSum=0;
int greatestSum=0x80000000;
for (int i = 0; i < array.length; i++) {
if (curSum<=0) {
curSum=array[i]; //记录当前最大值
}else {
curSum+=array[i]; //当array[i]为正数时，加上之前的最大值并更新最大值。
}
if (curSum>greatestSum) {
greatestSum=curSum;
}
}
return greatestSum;
}
//动态规划：使用动态规划 F（i）：以array[i]为末尾元素的子数组的和的最大值，子数组的元素的相对位置不变 。F（i）=max（F（i-1）+array[i] ， array[i]）
public int FindGreatestSumOfSubArray(int[] array) {
int res = array[0]; //记录当前所有子数组的和的最大值
int max=array[0]; //包含array[i]的连续数组最大值
for (int i = 1; i < array.length; i++) {
max=Math.max(max+array[i], array[i]);
res=Math.max(max, res);
}
return res;
}
我的：
//方法1：暴力O(nlogn)。
int NumberOf1Between1AndN_Solution(int n)
{
int count = 0;
for(int i =1;i<=n;i++){
int temp = i;
while(temp!=0){
if(temp%10==1) count++;
temp=temp/10;
}
}
return count;
}
//方法2：https://www.cnblogs.com/xuanxufeng/p/6854105.html O(logn).
int NumberOf1Between1AndN_Solution(int n)
{
int count=0;
long long i=1;
for(i=1;i<=n;i*=10)
{
//i表示当前分析的是哪一个数位
int a = n/i,b = n%i;
count=count+(a+8)/10*i+(a%10==1)*(b+1);
}
return count;
}
剑指：
//方法1：暴力
//方法2：数学规律
把数组排成最小的数
我的：
//方法1：
static bool cmp(int a , int b){ //注意sort中的这个得用static https://blog.csdn.net/u010982765/article/details/79021426
string temp1 = to_string(a);
string temp2 = to_string(b);
return (temp1+temp2)<(temp2+temp1);
}
string PrintMinNumber(vector<int> numbers) {
sort(numbers.begin(),numbers.end(),cmp);
string result = "";
for(int i:numbers){
result+=to_string(i);
}
return result;
}
//方法2：冒泡排序
string PrintMinNumber(vector<int> numbers) {
vector<string> str_numbers;
string result = "";
for(int i = 0;i<numbers.size();i++){
str_numbers.push_back(to_string(numbers[i]));
}
for(int i = 0 ; i<str_numbers.size();i++){
for(int j = 0 ; j<str_numbers.size()-i-1;j++){
if(str_numbers[j]+str_numbers[j+1]>str_numbers[j+1]+str_numbers[j]){
string temp = str_numbers[j+1];
str_numbers[j+1] = str_numbers[j];
str_numbers[j] = temp;
}
}
}
for(int i = 0;i<str_numbers.size();i++){
result+=str_numbers[i];
// cout<<str_numbers[i]<<endl;
}
return result;
}
剑指：
//重定义比较器
丑数
我的：想到每个数字一个数组维护，但是不会
//方法1：数学规律
int GetUglyNumber_Solution(int index) {
if(index<=1) return index;
vector<int> result;
result.push_back(1);
int p[3] = {0,0,0};
for(int i=1;i<index;i++){
result.push_back(min(min(2*result[p[0]],3*result[p[1]]),5*result[p[2]]));
if(result.back()%2==0) p[0]+=1;
if(result.back()%3==0) p[1]+=1;
if(result.back()%5==0) p[2]+=1;
}
return result.back();
}
//方法2：
int GetUglyNumber_Solution(int index) {
// 0-6的丑数分别为0-6
if(index < 7) return index;
//p2，p3，p5分别为三个队列的指针，newNum为从队列头选出来的最小数
int p2 = 0, p3 = 0, p5 = 0, newNum = 1;
vector<int> arr;
arr.push_back(newNum);
while(arr.size() < index) {
//选出三个队列头最小的数
newNum = min(arr[p2] * 2, min(arr[p3] * 3, arr[p5] * 5));
//这三个if有可能进入一个或者多个，进入多个是三个队列头最小的数有多个的情况
if(arr[p2] * 2 == newNum) p2++;
if(arr[p3] * 3 == newNum) p3++;
if(arr[p5] * 5 == newNum) p5++;
arr.push_back(newNum);
}
return newNum;
}
//方法3：
int GetUglyNumber_Solution(int index) {
if(index<=1) return index;
vector<int> result;
result.push_back(1);
int p[3] = {0,0,0};
for(int i=1;i<index;i++){
result.push_back(min(min(2*result[p[0]],3*result[p[1]]),5*result[p[2]]));
if(result.back()== result[p[0]]*2) p[0]+=1;
if(result.back()==result[p[1]]*3) p[1]+=1;
if(result.back()==result[p[2]]*5) p[2]+=1;
}
return result.back();
}
剑指：
找出字符串中第一次出现的一次的字符
我的：
int FirstNotRepeatingChar(string str) {
int flag2[256]={0};
for(char s: str){
flag2[s]++;
}
for(int i = 0;i<256;i++){
if(flag2[str[i]]==1) {return i;}
}
return -1;
}
剑指：
//方法1：暴力，每个字符和后面的字符对比。O(n^2)
//方法2：和我的相似
数组中的逆序对
我的：merge-sort，在merg中加入判断逆序，左数组的某数a大于右数组的某数b，那么a的后面数字也都大于b。
//方法1：
int cot = 0;
void merge(vector<int> &data, int left, int mid, int right){
vector<int> temp;
int i = left;
int j = mid;
while(i<mid&&j<right){
if(data[i]>data[j]){
cot = (cot+(mid-i))%1000000007;
temp.push_back(data[j++]);
}else{
temp.push_back(data[i++]);
}
}
while(i<mid){
temp.push_back(data[i++]);
}
while(j<right){
temp.push_back(data[j++]);
}
for(int k = 0;k<temp.size();k++){
data[left+k] = temp[k];
}
}
void mergesort(vector<int> &data, int left, int right){
if(left+1<right){
int mid = left+(right-left)/2;
mergesort(data, left, mid);
mergesort(data, mid, right);
merge(data, left, mid, right);
}
}
int InversePairs(vector<int> data) {
if(data.size()==0) return 0;
mergesort(data,0,data.size());
return cot;
}
PS：归并排序：速度仅次于快速排序，为稳定排序算法，一般用于对总体无序，但是各子项相对有序的数列，
一、一维数组
静态 int array[100]; 定义了数组array，并未对数组进行初始化
静态 int array[100] = {1，2}； 定义并初始化了数组array
动态 int* array = new int[100]; delete []array; 分配了长度为100的数组array
动态 int* array = new int100; delete []array; 为长度为100的数组array初始化前两个元素
五、字符数组
char类型的数组被常委字符数组，在字符数组中最后一位为转移字符'\0'（也被成为空字符），该字符表示字符串已结束。在C++中定义了string类，在Visual C++中定义了Cstring类。
字符串中每一个字符占用一个字节，再加上最后一个空字符。如：
char array[10] = "cnblogs";
虽然只有7个字节，但是字符串长度为8个字节。
剑指：
//方法1：暴力，每个和后面的对比
//方法2：从右数组的右边开始比较
long long InversePairsCore(vector<int> &data,vector<int>©,int start,int end)
{
if(start==end)
{
copy[start]=data[start];
return 0;
}
int length = (end-start)/2;
long long left = InversePairsCore(copy,data,start,start+length);
long long right = InversePairsCore(copy,data,start+length+1,end);
int i = start + length;
int j = end;
int indexCopy = end;
long long count=0;
while(i>=start&&j>=start+length+1)
{
if(data[i]>data[j])
{
copy[indexCopy--]=data[i--];
count+=j-start-length;
}
else
{
copy[indexCopy--]=data[j--];
}
}
for(;i>=start;--i)
copy[indexCopy--] = data[i];
for(;j>=start+length+1;--j)
copy[indexCopy--] = data[j];
return left+right+count;
}
int InversePairs(vector<int> data) {
int length = data.size();
if(length<=0)
return 0;
vector<int> copy;
for(int i=0;i<length;i++)
copy.push_back(data[i]);
long long count = InversePairsCore(data,copy,0,length-1);
copy.clear();
return count%1000000007;
}
两个链表的第一个公共节点
我的：
//方法1：长的先走
ListNode* FindFirstCommonNode( ListNode* pHead1, ListNode* pHead2) {
if(pHead1==NULL&&pHead2==NULL) return NULL;
int le1 = 0;
int le2 = 0;
ListNode* temp1 =pHead1;
ListNode* temp2 =pHead2;
while(temp1!=NULL||temp2!=NULL){
if(temp1!=NULL){
le1++;
temp1 = temp1->next;
}
if(temp2!=NULL){
le2++;
temp2 = temp2->next;
}
}
temp1 =pHead1;
temp2 =pHead2;
if(le1>le2){
int dif = le1-le2;
while(dif>0){
temp1=temp1->next;
dif--;
}
}else if(le2>le1){
int dif = le2-le1;
while(dif>0){
temp2=temp2->next;
dif--;
}
}
while(temp1!=NULL&&temp2!=NULL){
if(temp1==temp2) return temp1;
else {
temp1=temp1->next;
temp2=temp2->next;
}
}
return NULL;
}
//尾部使用stack，后往前
思路： 如果存在共同节点的话，那么从该节点，两个链表之后的元素都是相同的。
也就是说两个链表从尾部往前到某个点，节点都是一样的。
我们可以用两个栈分别来装这两条链表。一个一个比较出来的值。
找到第一个相同的节点。
import java.util.Stack;
public class Solution {
public ListNode FindFirstCommonNode(ListNode pHead1, ListNode pHead2) {
if (pHead1 == null || pHead2 == null) {
return null;
}
Stack<ListNode> stack1 = new Stack<>();
Stack<ListNode> stack2 = new Stack<>();
while (pHead1 != null) {
stack1.push(pHead1);
pHead1 = pHead1.next;
}
while (pHead2 != null) {
stack2.push(pHead2);
pHead2 = pHead2.next;
}
ListNode commonListNode = null;
while (!stack1.isEmpty() && !stack2.isEmpty() && stack1.peek() == stack2.peek() ) {
stack2.pop();
commonListNode = stack1.pop();;
}
return commonListNode;
}
}
//方法3：使用hashmap
//方法3：巧妙的弄成长度想通
有个思路，不需要存储链表的额外空间。也不需要提前知道链表的长度。看下面的链表例子：
0-1-2-3-4-5-null
a-b-4-5-null
代码的ifelse语句，对于某个指针p1来说，其实就是让它跑了连接好的的链表，长度就变成一样了。
如果有公共结点，那么指针一起走到末尾的部分，也就一定会重叠。看看下面指针的路径吧。
p1： 0-1-2-3-4-5-null(此时遇到ifelse)-a-b-4-5-null
p2: a-b-4-5-null(此时遇到ifelse)0-1-2-3-4-5-null
因此，两个指针所要遍历的链表就长度一样了！
class Solution:
def FindFirstCommonNode(self, pHead1, pHead2):
p1,p2=pHead1,pHead2
while p1!=p2:
p1 = p1.next if p1 else pHead2
p2 = p2.next if p2 else pHead1
return p1
剑指：
//方法1：栈，后向前弹找
//方法2：长度长的先走
数字在排序数组中出现的次数
我的：排序想到二分法，学会递归和非递归
//方法1：使用二分法找出左右边界，右边界使用k+1找，我写的不太好，要判断的情况太多了。
int BiSearch(vector<int> data, int k, int left, int right){
if(left<right){
int mid = left + (right - left)/2;
if(k==data[mid]) {
return BiSearch(data, k, left, mid);
}else{
if(k>data[mid])
return BiSearch(data, k, mid+1, right);
else
return BiSearch(data, k, left, mid);
}
}else{
return right;
}
}
int GetNumberOfK(vector<int> data ,int k) {
int length = data.size();
if(length == 0) return 0;
int f1 = BiSearch(data, k, 0, length-1);
int f2 = BiSearch(data, k+1, 0, length-1);
int result = f2 - f1;
if(f2==f1){
if(data[f1]!=k)
return 0;
else return f2-f1+1;
}else
{
if(f2==length-1&&data[length-1]==k) return result+1;
}
return result;
}
//方法2：左找，右找
int FirstBiSearch(vector<int> data, int k, int left, int right){
while(left<=right){
int mid = left + (right - left)/2;
if(data[mid] == k){
if(mid>0&&data[mid-1]!=k||mid==0){
return mid;
}else{
right = mid - 1;
}
}else if(data[mid] > k){
right = mid - 1;
}else{
left = mid + 1;
}
}
return -1;
}
int LastBiSearch(vector<int> data, int k, int left, int right){
int length = data.size();
while(left<=right){
int mid = left + (right - left)/2;
if(data[mid] == k){
if(mid<length-1&&data[mid+1]!=k||mid==length-1){
return mid;
}else{
left = mid + 1;
}
}else if(data[mid] > k){
right = mid - 1;
}else{
left = mid + 1;
}
}
return -1;
}
int GetNumberOfK(vector<int> data ,int k) {
int length = data.size();
if(length == 0) return 0;
int f1 = FirstBiSearch(data, k, 0, length-1);
int f2 = LastBiSearch(data, k, 0, length-1);
if(f1!=-1&&f2!=-1){
return f2-f1+1;
}
return 0;
}
//方法3：找K-0.5和K+0.5的位置
public:
int GetNumberOfK(vector<int> data ,int k) {
return biSearch(data, k+0.5) - biSearch(data, k-0.5) ;
}
private:
int biSearch(const vector<int> & data, double num){
int s = 0, e = data.size()-1;
while(s <= e){
int mid = (e - s)/2 + s;
if(data[mid] < num)
s = mid + 1;
else if(data[mid] > num)
e = mid - 1;
}
return s;
}
PS：二分法
//非递归：
int Binary_Search(T *x, int N, T keyword)
{
int low = 0, high = N-1,mid;
while(low <= high)
{
mid = (low + high)/2;
if(x[mid] == keyword)
return mid;
if(x[mid] < keyword)
low = mid + 1;
else
high = mid -1;
}
return -1;
}
/*折半查找，递归实现*/
int Binary_Search2(int *a, int low, int high, int key)
{
if(low > hign)
return -1;
int mid = (low + high) / 2;
if(a[mid] == key)
return mid;
if(a[mid] > key)
return Binary_Search2(a, low, mid-1, key);
else
return Binary_Search2(a, mid+1, high, key);
}
剑指：方法2
public:
int GetFirstK(vector<int>data,int k,int start,intend)
{
if(start>end)
return -1;
int middleIndex = (start+end)/2;
int middleData = data[middleIndex];
if(middleData==k)
{
if((data[middleIndex-1]!=k&&middleIndex>0)||middleIndex==0)
return middleIndex;
else
end = middleIndex-1;
}
else if(data[middleIndex]>k)
end = middleIndex-1;
else
start = middleIndex+1;
return GetFirstK(data,k,start,end);
}
int GetLastK(vector<int>data,int k,int start,intend)
{
if(start>end)
return -1;
int middleIndex = (start+end)/2;
int middleData = data[middleIndex];
if(middleData==k)
{
if((data[middleIndex+1]!=k&&middleIndex>0)||middleIndex==0)
return middleIndex;
else
start = middleIndex+1;
}
else if(data[middleIndex]>k)
end = middleIndex-1;
else
start = middleIndex+1;
return GetLastK(data,k,start,end);
}
int GetNumberOfK(vector<int> data ,int k) {
int length = data.size();
if(length<=0)
return 0;
int start = 0;
int end = length-1;
int firstNumber = GetFirstK(data,k,start,end);
int lastNumber = GetLastK(data,k,start,end);
if(firstNumber==-1||lastNumber==-1)
return 0;
else
return lastNumber-firstNumber+1;
}
二叉树的深度
我的：
//bfs:
int TreeDepth(TreeNode* pRoot)
{
if(pRoot==NULL){
return 0;
}
int depth = 0;
queue<TreeNode*> nodes;
nodes.push(pRoot);
while(!nodes.empty()){
int size = nodes.size();
TreeNode* temp;
for(int i = 0 ; i < size;i++){
temp = nodes.front();
nodes.pop();
if(temp->left!=NULL) nodes.push(temp->left);
if(temp->right!=NULL) nodes.push(temp->right);
}
depth++;
}
return depth;
}
//递归：
int TreeDepth(TreeNode* pRoot)
{
if(pRoot==NULL){
return 0;
}
int left = TreeDepth(pRoot->left);
int right = TreeDepth(pRoot->right);
return left>right?left+1:right+1;
}
剑指：
//递归：
int TreeDepth(TreeNode* pRoot)
{
if(pRoot==NULL){
return 0;
}
int left = TreeDepth(pRoot->left);
int right = TreeDepth(pRoot->right);
return left>right?left+1:right+1;
}
平衡二叉树
我的：
//方法1：从上至下计算深度，当前总体左右子树是不是符合，符合的话递归下一个左右子树判断，这种做法有很明显的问题，在判断上层结点的时候，会多次重复遍历下层结点，增加了不必要的开销。如果改为从下往上遍历，如果子树是平衡二叉树，则返回子树的高度；如果发现子树不是平衡二叉树，则直接停止遍历，这样至多只对每个结点访问一次。
int depth(TreeNode* pRoot){
if(pRoot == NULL) return 0;
int left = depth(pRoot->left);
int right = depth(pRoot->right);
return left>right?(left+1):(right+1);
}
bool IsBalanced_Solution(TreeNode* pRoot) {
if(pRoot==NULL) return true;
int left = depth(pRoot->left);
int right = depth(pRoot->right);
if(abs(left-right)<=1){
return IsBalanced_Solution(pRoot->left)&&IsBalanced_Solution(pRoot->right);
}else return false;
}
//方法2：从下到上，一遇到不合格的直接返回错误。后序遍历就是从下到上的。
int depth(TreeNode* pRoot){
if(pRoot == NULL) return 0;
int left = depth(pRoot->left);
if(left == -1) return -1;
int right = depth(pRoot->right);
if(right == -1) return -1;
return left>right?(left+1):(right+1);
}
bool IsBalanced_Solution(TreeNode* pRoot) {
if(pRoot==NULL) return true;
return depth(pRoot)!=-1;
}
PS：平衡二叉搜索树（Self-balancing binary search tree）又被称为AVL树（有别于AVL算法），且具有以下性质：它是一 棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
剑指：
//方法1：从上到下，重复
//方法2：从下到上，记录每个深度。
//后续遍历时，遍历到一个节点，其左右子树已经遍历 依次自底向上判断，每个节点只需要遍历一次
bool IsBalanced(TreeNode *root, int & dep){
if(root == NULL){
return true;
}
int left = 0;
int right = 0;
if(IsBalanced(root->left,left) && IsBalanced(root->right, right)){
int dif = left - right;
if(dif<-1 || dif >1)
return false;
dep = (left > right ? left : right) + 1;
return true;
}
return false;
}
bool IsBalanced_Solution(TreeNode* pRoot) {
int dep = 0;
return IsBalanced(pRoot, dep);
}
数组中只出现一次的数字
我的：只想到了异或，没想到原理
//方法1：
int length = data.size();
if(length<2) return;
vector<int> temp1;
vector<int> temp2;
int temp=0;
for(int i : data){
temp=temp^i;
}
int flag=0;
while(temp!=0){
if(temp&1==1) break;
temp = temp>>1;
flag++;
}
flag = 1<<flag;
for(int i : data){
if(i&flag) temp1.push_back(i);
else temp2.push_back(i);
}
temp = 0;
for(int i : temp1){
temp=temp^i;
}
*num1 = temp;
temp = 0;
for(int i : temp2){
temp=temp^i;
}
*num2 = temp;
PS：
i&flag不一定等于1，只能判断那一位是不是1。
位运算中异或的性质：两个相同数字异或=0，一个数和0异或还是它本身。
剑指：
public void FindNumsAppearOnce(int [] array,int num1[], int num2[]) {
if(array==null ||array.length<2)
return ;
int temp = 0;
for(int i=0;i<array.length;i++)
temp ^= array[i];
int indexOf1 = findFirstBitIs(temp);
for(int i=0;i<array.length;i++){
if(isBit(array[i], indexOf1))
num1[0]^=array[i];
else
num2[0]^=array[i];
}
}
public int findFirstBitIs(int num){
int indexBit = 0;
while(((num & 1)==0) &&(indexBit)<8*4){
num = num >> 1;
++indexBit;
}
return indexBit;
}
public boolean isBit(int num,int indexBit){
num = num >> indexBit;
return (num & 1) == 1;
}
}
和为S的连续正数序列
我的：第一时间不会
//方法1：滑动窗口，小于sum则右边向右移动，大于sum则左边向右移动，
vector<vector<int> > result;
vector<vector<int> > FindContinuousSequence(int sum) {
int left = 1;
int right = 2;
while(left<right){
int s = (left+right)*(right-left+1)/2;
if(s == sum){
vector<int> temp;
for(int i = left;i<=right;i++){
temp.push_back(i);
}
result.push_back(temp);
left++;
}else if(s<sum){
right++;
}else left++;
}
return result;
}
//方法2：解方程:https://blog.csdn.net/qq_41822235/article/details/82109081
(a + b)(b - a + 1) = 2 * sum;此为等差数列公式。
剑指：
public class FindContinuousSequenceSolution {
public ArrayList<ArrayList<Integer>> FindContinuousSequence(int sum) {
ArrayList<ArrayList<Integer>> result = new ArrayList<>();
if (sum < 3){
return result;
}
int small = 1;
int big = 2;
int curSum = small +big;
int middle = (sum+1)/2;
while (small<middle){
if (curSum == sum){
ArrayList<Integer> temp = new ArrayList<>();
for (int i = small; i <= big; i++) {
temp.add(i);
}
result.add(temp);
}
while (curSum > sum && small<middle){
curSum -= small;
small++;
if (curSum == sum){
ArrayList<Integer> temp = new ArrayList<>();
for (int i = small; i <= big; i++) {
temp.add(i);
}
result.add(temp);
}
}
big++;
curSum += big;
}
return result;
}
}
//方法2：优化
vector<vector<int> > FindContinuousSequence(int sum) {
vector<vector<int>> res;
if(sum<3)
return res;
int begin = 1;
int end = 2;
//初始化curSum时直接用3，不要用a+b,这样效率会高一点
int curSum = 3;
int mid = (1+sum)>>1;
//当begin<mid或者end<(mid+1)时，连续序列的和肯定超出sum了，所以这两个都要限制一下
while(begin<mid && end<mid+1){
while(curSum>sum){
curSum -= begin;
++begin;
}
//这段代码不要上一个while之前，不然会代码重复，而且多了一次判断，效率不高
if(curSum==sum)
insertRes(begin,end,res);
++end;
curSum += end;
}
return res;
和为S的两个数字
我的：
//方法1：左右指针
vector<int> FindNumbersWithSum(vector<int> array,int sum) {
vector<int> result;
int length = array.size();
if(length<2) return result;
int start = 0;
int end = length-1;
while(start<end){
int temp = array[start]+array[end];
if(temp == sum){
result.push_back(array[start]);
result.push_back(array[end]);
return result;
}else if(temp > sum){
end--;
}else start++;
}
return result;
}
PS：
假设：若b>a,且存在，
a + b = s;
(a - m ) + (b + m) = s
则：(a - m )(b + m)=ab - (b-a)m - m*m < ab；说明外层的乘积更小
剑指：一样
左旋转字符串
我的：
//方法1：
int length = str.size();
if(length==0||n%length==0) return str;
if(n > length) n= n%length;
string temp="";
for(int i =0;i<n;i++){
temp=temp+str[i];
}
for(int i = length-1;i>=n;i--){
temp=str[i]+temp;
}
return temp;
//方法2：翻转YX = (X^TY ^T)T
void reverse(string &s, int start, int end){
char temp;
while(start<end){
temp = s[start];
s[start] = s[end];
s[end] = temp;
start++;
end--;
}
}
string LeftRotateString(string str, int n) {
int length = str.size();
if(length==0||n%length==0) return str;
if(n > length) n= n%length;
reverse(str,0,n-1);
reverse(str,n,length-1);
reverse(str,0,length-1);
return str;
}
剑指：方法2
翻转单词顺序列
我的：
//方法1：
void reverse(vector<string> &s, int start, int end){
string temp;
while(start<end){
temp = s[start];
s[start] = s[end];
s[end] = temp;
start++;
end--;
}
}
string ReverseSentence(string str) {
int length = str.size();
string result = "";
vector<string> s;
if(length == 0) return result;
int flag = 0;
string temp = "";
for(int i = 0;i<length;i++){
if(str[i]!=' ') temp+=str[i]; //最后一个单词不会放进去
else {
s.push_back(temp);
temp = "";
}
}
s.push_back(temp);//最后一个单词放进去
reverse(s,0,s.size()-1);
for(int i = 0;i<s.size();i++){
if(i!=s.size()-1) result+=(s[i]+" ");
else result+=s[i];
}
return result;
}
//方法2：优化
string ReverseSentence(string str) {
int length = str.size();
string result = "";
if(length == 0) return result;
int flag = 0;
string temp = "";
for(int i = 0;i<length;i++){
if(str[i]!=' ') temp+=str[i];
else {
result=" "+temp + result;
temp = "";
}
}
result = temp+result;
return result;
}
//方法3：翻转整个句子，在翻转每个单词
public String ReverseSentence(String str) {
if(str==null||str.trim().getClass().equals(""))
return str;
char[] c=str.toCharArray();
reverse(c, 0, str.length()-1);//翻转整个句子
//翻转句子中的每个单词
int begin=0;
int end=0;
while(begin!=c.length){//若起始字符为空格，则begin和end都自加
if(c[begin]==' '){
begin++;
end++;
}
else if(c[end]==' '){//遍历到终止字符为空格，就进行翻转
reverse(c, begin, --end);
begin=++end;
}
else if(end==c.length-1){//若遍历结束，就进行翻转
reverse(c, begin,end);
begin=++end;
}
else{//没有遍历到空格或者遍历结束，则单独对end自减
end++;
}
}
return String.valueOf(c);
}
剑指：方法3
扑克牌顺子
我的：
//方法1：找出一些规律，不能相差大于4，不能相等
int ma=INT_MIN;
int mi=INT_MAX;
bool equal(vector<int> numbers){
int temp[13]={0};
bool flag = true;
for(int i :numbers){
if(i==0) continue;
else{
ma = max(ma,i);
mi = min(mi,i);
if(temp[i]==0)temp[i]++;
else flag = false;
}
}
return flag;
}
bool IsContinuous( vector<int> numbers ) {
if(numbers.size()<5||!equal(numbers)) return false;
if(ma-mi>4) return false;
return true;
}
剑指：找出0，找出空缺数目，看是否弥补
public boolean isContinuous(int[] numbers) {
int numOfZero = 0;
int numOfInterval = 0;
int length = numbers.length;
if(length == 0){
return false;
}
Arrays.sort(numbers);
for (int i = 0; i < length - 1; i++) {
// 计算癞子数量
if (numbers[i] == 0) {
numOfZero++;
continue;
}
// 对子，直接返回
if (numbers[i] == numbers[i + 1]) {
return false;
}
numOfInterval += numbers[i + 1] - numbers[i] - 1;
}
if (numOfZero >= numOfInterval) {
return true;
}
return false;
}
孩子们的游戏(圆圈中最后剩下的数)
我的：
//方法1：链表模拟游戏过程，O（MN）
struct ListNode2 {
int val;
struct ListNode2 *next;
struct ListNode2 *pre;
ListNode2(int x) :
val(x), next(NULL), pre(NULL) {
}
};
void del(ListNode2* node){
ListNode2 *temp = node;
temp->pre->next = temp ->next;
}
int LastRemaining_Solution(int n, int m)
{
if(n==0||m<1) return -1;
ListNode2 *head = new ListNode2(0);
ListNode2 *temp = head;
for(int i = 1;i<n;i++){
ListNode2 *newnode = new ListNode2(i);
newnode->pre = temp;
temp->next = newnode;
temp = temp->next;
}
temp -> next = head;
head ->pre = temp;
temp = head;
int con = 0;
while(temp->next!=temp){
if(con == m-1){
con = 0;
temp->pre->next = temp ->next;
temp ->next->pre = temp->pre;
temp = temp->next;
}else {
temp = temp->next;
con++;
}
}
return temp->val;
}
//方法2：
/*
*这道题我用数组来模拟环，思路还是比较简单，但是各种下标要理清
*/
public static int findLastNumber(int n,int m){
if(n<1||m<1) return -1;
int[] array = new int[n];
int i = -1,step = 0, count = n;
while(count>0){ //跳出循环时将最后一个元素也设置为了-1
i++; //指向上一个被删除对象的下一个元素。
if(i>=n) i=0; //模拟环。
if(array[i] == -1) continue; //跳过被删除的对象。
step++; //记录已走过的。
if(step==m) { //找到待删除的对象。
array[i]=-1;
step = 0;
count--;
}
}
return i;//返回跳出循环时的i,即最后一个被设置为-1的元素
}
剑指：
//方法1：环形列表
//方法2：数学归纳法
public int LastRemaining_Solution(int n,int m) {
if(n==0) return -1;
int s=0;
for(int i=2;i<=n;i++){
s=(s+m)%i;
}
return s;
}
求1+2+3+...+n
我的：
int add(int& sum,int n){
sum+=n;
return (n-1)&&add(sum,n-1);
}
int Sum_Solution(int n) {
if(n<=1) return n;
int sum = 0;
add(sum,n);
return sum;
}
剑指：
//方法1：构造函数
static int sn;
static int ssum;
class temp
{
public:
temp()
{
sn++;
ssum = ssum+sn;
}
};
classSolution {
public:
intSum_Solution(intn) {
sn=0;
ssum=0;
temp *t=new temp[n];
delete[] t;
return ssum;
}
};
//方法2：虚函数
//方法3：函数指针
//方法4：模板
不用加减乘除做加法
我的：位运算，不会
//方法1：没通过
int Add(int num1, int num2)
{
vector<int> flag;
int f = 0;
while(num1!=0&&num2!=0){
int temp1 = num1&1;
int temp2 = num2&1;
if(temp1^temp2==0){
flag.push_back(f);
if(temp1 == 1) {
f = 1;
}else{
f=0;
}
}else{
if(f == 1) {
flag.push_back(0);
f = 1;
}else{
flag.push_back(1);
f=0;
}
}
num1 = num1>>1;
num2 = num2>>1;
}
while(num1!=0){
int temp = num1&1;
if(f == 1){
if(temp == 1){
flag.push_back(0);
f = 1;
}else{
flag.push_back(1);
f = 0;
}
}else{
flag.push_back(temp);
}
num1 = num1>>1;
}
while(num2!=0){
int temp = num2&1;
if(f == 1){
if(temp == 1){
flag.push_back(0);
f = 1;
}else{
flag.push_back(1);
f = 0;
}
}else{
flag.push_back(temp);
}
num2 = num2>>1;
}
if(f == 1){
flag.push_back(1);
f = 1;
}
int sum = 0;
for(int i = 0;i<flag.size();i++){
if(flag[i]==1){
sum = sum|(1<<i);
}
}
return sum;
}
//方法2：1.两个数异或：相当于每一位相加，而不考虑进位；
2.两个数相与，并左移一位：相当于求得进位；
3.将上述两步的结果相加
while(num2!=0){
int sum = num1^num2;
int c = (num1&num2)<<1;
num1 = sum;
num2 =c;
}
return num1;
剑指：方法2一样
字符串转整数
我的：
int StrToInt(string str) {
int length = str.size();
if(length == 0) return 0;
bool flag = true;
int result = 0;
for(int i = 0 ;i<length;i++){
if(i==0&&(str[i]=='-'||str[i]=='+')){
if(str[i]=='-') flag =false;
}else{
if(str[i]<'0'||str[i]>'9') return 0;
result = result * 10 + str[i]-'0';
}
}
return flag?result:-result;
}
剑指：
enum Status{kValid = 0,kInvalid};
int g_nStatus = kValid;
int StrToInt(string str) {
g_nStatus = kInvalid;
long long num = 0;
const char* cstr = str.c_str();
if( (cstr != NULL) && (*cstr != '\0') )
{
int minus = 1;
if(*cstr == '-')
{
minus = -1;
cstr++;
}
else if(*cstr == '+')
cstr++;
while(*cstr != '\0')
{
if(*cstr > '0' && *cstr < '9')
{
g_nStatus = kValid;
num = num*10 + (*cstr -'0');
cstr++;
if( ((minus>0) && (num > 0x7FFFFFFF)) ||
((minus<0) && (num > 0x80000000)) )
{
g_nStatus = kInvalid;
num = 0;
break;
}
}
else
{
g_nStatus = kInvalid;
num = 0;
break;
}
}
if(g_nStatus == kValid)
num = num * minus;
}
return (int)num;
}
};
数组中重复的数字
我的：
//方法1：
bool duplicate(int numbers[], int length, int* duplication) {
if(length<=1) return false;
vector<int> flag(length, 0);
for(int i = 0; i<length;i++){
if(++flag[numbers[i]]>1) {
*duplication = numbers[i];
return true;
}
}
return false;
}
剑指：
/*
1、判断输入数组有无元素非法
2、从头扫到尾，只要当前元素值与下标不同，就做一次判断,numbers[i]与numbers[numbers[i]]，相等就认为找到了
重复元素，返回true,否则就交换两者，继续循环。直到最后还没找到认为没找到重复元素，返回false
*/
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(length<=0||numbers==NULL)
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]])
{
*duplication = numbers[i];
return true;
}
//交换numbers[i]和numbers[numbers[i]]
int temp = numbers[i];
numbers[i] = numbers[temp];
numbers[temp] = temp;
}
}
return false;
}
构建乘积数组
我的：不会
//方法1：先计算下三角，再计算上三角，记得保存中间值
vector<int> multiply(const vector<int>& A) {
int length = A.size();
vector<int> B(length,0);
if(A.size()<1) return B;
B[0] = 1;
for(int i = 1 ;i<length;i++){
B[i] = B[i-1]*A[i-1];
}
int temp = 1;
for(int i = length-2 ;i>=0;i--){
temp = temp*A[i+1];
B[i] = temp*B[i];
}
return B;
}
//版本2：
vector<int> multiply(const vector<int>& A) {
int length = A.size();
vector<int> B;
if(A.size()<1) return B;
B.push_back(1);
for(int i = 1 ;i<length;i++){
B.push_back(B.back()*A[i-1]);
}
int temp = 1;
for(int i = length-2 ;i>=0;i--){
temp = temp*A[i+1];
B[i] = temp*B[i];
}
return B;
}
剑指：一样
正则表达式匹配
我的：
bool match(char* str, char* pattern)
{
if(*str=='\0'&&*pattern=='\0') return true;
if(*str!='\0'&&*pattern=='\0') return false;
if(*(pattern+1)=='*'){
if(*str!='\0'){
if(*str == *pattern||(*pattern=='.')){
return match(str, pattern+2) || match(str+1, pattern);
}else{
return match(str, pattern+2);
}
}else{
return match(str, pattern+2);
}
}else{
if(*str=='\0') return false;
if(*str == *pattern||*pattern=='.')
return match(str+1, pattern+1);
else return false;
}
return false;
}
//版本2：
if(*str=='\0'&&*pattern=='\0') return true;
if(*str!='\0'&&*pattern=='\0') return false;
if(*(pattern+1)=='*'){
if(*(pattern)=='.'&&*str!='\0'||*str==*pattern)
return match(str+1,pattern)|| match(str,pattern+2);
else
return match(str,pattern+2);
}else {
if(*(pattern)=='.'&&*str!='\0'||*str==*pattern)
{
return match(str+1,pattern+1);
}
return false;
}
剑指：
if(*str=='\0'&&*pattern=='\0') return true;
if(*str!='\0'&&*pattern=='\0') return false;
if(*(pattern+1)=='*'){
if(*(pattern)=='.'&&*str!='\0'||*str==*pattern)
return match(str+1,pattern)|| match(str,pattern+2)||match(str+1,pattern+2);
else
return match(str,pattern+2);
}else {
if(*(pattern)=='.'&&*str!='\0'||*str==*pattern)
{
return match(str+1,pattern+1);
}
return false;
}
表示数值的字符串
我的：
//方法1：
bool isNumeric(char* string)
{
bool markflag = true;
bool pointflag = true;
bool resultflag = true;
bool eflag = true;
int count = 0;
while(*string!='\0'){
if(*string!='-'&&*string!='+'&&*string!='e'&&*string!='E'&&*string!='.'&&(*string<'0'||*string>'9')) return false;
if(count == 0) {
count++;
markflag = false;
if(*string=='+'||*string=='-'||(*string>'0'&&*string<'9')){
string++;
continue;
}
return false;
}
if(*string=='.'){
if(!pointflag)return false;
pointflag =false;
markflag = false;
}
if(*string=='e'||*string=='E'){
if(!eflag) return false;
eflag = false;
if(*(string+1)=='\0') return false;
if(*(string+1)=='-'||*(string+1)=='+'){
markflag = true;
}
pointflag =false;
}
if(*string=='-'||*string=='+'){
if(!markflag) return false;
}
string++;
}
return true;
}
剑指：
private int index = 0;
public boolean isNumeric(char[] str) {
if (str.length < 1)
return false;
boolean flag = scanInteger(str);
if (index < str.length && str[index] == '.') {
index++;
flag = scanUnsignedInteger(str) || flag;
}
if (index < str.length && (str[index] == 'E' || str[index] == 'e')) {
index++;
flag = flag && scanInteger(str);
}
return flag && index == str.length;
}
private boolean scanInteger(char[] str) {
if (index < str.length && (str[index] == '+' || str[index] == '-') )
index++;
return scanUnsignedInteger(str);
}
private boolean scanUnsignedInteger(char[] str) {
int start = index;
while (index < str.length && str[index] >= '0' && str[index] <= '9')
index++;
return start < index; //是否存在整数
}
字符流中第一个不重复的字符
我的：
//方法1：
int flag[256]; //我的编译可以 vector<int> flag(256,0); 牛客的不行
queue<char> temp;
//Insert one char from stringstream
void Insert(char ch)
{
flag[ch]++;
if(flag[ch]==1){
temp.push(ch);
}else{
while(!temp.empty()&&flag[temp.front()]>1){
temp.pop();
}
}
}
//return the first appearence once char in current stringstream
char FirstAppearingOnce()
{
if(temp.empty()){
return '#';
}else{
return temp.front();
}
}
//方法2：
剑指：
链表中环的入口结点
我的：
//方法1：hash
bool find(vector<ListNode*> nodes, ListNode* node){
vector<ListNode*>::iterator temp ;
for(temp=nodes.begin();temp!=nodes.end();temp++){
if(*temp == node ) return true;
}
return false;
}
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
if(pHead==NULL) return NULL;
vector<ListNode*> nodes;
ListNode* temp = pHead;
while(temp!=NULL){
if(!find(nodes,temp)) nodes.push_back( temp);
else return temp;
temp=temp->next;
}
return NULL;
}
//方法2：set
ListNode* EntryNodeOfLoop(ListNode* pHead)
{ ListNode* result;
set<ListNode*> r;
while(pHead!=NULL){
if(!r.insert(pHead).second){
return pHead;
}
pHead=pHead->next;
}
return NULL;
}
//方法3：一个走快一个走慢，两倍速度，相遇第一次，思路：leetcode上也有这道题，具体思想是，两个指针fast和slow，fast以slow两倍速度前进，如果没有环，那么fast和slow不会相遇此时返回null；如果有环，那fast和slow肯定会再次相遇相遇的时候，fast刚好比slow多走了一圈环的长度。 用图来描述下，当fast与slow相遇时，fast走过的距离为a + b + c + b，而slow走过的距离为a + b，因为fast是slow速度的两倍，则有a+b+c+b = 2*(a+b)，登出a=c;此时slow节点所处X处到环起点Y处的距离a和X节点到Y处距离c其实是相等的，此时第三个指针p从x处，以和slow指针相同的速度前进，当它两相遇时，即为环的起点Y处！
ListNode* EntryNodeOfLoop(ListNode* pHead)
{
if(pHead==NULL) return NULL;
ListNode* fast = pHead;
ListNode* slow = pHead;
while(fast!=NULL&&fast->next!=NULL){
fast = fast->next->next;
slow = slow->next;
if(fast==slow) {
slow = pHead;
while(fast!=slow){
fast = fast->next;
slow = slow->next;
}
return slow;
}
}
return NULL;
}
剑指：
1.先找是否有环
2.找出环中节点个数n
3.两个指针节点，一个先走n步，一个再走，会在入口处相遇
public ListNode EntryNodeOfLoop(ListNode pHead)
{
if(pHead==null)
return null;
if(pHead.next==null)
return null;
//先找出是否有环
ListNode low = pHead;
ListNode fast = pHead;
do{
if(fast==null){
break;
}
if(low.next!=null)
low = low.next;
if(fast.next!=null)
fast = fast.next.next;
}while(fast!=low);
//如果fast正常走到链表尾部，说明没有环
if(fast==null){
return null;
}
//保存环中的当前的这个节点，寻找环中节点的个数，环中节点的个数等于从当前节点走一圈又回来
ListNode temp = fast;
int count = 0;
do{
fast = fast.next;
count = count +1;
}while(temp!=fast);
//环中有count个节点，fast先走count次，low开始走，会在入口处相遇
low = pHead;
fast = pHead;
for(int i=1;i<=count;i++)
fast = fast.next;
while(low!=fast){
low = low.next;
fast = fast.next;
}
return low;
}
