Max Consecutive Ones-LeetCode#485

  • cqh 
485. Max Consecutive Ones
Given a binary array, find the maximum number of consecutive 1s in this array. Example 1:
Input: [1,1,0,1,1,1]
Output: 3
Explanation: The first two digits or the last three digits are consecutive 1s.
    The maximum number of consecutive 1s is 3.
Note:
  • The input array will only contain 0 and 1.
  • The length of input array is a positive integer and will not exceed 10,000
思路:查找二进制数组中1的连续最长长度。利用String的indexOf计算0出现的位置,截取长度为1的连续长度。 代码如下:
/**
 * @Author: Poldi
 * @Date: 2019-06-01 17:34
 * @Description: 485. Max Consecutive Ones
 */
public class MaxConsecutiveOnes {
    public static int findMaxConsecutiveOnes(int[] nums) {
        StringBuilder stringBuilder = new StringBuilder();
        for (int a : nums) {
            stringBuilder.append(a);
        }
        int temp = sliceStr(stringBuilder.toString(), 0);
        return temp;
    }
    public static int sliceStr(String str, int temp) {
        if (str.equals("")) return temp;
        if (!str.contains("0")) {
            return temp > str.length() ? temp : str.length();
        }
        if (str.indexOf("0") > temp) {
            temp = str.indexOf("0");
        }
        str = str.substring(str.indexOf("0") + 1);
        return sliceStr(str, temp);
    }
    public static void main(String[] args) {
        int[] nums = {1, 1, 0, 1, 1, 1, 0, 1, 1};
        MaxConsecutiveOnes.findMaxConsecutiveOnes(nums);
    }
}
ps:好久没做算法了....懒啊

Prison Cells After N Days-LeetCode#957

  • cqh 
957. Prison Cells After N Days
There are 8 prison cells in a row, and each cell is either occupied or vacant. Each day, whether the cell is occupied or vacant changes according to the following rules:
  • If a cell has two adjacent neighbors that are both occupied or both vacant, then the cell becomes occupied.
  • Otherwise, it becomes vacant.
