算法(1)

求字符串中第一个没有重复的字符

###题目描述

Given a string s, find and return the first instance of a non-repeating character in it. If there is no such character, return '_'.

Example

  • For s = "abacabad", the output should be
    firstNotRepeatingCharacter(s) = 'c'.

    There are 2 non-repeating characters in the string: 'c' and 'd'. Return c since it appears in the string first.

  • For s = "abacabaabacaba", the output should be
    firstNotRepeatingCharacter(s) = '_'.

    There are no characters in this string that do not repeat.

Input/Output

  • [execution time limit] 4 seconds (js)

  • [input] string s

    A string that contains only lowercase English letters.

    Guaranteed constraints:
    1 ≤ s.length ≤ 105.

  • [output] char

    The first non-repeating character in s, or '_' if there are no characters that do not repeat.

###解法

  • 暴力解法:

两层循环,很低效

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
function firstNotRepeatingCharacter1(s) {
    for (var i = 0 ; i < s.length ; i++){
        var flag = false
        for (var j = 0 ; j < s.length ; j++){
            if (i == j){
                continue
            }
            if (s.charAt(i) == s.charAt(j)){
                flag = true
                break
            }
        }
        if (!flag){
            return s.charAt(i)
        }
    }
    return '_'
}

因为字母的数目是确定的,其实还可以借助哈希表来做

  • 简单解法:
1
2
3
4
5
6
7
8
9
//只需要一层循环
function firstNotRepeatingCharacter(s) {
    for (var i = 0 ; i < s.length ; i++){
        if (s.lastIndexOf(s.charAt(i)) == s.indexOf(s.charAt(i))){
            return s.charAt(i)
        }
    }
    return '_'
}

难点在于lastIndexOf和indexOf两个 API不知道,一个是求出最后一次出现的索引值, 一个是首次出现的 index, 两个 索引值相同表明该元素只出现了一次

##将数组顺时针旋转90度

题目描述

You are given an n x n 2D matrix that represents an image. Rotate the image by 90 degrees (clockwise).

Example

For

1
2
3
a = [[1, 2, 3],
     [4, 5, 6],
     [7, 8, 9]]

the output should be

1
2
3
4
rotateImage(a) =
    [[7, 4, 1],
     [8, 5, 2],
     [9, 6, 3]]

Input/Output

  • [execution time limit] 4 seconds (js)

  • [input] array.array.integer a

    Guaranteed constraints:
    1 ≤ a.length ≤ 100,
    a[i].length = a.length,
    1 ≤ a[i][j] ≤ 104.

  • [output] array.array.integer

    解法

1
2
3
4
5
6
7
8
9
10
11
12
function rotateImage(a) {
    var n = a.length
    var target = []
    for (var i = 0 ; i< n;i++){
        var row = []
        for (var j = 0 ; j< n;j++){
            row[j] = a[n-1-j][i]
        }
        target.push(row)
    }
    return target
}

仔细观察row[j] = a[n-1-j][i],其实可以看成row[i][j] = a[n-1-j][i],

所以:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
//评分最高的方法
function rotateImage(a) {
    // Transpose
    for(var i = 0;i<a.length;i++){
        for(var j = 0;j<i;j++){
            // Switch a[i][j] and a[j][i]
            // With XOR swap
            a[i][j] ^= a[j][i]
            a[j][i] ^= a[i][j]
            a[i][j] ^= a[j][i]
        }
    }

    // Reverse columns
    for(var i in a){
        a[i] = a[i].reverse()
    }

    return a
}

值得注意的是:

1
2
3
a[i][j] ^= a[j][i]
a[j][i] ^= a[i][j] 
a[i][j] ^= a[j][i]

不使用中间值,交换两个数的值

所有不使用临时变量的思路都是让其中一个变量变成一个a和b都有关系的值这样可以先改变另一个变量值，最后改变原修改的变量值