[CI] Bulb Switcher

 

There are n bulbs that are initially off. You first turn on all the bulbs. Then, you turn off every second bulb. On the third round, you toggle every third bulb (turning on if it’s off or turning off if it’s on). For the nth round, you only toggle the last bulb. Find how many bulbs are on after n rounds.

It’s quite a interesting problem and more like a math problem than a coding one. The direct solution is do the swith round by round and we can get the result at the final round. The time complexity of the direct solution is O(n2). The example code is as follows,

public int bulbSwitch(int n) {
		int[] lights = new int[n];
		int cnt = 0;
		int i = 0;
		// initailize the array
		for (i = 0; i < n; i++) {
			lights[i] = 0;
		}
		// do the round toggle
		for (i = 0; i < n; i++) {
			for (int j = i; j < n; j += i + 1) {
				lights[j] = lights[j] == 0 ? 1 : 0;
			}
		}
		// get the result
		for (i = 0; i < n; i++) {
			cnt += lights[i];
		}
		return cnt;
}

Seems like a perfect answer which definitely is not. When I submitted the above code on LeetCode OJ, the platform threw out an error of RUNNING TIME OUT. So it’s time to get the code optimized.
As you can see, each one of the bulb is turned on or off for n times which is the number of divisors. But still this cannot solve our problem for the time complexity is O(n2) too! What about printing the result to see whether there is a pattern? Let do it.
when n=40, the result is 1001000010000001000000001000000000010000 . And when n=60, the result is 100100001000000100000000100000000001000000000000100000000000 .
What do you see, guys? Yes, the mumber of each group which has only one 1 is an Arithmetic sequence. So we can get the final result without any toggling rounds. A half but passed solution is as follows,

public int bulbSwitch(int n) {
		int cnt = 0;
		for (int i = 3; n > 0; i += 2) {
			n -= i;
			cnt++;
		}
		return cnt;
}

That’s it.
The time complexity of the above code is O(n) and the code can pass the OJ’s test. But is this the most optimized one? No, of course. If you know more maths, the above code can be optimized to the time complexity of O(1) which means there is some formula to get the final result. Can you figure it out, buddy?
By the way, the Ultimate answer is  SQRT(n).
source page: https://leetcode.com/problems/bulb-switcher/

面试程序题-二分查找(1)

一个数组,大小先减后增,请找到增减部分的分界点,要求算法时间复杂度O(logN)。
下面给出了一个递归实现的版本。
这个问题还可以让查找其中的某个元素,也是二分,思路一样。

#include <iostream>
#define MAX 13
using namespace std;
void findBreakpoint(int* a, int starti, int endi){
int i = (endi-starti)/2+starti;
if(starti==i){
cout<<i<<endl;
return;
}
if(a[i]<a[i+1]){
findBreakpoint(a, starti, i);
}else{
findBreakpoint(a, i+1, endi);
}
}
int main(){
int a[MAX] = {12, 11, 10, 8, 5, 6, 7, 9, 11, 12, 13, 20, 50};
findBreakpoint(a, 0, MAX-1);
return 0;
}

关于Java类的hashCode和equals方法

前面两篇文章中提到了利用哈希表的数据结构,如HashMap,HashSet等,这些数据结构利用对象的hashCode和equals函数来识别对象是否相同,原则如下:
* hashCode不同的对象一定不同
* hashCode相同的对象不一定相同
比方说HashMap,查找元素时,会先以key的hashCode来查找,如果找到对象,然后再以equals方法来判定是否相等,如果相等,才返回相应的value。
自定义数据结构做key时,需要成对的实现两个函数才可以正确的使用利用哈希表实现的数据结构。

Java中HashSet, TreeSet, LinkedHashSet区别

三个结构都实现了Set接口,不允许含有重复元素。
* HashSet是用哈希表实现的,增删查的复杂度都是O(1),不能保证元素的顺序
* TreeSet是用一个树形结构实现(红黑树),增删查的复杂度为O(log(n)),维护一个排序的Set,可以用 first(), last(), headSet(), tailSet()等获取最大最小的元素。
* LinkedHashSet是用链表+哈希表实现,因为是Linked,所以可以保持插入的顺序,增删查复杂度都是O(1)