(Note that because the prison is a row, the first and the last cells in the row can't have two adjacent neighbors.) We describe the current state of the prison in the following way: cells[i] == 1 if the i-th cell is occupied, else cells[i] == 0. Given the initial state of the prison, return the state of the prison after N days (and N such changes described above.)
Example 1:
Input: cells = [0,1,0,1,1,0,0,1], N = 7
Output: [0,0,1,1,0,0,0,0]
Explanation:
The following table summarizes the state of the prison on each day:
Day 0: [0, 1, 0, 1, 1, 0, 0, 1]
Day 1: [0, 1, 1, 0, 0, 0, 0, 0]
Day 2: [0, 0, 0, 0, 1, 1, 1, 0]
Day 3: [0, 1, 1, 0, 0, 1, 0, 0]
Day 4: [0, 0, 0, 0, 0, 1, 0, 0]
Day 5: [0, 1, 1, 1, 0, 1, 0, 0]
Day 6: [0, 0, 1, 0, 1, 1, 0, 0]
Day 7: [0, 0, 1, 1, 0, 0, 0, 0]
Example 2:
Input: cells = [1,0,0,1,0,0,1,0], N = 1000000000
Output: [0,0,1,1,1,1,1,0]
Note:
  1. cells.length == 8
  2. cells[i] is in {0, 1}
  3. 1 <= N <= 10^9
思路:连续8个牢房,每个牢房被占用或空置。每天,根据以下规则,单元是否被占用或空置变化:如果一个小区有两个相邻的邻居,它们都被占用或者都是空的,那么该小区就会被占用。否则,它会变空。请注意,因为监狱是一排,所以行中的第一个和最后一个单元格不能有两个相邻的邻居。我们用以下方式描述监狱的当前状态:如果第i个cell被占用,则cell [i] == 1,否则cells [i] == 0。鉴于监狱的初始状态,在N天之后返回监狱的状态(以及上述N个这样的改变。) 看到N=1000000000,思考一下应该是有循环的
  • 0 1 0 1 1 0 0 1
  • 0 1 1 0 0 0 0 0
  • 0 0 0 0 1 1 1 0
  • 0 1 1 0 0 1 0 0
  • 0 0 0 0 0 1 0 0
  • 0 1 1 1 0 1 0 0
  • 0 0 1 0 1 1 0 0
  • 0 0 1 1 0 0 0 0
  • 0 0 0 0 0 1 1 0
  • 0 1 1 1 0 0 0 0
  • 0 0 1 0 0 1 1 0
  • 0 0 1 0 0 0 0 0
  • 0 0 1 0 1 1 1 0
  • 0 0 1 1 0 1 0 0
  • 0 0 0 0 1 1 0 0
  • 0 1 1 0 0 0 0 0
可以看出周期为14。 代码如下:
public class PrisonAfterNDays {
    public static int[] prisonAfterNDays(int[] cells, int N) {
        int n = 0;
        List<int[]> list = new ArrayList<>();
        switchCells(cells, list, n);
        if (N < 14){
            return list.get(N - 1);
        }else {
            if (N % 14 == 0){
                return list.get(13);
            }else {
                return list.get(N % 14 - 1);
            }
        }
    }
    static void switchCells(int[] cells, List<int[]> list, int n){
        n++;
        int[] temp = new int[8];
        temp[0] = 0;
        temp[7] = 0;
        for (int i = 1; i < cells.length - 1; i++) {
            temp[i] = cells[i - 1] == cells[i + 1] ? 1 : 0;
        }
        list.add(temp);
        if (n < 14){
            switchCells(temp, list, n);
        }
    }
}
 

License Key Formatting-LeetCode#482

  • cqh 
482. License Key Formatting
You are given a license key represented as a string S which consists only alphanumeric character and dashes. The string is separated into N+1 groups by N dashes. Given a number K, we would want to reformat the strings such that each group contains exactly K characters, except for the first group which could be shorter than K, but still must contain at least one character. Furthermore, there must be a dash inserted between two groups and all lowercase letters should be converted to uppercase. Given a non-empty string S and a number K, format the string according to the rules described above. Example 1:
Input: S = "5F3Z-2e-9-w", K = 4
Output: "5F3Z-2E9W"
Explanation: The string S has been split into two parts, each part has 4 characters.
Note that the two extra dashes are not needed and can be removed.
Example 2:
Input: S = "2-5g-3-J", K = 2
Output: "2-5G-3J"
Explanation: The string S has been split into three parts, each part has 2 characters except the first part as it could be shorter as mentioned above.
Note:
  1. The length of string S will not exceed 12,000, and K is a positive integer.
  2. String S consists only of alphanumerical characters (a-z and/or A-Z and/or 0-9) and dashes(-).
  3. String S is non-empty.
思路:将获得一个表示为字符串S的许可证密钥,该字符串仅包含字母数字字符和短划线。该字符串被N个破折号分成N + 1个组。给定数字K,我们希望重新格式化字符串,使得每个组包含正好的K个字符,但第一个组可能比K短,但仍然必须包含至少一个字符。此外,必须在两个组之间插入短划线,并且所有小写字母都应转换为大写。看完题目第一时间想到的就是使用split分割后使用StringBuilder拼接。 代码如下:
public class LicenseKeyFormatting {
    public static String licenseKeyFormatting(String S, int K) {
        String[] str = S.split("-");
        StringBuilder stringBuilder = new StringBuilder();
        for (int i = 0; i < str.length; i++) {
            stringBuilder.append(str[i].toUpperCase());
        }
        if (stringBuilder.length() <= 0) return "";
        int oth = stringBuilder.length() % K;
        int count = stringBuilder.length() / K;
        StringBuilder res = new StringBuilder();
        if (oth == 0) {
            for (int i = 0; i < count; i++) {
                String temp = stringBuilder.substring(i * K, i * K + K);
                res.append(temp + "-");
            }
        } else {
            String head = stringBuilder.substring(0, oth);
            res.append(head + "-");
            StringBuilder stringBuilder1 = stringBuilder.delete(0, oth);
            for (int i = 0; i < count; i++) {
                String temp = stringBuilder1.substring(i * K, i * K + K);
                res.append(temp + "-");
            }
        }
        return res.substring(0, res.length() - 1);
    }
}
更简便:
 public String licenseKeyFormatting(String S, int K) {
    S = S.replaceAll("-", "").toUpperCase();
    StringBuilder sb = new StringBuilder(S);
    // Starting from the end of sb, and going backwards. 
    int i = sb.length() - K;
    while(i > 0) {
        sb.insert(i, '-');
        i = i - K;
    }
    return sb.toString();
}

Buddy Strings-LeetCode#859

  • cqh 
859. Buddy Strings
Given two strings A and B of lowercase letters, return true if and only if we can swap two letters in A so that the result equals B.   Example 1:
Input: A = "ab", B = "ba"
Output: true
Example 2:
Input: A = "ab", B = "ab"
Output: false
Example 3:
Input: A = "aa", B = "aa"
Output: true
Example 4:
Input: A = "aaaaaaabc", B = "aaaaaaacb"
Output: true
Example 5:
Input: A = "", B = "aa"
Output: false
  Note:
  1. 0 <= A.length <= 20000
  2. 0 <= B.length <= 20000
  3. A and B consist only of lowercase letters.
思路:给定两个字母A和B的小写字母,当且仅当我们可以在A中交换两个字母以使结果等于B时返回true。三个条件:
  1. A.length() != B.length(): 长度不同 false
  2. A == B, 如果两个值相同,必需要存在重复的字符
  3. 其他情况 A[i] != B[i]只会出现两次
代码如下:
public class BuddyStrings {
    public boolean buddyStrings(String A, String B) {
        if (A.length() != B.length()) return false;
        if (A.equals(B)) {
            Set<Character> set = new HashSet<>();
            for (char c : A.toCharArray()) {
                set.add(c);
            }
            if (set.size() == A.length()) {
                return false;
            } else {
                return true;
            }
        } else {
            StringBuilder stringBuilderA = new StringBuilder();
            StringBuilder stringBuilderB = new StringBuilder();
            for (int i = 0; i < A.length(); i++) {
                if (A.toCharArray()[i] != B.toCharArray()[i]){
                    stringBuilderA.append(A.toCharArray()[i]);
                    stringBuilderB.append(B.toCharArray()[i]);
                }
            }
            if (stringBuilderA.toString().equals(stringBuilderB.reverse().toString())){
                return true;
            }else {
                return false;
            }
        }
    }
}
 

Reverse Words in a String III-LeetCode#557

  • cqh 
557. Reverse Words in a String III
Given a string, you need to reverse the order of characters in each word within a sentence while still preserving whitespace and initial word order. Example 1:
Input: "Let's take LeetCode contest"
Output: "s'teL ekat edoCteeL tsetnoc"
Note: In the string, each word is separated by single space and there will not be any extra space in the string.
 思路:给定一个字符串,你需要颠倒句子中每个单词中的字符顺序,同时仍然保留空格和初始单词顺序。可以运用StringBuilder的reverse方法。
代码如下:
public class ReverseWordsInAStringIII {
    public static String reverseWords(String s) {
        String[] strings = s.split(" ");
        StringBuilder res = new StringBuilder();
        for (int i = 0; i < strings.length; i++) {
            StringBuilder temp = new StringBuilder(strings[i]);
            res.append(temp.reverse() + " ");
        }
        return res.toString().trim();
    }
}
p: String的trim()方法,去除首尾空格

Pascal's Triangle-LeetCode#118

  • cqh 
118. Pascal's Triangle
Given a non-negative integer numRows, generate the first numRows of Pascal's triangle. In Pascal's triangle, each number is the sum of the two numbers directly above it. Example:
Input: 5
Output:
[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]
思路:给定非负整数numRows,生成Pascal三角形的第一个numRows。在Pascal的三角形中,每个数字是它正上方的两个数字的总和。从图中可以得出首尾数字都为1,中间数字res[i][j] = res[i-1][j-1] + res[i-1][j] 代码如下:
public class PascalTriangle {
    public static List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < numRows; i++) {
            List<Integer> temp = new ArrayList<>();
            if (i == 0) {
                temp.add(1);
            } else {
                for (int j = 0; j < i + 1; j++) {
                    if (j == 0) {
                        temp.add(1);
                    } else if (j == i) {
                        temp.add(1);
                    } else {
                        temp.add(res.get(i - 1).get(j - 1) + res.get(i - 1).get(j));
                    }
                }
            }
            res.add(temp);
        }
        return res;
    }
}

