矩阵中战斗力最弱的 K 行
 
一、题目
 
给你一个大小为 m * n 的矩阵 mat，矩阵由若干军人和平民组成，分别用 1 和 0 表示。
 
请你返回矩阵中战斗力最弱的 k 行的索引，按从最弱到最强排序。
 
如果第 i 行的军人数量少于第 j 行，或者两行军人数量相同但 i 小于 j，那么我们认为第 i 行的战斗力比第 j 行弱。
 
军人 总是 排在一行中的靠前位置，也就是说 1 总是出现在 0 之前。
 
示例：
 
输入：mat =
[[1,1,0,0,0],
[1,1,1,1,0],
[1,0,0,0,0],
[1,1,0,0,0],
[1,1,1,1,1]],
k = 3
输出：[2,0,3]
 
解释：
 
每行中的军人数目：
行 0 -> 2
行 1 -> 4
行 2 -> 1
行 3 -> 2
行 4 -> 5
从最弱到最强对这些行排序后得到 [2,0,3,1,4]
 
二、题解
 
单独分析每一行，并记录原始下标和目标个数
筛选符合题目的数据并返回
 
/**
 * @param {number[][]} mat
 * @param {number} k
 * @return {number[]}
 */
var kWeakestRows = function(mat, k) {
  const len = mat.length;
  const arr = [];
  for (let i = 0; i < len; i++) {
    arr.push({ index: i, count: countS(mat[i]) });
  }
  arr.sort((a, b) => {
    if (a.count === b.count) return a.index - b.index;
    return a.count - b.count;
  });
  return arr.slice(0, k).map(({ index }) => index);
};
// 只有统一单行的时候使用了2分法
const countS = function(nums) {
  const len = nums.length;
  let left = 0;
  let right = len - 1;
  if (nums[right] === 1) return len;
  while (left <= right) {
    const mid = left + ((right - left) >> 1);
    if (nums[mid] === 1) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }
  return left;
};
 
三、写在最后
 
本文是附加题，可能仅仅借助了二分思想中的一部分，加油！
 
如果对你有所帮助不妨给本项目的github 点个 star，这是对我最大的鼓励
 
关于我
 
花名：余光
WX：j565017805
沉迷 JS，水平有限，虚心学习中
 
其他沉淀
 
前端进阶笔记
JS 版 LeetCode 题解
CSDN
 
  

 
文章目录
 
一、弱对偶性质
二、弱对偶定理分析
三、弱对偶定理推论 1
四、弱对偶定理推论 2 对偶问题的无界性
五、弱对偶定理推论 3

 

 

 

 

 
一、弱对偶性质
 
 

 
弱对偶定理 :
 
假设 ${\mathrm{X}}^0$ 和 ${\mathrm{Y}}^0$ 分别是 问题 $(\mathrm{P})$ ( 目标函数求最大值 ) 和 问题 $(\mathrm{D})$ ( 目标函数求最小值 ) 的 可行解 , 则必有 $\mathrm{C}{\mathrm{X}}^0\le {\mathrm{Y}}^0\mathrm{b}$ ,
 
展开后为 ${\sum }_{\mathrm{j}=1}^{\mathrm{n}}{\mathrm{c}}_{\mathrm{j}}{\mathrm{x}}_{\mathrm{j}}\le {\sum }_{\mathrm{i}=1}^{\mathrm{m}}{\mathrm{y}}_{\mathrm{i}}{\mathrm{b}}_{\mathrm{i}}$
 

 

 

 

 
二、弱对偶定理分析
 
 

 
弱对偶定理分析 :
 

 
问题 $(\mathrm{P})$ 与 问题 $(\mathrm{D})$ 互为对偶 , 其中
 
问题 $(\mathrm{P})$ 是 原问题 , 目标函数求 最大值 ,
 
问题 $(\mathrm{D})$ 是 对偶问题 , 目标函数求 最小值 ;
 

 
$\mathrm{C}{\mathrm{X}}^0$ 是 原问题 $(\mathrm{P})$ 目标函数 代入 ${\mathrm{X}}^0$ 可行解之后的值 ; 计算出一个具体的数值 ;
 
