3 csu_xiji

尚未进行身份认证

我要认证

暂无相关简介

等级
TA的排名 5k+

CodingBat python Warmup-1

https://codingbat.com/python/Warmup-1sleep_in思路:简单的逻辑运算,如果weekdayweekdayweekday为FalseFalseFalse或者vacationvacationvacation为TrueTrueTrue就返回TrueTrueTrue,否则返回FalseFalseFalse。def sleep_in(weekday, vacation): return not weekday or vacationmonkey_trouble

2020-10-28 03:22:07

团体程序设计天梯赛 L2-004 这是二叉搜索树吗 递归

https://pintia.cn/problem-sets/994805046380707840/problems/994805070971912192思路:先序遍历即根左右,假设对应的数组区间为[head,tail][head,tail][head,tail],那么依据二叉搜索树的性质,可以将其分为三部分:1.1.1.根节点,即a[head]a[head]a[head];2.2.2.左子树,a[head…l]a[head…l]a[head…l];3.3.3.右子树,a[r…tail]a[r…tail

2020-10-23 19:46:21

力扣 378. 有序矩阵中第K小的元素

https://leetcode-cn.com/problems/kth-smallest-element-in-a-sorted-matrix/思路:显然易得矩阵最小值为m[0][0]m[0][0]m[0][0],最大值为m[n−1][n−1]m[n-1][n-1]m[n−1][n−1],那么我们可以二分第kkk小元素的值midmidmid,再遍历矩阵的每一行(或列)判断<=mid<=mid<=mid的数的总和,假设为numnumnum,如果num>=knum>=knum

2020-10-18 01:26:25

力扣 275. H 指数 II 二分

https://leetcode-cn.com/problems/h-index-ii/思路:即找到arr[i]>=n−iarr[i]>=n-iarr[i]>=n−i的第一个iii,所以是求满足题意的最小值,那么在不满足条件时再修改下限lll即可。class Solution: def hIndex(self, citations: List[int]) -> int: n=len(citations) l,r=0,n-1

2020-10-18 01:01:08

PIPIOJ 1176: 逃离迷宫 状压bfs

http://39.106.164.46/problem.php?id=1176思路:状压bfsbfsbfs模板题。step[x][y][key]step[x][y][key]step[x][y][key]表示从起点出发到(x,y)(x,y)(x,y)且拥有的钥匙状态为keykeykey时所需要的最少步数,然后做bfsbfsbfs即可,只需要注意对keykeykey的判断和更新。举个例子,假设有三把钥匙,那么二进制000000000表示没有钥匙,001001001表示拥有第一把钥匙,011011011表

2020-10-14 01:22:07

力扣 392. 判断子序列 dp/双指针

https://leetcode-cn.com/problems/is-subsequence/思路:有一个显然正确的贪心:对于任意一个字符iii,假设可选的匹配位置有pos1、pos2pos_1、pos_2pos1​、pos2​,且pos1<pos2pos_1<pos_2pos1​<pos2​,那么应该选择pos1pos_1pos1​而不是pos2pos_2pos2​。双指针的做法就不说了,说一下后续挑战怎么搞。第一个思路我们用vec[i][j]vec[i][j]vec[i][j]记

2020-10-08 18:54:45

力扣 1025. 除数博弈 dp/博弈

https://leetcode-cn.com/problems/divisor-game/思路一:dpdpdp,不妨设dp[i]dp[i]dp[i]表示数字为iii时,爱丽丝能否胜利。那么显然有dp[1]=falsedp[1]=falsedp[1]=false,dp[2]=truedp[2]=truedp[2]=true,对于任意的3<=i<=N3<=i<=N3<=i<=N,对于其任意一个因子jjj显然有dp[i]=dp[i]∣∣dp[i−j]dp[i]=dp[i]

2020-10-08 00:25:53

力扣 1382. 将二叉搜索树变平衡 思维+分治