Valid Parentheses-LeetCode#20

  • cqh 
20. Valid Parentheses
Given a string containing just the characters '('')''{''}''[' and ']', determine if the input string is valid. An input string is valid if:
  1. Open brackets must be closed by the same type of brackets.
  2. Open brackets must be closed in the correct order.
Note that an empty string is also considered valid. Example 1:
Input: "()"
Output: true
Example 2:
Input: "()[]{}"
Output: true
Example 3:
Input: "(]"
Output: false
Example 4:
Input: "([)]"
Output: false
Example 5:
Input: "{[]}"
Output: true
思路:给定一个只包含字符'(',')','{','}','['和']'的字符串,确定输入字符串是否有效。必须使用相同类型的括号关闭左括号。必须以正确的顺序关闭打开括号。
用一个栈,我们开始遍历输入字符串,如果当前字符为左半边括号时,则将其压入栈中,如果遇到右半边括号时,若此时栈为空,则直接返回false,如不为空,则取出栈顶元素,若为对应的左半边括号,则继续循环,反之返回false。
代码如下:
public class ValidParentheses {
    public boolean isValid(String s) {
        Stack<Character> temp = new Stack<>();
        char[] chars = s.toCharArray();
        for (int i = 0; i < s.length(); i++) {
            if (chars[i] == '(' || chars[i] == '{' || chars[i] == '[') {
                temp.push(chars[i]);
            } else {
                if (temp.empty()) return false;
                if (chars[i] == ')' && temp.peek() != '(') return false;
                if (chars[i] == '}' && temp.peek() != '{') return false;
                if (chars[i] == ']' && temp.peek() != '[') return false;
                temp.pop();
            }
        }
        return temp.empty();
    }
}

