给定一个字符串str，和一个字母ch，请实现相应的代码求出一个数组，使数组中每个数字表示该位置与字母ch之间的最短距离。
比如str=”lexinfintech” ch=”i”
则输出为：[3,2,1,0,1,1,0,1,2,3,4,5]
[编程题]字符串距离
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='')
编辑于 2019-06-28 23:29:45
回复(0)
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;
}
}
如果直接用Arrays.toString()输出，格式上通不过全部用例，直接输出能通过。
用栈实现：
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;
}
}
编辑于 2019-01-06 18:23:00
回复(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));
}
}
发表于 2019-01-03 17:12:30
回复(0)
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]+"]");}}
编辑于 2018-12-24 20:27:13
回复(0)
#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;}
发表于 2018-12-20 12:18:48
回复(0)
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
void func(string str,char b);
int main()
{
string str;
char ch;
cout<<"输入一串字符和一个字母"<<"\n";
cin>>str>>ch;
//int len = str.size();
//cout<<len<<endl;
func(str,ch);
return 0;
}
void func(string str,char b)
{
int j;
int len = str.size();
for(int i = 0;i<len;i++)
{
if(str[i]-b == 0)
j = i;
}
int c;
for(int i = 0;i<len;i++)
{
c = abs(i-j);
cout<<c<<",";
}
cout<<endl;
}
#include<cstring>
#include<cmath>
using namespace std;
void func(string str,char b);
int main()
{
string str;
char ch;
cout<<"输入一串字符和一个字母"<<"\n";
cin>>str>>ch;
//int len = str.size();
//cout<<len<<endl;
func(str,ch);
return 0;
}
void func(string str,char b)
{
int j;
int len = str.size();
for(int i = 0;i<len;i++)
{
if(str[i]-b == 0)
j = i;
}
int c;
for(int i = 0;i<len;i++)
{
c = abs(i-j);
cout<<c<<",";
}
cout<<endl;
}
为毛我的通过率为0%？
发表于 2018-12-18 23:37:29
回复(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)
编辑于 2018-12-18 18:16:46
回复(0)
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);
}
})
主要是中间加一个二分
编辑于 2018-12-17 23:30:27
回复(0)
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;
}
}
发表于 2018-12-17 23:23:32
回复(0)
问题信息
通过挑战的用户
-
2022-09-21 21:53:45
-
2022-06-29 17:11:57
-
2022-04-22 18:39:29 -
2022-04-20 10:44:43 -
2022-02-06 10:59:01
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K2座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
