leeyupeng

leeyupeng@126.com

0%

发表于 更新于 分类于 ， 阅读次数： Valine：

零钱兑换

322.零钱兑换

公式

dp[i] = Math.min(dp[i], dp[i - coin] + 1)

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
class Solution {
	public:
		int dp(vector<int>& d, vector<int>& coins,int n)
		{
			if (d[n] != -2)
			{
				return d[n];
			}
			else
			{
				d[n] = -1;
			}
			int i = 0;
			int j = 0;
			for (i = coins.size() - 1; i >= 0; i--)
			{
				j = n - coins[i];
				if (j >= 0)
				{
					int dpj = dp(d,coins,j);
					if (dpj != -1)
					{
						if (d[n] == -1)
						{
							d[n] = dpj + 1;
						}
						else if (d[n] > dpj + 1)
						{
							d[n] = dpj + 1;
						}
					}
				}
			}

			return d[n];
		}
		int coinChange(vector<int>& coins, int amount) {
			vector<int> d(amount + 1);
			d[0] = 0;
			for (int i = 1; i < amount + 1; i++)
			{
				d[i] = -2;
			}

			return dp(d,coins,amount);
		}
	};
阅读全文 »

发表于 更新于 阅读次数： Valine：

搜索

广度优先搜索(BFS)

深度优先搜索(DFS)

全排列搜索

0/1搜索

阅读全文 »

发表于 更新于 分类于 ， 阅读次数： Valine：

正则表达式

题目

- 44. 通配符匹配

递归式动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
class Solution {
public:
  string ss;
  string pp;
  map<int, bool>* m=new std::map<int, bool>();
  bool isMatchRecursive( int i, int j)
  {
    int key = i * (ss.length() + 10) * (pp.length() + 10)+ j;
    if (m->find(key) != m->end())
    {
      return m->at(key);
    }
    bool value = false;
    if (j < 0)
    {
      if (i < 0)
      {
        value = true;
      }
      else
      {
        value = false;
      }
    }
    else if (i < 0)
    {
      if (pp[j] == '*')
      {
        value = isMatchRecursive( i, j - 1);
      }
      else
      {
        value = false;
      }
    }
    else if (pp[j] == '*')
    {
      value = isMatchRecursive(i,j - 1) || isMatchRecursive(i - 1,j);
    }
    else if (ss[i] == pp[j] || pp[j] == '?')
    {
      value = isMatchRecursive( i - 1, j - 1);
    }
    else
    {
      value = false;
    }
    m->insert({ key,value });
    return value;
  }
  bool isMatch(string s, string p) {
    ss = s;
    pp = p;
    bool result = isMatchRecursive( ss.length() - 1, pp.length() - 1);
    return result;
  }
};
阅读全文 »

发表于 更新于 分类于 ， 阅读次数： Valine：

分享巧克力

描述

你有一大块巧克力，它由一些甜度不完全相同的小块组成。我们用数组 sweetness 来表示每一小块的甜度。

你打算和 K 名朋友一起分享这块巧克力，所以你需要将切割 K 次才能得到 K+1 块，每一块都由一些 连续 的小块组成。

为了表现出你的慷慨，你将会吃掉 总甜度最小 的一块，并将其余几块分给你的朋友们。

请找出一个最佳的切割策略，使得你所分得的巧克力 总甜度最大，并返回这个 最大总甜度。

输入： sweetness = [1,2,3,4,5,6,7,8,9], K = 5
输出： 6
解释： 你可以把巧克力分成 [1,2,3], [4,5], [6], [7], [8], [9]。 。

输入： sweetness = [5,6,7,8,9,1,2,3,4], K = 8
输出： 1
解释： 只有一种办法可以把巧克力分成 9 块。

阅读全文 »

发表于 阅读次数： Valine：

算法

  • Search − Algorithm to search an item in a data structure.
  • Sort − Algorithm to sort items in a certain order.
  • Insert − Algorithm to insert item in a data structure.
  • Update − Algorithm to update an existing item in a data structure.
  • Delete − Algorithm to delete an existing item from a data structure.

算法复杂度

时间复杂度

空间复杂度

阅读全文 »

发表于 更新于 分类于 ， 阅读次数： Valine：

poj.1745.Divisibility

poj.1745.Divisibility

问题描述

给N个数字和一个K，把N个数字加加减减后得到的数字是否能整除K。

问题分析

0/1背包相关问题

公式

dp[j] = dp[(j - v[i]) % k] || dp[(j + v[i]) % k]

动态规划

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
#include <iostream>
#include <vector>
using namespace std;

bool isDivisibility(vector<int>& v, int n, int k)
{
	vector<bool>* dp = new vector<bool>(k);
	vector<bool>* dptemp = new vector<bool>(k);
	(*dp)[0] = true;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < k; j++)
		{
			(*dptemp)[j] = (*dp)[((j - v[i]) % k + k) % k] || (*dp)[((j + v[i]) % k + k) % k];
		}

		vector<bool>* temp = dp;
		dp = dptemp;
		dptemp = temp;
	}

	return (*dp)[0];
}

int main()
{
	int n, k;
	cin >> n >> k;
	vector<int> v(n);
	for (int i = 0; i < n; i++)
	{
		cin >> v[i];
	}

	bool result = isDivisibility(v,n,k);
	cout<< (result ? "Divisible" : "Not divisible")<<endl;
	return 0;
}
阅读全文 »

发表于 更新于 分类于 ， 阅读次数： Valine：

贪心算法

  • 描述

    贪心算法的解不一定是最优解

    但是贪心算法的解有用途，可以作为DFS的剪枝条件,搜索过程中解大于贪心算法的解时break

  • 问题

    活动选择问题，
钱币找零问题，
再论背包问题，
小船过河问题，
区间覆盖问题，
销售比赛，
Huffman编码，
Dijkstra算法（求解最短路径），
最小生成树算法
阅读全文 »