Repeated Substring Pattern-LeetCode#459

  • cqh 
459. Repeated Substring Pattern
Given a non-empty string check if it can be constructed by taking a substring of it and appending multiple copies of the substring together. You may assume the given string consists of lowercase English letters only and its length will not exceed 10000.   Example 1:
Input: "abab"
Output: True
Explanation: It's the substring "ab" twice.
Example 2:
Input: "aba"
Output: False
Example 3:
Input: "abcabcabcabc"
Output: True
Explanation: It's the substring "abc" four times. (And the substring "abcabc" twice.)
思路:从原字符串长度的一半遍历到1,如果当前长度能被总长度整除,说明可以分成若干个子字符串,我们将这些子字符串拼接起来看跟原字符串是否相等。
代码如下:
public class RepeatedSubstringPattern {
    public boolean repeatedSubstringPattern(String s) {
        int l = s.length();
        for (int i = l / 2; i >= 1; i--) {
            if (l % i == 0) {
                String temp = s.substring(0, i);
                StringBuilder stringBuilder = new StringBuilder();
                for (int j = 0; j < l / i; j++) {
                    stringBuilder.append(temp);
                }
                if (stringBuilder.toString().equals(s)) return true;
            }
        }
        return false;
    }
}

Counting Bits-LeetCode#338

  • cqh 
338. Counting Bits
Given a non negative integer number num. For every numbers i in the range 0 ≤ i ≤ num calculate the number of 1's in their binary representation and return them as an array. Example 1:
Input: 2
Output: [0,1,1]
Example 2:
Input: 5
Output: [0,1,1,2,1,2]
Follow up:
  • It is very easy to come up with a solution with run time O(n*sizeof(integer)). But can you do it in linear time O(n) /possibly in a single pass?
  • Space complexity should be O(n).
  • Can you do it like a boss? Do it without using any builtin function like __builtin_popcount in c++ or in any other language.
思路:题目意为给定一个非负整数,计算每个从0至num的数字二进制中1的个数,返回数组。用动态规划的思想可以举例 dp[0] = 0; dp[1] = dp[0] + 1; dp[2] = dp[0] + 1; dp[3] = dp[1] +1; dp[4] = dp[0] + 1; dp[5] = dp[1] + 1; dp[6] = dp[2] + 1; dp[7] = dp[3] + 1; dp[8] = dp[0] + 1; 等于 dp[0] = 0; dp[1] = dp[1-1] + 1; dp[2] = dp[2-2] + 1; dp[3] = dp[3-2] +1; dp[4] = dp[4-4] + 1; dp[5] = dp[5-4] + 1; dp[6] = dp[6-4] + 1; dp[7] = dp[7-4] + 1; dp[8] = dp[8-8] + 1; 能得出dp[index] = dp[index - offset] + 1; 代码如下:
public class CountingBits {
    public static int[] countBits(int num) {
        int[] res = new int[num + 1];
        int i = 1;
        int offset = 1;
        while (i < num + 1) {
            if (offset * 2 == i) {
                offset = offset * 2;
            }
            res[i] = res[i - offset] + 1;
            i++;
        }
        return res;
    }
}

Perfect Squares-LeetCode#279

  • cqh 
279. Perfect Squares
Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n. Example 1:
Input: n = 12
Output: 3
Explanation: 12 = 4 + 4 + 4.
Example 2:
Input: n = 13
Output: 2
Explanation: 13 = 4 + 9.
思路:题目意思为给定一个正整数n,找到总和为n的最小正方数(例如,1,4,9,16 ......)。可以用动态规划的思想,循环里计算,每次增加一个dp数组的长度,里面那个for循环一次循环结束就算好下一个数由几个完全平方数组成,直到增加到第n+1个,返回即可。
代码如下:
public class PerfectSquares {
    public static int numSquares(int n) {
        int[] dp = new int[n + 1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0] = 0;
        for (int i = 0; i <= n; i++) {
            for (int j = 1; j * j <= i; j++) {
                dp[i] = Math.min(dp[i], dp[i - j * j] + 1);
            }
        }
        return dp[n];
    }
}