Category Archives: IT技術

新发现

tree可以装到stack里,读取的逻辑还是tree结构的顺序 我以前的逻辑是,把一个数字和index写入字典,然后判断写入的内容,其实还可以是:判断内容,再写入,就可以随时return 有一个递归函数 def(node.right)=node.left 一开始觉得这个函数 输入是right输出是left很奇怪,里面没操作啊,其实这就是一个f(x)=y的结构,把x映射到y,在程序里 应该就是指针的关系吧

Posted in leetcode | Leave a comment

203.remove-linked-list-elements

把每一个node想象成一个车厢,这个车厢可以传送到下一节连着的车厢,也可以读到下一节车厢的数字。 由于第一节车厢也有可能是报废,所以首先利用listnode创造一个叫做fa的实例,然后把fa指向list的首位,作为试探车。 然后我们需要双指针,一个指针在fa(pre),另一个是读数,即fa.next(用cur来表示)。如果cur.val!=val,那么pre前进一步检查下一节即pre=cur,cur=cur.next。如果cur.val==val,,pre.next连接的也不是废弃的那节了,先让cur读下一节车厢(cur.next),再让pre.next 与之连接即pre.next= cur.next 如果

Posted in leetcode | Leave a comment

0198.house-robber

我的思路 就是用动态规划的思路填表, 假设会去第一间房子,然后如果和第二间房子进行比较,如果第二间大,谁就是真正意义的参照物。因为从第三间开始就要计算,1+3和2谁大的问题。scoretable[i-2]代表上一间没偷的值 但是太过于复杂,一不小心就错了 参考答案的思路,dp[i] = Math.max(dp[i – 2] + nums[i – 2], dp[i – 1]); 更直观的解释:指针一负责找王储,指针二找国王。王储和国王不能连任 因为动态规划的特点,比如指针在i,i-1是最优解,i-2是次最优解,i只能和次最优解合并 比如在 [2,7,9,3,1] 王储先储备2,如果7大于2,王储不变,7作为国王, 读到9的时候,国王的计算公式是 max(当前数字+王储,国王),可以看到2+9>7,所以11列为国王,7变成王储。读到3时候,max(3+7,11),所以王储是10,11是国王;但是他们不能连任,所以11是王储,10是国王。最后读到1的时候,max(1+11,10),国王变成12是答案

Posted in leetcode | Leave a comment

191.number-of-1-bits

190 会做了 就是一秒钟的事情 思路:判断器:n&1 判断这一位是不是1 然后右移一位 答案似乎有更简洁的写法: n=n &(n-1 )可以把n里的1进行降维打击,原因是n的每一位,不是0就是1 如果尾数是1,减去1会消去0 如果尾数是0,就势必要去问前面借一个1,就又干掉了一个1

Posted in leetcode | Leave a comment

190.reverse-bits

https://www.geeksforgeeks.org/python-bitwise-operators/ 因为是unsigned bit,和普通int不一样 思路,看答案后: 双指针,一个指针读n的末位和1做&逻辑运算(if both 1 return 1 else 0),因为1只有1位,所以默认和末尾pk;比较完后得到的结果,加到新队伍(某变量,初始值0)里,新队伍要保证加进来的结果在尾部,因此在做加法前,用位移把已有的部分往前移动一格,在bit运算里,移动向左移动一格用<<表示。完毕后,把n指针指向倒数第二格,准备进入下一轮循环。指向倒数第二格也要用到>>的方法

Posted in leetcode | Leave a comment

172.factorial-trailing-zeroes

思路: 看到factorial 想到递归,模拟一遍n!的过程 然后研究0出现的规律,0的由来取决于有几个5 所以在递归中,加一个判断,如果读到5的倍数就加一 问题:好像没法让我自己加一个count变量 解决:直接算n里有几个5以及除了5以后的部分里还有几个5,如果n=100,就是100//5+20//5+4//5 这样的递归(结束条件是n=0) 总结:除以5和剩余部分几个5这样 更简单直观的递归 没想到

Posted in leetcode | Leave a comment

169.majority-element

原始思路:字典 参考答案思路:投票算法 背后原理简单的理解是 如果你要当选,支持你的人至少要超过半数 和题目的定义:The majority element is the element that appears more than ⌊ n/2 ⌋ times 一致 我的后续思路:做一个栈,如果读到的数字和栈顶的数字不一样,意思是这个人是个反对党的,然后栈顶数字出列,代表他们两个抵消了;如果读到的数字和栈顶数字一样,入栈,代表相同势力 最后还在栈里的人就是答案

Posted in leetcode | Leave a comment

167.two-sum-ii-input-array-is-sorted.

思路: 做一个字典,列表里的第一个数字,写在第1页 第二个数字写在第二页,类推 在写下去之前,查一下,target减去这个数字 是不是已经写过 即是否存在字典的keys里,如果写过就返回页数(values) 没有写过就写一下 这里的注意事项是,先判断有没有写过,在写下去 不然,例如【2,3,4】数列,target为6的情况下 先写再判断,会把3当成答案

Posted in leetcode | Leave a comment

leetcode 刷题计划

简单难度 0020.Valid Parentheses 0026.remove-duplicates-from-sorted-array 0053.maximum-sum-subarray  0088.merge-sorted-array 0104.maximum-depth-of-binary-tree 0121.best-time-to-buy-and-sell-stock 0122.best-time-to-buy-and-sell-stock-ii 0125.valid-palindrome ? 0136.single-number 0155.min-stack  0167.two-sum-ii-input-array-is-sorted 0169.majority-element 0172.factorial-trailing-zeroes 0190.reverse-bits 0191.number-of-1-bits 0198.house-robber 0203.remove-linked-list-elements 0206.reverse-linked-list 0219.contains-duplicate-ii 0226.invert-binary-tree 0232.implement-queue-using-stacks ? 0263.ugly-number 0283.move-zeroes 0342.power-of-four 0349.intersection-of-two-arrays 0437.path-sum-iii ? 0371.sum-of-two-integers 0501.find-mode-in-binary-search-tree? 0575.distribute-candies 0874.walking-robot-simulation ? 1260.shift-2d-grid ? 1332.remove-palindromic-subsequences ?

Posted in leetcode | Leave a comment

155.min-stack

一开始的思路: 第一反应:建一个list, 新增:新增元素append到尾部 弹出:list尾部pop top:取list尾部首元素 min:每次新进一个人,和当前min对比 问题: 如果当前的min弹出后,min变量没有记忆性,不知道之前存的min是多少 解决: 建一个存min的list,用法和stack一样,如果出队后,还是可以知道上一个最小值是多少

Posted in leetcode | Leave a comment