/**
 * 给定一个字符串，请编写一个函数判断该字符串是否回文。如果回文请返回true，否则返回false。
 * 
 * 思路: 从左往右和从右往左输出的字符串都是一样的就是回文字符串
 * 将字符串转为数组，然后循环数组，循环的个数是对数组除以2, 然后判断数组的第一个和最后一个是否一致，然后依次对比，
 * 如果发现不一致，则认为不是回文
 * 
 * 
 * @param str string字符串 待判断的字符串
 * @return bool布尔型
 */
public boolean judge(String str) {
    if (str.length == 0) {
        return false; // 或者抛错
    }

    if (str.length() == 1) {
        return true;
    }

    char[] strArr = str.toCharArray();

    boolean isJudge = true;
    int strArrleng = strArr.length;

    for (int i = 0; i < strArrleng / 2 ; i++) {
        if (strArr[i] != strArr[strArrleng - i - 1]) {
            isJudge = false;
            break;
        }
    }

    return isJudge;
}

/**
 * NC103 反转字符串
 * 描述
 * 写出一个程序，接受一个字符串，然后输出该字符串反转后的字符串。
 */
public String solve (String str) {
    if (str.length() < 0 || str.length() > 1000) {
        throw new RuntimeException("非法字符串");
    }
    
    StringBuffer s = new StringBuffer();
    
    char[] strArr = str.toCharArray();
    for (int i = strArr.length - 1; i >= 0 ; i--) {
        s.append(strArr[i]);
    }
    
    return s.toString();
}

public String solve (String str) {
        if (str.length() < 0 || str.length() > 1000) {
            throw new RuntimeException("非法字符串");
        }
     
        char[] strArr = str.toCharArray();
        int strArrLeng = strArr.length;

        for (int i = 0; i < strArrLeng / 2; i++) {
            if (strArr[i] == strArr[strArrLeng - i - 1]) {
                continue;
            }
            
            char temp = strArr[i];
            strArr[i] = strArr[strArrLeng - i - 1];
            strArr[strArrLeng - i - 1] = temp;
        }
        
        return String.valueOf(strArr);
    }


/**
 * 描述：输入一个整数，输出该数32位二进制表示中1的个数。其中负数用补码表示。
 * 
 * 注: 借助于JAVA的十进制转二进制的方法
 */
public int numberOf1(int n) {
    String str = Integer.toBinaryString(n); // 返回int变量的二进制表示的字符串。

    char[] strArr = str.toCharArray();
    int count = 0;
    for (int i = 0; i < strArr.length; i++) {
        if (strArr[i] == '1') {
            count++;
        }
    }
       
    return count; 
}

/**
 * 冒泡排序 - 从大到小排序
 */
public static int[] sort(int[] sortArr) {
    int sortSize = sortArr.length;
    for (int i = 0; i < sortSize - 1; i++) {
        for (int j = 0; j < sortSize - i -1; j++) {
            if (sortArr[j] < sortArr[j + 1]) {
                int temp = sortArr[j];
                sortArr[j] = sortArr[j + 1];
                sortArr[j + 1] = temp;
            }
        }
    }

    return sortArr;
}

/**
 * 冒泡排序 - 从小到大排序
 */
public static int[] sort(int[] sortArr) {
    int sortSize = sortArr.length;
    for (int i = 0; i < sortSize - 1; i++) {
        for (int j = 0; j < sortSize - i - 1; j++) {
            if (sortArr[j] > sortArr[j + 1]) {
                int temp = sortArr[j];
                sortArr[j] = sortArr[j + 1];
                sortArr[j + 1] = temp;
            }
        }
    }

    return sortArr;
}


/**
  * 1. 第一个只出现一次的字符
  *
  * 解释: 在一个字符串(0<=字符串长度<=10000，全部由字母组成)中找到第一个只出现一次的字符,并返回它的位置, 如果没有则返回 -1（需要区分大小写）.（从0开始计数）
  *
  * 方法比较笨，使用了双层循环
  */
public int FirstNotRepeatingChar(String str) {
    if (str == null || str == "") {
        return -1;
    }
    
    char[] strArr = str.toCharArray();
    
    int index = -1;
    boolean isTrue = false;

    for (int i = 0; i < strArr.length; i++) {
        for (int j = 0; j < strArr.length; j++) {
            if (strArr[i] == strArr[j]) {
                if (index == -1) {
                    index = j;
                } else {
                    index = -1;
                    break;
                }
            }
        }
        
        if (index != -1) {
            break;
        }
    }
    
    return index;
}

