xindoo_社区达人页

2023年11月

• 11.01 09:26:01
  发表了文章 2023-11-01 09:26:01

  Leetcode 368. Largest Divisible Subset思路及详解

  这里有个很简单的数学性质，就是整除的传递性，如果a%b==0 且 b%c == 0，那么a%c == 0，说白了如果c是b的因子，b又是a的因子，那么c肯定是a的因子。这样我们就可以在数组中找出很多整除链（a->b->c->d，其中b是a的因子，c是b的因子，d是c的因子），这样的链条就满足两两整除的条件，题目就变成了求最长的链条。 先上代码，然后我再解释下我的代码。
• 11.01 09:24:15
  发表了文章 2023-11-01 09:24:15

  一次诡异的磁盘空间占用问题排查

  大半夜接到线上一服务器磁盘占用率超过90%的短信，需要立即处理。一般这种情况都是线上异常，当天日志打太多，无法自动删掉的。上来第一反应就是查我们规范java应用日志目录，居然没有文件，再查，居然连java进程都没有，原来不是java应用，不过没关系，干一年运维也不是白干的，还是有其他方法可以查的，在此记录下整个排查过程。
• 11.01 09:22:11
  发表了文章 2023-11-01 09:22:11

  Leetcode 53.Maximum Subarray

  题意简单，给出一个数组，求出其中最大的子数组和。 这种简单题目背后蕴藏着很巧妙的解题方法。其实只需要遍历一次数组就可以求得解。 思路是这样的，你想想看，如果一段子数组的和是负数， 那么这一段子数组不可能是最大和数组的一部分，丢掉重新从下一个位置开始选。
• 11.01 09:20:47
  发表了文章 2023-11-01 09:20:47

  Leetcode 372. Super Pow

  真正的解法其实思路很简单，我随便举个例子就很容易理解了，假设要求(123^4567)%1337,只需要把这个幂式子分解成几个层次，然后把球模加到每一层中间就很容易计算出来了。
• 11.01 09:19:00
  发表了文章 2023-11-01 09:19:00

  Leetcode 377. Combination Sum IV

  赤裸裸的完全背包，属于动态规划的范畴，大家有兴趣可以在网上搜索下其他资料。个人觉得动态规划还是比较难理解的，更难给别人讲清楚，所以这里我直接附上我的代码供大家参考。
• 11.01 09:17:58
  发表了文章 2023-11-01 09:17:58

  Leetcode 240. Search a 2D Matrix II

  具体思路就是每一行倒着扫，扫到第一个比target小的数就跳到下行，如果等于当然是直接返回true了，如果下一行还比target小就继续跳下一行，直到最后一行。 为啥这么做是可行的？ 可能我比较笨，想了半天才想到。 因为每一列都是增序的，举个例子，假设matrix[0][5] > target,那么[0][5]位置右下（包含右和下）所有元素不可能比target小。
• 11.01 09:16:38
  发表了文章 2023-11-01 09:16:38

  Leetcode 74. Search a 2D Matrix

  这道题很简单，为此专门写篇博客其实算博客凑数了。给你一个每一行每一列都是增序，且每一行第一个数都大于上一行末尾数的矩阵，让你判断某个数在这个矩阵中是否存在。 假设矩阵是m*n，扫一遍的时间复杂度就是O(m*n)，题目中给出的这么特殊的矩阵，时间复杂度可以降到O(m+n)，具体代码如下，写的比较挫。
• 11.01 09:15:37
  发表了文章 2023-11-01 09:15:37

  Leetcode 230. Kth Smallest Element in a BST

  先来看下二叉搜索树的性质，对于任意一个非叶子节点，它的左子树中所有的值必定小于这个节点的val，右子树中所有的值必定大于或等于当前节点的val。 这条性质就保证了如果我们对二叉搜索树做中序遍历，中序遍历的结果肯定是有序的。对于此题而言，我们只需要拿到中序遍历结果，然后返回第k个即可，时间复杂度是O(n)。
• 11.01 09:14:39
  发表了文章 2023-11-01 09:14:39

  Leetcode 313. Super Ugly Number

  题目翻译成中文是『超级丑数』，啥叫丑数？丑数就是素因子只有2，3，5的数，7 14 21不是丑数，因为他们都有7这个素数。 这里的超级丑数只是对丑数的一个扩展，超级丑数的素因子不再仅限于2 3 5，而是由题目给定一个素数数组。与朴素丑数算法相比，只是将素因子变了而已，解法还是和朴素丑数一致的。
