leetcode 第3题 Longest Substring Without Repeating Characters

题目地址

https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

题目描述

/*
 * @lc app=leetcode id=3 lang=c
 *
 * [3] Longest Substring Without Repeating Characters
 *
 * https://leetcode.com/problems/longest-substring-without-repeating-characters/description/
 *
 * algorithms
 * Medium (28.40%)
 * Total Accepted:    938K
 * Total Submissions: 3.3M
 * Testcase Example:  '"abcabcbb"'
 *
 * Given a string, find the length of the longest substring without repeating
 * characters.
 *
 *
 * Example 1:
 *
 *
 * Input: "abcabcbb"
 * Output: 3
 * Explanation: The answer is "abc", with the length of 3.
 *
 *
 *
 * Example 2:
 *
 *
 * Input: "bbbbb"
 * Output: 1
 * Explanation: The answer is "b", with the length of 1.
 *
 *
 *
 * Example 3:
 *
 *
 * Input: "pwwkew"
 * Output: 3
 * Explanation: The answer is "wke", with the length of 3.
 * ⁠            Note that the answer must be a substring, "pwke" is a
 * subsequence and not a substring.
 *
 *
 *
 *
 *
 */

思路

这道题求字符串中最长不重复的子串的长度.因为可打印的ASCII一共有128个,所以字符串的出现的可能性一共有128个.
声明一个大小为128的数组,并全部初始化为-1.然后遍历数组中的每一个元素,遍历的时候记录每个元素出现的位置,
元素的出现位置要么为-1,即还没有出现过,此时记录出现的位置并计算相应的最长不重复的子串的长度;要么为相应
的循环次数,即上次出现的位置,此时应该重置start为上次相应元素出现位置的下一个位置,同时记录相应元素出现的位置.

代码实现

#include <stdio.h>
#include <string.h>
#include <stdlib.h>

int lengthOfLongestSubstring(char * s){
    int i, start = 0, maxLen = 0;
    int strLen = strlen(s);
    int lastAppear[128];
    memset(lastAppear,0xFF,sizeof(lastAppear));
    for(i = 0; i < strLen; i++){
        if(start > lastAppear[s[i]]){
            lastAppear[s[i]] = i;
            maxLen = (maxLen > i - start + 1) ? maxLen : i - start + 1;
        }
        else{
            start = lastAppear[s[i]] + 1;
            lastAppear[s[i]] = i;
        }
    }
    return maxLen;
}

int main(int argc, char **argv)
{
    if (argc != 2) {
        fprintf(stderr, "Usage: ./test string     (for example: ./test abcabcbb)\n");
        exit(-1);
    }

    printf("%d\n", lengthOfLongestSubstring(argv[1]));
    return 0;
}

编译并运行:

haha@hello:~$ gcc -g -o test longest-substring-without-repeating-characters.c
haha@hello:~$ ./test abcabcbb
3
haha@hello:~$ ./test azxcyxdba
6
haha@hello:~$