https://leetcode-cn.com/problems/balance-a-binary-search-tree/思路:首先序列化二叉搜索树,即对其做一次中序遍历得到一个有序数组。每次都选择l、rl、rl、r的中间位置的值作为当前节点,分治得到左右子节点即可。/** * Definition for a binary tree node. * struct TreeNode { * int val; * TreeNode *left; * TreeNode

2020-09-28 15:05:55

Ray Tracing in One Weekend(中文翻译)

文章目录1. 写在前面2. Output an Image2.1 The PPM Image Format2.2 Creating an Image File3. The vec3 Class3.1 Variables and Methods3.2 vec3 Utility Functions3.3 Color Utility Functions4. Rays, a Simple Camera, and Background4.1 The ray Class4.2 Sending Rays Into the

2020-09-25 00:22:51

力扣 1438. 绝对差不超过限制的最长连续子数组 单调队列+思维

https://leetcode-cn.com/problems/longest-continuous-subarray-with-absolute-diff-less-than-or-equal-to-limit/思路:很容易想到,枚举区间的起始点lll,然后找到第一个不满足题意的终结点rrr,显然[l,r−1][l,r-1][l,r−1]是满足题意的,那么可以更新答案ans=max(ans,r−l)ans=max(ans,r-l)ans=max(ans,r−l)。那么整体框架就有了,初始令l=0l=

2020-09-23 22:04:39

Whitted光线追踪

更详细的内容可以看知乎的这篇文章。这里简要的说了一下几何光学的规则。这里引出了光线追踪:正向(从光源开始)和反向(从眼睛开始)。在介绍光线追踪前,先来看一些比较简单的。WhittedWhittedWhitted光线追踪算法,结合了反向光线追踪和rays to lightrays\ to\ lightrays to light(看图会更清晰一点),而且需要递归计算。具体的算法:1.1.1.对于每个像素,沿VVV方向跟踪主光线到第一个可见表面。2.2.2.

2020-09-17 18:32:15

Phong和Blinn-Phong光照模型

文章内容来自上面这篇pdfpdfpdf,如有错误,欢迎指正。简要介绍一下PhongPhongPhong和Blinn−PhongBlinn-PhongBlinn−Phong光照模型的特点。简要介绍一下问题,同时给出了N、L、V、PN、L、V、PN、L、V、P的意义(之后计算会用到)。第000步,此时最终颜色仅与物体本身的材质有关。第111步,我们可以加上环境光(它能将灯光均匀地照射在场景中每个物体上面)。这里对Ke、Ka、ILaK_e、K_a、I_{La}Ke​、Ka​、ILa​进行了更.

2020-09-14 22:21:48

射线与球体/三角面片求交、重心坐标、插值

射线已知射线方程为P(t)=Pˉ+t∗DˉP(t)=\bar{P}+t*\bar{D}P(t)=Pˉ+t∗Dˉ,其中Pˉ\bar{P}Pˉ为射线的起点(x0,y0,z0)(x_0,y_0,z_0)(x0​,y0​,z0​),Dˉ\bar{D}Dˉ为射线的方向向量,其模长为111,只要知道距离ttt,我们就可以计算出对应点的坐标。球体求交不妨设球体的方程为(Xˉ−Cˉ)2=R2(\bar{X}-\bar{C})^2=R^2(Xˉ−Cˉ)2=R2,其中Xˉ\bar{X}Xˉ为球体上任意一点的坐标,Cˉ\b

2020-09-14 22:19:48

力扣 剑指 Offer 43. 1~n整数中1出现的次数 规律

https://leetcode-cn.com/problems/1nzheng-shu-zhong-1chu-xian-de-ci-shu-lcof/思路:应该算是找规律吧,看了别人的题解才会做…class Solution {public: int countDigitOne(int n) { long long high=n/10,cur=n%10,low=0,digit=1,ans=0; while(high||cur){

2020-09-09 19:41:46

力扣 214. 最短回文串 字符串hash/KMP算法