• 11.01 09:13:24
  发表了文章 2023-11-01 09:13:24

  Leetcode 11. Container With Most Water

  题目可以这么理解，在i位置有条高为ai的竖线，让你选出两台竖线构成一个容器，使得该容器装的水最多，注意容器不能倾斜。
• 11.01 09:12:01
  发表了文章 2023-11-01 09:12:01

  Leetcode 347.Top K Frequent Elements

  一句话理解题意：输出数组中出现次数对多的ｋ个数。 在如果用C语言来写这个题目，思路就是先按数的大小排序，然后再用一个结构体数组保存每个数的出现次次数。 因为数组已经有序了，所以只需要遍历一次数组就可以获得每个数的出现次数了。
• 11.01 09:10:26
  发表了文章 2023-11-01 09:10:26

  Leetcode 198. House Robber

  一句话理解题意，有个偷马贼晚上要偷尽可能值钱的马，但连续两头马被偷会触发报警，问他如何在不触发报警（不偷连续的两匹马）的情况下偷到总价值最高马，返回最高总价值。
• 11.01 09:09:15
  发表了文章 2023-11-01 09:09:15

  Leetcode 3. Longest Substring Without Repeating Characters

  此题题意是找出一个不包含相同字母的最长子串，题目给出了两个例子来说明题意，但这两个例子具有误导性，让你误以为字符串中只有小写字母。还好我是心机boy，我把大写字母的情况也给考虑进去了，不过。。。。字符串里竟然有特殊字符，于是贡献了一次wrong answer，这次我把ascii字符表都考虑进去，然后就没问题了。这个故事告诫我们在编程处理问题的时候一定要注意输入数据的范围，面试中可以和面试官去确认数据范围，也能显得你比较严谨。
• 11.01 09:08:02
  发表了文章 2023-11-01 09:08:02

  萌妹子Python入门指北（五）

  def isprime(n): //isprime是函数名，n是需要判断的数 for i in range(2, n): if n%i == 0: //这里如果被i整除了看到不是素数了，素数的定义就是因子只有1和它本身 return False return True
• 11.01 09:05:40
  发表了文章 2023-11-01 09:05:40

  萌妹子Python入门指北（四）

  1.if可以嵌套for吗？可以嵌套while循环吗？ 2.难道只能嵌套两层吗？3层 4层 5层可不可以？ 一般的文章在这个时候会告诉大家『这里我就不公布答案了，大家可以去尝试下』，然而我这里我偏要告诉大家答案很明显都是yes yes，你试不试就和我无关了。
• 11.01 09:03:19
  发表了文章 2023-11-01 09:03:19

  萌妹子Python入门指北（三）

  其中if和else之间可以加多个else if语句，如果代码执行到这一个判断，你们就执行本行后面有相同缩进的代码，负责就跳到下一个else if，或者else。
• 11.01 08:58:48
  发表了文章 2023-11-01 08:58:48

  萌妹子Python入门指北（一）

  print 'hello world!'
• 11.01 08:56:37
  发表了文章 2023-11-01 08:56:37

  Leetcode Find Minimum in Rotated Sorted Array 题解

  对一个有序数组翻转， 就是随机取前K个数，移动到数组的后面，然后让你找出最小的那个数，注意，K有可能是0，也就是没有翻转。
• 11.01 08:54:55
  发表了文章 2023-11-01 08:54:55

  Vim的配置说明

  在网上参考了某大牛个vim配置，然后更改添加了一部分，形成了自己的配置，让Vim变的更强大。
• 11.01 08:53:09
  发表了文章 2023-11-01 08:53:09

  Leetcode Minimum Depth of Binary Tree （面试题推荐）

  计算树的最小深度 很简单的一道题，只需要遍历一次树，到叶子节点的时候计算一下深度和当前最小深度比较，保存最小值就行。 我在这用了一个全局变量 mindepth。总感觉我这代码写的不够简练，求更精简的方法。
• 11.01 08:51:28
  发表了文章 2023-11-01 08:51:28

  Leetcode Binary Tree Postorder Traversal(面试题推荐)

  非递后续归遍历二叉树，肯定得用到栈。先序遍历很好写，但后续遍历就不是那么容易了。 只需要设置个指针pre，指向最后输出的那个节点就行了，只要判断cur指针指向的是上次输出节点的父节点，且cur无其他未遍历的节点，这个时候就把cur节点输出即可，然后更改pre。原理是要遍历当前节点，其所有子节点都必须遍历完，因为肯定是先左后右，所以只需一个指针保持前一次输出的结果即可。
