在长度为n的（）上，删除第一个元素，其算法的时间复杂度为O(n)

A.只有表头指针的不带表头结点的循环单链表

B.只有表尾指针的不带表头结点的循环单链表

C.只有表尾指针的带表头结点的循环单链表

D.只有表头指针的带表头结点的循环单链表
答案：A
分析：

单链表只能按单方向顺序访问节点，按题目意思，只有当A条件时，并当新元素的节点从表头插入，使得第一个元素的节点在表尾，才成立。这样表头指针顺序访问节点，访问至链表尾部时，复杂度刚好为O(n)。



对于B而言，不带头节点循环链表，表尾指针，如果是头插法则第一元素就是表尾指针rear（假设表尾指针为rear）所指的节点，即当前节点，时间复杂度为O(1)。如果是正常顺序插入节点（即非头插法），由于是循环链表，表尾指针rear指向最后一个元素，rear->next即为第一个元素（因为循环链表，表尾的next是表头，且没有头节点），时间复杂度仍然是O(1)，所以B不成立。

对于C而言，和B情况相似，多了一个表头节点，如果是头插法，则和B一样表尾指针rear所指当前元素即为第一个元素，时间复杂度为O(1)。如果是正常顺序插入节点，则比B多一个头节点，就变成rear->next->next，但时间复杂度仍然是O(1)，所以C不成立。

对于D而言，比A多一个头节点，虽然当头插法时时间复杂度为O(n+1)，根据次数化解原则，就为O(n)，但是答案不是选D（我也不是很清楚，老师讲解时直接跳过没有解释清楚，希望大佬评论解答，感激！！！）

 int a[] = {1, 2, 3, 4, 5,6};
        //第一个元素
        for (int i = 0; i <a.length; i++) {
            //第二个元素
            for (int j = i+1; j <a.length ; j++) {
                //第三个元素
                for (int k = j+1; k <a.length ; k++) {
                    System.out.print(a[i]+","+a[j]+","+a[k]+"\t");
                }
            }
            System.out.println();
        }

 

组合有几个元素，循环就有几层，循环的变量初始值按上依次+1，在最内层打印到控制台。

最后一个输出的组合的第一个元素，下标应该是数组长度减去取得的元素个数，长度5，个数2，下标则为3(下标从0开始)

-----------------------输出结果如下-----------------------------

1,2,3 1,2,4 1,2,5 1,2,6 1,3,4 1,3,5 1,3,6 1,4,5 1,4,6 1,5,6 

2,3,4 2,3,5 2,3,6 2,4,5 2,4,6 2,5,6 

3,4,5 3,4,6 3,5,6 

4,5,6 

题目：

一个长度为n的递增排序数组中的所有数字都是唯一的，并且每个数字都在范围0～n-1之内。在范围0～n-1内的n个数字中有且只有一个数字不在该数组中，请找出这个数字

示例 1:

输入: [0,1,3]
输出: 2


示例 2:

输入: [0,1,2,3,4,5,6,7,9]
输出: 8

来源：力扣（LeetCode）

链接：https://leetcode-cn.com/problems/que-shi-de-shu-zi-lcof

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

思路：

找的是第一个值不等于下标的元素    的下标

二分查找法很重要的一点就是数组不要越界！ 不要越界！ 不要越界！

j往前移和i往后移都是要注意

class Solution {
public:
    int missingNumber(vector<int>& nums) {
        int i=0;
        int j=nums.size()-1;
        while(i<=j)
        {
            int mid=(i+j)/2;
            if(nums[mid]==mid)
            {
                if(mid!=nums.size()-1)
                {
                    i=mid+1;
                }
                else
                {
                    return mid+1;
                }
            }
            else if(mid==0)
            {
                return 0;
            }
            else if(nums[mid-1]==mid-1 && mid>0)
            {
               return mid;
              // break;
            }
            else
            {
                j=mid-1;
            }
        }
        return nums[i]-1;
    }
};

 

1.问题描述：
  试在一个长度为n的数组中实现两个栈，使得二者在元素的总数目为n之前都不会溢出，并且保证push和pop操作的时间代价为O(1)。
2.完整代码如下：
/* 77.6 - C++ - 在一个长度为n的数组中实现两个栈、且共享存储区[0,max_size-1] */
/* 构栈方法 - 栈顶相向，迎面增长 */

#include <iostream>
using namespace std;

//混合顺序栈的类ArrStack 
template <typename T>
class ArrStack
{
	private:
		int top1, top2, MaxSize;       //top1 - 栈1的栈顶指针，top2 - 栈2的栈顶指针，MaxSize - 数组最大容量
		T *st;                         //存放类型为T的栈元素数组 
		
	public:
	    ArrStack(int size);           //构造函数 - 为栈预先分配空间，初始化栈顶指针 
		
		~ArrStack();                //析构函数
		
		bool push(const int i, const T item);       //入栈
		
		bool pop(const int i, T &item);             //出栈 
};

//构造函数 
template <typename T>
ArrStack<T>::ArrStack(int size)
{
	MaxSize = size;
	st = new T[MaxSize];               //给混合栈预先分配存储空间 
	top1 = -1;                         //初始化栈1指针 
	top2 = MaxSize;                    //初始化栈2指针 
} 

//析构函数 
template <typename T>
ArrStack<T>::~ArrStack()
{
	if( st != NULL )
	{
		delete [] st;              //释放new分配的内存 
		cout << "析构函数调用成功" << endl;
	} 
}

//入栈 
template <typename T>
bool ArrStack<T>::push(const int i, const T item)
{
	if( top1+1 == top2 )
	{
		cout << "栈上溢出" << endl;
		return false;
	}
	else
	{
		switch(i) 
		{
			case 1:
				st[++top1] = item;        //入栈1，先是top1++，后将item赋值给st[top1] 
				break;
			case 2:
			    st[++top2] = item;       //入栈2         
				break; 
		}
	}
	return true; 
}

//出栈
template <typename T>
bool ArrStack<T>::pop(const int i, T& item)
{
	switch(i)
	{
		case 1:
			if( top1 == -1 )
			{
				cout << "栈1下溢出" << endl;
				return false;
			}
			else
		        item = st[top1--];          //先是item = st[top1], 再是top1-- 
		    break;
		case 2:
			if( top2 == MaxSize )
			{
				cout << "栈2上溢出" << endl;
				return false;
			}
			else
			    item = st[top2--];
			break;
	}
	
	return true;
}


int main()
{
	int n, i;
	char item;
	cout << "请输入数组最大容量:";
	cin >> n;
	
	//以下为测试代码、读者可自行设计测试 
	ArrStack<char> A(n);
	
	cout << "栈1入栈 - 'a'" << endl;
	A.push(1,'a');
	cout << "栈2入栈 - 'a'" << endl;
	A.push(2,'a');
	cout << "栈1入栈 - 'b'" << endl;
	A.push(1,'b');
	
	for( i = 0; i < 2; i++ )
	{
		cout << "请输入要入栈2元素:";
		cin >> item;
		A.push(2,item); 
	}
	
	//输出栈2元素
	for( i = 0; i < 3; i++ )
	{
		A.pop(2,item);
		cout << "出栈2第" << i+1 << "个元素:" << item << endl; 
	} 
	cout << endl;
	
	return 0;
}
3.运行结果：