- 博客(168)
- 收藏
- 关注
RSS订阅原创 转载-极化码系列（4）-编码之极化信道可靠性估计
前言由Arikan发明的Polar Code的经典编码算法已经在第二节基本阐述完毕，第三节则是对前文的举例。在编码实例中，有两个前提假设：1.假设采用二进制删除信道2.假设采用巴氏参数来评估各分裂子信道的可靠性。Arikan在讨论信道极化时，采用的是B-DMC（二进制离散无记忆信道），然而在构造极化码时需要使用的计算巴氏参数Z(W)Z(W)Z(W)方法的适用范围是BEC信道。又因为BEC是B-DMC的子集。因此在Polar Code编码时只能回落到BEC上来构造。注意：当信道不是BEC信道时，比如
2020-12-09 16:58:48
2365
原创 转载-极化码系列（3）-极化码的编码实例
前言在《Polar Code（2）编码原理》中详细阐述了Polar Code的编码原理。为了更好的理解编码的过程，本文将给出一个编码实例。设码长N=8N=8N=8，信息比特数K=4K=4K=4，下面列出所有使用到的公式。c1N=u1NGNGN=BNF⊗nF⊗n=F⊗F⊗(n−1)F=[1011]BN=RN(I2⊗BN/2)B2=I2c_1^N=u_1^NG_N \\G_N=B_NF ^{\otimes n} \\F^{\otimes n}= F\otimes F^{\otimes (n-1)} \
2020-12-05 11:51:56
2145
2
原创 转载-极化码系列（2）-极化码的编码原理
前言在《Polar Code（1）概述》中建立了PolarCode初步印象，本文将详细阐述Polar Code的编码原理。Polar Code是通过引入信道极化的概念而建立的。信道极化分两个阶段，分别是信道联合和信道分裂。通过信道的联合和分裂，各个子信道的对称容量将呈现两极分化的趋势：随着码长NNN的增加，一部分子信道的容量趋于1，而其余子信道的容量趋于0。Polar Code正是利用这一信道极化现象，在容量趋于1的KKK个子信道上传输信息比特，在其余子信道上传输冻结比特（即收发双方已知的固定比特，通常设
2020-12-01 17:33:58
6991
5
原创 转载-极化码系列（1）-极化码的起源和概述
x+y=zx+y=zx+y=z重大时间节点2016年11月18日，在美国内华达州里诺召开的3GPP RAN1 #87次会议，确定Polar Code作为5G eMBB（增强移动宽带）场景下控制信道编码方案。2008年，Erdal Arikan在国际信息论ISIT会议上首次提出了信道极化（Channel Polarization）的概念；2009年在“IEEE Transaction on Information Theory”期刊上发表了一篇长达23页的论文更加详细地阐述了信道极化，并基于信道极化给
2020-12-01 09:35:05
4013
原创 2020-09-18-并查集复习
并查集复习来自weiwei大佬的代码：https://leetcode-cn.com/problems/satisfiability-of-equality-equations/solution/shi-yong-bing-cha-ji-chu-li-bu-xiang-jiao-ji-he-we/class UnionFind { private int[] parent; public UnionFind(int len) { parent = new int[len
2020-09-18 21:49:33
84
原创 2020-08-19-对链表进行插入排序（O(1) 的空间复杂度）
代码参考来自：https://leetcode-cn.com/problems/insertion-sort-list/comments/ public ListNode insertionSortList(ListNode head) { ListNode dummy = new ListNode(-1); dummy.next = head; ListNode pre; while (head != null && h
2020-08-19 11:17:30
226
原创 2020-0817-归并排链表（递归和迭代）
递归：https://leetcode-cn.com/problems/sort-list/solution/sort-list-gui-bing-pai-xu-lian-biao-by-jyd/class Solution { public ListNode sortList(ListNode head) { if (head == null || head.next == null) return head; ListNode fast
2020-08-17 22:53:45
117
原创 2020-08-17-O(1)空间复杂度的反转栈
//反转一个栈 public void reverse(Stack<Integer> stack) { if (stack.isEmpty()) return; int value = getBottom(stack); reverse(stack); stack.push(value); } private int getBottom(Stack<Integer> stack) { .
2020-08-17 22:26:04
137
原创 2020-08-17-找小于n的素数的个数（厄拉多塞筛法）
笨重的解法，利用相对较大的素数都是 6n - 1 或者 6n + 5class Solution { public int countPrimes(int n) { if(n < 3) return 0; int res = 0; n -= 1; while(n >= 2) { if(isPrime(n)) { res++; }
2020-08-17 16:40:49
235
原创 2020-0807-背包问题九讲（待完善）
代码和思想：来源于大雪菜网站：https://www.acwing.com/about/遍历物品 -> 遍历约束条件 -> 遍历决策01背包问题每一个物品只能选一个，或者不选，求不超出容量的物品的最大价值。二维dp，遍历约束（体积），是什么顺序就无所谓了。import java.util.*;public class Main{ public static void main(String[] args) { Scanner sc = new Scanner
2020-08-07 15:31:48
175
原创 2020-0806-位运算
public int hammingWeight(int n) { int res = 0; while(n != 0) { res++; n &= (n - 1); } return res; }算一个数二进制的1的位数时，学到的东西。n = n & (n - 1);会把最后一个1减去n -= n & (-n); n & ( - n) 相当于得.
2020-08-06 14:55:21
89
原创 0713-2020-dp专题-股票等等
第一种，只卖买一次，那就是找出前面最小的买入价格，在最后卖出即可。121.买卖股票的最佳时机 public int maxProfit(int[] prices) { if(prices == null || prices.length == 0) return 0; int min = prices[0]; int max = 0; for(int i = 1;i < prices.length;i++) {
2020-07-13 11:40:16
169
原创 0527-2020-LEETCODE-27.解数独
自己写的不知道哪里出问题了，贴一个类似的评论区的代码，逻辑还是明显比自己的清晰好多。在自己代码基础上稍微改了改，用map加set存，代码来源：作者：Angus-Liu链接：https://leetcode-cn.com/problems/sudoku-solver/comments/class Solution { public void solveSudoku(char[][] board) { if (board == null || board.length ==
2020-06-27 22:30:45
126
原创 0626-2020-LEETCODE-拓扑排序
什么是拓扑排序？把这样一个 有向无环图 变成 线性的排序 就叫 拓扑排序。代码来源：https://leetcode-cn.com/problems/longest-increasing-path-in-a-matrix/solution/zhi-jie-tao-yong-tuo-bu-pai-xu-mo-ban-mei-you-ji-q/329.矩阵中的最长路径class Solution { public int longestIncreasingPath(int[][] matrix
2020-06-26 11:32:03
152
原创 0617-2020-dfs专题
695.岛屿的最大面积自己能写出来了，特别注意沉岛思想，就是每次判断当前的位置不为0以后max = 1，然后立即沉岛，以便下一次不会重复计算到这块面积。每次找不到要return 0 需要注意。class Solution { public int maxAreaOfIsland(int[][] grid) { int row = grid.length; int col = grid[0].length; int res = 0;
2020-06-17 15:46:54
449
原创 0614-2020-LEETCODE-5438.制作m束花所需要的最少天数
暴力解不出来啊，这道题确实没啥思路，二题选手退场了。下面介绍一下评论区的二分解法：核心还是利用花开先后的有序性，我们试图从成熟日期的max中挑出一天mid，如果mid天无法制作足够的花束，那么left = mid + 1,反之,right = mid - 1;太经典了，如何把开花天数的有序性加入呢，就是计算mid天的制作花束的数量时，巧妙的是采用从i = 0开始遍历，这样就保证了连续性，一旦有没成熟的花束，count立即置零，每次计算count是不是等于k，足不足够制作一束花，如果够的话，就count置
2020-06-14 16:08:49
128
1
原创 0612-2020-LEETCODE-单调栈专题
入门：739.每日温度 public int[] dailyTemperatures(int[] T) { if (T == null || T.length == 0) return new int[0]; int len = T.length; int[] res = new int[len]; Deque<Integer> stack = new ArrayDeque<>(); for
2020-06-12 16:02:11
149
原创 0612-2020-LEETCODE-15.三数之和(超时的经典解决方案/特判/排序)
暴力是超时的，第三个for用二分查找依然超时，需要加特判可以通过，特判：第一个数必须小于等于0，如果第一个数重复，就跳过，这样改代码的话可以通过。但是效率不高，最后我们还是要利用排序的双指针，固定第一个值，把双指针定位在第一个数的左右两端，利用数组的有序性，进行双指针的移动。代码来源：https://leetcode-cn.com/problems/3sum/solution/hua-jie-suan-fa-15-san-shu-zhi-he-by-guanpengchn/ public List&
2020-06-12 11:14:51
233
原创 0610-2020-LEETCODE-9.判断是否是回文数(转字符串/数学除余解法)
转字符串的不贴了 public boolean isPalindrome(int x) { if(x < 0) return false; int res = 0; int y = 0; int temp = x; while(temp != 0){ y = temp % 10; temp /= 10; res = res * 10 + y;
2020-06-10 10:02:37
121
原创 0609-2020-LEETCODE-不用加减乘除的加法(位运算)
思路：肯定是用位运算，但是要好好思考，位运算怎么用？要考虑的是不进位的值和进位的值。代码来源：https://leetcode-cn.com/problems/bu-yong-jia-jian-cheng-chu-zuo-jia-fa-lcof/solution/mian-shi-ti-65-bu-yong-jia-jian-cheng-chu-zuo-ji-7/ public int add(int a, int b) { while(b != 0){ int
2020-06-09 20:11:17
107
原创 0609-2020-LEETCODE-58.最后一个单词的长度(API/手动写从后向前遍历)
自己写的是调API public int lengthOfLastWord(String s) { s = s.trim(); return s.length() - 1 - s.lastIndexOf(" "); }从后向前遍历代码思路来源：https://leetcode-cn.com/problems/length-of-last-word/solution/hua-jie-suan-fa-58-zui-hou-yi-ge-dan-ci-de-chan
2020-06-09 16:36:07
75
原创 0609-2020-LEETCODE-有效的括号对(栈的典型应用)
自己写的是纯用栈写的，只判断是不是右括号，可以直接抵消的话继续进行，否则就匹配不上，左括号直接进，最后返回栈是否为空。 public boolean isValid(String s) { Deque<Character> stack = new ArrayDeque<>(); for (int i = 0; i < s.length(); i++) { char c = s.charAt(i);
2020-06-09 16:09:39
65
原创 0608-2020-LEETCODE-把字符串转换成整数(经典处理越界的问题)
自己写的代码，代码最后的异常捕获是看的之前代码，应该是看的之前的题解写的。public int strToInt(String str) { if (str == null || str.length() == 0) return 0; str = str.trim(); if (str.length() == 0) return 0; boolean flag = true; if (str.charAt(0) == '+'
2020-06-08 17:13:35
137
原创 0608-2020-LEETCODE-192.周赛回顾-(自定义数组排序算法/浏览器访问记录)
这个就直接自定义排序方法就行。其中自定义排序方法：可以简洁地写成：Arrays.sort(temp,(x,y) -> (Math.abs(x - m) == Math.abs(y - m) ? y - x : Math.abs(y - m) - Math.abs(x - m)));class Solution { public int[] getStrongest(int[] arr, int k) { Arrays.sort(arr); int[
2020-06-08 16:02:15
85
原创 0608-2020-LEETCODE-990-等式方程的可满足性(并查集的典型应用)
其实思路的框架自己也想到了，但是没有想出如何处理并查集的代码实现。并查集需要好好看看，需要注意的是这的之前的kruskal算法有关，需要仔细再复习复习。思路1.把等式全找出来，加入并查集。代码显示为union方法的调用。2.把不等式全找出来，判断不等式在不在并查集里。3.一旦有不等式在并查集里连通，说明条件有冲突，直接返回false；否则返回true代码来源：https://leetcode-cn.com/problems/satisfiability-of-equality-equation
2020-06-08 15:07:42
102
原创 0606-2020-LEETCODE-经典.63-股票的最大利润
自己写的稍微有点复杂了，其实完全可以不用数组。用一个cost 和 profit 就可以了。但是值得高兴的是，自己的思路跟上了大佬的思路，想到了动态规划。 public int maxProfit(int[] prices) { if(prices == null || prices.length == 0) return 0; int len = prices.length; int[] dp = new int[len]; dp[0] =
2020-06-06 16:17:29
303
原创 0606-2020-LEETCODE-经典.61-扑克牌中的顺子(最大值/最小值/去重)
自己写的，略微有些麻烦。 public boolean isStraight(int[] nums) { int zCount = 0; int[] arr = new int[5]; int index = 0; for (int i = 0; i < nums.length; i++) { if (nums[i] == 0) zCount++; else arr[index++] =
2020-06-06 15:33:07
554
原创 0605-2020-LEETCODE-能实时记录最大值的双端队列(API接口)
思路首先实现一个队列不难。直接调用现成的库类就行。但是要实时的记录max就不容易，因为当你记录的最大值poll出去的时候，你不知道当前的最大值是哪个。所以就想到记录一个一下最大值的双端队列。4 2 0 3最大值： 4最大值 ： 4 2最大值： 4 2 0 最大值： 4 3 因为 4出去以后 2,0出不出去不影响最大值。public class MaxQueue { Deque<Intege
2020-06-05 17:12:28
102
原创 0605-2020-LEETCODE-经典.56-和为s的正数递增序列-经典57-和为s的连续正数序列(双指针/滑动窗口/前缀和)
可以直接使用set集合，边存边添加，递增序列，有序会想到二分，但是还是滑动窗口的双指针算法比较快。 public int[] twoSum1(int[] nums, int target) { HashSet<Integer> set = new HashSet<>(); for(int e : nums){ int num = target - e; if(set.contains(num)){
2020-06-05 10:37:39
131
原创 0605-2020-LEETCODE-经典.29-顺时针打印数组-(旋转矩阵/简洁写法)
自己写的是使用两个四维的旋转矩阵，再加一个visited访问boolean访问数组以下代码相对就简洁很多。代码来源：作者：Krahetshttps://leetcode-cn.com/problems/shun-shi-zhen-da-yin-ju-zhen-lcof/solution/mian-shi-ti-29-shun-shi-zhen-da-yin-ju-zhen-she-di/ public int[] spiralOrder(int[][] matrix) { if(m
2020-06-05 09:41:31
139
原创 0604-2020-LEETCODE-238-除自身以外数组的乘积.经典.66-构建乘积数组(前缀后缀乘积)
题目要求不能用除法，所以还是从乘积入手。自己写的前缀积 * 后缀积代码，是比较正常的传统解题思路，比较容易想到。受网友启发 public int[] productExceptSelf(int[] nums) { int len = nums.length; int[] resL = new int[len]; resL[0] = nums[0]; int[] resR = new int[len]; resR[len -
2020-06-04 11:03:19
86
原创 0602-2020-LEETCODE-二分查找专题.经典53
二分什么时候用呢？给的数据是有序的，就要想到是不是可以使用二分。经典.53. 统计一个数字在排序数组中出现的次数。 public int search(int[] nums, int target) { if(nums == null || nums.length == 0 || nums[nums.length - 1] < target) return 0; int left = 0,right = nums.length - 1; int re
2020-06-03 17:03:38
176
原创 0602-2020-LEETCODE-经典.52-寻找链表的公共节点(快慢指针)
自己写的暴力解法，复杂度O(n2) public ListNode getIntersectionNode1(ListNode headA, ListNode headB) { if (headA == null || headB == null) return null; ListNode h1 = headA; ListNode h2 = headB; while (h1 != h2){ while (h1 !=
2020-06-02 22:13:17
161
原创 0602-2020-LEETCODE-经典.50-第一个只出现一次的字符(数组/哈希)
自己写的代码，很冗余，但是竟然效率还挺高 public char firstUniqChar(String s) { if ("".equals(s)) return 0; char[] arr = s.toCharArray(); int[] res = new int[128]; for (char c : arr) { res[c]++; } ArrayList<Charac
2020-06-02 16:36:33
80
原创 0602-2020-LEETCODE-经典.49-寻找第N个丑数(dp)
自己写的超时版本，每次计算没有用到之前的计算结果。 public int nthUglyNumber(int n) { if (n == 1) return 1; int[] arr = new int[n]; arr[0] = 1; int index = 1; int num = 2; while (index < n){ if (isUgly(num)){
2020-06-02 15:41:13
132
原创 0602-2020-LEETCODE-面试48.最长不含重复字符的子串长度(dp/哈希)
这个算线性遍历，复杂度在最坏的时候应该是O(n2)public int lengthOfLongestSubstring(String s) { char[] arr = s.toCharArray(); int len = arr.length; int[] map = new int[128]; int left = 0,right = 0; int max = 0; while (right < l
2020-06-02 11:19:57
110
原创 0602-2020-LEETCODE-面试.64求1+2+...+n(要求不能使用乘除法和条件判断语句)
虽然说不能使用条件判断语句，但是我们可以使用 && 的短路效应来结束 && 右边的递归代码来源：链接：https://leetcode-cn.com/problems/qiu-12n-lcof/solution/mian-shi-ti-64-qiu-1-2-nluo-ji-fu-duan-lu-qing-xi-/来源：力扣（LeetCode）著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。int res = 0; public int s
2020-06-02 09:56:09
156
原创 0601-2020-LEETCODE-经典.46把数字翻译成字符串-经典.47礼物的最大价值(经典的DP问题)
一开始自己想用DFS，死活想不出来，最后看评论可以用DP，今天的两道题都是用dp解的，一定要多注意想不出来的时候，特别是数组字符串问题，多用dp。评论链接：https://leetcode-cn.com/problems/li-wu-de-zui-da-jie-zhi-lcof/comments/ public int translateNum(int num) { if (num <= 9) return 1; char[] arr = String.valueO
2020-06-01 20:23:17
120
原创 0601-2020-LEETCODE-把数组排成最小的数
比较容易想到的是：利用字符串的比较方法，来比较各个字符的先后顺序，但是有一个问题，比如 3 和 30 这个不太好比较，根据字符串的比较方法，3 和 30 的第一位相同，又因为3只有一位，所以不再比较，直接返回长度更小的那一个，就是 3 ，即 3 比 30 小，但是 330 比 303 大，所以如何进行字符串的比较是一个重要的问题。根据大佬的文章，可以看出，可以返回任意两个字符串相加的结果，再进行比较，返回合适的顺序。可以依然例举刚刚的例子：设x = 3,y = 30,设计 x + y > y
2020-06-01 11:14:40
119
原创 0528-2020-LEETCODE-53-最大连续数组子序和(贪心)
代码来源：https://leetcode-cn.com/problems/maximum-subarray/solution/hua-jie-suan-fa-53-zui-da-zi-xu-he-by-guanpengchn/public int maxSubArray(int[] arr){ int ans = arr[0],sum = 0; for (int e : arr) { if (sum > 0) {
2020-05-28 22:27:46
109
空空如也
空空如也
TA创建的收藏夹 TA关注的收藏夹
TA关注的人