Deshill和Rusela

算法分享

12月15日

因为报了明年的蓝桥杯，博主此时要学习python的算法了，以后有什么收获都会发在这个页面里面

更新ing。。。。

12月17日

快排算法分享

介绍：给定一个数组，要求对数组进行升序排序。而快排就是把数组排序好的基础上时间复杂度最低的，非常之nb，同时，效果越好，索要的代码复杂度就会提升，本章节就将对快排的思想进行进一步的加深，以及代码中可能会出现的小问题。

思想：

  1. 一列数组，有左指针和右指针，以及一个key（一般都设置为数组第一个即a[0]），左指针起始在0号位置（数组左边）右指针起始在最右边。
  2. 移动右指针，依次与key比较，若大于key就right–（指针左移），直到a[right]<key,就将左指针上的值（a[left]）设为右指针上的值，即a[left] = a[right],执行第三步
  3. 移动左指针，依次与key比较，若小于key就left++（指针右移动）,直到a[left]>key,就将右指针上的值（a[right]）设为左指针上的值,即a[right] = a[left],执行第四步
  4. 判断left是否等于right，若等于，则退出循环，执行第五步.若不等于，则重复23步
  5. 最终让a[left] = key，此时key在数组中，key的左边即为比key小的数，右边即为比key大的数，把左边和右边分别看成两个新的数组，然后重复1234步（递归的思想）

代码如下

#include <stdio.h>
void print(int a[] ,int n)
{//输出数组元素，数字之间以一个空格为界，输出结束后换一行
	if(n==1) return ;
  for(int i=0;i<n;i++)
  {
    printf("%d ",a[i]);
  }
  printf("\n");

}

void qSort(int a[] ,int left, int right) //
{
  if(left>=right) return ;//这一步非常关键，保证了不会重复排序
  int L = left;
  int R = right;
  int key = a[left];
  while(left!=right)
  {
    for(;right>left;right--)
    {
       if(a[right]<key)
        {
          a[left] = a[right];
          break;
        }
    }
    if(right==left) 
    {
      break;
    }
    for(;left<right;left++)
    {
      if(a[left]>key)
      {
        a[right] = a[left];
        break;
      }
    }
  }
  //printf("右边是%d\n左边是%d\n",R,L); 
  //printf("关键变量是%d\n",key);
  //if(L==left&&R==right) return ;
  a[right] = key;
  print(a,R+1);
  if(left!=0) qSort(a ,L,left-1);//左指针和右指针的位置很关键
  if(right<R)qSort(a ,left+1,R);
  
}





int main(void)
{
  int num ;
  scanf("%d",&num);
  int data[num];
  for(int i=0;i<num;i++)
    scanf("%d",&data[i]);

  qSort(data ,0,num-1);
  print(data,num);
}

参考资料：

后续学到有趣的算法也会分享到这里，尽情期待。。。。

1月12日（dp和递归问题）

详情见力扣1月12日周赛题目（点我）

这题用的是动态规划的解法

class Solution:
    def maximumAmount(self, coins: List[List[int]]) -> int:
        # 每一个格子等于max(dfs(i-1,j,k),dfs(i,j-1,k))+x,多考虑一个要不要感化
    @cache# 这个很nb，记忆化搜索，防止超出时间限制
        def dfs(n,m,k):
            if n<0 or m<0:
                return -inf
            x = coins[n][m]
            if n==0 and m==0:
                return max(x,0) if k else x
            big = max(dfs(n-1,m,k),dfs(n,m-1,k))+x
            if x<0 and k>0:
                big = max(big,dfs(n-1,m,k-1),dfs(n,m-1,k-1))
            return big
        return dfs(len(coins)-1,len(coins[0])-1,2)

本题目的思想是从后往前推，不断递归，化繁为简

相类似的题目还有这题（点我）

桂ICP备2024049770号