8. 给定一个无序数组，建一个最大堆。

priority_queue>这个是堆的表达式
code

class Solution {
public:
    vector GetLeastNumbers_Solution(vector input, int k) {
        //采用最小堆的方式
        vector arr;
        if(input.size()==0||k==0||k>input.size())
            return arr;
        priority_queue> que;//实现优先队列的数据结构，底层实现堆实现 priority_queue Type为数据类型，Container为保存数据的容器，Functional为元素比较方式，若不写后两个元素，则容器默认是vector，比较方式默认用operator<,也就是优先队列是大顶堆，队头元素最大。
        for(auto x:input)
        {
            if(que.size()que.top())
                {
                    que.pop();
                    que.push(x);
                }
            }
        }
        
        while(!que.empty())
        {
            arr.push_back(que.top());
            que.pop();
        }
        return arr;

    }
};

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

题目

方法一：多开辟一个数组的方法
code

class Solution {
public:    /**     * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可     *     *
		   * @param array int整型vector      * @return int整型vector     */
	vector reOrderArray(vector& array)
	{
		if (array.size() == 0)
			return array;
		vector num(array.size());
		int head = 0;
		int tail = array.size() - 1;
		int index_head = head;
		int index_tail = tail;
		while (head < array.size() && tail >= 0)
		{
			if (array[head] % 2 == 1)
			{
				num[index_head] = array[head];
				index_head++;
			}
			head++;
			if (array[tail] % 2 == 0)
			{
				num[index_tail] = array[tail];
				index_tail--;
			}
			tail--;
		}
		return num;
	}
};

方法二：用一个i来放奇数，不断移动该值。
思路：进行一次遍历，若得到当前数为奇数的话，则将该数到真正存放奇数部分的那一位的后面一位的前部数，都往后移。这样，就相当于把所有的技术都放在前面了。
code

class Solution {
public:
	void reOrderArray(vector& array)
	{
		int i = 0;
		for (int j = 0; j < array.size(); j++)
		{
			if (array[j] & 1)//表示是奇数的话         
			{
				int temp = array[j];//先将该奇数进行赋值  
				for (int k = j - 1; k >= i; --k)//从该奇数的位置，到要存放奇数的i位置  
				{
					array[k + 1] = array[k];//不断的向后移动 
				}
				array[i++] = temp;//然后，将该temp值赋值给放奇数的这个位置    
			}
		}
	}
};

11.旋转链表

题目

思路：先收尾相连，然后在最后面的那个指针向前移动k个位置，移到那个位置后，断开当前链表。**注意一点点是若k的大小大于这个链表的长度的话，则哟啊进行取余的操作。
code

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* rotateRight(ListNode* head, int k) {
        if(k==0||head==nullptr||head->next==nullptr)
            return head;
        int n = 1;
        ListNode* node = head;
        while(node->next!=nullptr)//通过这个可以计算出当前有多少元素
        {
            node = node->next;
            n++;
        }
        int add = n-k%n;
        if(add==n)//若需要左移的元素刚好是n的整数倍
            return head;
        node->next = head;//收尾相连
        while(add--)//根据这个，移到要断开的那个位置
        {
            node = node->next;
        }
        ListNode *ret = node->next;
        node->next  = nullptr;
        return ret;
    }
};

题解
这题有几个点：

1. 首先，将链表首尾相连
2. 得出链表有多少个元素。
3. 注意移动的元素的数量有可能大于n.所以要取余。
4. 注意，这里的这个add，移动的个数是n-k。

12. 求一个数组最大递减子数组，要求返回数组

思路：在这个的基础上修改一下就可以了。首先，dp[0]为数组的第一个元素，接下来，dp[i] = max(arr[i-1],dp[i-1]+arr[i-1])哪个更大。然后，还要比较一下之前的最大值，和现在形成的最大值。
code

class Solution {
public:
	int FindGreatestSumOfSubArray(vector array)
	{
		int size = array.size();
		vector dp(size + 1, 1);
		dp[0] = 0;
		int ret = array[0];//ret作为返回值    
		for (int i = 1; i <= size; i++)//由第一个元素到最后一个元素 
		{
			dp[i] = max(array[i - 1], dp[i - 1] + array[i - 1]);//判断加上这个元素更大，还是不加更大 
			ret = max(ret, dp[i]);
		}
		return ret;
	}
};

