给一个字符串, 找到所有可能的回文子字符串的个数.

这题还是很巧妙的, 利用回文的性质, 就是奇数对称和偶数对称两种回文, 然后搜索, couting一下即可

class Solution {
    public int countSubstrings(String s) {
        int n = s.length();
        int res = 0;
        for(int i = 0; i < n; i++) {
            int odd = count(s, i, i);
            int even = count(s,i, i + 1);
            res += odd;
            res += even;
        }
        return res;
    }
    
    private int count(String s, int start, int end){
        int i = start;
        int j = end;
        int res = 0;
        while(i >= 0 && j < s.length() && s.charAt(i) == s.charAt(j)){
            res++;
            i--;
            j++;
        }
        return res;
    }
    //abbacca
}

最长公共子序列, 这题就是dp.

dp[i][j]表示在第一个string的i位和第二个string的j位的最长公共子序列.

dp[i][j] = dp[i – 1][j – 1] when A[i] == B[j], otherwise dp[i][j] = max(dp[i][j – 1], dp[i – 1][j])

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int n = text1.length();
        int m = text2.length();
        int[][] dp = new int[n][m];
        for(int i = 0; i < n; i++) {
            if(text1.charAt(i) == text2.charAt(0))
                dp[i][0] = 1;
            else if(i > 0 && dp[i - 1][0] == 1)
                dp[i][0] = 1;
        }
        for(int j = 0; j < m; j++) {
            if(text1.charAt(0) == text2.charAt(j))
                dp[0][j] = 1;
            else if(j > 0 && dp[0][j - 1] == 1)
                dp[0][j] = 1;
                
        }
        for(int i = 1; i < n; i++){
            for(int j = 1; j < m; j++){
                if(text1.charAt(i) == text2.charAt(j))
                    dp[i][j] = dp[i - 1][j - 1]+ 1;
                else
                    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
        return dp[n - 1][m - 1];
    }
}

模拟一个银行系统,存钱取钱.

主要是判断一下各种可能情况.

class Bank {

    private long[] b;
    private int n;
    public Bank(long[] b) {
        this.n = b.length;
        this.b = new long[n + 1];
        for(int i = 0; i < n; i++){
            this.b[i+1] = b[i];
        }
    }
    private boolean exist(int a){
        return 1 <= a && a <= n;
    }
    public boolean transfer(int a1, int a2, long m) {
        if(exist(a1) && exist(a2) && b[a1] >= m){
            b[a1] -= m;
            b[a2] += m;
            return true;
        }
        else
            return false;
    }
    
    public boolean deposit(int a, long m) {
        if(!exist(a))
            return false;
        b[a] += m;
        return true;
    }
    
    public boolean withdraw(int a, long m) {
        if(!exist(a))
            return false;
        if(b[a] < m)
            return false;
        b[a] -= m;
        return true;
    }
}

/**
 * Your Bank object will be instantiated and called as such:
 * Bank obj = new Bank(balance);
 * boolean param_1 = obj.transfer(account1,account2,money);
 * boolean param_2 = obj.deposit(account,money);
 * boolean param_3 = obj.withdraw(account,money);
 */

给一个数组, 找最小的index, 使i mod 10 == nums[i].

用一个j表示一个从0->9的循环. 然后挨个找.

class Solution {
    public int smallestEqual(int[] nums) {
        int j = 0;
        for(int i = 0; i < nums.length; i++) {
            if(nums[i] == j)
                return i;
            j++;
            j %= 10;
        }
        return -1;
    }
}

给一个字符串组和一个target字符串, 问有多少个pair,组成target.

这题字符串组有重复, 所以先要counting一下, 然后切割target, 因为切割后的两个部分有可能相同, 相同的时候是C(n,n-1)个, 不同的时候是n* n-1个.

class Solution {
    public int numOfPairs(String[] nums, String target) {
        Map<String, Integer> count = new HashMap<>();
        for(String s : nums){
            count.put(s, count.getOrDefault(s, 0) + 1);
        }
        int res = 0;
        for(int i = 1; i < target.length(); i++) {
            String a = target.substring(0, i);
            String b = target.substring(i, target.length());
            if(count.containsKey(a) && count.containsKey(b)){
                if(a.equals(b)){ 
                    int n = count.get(a);
                    res += n * (n - 1);
                }else
                {
                    res += count.get(a) * count.get(b);
                }
            }
        }
        return res;
    }
}

把一个字符串分割成k组, 如果不满k,就用fill字符补.

class Solution {
    public String[] divideString(String s, int k, char fill) {
        List<String> list = new ArrayList<>();
        int n = s.length();
        StringBuffer sb = new StringBuffer(s);
        int m = n % k == 0 ? 0 : k - (n%k);
        for(int i = 0; i < m; i++)
            sb.append(fill);
        String str = sb.toString();
        for(int i = 0; i < str.length(); i+=k){
            list.add(str.substring(i, i + k));
        }
        String[] strs = new String[list.size()];
        for(int i = 0; i < list.size(); i++)
            strs[i] = list.get(i);
        return strs;
    }
}

给一个数组, 是东西的价格, 可以买二送一, 求花费. 要求送的cost比买的要少.

class Solution {
    public int minimumCost(int[] cost) {
        Arrays.sort(cost);
        if(cost.length == 1)
            return cost[0];
        if(cost.length == 2)
            return cost[0] + cost[1];
        int res = 0;
        int i = cost.length - 1;
        while(i >= 0){
            if(i == 0){
                res += cost[i];
                break;
            }else if(i == 1){
                res += cost[i];
                res += cost[i - 1];
                break;
            }else{
                res += cost[i];
                res += cost[i - 1];
                i -= 3;
            }
        }
        return res;
    }
}

给一个数组, 问这个数组有多少个数字是至少有一个数字严格比它大还有一个严格比它小的.

class Solution {
    public int countElements(int[] nums) {
        int nMax = 0;
        int max = Integer.MIN_VALUE;
        int nMin = 0;
        int min = Integer.MAX_VALUE;
        for(int n : nums){
            max = Math.max(max, n);
            min = Math.min(min, n);
        }
        for(int n : nums){
            if(n == max)
                nMax++;
            if(n == min)
                nMin++;
        }
        if(nMax == nums.length)
            return 0;
        return nums.length - nMax - nMin;
    }
}

class Solution {
    public int finalValueAfterOperations(String[] operations) {
        int res = 0;
        String a = "++X";
        String b = "X++";
        for(String o : operations)
        {
            if(o.equals(a) || o.equals(b))
                res++;
            else
                res--;
        }
        return res;
    }
}

给一个数组, 找到两个数, i<j的差的最大值.

这题因为要求两个数有顺序, 所以只需要扫一次, 并且一直track最小值,就可以.

class Solution {
    public int maximumDifference(int[] nums) {
        int min = Integer.MAX_VALUE;
        int res = -1;
        for(int n : nums)
        {
            if(n <= min)
                min = n;
            else
                res = Math.max(n - min, res);
        }
        return res;
    }
}