/**
 * 描述
 * 输入一个整数数组，实现一个函数来调整该数组中数字的顺序，使得所有的奇数位于数组的前半部分，
 * 所有的偶数位于数组的后> > 半部分，并保证奇数和奇数，偶数和偶数之间的相对位置不变。
 * 
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 *
 * 
 * @param array int整型一维数组 
 * @return int整型一维数组
 */
public int[] reOrderArray (int[] array) {
    int leg = array.length;
    
    if (leg <= 1) {
        return array;
    }
    
    int oddCount = 0;
    for (int i = 0; i < leg; i++) {
        if (array[i] % 2 == 1) {
           oddCount++;
        }
    }
    
    if (oddCount == 0) {
        return array;
    }
    
  
    int[] newArr = new int[array.length];
    int oddNow = 0;
    for (int i = 0; i < leg; i++) {
        if (array[i] % 2 == 1) {
           newArr[oddNow] = array[i];
           oddNow++;
        } else {
            newArr[oddCount] = array[i];
            oddCount++;
        }
    }
    
    return newArr;
}

/**
 * 描述 :
 * 给定一个double类型的浮点数base和int类型的整数exponent。求base的exponent次方。
 * 保证base和exponent不同时为0。不得使用库函数，同时不需要考虑大数问题，也不用考虑小数点后面0的位数。
 */
public double Power(double base, int exponent) {
    double tempBase = base;
    if (exponent == 0) {
        return 1;
    }
    
    int loop = exponent > 0 ? exponent : -exponent;
    
    for (int i = 1; i < loop; i++) {
        tempBase = base * tempBase;
    }
    
    return exponent > 0 ? tempBase :  1 / tempBase;
}

/**
 *
 * 描述：
 * 给出一个仅包含字符'(',')','{','}','['和']',的字符串，判断给出的字符串是否是合法的括号序列
 * 括号必须以正确的顺序关闭，"()"和"()[]{}"都是合法的括号序列，但"(]"和"([)]"不合法。
 * 
 * 思路: 循环字符串，判断第一个字符，将对应的另一个字符放到堆栈中，如果下一个和当前出栈的字符串是否一致，
 * 如果一致则继续，如果不一致则返回false.
 *
 */
public boolean isValid (String s) {
    // write code here
    char[] sArray = s.toCharArray();
    Stack<Character> stack = new Stack<>();
     
    for (char alp : sArray) {
        if(alp == '('){
            stack.push(')');
        }else if(alp == '['){
            stack.push(']');
        }else if(alp == '{'){
            stack.push('}');
        }else if(stack.isEmpty() || stack.pop()!= alp){
            return false;
        }
    }
    
    return stack.isEmpty();
}

/**
 *
 * 计算除去空格的最长字符串长度
 * 例如: "the stop world";
 * 结果: 5
 */
public static void main(String[] args) {
    String str = "the stop world";
    char[] strArray = str.toCharArray();
    int maxCount = 0;
    int tempCount = 0;

    for (int i = 0; i < strArray.length; i++) {
        // 注意, 需要处理最后一个字符
        if (strArray[i] == ' ' || strArray.length - 1 == i) {
            if (strArray.length - 1 == i) {
                tempCount++;
            }

            maxCount = Math.max(tempCount, maxCount);
            tempCount = 0;
        } else {
            tempCount++;
        }
    }

    System.out.println(maxCount);
}

/**
 *
 * 描述
 * 输入一个链表的头节点，按链表从尾到头的顺序返回每个节点的值（用数组返回）。
 * 如输入{1,2,3}的链表如下图:
 *
 * 返回一个数组为[3,2,1]
 * 0 <= 链表长度 <= 10000
 */

public class Solution {
    public ArrayList<Integer> printListFromTailToHead(ListNode listNode) {
        ArrayList<Integer> list = new ArrayList<Integer>();
        while (listNode != null) {
            list.add(listNode.val);
            listNode = listNode.next;
        }
        
        Collections.reverse(list);
        
        return list;
    }
}

/**
 * 包含min函数的栈
 * 序号 stock 相关方法描述
 * 1. boolean empty() 测试堆栈是否为空。
 * 2. Object peek( ) 查看堆栈顶部的对象，但不从堆栈中移除它。
 * 3. Object pop( ) 移除堆栈顶部的对象，并作为此函数的值返回该对象。
 * 4. Object push(Object element） 把项压入堆栈顶部。
 * 5. int search(Object element) 返回对象在堆栈中的位置，以 1 为基数。
 */
