春节7天练 | Day 7：贪心、分治、回溯和动态规划

精选留言(25)

• 
  kai

  2019-02-11

   4

  听了老师的课程，第一遍的时候，只是在读，现在开始回顾：
  课程相关的知识点，做了笔记：https://github.com/guokaide/algorithm/blob/master/summary/algorithm.md
  课程涉及的题目，也在逐步总结当中：
  https://github.com/guokaide/algorithm/blob/master/questions/questions.md
  
  希望和大家一起进步，欢迎小伙伴们一起来讨论~
  

  展开

  编辑回复: 感谢您参与春节七天练的活动，为了表彰你在活动中的优秀表现，赠送您99元专栏通用阅码，我们会在3个工作日之内完成礼品发放，如有问题请咨询小明同学，微信geektime002。

• 
  kai

  2019-02-11

   3

  动态规划，感觉是面试必考内容，今天跟着这些题目再来复习一遍~
• 
  kai

  2019-02-11

   2

  8皇后问题
  
  public class EightQueen {
  
      private static final int QUEEN_NUMBER = 8; // 皇后个数
      private int[] columns = new int[QUEEN_NUMBER]; // 每个皇后存储的列 (row, col), row天然不相等
      private int total = 0;
  
      public int solution() {
          queen(0);
          return total;
      }
  
      private void queen(int row) {
          if (row == QUEEN_NUMBER) {
              total++;
          } else {
              for (int col = 0; col != QUEEN_NUMBER; col++) {
                  columns[row] = col;
                  if (isPut(row)) {
                      queen(row+1);
                  }
              }
          }
      }
  
      private boolean isPut(int row) {
           for (int i = 0; i != row; i++) {
               if (columns[row] == columns[i] || row - i == Math.abs(columns[row]-columns[i])) {
                   return false;
               }
           }
           return true;
      }
  
  }

  展开
