日期: 2021 年 7 月 5 日

Macbook外接2k显示器开启hidpi的方法

一、前言：

大家平时用macbook开发的时候一般都喜欢外接一个显示器开发吧？这里我用了一台2k的显示器，我们要开启hidpi模式。

你们会问到为什么要开启hidpi模式呢？我的2k显示器是2560*1440分别率，如果采用默认的设置，那么在显示器上面的字会特别的小。如果我们开启显示器的hidpi模式就类似于macbook的retina模式，那么就会在图像大小不变的情况下，变的特别清晰。

我在升级*新的10.13.4后，我的2k显示器的分别率恢复默认了，SwitchResX软件不起作用了，因此我打算采用另一种轻量级的方式去开启2k显示器的hidpi模式。如果你的SwitchResX因为升级系统出问题了，或许这篇文章可以帮到你。

二、方法：

2.1 准备工具

1.PlistEdit Pro

2.RDM

3.16进制和10进制转换工具

这里工具我就不提供下载了，大家支持正版吧。

2.2 关闭System Integrity Protection SIP

我们重启macbook，在开机的时候按command+R进入恢复模式，然后我们在终端输入

csrutil disable

当我们设置完分辨率后可以再输入以下命令打开，保证安全性。

csrutil enable

2.3 开启macbook的hidpi

打开终端输入

sudo defaults write /Library/Preferences/com.apple.windowserver DisplayResolutionEnabled -bool YES

回车后，需要输入管理员密码，然后再回车，完毕。

2.4 获取2k显示器的DisplayVendorID和DisplayProductID

我们先不插外界显示器的连接线，获取macbook自己屏幕的ID，然后再插上外接显示器获取外界显示器的ID。

在终端输入如下命令

ioreg -l | grep “DisplayVendorID”

ioreg -l | grep “DisplayProductID”

如图：

%title插图%num

我经过显示器的拔插就可以筛选出外接显示器的两个ID。DisplayVendorID为2513，DisplayProductID为32795

我们新建一个名字为DisplayVendorID-XXXX的文件夹，其中XXXX是DisplayVendorID的16进制小写即9d1，则文件夹名字为DisplayVendorID-9d1。然后再创建一个空白文件，这里你们可以直接用我的模板进行修改。传送门->https://www.ianisme.com/download/201803/DisplayVendorID-9d1.zip

我们将这个文件命名为DisplayProductID-YYYY，其中YYYY即DisplayProductID的16进制小写即801b。

2.5 编辑DisplayProductID-YYYY文件

我们使用PlistEdit Pro去打开这个文件，然后在DisplayProductID和DisplayVendorID处填写这两个值的10进制原始值，然后下面按照如下规则去设置对应的分辨率。

例如我这里要设置 1920 * 1080 hidpi 的设置，我设置 1920 * 1080 和 3840 * 2160 两种。

1920的16进制是00000780，1080的16进制是00000438，后面需要拼接上00000001 00200000

即：

00000780 00000438 00000001 00200000

3840的16进制是00000F00，2160的16进制是00000870，后面需要拼接上00000001 00200000

00000F00 00000870 00000001 00200000

我们将这个数据添加到文件中去。

文件中添加了几个例子。

如图：

%title插图%num

然后我们把这个文件夹拷贝到/System/Library/Displays/Contents/Resources/Overrides/中去

2.6 使用RDM进行切换

重启系统打开RDM，这就可以进行切换了。

如图：

%title插图%num

三、总结

工欲善其事，必先利其器。macbook配上一个2k甚至5k的显示器，无疑是可以提高程序员的工作效率的。以上是借鉴网上的一些文章，整理了一下，提供给大家一个方便的解决方案。

iOS代码瘦身实践：删除无用的类

Mach-o 文件中 __DATA objc_classrefs 段记录了引用类的地址，DATA __objc_classlist 段记录了所有类的地址，取差集可以得到未使用的类的地址，然后进行符号化，就可以得到未被引用的类信息。

引用类地址

可以通过Mac自带的工具otool打印Mach-o中的段信息，需要注意的是模拟器和真机对应的可执行文件，数据的存储方式不同需要加以区分。
可以通过file命令获取到arch。






