Monday, January 16, 2017

Day Change

Given an int array 'days', and a number n representing number of days, suppose the numbers at the left of days[0] and at the right of days[days.length - 1] are both 0. Every day, the number in days array will be changed in such rule: array[i] = array[i + 1] == array[i - 1] ? 0 : 1. Return the array after n days. 

For example:
Given: days = [1,0,1,1], n = 1
Return: [0,0,1,1]

/*
Everyday, the change of each number only depends on the previous unchanged number at the left and right. The change in today of each number will not influence the next number.

time:O(n), space:O(n)
*/

import java.util.*;

public class Solution {
    public static int[] dayChange(int[] days, int n) {
        if (days == null || days.length == 0 || n <= 0) {
            return days;
        }
        if (days.length == 1) {
            days[0] = 0;
            return days;
        }
        int[] res = new int[days.length];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < days.length; j++) {
                if (j + 1 == days.length) {
                    res[j] = days[j - 1] == 0 ? 0 : 1;
                } else {
                    if (j == 0) {
                        res[j] = days[j + 1] == 0 ? 0 : 1;
                    } else {
                        res[j] = days[j + 1] == days[j - 1] ? 0 : 1;
                    }
                }
            }
            int[] tmp = res;
            res = days;
            days =tmp;
        }
        return days;
    }

    public static void main(String[] args) {
        int[] days = {0,1,0,1,1,0};
        int[] res = dayChange(days, 2);
        for(int i : res) {
            System.out.print(i + " ");
        }
    }
}

No comments:

Post a Comment