13. 完全二叉树怎么判断？

思路:转变思路，如何判断该树不是完全二叉树，就是层序遍历已经输出null节点了，后面却还有节点。
code

class Solution
{
public:
	bool isCompleteTree(TreeNode* root)
	{
		queue q;
		bool reachNull = false;
		q.push(root);
		while (!q.empty())
		{
			TreeNode* cur = q.front();
			q.pop();
			if (cur == nullptr)
			{
				reachNull = true;
				continue;
			}
			else
			{
				if (reachNull)
				{
					return false;
				}
				q.push(cur->left);
				q.push(cur->right);
			}
		}
		return true;
	}
};

15. 链表中将所有的偶数移到奇数后面不改变原来的相对位置？

code

ListNode* oddEvenList(ListNode* head)
{
	if (head == nullptr || head->next == nullptr)
		return head;
	ListNode* q = NULL;
	ListNode* p = head;
	while (p)
	{
		if (p->val & 1)
		{
			if (q == NULL)
			{
				swap(head->val, p->val);
					q = head;
			}
			else
			{

				q = q->next;//相当于q所指的位置，就是所有奇数的最后一位 
					swap(q->val, p->val);
			}
		}
		p = p->next;
	}
	return head;
}

16. LCS最大子序列问题

17. 字母的全排列

code

class Solution {
public:
	set tempRes;//为了剔除掉重复的，所以用set 
	vector Permutation(string str)
	{
		vector strOut;
		if (str.size() == 0)
			return strOut;
		Recursion(str, 0);
		for (auto x : tempRes)
		{
			strOut.push_back(x);
		}
		return strOut;
	}
	/*    void swap(string str,int r,int k)
		 {
		 char temp = str[k];
		 str[k] = str[r];
		 str[r] = temp;
		 }
		 */
	void Recursion(string str, int index)
	{
		if (index == str.size() - 1)//这个只是为了把最后一个也放进去，然后回溯的时候就会把该放的放进去 
			tempRes.insert(str);
		for (int i = index; i < str.size(); i++)
		{
			swap(str[index], str[i]);
			Recursion(str, index + 1);
		}
	}
};

18. 判断回文链表？

题目

code

class Solution {
public:
	bool isPalindrome(ListNode* head)
	{

		if (head == nullptr)
		{
			return true;
		}
		// 找到前半部分链表的尾节点并反转后半部分链表  
		ListNode* firstHalfEnd = endOfFirstHalf(head);//先使用快慢指针找到中间节点 
		ListNode* secondHalfStart = reverseList(firstHalfEnd->next);//将该节点后面的所有节点进行翻转  
																	// 判断是否回文   
		ListNode* p1 = head;
		ListNode* p2 = secondHalfStart;
		bool result = true;
		while (result && p2 != nullptr)
		{
			if (p1->val != p2->val)
			{
				result = false;
			}
			p1 = p1->next;
			p2 = p2->next;
		}
		// 还原链表并返回结果    
		firstHalfEnd->next = reverseList(secondHalfStart);
		return result;
	}
	ListNode* reverseList(ListNode* head)
	{
		ListNode* prev = nullptr;
		ListNode* curr = head;
		while (curr != nullptr)
		{
			ListNode* nextTemp = curr->next;//先储存下这个next节点 
			curr->next = prev;//将指针进行反转 
			prev = curr;//把cur变成pre,把next变成cur 
			curr = nextTemp;
		}
		return prev;
	}
	ListNode* endOfFirstHalf(ListNode* head)
	{//返回的是链表中间节点的指针   
		ListNode* fast = head;
		ListNode* slow = head;
		while (fast->next != nullptr && fast->next->next != nullptr)
		{
			fast = fast->next->next;
			slow = slow->next;
		}
		return slow;
	}
};

19. 反转链表

code