Java中ArrayList,Vector,LinkedList区别

三种结构都实现了Collection接口和List接口。而LinkedList还实现了Queue接口。
内部实现区别:
* ArrayList可以理解为一个可变长度数组,特点是内存连续,随机访问快,插入、删除慢,扩展容量时,每次增加原容量的50%;
* Vector可以理解为线程安全的ArrayList,扩展容量时,每次容量翻倍;
* LinkedList实现上为一个双向链表,随机访问慢,插入、删除快。
refrence: http://www.programcreek.com/2013/03/arraylist-vs-linkedlist-vs-vector/

内存数据更新策略总结

因为后台线程更新数据,而前台继续服务,所以涉及数据共享的问题。

解决方案大致有以下几种:

  1. 使用读写锁
  2. 开辟两份内存,reload时来回切换
  3. 在reload的时候开辟一块内存,切换之后,等待一段时间,前台线程全部切换为新内存后,把老内存释放

方法1效率相对低下,不考虑。

方法2完全可以满足需求,并且不用担心前台线程引用到不可用的数据,如果是配置文件之类,完全没有问题,但是如果占用内存比较可观时,成本较高,可行性不高。

方法3效率高且不需要长期占用双份内存,是较好的方法,但是在实践中,还是需要注意一些问题:

  • 读取数据的线程,需要将一个临时指针指向使用的数据(不要使用成员指针),防止在查询过程中(可能有遍历等比较费时的操作)内存被更新的问题,可能导致程序core掉。
  • sleep的时间尽可能长些,以等待后台线程更新内存(要考虑到如果更新线程每次是新起的话,更新间隔不能太小,如果是单一线程,就不用考虑这问题)

Bash速成

条件语句(注意:条件里两边的空格,引号,等号)

if [ “$var” = “abc” ]; then

elif [ “$var” = “ac” ]; then

else

fi

for循环

for var in $(ls *.sh); do
echo $var
done

while循环

var=1
while [ “$var” -le 20 ] ; do
var=$(($var+1))
done

until循环(跟while循环相反的)

until condition
do

done

case条件(可用正则,;;相当于break)

case “$var” in
yes | YES | y )
echo “YES”
echo “haha”
;;
[Nn]* ) echo “NO”;;
* ) echo “OTHER”;;
esac

定义/赋值变量

var=xxx  (等号两边不能有空格)

变量读取

echo $var

读取用户输入

read var

不输出换行

echo -n

执行命令并捕获返回值

$(command)

其它

shell里默认类型是字符串型

php json_encode utf-8中文问题

utf-8字符json_encode为变成转成utf16编码,也就是介个样子:

$ ./php/bin/php -r 'echo json_encode("中文");'
"u4e2du6587"

可读性降低,最新的php 5.4的json_encode支持了UTF-8编码,可以把中文不编码直接输出。
那低版本怎么办呢?也有办法,封装成一个函数给大家分享一下:

function my_json_encode($var) {
    return preg_replace("/\u([a-f0-9]{4})/e",
      "iconv('UCS-4LE','UTF-8',pack('V', hexdec('U$1')))", json_encode($var));
}

JAVA volatile关键字特性备忘

  1. 对volatile变量的读写有一个全局的排序,但是volatile变量跟常规变量的读写顺序没并没有保证
  2. volatile的值不会被缓存,所有线程读取到的都是当前的(主存中的)值
  3. 对volatile的变量的读写好像是用了synchronized包围起来一样

PHP中的拷贝

对象用等号赋值,只是引用,是浅拷贝,除非使用clone关键字。
而基本类型,int、float、string、array几种类型都是复制也是引用,不过有copy-on-write机制控制,感觉好像是直接复制,但是效率却高一些。基本类型如果想传引用,需要加一个&.
下面代码可以说明: Continue reading “PHP中的拷贝”