${\mathrm{Y}}^0\mathrm{b}$ 是 对偶问题 $(\mathrm{D})$ 目标函数 代入 ${\mathrm{Y}}^0$ 可行解之后的值 ; 计算出一个具体的数值 ;
 

 
只要互为对偶的两个问题都有可行解 , 目标函数求最大值的 $\mathrm{C}{\mathrm{X}}^0$ 值 ( 原问题 ) , 一定小于等于 , 目标函数求最小值的 ${\mathrm{Y}}^0\mathrm{b}$ 值 ( 对偶问题 ) ;
 

 
如果互为对偶的两个问题都有可行解 , 原问题求最大值 , 对偶问题求最小值 ,
 

 
求最大值的原问题一定都 在某个界限值之下 ,
 
求最小值的对偶问题一定都 在某个界限之上 ,
 
上述描述中的 界限值是同一个界限值 ;
 

 

 

 

 
三、弱对偶定理推论 1
 
 

 
弱对偶定理推论 1 :
 
原问题 任何一个 可行解 的目标函数值 , 都是其对偶问题 目标函数值的下界 ;
 
反之 ,
 
对偶问题 任何一个 可行解 的目标函数值 , 都是其原问题 目标函数的上界 ;
 

 
问题 $(\mathrm{P})$ 与 问题 $(\mathrm{D})$ 互为对偶 , 其中
 
问题 $(\mathrm{P})$ 是 原问题 , 目标函数求 最大值 ,
 
问题 $(\mathrm{D})$ 是 对偶问题 , 目标函数求 最小值 ;
 

 
$\mathrm{C}{\mathrm{X}}^0$ 是 原问题 $(\mathrm{P})$ 目标函数 代入 ${\mathrm{X}}^0$ 可行解之后的值 , 该值是其对偶问题目标函数值的下界 ;
 
${\mathrm{Y}}^0\mathrm{b}$ 是 对偶问题 $(\mathrm{D})$ 目标函数 代入 ${\mathrm{Y}}^0$ 可行解之后的值 , 该值是其原问题目标函数值的上界 ;
 

 

 

 

 
四、弱对偶定理推论 2 对偶问题的无界性
 
 

 
弱对偶定理推论 2 : ( 对偶问题的无界性 )
 
在一对 对偶问题 $(\mathrm{P})$ 和 $(\mathrm{D})$ 中 ,
 
如果其中 一个线性规划问题可行 , 但是 目标函数无界 , 则 另外一个问题没有可行解 ;
 
如果其中 一个线性规划问题不可行 , 其 对偶问题不一定不可行 ;
 

 

 
弱对偶定理推论 2 ( 对偶问题的无界性 ) 解析 :
 
如果目标函数求最小值的问题无界 , 则 取值一直可以减小 , 此时不存在一个界限值 ,
 
因此其对偶问题 一定没有可行解 ;
 
只要该问题有可行解 , 将可行解代入目标函数 , 即可获得一个 界限值 ;
 
这个界限值一定是另外对应对偶问题的可行解 ;
 

 
如果目标函数求最大值的问题无界 , 则 取值一直可以增大 , 此时不存在一个界限值 ,
 
因此其对偶问题 一定没有可行解 ;
 
只要该问题有可行解 , 将可行解代入目标函数 , 即可获得一个 界限值 ;
 
这个界限值一定是另外对应对偶问题的可行解 ;
 

 

 
一个线性规划是不可行的 , 其对偶问题不一定不可行 ;
 

 
一个线性规划不可行 , 其对偶问题可能有如下情况 :
 
 
① 有最优解 ( 不会成立 ) , 根据最优性定理 , 一个有最优解 , 另一个也有最优解 ;
 
 
② 无界解
 
 
③ 无可行解
 
 

 
原问题 与 对偶问题 ,
 
一个无界 , 另一个肯定不可行 ;
 
一个不可行 , 另一个不一定可行 , 有两种情况 ① 无界解 ② 无可行解 ;
 

 

 

 

 
五、弱对偶定理推论 3
 
 

 
弱对偶定理推论 3 :
 
在一对 对偶问题 $(\mathrm{P})$ 和 $(\mathrm{D})$ 中 ,
 
如果其中 一个线性规划问题可行 , 而 另一个线性规划问题不可行 , 则 该可行问题的目标函数是无界的;

