[关闭]
@thousfeet 2018-02-25T21:09:03.000000Z 字数 4032 阅读 1026

来刷题啊 2.25（动态规划、vector）

LeetCode

看了正月点灯笼的动规，觉得挺有意思的qvq，动规的思想经常就是在于 “选或不选”
回头如果复习DP时候有闲工夫可以看看这个：https://www.bilibili.com/video/av18512769/

198. House Robber

You are a professional robber planning to rob houses along a street. Each house has a certain amount of money stashed, the only constraint stopping you from robbing each of them is that adjacent houses have security system connected and it will automatically contact the police if two adjacent houses were broken into on the same night.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.

这其实就是视频里提到的一题，找一串两两不相邻的数使得和最大

【思路】
dp[i]存的是从起始到 i 这个位置能得到的最大和，对于 i 这个位置有：
1. 选。dp[i] = dp[i-2]+nums[i] （因为不能相邻，要选 i 的话那之前的和最多就只能拿到 i-2 的位置）
2. 不选。dp[i] = dp[i-1]

【代码】

  1. int rob(int* nums, int numsSize) {
  2.     if(numsSize == 0) return 0;
  3.     if(numsSize == 1) return nums[0];
  4.     int dp[numsSize];
  5.     memset(dp,0,sizeof(dp));
  6.     dp[0] = nums[0];
  7.     dp[1] = max(nums[0], nums[1]);
  8.     for(int i = 2; i < numsSize; i++)
  9.         dp[i] = max(dp[i-1],dp[i-2]+nums[i]);
  10.     return dp[numsSize-1];
  11. }

121. Best Time to Buy and Sell Stock

Say you have an array for which the ith element is the price of a given stock on day i.

If you were only permitted to complete at most one transaction (ie, buy one and sell one share of the stock), design an algorithm to find the maximum profit.

Example 1:

Input: [7, 1, 5, 3, 6, 4]
Output: 5

max. difference = 6-1 = 5 (not 7-1 = 6, as selling price needs to be larger than buying price)

Example 2:

Input: [7, 6, 4, 3, 1]
Output: 0

In this case, no transaction is done, i.e. max profit = 0.

【思路】
就只要一路遍历，每次找到历史最低点去和它做差取最大就好了。
这题就是上次那个收手续费的股市操作简简简化版。

【代码】

  1. int maxProfit(int* prices, int pricesSize) {
  2.     int low = INT_MAX;
  3.     int ans = 0;
  4.     for(int i = 0; i < pricesSize; i++)
  5.     {
  6.         if(prices[i] < low) low = prices[i];
  7.         else ans = max(ans,prices[i]-low);
  8.     }
  9.     return ans;
  10. }

139. Word Break

Given a non-empty string s and a dictionary wordDict containing a list of non-empty words, determine if s can be segmented into a space-separated sequence of one or more dictionary words. You may assume the dictionary does not contain duplicate words.

For example, given
s = "leetcode",
dict = ["leet", "code"].

Return true because "leetcode" can be segmented as "leet code".

显然不是扫一遍那样简单，因为会有比如 leetscode 然后字典是 leets/leet/scode ，可能在前面匹配中多吃掉几位导致后面不能匹配的情况。
只想到O(n^2)的打法又因为没给数据范围一直不敢打，又没想到更好的做法纠结了超级久，没想到看了眼discuss跟自己想的一毛一样人家还是fast solution……果然自己还是怂（）

【思路】
用 bool dp[i] 表示从起始到 i-1 这串是否能匹配。当看到一个新的位置的时候显然就要拿它跟之前所有为 1 的区段间都拿出来去字典里找一下有没有，如果有就可以匹配。
之所以用 i-1 不用 i 是因为要放一个前置的 true 才能保证最开始那段也能正常判而不用特判。