#binary_file_arch: distinguish Big-Endian and Little-Endian
#file -b output example: Mach-O 64-bit executable arm64
binary_file_arch = os.popen('file -b ' + path).read().split(' ')[-1].strip()








在取类地址的时候区分x86_64和arm










def pointers_from_binary(line, binary_file_arch):
    line = line[16:].strip().split(' ')
    pointers = set()
    if binary_file_arch == 'x86_64':
        #untreated line example:00000001030cec80    d8 75 15 03 01 00 00 00 68 77 15 03 01 00 00 00
        pointers.add(''.join(line[4:8][::-1] + line[0:4][::-1]))
        pointers.add(''.join(line[12:16][::-1] + line[8:12][::-1]))
        return pointers
    #arm64 confirmed,armv7 arm7s unconfirmed
    if binary_file_arch.startswith('arm'):
        #untreated line example:00000001030bcd20    03138580 00000001 03138878 00000001
        pointers.add(line[1] + line[0])
        pointers.add(line[3] + line[2])
        return pointers
    return None







通过otool -v -s __DATA __objc_classrefs获取到引用类的地址。










def class_ref_pointers(path, binary_file_arch):
    ref_pointers = set()
    lines = os.popen('/usr/bin/otool -v -s __DATA __objc_classrefs %s' % path).readlines()
    for line in lines:
        pointers = pointers_from_binary(line, binary_file_arch)
        ref_pointers = ref_pointers.union(pointers)
    return ref_pointers







所有类地址


通过otool -v -s __DATA __objc_classlist获取所有类的地址。










def class_list_pointers(path, binary_file_arch):
    list_pointers = set()
    lines = os.popen('/usr/bin/otool -v -s __DATA __objc_classlist %s' % path).readlines()
    for line in lines:
        pointers = pointers_from_binary(line, binary_file_arch)
        list_pointers = list_pointers.union(pointers)
    return list_pointers







取差集


用所有类信息减去引用类的信息，此时我们可以拿到未使用类的地址信息。










unref_pointers = class_list_pointers(path, binary_file_arch) - class_ref_pointers(path, binary_file_arch)







符号化


通过nm -nm命令可以得到地址和对应的类名字。










def class_symbols(path):
    symbols = {}
    #class symbol format from nm: 0000000103113f68 (__DATA,__objc_data) external _OBJC_CLASS_$_EpisodeStatusDetailItemView
    re_class_name = re.compile('(w{16}) .* _OBJC_CLASS_$_(.+)')
    lines = os.popen('nm -nm %s' % path).readlines()
    for line in lines:
        result = re_class_name.findall(line)
        if result:
            (address, symbol) = result[0]
            symbols[address] = symbol
    return symbols







过滤


在实际分析的过程中发现，如果一个类的子类被实例化，父类未被实例化，此时父类不会出现在__objc_classrefs这个段里，在未使用的类中需要将这一部分父类过滤出去。使用otool -oV可以获取到类的继承关系。










def filter_super_class(unref_symbols):
    re_subclass_name = re.compile("w{16} 0xw{9} _OBJC_CLASS_$_(.+)")
    re_superclass_name = re.compile("s*superclass 0xw{9} _OBJC_CLASS_$_(.+)")
    #subclass example: 0000000102bd8070 0x103113f68 _OBJC_CLASS_$_TTEpisodeStatusDetailItemView
    #superclass example: superclass 0x10313bb80 _OBJC_CLASS_$_TTBaseControl
    lines = os.popen("/usr/bin/otool -oV %s" % path).readlines()
    subclass_name = ""
    superclass_name = ""
    for line in lines:
        subclass_match_result = re_subclass_name.findall(line)
        if subclass_match_result:
            subclass_name = subclass_match_result[0]
        superclass_match_result = re_superclass_name.findall(line)
        if superclass_match_result:
            superclass_name = superclass_match_result[0]

        if len(subclass_name) > 0 and len(superclass_name) > 0:
            if superclass_name in unref_symbols and subclass_name not in unref_symbols:
                unref_symbols.remove(superclass_name)
            superclass_name = ""
            subclass_name = ""
    return unref_symbols