import java.util.Stack;

public class Solution {
    // 入栈的所有对象
    private Stack<Integer> s1 = new Stack();
    // 每次入栈之后，获取peek()最高栈(最小值)，然后放入栈中
    private Stack<Integer> minStock = new Stack();
    
    public void push(int node) {
        // 入栈
        s1.push(node);
        // 如果最小栈对象为空，则放入，如果最小栈对象不为空，则取出栈顶（最小值）和入栈的值做比较，取出最小的值，放入栈顶。
        if (minStock.isEmpty()) {
            minStock.push(node);
        } else {
            minStock.push(Math.min(node, minStock.peek()));
        }
    }
    
    // 每次出栈，两个对象都是从后面出栈
    public void pop() {
        s1.pop();
        minStock.pop();
    }
    
    // 最近一次入栈的数据
    public int top() {
       return  s1.peek();
    }
    
    // 顶部为全栈最小值
    public int min() {
        return minStock.peek();
    }
}

/**
 *
 * [数组中出现次数超过一半的数字]
 * 
 * 思路: 出现一个新的数字，放入对应的MAP中，key是值，value是出现的次数，判断如果次数大于总数的一半以上，则退出，并确定该数字。
 *
 */
import java.util.*;

public class Solution {
    public int MoreThanHalfNum_Solution(int [] array) {
        int leg = array.length;
        if (leg < 1 || leg > 50000) {
            throw new RuntimeException("非法数组");
        }
        
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();
       
        int legHalf = leg / 2 + leg % 2;
        int temp = 0;
        
        for (int i = 0; i < leg; i++) {
            int temp1 = array[i];
            if (map.get(temp1) == null) {
                map.put(temp1, 1);

            } else {
                map.put(temp1, map.get(temp1) + 1);
            }
            
            if (map.get(temp1) == legHalf) {
                temp = temp1;
                break;
            }
            
        }
        
        return temp;
    }
}

/**
 * [数组中出现次数超过一半的数字]
 * 思路: 超过一半以上的数字，所以该数字的出现次数一定是最多之一，看一个相同的则加1，看见不相同的则减去1，这样如果是偶数可能是0，这样显示的是最后一次出现的那个数字，如果是基数，则最后的出现的次数一定大于1.
 *
 */
public int MoreThanHalfNum_Solution1(int [] array) {
    int voted = 1;
    int res = array[0];
    for(int i=1;i<array.length;i++){
        if(array[i] == res){
            voted++;
        }else{
            voted--;
            if(voted == 0){
                voted = 1;
                res = array[i];
            }
        }
    }
    return res;
}

/**
  * [字符串替换 - 方案1]

  * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
  *
  * 
  * @param s string字符串 
  * @return string字符串
  */
 public String replaceSpace (String s) {
     StringBuilder sb = new StringBuilder();
     
     for (int i = 0; i < s.length(); i++) {
         if (s.charAt(i) == ' ') {
             sb.append("%20");
         } else {
             sb.append(s.charAt(i));
         }
     }
     
     return sb.toString();
 }


/**
 *  [字符串替换 - 方案2]
 * 代码中的类名、方法名、参数名已经指定，请勿修改，直接返回方法规定的值即可
 * 
 * @param s string字符串 
 * @return string字符串
 */
public String replaceSpace (String s) {
    return s.replace(" ", "%20");
}

/**
 * 方案1
 * 
 * 在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，
 * 每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 *
 */
public boolean Find(int target, int [][] array) {
    boolean isHas = false;
    for (int i = 0; i < array.length; i++) {
        for (int j = 0 ; j < array[i].length; j++) {
            if (array[i][j] == target) {
                isHas = true;
                break;
            }
        }
        
        if (isHas) {
            break;
        }
    } 
    
    return isHas;
}

/**
 * 方案2
 * 
 * 在一个二维数组array中（每个一维数组的长度相同），每一行都按照从左到右递增的顺序排序，
 * 每一列都按照从上到下递增的顺序排序。请完成一个函数，输入这样的一个二维数组和一个整数，判断数组中是否含有该整数。
 *
 */
import java.util.*;
public class Solution {
    public boolean Find(int target, int [][] array) {
        boolean isHas = false;
        for (int i = 0; i < array.length; i++) {
            if (Arrays.binarySearch(array[i], target) >= 0) {
                isHas = true;
                break;
            }
        }
         
        return isHas;
    }
}

题目大多来自牛客网.