https://leetcode-cn.com/problems/shortest-palindrome/思路:思路其实很简单,因为只能在字符串的头部添加字符,所以我们只要找到下标从0开始的最长回文串s1s_1s1​,假设后面部分为s2s_2s2​,那么答案就等于reverse(s2)+sreverse(s_2)+sreverse(s2​)+s。怎么在线性复杂度内找到s1s_1s1​呢?我们有两种方法,第一种方法是利用hashhashhash,通过定义进制数和模数,我们可以将一个字符串表示成数字,比如进

2020-09-09 02:54:16

力扣 459. 重复的子字符串 kmp求循环节/思维

https://leetcode-cn.com/problems/repeated-substring-pattern/思路一:kmp,详见:https://blog.csdn.net/xiji333/article/details/88614354。class Solution {public: bool repeatedSubstringPattern(string s) { int siz=s.size(); if(!siz) r

2020-09-07 15:56:03

力扣 567. 字符串的排列 滑动窗口

https://leetcode-cn.com/problems/permutation-in-string/思路:如果s2s_2s2​包含s1s_1s1​的排列,那么必定存在一个s2s_2s2​的字串sss,sss中任意字符的出现次数一定等于s1s_1s1​中对应字符的出现次数。转换到这一步就比较好搞了,当然暴力做还是会超时的,正解是滑动窗口。首先用cntcntcnt数组记录s1s_1s1​中每个字符的出现次数,然后令l=r=0l=r=0l=r=0(窗口的边界),我们不断移动右边界(入窗),当某个时候

2020-09-07 13:59:57

力扣 416. 分割等和子集 01背包/暴力

https://leetcode-cn.com/problems/partition-equal-subset-sum/思路一:dpdpdp,首先计算数组元素的和,如果为奇数则一定不能满足题意,否则子集的和就等于总和的一半,假设为halfhalfhalf,那么问题转换成:是否可以从数组中任取一些数字使得它们的和为halfhalfhalf。010101背包可解,dp[i]=1dp[i]=1dp[i]=1说明可以组成iii这个数,否则说明不能组成iii这个数,那么对于数组中的每个元素vvv都有,dp[i]=

2020-09-06 22:45:34

力扣 1114. 按序打印 C++多线程

https://leetcode-cn.com/problems/print-in-order/思路:条件变量就行了。class Foo {public: Foo() { } void first(function<void()> printFirst) { unique_lock<mutex> lck(mtx); cv.wait(lck,func1); // printFirst()

2020-09-06 21:01:58

力扣 85. 最大矩形 单调栈

https://leetcode-cn.com/problems/maximal-rectangle/思路:这题其实和力扣848484很像。如果能把这个矩阵转换成高度数组(柱状图),那么利用单调栈就可以在线性复杂度内求解出柱状图内的最大矩形面积。这个转换其实很简单,我们用heights[i]heights[i]heights[i]表示第iii列的高度,依次枚举nnn行即可(枚举第iii行就相当于把第iii行作为柱状图的底部)。class Solution {public: int large

2020-08-22 15:24:48

查看更多

勋章 我的勋章
  • 签到新秀
    签到新秀
    累计签到获取,不积跬步,无以至千里,继续坚持!
  • 新人勋章
    新人勋章
    用户发布第一条blink获赞超过3个即可获得
  • 阅读者勋章Lv2
    阅读者勋章Lv2
    授予在CSDN APP累计阅读博文达到7天的你,是你的坚持与努力,使你超越了昨天的自己。
  • 持之以恒
    持之以恒
    授予每个自然月内发布4篇或4篇以上原创或翻译IT博文的用户。不积跬步无以至千里,不积小流无以成江海,程序人生的精彩需要坚持不懈地积累!
  • 勤写标兵Lv4
    勤写标兵Lv4
    授予每个自然周发布9篇以上(包括9篇)原创IT博文的用户。本勋章将于次周周三上午根据用户上周的博文发布情况由系统自动颁发。
  • 分享学徒
    分享学徒
    成功上传1个资源即可获取