我们平常用的都是对象的强引用，如果有强引用存在，GC是不会回收对象的。我们能不能同时保持对对象的引用，而又可以让GC需要的时候回收这个对象呢？.NET中提供了WeakReference来实现。弱引用可以让您保持对对象的引用，同时允许GC在必要时释放对象，回收内存。对于那些创建便宜但耗费大量内存的对象，即希望保持该对象，又要在应用程序需要时使用，同时希望GC必要时回收时，可以考虑使用弱引用。
 
一：什么是弱引用
 
      了解弱引用之前，先了解一下什么是强引用
 
　　例如 ： Object obj=new Object();     就是一个强引用，内存分配一份空间给用以存储Object数据，这块内存有一个首地址，也就是obj所保存的数据，内存分配的空间中不仅仅保存着Object对象信息，还保存着自己（Object本身）被引用的次数。
 
　　当一个对象被强引用的形式创建的时候，本身被引用的次数已经为1.
 
　　接着Object o=obj; 这句代码执行之后，obj指向的Object的存储空间已经被引用了2次，所以Object保存的被引用数值为2.
 
　　总结：强引用最终导致的结果就是被引用的对象的被引用次数+1;
 
　　相反的弱引用就是不会对被引用对象的被引用次数有任何影响。
 
二：弱引用有什么作用
 
　　防止内存泄露。
 
　　
 
Object obj=new Object();
 
　　当你在通过异步的形式访问网络上面的资源的时候，需要的时间可能会比较长，在数据返回之前，用户很可能转向了其他的页面，如果异步访问的对象(obj)对本地的一个对象(Object)是强引用的话，那么在这个异步访问对象(obj)被释放之前，也即在数据被回调之前，这个被引用的对象(Object)是不会被销毁的，这样一来，就导致内存一直被占用。
 
　　WeakReference weakObj=new WeakReference(Object);
 
　　此时就可以使用弱引用，弱引用对象(weakObj)发出异步请求，在回调之前，如果用户要转到其他的页面，这个被引用的对象(Object)是可以被释放的，这样子就不会出现内存一直被占用的现象。
 
三：怎样使用弱引用
 
　　弱引用类： WeakReference //有两个重载的构造函数
 
　　
 
WeakReference WeakObj=new WeakReference(Object); //弱引用方式
 
　　IsAlive属性是判断此弱引用对象所引用的对象是否还存在，存在：IsAlive=True;
 
     Target属性是设置该弱引用对象所引用的数据对象的值
 
 
 
       弱引用使用起来很简单，看下面的代码：
 
Object obj = new Object();
WeakReference wref = new WeakReference( obj );
obj = null;
 

        第一行代码新建了一个新的对象，这里叫它对象A，obj是对对象A的强引用。接着第二行代码新建了一个弱引用对象，参数就是对象A的强引用，第三行代码释放掉对对象A的强引用。这时如果GC进行回收，对象A就会被回收。
 怎样在取得对象A的强引用呢？很简单，请看代码2：
  
 
Object obj2 = wref.Target;
if( obj2 != null )
{
    // 做你想做的事吧。
}
else
{
    // 对象已经被回收，如果要用必须新建一个。
}
 
       只要显示的将弱引用的Target属性附值就会得到弱引用所代表对象的一个强引用。不过在使用对象之前要对其可用性进行检查，因为它可能已经被回收了。如 果你得到的是null（VB.NET下为Nothing），表明对象已经被回收，不能再用了，需要重新分配一个。如果不是null，就可以放心大胆的用 了。

1. 强符号和弱符号
 
1.1 u-boot和kernel中的__weak指令
 
u-boot和kernel比较普遍地使用了__weak来定义函数。
 
在include\linux\compiler-gcc.h中__weak是这样定义的：
 
#define __weak              __attribute__((weak))
 
GCC通过__attribute__((weak))指令定义的函数或变量称为弱符号（Weak Symbol），实际上这个指令大部分时候都是用来定义函数，很少用于定义变量。 
 
编译器默认函数和初始化了的全局变量为强符号（Strong Symbol），未初始化的全局变量为弱符号（Weak Symbol）。
 
1.2 强符号和弱符号的链接规则
 
<<程序员的自我修养>>第三章对这个强弱符号的链接规则做了很好的总结：
 
 
 
