给定一个字符串str,和一个字母ch,请实现相应的代码求出一个数组,使数组中每个数字表示该位置与字母ch之间的最短距离。
比如str=”lexinfintech” ch=”i”
则输出为:[3,2,1,0,1,1,0,1,2,3,4,5]
第一行为字符串
第二行为字母
一个数字数组
lexinfintech i
[3,2,1,0,1,1,0,1,2,3,4,5]
假定所有输入的字符ch都在字符串str中,且str中的所有字母为小写,str长度不超过10000
s = input() ch = input() l = len(s) re = [] for i in range(l): if s[i] == ch: re.append(i) relist = [] if re is None: print([l for i in range(l)]) else: for i in range(l): minVal = l for j in re: if abs(i - j) < minVal: minVal = abs(i - j) relist.append(minVal) print(str(relist).replace(' ',''),end='')
import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String str = scanner.nextLine(); String c = scanner.nextLine(); int[] res = process(str, c.charAt(0)); int i = 0; System.out.print("["); for (i = 0; i < res.length - 1; i++){ System.out.print(res[i] + ","); } System.out.print(res[i] + "]"); } public static int[] process(String S, char C) { if (null == S || 0 == S.length()) { return null; } int N = S.length(); int[] ans = new int[N]; int prev = Integer.MIN_VALUE / 2; for (int i = 0; i < N; ++i) { if (S.charAt(i) == C) prev = i; ans[i] = i - prev; } prev = Integer.MAX_VALUE / 2; for (int i = N-1; i >= 0; --i) { if (S.charAt(i) == C) prev = i; ans[i] = Math.min(ans[i], prev - i); } return ans; } }
import java.util.Stack; import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner scanner = new Scanner(System.in); String str = scanner.nextLine(); String c = scanner.nextLine(); int[] res = process(str, c.charAt(0)); int i = 0; System.out.print("["); for (i = 0; i < res.length - 1; i++){ System.out.print(res[i] + ","); } System.out.print(res[i] + "]"); } public static int[] process(String str, char c) { if (null == str || 0 == str.length()) { return null; } int n = str.length(); int[] res = new int[n]; Pair[] pairs = new Pair[n]; Stack<Pair> stack = new Stack<>(); for (int i = 0; i < n; i++) { char temp = str.charAt(i); pairs[i] = new Pair(temp); if (temp != c) { if (!stack.isEmpty()) { if (stack.peek().word == c) { pairs[i].distance = 1; } else { pairs[i].distance = stack.peek().distance > 0 ? stack.peek().distance + 1 : 0; } } stack.add(pairs[i]); } else if (temp == c){ if (!stack.isEmpty()) { int k = 1; while (!stack.isEmpty() && stack.peek().word != c) { Pair pair = stack.pop(); pair.distance = pair.distance > 0 ? Math.min(pair.distance, k++) : k++; } } stack.add(pairs[i]); } } for (int i = 0; i < n; i++) { res[i] = pairs[i].distance; } return res; } } class Pair { char word; int distance; public Pair(char word) { this.word = word; this.distance = 0; } }
public class Demo2 { public static void main(String[] args) { String str = "ddfsfafafdsffggfdssasdsd"; char ch = 'a'; int[] arr = new int[str.length()]; int[] arr_rev = new int[str.length()]; int[] result = new int[str.length()]; //从左往右看 boolean flag = false; int num = 0; for(int i=0;i<str.length();i++){ if(str.charAt(i)==ch) { num = 0; flag = true; } arr[i] = num; if(flag) num++; } //从右往左看 boolean flag_rev = false; int num_rev = 0; for(int i=str.length()-1;i>=0;i--){ if(str.charAt(i)==ch) { num_rev = 0; flag_rev = true; } arr_rev[i] = num_rev; if(flag_rev) num_rev++; } //两个数组合并取结果 for(int i=0;i<arr.length;i++){ if(arr[i]==0&&arr_rev[i]==0) result[i]=0; if((arr[i]==0&&arr_rev[i]!=0)||(arr[i]!=0&&arr_rev[i]!=0&&arr[i]>=arr_rev[i])) result[i]=arr_rev[i]; if((arr[i]!=0&&arr_rev[i]==0)||(arr[i]!=0&&arr_rev[i]!=0&&arr[i]<arr_rev[i])) result[i]=arr[i]; } System.out.println(Arrays.toString(result)); } }
import java.util.Scanner;public class Main {public static void main(String[]args) {Scanner str1 = new Scanner(System.in);String str = str1.nextLine();
Scanner cha = new Scanner(System.in);String ch = cha.next();
char c = ch.charAt(0);
String[] ss = str.split(ch);
char s = str.charAt(str.length()-1);
int i = 0;
int j = 0;
int k = 0;
//存放距离的数组int [] a = new int[str.length()];//如果字符串的最后一个字符和输入的字符相同,则做记号特殊考虑boolean flag=false;if(s==c){
flag = true;
}//遍历每一个字符数组,分别计算距离for (i = 0 ; i< ss.length;i++){
if(i==0){
//分割的第一个字符数组for ( k=ss[i].length();k>0;k--){
a[j++] = k;}}else if (i==ss.length-1 && flag != true){//分割的最后一个数组 并且字符串最后一个元素不等于分割字符for ( k= 0;k<ss[i].length();k++){
a[j++] = k+1;}}else {
//中间的字符串//m和n判断当前字符数组的字符个数是奇偶int n = ss[i].length()/2;
int m = ss[i].length()%2;
//当前字符数组前半部分距离for( k = 0;k<n;k++){
a[j++]=k+1;}//奇数则中间值特殊考虑if (m==1){
a[j++]=n+1;}//当前字符数组后半部分距离for( k = n;k>0;k--){
a[j++]=k;}}//字符串中每个与分割字符相同的字符位置置为0if (i!=ss.length-1||flag){ a[j++]=0; }
}//最终结果遍历输出int ii = 0;
System.out.print("[");for (ii = 0;ii < a.length-1; ii++){ System.out.print(a[ii]+","); }System.out.print(a[ii]+"]");}}
#include <iostream>#include <string>#include <math.h>#include <vector>usingnamespacestd;int main(){string str="";char ch;cin>>str>>ch;int len=str.size();vector<int> b;for(int x=0;x<len;x++){if(str[x]==ch){b.push_back(x);}}b.push_back(2147483647);int lenb=b.size();int s=0,e=1;cout<<"[";for(int x=0;x<len;x++){if(x){cout<<",";}if(x<b[s]){cout<<b[s]-x;}if(x==b[s]){cout<<"0";}if(x>b[s]&&x<b[e]){cout<<min(x-b[s],b[e]-x);}if(x==b[e]){s++;e++;cout<<"0";}}cout<<"]";return 0;}
解法 1:比较暴力
def func1(test_str, target):
result_list = [0 if c == target else 9999 for c in test_str]
last_target, str_len = 0, len(test_str)
for i, distance in enumerate(result_list):
if distance == 0:
for k in range(last_target, i): # 向前填数
temp_distance = i-k
if result_list[k] > temp_distance:
result_list[k] = temp_distance
for k in range(i+1, str_len): # 向后填数
if result_list[k] == 0:
break
temp_distance = k-i
if result_list[k] > temp_distance:
result_list[k] = temp_distance
last_target = i
print_str = '[' + ','.join([str(i) for i in result_list]) + ']'
print(print_str)
if __name__ == '__main__':
input_str, input_target = input(), input()
func1(input_str, input_target)
解法 1:
合并了两个循环,但是效率更低了
def func1(test_str, target):
result_list = [0 if c == target else 9999 for c in test_str]
last_target, str_len = -1, len(test_str)
for i, distance in enumerate(result_list):
if distance == 0:
range_l = list(range(last_target+1, i)) + list(range(i+1, str_len))
for k in range_l:
if result_list[k] == 0:
break
temp_distance = abs(k-i)
if result_list[k] > temp_distance:
result_list[k] = temp_distance
last_target = i
print_str = '[' + ','.join([str(i) for i in result_list]) + ']'
print(print_str)
if __name__ == '__main__':
input_str, input_target = input(), input()
func1(input_str, input_target)
解法 2:二分法
import math
def func1(test_str, target):
target_index_list = [i for i, c in enumerate(test_str) if c == target]
result_list = []
str_len, i_list_len = len(test_str), len(target_index_list)
for i, index in enumerate(target_index_list):
start = 0 if i == 0 else \
math.ceil((target_index_list[i-1] + target_index_list[i] + 1) / 2)
end = str_len-1 if i == i_list_len-1 else \
math.ceil((target_index_list[i] + target_index_list[i+1] - 1) / 2)
for k in range(start, end+1):
if k != target_index_list[i]:
result_list.append(abs(target_index_list[i]-k))
else:
result_list.append(0)
print_str = '[' + ','.join([str(i) for i in result_list]) + ']'
print(print_str)
if __name__ == '__main__':
input_str, input_target = input(), input()
func1(input_str, input_target)
var readline=require('readline'); var r1=readline.createInterface({ input:process.stdin, output:process.stdout }); var inputs=[]; r1.on('line',function(data){ inputs.push(data); if(inputs.length===2){ var ind=inputs[0].indexOf(inputs[1]); var res=inputs[0].split('').reduce(function(prev,curr,index){ if(curr==inputs[1]){ for(let i=Math.ceil((ind+index)/2);i<index;i++){ prev.splice(i,1,Math.abs(index-i)) } ind=index; } prev.push(Math.abs(index-ind)); return prev; },[]); console.log(res); } })主要是中间加一个二分
import java.util.ArrayList; import java.util.List; import java.util.Scanner; /** * @author: ycz * @date: 2018/12/17 0017 16:43 * @description: */ public class Distance { public static void main(String[] args) { Scanner sc = new Scanner(System.in); String str = sc.nextLine(); String str1 = str; String ch = sc.nextLine(); List<Integer> list = getCharList(str1,ch); List<Integer> result = new ArrayList<>(); for (int p=0;p<str.length();p++){ if (p <= list.get(0)){ result.add(list.get(0)-p); }else if (p >= list.get(list.size()-1)){ result.add(p-list.get(list.size()-1)); }else { for (int q=1;q<list.size();q++){ if (list.get(q) >= p){ result.add(compare(list.get(q-1),list.get(q),p)); break; } } } } System.out.println(result.toString()); } //得到ch位置数组 private static List<Integer> getCharList(String str1,String ch){ List<Integer> list = new ArrayList<>(); int i=0; int j=0; while (str1.contains(ch)){ i = str1.indexOf(ch); list.add(i+j); j = i + j +1; str1 = str1.substring(i+1); } return list; } //比较不是头尾段的其他字符与char的距离 private static int compare(int ch1,int ch2,int num){ int d1 = num - ch1; int d2 = ch2 - num; if (d1 < d2){ return d1; } return d2; } }