为了防止一些三方库的误伤，还可以去过滤一些前缀，或者是是仅保留带有某些前缀的类。








for unref_pointer in unref_pointers:
        if unref_pointer in symbols:
            unref_symbol = symbols[unref_pointer]
            if len(reserved_prefix) > 0 and not unref_symbol.startswith(reserved_prefix):
                continue
            if len(filter_prefix) > 0 and unref_symbol.startswith(filter_prefix):
                continue
            unref_symbols.add(unref_symbol)







*终结果保存在脚本目录下。










script_path = sys.path[0].strip()
f = open(script_path+"/result.txt","w")
f.write( "unref class number:   %d
" % len(unref_symbles))
f.write("
")
for unref_symble in unref_symbles:
    f.write(unref_symble+"
")
f.close()








这个思路在一定程度上能够减少代码的冗余，减小包的体积。因为是静态分析，不能包括动态调用的情况，对于需要删除的类需要进一步的确认。

	


	
	






	
	

		
初涉iOS逆向工程：免越狱修改微信（外观篇）
	


	

		
美国学者埃德加·戴尔（Edgar Dale）1946年提出了“学习金字塔”（Cone of Learning）的理论。他提到：学习效果在50%以上的，都是主动学习包括讨论、实践和讲授。我希望能通过做笔记的方式，巩固自己学过的知识，以及分享这些知识给其他对此感兴趣的人。


前言


微信成立七年多了，主界面也一直没有变过，和刚推出一样的简洁，纯粹。 但是看久了这个唯一的主题，总会有一些眼腻。偶然在网上看到了美化版的微信，而这些“分身版”、“美化版”的客户端预留了大量高危接口，一不注意手机就会中招（详情参考 ：微信双开是定时炸弹？关于非越狱iOS上微信分身高危插件ImgNaix的分析），于是生出了自己捣鼓的念头。刚开始的时候什么都不懂，做了一大堆无用功，写下来避免更多人重蹈覆辙。


iMazing导入（失败）


之前在Mac上用iMazing改过几个小游戏的数据，所以我先试着从iMazing导出，结果发现导出的.imazingapp文件只有几份简单的数据（猜测是没受签名保护的文件），根本没有能修改的东西，心态崩了。


PP/爱思助手导入（失败）


这是网上出现*多的方法，在PP助手上下载正版ipa，提取其中的文件，发现朋友圈的颜色在其根目录下的color.css文件中。直接用记事本打开随便修改几个RGB颜色，保存。导入到手机时出现验证失败的提示，很明显是签名的问题。网上对这个问题的说法不一，个人觉得是版本的问题 。到这篇文章完成之前iOS 11.2  仍然不能越狱，第三方助手工具也没有找到此版本对应的漏洞，所以不支持导入修改过的ipa，心态继续崩。


IPAPatch导入（成功）


此方法涉及到了精彩的iOS逆向工程，感谢Naituw大神带我打开了新世界的大门。


IPAPatch是什么？


GitHub用户Naituw表示之前开源的关闭 Facebook for iOS 的 HTTPS 证书校验的方法操作太过繁琐，为了进一步简化调试、验证操作，研发了IPAPatch，它可以提供一个简单的方法来修补iOS应用程序，且不需要越狱。


IPAPatch 可以做什么呢？


和 “HackingFacebook” 类似，”IPAPatch” 主要可以在第三方的 IPA 文件上 “添加” 自己的代码，但过程有很大不同：


大神Github：https://github.com/Naituw/


开整


一 . *终效果展示


640?wx_fmt=jpeg


聊天界面


640?wx_fmt=png


发现界面


640?wx_fmt=png


我的界面


640?wx_fmt=png


朋友圈界面


二 . 需要准备的工具及设备


    

  • 清醒的头脑
    • 

  • 开发者账号（或证书）
    • 

  • Macbook
    • 

  • Xcode for mac
    • 

  • Reveal for mac
    • 

  • PlistEdit Pro for mac
    • 



三 . 具体实现步骤


1.下载开源项目IPAPatch，下载地址：百度网盘 密码: wu1m;


2.打开Reveal，依次点击菜单栏 Help → Show Reveal Library in Finder → iOS Library ，  在iOS Library里拿到集成文件RevealServer.framework，并将此集成文件移动到IPAPatch/Assets/Frameworks文件夹里；


640?wx_fmt=png


640?wx_fmt=png


3.准备一个解密过的 微信.ipa 文件。可以自行砸壳，因为身边没有越狱的手机，所以我是在PP助手下载的越狱版。放上已破壳6.6.6版本：百度网盘https://pan.baidu.com/share/init?surl=zP4MlvUfLkVXwgFGqcRZtA 密码: ipyj；


4.修改文件并保存;


5.将 微信.ipa 重命名为 app.ipa，替换文件夹IPAPatch/Assets里的模板文件app.ipa;


640?wx_fmt=png


6.打开IPAPatch.xcodeproj文件，点击左上角项目栏的三角形感叹号移动界面至Show the Issue navigator，再点击进入左侧 IPAPatch-DummyApp 标签，在右边的详细信息里配置Bundle Identifier和开发者证书。其中Display Name更改后会作为前缀添加到更改后的App上;


640?wx_fmt=png


7.连接iPhone，趁电脑不注意，迅速点击左上角的运行按钮，稍等片刻，将自动将此App安装到手机上;


上面的操作其实很简单，关键性的编译、执行以及注入步骤都已经由大神写进了patch.sh的脚本里，编译运行时，所有操作都是全自动完成的。


Build Succeed后，激起了我修改更多数据的兴趣，刚好又在网上找到了另一个大神制作的一大堆iOS主题包。


随便下载一个主题替换包，能替换的东西基本上已经全部包含在里面了。解压后将要替换的文件拖入之前的app.ipa里，等待文件替换完成。


再重复第七步即可。


简单介绍一下部分替换文件，有待继续挖掘


app.ipa/AppIcon**x**@*x.png：微信图标，目前更改后手机桌面仍然显示原图标，原因不详


app.ipa/Expression_**@2x.png ：老掉牙的表情


640?wx_fmt=jpeg


app.ipa/zh_CN.lproj/InfoPlist.strings ：包含微信的名称、以及发现页的几项文字（朋友圈、扫一扫）


640?wx_fmt=jpeg


app.ipa/zh_CN.lproj/mm.strings：大部分文字选项都在这个文件里，都可以修改，随便修改了两项


640?wx_fmt=jpeg


app.ipa/Assets.car：大多数图标文件集成在这个文件里


app.ipa/in.caf ：消息铃声


四．遇到的几项问题以及注意事项


1.个人描述证书只有七天的期限，七天后需要重新安装。


2.用自己证书安装的微信不支持Safiri浏览器上的网页分享，应该是未上架App store客户端的通病。


3.有时候不推送通知，或只通知一次，原因不详。


4.解压后的IPAPatch文件只能用Xcode运行一次，第二次运行会出现“apple match-o linker error”，此问题还没有找到解决办法，望各路大神指点一二。


5.*次进入微信或者结束进程后再打开微信会有hock成功的提示。此提示可以在IPAPatchEntry.mm文件里更改（alertControllerWithTitle；message；alertControlleraddAction；）。


640?wx_fmt=png


贴上代码


640?wx_fmt=png


hook成功的标签


总结


这篇文章只记录了如何修改App的外观，其他的例如防撤回、自动抢红包以及隐藏小红点等功能性模块涉及到了更多Objective-C方面的知识，本人刚接触OC，尚未弄懂其深邃的语法，在接下来的日子里我会继续向深层次探索。

	


	
	






	
	

		
319. 灯泡开关（JS实现）
	


	

		
319. 灯泡开关（JS实现）




1 题目


初始时有 n 个灯泡关闭。 第 1 轮，你打开所有的灯泡。 第 2 轮，每两个灯泡你关闭一次。 第 3 轮，每三个灯泡切换一次开关（如果关闭则开启，如果开启则关闭）。第 i 轮，每 i 个灯泡切换一次开关。 对于第 n 轮，你只切换*后一个灯泡的开关。 找出 n 轮后有多少个亮着的灯泡。


示例:


输入: 3


输出: 1


解释:


初始时, 灯泡状态 [关闭, 关闭, 关闭].


*轮后, 灯泡状态 [开启, 开启, 开启].


第二轮后, 灯泡状态 [开启, 关闭, 开启].


第三轮后, 灯泡状态 [开启, 关闭, 关闭].


你应该返回 1，因为只有一个灯泡还亮着。




链接：https://leetcode-cn.com/problems/bulb-switcher




2 思路


仔细观察，可以看出规律只有完全平方数索引处的灯泡还亮着，即1，4，9等。。。




3代码


/**


 * @param {number} n


 * @return {number}


 */


var bulbSwitch = function(n) {


    return Math.floor(Math.sqrt(n));


};



	


	
	






	
	

		
13. 超级丑数（JS实现）
	


	

		
13. 超级丑数（JS实现）






1 题目


编写一段程序来查找第 n 个超级丑数。


超级丑数是指其所有质因数都是长度为 k 的质数列表 primes 中的正整数。


示例:


输入: n = 12, primes = [2,7,13,19]


输出: 32


解释: 给定长度为 4 的质数列表 primes = [2,7,13,19]，前 12 个超级丑数序列为：[1,2,4,7,8,13,14,16,19,26,28,32] 。


说明:


1 是任何给定 primes 的超级丑数。


给定 primes 中的数字以升序排列。


0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000 。


第 n 个超级丑数确保在 32 位有符整数范围内。




链接：https://leetcode-cn.com/problems/super-ugly-number




2 思路


这道题和之前丑数二有点类型，区别在于这里的质数数组为输入参数，而不再是固定的了，但本质上不变，在原来的动态规划的基础上增加一个循环即可




3代码


/**


 * @param {number} n


 * @param {number[]} primes


 * @return {number}


 */


var nthSuperUglyNumber = function(n, primes) {


    const res = [1];


    let p = [];


    for (let i=0;i<primes.length;i++){   //初始化指针


        p.push(0);


    }


    let prev;


    let minIndex = 0;


    while(res.length < n) {


        let min = res[p[minIndex]] * primes[minIndex];  //初始化*小值


        for (let i=0;i<primes.length;i++){    //循环比较获取当前*小乘积


            let num = res[p[i]] * primes[i];


            min = Math.min(min, num);


            if (min === num) minIndex = i;


        }


        if (prev !== min) res.push(min);     //用于去重


        prev = min;


        p[minIndex]++;


    }




    return res[res.length – 1];


};



	


	
	






	
	

		
328. 奇偶链表（JS实现）
	


	

		
328. 奇偶链表（JS实现）




1 题目


给定一个单链表，把所有的奇数节点和偶数节点分别排在一起。请注意，这里的奇数节点和偶数节点指的是节点编号的奇偶性，而不是节点的值的奇偶性。


请尝试使用原地算法完成。你的算法的空间复杂度应为 O(1)，时间复杂度应为 O(nodes)，nodes 为节点总数。


示例 1:


输入: 1->2->3->4->5->NULL


输出: 1->3->5->2->4->NULL


示例 2:


输入: 2->1->3->5->6->4->7->NULL


输出: 2->3->6->7->1->5->4->NULL


说明:


应当保持奇数节点和偶数节点的相对顺序。


链表的*个节点视为奇数节点，第二个节点视为偶数节点，以此类推。




链接：https://leetcode-cn.com/problems/odd-even-linked-list




2 思路


这道题我的思路*遍遍历，我给每个节点添加一个_next指针，奇数节点指向下一个奇数节点，而偶数节点指向下一个偶数节点，第二次遍历将_next替换为原来的next指针




3代码


/**


 * Definition for singly-linked list.


 * function ListNode(val, next) {


 *     this.val = (val===undefined ? 0 : val)


 *     this.next = (next===undefined ? null : next)


 * }


 */


/**


 * @param {ListNode} head


 * @return {ListNode}


 */


var oddEvenList = function(head) {


    if (!head || !head.next) return head;


    let link = head;




    let headOdd = head;


    let headEven = secondNode = head.next;


    let lastOddNode;


    while(headOdd || headEven) {


        if (headOdd) {


            headOdd._next = (headOdd.next && headOdd.next.next) || null;


            if (!headOdd._next) {


                lastOddNode = headOdd;


            }


            headOdd = headOdd._next;


        }




        if (headEven) {


            headEven._next = (headEven.next && headEven.next.next) || null;


            headEven = headEven._next;


        }


    }




    while(head) {


        let nextNode = head.next;


        head.next = head._next;


        delete head._next;


        head = nextNode;


    }




    lastOddNode.next = secondNode;




    return link;


};



	


	
	






	
	

		
PHP的exec()函数无返回值排查方法
	


	

		
在安全imagemagic时 需要用到 exec很多服务器上安装失败


exec()执行外部命令失败，但没有任何错误信息。


exec执行某命令在命令行下没有问题，但是在php中就出错。这个问题99.99%与权限有关，但是exec执行的命令不会返回错误。一个技巧就是使用管道命令，假设你的exec调用如下：


exec('convert a.jpg b.jpg', $output, $return_val);


可以更改如下：




    

  1. 

    

    

    

    

    exec(‘convert a.jpg b.jpg 2>&1’, $output, $return_val);
    

    

    2. 

  2. 

    

    

    

    

    print_r($output);
    

    

    3. 





使用 2>&1 , 命令就会输出shell执行时的错误到$output变量, 输出该变量即可分析。


备注: exec有3个参数，*个是要执行的命令，第二个是参数是一个数组，数组的值是由*个命令执行后生成的，第三个参数执行的状态，0表示成功，其他都表示失败。


在php里面一共有三个函数可以用来执行外部命令system，exec，passthru。

	


	
	






	
	

		
php执行shell，返回空
	


	

		
问题：以下shell脚本在 www 用户下执行 sudo /usr/local/webserver/nginx/sbin/nginx -t 是有返回结果的，但用http://localhost/nginx.php?act=test 访问是看不到返回值,shell指令都没执行，safe-mode 是off的，不知为何，请教高人了？

nginx.php代码如下：

<?php

if(isset($_GET[‘act’])&&!empty($_GET[‘act’])){

if($_GET[‘act’]==’test’){

$message=shell_exec(“sudo /usr/local/webserver/nginx/sbin/nginx -t”);

echo “测试结果:”.$message;

}elseif($_GET[‘act’]==’restart’){

$message=shell_exec(“sudo /usr/local/webserver/nginx/sbin/nginx -s reload”)

;

echo “重启结果:”.$message;

}

}else{

header(“Status: 404 Not Found”);

}

?>


回复：我一开始也为这个问题迷惑不解，为何 php cgi以www用户执行sudo ls -al / 命令就可以正常输出，而执行


sudo /usr/local/webserver/nginx/sbin/nginx -t 却没有输出？


没有任何输出，导致我们无法跟踪错误的原因，那么，使用Linux标准输出重定向，看看有无输出，我的php代码是（设置/wwwroot/log.txt权限为777）：

/wwwroot/index.php

<?php

$s = shell_exec(“/usr/bin/sudo /home/nginx/sbin/nginx -t >/wwwroot/log.txt”);

echo $s;


请求http://localhost/index.php, 发现log.txt文件是空白的，即没有正常输出，那说明有可能发生了错误，为此，我再尝试使用Linux的标准错误输出重定向：

$s = shell_exec(“/usr/bin/sudo /home/nginx/sbin/nginx -t 2>/wwwroot/log.txt”);


注意重定向符号前的2


再请求index.php 这时，在log.txt中记录了详细的错误：

sudo: sorry, you must have a tty to run sudo


这个错误我没见过，大致意思说，当执行sudo时，必须要从终端登录（可能nginx本身的一些限制）


google搜索这个错误提示,　解决办法也很简单：

注释掉 /etc/sudoers中 ‘Defaults requiretty’ 这个就行，即前面加#


按这个办法处理，浏览器仍然没有任何输出，我的猜测：可能是nginx启动程序输出目标是终端，那么折衷的办法就是使用输出重定向了，所以，改造的代码如下：

index.php

<?php

$trace=”/wwwroot/log.txt”;


if(!is_writable($trace) || !is_readable($trace)) {

exit(“$trace must readable and writable”);

}


file_put_contents($trace,”);


echo `/usr/bin/sudo /home/nginx/sbin/nginx -t >$trace 2>&1`;


echo `top -b -n 1`;

echo file_get_contents($trace);


这是通过简接方式来观察输出的，类似这个现象的，还有使用top命令查看系统负载，top命令需要在终端窗口中执行，使用php执行shell_exec(“top -n 1”)，给出的错误就是TERM environment variable not set. 解决办法就是使用-b参数执行top, 即shell_exec(“top -b -n 1”)


如果你有更好的方法，欢迎一起探讨，如果实验成功，也就可以通过web页面控制nginx了。

	


	
	






	
	

		
324. 摆动排序 II（JS实现）
	


	

		
324. 摆动排序 II（JS实现）




1 题目


给定一个无序的数组 nums，将它重新排列成 nums[0] < nums[1] > nums[2] < nums[3]… 的顺序。


示例 1:


输入: nums = [1, 5, 1, 1, 6, 4]


输出: 一个可能的答案是 [1, 4, 1, 5, 1, 6]


示例 2:


输入: nums = [1, 3, 2, 2, 3, 1]


输出: 一个可能的答案是 [2, 3, 1, 3, 1, 2]


说明:


你可以假设所有输入都会得到有效的结果。


进阶:


你能用 O(n) 时间复杂度和 / 或原地 O(1) 额外空间来实现吗？




链接：https://leetcode-cn.com/problems/wiggle-sort-ii




2 思路


很明显，我做这道题就是先把数组排序，然后将数组分为两部分，依次构造新数组的，题解中有O（n）的算法，其先用快速选择法，找到数组的中位数，然后将小于等于中位数的数放置在左侧，大于中位数的放置在右侧，这样就成了两部分了




3代码


/**


 * @param {number[]} nums


 * @return {void} Do not return anything, modify nums in-place instead.


 */


var wiggleSort = function(nums) {


  nums.sort((a,b) => a-b);




  let mid = nums.length % 2 === 0 ? Math.floor(nums.length / 2) : Math.floor(nums.length / 2) + 1;




  const res = [];




  let low = mid – 1;


  let high = nums.length – 1;


  while (low >= 0 && high >= mid) {


    res.push(nums[low–]);


    res.push(nums[high–]);


  }




  if (low >= 0) res.push(nums[low–]);   //从后向前进行插入


  if (high >= mid) res.push(nums[high–]);  //从后向前进行插入




  for (let i=0; i<res.length;i++) {


    nums[i] = res[i];


  }


};



	


	
	






	
	

		
322. 零钱兑换（JS实现）
	


	

		
322. 零钱兑换（JS实现）






1 题目


给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的*少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回 -1。


示例 1:


输入: coins = [1, 2, 5], amount = 11


输出: 3


解释: 11 = 5 + 5 + 1


示例 2:


输入: coins = [2], amount = 3


输出: -1




链接：https://leetcode-cn.com/problems/coin-change




2 思路


这道题考察贪心+回溯算法，我们先把硬币排序，然后构造一棵树，先从大面值的硬币开始，逐级相减，直到总金额为0，即找到了目标的*优组合，题解中还可以用动态规划的方法来做




3代码


/**


 * @param {number[]} coins


 * @param {number} amount


 * @return {number}


 */


var coinChange = function(coins, amount) {


  coins.sort((a,b) => a-b);




  if (amount === 0) return 0;


  if (amount < coins[0]) return -1;




  let ans = 999999;


  d(amount, coins.length – 1, 0, coins);






  function d(num, index, len, coins) {


    if (num === 0) {


      ans = Math.min(ans, len);


      return;


    };


    if (index < 0) return;




    for (let k=Math.floor(num / coins[index]); k >=0 && k + len < ans; k–) {


        d(num – coins[index] * k, index – 1, len + k, coins);


    }


  }




  return ans === 999999 ? -1 : ans;


};