算法题

1.有一组“+”和“-”符号，要求将“+”排到左边，“-”排到右边，写出具体的实现方法。

from collections import dequefrom timeit import Timers = "++++++----+++----"# 方法一def func1():    new_s = s.replace("+", "0").replace("-", "1")    result = "".join(sorted(new_s)).replace("0", "+").replace("1", "-")    return result# 方法二def func2():    q = deque()    left = q.appendleft    right = q.append    for i in s:        if i == "+":            left("+")        elif i == "-":            right("-")# 方法三def func3():    data = list(s)    start_index = 0    end_index = 0    count = len(s)    while start_index + end_index < count:        if data[start_index] == '-':            data[start_index], data[count - end_index - 1] = data[count - end_index - 1], data[start_index]            end_index += 1        else :            start_index += 1    return "".join(data)if __name__ == '__main__':    timer1 = Timer("func1()", "from __main__ import func1")    print("func1", timer1.timeit(1000000))    timer2 = Timer("func2()", "from __main__ import func2")    print("func2", timer2.timeit(1000000))    timer3 = Timer("func3()", "from __main__ import func3")    print("func3", timer3.timeit(1000000))# 1000000 测试结果# func1 1.39003764# func2 1.593012875# func3 3.3487415590000005# func1 的方式最优，其次是 func2

2.给定一个字符串，请你找出其中不含有重复字符的最长子串的长度
题目：
示例 1:

输入: “abcabcbb”
输出: 3
解释: 因为无重复字符的最长子串是 “abc”，所以其长度为 3。
示例 2:

输入: “bbbbb”
输出: 1
解释: 因为无重复字符的最长子串是 “b”，所以其长度为 1。
示例 3:

输入: “pwwkew”
输出: 3
解释: 因为无重复字符的最长子串是 “wke”，所以其长度为 3。
请注意，你的答案必须是子串的长度，“pwke” 是一个子序列，不是子串。

public class LeetCode3 {       public static void main(String[] args) {        /**         * LeetCode第3题：         * 给定一个字符串，找出不含有重复字符的最长子串的长度。         * 示例：给定 "abcabcbb" ，没有重复字符的最长子串是 "abc" ，那么长度就是3。         * 解题思路：建立指针i,j,i=0,j=i+1;最大字符长度为max         * if str[i-(j-1)]的区间中存在 = str[j] ， i++;j=i+1;break;         * else j++;         * 运行时间 n的2次方         */           String s = "pwwkew";           System.out.println(lengthOfLongestSubstring(s));    }       public static int lengthOfLongestSubstring(String s) {           if(s.length() == 1) return 1;           if(s.length() == 0) return 0;           char str[] = s.toCharArray();            int i = 0,j = i+1,max = 0;           boolean  t = true;           while(i < s.length() - 1){                   int length = 1;                   //检测是否重复                   if(j == s.length()) break;                   for(int k = i; k < j;k++){                       if(str[j] != str[k] ){                           length++;                           }else{                               t = false;                                break;                           }                   }                   if(length > max){                       max = length;                    }                   //如果检测成功，j指针右移一次                   if(t) j++;                   //检测失败，i指针右移一次，j指针回到i+1的位置                   else{                       t = true; i++; j = i + 1; length = 1;                   }           }           return max;       }}

©著作权归作者所有：来自51CTO博客作者cuijm51的原创作品，如需转载，请注明出处，否则将追究法律责任

每一份赞赏源于懂得

赞赏

0人进行了赞赏支持

每一份赞赏源于懂得

更多相关文章

随机推荐