• 
  Richard

  2019-02-11

   2

  老师留的题都很不错，正在刷之前没做过的LeetCode题。
  参与下答对三题送课程的活动:
  Day 1：
  1.求众数(Python)
  class Solution:
      def majorityElement(self, nums):
          return sorted(nums)[len(nums) // 2]
  2.缺失的第一个正数(Golang)
  func firstMissingPositive(nums []int) int {
      if len(nums) == 0 {
          return 1
      }
  
      var arr = make([]bool, len(nums)+1)
      var idx = 1
      for i := 0; i < len(nums); i++ {
          if nums[i] >= 0 && nums[i] < len(arr) {
              arr[nums[i]] = true
          }
      }
  
      for i := 1; i < len(arr); i++ {
          if arr[i] == false {
              idx = i
              break
          } else {
              idx = i + 1
          }
      }
  
      return idx
  }
  Day 7:
  3. 买卖股票的最佳时机(Python)
  class Solution:
      def maxProfit(self, prices):
          if not prices:
              return 0
          min_price = prices[0]
          res = 0
          for i in prices[1:]:
              min_price = min(min_price, i)
              if res < i - min_price:
                  res = i - min_price
          return res
  

  展开

  编辑回复: 感谢您参与春节七天练的活动，为了表彰你在活动中的优秀表现，赠送您99元专栏通用阅码，我们会在3个工作日之内完成礼品发放，如有问题请咨询小明同学，微信geektime002。

• 
  纯洁的憎恶

  2019-02-10

   2

  这冲刺压力有点大了😓

  展开
• 
  黄丹

  2019-02-11

   1

  课程的最后一天，也是新年上班的第一天，感谢王老师的教育和陪伴，祝您生活开心，工作顺利。
  今天的题目比前几天的都难一点，只做了三题，太累了TaT。对于动态规划和贪心总觉得很巧妙，如果想不到动态转移方程式，就很难做，但要是想到了，真的是豁然开朗。对于这一类题，还是要多锻炼，找动态转移方程式要从最后一个结果出发，去想这个结果可以由什么得到，知道之前所有结点的信息，如何推导出当前结点的信息，其实和高中学的归纳法有一点点像。
  下面给出我今天做的三题的解题思路和代码
  1.    Problem 121. Best Time to Buy and Sell Stock
  解题思路：这道题很久以前做的，我们可以维持两个变量 - 分别对应于最小谷值和最大利润（销售价格和最低价格之间的最大差异）的minprice 和maxprofit。
  代码：https://github.com/yyxd/leetcode/blob/master/src/leetcode/array/easy/Problem121.java
  2.    Problem 120. Triangle
  解题思路：这道题给一个由整数组成的三角形，自上而下寻找顶点到三角形边的最短的一条路径，设置一个数组A[0...n-1][0...n-1]，A[i][j]代表到达第i行第j列结点的最短路径
* DP转移方程式为：A[i][j]=min(A[i-1][j-1],A[i-1][j])+triangle[i][j]
* 其中二维数组可以简化为一维数组，因为我们只需要上一行结点的信息
* 然后遍历到达最后一行的节点的路径，找到最短路径的值
  代码：https://github.com/yyxd/leetcode/blob/master/src/leetcode/dp/Problem120_Triangle.java
  3.    Problem 322. Coin Change
  解题思路：这道题是给定具有n个不同金额的硬币（硬币个数无限）coins[0...n-1]，给一个整数amount，是否给的硬币能正好达到整数，给出能组成整数最少需要的硬币个数.
解法是设置一个数组A[0...amount],进行初始化A[0]=0;A[1...amount] = -1;保存的是当给定金额为i时，所需要的最少的硬币。
* dp转移方程式为 A[k] = 1+min(A[k-coins[0]],A[k-coins[1]],....A[k-coins[n-1]]).
* 这里要注意的是判断A[k]是否有解
  代码：https://github.com/yyxd/leetcode/blob/master/src/leetcode/dp/Problem322_CoinChange.java
  课程完结撒花，真的学到好多，自己以后还会反复回顾的，再次感谢王争老师，还有每天负责朗读的声音好好听的修阳小哥哥。
  

  展开
• 
  李皮皮皮皮...

  2019-02-11

   1

  每天一道算法题，风雨无阻（过年偷懒不算😛）

  展开
• 
  _CountingS...

  2019-02-11

   1

  买卖股票的最佳时机 go 语言实现
  package main
  
  import "fmt"
  
  func maxProfit(prices []int) int {
      max := -1
      for i := 0; i < len(prices); i++ {
          for j := i + 1; j < len(prices); j++ {
              profit := prices[j] - prices[i]
              if profit > 0 && profit > max {
                  max = profit
              }
          }
      }
  
      if max == -1 {
          return 0
      }
  
      return max
  }
  
  func main() {
      testData1 := []int{7, 1, 5, 3, 6, 4}
      testData2 := []int{7, 6, 4, 3, 1}
  
      fmt.Println(maxProfit(testData1))
      fmt.Println(maxProfit(testData2))
  }
  

  展开
• 
  Nereus

  2019-02-19

  

  零钱兑换 - GO
  
  func coinChange(coins []int, amount int) int {
      var dp []int = make([]int, amount+1)
      for _, record := range coins {
          if amount >= record {
              dp[record] = 1
          }
      }
  
      for i := 1; i <= amount; i++ {
          dp[i] = amount + 1
          for _, record := range coins {
              if i-record >= 0 {
                  dp[i] = min(dp[i-record]+1, dp[i])
              }
          }
      }
  
      if dp[amount] > amount {
          return -1
      }
  
      return dp[amount]
  }
  
  func min(a, b int) int {
      if a < b {
          return a
      }
      return b
  }
  
  

  展开
• 
  拉欧

  2019-02-15

  

  买卖股票的最佳时机 go 语言实现
  
  func maxProfit(prices []int) int {
  
      max:=0
      for i:=0;i<len(prices);i++{
          for j:=0;j<i;j++{
              num:=prices[i]-prices[j]
              if num>max{
                  max=num
              }
          }
      }
      return max
  }

  展开
• 
  拉欧

  2019-02-15

  

  零钱兑换 go语言实现
  func coinChange(coins []int, amount int) int {
      if amount==0{
          return 0
      }
      if len(coins)==0 && amount!=0{
          return -1
      }
  
      isSmall:=true
      for _,coin:=range coins{
          if coin<=amount{
              isSmall=false
          }
      }
      if isSmall{
          return -1
      }
      grid:=make([]int,amount+1)
  
  
      for _,coin:=range coins{
          if coin<=amount{
              grid[coin]=1
          }
          if coin==amount{
              return 1
          }
      }
      for i:=2;i<amount+1;i++{
          newGrid:=make([]int,amount+1)
          for j:=1;j<amount+1;j++{
              for _,coin:=range coins{
                  if grid[j]==1 && j+coin<=amount{
                      newGrid[j]=1
                      newGrid[j+coin]=1
                  }
              }
          }
          grid=newGrid
          if grid[amount]==1{
              return i
          }
      }
      return -1
  }

  展开
• 
  拉欧

  2019-02-15

  

  最小路径和 go实现
  
  func minPathSum(grid [][]int) int {
      l:=len(grid)
      w:=len(grid[0])
      sum:=make([][]int,l)
      for i:=0;i<l;i++{
          sum[i]=make([]int,w)
      }
      sum[0][0]=grid[0][0]
      for i:=1;i<w;i++{
          sum[0][i]=grid[0][i]+sum[0][i-1]
      }
      for j:=1;j<l;j++{
          sum[j][0]=grid[j][0]+sum[j-1][0]
      }
      for i:=1;i<l;i++{
          for j:=1;j<w;j++{
              sum[i][j]=less(sum[i-1][j],sum[i][j-1])+grid[i][j]
          }
      }
  
      return sum[l-1][w-1]
  }
  
  func less(i,j int) int{
      if i>j{
          return j
      }else{
          return i
      }
  }

  展开
• 
  拉欧

  2019-02-15

  

  正则表达式匹配 go语言实现，还是看别人的提示搞出来的
  func isMatch(s string, p string) bool {
      if len(p)==0{
          if len(s)==0{
              return true
          }else{
              return false
          }
      }
      if len(p)==1{
          if len(s)==1 && (s[0]==p[0] || p[0]=='.'){
              return true
          } else {
              return false
          }
      }
      if p[1]!='*'{
          if len(s)==0{
              return false
          }
          return (s[0]==p[0]||p[0]=='.') && isMatch(s[1:],p[1:])
      }else{
          for ;len(s)!=0 && (s[0]==p[0]||p[0]=='.');{
              if isMatch(s,p[2:]){
                  return true
              }
              s=s[1:]
          }
          return isMatch(s,p[2:])
      }
  
  
  
      return true
  }

  展开
• 
  TryTs

  2019-02-14

  

  //零钱兑换
  #include<iostream>
  #include<algorithm>
  using namespace std;
  int coins[10];
  int amount;
  int k;//k代表纸币的数目
  int dp[20];//代表面值最大，也可以采用动态扩容的方式
  int cmax = 32767;
  int coinChange(int coins[],int amount){
      for(int i = 1;i <= amount;i++){
          dp[i] = cmax;
          for(int j = 0;j < k;j++){
              int t = coins[j];
              if(i >= t && coins[i - t] != cmax){
                  dp[i] = min(dp[i - t] + 1,dp[i]);
              }
          }
      }
      if(dp[amount] < cmax && dp[amount] > 0){
          return dp[amount];
      }
      else
          return -1;
  }
  int main(){
      k = 0;
      while(true){
          cin>>k;
          for(int i = 0;i < k;i++){
              cin>>coins[i];
          }
          cin>>amount;
          cout<<coinChange(coins,amount)<<endl;
      }    
  }

  展开
• 
  TryTs

  2019-02-14

  

  回溯0-1背包问题
  #include<iostream>
  using namespace std;
  int v[10] = {2,2,4,6,3};
  int M;//代表背包的容积
  int n;
  int cmax = 0;
  
  void f(int w,int k){
  //    if(w == 0){
  //        if(w > max) max = w;
  //    }
      if(w == M || k == n){
          if(w > cmax) cmax = w;
          return ;
      }
      f(w,k + 1);
      if(w + v[k] <= M){
          f(w + v[k],k + 1);
      }
  }
  int main(){
      //v[] = {2,2,4,6,3};
      M = 9;
      n = 5;
      f(0,0);
      cout<<cmax<<endl;
  }

  展开
• 
  TryTs

  2019-02-14

  

  #include<iostream>
  #include<cmath>
  using namespace std;
  
  int queen[100];
  int sum = 0;
  int n;
  void Print(){
      //cout<<"ss"<<endl;
      for(int i = 0;i < n;i++){
          cout<<"("<<i+1<<","<<queen[i] + 1<<")";
      }
      sum++;
      cout<<endl;
  }
  
  void Queen(int queen[],int k){
      if(k == n) {
          Print();
          //return ;
      }
      int j = 0;
      for(int i = 0;i < n;i++){
          //j = i;
          for( j = 0;j < k;j++){
              if((queen[j] == i)||(abs(queen[j] - i) == abs(k - j)))
                  break;
          }
          if(j == k){
              queen[k] = i;
              Queen(queen,k+1);
          }
      }
  }
  int main(){
      cin>>n;
      Queen(queen,0);
      cout<<sum<<endl;
  }

  展开
• 
  纯洁的憎恶

  2019-02-12

  

  第一题，把39讲的代码改了一下。。。
  
  public class Pattern {
    private boolean matched = false;
    private char[] pattern; // 正则表达式
    private int plen; // 正则表达式长度
  
    public Pattern(char[] pattern, int plen) {
      this.pattern = pattern;
      this.plen = plen;
    }
  
    public boolean match(char[] text, int tlen) { // 文本串及长度
      matched = false;
      if (pattern[0]='*')
             return matched;
     int i = 0;
     int j = 0;
     while (i<=plen&&j<=tlen&&pattern[i]!=text[j]&&pattern[i]!='.')
           i++;
      rmatch(0, 0, text, tlen);
      return matched;
    }
  
    private void rmatch(int ti, int pj, char[] text, int tlen) {
      if (matched) return; // 如果已经匹配了，就不要继续递归了
      if (ti == tlen){ //文本串到结尾了
        matched = true;
        return;
      }
      if (pattern[pj] == '*') { // * 匹配任意个字符
        for (int k = 0; k <= tlen-ti&&tex[ti+k]==text[ti]; ++k) {
          rmatch(ti+k, pj+1, text, tlen);
        }
      } else if (pattern[pj] == '.') { // . 匹配 0 个或者 1 个字符
        rmatch(ti, pj+1, text, tlen);
        rmatch(ti+1, pj+1, text, tlen);
      } else if (ti < tlen && pattern[pj] == text[ti]) { // 纯字符匹配才行
        rmatch(ti+1, pj+1, text, tlen);
      }
    }
  }

  展开
• 卡罗

  2019-02-12

  

  感觉，明天就是专栏的最后一天

  展开
• 
  C_love

  2019-02-11

  

  Best Time to Buy and Sell Stoc...
  
  class Solution {
      public int maxProfit(int[] prices) {
          if (prices == null || prices.length == 0 || prices.length == 1) {
              return 0;
          }
          
          int max = 0;
          int start = 0;
          
          for (int i = 1; i < prices.length; i++) {
              if (prices[i] < prices[start]) {
                  start = i;
              } else {
                  max = Math.max(max, prices[i] - prices[start]);
              }
          }
          return max;
      }
  }

  展开
• 
  ext4

  2019-02-11

  

  最小路径和
  class Solution {
    public:
      int minPathSum(vector< vector<int> >& grid) {
        int m = grid.size();
        if (m == 0) return 0;
        int n = grid[0].size();
        if (n == 0) return 0;
        int matrix[m][n];
        int accum = 0;
        for (int i = 0; i < m; i++) {
          accum += grid[i][0];
          matrix[i][0] = accum;
        }
        accum = 0;
        for (int j = 0; j < n; j++) {
          accum += grid[0][j];
          matrix[0][j] = accum;
        }
        for (int i = 1; i < m; i++) {
          for (int j = 1; j < n; j++) {
            matrix[i][j] = min(matrix[i - 1][j], matrix[i][j - 1]) + grid[i][j];
          }
        }
        return matrix[m - 1][n - 1];
      }
  };
  

  展开