时光博客

Two Sum

题目如下:

Given an array of integers, find two numbers such that they add up to a specific target number.
The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2. Please note that your returned answers (both index1 and index2) are not zero-based.
You may assume that each input would have exactly one solution.

Input: numbers={2, 7, 11, 15}, target=9
Output: index1=1, index2=2

用C写一直没过,而且发现网上好像也很少能看到有C版的,过了几天发现支持了JS Lang于是,用JS实现了一版 160ms,这题可以用暴力,但是会超时。如果是C++可以用Hashmap,当然JS没有这些黑魔法,只能用普通的数据结构,以下是我的解题思路。

解题思路:

  1. 创建一个输入数组的反转数组,就是value => key,方便后面根据value来获取key,也就是元素索引
  2. 排序原数组,从小到大,排序可以用二分排
  3. 创建2个指针一个在数组头部,一个在尾部,如果和小于要求输入的值则头部指针向后偏移,否则尾部指针向前移,直到和等于输入值停止
  4. 在第一步创建的数组中,找到对应的元素索引,返回并++

代码如下:

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]} two integers in an array, ie: [index1, index2]
 */
var twoSum = function(numbers, target) {
	function compareNumbers(a, b) {
	  return a - b;
	}
	var len = numbers.length;
	var unsortNumbers = [];
	for (var i = 0; i < len; i++) {
		unsortNumbers[i] = numbers[i];
	};
	numbers.sort(compareNumbers);
	var sp = 0;
	var ep = len-1;
	do {
		if(((numbers[sp]+numbers[ep]) > target) && ep > sp) ep--;
		if((numbers[sp]+numbers[ep]) < target && ep > sp) sp++;
	} while ((numbers[sp]+numbers[ep])!= target)

	var output = [];
	for (var i = 0; i < len; i++) {
		if(unsortNumbers[i] == numbers[sp]){
			for (var j = len - 1; j >= 0; j--) 
			{
				if(unsortNumbers[j] == numbers[ep]){
					output = (i > j) ? [++j, ++i] : [++i, ++j];
					break;
				}
			};
			break;
		}
	};
	return output;
};

妙用PHP数组函数实现笛卡尔积

之前我写过一篇关于笛卡尔积的2个版本的PHP实现,在网上看到一篇结合PHP数组函数和递归实现的版本。代码如下:

<?php

$arr = array(
    array(1),
    array(2,3),
    array(4,5,6)
);

fun($arr);
print_r($res);

function fun($arr, $tmp = array())
{
    foreach(array_shift($arr) as $v)
    {
        $tmp[]  = $v;
        if($arr)
        {
            fun($arr, $tmp);
        }
        else
        {
            $GLOBALS["res"][]   = implode("", $tmp);
        }
        array_pop($tmp);
    }
}

?>

下图是我对该版本算法运行的简易流程图:

flow.png - 大小: 10.42 KB - 尺寸:  x  - 点击打开新窗口浏览全图

说妙用是因为,利用array_shift实现数组的剔除,来实现遍历,另一个妙用array_pop实现数组的弹出,避免在递归中出现的重复值。

笛卡尔积算法,二维数组矩阵算法

给定一个数组: 

$list ['a'] = array (1,2,3); 
$list ['b'] = array (1,2); 
$list ['c'] = array (1,2,3,4);
...

要求输出这样:111,112,113,114,121,122,123.....

以上结果其实就是笛卡尔积下面为我实现的2个版本

继续阅读

in_array数组的优化思考

问题

有个朋友跟我说去面试的时候碰到面试官被问倒。
问:怎样判断一个字符串在一个数组中?
答:in_array函数
问:是否有优化的空间呢?
答:...这还需要优化吗?


分析

先来看看in_array的官方解释

in_array — 检查数组中是否存在某个值
bool in_array  ( mixed  $needle  , array $haystack  [, bool $strict  = FALSE ] )
在 haystack 中搜索 needle,如果没有设置 strict 则使用宽松的比较

继续阅读

C#程序利用ILMerge打包EXE

做 xy2TK 软件打包的时候,有一个需求,就是最终生产1个exe程序,方便使用者携带、拷贝。因为使用了JSON扩展,必须引入Newtonsoft.Json.dll,主程序+扩展至少2个文件。Google了一下,有两种方法:

1、将DLL设置为资源在主程序初始化的时候,将资源动态载入

2、用微软的ILMerge程序打包

我们来看看微软的官方介绍:

ILMerge is a utility for merging multiple .NET assemblies into a single .NET assembly. It works on executables and DLLs alike and comes with several options for controlling the processing and format of the output. See the accompanying documentation for details

大小之后726KB,下载ILMerge之后,安装,我是64位WIN7,默认安装位 C:\Program Files (x86)\Microsoft\ILMerge

继续阅读

大话西游2专业调抗工具

利用空余时间,给大话西游2游戏队伍里面的队友做的一个小工具,由于游戏特别复杂,队友又都是壕,无法专注游戏,Excel不方便维护,所以用C#写了此软件,第一次用C#,全靠Google = =~,在授权的时候碰到一些坑,对于想获取唯一ID的话,建议还是用主板ID,不要使用硬盘SN,各种坑~下面来看看截图吧:


继续阅读
较新的文章 »« 较旧的文章

©2008-2017 - 时光博客 Ucloud

京ICP备15052479号返回顶部