class Solution {
    public int numberOfBeams(String[] bank) {
        int n = bank.length;
        int pre = -1;
        int res = 0;
        for(int i = 0; i < n; i++){
            int count = 0;
            for(int j = 0; j < bank[i].length(); j++) {
                if(bank[i].charAt(j) == '1')
                    count++;
            }
            if(count == 0)
                continue;
            if(pre == -1)
                pre = count;
            else{
                res += pre * count;
                pre = count;
            }
                
        }
        return res;
    }
}

class Solution {
    public int minimumSum(int num) {
        List<Integer> list = new ArrayList<>();
        while(num != 0){
            int n = num%10;
            if(n != 0)
                list.add(n);
            num /= 10;
        }
        Collections.sort(list, Collections.reverseOrder());
        if(list.size() == 1)
            return list.get(0);
        else if(list.size() == 2)
            return list.get(0) + list.get(1);
        else if(list.size() == 3)
            return (list.get(0) + 10 * list.get(2)) + list.get(1);
        else
            return (list.get(0) + 10 * list.get(2)) + (list.get(1) + 10 * list.get(3));
    }
}

Partition一个array, 要求stable..

这个c++有stable_partition的方法, java没有..

class Solution {
    public int[] pivotArray(int[] nums, int pivot) {
        List<Integer> s = new ArrayList<>();
        List<Integer> e = new ArrayList<>();
        List<Integer> g = new ArrayList<>();
        for(int n : nums){
            if(n < pivot)
                s.add(n);
            else if(n == pivot)
                e.add(n);
            else
                g.add(n);
        }
        s.addAll(e);
        s.addAll(g);
        int n = nums.length;
        int[] res = new int[n];
        for(int i = 0; i < n; i++){
            res[i] = s.get(i);
        }
        return res;
    }

}

给两个数字, 大减小, 求多少步能减到0.

class Solution {
    public int countOperations(int a, int b) {
        if(a == 0 || b == 0)
            return 0;
        if(a > b)
            return countOperations(a - b, b) + 1;
        else
            return countOperations(a, b - a) + 1;
    }
}

给一个矩阵和一个bot的起始位置还有一串命令, 求能运行多少个这个命令的suffix命令.

这题就是模拟题.

class Solution {
    public int[] executeInstructions(int n, int[] startPos, String s) {
        int[] res = new int[s.length()];
        for(int i = 0; i < s.length(); i ++){
            res[i] = sim(startPos[0], startPos[1], n, i, s);
        }
        return res;
    }
    
    private int sim(int x, int y, int n, int pos, String s) {
        if(pos >= s.length())
            return 0;
        if(s.charAt(pos) == 'L' && y - 1 >= 0)
            return sim(x, y - 1, n, pos + 1, s) + 1;
        else if(s.charAt(pos) == 'U' && x - 1 >= 0)
            return sim(x - 1, y, n, pos + 1, s) + 1;
        else if(s.charAt(pos) == 'R' && y + 1 < n)
            return sim(x, y + 1, n, pos + 1, s) + 1;
        else if(s.charAt(pos) == 'D' && x + 1 < n)
            return sim(x + 1, y, n, pos + 1, s) + 1;
        else
            return 0;
    }
}

给一个按照绝对值排序的链表, 求按照数字排序的链表.

这题就是先拆分成pos和neg两个链表, 然后如果neg是空的, 返回pos, 如果不是, 翻转neg后连上pos再返回.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode sortLinkedList(ListNode head) {
        ListNode neg = new ListNode();
        ListNode pos = new ListNode();
        ListNode nh = neg;
        ListNode ph = pos;
        ListNode p = head;
        while(p != null){
            if(p.val >= 0){
                ph.next = new ListNode(p.val);
                ph = ph.next;
            }
            else
            {
                nh.next = new ListNode(p.val);
                nh = nh.next;
            }
            p = p.next;
        }
        if(neg.next == null)
            return pos.next;
        ListNode th = rev(neg.next);
        ListNode d = th;
        while(d.next != null)
            d = d.next;
        d.next = pos.next;
        return th;
    }
    private ListNode rev(ListNode head) {
        ListNode newHead = null;
        while(head != null){
            ListNode next = head.next;
            head.next = newHead;
            newHead = head;
            head = next;
        }
        return newHead;
    }
}

