数组

• 题号122：买卖股票的最佳时机 II

class Solution {
    public int maxProfit(int[] prices) {
        int maxProfit = 0;
        int i = 0;
        //定义谷底
        int bottom = 0;
        //定义谷峰
        int top = 0;
        while(i < prices.length-1)
        {
            //数组第i的元素小于第i+1个元素的时候，跳出循环。
            //找到谷底
            while(i < prices.length-1 && prices[i] >= prices[i+1])
            {
                i++;
            }
            //给谷底赋值
            bottom = prices[i];
            //同理，找到谷峰
            while(i < prices.length-1 && prices[i] <= prices[i+1])
            {
                i++;
            }
            //给谷峰赋值
            top = prices[i];
            //将谷峰-谷底的利润赋值给总利润，i接着增加，找到下一组谷底和谷峰。
            maxProfit += top - bottom;
        }
        return maxProfit;
    }
}

题解：
假设给定了一个数组 [7, 1, 5, 3, 6, 4]
方法：峰谷法

我们只需要找到谷底和谷峰，如果我们错过一个峰值的话，我们的收益会减少，所以我们不能错过谷峰。

• 题号189：旋转数组
  两种方法：第一种：暴力法，一次将数组中的元素向右移动一个位置，移动k次。

class Solution {
    public void rotate(int[] nums, int k) {
        //定义数的前驱
        int previous = 0;
        int temp = 0;
        for(int i = 0 ; i < k ; i++)
        {
            //第一个for循环是需要移动k次
            //先将previous初始化为最后一个元素，即第一个元素的前驱
            previous = nums[nums.length-1];
            for (int j = 0 ; j < nums.length ; j++)
            {
                //从数组中的第一个元素开始
                //将这个数（假设为num）赋值为他前边的数，同时将num的值存在previous中，当作下一个数的前驱
                temp = nums[j];
                nums[j] = previous;
                previous = temp;
            }
        }
    }
}

第二种：数组法（较为简单）

class Solution {
    public void rotate(int[] nums, int k) {
        //只需要定义一个数组，和该数组大小相等
        int[] a = new int[nums.length];

        for(int i = 0 ; i < nums.length ; i++)
        {
            //原本下标为i的元素，我们将他放到了(i+k)%nums.length的位置上
            a[(i+k)%nums.length] = nums[i];
        }
        for(int i = 0 ; i < nums.length ; i++)
        {
            nums[i] = a[i];
        }

    }
}

• 题号217：存在重复元素
  两种方法：第一种：先将数组排序，相同的肯定相邻

class Solution {
    public boolean containsDuplicate(int[] nums) {
        Arrays.sort(nums);
        //注意i的取值需要小于length-1，否则数组会越界
        for(int i = 0 ; i < nums.length-1 ; i++)
        {
            if(nums[i] == nums[i+1])
                return true;
        }
        return false;
    }
}

第二种：暴力法（超时）

public static void main(String[] args) {
        int[] nums = {1,2,3,5};
        int temp = 0;
        //使用total来记录重复的数的个数
        int total = 0;

        for(int i = 0 ; i <nums.length ; i++)
        {
            total = 0;
            //将每个数取出来和数组中的数进行比较，其中和自己肯定相等，所以total肯定为1
            //若是还有相等的元素则total肯定大于2
            temp = nums[i];
            for(int j = 0 ; j < nums.length ; j++)
            {
                if(nums[j] == nums[i])
                {
                    total++;
                }
                if(total == 2)
                {
                    System.out.println("至少有两个重复的数");
                    return;
                }
            }
        }
        if(total == 1)
        {
            System.out.println("没有重复的数");
        }
}

• 题号136：只出现一次的数

class Solution {
    public int singleNumber(int[] nums) {
        int ans = nums[0];
        for(int i = 1 ;i<nums.length;i++)
        {
            ans = ans ^ nums[i];
        }
        return ans;
    }
}

题解：
使用异或的方法：
异或：1^1=0; 0001 ^ 0010 = 0011
也就是转换为二进制之后，不同则为1。
这道题使用异或，ans取值为第一个数，依次和后边的数进行异或，若是存在两个相等的数，这两个数的异或为0，最后只剩下一个单独出现的数字。

• 题号350:两个数组的交集Ⅱ
  解题思路：
  先将两个数组排序，然后使用双指针遍历

