4.25

1、46全排列——递归

class Solution {
public:
    vector<vector<int>>result;
    void func(vector<int>& nums, vector<int>& current, vector<bool>visit)
    {
        int len = nums.size();
        if (current.size() == len)
        {
            result.push_back(current);
        }
        else
        {
            for (int i = 0; i < len; i++)
            {
                if (visit[i])
                {
                    current.push_back(nums[i]);
                    visit[i] = false;
                    func(nums, current, visit);
                    visit[i] = true;
                    current.pop_back();
                }
            }
        }
    }
    vector<vector<int>> permute(vector<int>& nums) {
        if (nums.size() == 0)return {};
        if (nums.size() == 1)return { nums };
        int len = nums.size();
        vector<int>current;
        vector<bool>visit(len, true);
        func(nums, current, visit);
        return result;
    }
};

2、21合并两个升序链表——递归

struct ListNode {

	int val;
	ListNode* next;
	ListNode(int x) : val(x), next(NULL) {}
};

class Solution
{
public:
	ListNode* mergeTwoLists(ListNode* L1, ListNode* L2)
	{
		if (L1 == nullptr)return L2;
		if (L2 == nullptr)return L1;
		if (L1->val <= L2->val)
		{
			L1->next = mergeTwoLists(L1->next, L2);
			return L1;
		}
		else
		{
			L2->next = mergeTwoLists(L1, L2->next);
			return L2;
		}
	}
};
3、26.删除排序数组中的重复项
```cpp
class Solution
{
public:
	int removeDuplicates(vector<int>& nums)
	{
		int ret = nums.size();
		if (ret < 2)return ret;
		int cout = 0;
		for (int i = 0; i < ret; i++)
		{
			if (nums[i] != nums[cout])
			{
				cout++;
				nums[cout] = nums[i];
			}
		}
		nums.resize(cout + 1);
		return cout + 1;
	}
};

4、27.移除元素——原地修改通常考虑重新设置计数指针对数组进行原地覆盖

//1法
class Solution

{
public:
	int removeElement(vector<int>& nums, int val)
	{
		for (int i = 0; i < nums.size(); i++)
		{
			if (nums[i] == val)
			{
				nums.erase(nums.begin() + i);
				i--;
			}
		}
		return nums.size();
	}
};
//2法
class Solution
{
public:

	int removeElement(vector<int>& nums, int val)
	{
		int ret = nums.size();
		int j = 0;
		for (int i = 0; i < ret; i++)
		{
			if (nums[i] != val)
			{
				nums[j] = nums[i];
				j++;
			}
		}
		nums.reserve(j);
		return j;
	}

};

5、35搜素插入位置————有序表的二分法查找位置

class Solution
{
public:
	int searchInsert(vector<int>& nums, int target)
	{
		int low = 0, high = nums.size() - 1;
		if (target < nums[low])return 0;
		if (target > nums[high])return nums.size();
		while ((high - low) != 1) {
			int middle = (low + high) / 2;
			if (nums[middle] < target)low = middle;
			if (nums[middle] > target)high = middle;
			if (nums[middle] == target)return middle;
		}
		if (target == nums[low])return low;
		else return high;
	}

};

6、53最大子序和

//动态规划的方法
class Solution

{

public:

????????int maxSubArray(vector<int>& nums)

????????{

???????????????int len = nums.size();

???????????????vector<int> v(len,0);

???????????????v[0] = nums[0];

???????????????int maxsum = v[0];

???????????????for (int i = 1; i < len; i++)

???????????????{

???????????????????????v[i] = max(v[i - 1] + nums[i], nums[i]);

???????????????????????if (v[i] > maxsum)maxsum = v[i];

???????????????}

???????????????return maxsum;

????????}

};
//贪心法解题
class Solution

{

public:

????????int maxSubArray(vector<int>& nums)

????????{

???????????????int len = nums.size();

???????????????int maxsum = 0, temp = 0;

???????????????for (int i = 0; i < len; i++)

???????????????{

???????????????????????temp += nums[i];

???????????????????????if (temp > maxsum)maxsum = temp;

???????????????????????if (temp < 0)temp = 0;

???????????????}

???????????????return maxsum;

????????}

};


int main()

{

????????vector<int>v1 = { -2,1,-3,4,-1,2,1,-5,4 };

????????Solution c;

????????cout << c.maxSubArray(v1);

????????return 0;

}

4.25

原文：https://www.cnblogs.com/wfplingyun/p/12773985.html