• 11.01 08:49:39
  发表了文章 2023-11-01 08:49:39

  Leetcode Single Number II （面试题推荐）

  给你一个整数数组，每个元素出现了三次，但只有一个元素出现了一次，让你找出这个数，要求线性的时间复杂度，不使用额外空间。
• 11.01 08:48:37
  发表了文章 2023-11-01 08:48:37

  Leetcode Copy List with Random Pointer（面试题推荐）

  给大家推荐一道leetcode上的面试题，这道题的具体讲解在《剑指offer》的P149页有思路讲解，如果你手头有这本书，建议翻阅。
• 11.01 08:46:56
  发表了文章 2023-11-01 08:46:56

  Stanford 机器学习练习 Part 3 Neural Networks: Representation

  从神经网络开始，感觉自己慢慢跟不上课程的节奏了，一些代码好多参考了别人的代码，而且，让我现在单独写也不一定写的出来了。学习就是一件慢慢积累的过程，两年前我学算法的时候，好多算法都完全看不懂，但后来，看的多了，做的多了，有一天就茅塞顿开。所有的困难都是一时的，只要坚持下去，一切问题都会解决的。没忍住发了点鸡汤文。
• 11.01 08:44:52
  发表了文章 2023-11-01 08:44:52

  Stanford 机器学习练习 Part 2 Logistics Regression

  以下是我学习Andrew Ng machine learning 课程时logistic regression的相关代码，仅作为参考，因为是初学，暂时没办法做出总结。

2023年10月

• 10.31 23:53:21
  发表了文章 2023-10-31 23:53:21

  Stanford 机器学习练习 Part 1 Linear Regression

  In octave, we return values by defining which variables % represent the return values (at the top of the file)
• 10.31 23:47:09
  发表了文章 2023-10-31 23:47:09

  Ubuntu下python安装mysqldb(驱动)

  先跳转的该目录下，然后执行 sudo python setup.py install 然后就是各种问题，需要配置这个那个的。
• 10.31 23:45:54
  发表了文章 2023-10-31 23:45:54

  poj 1455 Crazy tea party

  说一下大概思路，如果是排成一排的n个人,如 1 2 3 4 5 6 7 8 我们要变成 8 7 6 5 4 3 2 1 需要交换 28次，找规律的话就是 n*(n-1)/2，但这道题是一个圈，要让他们顺序变反的话不一定1要在8的位置上去，4 3 2 1 8 7 6 5 这样也是反的，我们只要把n个人分成两部分，然后按拍成一条线的方法来出来两部分就OK了；
• 10.31 23:44:33
  发表了文章 2023-10-31 23:44:33

  hdoj 4768 Flyer

  题目意思很容易理解，学校有n个社团，每个社团只给编号从a到b 的发传单，而且只给隔了c的人发，问最后谁收到的传单是单数，输出他的编号和收到的传单数量。
• 10.31 23:43:17
  发表了文章 2023-10-31 23:43:17

  codeforces 347A - Difference Row

  给你一个序列，让你求(x1 - x2) + (x2 - x3) + ... + (xn - 1 - xn).值最大的一个序列，我们化简一下公式就会发现(x1 - x2) + (x2 - x3) + ... + (xn - 1 - xn). = x1 - xn， 也就是说只有第一个和最后一个是确定的，其他的随便了！ 也不是了， 还要让你按字典序最小的排列，也就是说其他的是按飞递减序排列的，简单的一次排序就OK了。
• 10.31 23:42:02
  发表了文章 2023-10-31 23:42:02

  codeforces 344B - Simple Molecules

  题意就是给出3个原子的化学价，然后组成一个分子，要保证这个分子是稳定的，如果你还记得高中化学知识的话这个很容易理解，然后让你求出1-2 2-3 1-3 号原子之间有几条键， 这里我分别用ta tb tc 表示， 用数学的方法表示出来的话就是a = tc + tb; b = ta+tc; c = ta + tb;可能有多种情况，只要输出一种即可。
