[数据结构与算法]【yotta games：exam replay】

消消乐游戏(lc crush candy)

思路确定(determine ideas)

首先要找到能消除的棋子，之后进行判断然后重力模拟即可。需要注意的是L型消除，其实非常简单只要标记时使用-x , 遍历时比较的是Math.abs即可（这与《leetcode寻找消失的数字》的最优解有着异曲同工之妙：用数组本身存储额外的信息但是并不破坏数组原有的数据）。
消除方法的思想是先遍历行或者是列在遍历列或者是行，找到三个以上的就可以标记为负数状态。所有的可消除都标记完成之后就可以下落判断了。

代码实现(programming)

find the correct postive number and mark them

we need use minus sympol to mark them ,and this will maintain the original message which will be used in another row/col scanning

//mark(remove) positive numbers
    //horizontally
    static boolean mark(int[][] array){
        boolean flag = false;
        for(int i = 0 ; i < array.length ; i++) {
            for(int j = 0 ; j + 2 < array[0].length ; j++){
                if(Math.abs(array[i][j]) == Math.abs(array[i][j+1])
                        && Math.abs(array[i][j]) == Math.abs(array[i][j+2])
                        && array[i][j] != 0 && array[i][j+1] != 0 && array[i][j+2] != 0  ){
                    if(array[i][j] > 0)array[i][j] = -array[i][j];
                    if(array[i][j+1] > 0)array[i][j+1] = -array[i][j+1];
                    if(array[i][j+2] > 0)array[i][j+2] = -array[i][j+2];
                    flag = true;
                }
            }
        }
        //vertically
        for( int j = 0 ; j < array[0].length ; j++){
            for(int i = 0 ; i + 2 < array.length ; i++){
                if(Math.abs(array[i][j]) == Math.abs(array[i+1][j])
                        && Math.abs(array[i+1][j]) == Math.abs(array[i+2][j])
                        && array[i][j] != 0 && array[i+1][j] != 0 && array[i+2][j] != 0  ){//you need keep those numbers is not zero
                    if(array[i][j] > 0)array[i][j] = -array[i][j];
                    if(array[i+1][j] > 0)array[i+1][j] = -array[i+1][j];
                    if(array[i+2][j] > 0)array[i+2][j] = -array[i+2][j];
                    flag = true;
                }
            }
        }
        return flag;
    }

notably , we need use a flag to record whether we need to mark and move in the next turn,if parameter flag equals true,then we go on,or we will stop the recursion.
here is the recursion code , it contains two steps : mark and move.

static void start02(int[][] array){
        if(mark(array)){
            move(array);
            start02(array);
        }
    }

we have already finished the mark function now lets begin the move function.
here is code:

//gravity simulation
    static void move(int[][] array){
        for(int j = 0 ; j < array[0].length ; j++){//vertically scanning
            int x = array.length - 1;
             for(int i = array.length - 1 ; i >= 0 ; i--){//subtract one from i(or you can say i minus one)
                 if(array[i][j] > 0){
                     array[x][j] = array[i][j];//赋值给最下方
                     x--;//下方指针向上移动

                 }
             }
             //attention:here need to change negative number into zero,move point x upward to finish it.
            //assure the numbers above is all zero
             while(x >= 0){
                   array[x][j] = 0;
                   x--;
             }
        }
    }

now give it a test:

	020
    111
    212
    212
    * */
    public static void main(String[] args) {
        int[][] array  = new int[][]{{0,2,0},{1,1,1},{2,1,2},{2,1,2}};
        start02(array);
    }

lc 714 买卖股票的最佳时机，含手续费

here is code(optimized):

class Solution {
    public int maxProfit(int[] prices, int fee) {
        int[][] dp = new int[2][prices.length ];
        // dp[0][0] = 0;
        // dp[1][0] = -prices[0] - fee;
        int a = 0;
        int b = -prices[0] - fee;
        for( int i = 1 ; i < prices.length  ; i++){
           a = Math.max(a , b + prices[i]);
           b = Math.max(a - prices[i] - fee , b);
        }
        return a;
    }
}

寻找最大连续的01并返回是0连续的最长还是1连续的最长

classical sliding window, we can use queue to solve it.

public static void main(String[] args) {
        String[] a = checkZeroOnes(new String[]{"1101","111000"});
    }
    public static String[] checkZeroOnes (String[] strs) {
        // write code here
        String[] res = new String[strs.length];
        Queue<Character> queue = new LinkedList<>();
        for(int i = 0 ; i < strs.length ; i++){
            int a = 0 , b = 0;
            String s = strs[i];
            for(int j = 0 ; j < s.length() ; j++){

                if(queue.isEmpty() || queue.peek() == s.charAt(j)  ){
                    queue.offer(s.charAt(j));
                    if(queue.peek() == '1')a = Math.max(a,queue.size());
                    if(queue.peek() == '0')b = Math.max(b,queue.size());
                }else{
                    while(!queue.isEmpty())queue.poll();
                    queue.offer(s.charAt(j));
                    if(queue.peek() == '1')a = Math.max(a,queue.size());
                    if(queue.peek() == '0')b = Math.max(b,queue.size());
                }
            }
            while(!queue.isEmpty())queue.poll();
            res[i] = b >= a ? "0" : "1";
        }
        return res;

    }