Mark一下那些年做过的题，偶尔看看卷一卷~

///有效的括号  ( * )
import java.util.ArrayList;
import java.util.HashMap;
import java.util.*;

class Test {

    public static void main(String []args){

        String[] arg = {"(","*",")",")","*"};
        Boolean a = Vailed(arg);
        System.out.println(a);
    }

    public static Boolean Vailed(String[] args) {

        Stack <String> stack1 = new Stack <String> ();
        Stack <String> stack2 = new Stack <String> ();
        for (int i = 0; i < args.length; i++) {
            if (args[i] == "(") {
                stack1.push(args[i]);
            } else if (args[i] == "*") {
                stack2.push(args[i]);
            } else {
                if (!stack1.empty()) stack1.pop();
                else if (!stack2.empty()) stack2.pop();
                else return false;
            }
        }

        if (!stack1.empty()) {
            return stack1.size() == stack2.size();
        }
        return true;
    }
}

/// 回文串 ：删除连续子串（删一次） 保持最大回文 
import java.util.ArrayList;

class HelloWorld1 {

    public static void main(String []args){

        String origin = "fffsdddaacfgaaddd";
        String s = longestSubStr(origin);
        System.out.printf("subStr:----%s---\n", s);

        int len = s.length();
        ArrayList<Integer> res = new ArrayList<Integer>();

        int i = 0;
        int j = len -1;
        while(i<j) {
            if (s.charAt(i) == s.charAt(j)) {
                i++;
                j--;
            } else {
                i++;
                res.add(i);
            }
        }

        if(res.size() > 0) {
            String a = s.substring(0, res.get(0));
            String b = s.substring(res.get(res.size() - 1)+1, s.length());
            System.out.printf("resultStr:%s\n", a.concat(b));
            String delStr = s.substring(res.get(0),res.get(res.size() - 1)+1);
            System.out.printf("delStr:%s\n", delStr);
        } else {
            System.out.printf("resultStr:%s\n", s);
            int index = origin.indexOf(s) == 0 ? 1 : 0; 
            System.out.printf("delStr:%s\n", origin.split(s)[index]);
        }
        
    }

    public static String longestSubStr(String s) {
        String res = "";
        for (int i = 0; i < s.length(); i++) {
            String res1 = get(s, i, i);
            String res2 = get(s, i, i+1);
            res = res1.length() > res.length() ? res1 : res;
            res = res2.length() > res.length() ? res2 : res;
        }

        return res;
    }

    public static String get(String s, int l, int r) {
        Boolean canMove = true; 
        while (l >= 0 && r < s.length()) {
            if ( s.charAt(l) == s.charAt(r)) {
                l--;
                r++;
                
            } else if (canMove) {
                int temp = l;
                while (temp >= 0 && r < s.length()) {
                    if (s.charAt(temp) != s.charAt(r)) {
                        temp--;
                    } else {
                        l = temp;
                        break;
                    }
                }
                canMove = false;
            } else {
                break;
            }
        }

        if (l==-1) {
            return s.substring(l+1, r);
        } else if (canMove == false) {
            return "";
        }
        //[)
        return s.substring(l+1, r); 
    };
}

///逆序对 ：归并排序
class HelloWorld {

    public static void main(String []args){
        int []arr = {7,5,6,4};

        int a = reversePairs(arr);
        System.out.println(a);
    }

    public static int reversePairs(int[] nums) {
        int len = nums.length;

        if (len < 2) {
            return 0;
        }
        // int[] copy = new int[len];
        // for (int i = 0; i < len; i++) {
        //     copy[i] = nums[i];
        // }

        int[] temp = new int[len];
        return sort(nums, 0, nums.length-1, temp);
    }

    public static int sort(int[] nums, int left, int right, int[] temp) {
        if (left < right) {
            int mid = left + (right-left)/2;
            int leftPairs =  sort(nums,left,mid, temp);
            int rightPairs = sort(nums,mid+1,right, temp);
            int mergrPairs = merge(nums, left, mid, right, temp);

            return leftPairs+rightPairs+mergrPairs;
        }
        return 0;
    }

    public static int merge(int[] nums, int left, int mid, int right, int[] temp) {
        for (int i = left; i <= right; i++) {
            temp[i] = nums[i];
        }
        int i = left;
        int j = mid+1;

        int count = 0;
        for (int k = left; k <= right; k++) {
            if (i== mid+1) {
                nums[k] = temp[j];
                j++;
            } else if (j == right+1) {
                nums[k] = temp[i];
                i++;
            } else if(temp[i] <= temp[j]) {
                nums[k] = temp[i];
                i++;
            } else {
                nums[k] = temp[j];
                j++;
                count += mid-i+1;
            }
            
        }
        return count;
    }
}

import java.util.HashMap;
import java.util.Map;

/*
 * @lc app=leetcode.cn id=10 lang=java
 *
 * [10] 正则表达式匹配
 */

// @lc code=start
class Solution {
    public static Map<String, Boolean> map = new HashMap<String, Boolean>();
    public boolean isMatch(String s, String p) {
        return dp(s, p, 0, 0);
    }

    public boolean dp(String s, String p, int i, int j) {
        int m = s.length(); 
        int n = p.length();

        if (j == n) {
            return i==m;
        }

        if (i==m) {
            if ((n-j)%2 != 0) {
                return false;
            }
            for (; j+1 < n; j+=2) {
                if (p.charAt(j+1) != '*') {
                    return false;
                }
            }
            return true;
        }

        String key = String.valueOf(i) + "_" + String.valueOf(j);
        if(map.containsKey(key)) return map.get(key);
        boolean res = false;
        if (s.charAt(i) == p.charAt(j) || p.charAt(j) == '.') {
            if (j+1<n && p.charAt(j+1) == '*') {
                res = dp(s, p, i+1, j) || dp(s, p, i, j+2);
            } else {
                res = dp(s, p, i+1, j+1);
            }
        } else {
            if (j+1<n && p.charAt(j+1) == '*') {
                res = dp(s, p, i, j+2);
            } else {
                res = false;
            }
        }
        map.put(key, res);
        return res;
    }
}