leetcode题解日练--2016.9.14

本文主要是介绍leetcode题解日练--2016.9.14，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

平常心

今日题目：

1、最长包含K次重复子串

2、实现平方根sqrt(x)

今日摘录：

说那个话的时候是在那样的一种心醉的情形下，简直什么都可以相信，自己当然绝对相信那不是谎话。
——《半生缘》

395. Longest Substring with At Least K Repeating Characters | Difficulty: Medium

Find the length of the longest substring T of a given string (consists of lowercase letters only) such that every character in T appears no less than k times.

Example 1:

Input:
s = “aaabb”, k = 3

Output:
3

The longest substring is “aaa”, as ‘a’ is repeated 3 times.
Example 2:

Input:
s = “ababbc”, k = 2

Output:
5

The longest substring is “ababb”, as ‘a’ is repeated 2 times and ‘b’ is repeated 3 times.

tag：
题意：找到最长子串，需要满足这个子串中每个字符出现次数均要大于K次。

思路：
1、如何找到这样的子串，找到一头一尾(first、last)，并且中间的都满足出现次数大于等于K。每找到一个这样的last就更新一次，这样从一个first找到最后之后，每次查找之后将first移动到最后一个找到符合的last字符的后面一位。

class Solution {
public:int longestSubstring(string s, int k) {int max_len = 0;int first,last;int n = s.size();for(first = 0;first+k<=n;){int max_last=first;int mask = 0;int count[26] = {0};for(last = first;last<n;last++){int i = s[last]-'a';count[i]++;if(count[i]<k)  mask |=(1<<i);else    mask&=(~(1<<i));if(mask==0) {max_len = max(max_len,last-first+1);max_last = last;}}if(max_len>=n-first) break;first = max_last+1;}
        return max_len;}
};

结果：3ms

2、递归写法，每次从当前区间[first,last]中去查找区间，先遍历一次做一次统计，然后统计完之后去找一个在[first,last]中出现大于等于K次的字符组成的区间，再递归去判断这个更小的区间。递归终止条件是更小的区间就是原区间，返回区间长度。

class Solution {
public:int helper(const string& s,int k,int first,int last){if(first>last)  return 0;int cnt[26] = {0};for(int i=first;i<last;i++){cnt[s[i]-'a']++;}int max_len=0;int l=0,r=0;for(l = first;l<last;){while(l<last && cnt[s[l]-'a'] <k) l++;if(l==last) break;r = l;while(r<last && cnt[s[r]-'a']>=k) r++;if(l==first && r==last) return r-l;max_len = max(max_len,helper(s,k,l,r));l = r;}return max_len;}int longestSubstring(string s, int k) {int n = s.size();if(n==0)    return 0;return helper(s,k,0,n);}
};

结果：3ms

69. Sqrt(x) | Difficulty: Medium

Implement int sqrt(int x).

Compute and return the square root of x.

tag：数学|二分

题意：实现平方根函数
思路：
1、用牛顿法去做，
x_{{n+1}}=x_{n}-{\frac {f(x_{n})}{f’(x_{n})}}

class Solution {
public:int mySqrt(int x) {long long  r = x;while(r*r>x){r = (r+x/r)/2;}return r;}
};

结果：6ms

2、二分查找
相当于找第一个<=sqrt(x)的整数，这种情况下要使用偏右的二分查找方法

class Solution {
public:int mySqrt(int x) {if(x==0)    return 0;int l = 1,r = x;while(l<r){int mid = l+(r-l+1)/2;if(mid>x/mid)   r = mid-1;else if(mid<x/mid) l=mid;else    return mid;}return l;}
};

结果：6ms

这篇关于leetcode题解日练--2016.9.14的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---