分类 算法 中的文章

Consideration make three pointers , pre,current,next; initial pre as null use tmp to save current’s next node info change current’s next to link pre node(first is null) move pre pointer to next node move current pointer to next node soultion 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 /** * Definition for singly-linked list. * public class ListNode { * int val; * ListNode next; * ListNode(int x) { val = x; } * } */ class Solution { public ListNode reverseList(ListNode head) { ListNode pre = null; ListNode current = head; while (current != null){ ListNode next = current.next; current.next = pre; pre = current; current = next; } return pre; } }……

阅读全文

hamming-distance

The Hamming distance between two integers is the number of positions at which the corresponding bits are different. Given two integers x and y, calculate the Hamming distance. Note: 0 ≤ x, y < 231. Example: Input: x = 1, y = 4 Output: 2 Explanation: 1 (0 0 0 1) 4 (0 1 0 0) ↑ ↑ The above arrows point to positions where the corresponding bits are different. Consideration This problem is also have a relationship with ‘^’ , Think about it : 1(0001) and 4(0100) their Xor is 5(0101) . next we use & Operator to calculate the number of 1 , let the binary & 1 ,if result is 1 ,sum’s up , use » to move the postion. 5(0101) 0&1 = 0 pass 01&01 = 1 sum 010&001 = 0 pass 0101&0001 = 1 sum……

阅读全文

条件概率、全概率与贝叶斯公式

条件概率公式 设事件A 发生的概率为 P(A), 事件B 发生的概率为 P(B),则在事件B发生的情况下事件A发生的概率(A given B 的概率)为: $$ P(A|B)=\frac{P(AB)}{P(B)} $$ 全概率公式 如果直接求事件A 的概率比较困难的时候,可以将事件A发生的概率分成一个个小的事件B的概率 $$ P(A)=\sum \limits_n{P(B_{n})P(A|B_{n})} $$ 贝叶斯公式 $$ P(B_{n}|A)=\frac{P(A|B_{n})P(B_{n})}{\sum \limits_n P(A|B_{n})P(B_{n})} $$……

阅读全文

使用移位运算符

middle = (L+R)/2 这样的写法 L+R 有可能溢出 middle = L + (R-L)/2 =>minddle = L + (R-L)>>1 这样写的好处是不会发生数据溢出,除以 2 则是向右移一位,位运算比算术运算快……

阅读全文

master 公式

master公式 T(N) = a*T(N/b) + O(Nd) N:样本量 T:时间复杂度 a:样本量发生的次数 b:将样本量进行分治 c:执行子过程之外其余过程的时间复杂度 用途:计算递归算法的时间复杂度 快速计算 logba > d -> 复杂度为O(Nlogba) logba = d -> 复杂度为O(Nd* logN) logba < d -> 复杂度为O(Nd) 适用范围 递归调用使,划分的……

阅读全文

关于进制的计算

进制转换 进制包括 二进制 八进制 十进制 十六进制 二进制(BIN)转十进制(DEC) 将二进制数按权展开相加得十进制数 举例:10010 的十进制为 18 十进制(DEC)转二进制(BIN) 除 2 取余,逆序排列。 举例: 666 的二进制为 1010011010 二进制(BIN)转八进制(OCT) 从右向左,每三位二进制数为一组按权展……

阅读全文