class Solution {
    public int[] intersect(int[] nums1, int[] nums2) {
	//对两个数组进行排序
        Arrays.sort(nums1);
        Arrays.sort(nums2);
	//i遍历nums1，j遍历nums2，m标记两个数组的交集，并记录交集的个数，存在nums1中
        int i = 0,j = 0, m = 0;

        while (i<nums1.length && j<nums2.length)
        {
            //这些if条件很好理解，哪个数组的数小，让他的指针往后移即可
            //若碰到相等，则是交集，存放在nums1数组中
            //相等的时候，两个数组的指针都往后移一位
            if(nums1[i] < nums2[j])
            {
                i++;
            }else if(nums1[i] > nums2[j])
            {
                j++;
            }else if(nums1[i] == nums2[j])
            {
                nums1[m]=nums1[i];
                m++;
                i++;
                j++;
            }
        }
        int[] a = new int[m];
        //m为交集的数量，再创建一个长度为m的数组，
        //我测试的时候，数组过长，后边都为0的话，不给通过
        //最后将nums1的数组的数移到新创建的数组中即可。
        for(int n=0;n<m;n++)
        {
            a[n]=nums1[n];
        }
        return a;
    }
}

• 题号66：加一
  解题思路：
  主要判断数组中9的情况。

1. 如果数组不全为9的话，从数组最后开始，加1，通过取余判断是否为9，直到不为9，返回该数组
2. 如果数组全为9的话，把数组每一位加1，最后创建一个多一个长度的数组，将第一位设置为1即可。

class Solution {
    public int[] plusOne(int[] digits) {

        for(int i = digits.length-1 ; i >= 0 ; i--)
        {
            digits[i] ++;
            digits[i] = digits[i]%10;
            if(digits[i] != 0)
                return digits;
        }
        int[] a = new int[digits.length+1];
        for(int i = 1 ;i <= digits.length ; i++)
        {
            a[i] = digits[i-1];
        }
        a[0] = 1;
        return a;

    }
}

• 题号283：移动零
  解题思路：
  遍历一次数组，判断 i 指针指向的数是否为0，
  用count记录为0的数，碰到0的话，count+1，如果前边存在0的话，让后边的不为0的数，放在(当前i指针的下标 - count（当前指针i的前边0的个数）)，也就是代码中的nums[i-count] = nums[i];

重点：
判断当前指针 i 前是否已经有0 ， 有则往前移 ，并且把该数设置为0， 没有则不动。

class Solution {
    public void moveZeroes(int[] nums) {

        int count = 0;
        for(int i = 0 ; i < nums.length ; i++){
            if(nums[i] == 0)
                count++;
            else if(count >0){
                nums[i-count] = nums[i];
                nums[i] = 0;
            }
        }

    }
}

• 题号1：两数之和
  解题思路：
  使用哈希表，先遍历一次将数组存在哈希表中
  再遍历一次查询哈希表中是否有(target - nums[i])的key值，如果有的话，且对应的下标不和 i 相等 ， 则返回new int[]{i,map.get(a)}

class Solution {
    public int[] twoSum(int[] nums, int target) {
        /*
          定义一个图，在存放数组的时候，用数组值做value，下标作为key
          方便后来获取下标可以直接使用map.get(value)
        */
        HashMap<Integer, Integer> map = new HashMap<>();
        for (int i = 0 ; i < nums.length ; i++)
        {
            map.put(nums[i],i);
        }
        for(int i = 0 ; i < nums.length ; i++)
        {
            int a = target - nums[i];
            if(map.containsKey(a) && i != map.get(a))
            {
                return new int[]{i,map.get(a)};
            }
        }
        throw new IllegalArgumentException("No two sum solution");
    }
}

（难度中等的空过去）
有效的数独：空
旋转图像：空

字符串

• 题号344：反转字符串
  解题思路：
  使用递归，用了两个指针left和right，当左指针大于右指针的时候，return推出递归。
  调用递归函数的时候，设置左右指针初值分别为：0,s.length-1。

class Solution {
    public void helper(char[] s , int left , int right){
        if(left >= right)
            return;
        char temp;
        temp = s[left];
        s[left] = s[right];
        s[right] = temp;
        helper(s,left+1,right-1);
    }
    public void reverseString(char[] s) {
        helper(s,0,s.length-1);
    }
}