/*struct ListNode {	int val;	struct ListNode *next;	ListNode(int x) :			val(x), next(NULL) {	}};*/class Solution {
public:
	ListNode* ReverseList(ListNode* pHead)
	{
		ListNode* pReversedHead = NULL;
		ListNode* pNode = pHead;
		ListNode* pPrev = NULL;
		while (pNode != NULL)
		{
			ListNode* pNext = pNode->next;
			if (pNext == NULL)//这时只有一个节点的情况 
				pReversedHead = pNode;
			pNode->next = pPrev;
			pPrev = pNode;
			pNode = pNext;
		}
		return pReversedHead;
	}
};

20、 二叉树的序列化和反序列化

21. 返回峰值

22. 写生成堆的代码

code

#include 
#include 
#include  
using namespace std;

void adjustHeap(std::vector& in, int i, int size);
void heapBuild(std::vector& vec);
void heapSort(std::vector& in);
void swap(std::vector& in, int index1, int index2);

void swap(vector& in, int index1, int index2)
{
    int tmp = in[index1];
    in[index1] = in[index2];
    in[index2] = tmp;
}

void adjustHeap(vector& in, int i, int size)
{
    int root = i;
    int left = i * 2;
    int right = i * 2 + 1;
    int max = root;
    if (left<=size && in[left - 1]>in[max-1])
    {
        max = left;
    }
    if (right<=size && in[right - 1]>in[max - 1])
    {
        max = right;
    }
    //上面两个if做出的结果是max中的值得索引，是最大值的索引
    if (left <= size && max == left)
    {
        swap(in, root - 1, left - 1);//然后进行交换
        adjustHeap(in, left, size);//调整这一边的树就可以了，另一边不用调整
    }
    if (right<=size&&max == right)
    {
        swap(in, root - 1, right - 1);
        adjustHeap(in, right, size);
    }

}
void heapBuild(vector& vec)
{
    for (int i = vec.size() / 2; i > 0; --i)//从1/2处开始到第一个元素，逐渐调整吗
    {
        adjustHeap(vec, i, vec.size());
    }
}
void heapSort(vector& in)
{
    heapBuild(in);//第一遍，建堆
    for (int size = in.size(); size > 1; --size)
    {
        swap(in, 0, size-1);
        adjustHeap(in, 1, size-1);
    }
}

int main() {
    vector input = { 1,25,24,34,65,1,214,-89,74 };
    heapSort(input);//堆排序

    for (auto it : input) {
        cout << it << " ";
    }
    cout << endl;

    return 0;
}

23. 二叉树叶节点中的最小深度

24. 求两个数组的交集，返回交集数组

题目
给定两个数组，编写一个函数来计算它们的交集。

code