【代码】

  1. bool wordBreak(string s, vector<string>& wordDict) {
  2.     vector<bool> dp(s.length()+1,0);
  3.     dp[0] = true;
  5.     for(int i = 1; i <= s.length(); i++)
  6.     {
  7.         for(int j = i-1; j >= 0; j--)
  8.         {
  9.             if(dp[j] == 1) 
  10.             {
  11.                 string sub = s.substr(j,i-j);
  12.                 if(find(wordDict.begin(),wordDict.end(),sub) != wordDict.end()) 
  13.                 {
  14.                     dp[i] = 1;
  15.                     break;
  16.                 }
  17.             }
  18.         }   
  19.     }
  20.     return dp[s.length()];  
  21. }

这里算是新学了 c++ 的 vector，之前一直逃避硬拿数组模拟，但是一看到 c 语言的 char ** 我就...算了还是 vector 吧...

C++STL vector

1.声明和初始化

  1.     vector<int> vec;        //声明一个int型向量
  2.     vector<int> vec(5);     //声明一个初始大小为5的int向量
  3.     vector<int> vec(10, 1); //声明一个初始大小为10且值都是1的向量
  4.     vector<int> vec(tmp);   //声明并用tmp向量初始化vec向量
  5.     vector<int> tmp(vec.begin(), vec.begin() + 3);  //用向量vec的第0个到第2个值初始化tmp
  6.     int arr[5] = {1, 2, 3, 4, 5};   
  7.     vector<int> vec(arr, arr + 5);      //将arr数组的元素用于初始化vec向量，注意：其中不包括arr[4]元素，末尾指针都是指结束元素的下一个元素，

2.基本操作

(1). 容量

向量大小： vec.size();
向量最大容量： vec.max_size();
更改向量大小： vec.resize();
向量真实大小： vec.capacity();
向量判空： vec.empty();
减少向量大小到满足元素所占存储空间的大小： vec.shrink_to_fit(); //shrink_to_fit

(2). 修改

多个元素赋值： vec.assign(); //类似于初始化时用数组进行赋值
末尾添加元素： vec.push_back();
末尾删除元素： vec.pop_back();
任意位置插入元素： vec.insert();
任意位置删除元素： vec.erase();
交换两个向量的元素： vec.swap();
清空向量元素： vec.clear();

(3)迭代器

开始指针：vec.begin();
末尾指针：vec.end(); //指向最后一个元素的下一个位置
指向常量的开始指针： vec.cbegin(); //意思就是不能通过这个指针来修改所指的内容，但还是可以通过其他方式修改的，而且指针也是可以移动的。
指向常量的末尾指针： vec.cend();

(4)元素的访问

下标访问： vec[1]; //并不会检查是否越界
at方法访问： vec.at(1); //以上两者的区别就是at会检查是否越界，是则抛出out of range异常
访问第一个元素： vec.front();
访问最后一个元素： vec.back();
返回一个指针： int* p = vec.data(); //可行的原因在于vector在内存中就是一个连续存储的数组，所以可以返回一个指针指向这个数组。这是是C++11的特性。

3.算法

遍历

  1. vector<int>::iterator it;
  2. for (it = vec.begin(); it != vec.end(); it++)
  3.     cout << *it << endl;
  4. //或者
  5. for (size_t i = 0; i < vec.size(); i++) {
  6.     cout << vec.at(i) << endl;
  7. }

翻转

  1.     #include <algorithm>
  2.     reverse(vec.begin(), vec.end());

排序

  1.     #include <algorithm>
  2.     sort(vec.begin(), vec.end()); //采用的是从小到大的排序
  3.     //如果想从大到小排序，可以采用上面反转函数，也可以采用下面方法:
  4.     bool Comp(const int& a, const int& b) {
  5.         return a > b;
  6.     }
  7.     sort(vec.begin(), vec.end(), Comp);

查找元素

  1. if(find(v.begin(), v.end(), val) != v.end()){...} //val为待查找元素
添加新批注
在作者公开此批注前，只有你和作者可见。
回复批注