1.最大子序和

/**
 * 给定一个整数数组 nums ，找到一个具有最大和的连续子数组（子数组最少包含一个元素），返回其最大和。
 * 输入：nums = [-2,1,-3,4,-1,2,1,-5,4]
 * 输出：6
 * 解释：连续子数组 [4,-1,2,1] 的和最大，为 6 。
 */
public class Test_01 {
    public static void main(String[] args) {
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        int res = mxaSubArray(nums);
        System.out.println(res);
    }
    /**
     * 解释：
     * 数组第一个数赋值给res
     * 定义一个常量sum=0存放临时
     * for循环
     */
    private static int mxaSubArray(int[] nums) {
        int res = nums[0];
        int sum = 0;
        for (int num : nums) {
            if (sum > 0)
                sum += num;
            else
                sum = num;
            res = Math.max(res, sum);
        }
        return res;
    }
}

2.两数之和

/**
 * 输入：nums = [2,7,11,15], target = 9
 * 输出：[0,1]
 * 解释：因为 nums[0] + nums[1] == 9 ，返回 [0, 1] 
 */
public class Test {
    public static void main(String[] args) {
        int[] nums = {3,2,4};
        int target = 6;
        Solution solution = new Solution();
        int[] ints = solution.twoSum(nums, target);
        for (Integer i :ints) {
            System.out.println(i);
        }
    }
}
class Solution {
    public int[] twoSum(int[] nums, int target) {
        HashMap<Integer,Integer> map = new HashMap<>();
        for(int i = 0; i < nums.length; i++){
            if(map.containsKey(nums[i])){
                return new int[]{map.get(nums[i]), i};
            }
            map.put(target - nums[i], i);
        }
        return null;
    }
}

3.最后一个单词的长度

/**
 * 给你一个字符串 s，由若干单词组成，单词之间用空格隔开。
 * 返回字符串中最后一个单词的长度。如果不存在最后一个单词，请返回 0
 *
 * 单词 是指仅由字母组成、不包含任何空格字符的最大子字符串。
 */
public class Test_02 {
    public static void main(String[] args) {
        String s = "Today is a nice day";
        int res = lengthOfLastWord(s);
        System.out.println(res);
    }
    private static int lengthOfLastWord(String s) {
        String[] split = s.split(" ");
        if (split.length==0){
            return 0;
        }
        return split[split.length-1].length();
    }
}

4.加一

/**
 * 给定一个由 整数 组成的 非空 数组所表示的非负整数，在该数的基础上加一。
 * 最高位数字存放在数组的首位， 数组中每个元素只存储单个数字。
 * 你可以假设除了整数 0 之外，这个整数不会以零开头。
 */
public class Test_03 {
    public static void main(String[] args) {
        int[] array = {9,9,9};
        int[] res = plusOne(array);
        System.out.println(Arrays.toString(res));
    }
    private static int[] plusOne(int[] array) {
        for (int i = array.length-1; i >=0 ; i--) {
            if (array[i]!=9){
                array[i]++;
                return array;
            }
            array[i] = 0;
        }
        //跳出for循环，说明数字全为9
        int[] temp = new int[array.length+1];
        temp[0] = 1;
        return temp;
    }
}

5.整数反转

/**
 * 给你一个 32 位的有符号整数 x ，返回将 x 中的数字部分反转后的结果。
 * 如果反转后整数超过 32 位的有符号整数的范围 [−231,  231 − 1] ，就返回 0。
 *
 * 假设环境不允许存储 64 位整数（有符号或无符号）。
 * 输入：x = 123
 * 输出：321
 * 输入：x = -123
 * 输出：-321
 * 输入：x = 120
 * 输出：21
 */
public class Test_01 {
    public static void main(String[] args) {
        int x = 0;
        int y = reversee(x);
        System.out.println(y);
    }
    private static int reversee(int x) {
        String s = String.valueOf(x);
        int flag = 1;
        if (x<0){
            flag = -1;
            s = s.substring(1);
        }
        try{
            return Integer.parseInt(new StringBuffer(s).reverse().toString())*flag;
        }catch (Exception e){
            return 0;
        }
    }
}

6.回文数

/**
 * 回文数
 输入：x = 121
 输出：true
 输入：x = 10
 输出：false
 */
private static boolean isPalindrome1(int x) {
    String str = String.valueOf(x);
    char[] chars = str.toCharArray();
    for (int i = 0; i < chars.length; i++) {
        if (chars[i] != chars[chars.length-1-i]){
            return false;
        }
    }
    return true;
}

7.最长公共长缀

/**
 * 编写一个函数来查找字符串数组中的最长公共前缀。
 * 如果不存在公共前缀，返回空字符串 ""。
 * 输入：strs = ["flower","flow","flight"]
 * 输出："fl"
 * 输入：strs = ["dog","racecar","car"]
 * 输出：""
 * 思想：拿String 的 startWith方法判断是否以她为前缀
 */
public static String longestCommonPrefix(String[] strs){
    if (strs.length == 0) return "";
    String flag = strs[0];
    for (String string:strs) {
        while (!string.startsWith(flag)){
            flag = flag.substring(0, flag.length()-1);
        }
    }
    return flag;
}

8.爬楼梯

/**
 * 1 2 3 4 5 6
 * 1 2 3 5 8 13
 *
 * 输入： 2
 * 输出： 2
 * 解释： 有两种方法可以爬到楼顶。
 * 1.  1 阶 + 1 阶
 * 2.  2 阶
 * 示例 2：
 *
 * 输入： 3
 * 输出： 3
 * 解释： 有三种方法可以爬到楼顶。
 * 1.  1 阶 + 1 阶 + 1 阶
 * 2.  1 阶 + 2 阶
 * 3.  2 阶 + 1 阶
 */
private static int climbStairs(int i) {
    if (i<=2){
        return i;
    }
    int i1 = 1;
    int i2 = 2;
    for (int j = 3; j <= i; j++) {
        int temp = i1+i2;
        i1=i2;
        i2=temp;
    }
    return i2;
}

9.1比特与2比特字符

/**
 * 有两种特殊字符：
 *
 * 第一种字符可以用一个比特 0 来表示
 * 第二种字符可以用两个比特(10 或 11)来表示、
 * 给定一个以 0 结尾的二进制数组bits，如果最后一个字符必须是一位字符，则返回 true 。
 *
 * 示例:
 *
 * 输入: bits = [1, 0, 0]
 * 输出: true
 * 解释: 唯一的编码方式是一个两比特字符和一个一比特字符。
 * 所以最后一个字符是一比特字符。
 *
 * 输入: bits = [1, 1, 1, 0]
 * 输出: false
 * 解释: 唯一的编码方式是两比特字符和两比特字符。
 * 所以最后一个字符不是一比特字符。
 */
/**
 * 思路：
 *      1、遇到0则+1
 *      2、遇到1则+2
 *      3、判断最后与数组长度是否相等
 */
public static boolean isOneBitCharacter(int[] bits) {
        int start = 0;
        while (start<bits.length-1){
            if (bits[start] == 0){
                start++;
            }
            if (bits[start] == 1){
                start += 2;
            }
        }
        return start == bits.length-1;
}