• 题号7：整数反转
  解题思路：
  题目要求溢出的话，返回0，所以我们需要知道整数类型的范围是多少：
  取值范围：-2147483648 至 2147483647

我们需要在计算前判断是否溢出

class Solution {
    public int reverse(int x) {
        int rev = 0;
        while (x != 0) {
            int pop = x % 10;
            x /= 10;
            if (rev > Integer.MAX_VALUE/10 || (rev == Integer.MAX_VALUE / 10 && pop > 7)) return 0;
            if (rev < Integer.MIN_VALUE/10 || (rev == Integer.MIN_VALUE / 10 && pop < -8)) return 0;
            rev = rev * 10 + pop;
        }
        return rev;
    }
}

还有一种方法，在评论中看到的，很厉害：
他判断溢出的方法很厉害，用自己本身乘10，再除10，如果不是他本身的话，则这个数乘10之后会溢出。

class Solution {
    public int reverse(int x) {
        int ans = 0;
        while (x != 0)
        {
            if((ans * 10)/10 != ans)
            {
                ans = 0;
                break;
            }
            ans = ans * 10 + x % 10 ;
            x = x/10 ;
        }
        return ans;
    }
}

• 题号387：字符串中的第一个唯一字符
  解题思路：
  使用hashmap，用到的getOrDefault。

class Solution {
    public int firstUniqChar(String s) {

        //char的封装类是character, hashmap中需要使用封装类
        HashMap<Character,Integer> map = new HashMap<>();
        for (int i = 0 ; i < s.length() ; i++)
        {
            char a = s.charAt(i);
            map.put(a,map.getOrDefault(a,0)+1);
        }
        for (int i = 0 ; i < s.length() ; i++)
        {
            if(map.get(s.charAt(i)) == 1)
            {
                return i;
            }
        }
        return -1;

    }
}

• 题号242：有效的字母异位词
  字母异位词：也就是两个单词只有顺序不一样，每个字母出现的次数相等
  第一种方法：
  用一个长度为26的数组记录每个字母出现的次数
  不需要遍历两次：遍历s的时候++，遍历t的时候–，只需要遍历一次就可以。

class Solution {
    public boolean isAnagram(String s, String t) {
      /*
        1.两个字符串长度肯定相等
      */
        if(s.length() != t.length())
            return false;

        int[] a = new int[26];

        for(int i = 0 ; i < s. length() ; i++)
        {
            a[s.charAt(i)-'a']++;
            a[t.charAt(i)-'a']--;
        }
        for(int i = 0 ; i < a.length ; i++)
        {
            if(a[i] != 0)
                return false;
        }
        return true;
    }
}

第二种方法：
使用到了排序，先将两个字符串转换为char类型的数组，在进行排序，最后遍历看是否有不相等的。

class Solution {
    public boolean isAnagram(String s, String t) {

        if(s.length() != t.length())
            return false;

        char[] str1 = s.toCharArray();
        char[] str2 = t.toCharArray();

        Arrays.sort(str1);
        Arrays.sort(str2);

        for(int i = 0 ; i < str1.length ; i++)
        {
            if(str1[i] != str2[i])
                return false;
        }
        return true;

    }
}

• 题号125：验证回文字符串

class Solution {
    public boolean isPalindrome(String s) {
        /*1.将字符串转换为char数组*/
        char[] chars = s.toCharArray();
        int count = 0 ;
        /*2.将除了字母和数字意外的字符过滤掉*/
        for (int i = 0 ; i < chars.length ; i++)
        {
            if((chars[i] >= '0' && chars[i] <= '9') || (chars[i] >= 'a' && chars[i] <= 'z') )
            {
                chars[count] = chars[i];
                count++;
            }else if((chars[i]>='A' && chars[i]<='Z')){
                chars[count] = (char)(chars[i] - 'A' + 'a');
                count++;
            }
        }
        
        /*3.count作下标，需要减1*/
        count--;
        int start = 0;
        
        /*4.判断是否是回文*/
        while(start < count)
        {
            if(chars[start++] != chars[count--])
                return false;
        }
        return true;
    }
}

• 题号8：字符串转换整数
  思路在代码的注释中