• 10.31 23:40:30
  发表了文章 2023-10-31 23:40:30

  hdoj 4712 Hamming Distance(靠人品过的)

  在信息论中，两个等长字符串之间的汉明距离是两个字符串对应位置的字符不同的个数。换句话说，它就是将 一个字符串变换成另外一个字符串所需要替换的字符个数。
• 10.31 23:39:10
  发表了文章 2023-10-31 23:39:10

  hdoj 4706 Children's Day

  题目意思就是用a-z组成一个N，然后到z后又跳回a，输出宽从3到10的N。
• 10.31 23:38:04
  发表了文章 2023-10-31 23:38:04

  hdoj 4715 Difference Between Primes 素数筛选+二分查找

  hdoj 4715 Difference Between Primes 素数筛选+二分查找
• 10.31 23:37:12
  发表了文章 2023-10-31 23:37:12

  poj 1503 高精度加法

  把输入的数加起来，输入0表示结束。 先看我Java代码，用BigINteger类很多东西都不需要考虑，比如前导0什么的，很方便。不过java效率低点，平均用时600ms，C/C++可以0ms过。
• 10.31 23:35:25
  发表了文章 2023-10-31 23:35:25

  hdoj 1715 大菲波数

  先java代码
• 10.31 23:33:22
  发表了文章 2023-10-31 23:33:22

  hdoj 1753 (Java)

  刚刚开始用Java，代码难免不够简洁。
• 10.31 23:32:19
  发表了文章 2023-10-31 23:32:19

  poj 1131 Octal Fractions（高精度小数进制转换） Java

  虽然题目那么长其实就是把8进制的浮点数转换成10进制，为了练习Java Biginteger 类 我这里用的是Java，也可以用数组模拟
• 10.31 23:27:57
  发表了文章 2023-10-31 23:27:57

  poj 1205 ：Water Treatment Plants (DP+高精度)

  思路：DP+高精度。DP部分，易得最右边城市的状态只可能用3种：>V, V, <。故分三种状态讨论，设dp[i][0]为第i个城市的状态为：> V ，dp[i][1]为：V ，dp[i][2]为：<。由实际流动的可能性可以得到状态转移方程：
• 10.31 23:26:30
  发表了文章 2023-10-31 23:26:30

  Qtech 暑假未讲到的算法（不完全）

  优先队列、堆、RMQ问题（区间最值问题，可以用线段树解决，还有一个Sparse-Table算法）、排序二叉树、划分树、归并树.....
• 10.31 23:24:10
  发表了文章 2023-10-31 23:24:10

  poj 2155 Matrix (二维树状数组)

  这是楼教主出的二维线段树或者是二维树状数组的题，题意很简单，就是有个n*n的矩阵，初始值都是0，然后给你两个操作，一个是给你左上角和右下角的坐标，把这个长方形的区间所有元素反取反（0变1 1变0），另一个是求某个具体坐标的值。 这里我用了二维的线树状数组，一维树状数组可以解决区间更新和点查询的问题，这里只需要加一维就可以了，代码比较好写，不过开始犯了很多低级的错误。
• 10.31 23:22:41
  发表了文章 2023-10-31 23:22:41

  codeforces 339 D.Xenia and Bit Operations（线段树）

  输入n,m表示有2^n个数和m个更新，每次更新只把p位置的值改成b，然后输出整个序列运算后的值，而这个运算就比较复杂了， 最下面一层两个数字之间或运算得到原来数目一半的数字，然后两个之间异或运算，得到一半，再或再异或………………，一直到得到一个数字，这个数字就是要求的结果。
• 10.31 23:19:24
  发表了文章 2023-10-31 23:19:24

  codeforces 339A.Helpful Maths B.Xenia and Ringroad 两水题

  .题意就是把字符串里面的数字按增序排列，直接上代码。
• 10.31 23:13:42
  发表了文章 2023-10-31 23:13:42

  poj 1990 MooFest 树状数组

  题意就是有N头牛，每头牛都有一个坐标和声调值（x, v），两头牛之间通讯要花费的能量是他们的距离乘以最大的一个音调值，现在要任意两头牛之间都相互通讯一次，求总共需要花费多少能量？
• 10.31 23:12:13
  发表了文章 2023-10-31 23:12:13

  light oj 1159 - Batman LCS

  学过简单动态规划的人应该对最长公共子序列的问题很熟悉了，这道题只不过多加了一条字符串变成三条了，还记得，只要把状态变成三维的即可。