针对强弱符号的概念，链接器就会按照如下规则处理与选择被多次定义的全局符号：
 
 
规则1：不允许强符号被多次定义（即不同的目标文件中不能有同名的强符号）；如果有多个强符号定义，则链接器报符号重复定义错误。
规则2：如果一个符号在某个目标文件中是强符号，在其他文件中都是弱符号，那么选择强符号。
规则3：如果一个符号在所有目标文件中都是弱符号，那么选择其中占用空间最大的一个。比如目标文件A定义全局变量global为int型，占4个字节；目标文件B定义global为doulbe型，占8个字节，那么目标文件A和B链接后，符号global占8个字节（尽量不要使用多个不同类型的弱符号，否则容易导致很难发现的程序错误）。
 
 
规则1很好理解，如果程序中多次定义了一个初始化过的全局变量（如int a=0），则编译器会报告multiple definition的错误，比较常见。
 
多次定义的全局函数也属于此类，因为函数名也是一个符号变量，只不过它指向了随后定义的函数体，而且这个变量是只读的，不可改变。这也是为什么函数名可以赋值给一个变量，但是却无法给函数名赋值的原因。
 
规则2就是u-boot和kernel中最常用的技巧了。
 
首先在平台无关的代码中定义一个__weak属性的函数，如u-boot的board_f.c的文件头部定义了很多led相关的空函数：
 
__weak void coloured_LED_init(void) {}
__weak void red_led_on(void) {}
__weak void red_led_off(void) {}
__weak void green_led_on(void) {}
__weak void green_led_off(void) {}
__weak void yellow_led_on(void) {}
__weak void yellow_led_off(void) {}
__weak void blue_led_on(void) {}
__weak void blue_led_off(void) {} 
 
如果需要这些led相关的功能，再在相关的文件中重新定义并实现这些函数即可，例如文件gpio_led.c中在宏CONFIG_GPIO_LED_STUBS打开时就调用__led_set重新实现了这些函数。
 
规则3指明了同名弱符号的多个定义以占用空间最大的为准，主要是针对不用类型的变量而言；对于函数，其对应的符号相当于一个只读指针变量，而指针类型大小是固定的，不存在这个问题。
 
2. 强引用和弱引用
 
<<程序员的自我修养>>第三章对也对强引用和弱引用做了说明：
 
 
 
弱引用和强引用 目前我们所看到的对外部目标文件的符号引用在目标文件被最终链接成可执行文件时，它们必须要被正确决议，如果没有找到该符号的定义，链接器就会报符号未定义错误，这种被称为强应用（Strong Reference）。与之相对应还有一种弱引用（Weak Reference），在处理弱引用时，如果该符号有定义，则链接器将该符号的引用决议；如果该符号未被定义，则链接器对于该引用不报错。链接器处理强引用和弱引用的过程几乎一样，只是对于未定义的弱引用，链接器不认为它是一个错误。一般对于未定义的弱引用，链接器默认其为0，或者是一个特殊的值，以便于程序代码能够识别。
 
 
在GCC中，我们可以通过使用__attribute__((weakref))扩展关键字来声明对一个外部函数的引用为弱引用。比如下面这段代码：
 
 
__attribute__ ((weakref)) void foo();
int main()
{
    foo();
}
 
 
 
我们可以将它编译成一个可执行文件，GCC并不会报链接错误。但是当我们运行这个可执行文件时，会发生运行错误。因为当main函数试图条用foo函数是，foo函数的地址为0，于是发生了非法地址访问的错误。一个改进的例子是：
 
 
__attribute__ ((weakref)) void foo();
int main()
{
  if (foo) foo();
}
 
 
 
这种弱符号和弱引用对于库来说十分有用，比如库中定义的弱符号可以被用户定义的强符号所覆盖，从而使得程序可以使用自定义版本的库函数；或者程序可以对某些扩展功能模块的引用定义为弱引用，当我们将扩展模块与程序连接在一起时，功能模块就可以正常使用；如果我们去掉了某些功能模块，那么程序也可以正常链接，只是缺少了相应的功能，这使得程序的功能更加容易裁剪和组合。
 
 
专门检查过u-boot v2016.09和linux v3.3-3.8的代码，没有找到采用弱引用来定义函数的情况，可见也不是很常用的做法。
 
4. 其它
 
对于弱符号（Weak Symbol）和弱引用，其都仅是GNU工具链GCC对C语言语法的扩展，并不是C本身的语言特性。 
 有提到微软的MSVC就不支持弱符号和弱引用特性。