class Solution {
    public int myAtoi(String str) {
         /*
        解题思路：
                1. 首先判断首位是什么
                我们需要弄清首位可能的取值为什么： ①'+'  ② '-'  ③0~9的数字  ④0~9以外的任何字符   ⑤空格' '
                2.判断完首位的取值之后就很好办了，我们将变量i定义为全局变量
                  如果首位是 + 或 - 的话，那么让i++，在进行下一次遍历的时候，可以直接从+ 或 - 之后接着进行遍历
                3.将符号存储在变量fh中。
        */

        /*1.转换成数组*/
        char[] ch = str.toCharArray();
        /*2.遍历数组*/
        int i = 0;
        int fh = 1;
        int length = ch.length;
        /*先判断第一位是什么*/
        for ( ; i < length ; i++)
        {
            /*如果是空格的话，跳过*/
            if( ch[i] == ' ')
                continue;
            else{
                /*如果不是空格的话，再进行分类*/
                if(ch[i] == '+')
                {
                    fh = 1;
                    i++;
                    break;
                }
                if(ch[i] == '-')
                {
                    fh = -1;
                    i++;
                    break;
                }
                if(ch[i] < '0' || ch[i] > '9')
                {
                    return 0;
                }
                /*这个break针对的是 ('0' < ch[i] < '9')的情况。*/
                break;
            }
        }
        /*此时若有符号，i=1,若没有符号，i=0*/
        int pop = 0;
        int res = 0;
        for ( ; i < length ; i++)
        {
            if(ch[i] < '0' || ch[i] > '9')
                return res;
            pop = fh * (ch[i] - '0');
            if (res > Integer.MAX_VALUE/10 || (res == Integer.MAX_VALUE/10 && pop > 7))
                return 2147483647;
            if (res < Integer.MIN_VALUE/10 || (res == Integer.MIN_VALUE/10 && pop < -8))
                return -2147483648;
            res = res * 10 + pop;
        }
        return res;

    }
}

• 题号14：最长公共前缀
  第一种方法：使用暴力法
  击败了 5% 的用户 /(ㄒoㄒ)/~~

class Solution {
    public String longestCommonPrefix(String[] strs) {

        /*先判断字符串数组是否为空，为空直接返回*/
        if(strs.length == 0 || strs == null)
            return "";

        /*
            解题思路： 求出公共前缀，再拿这个公共前缀和后边比较，找出公共前缀
                      MaxPro(MaxPro(MaxPro(strs[0],strs[1]),strs[2]),strs[3])......
        */
        
        String res = "";
        String a = "";
        a = strs[0];
        /*将数组中第一个字符串赋值给 a ，然后用这个a与第二个字符串比较，最后将a与第二个的公共前缀，再次赋值给a，以此类推*/
        for (int i = 1 ; i < strs.length ; i++)
        {

            int m = 0;
            int n = 0;

            /* m : 用来遍历每一个字符串中的每个字符,且小于需要遍历的字符串的长度 */
            while (i<strs.length && m < a.length() && m < strs[i].length() && (a.charAt(m) == strs[i].charAt(m)) )
            {
                res += a.charAt(m)+"";
                m++;
            }

            a = res;
            res = "";

        }
        return a;
    }
}

• 求二进制和（主要是看如何进位）

class Solution {
    public String addBinary(String a, String b) {
       StringBuilder res = new StringBuilder();
       int cal = 0;
       for(int i = a.length() - 1, j = b.length() - 1;i >= 0 || j >= 0; i--, j--) {
           int sum = cal;
           sum += i >= 0 ? a.charAt(i) - '0' : 0 ;
           sum += j >= 0 ? b.charAt(j) - '0' : 0 ;
           res.append(sum%2);
           cal = sum / 2;
       }
       res.append(cal == 1?cal:"");
       return res.reverse().toString();
    }
}

• 反转字符串里的单词：
  用到了strip()方法
  注意最后返回的时候需要加上前边的第一个单词

class Solution {
    public String reverseWords(String s) {
        //去掉字符串两端的空格
        s = s.strip();
        StringBuilder res = new StringBuilder();
        int i = s.length() -1 , j = s.length();
        while(i > 0)
        {
            if(s.charAt(i) == ' ')
            {
                res.append(s.substring(i+1,j));
                res.append(" ");
            
                while(s.charAt(i) == ' ')
                    i--;
                j = i + 1;
            }
            i--;
        }
        return res.append(s.substring(0,j)).toString();
    }
}