讨论两个面经题

Smilenceyu 发表于 2021-3-25 14:05
就是把等号左右两边分开 然后把每个变量换到左边取负， 并且把其他变量都换到右边 这样每个变量都有会有几 ...

能否求一个Java版本的解答，我试着写了下还是没法处理。会持续加米。

Smilenceyu 发表于 2021-3-25 13:27
不需要建图，也不需要高斯。我当时后来自己写了下ruby代码，就是字符串parse然后每 ...

thank you!

不知道小帅 发表于 2021-1-25 20:09
第一个我觉得greedy是更好的解法啊。第二个的话，感觉常规是高斯消元。

你好! 能详细说一下greedy解法么? 多谢多谢

所以这题目有没有java的解法，哪个好心人贴一下

I cam up with the below. Not sure if this covers all the use cases. Rice if this helps

1. public void run() {
   
2.         String text = "CDFGAGB";
   
3.         String pattern = "*A*";
   
4.         System.out.println(patternMatch(text, pattern));
   
5.     }
   
6.    
   
7.     public int patternMatch(String s, String pattern) {
   
8.         String[] patternList = pattern.split("\\*");
   
9.         
   
10.         //for (int i = 0; i < patternList.length; i++) {
    
11.             System.out.println(patternList.length);
    
12.         //}
    
13.         
    
14.         if (patternList.length == 0) return 0;
    
15.         if(patternMatch(s, patternList, 0))
    
16.             return getIndex(s, patternList[0]);
    
17.         else return -1;
    
18.             
    
19.     }
    
20.    
    
21.     public boolean patternMatch(String s, String[] pattern, int index) {
    
22.         while (index < pattern.length && pattern[index] == "") index++;
    
23.         if (index == pattern.length) return true;
    
24.         
    
25.         int patIndex = getIndex(s, pattern[index]);
    
26.         
    
27.         if (patIndex == -1) return false;
    
28.         
    
29.         if (index == pattern.length-1) return true;
    
30.         if (patIndex+pattern[index].length() >= s.length()) return false;
    
31.         
    
32.         return patternMatch(s.substring(patIndex+pattern[index].length()), pattern, index+1);
    
33.     }
    
34.    
    
35.     public int getIndex(String s, String pattern) {
    
36.         int m = s.length();
    
37.         int n = pattern.length();
    
38.         
    
39.         for (int i = 0; i <= m-n; i++) {
    
40.             boolean notMatch = false;
    
41.             for (int j = 0; j < n; j++) {
    
42.                 if (s.charAt(i+j) != pattern.charAt(j)) {
    
43.                     notMatch = true;
    
44.                     break;
    
45.                 }
    
46.             }
    
47.             if (!notMatch) return i;
    
48.         }
    
49.         
    
50.         return -1;
    
51.     }

复制代码