锐客网

  1. 首页 > 睿知 > it技术 > >

算法|KMP算法、计算器(一）、(二)

算法java数据结构


文章目录

  • 题目1——KMP算法
    • 解题思路
    • 代码实现
  • 题目2——计算器(一）
    • 解题思路
    • 代码实现
  • 题目3——计算器(二）
    • 解题思路
    • 代码实现

题目1——KMP算法 给定两个字符串str和match，长度分别为N和M，实现一个算法，如果字符串中含有子串match，则返回match在str中的开始位置，不含有则返回-1，若出现了多次，则按照升序输出所有出现位置。
要求：时间复杂度为O(n)。
示例
输入：acbc(第一行str) bc(第二行match)
输出：2
解题思路
【算法|KMP算法、计算器(一）、(二)】KMP算法主要是用来做字符串匹配的，它是在我们挨个字符匹配的基础上改进的。举个例子，当母串为ababcababa，子串为ababa，设两个指针i和j分别指向母串和子串，当i指向c，j指向子串最后一个字符a的时候，我们发现出现不匹配现象，但是我们可以不用将i指向第二个字符，j指向第一个字符，重新匹配。我们可以不移动i指针，将j指针前移(下面代码中的next记录了j指针的转移)指向第三个字符开始重新匹配，因为我们可以发现前缀字符ab是已经在母串中匹配了的(子串中是有对称串的，)，所以不用再重新从第二个字符匹配。这样可以大大节省时间。
代码实现
import java.io.BufferedReader; import java.io.InputStreamReader; import java.io.IOException; import java.util.*; public class Main{ public static int[] getNext(String match){ int n = match.length(); int[] next = new int[n]; next[0] = -1; //-1表示不存在最大前缀和最大 后缀 int k = -1; for(int i=1; i-1 && match.charAt(k+1) != match.charAt(i)){ k = next[k]; } if(match.charAt(k+1) == match.charAt(i)) k++; next[i] = k; } return next; } public static ArrayList KMP(String str,String match){ ArrayList res = new ArrayList(); int[] next = getNext(match); int str_n = str.length(); int match_n = match.length(); int k = -1; for(int i=0; i; i++){ while(k>-1 && match.charAt(k+1) != str.charAt(i)) k = next[k]; //往前回溯 if(match.charAt(k+1) == str.charAt(i)) k++; if(k == match_n-1){ res.add(i-match_n+1); //重新初始化，寻找下一个位置 k = -1; i = i-match_n+1; } } return res; } public static void main(String[] args) throws IOException{ BufferedReader in = new BufferedReader(new InputStreamReader(System.in)); String str = in.readLine(); String match = in.readLine(); if(str.length() < match.length()) System.out.println(-1); ArrayList res = KMP(str,match); if(res.size() == 0) System.out.println(-1); else{ Collections.sort(res); for(int i=0; i

题目2——计算器(一） 给定一个字符串形式的表达式，请你实现一个计算器并返回结果，字符串中包含+,-,(,)，保证表达式合法。
示例
输入：“1+2”
输出：3
解题思路
如果是数字，则更新当前数字tmp，其他情况将tmp重置为0；
如果是+/-，更新res+=sig*tmp，并重置tmo=0,sig根据+/-设置为1/-1；
如果是（，后面小括号里面的内容需要优先计算，所以暂时把之前的res和符号入栈，并重置res=0，sig=1;
如果是右括号，之前的结果出栈，并计算整个式子。
代码实现
import java.util.*; public class Solution { public int calculate (String s) { Deque num_st = new ArrayDeque<>(); int tmp = 0; int sig = 1; //符号位，加法是1，减法就是-1 int res = 0; for(int i=0; i.length(); i++){ char c = s.charAt(i); if(c>='0' && c<='9') tmp = tmp*10 + (c-'0'); else if(c == '+' || c == '-'){ res += sig*tmp; tmp = 0; if(c=='+') sig = 1; else sig = -1; }else if(c == '('){ num_st.push(res); num_st.push(sig); sig = 1; res = 0; } else if(c == ')'){ res += sig*tmp; tmp = 0; res *= num_st.pop(); res += num_st.pop(); } } if(tmp!=0) res += sig*tmp; return res; } }

题目3——计算器(二） 给定一个字符串形式的表达式s，请你实现一个计算器并返回结果，除法向下取整。字符串中包含+,-,*,/，保证表达式合法。
示例
输入：“8*9-19”
输出：53
解题思路
从题目中我们可以得知，字符串中一共包含几种数据：数组，操作符±*/，对于这些操作来说又可以进一步细分，一元操作符(需要知道操作符右边的数字，比如+5,-4)和二元操作符(需要知道左右两边的操作数)。
所以我们可以利用栈，从左到右遍历字符串，如果是数组，则更新数字，如果是运算符，则按照运算符规则计算，并将结果重新入栈。
代码实现
import java.util.*; public class Solution { public int calculate (String s) { String str = s+'$'; Deque st = new ArrayDeque(); char sig = '+'; //操作数之前的运算符 int num = 0; for(int i=0; i.length(); i++){ char c = str.charAt(i); if(c>='0' && c<='9'){ num = num*10 + (c -'0'); //数字则更新 }else{ if(sig == '+') st.push(num); //加法则+num入栈 else if(sig == '-') st.push(-1*num); //减法则-num入栈 else if(sig == '*') st.push(st.pop()*num); //乘法，则栈顶为左操作数，出栈计算，结果重新入栈 else if(sig == '/')//除法，与乘法类似 st.push(st.pop()/num); sig = c; //更新运算符 num = 0; //操作数置为0 } } int res = 0; //栈内所有元素的和即为表达式的值 while(!st.isEmpty()){ res += st.pop(); } return res; } }

    推荐阅读


    上一篇：前端|Vue电商项目实战（三）

    下一篇：大健康|净利润缩水，红利不再，华大基因增长前景不明朗 | 看财报