class Solution {
public:
    vector intersection(vector& nums1, vector& nums2) {
        vector arr;
        if(nums1.size()==0||nums2.size()==0)
            return arr;
        map map;
        for(int i = 0;inums2[j])
                j++;
            else if(nums1[i]

class Solution {
public:
    int lengthOfLIS(vector& nums) {
        int n = (int)nums.size();
        if(n==0)
            return 0;
        vector dp(n,0);//申请一个n的空间
        for(int i = 0 ;i

/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode() : val(0), next(nullptr) {}
 *     ListNode(int x) : val(x), next(nullptr) {}
 *     ListNode(int x, ListNode *next) : val(x), next(next) {}
 * };
 */
class Solution {
public:
    ListNode* swapPairs(ListNode* head) {
        if(head==nullptr||head->next==nullptr)
            return head;
        ListNode* newNode = head->next;
        head->next= swapPairs(newNode->next);
        newNode->next = head;
        return newNode;
    }
};

/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     TreeNode *left;
 *     TreeNode *right;
 *     TreeNode() : val(0), left(nullptr), right(nullptr) {}
 *     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
 *     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
 * };
 */
class Solution {
public:
    int minDepth(TreeNode* root) {
        if(root==nullptr)
            return 0;
        if(root->left==nullptr&&root->right==nullptr)
            return 1;
        int left = 0;
        int right = 0;
        int minDepthInt =INT_MAX;
        if(root->left)
            minDepthInt = min(minDepthInt,minDepth(root->left));
        if(root->right)
            minDepthInt = min(minDepthInt,minDepth(root->right));
        return minDepthInt+1;
    }
};

class Solution {
public:
    vector maxSlidingWindow(vector& nums, int k) {
        vector arrOut;
        if(nums.size()==0||k==0)
            return arrOut;
        int r = 1-k;
        for(int i = 0;i<=nums.size()-k;i++)
        {
            int res = nums[i];
            for(int j = i;j

class Solution {
public:
    vector maxInWindows(const vector& num, unsigned int size) {
        vector res;
        int n = num.size();
        if(num.size() dp;//双端队列
        while(high=1&&num[low-1]==dp[0])//当目前的最大元素是low-1.已经出了滑窗的话，就要出队列了
            {
                dp.pop_front();
            }
            
            while(!dp.empty()&&num[high]>dp[0])//判断是否大于dp[0]
            {
                dp.pop_front();
            }
            while(!dp.empty()&&num[high]>dp[dp.size()-1])//判断是否大于dp的最后一个元素
            {
                dp.pop_back();
            }
            dp.push_back(num[high]);//直接加入high元素
            
            if(low>=0)//dp[0]每次都是最大值，所以，直接加入，但注意，要low端滑到0的时候，才可以加入该数组
                res.push_back(dp[0]);
            low++;
            high++;
        }
        return res;
    }
};

class Solution {
public:
    int lengthOfLongestSubstring(string s) {
        if(s.size()==0)
            return 0;
        unordered_set set;
        int rk = -1;//右边界
        int res = 0;//每次求的最长子串
        for(int i = 0;i0的时候才会进行erase
            }
            while(rk+1

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        if (l1 == nullptr) {
            return l2;
        } else if (l2 == nullptr) {
            return l1;
        } else if (l1->val < l2->val) {
            l1->next = mergeTwoLists(l1->next, l2);
            return l1;
        } else {
            l2->next = mergeTwoLists(l1, l2->next);
            return l2;
        }
    }
};

class Solution {
public:
    ListNode* mergeTwoLists(ListNode* l1, ListNode* l2) {
        ListNode* preHead = new ListNode(-1);

        ListNode* prev = preHead;
        while (l1 != nullptr && l2 != nullptr) {
            if (l1->val < l2->val) {
                prev->next = l1;
                l1 = l1->next;
            } else {
                prev->next = l2;
                l2 = l2->next;
            }
            prev = prev->next;
        }

        // 合并后 l1 和 l2 最多只有一个还未被合并完，我们直接将链表末尾指向未合并完的链表即可
        prev->next = l1 == nullptr ? l2 : l1;

        return preHead->next;
    }
};

class MyStack {
public:
    queue q;
    MyStack() {

    }
    
    void push(int x) {
        q.push(x);
    }
    
    int pop() {
        int size = q.size();
        size--;
        while(size--)
        {
            q.push(q.front());//把头部的元素移到尾巴，除了最后一个元素
            q.pop();
        }
        int result= q.front();
        q.pop();
        return result;
    }
    
    int top() {
        return q.back();
    }
    
    bool empty() {
        return q.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

class MyStack {
public:
    queue que1;
    queue que2;

    MyStack() {

    }
    
    void push(int x) {
        que2.push(x);//这个就是作为一个辅助队列而已，
        while(!que1.empty())//这个是作为一个主队列
        {
            que2.push(que1.front());
            que1.pop();
        }
        swap(que1,que2);
    }
    
    int pop() {
        int r = que1.front();
        que1.pop();
        return r;

    }
    
    int top() {
        int r = que1.front();
        return r;
    }
    
    bool empty() {
        return que1.empty();
    }
};

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack* obj = new MyStack();
 * obj->push(x);
 * int param_2 = obj->pop();
 * int param_3 = obj->top();
 * bool param_4 = obj->empty();
 */

class Solution {
public:
    int findRepeatNumber(vector& nums) {
        if(nums.size()==0)
        {
            return 0;
        }
        set set;
        for(int i = 0;i

class Solution {
    public int findRepeatNumber(int[] nums) {
        Arrays.sort(nums);
        for(int i = 0;i < nums.length;i++){
            if(nums[i] == nums[i+1]){
                return nums[i];
            }
        }
        return -1;
    }
}