时光博客

Leetcode

Single Number II

题目如下
Given an array of integers, every element appears three times except for one. Find that single one. Note: Your algorithm should have a linear runtime complexity. Could you implement it without using extra memory?

问题:给一个数组,里面只有一个数字一次,其它数字都出现3次,找出这个出现一次的数字,要求时间复杂度为O(n),空间复杂度为O(1)。

解题思路:

这里我们需要用到的知识为二进制、位计算。这里需要思考数字在计算机是怎么存储的。考虑全部用二进制表示,如果我们把第i个位置上所有数字的和对3取余,那么只会有两个结果 0 或 1 (根据题意,3个0或3个1相加余数都为0).

AC代码如下:

#include <stdio.h>
int singleNumber(int A[], int n) {
    int count[32] = {0};
    int result = 0;
    for (int i = 0; i < 32; i++) {
        for (int j = 0; j < n; j++) {
            //判断A[J]的第i位的奇偶,奇数才加,偶数为0不加
            if ((A[j] >> i) & 1) {
                count[i]++;
            }
        }
        // 计算第i位的和,然后计算其对应的10进制,再通过与运算求和(其实加法求和也可以)
        result |= ((count[i] % 3) << i);
    }
    return result;
}

我们可以用一组CASE来测试一下 {12, 1, 12, 3, 12, 1, 1,15, 3, 3}

最后依次统计各位上的和如下

qq20150515-1@2x.png - 大小: 12 KB - 尺寸: 168 x 423 - 点击打开新窗口浏览全图

依次为 4447,高位为0直接省略。最后求余之后为 为 1111,转换为2进制则为 8+4+2+1 = 15

算法中值得注意的是:

通过位运算 (A[j] >> i) & 1 来判断奇偶

因为此题又看了一下位运算,感觉CS的世界博大精深

Longest Substring Without Repeating Characters

题目如下:

Given a string, find the length of the longest substring without repeating characters. For example, the longest substring without repeating letters for "abcabcbb" is "abc", which the length is 3. For "bbbbb" the longest substring is "b", with the length of 1.

这基本就是水题,求最长不重复子串长度。关键在于考察处理边界情况的能力,主要是碰到相同字母,起始位置重新计算这个细节需要注意

代码如下:

/**
 * @param {string} s
 * @return {number}
 */
var lengthOfLongestSubstring = function(s) {
    if(!s) return 0;
    var n = 0;
    var l = s.length;
    var _s = "";
    var _t = 0;
    for (var i = 0;i < l;i++) {
        var flag = _s.indexOf(s[i]);
        if(flag != -1){
            _s = _s.substr(++flag, _s.length) + s[i];
            _t = _s.length;
        } else {
            _s += s[i];
            _t++;
        }
        n = _t > n ? _t : n;
    }
    return n;
};

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;
};

©2008-2017 - 时光博客 Ucloud

京ICP备15052479号返回顶部