给一个字符串, 求所有子字符串的元音字母的和.

观察可以知道如果某一个字符是元音, 那么所有的包含这个元音的字符串的个数是它前边的所有字符的个数加上后边所有字符的个数.

class Solution {
    public long countVowels(String word) {
        int n = word.length();
        long count = 0;
        long res = 0;
        for(int i = 0; i < n; i++){
            if(check(word.charAt(i))){
                res += (count + 1) * (n - count); 
            } 
                count++; 
        }
        return res;
    }
    
    private boolean check(char c) {
        return c == 'a' || c == 'e' || c == 'i' || c =='o' || c == 'u';
    }
}

给一个矩阵, 每个格子都能往下面的相邻的格子落, 问怎么落的相加后的和最小.

这题就是典型的矩阵dp.

class Solution {
    public int minFallingPathSum(int[][] matrix) {
        int n = matrix.length;
        int[][] dp = new int[n][n]; // dp[i][j] = the min falling path sum to the current cell [i][j]
        for(int i = 0; i < n; i++){
            dp[0][i] = matrix[0][i];
        }
        for(int i = 1; i < n; i++) {
            for(int j = 0; j < n; j++) {
                dp[i][j] = Math.min(Math.min(j > 0 ? dp[i - 1][j - 1] : Integer.MAX_VALUE, dp[i - 1][j]), j < n - 1 ? dp[i - 1][j + 1] : Integer.MAX_VALUE) + matrix[i][j];  
            }
        }
        int res = Integer.MAX_VALUE;
        for(int i = 0; i < n; i++){
            res = Math.min(dp[n - 1][i],res);
        }        
        return res;
    }
}

定义一个alternating subsequence sum为偶数相加减去奇数相减的和. 求最大的一个.

这题就是找两个上下波动的本地最值, 用dp做, 选的方法只有从当前最大的even或者odd选或者不选.

class Solution {
    public long maxAlternatingSum(int[] nums) {
        long [][] dp = new long[2][nums.length+1];
        long max = 0;
        for(int i=0;i<nums.length;i++){
            dp[0][i+1] = Math.max(dp[1][i]+nums[i], dp[0][i]);
            dp[1][i+1] = Math.max(dp[0][i]-nums[i], dp[1][i]);
            max = Math.max(dp[0][i+1], Math.max(max, dp[1][i+1]));
        }
        return max;
    }
}

给一个字符串, 可以替换k个字符, 求替换后最长的reapting character.

这题有点难度, 需要双指针滑窗, 当找到满足的后, start应该++.

class Solution {
    public int characterReplacement(String s, int k) {
        int start = 0;
        int end = 0;
        char max = s.charAt(0);
        int curMax = 0;
        int len = s.length();
        int res = 0;
        int flip = 0;
        int sameLetter = 0;
        Map<Character, Integer> map = new HashMap<>();
        while (start < len - k) {
            while (end < len && flip <= k) {
                char c = s.charAt(end);
                Integer value = map.get(c);
                if (value == null) {
                    map.put(c, 1);
                } else {
                    map.put(c, value + 1);
                }
                value = map.get(c);
                if (value > sameLetter) {
                    max = c;
                    sameLetter = value;
                }
                flip = end - start + 1 - sameLetter;
                if (flip <= k) {
                    curMax = Math.max(curMax, end - start + 1);
                }
                end++;
            }
            res = Math.max(res, curMax);
            char remove = s.charAt(start);
            Integer i = map.get(remove);
            map.put(remove, i - 1);
            start++; // aaabb
            flip=0;
        }
        return res;
    }
}