1
2
3
4
5
6
7
8
9
10
11
12
13
14
int removeDuplicates(int* nums, int numsSize){
    if(numsSize==0){
        return 0;
    }
    int i = 0,j;
    for(j=1; j<numsSize; j++){
        if(nums[j]!=nums[i]){
            i++;
            nums[i] = nums[j];
        }
    }
    return i+1;
}

1
2
3
4
5
6
7
8
9
10
11
int removeElement(int* nums, int numsSize, int val){
    int i = 0,j;
    for(j=0; j<numsSize; j++){
        if(nums[j]!=val){
            nums[i]=nums[j]; //nums[i]为新数组
            i++;
        }
    }
    return i;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
int maxSubArray(int* nums, int numsSize){
    int subsum = 0, maxsum = -2147483648;
    
    for(int i = 0; i < numsSize; i ++)
    {
        subsum += nums[i];
        if(subsum > maxsum)
        {
            maxsum = subsum;
        }
        if(subsum < 0) subsum = 0;
    }
    return maxsum;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* plusOne(int* digits, int digitsSize, int* returnSize){
    if (digits == NULL && digitsSize == 0){ //传参检查
        *returnSize = 0;
        return NULL;
    }
    int flag = 0; //进位标志
    int i = digitsSize - 1; //数组下标
    int* res = (int*)malloc((digitsSize+1) * sizeof(int));
    //申请多一位空间（最高位产生进位）
    digits[i] = digits[i] + 1;//最低位 + 1

    //特别注意这里改变了源数据，这点不太好，值得改进
    for (; i >= 0; --i){
        res[i] = digits[i] + flag;
        if (res[i] >= 10){//判断有无进位
            res[i] = res[i]%10;
            flag = 1;
        }
        else{
            flag = 0;
        }
    }

    *returnSize = digitsSize + flag;
    if (flag != 0){ //最高位产生了进位
        int tmp;
        int mid = flag; //进位数 赋给 数组第一位（新的最高位）
        for (i = 0; i <= digitsSize; ++i){
            tmp = res[i]; //保存当前值
            res[i] = mid;
            mid = tmp; //移动至下一个位置
        }
    }
    return res;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
//由后向前排

void merge(int* nums1, int nums1Size, int m, int* nums2, int nums2Size, int n){

    int tag1=m-1;       //nums1最后一个元素数组下标
    int tag2=n-1;       //nums2最后一个元素数组下标
    int end=m+n-1;      //目标nums1处理下标
    while(end>-1){
        if(tag1<0){     //处理边界问题，防止nums[tag]数组越界
            nums1[end]=nums2[tag2];
            tag2--;
        }
        else if(tag2<0){
            nums1[end]=nums1[tag1];
            tag1--;
        }
        else if(nums1[tag1]>nums2[tag2]){
            nums1[end]=nums1[tag1];
            tag1--;
        }
        else{
            nums1[end]=nums2[tag2];
            tag2--;
        }
        end--;
    }
}

1
2
3
4
5
6
7
8
class Solution {
  public void merge(int[] nums1, int m, int[] nums2, int n) {
    System.arraycopy(nums2, 0, nums1, m, n); //将俩个数组合并
    Arrays.sort(nums1); //对合并后的新数组排序  缺点：没考虑俩个旧数组已经是有序的
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
int** generate(int numRows, int* returnSize, int** returnColumnSizes){
    *returnSize = numRows;
    *returnColumnSizes = (int*)malloc(4*numRows);
    
    int i,j;
    int **ret = (int**)malloc(sizeof(int*)*numRows); //声明

    for(i=0; i<numRows; i++){
        (*returnColumnSizes)[i] = i+1; //初始化
        ret[i] = (int*)malloc(i*4+4);
        ret[i][0] = 1;
        ret[i][i] = 1;
    }

    for(i=2; i<numRows; i++){
        for(j=1; j<i; j++){
            ret[i][j] = ret[i-1][j-1] + ret[i-1][j]; //计算
        }
    }
    
    return ret;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
//申请一行的空间，从后往前处理就不需要考虑数组元素被处理时被覆盖的问题。

int* getRow(int rowIndex, int* returnSize){
    * returnSize = rowIndex + 1; //第k行有k个元素
    int* array = (int *)malloc(sizeof(int) * (rowIndex+1));
    for(int i=0; i<rowIndex+1; i++){
        array[i]=1; //行末尾为1
        for(int j=i-1; j>0; j--){ //每一行的更新过程
            array[j] = array[j] + array[j-1];
        }
        array[0] = 1;
    }
    return array;
}

1
2
3
4
5
6
7
8
bool isOneBitCharacter(int* bits, int bitsSize){
    int i = 0;
    while(i<bitsSize-1){
        i += bits[i] + 1;
    }
    return i == bitsSize - 1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public List<Integer> addToArrayForm(int[] A, int K) {
        int N = A.length;
        int cur = K;
        List<Integer> ans = new ArrayList();

        int i = N;
        while (--i >= 0 || cur > 0) {
            if (i >= 0)
                cur += A[i];
            ans.add(cur % 10);
            cur /= 10;
        }

        Collections.reverse(ans);
        return ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11
public class Solution {
    public int arrayPairSum(int[] nums) {
        Arrays.sort(nums);
        int sum = 0;
        for (int i = 0; i < nums.length; i += 2) {
            sum += nums[i];
        }
        return sum;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public double average(int[] salary) {
        double sum = 0;

        Arrays.sort(salary);

        for(int i=1; i<salary.length-1; i++){
            sum += salary[i];
        }

        return sum/(salary.length-2);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
public class Solution {
    public int maxProfit(int prices[]) {
        int maxprofit = 0; //存储最大利润
        for (int i = 0; i < prices.length - 1; i++) {
            for (int j = i + 1; j < prices.length; j++) { //保证买卖时间的先后顺序
                int profit = prices[j] - prices[i]; //计算第i天后的每一天和第i天价格的差值
                if (profit > maxprofit) //找出最大差值
                    maxprofit = profit;
            }
        }
        return maxprofit;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int maxProfit(int prices[]) {
        int minprice = Integer.MAX_VALUE;
        int maxprofit = 0;
        for (int i = 0; i < prices.length; i++) {
            if (prices[i] < minprice){
                minprice = prices[i];
             }
            else if (prices[i] - minprice > maxprofit){
                maxprofit = prices[i] - minprice;
            }
        }
        return maxprofit;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int maxProfit(int[] prices) { //主
        return calculate(prices, 0);
    }

    public int calculate(int prices[], int s) { 
        if (s >= prices.length) //数组长度小于s(s=0时数组为空) 没有股票 利润为0
            return 0;
        int max = 0; //多次交易后最终的最大利润
        for (int start = s; start < prices.length; start++) { //遍历数组
            int maxprofit = 0; //定义一次交易后的最大利润
            for (int i = start + 1; i < prices.length; i++) { //遍历买入股票后的每一天
                if (prices[start] < prices[i]) { //第i天股票价格大于买入时价格
                    int profit = calculate(prices, i + 1) + prices[i] - prices[start]; //计算此时利润
                    if (profit > maxprofit) //与之前的利润作比较 求出每一次交易最大利润
                        maxprofit = profit;
                }
            }
            if (maxprofit > max) //多次交易后的最大利润
                max = maxprofit;
        }
        return max;
    }
    
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int maxProfit(int[] prices) {
        int i = 0;
        int valley = prices[0]; //峰
        int peak = prices[0]; //谷
        int maxprofit = 0; 

        while (i < prices.length - 1) { //遍历数组
            while (i < prices.length - 1 && prices[i] >= prices[i + 1]){ //找波谷
                i++;
            }
            valley = prices[i]; //将所有的波谷值相加
            while (i < prices.length - 1 && prices[i] <= prices[i + 1]){ //找波峰
                i++;
            }
            peak = prices[i]; //将所有的波峰值相加

            maxprofit += peak - valley;
        }

        return maxprofit;
    }
}

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public int maxProfit(int[] prices) {
        int maxprofit = 0;
        for (int i = 1; i < prices.length; i++) {
            if (prices[i] > prices[i - 1])
                maxprofit += prices[i] - prices[i - 1];
        }
        return maxprofit;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
bool* prefixesDivBy5(int* A, int ASize, int* returnSize)
{
    int temp = 0;
    *returnSize = ASize;

    bool* ret = (bool*)malloc(ASize * sizeof(bool));

    for (int i = 0; i < ASize; i++) {
        temp = (temp << 1) + A[i]; //换算成十进制
        temp = temp % 5;
        if (temp == 0) { //判断是否能被5整除
            ret[i] = true;
        } else {
            ret[i] = false;
        }
    }

    return ret;
}

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public boolean canMakeArithmeticProgression(int[] arr) {
        Arrays.sort(arr);
        for (int i = 1; i < arr.length - 1; ++i) {
            if (arr[i] * 2 != arr[i - 1] + arr[i + 1]) {
                return false;
            }
        }
        return true;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public boolean canPlaceFlowers(int[] flowerbed, int n) {
        int i = 0, count = 0;

        while (i < flowerbed.length) { //遍历数组
            if (flowerbed[i] == 0 && (i == 0 || flowerbed[i - 1] == 0) && (i == flowerbed.length - 1 || flowerbed[i + 1] == 0)) { //判断能否种花
                flowerbed[i] = 1;
                count++;
            }
            i++;
        }

        return count >= n;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
class Solution {
    public int countNegatives(int[][] grid) {

        int count = 0, m = grid.length, n = grid[0].length; //m:有多少组，n:一组有多少个数

        for (int i = 0; i < m; i++) { //一组一组遍历
            int[] row = grid[i];
            if (row[n - 1] >= 0){ 
                continue;
            } // 整行非负，跳过
            if (row[0] < 0) { // 整行负数
                count += (m - i) * n; // 后面的行也计入
                break; // 无需再继续遍历
            }
            int first = _binarySearch(row); // 当前行二分查找第一个小于 0 的数的索引
            count += n - first;
        }

        return count;
    }

    // 查找第一个小于 0 的数的索引
    private int _binarySearch(int[] arr) {
        int begin = 0, end = arr.length;

        while (begin < end) {
            int mid = begin + ((end - begin) >> 1);
            if (arr[mid] >= 0) {
                begin = mid + 1;
            }
            else { // 负数之后，还要再判断前一个不是负数（不太懂）
                if (arr[mid - 1] >= 0) {
                    return mid;
                }
                end = mid;
            }
        }

        return begin;
    }
    
}

1
2
3
4
5
6
7
8
9
public class Solution {
    public int fib(int N) {
        if (N <= 1) {
            return N;
        }
        return fib(N-1) + fib(N-2);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] sortArrayByParity(int[] A) {
        int[] ans = new int[A.length];
        int t = 0;

        //第一遍扫描 输出偶数
        for (int i = 0; i < A.length; ++i)
            if (A[i] % 2 == 0)
                ans[t++] = A[i];

        //第二遍扫描 输出奇数
        for (int i = 0; i < A.length; ++i)
            if (A[i] % 2 == 1)
                ans[t++] = A[i];

        return ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    public int[] sortArrayByParityII(int[] A) {
        int N = A.length;
        int[] ans = new int[N];

        int t = 0;
        for (int x: A){
            if (x % 2 == 0) {
                ans[t] = x;
                t += 2;
            }
        }

        t = 1;
        for (int x: A){
            if (x % 2 != 0) {
                ans[t] = x;
                t += 2;
            }
        }

        return ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] sortArrayByParityII(int[] A) {
        int j = 1;
        for (int i = 0; i < A.length; i += 2)
            if (A[i] % 2 != 0) {
                while (A[j] % 2 != 0)
                    j += 2;

                // Swap A[i] and A[j]
                int tmp = A[i];
                A[i] = A[j];
                A[j] = tmp;
            }

        return A;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int[] sortedSquares(int[] A) {
        int N = A.length;
        int[] ans = new int[N];
        for (int i = 0; i < N; ++i)
            ans[i] = A[i] * A[i];

        Arrays.sort(ans);
        return ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
       public int heightChecker(int[] heights) {
        // 值的范围是1 <= heights[i] <= 100，因此需要1,2,3,...,99,100，共101个桶
        int[] arr = new int[101];
        // 遍历数组heights，计算每个桶中有多少个元素，也就是数组heights中有多少个1，多少个2，。。。，多少个100
        // 将这101个桶中的元素，一个一个桶地取出来，元素就是有序的
        for (int height : heights) {
            arr[height]++;
        }

        int count = 0;
        for (int i = 1, j = 0; i < arr.length; i++) {
            // arr[i]，i就是桶中存放的元素的值，arr[i]是元素的个数
            // arr[i]-- 就是每次取出一个，一直取到没有元素，成为空桶
            while (arr[i]-- > 0) {
                // 从桶中取出元素时，元素的排列顺序就是非递减的，然后与heights中的元素比较，如果不同，计算器就加1
                if (heights[j++] != i) count++;
            }
        }
        return count;
    }
}

1
2
3
4
5
6
7
class Solution {
    public int majorityElement(int[] nums) {
        Arrays.sort(nums);
        return nums[nums.length/2];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
class Solution {
    public List<String> commonChars(String[] A) {
        //记录当前处理到的单词每个字符的出现次数
        int[] hash = new int[26];
        //记录已处理过的所有单词共有字符的出现次数
        int[] temp = new int[26];

        for(int i = 0; i < 26; i++)
            //每个字符出现次数最多100次，因为题目有限制每个单词最多含有100字符
            hash[i] = 100;

        //用temp更新hash
        for(int i = 0; i < A.length; i++) //每个单词
        {
            for(char c : A[i].toCharArray()) //toCharArray()将字符串转换为字符数组
                temp[c - 'a']++; //a b c d->0 1 2 3 
            for(int j = 0; j < 26; j++) //单词里的每个字母
            {
                hash[j] = Math.min(hash[j], temp[j]);
                temp[j] = 0;
            }
        }

        List<String> list = new LinkedList<String>();
        for(int i = 0; i < 26; i++)
        {
            while(hash[i] > 0)
            {
                list.add(String.valueOf((char)(i + 'a')));
                hash[i]--;
            }
        }

        return list;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public class Solution {
    public void rotate(int[] nums, int k) {
        int temp, previous;
        //向右移动k次
        for (int i = 0; i < k; i++) {
            //存储数组的最后一个元素
            previous = nums[nums.length - 1]; 
            //交换第一个和最后一个元素
            for (int j = 0; j < nums.length; j++) {
                temp = nums[j];
                nums[j] = previous;
                previous = temp;
            }
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public boolean containsDuplicate(int[] nums) {
    Arrays.sort(nums);
    for (int i = 0; i < nums.length - 1; ++i) {
        if (nums[i] == nums[i + 1]) return true;
    }
    return false;
}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public boolean containsNearbyDuplicate(int[] nums, int k) {
    Set<Integer> set = new HashSet<>();
    for (int i = 0; i < nums.length; ++i) {
        if (set.contains(nums[i])) return true;
        set.add(nums[i]);
        if (set.size() > k) {
            set.remove(nums[i - k]);
        }
    }
    return false;
}

}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int missingNumber(int[] nums) {
        Arrays.sort(nums);

        // 判断 n 是否出现在末位
        if (nums[nums.length-1] != nums.length) {
            return nums.length;
        }
        // 判断 0 是否出现在首位
        else if (nums[0] != 0) {
            return 0;
        }

        // 此时缺失的数字一定在 (0, n) 中
        for (int i = 1; i < nums.length; i++) {
            int expectedNum = nums[i-1] + 1;
            if (nums[i] != expectedNum) {
                return expectedNum;
            }
        }

        // 未缺失任何数字（保证函数有返回值）
        return -1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
	public void moveZeroes(int[] nums) {
		if(nums==null) {
			return;
		}
		//第一次遍历的时候，j指针记录非0的个数，只要是非0的统统都赋给nums[j]
		int j = 0;
		for(int i=0;i<nums.length;++i) {
			if(nums[i]!=0) {
				nums[j++] = nums[i];
			}
		}
		//非0元素统计完了，剩下的都是0了
		//所以第二次遍历把末尾的元素都赋为0即可
		for(int i=j;i<nums.length;++i) {
			nums[i] = 0;
		}
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
	public List<Integer> findDisappearedNumbers(int[] nums) {
		List<Integer> res = new ArrayList<Integer>();
		//第一遍扫描，根据数组的值找到对应的下标，比如3对应下标2
		//将arr[i]设置成负数
		for(int i=0;i<nums.length;++i) {
            //abs()绝对值
			int index = Math.abs(nums[i])-1;
			if(nums[index]>0) {
				nums[index] *= -1;
			}
		}
		//第二遍扫描，找到所有非负数，非负数所在的下标+1，即为缺失的数字
		for(int i=1;i<=nums.length;++i) {
			if(nums[i-1]>0) {
				res.add(i);
			}
		}
		return res;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
  public int findMaxConsecutiveOnes(int[] nums) {
    int count = 0;
    int maxCount = 0;
    for(int i = 0; i < nums.length; i++) {
      if(nums[i] == 1) {
        // Increment the count of 1's by one.
        count += 1;
      } else {
        // Find the maximum till now.
        maxCount = Math.max(maxCount, count);
        // Reset count of 1.
        count = 0;
      }
    }
    return Math.max(maxCount, count);
  }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
    public int findUnsortedSubarray(int[] nums) {
        int[] snums = nums.clone();
        Arrays.sort(snums);
        int start = snums.length, end = 0;
        for (int i = 0; i < snums.length; i++) {
            if (snums[i] != nums[i]) {
                start = Math.min(start, i);
                end = Math.max(end, i);
            }
        }
        return (end - start >= 0 ? end - start + 1 : 0);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
int thirdMax(int* nums, int numsSize){
    int i;
    int one,two,three;
    int min = nums[0];
    //找最小值
    for(i=0;i<numsSize;i++){    
        if(nums[i]<=min)
           min = nums[i];
    }
    one  = two = three = min;
    for(i=0;i<numsSize;i++){
        //注意赋值顺序   一层层往上传值 最大的值给one 下面的类似
        if(nums[i]>one){      
            three = two;
            two = one;
            one = nums[i];
        }
        else if(nums[i] > two && nums[i] != one){
            three = two;
            two = nums[i];
        }
        else if(nums[i] > three && nums[i] != two && nums[i] != one){
            three = nums[i];
        }
    }                            
    //当三个层次的最值里面有两个值相等时 说明没有第三大的值 直接返回最大值
    if(three == two || two == one){    
        return one;
    }
    return three;
}

1
2
3
4
5
6
7
8
public class Solution {
    public int maximumProduct(int[] nums) {
        Arrays.sort(nums);
        return Math.max(nums[0] * nums[1] * nums[nums.length - 1], nums[nums.length - 1] * nums[nums.length - 2] * nums[nums.length - 3]);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Solution {
    public int findLengthOfLCIS(int[] nums) {
        int ans = 0, anchor = 0;

        for (int i = 0; i < nums.length; ++i) {
            if (i > 0 && nums[i-1] >= nums[i]) anchor = i;
            
            ans = Math.max(ans, i - anchor + 1);
        }

        return ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution {
    public boolean checkPossibility(int[] nums) {
        int cnt = 0;                                              
        for(int i = 1; i < nums.length && cnt<=1 ; i++){
            if(nums[i-1] > nums[i]){
                cnt++;
                if(i-2>=0 && nums[i-2]>nums[i]){
                    nums[i] = nums[i-1];
                } 
            }
        }

        return cnt<=1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean isMonotonic(int[] A) { //主
        return increasing(A) || decreasing(A);
    }
    //单增
    public boolean increasing(int[] A) {
        for (int i = 0; i < A.length - 1; ++i)
            if (A[i] > A[i+1]) return false;
        return true;
    }
    //单减
    public boolean decreasing(int[] A) {
        for (int i = 0; i < A.length - 1; ++i)
            if (A[i] < A[i+1]) return false;
        return true;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean isMonotonic(int[] A) {
        int store = 0;
        for (int i = 0; i < A.length - 1; ++i) {
            //若A[i]=A[i+1]，返回0；若A[i]>a[i+1],返回>0的值
            int c = Integer.compare(A[i], A[i+1]);
            if (c != 0) {
                if (c != store && store != 0)
                    return false;
                store = c;
            }
        }

        return true;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* relativeSortArray(int* arr1, int arr1Size, int* arr2, int arr2Size, int* returnSize){
    int arr[1001]={0};
    int i,j=0;
    //记录arr1数字出现的次数次数
    for(i=0;i<arr1Size;i++){
        arr[arr1[i]]++;
    }
    //找到在arr2和arr1都出现的数字
    for(i=0;i<arr2Size;i++){
        while(arr[arr2[i]]>0){
            arr1[j]=arr2[i];
            j++;
            arr[arr2[i]]--;
        }
    }
    //找arr1有，arr2没有的
    for(i=0;i<1001;i++){
        while(arr[i]>0){
            arr1[j++]=i;
            arr[i]--;
        }
    }
    *returnSize=arr1Size;
    return arr1;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
public class Solution {
	public double findMaxAverage(int[] nums, int k) {
		int[] sum = new int[nums.length];
		sum[0] = nums[0];

		for (int i = 1; i < nums.length; i++){
		    sum[i] = sum[i - 1] + nums[i];
        }
        
		double res = sum[k - 1] * 1.0 / k;
		for (int i = k; i < nums.length; i++) {
			res = Math.max(res, (sum[i] - sum[i - k]) * 1.0 / k);
		}

		return res;
	}
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public List<List<Integer>> minimumAbsDifference(int[] arr) {
        Arrays.sort(arr);
        List<List<Integer>> res = new LinkedList<>();
        int min = 99999999;
        
        for (int i = 1; i < arr.length; i++) {
            int tmp = arr[i] - arr[i - 1];
            // 找到新的最小差，清空原有结果
            if (tmp < min) {
                min = tmp;
                res.clear();
            }
            // 如果是最小差，记录
            if (tmp == min) {
                List<Integer> item = new ArrayList<>(2);
                item.add(arr[i - 1]);
                item.add(arr[i]);
                res.add(item);
            }
        }
        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int[] shuffle(int[] nums, int n) {
        //1、新建一个数组用来存放排好的数
		 int[] arry = new int[nums.length];
		 
		 //2、用for来排好
		 int j =0; 
		 //循环 nums/2 次 
		 for(int i = 0 ; i < nums.length/2 ; i++){
			 arry[j++] = nums[i];  //第一个位置放 第 i个元素，每次j++自增1
			 
			 arry[j++] = nums[n +i]; //从第n+i 就是从一半开始到数组的最后
		 }
		 //3、存到新数组里
		return arry;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int pivotIndex(int[] nums) {
        int sum = 0, leftsum = 0;

        for (int x: nums) sum += x;
        
        for (int i = 0; i < nums.length; ++i) {
            if (leftsum == sum - leftsum - nums[i]) return i;

            leftsum += nums[i];
        }

        return -1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
class Solution {
    public int findLucky(int[] arr) {
        int temp = -1;
        int len = 1;
        Arrays.sort(arr);
        //数组长度为1
         if(arr.length == 1){
                if(arr[0] == 1){
                    return 1;
                }else{
                    return -1;
                }
        }
        for(int i = 0;i<arr.length-1;i++){
            if(arr[i] == arr[i+1]){
                    len++;
                    if(len == arr[i] && i == arr.length-2){
                        temp = len;
                    }
            }else{
                if(len == arr[i]){
                    temp = len;
                }
                len = 1;
            }         
        } 
        return temp;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
class Solution {
    public int countLargestGroup(int n) {

        int ans = 0, max = 1;
        // 统计数位和有多少
        int[] count = new int[n +  1];
        //计算1-n各个元素的数位和，例如数字i的数位和是sum[i / 10] + i % 10
        int[] sum = new int[n + 1]; 
        
        for(int i = 1; i <= n; i++){
            sum[i] = sum[i / 10] + i % 10;
            count[sum[i]]++;
            if(count[sum[i]] > max) 
                max = count[sum[i]];
        }

        for(int num : count) ans += num == max ? 1 : 0;
        
        return ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
class Solution {
    public boolean canThreePartsEqualSum(int[] A) {
        int sum = 0;
        for(int i : A){
            sum += i;
        }
        if(sum%3 != 0){
            // 总和不是3的倍数，直接返回false
            return false;
        }

        // 使用双指针,从数组两头开始一起找，节约时间
        int left = 0;
        int leftSum = A[left];
        int right = A.length - 1;
        int rightSum = A[right];

        // 使用left + 1 < right 的原因，防止只能将数组分成两个部分
        // 例如：[1,-1,1,-1]，使用left < right作为判断条件就会出错
        while(left + 1 < right){
            if(leftSum == sum/3 && rightSum == sum/3){
                // 左右两边都等于 sum/3 ，中间也一定等于
                return true;
            }
            if(leftSum != sum/3){
                // left = 0赋予了初值，应该先left++，在leftSum += A[left];
                leftSum += A[++left];
            }
            if(rightSum != sum/3){
                // right = A.length - 1 赋予了初值，应该先right--，在rightSum += A[right];
                rightSum += A[--right];
            }
        }
        return false;  
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
class Solution {
    public int findTheDistanceValue(int[] arr1, int[] arr2, int d) {
                int count =0;
                
                for(int i=0;i<arr1.length;i++){
                    boolean flag = true;
                    for(int j =0;j<arr2.length;j++){
                        int value= Math.abs(arr1[i]-arr2[j]);
                        if(value<=d){   
                            flag = false;
                            break;
                        }
                    }
                    if(flag){
                        count++;
                    }
                }

                return count;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int countGoodTriplets(int[] arr, int a, int b, int c) {
        int n = arr.length, cnt = 0;

        for (int i = 0; i < n; ++i) {
            for (int j = i + 1; j < n; ++j) {
                for (int k = j + 1; k < n; ++k) {
                    if (Math.abs(arr[i] - arr[j]) <= a && Math.abs(arr[j] - arr[k]) <= b && Math.abs(arr[i] - arr[k]) <= c) {
                        ++cnt;
                    }
                }
            }
        }
        
        return cnt;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int[] replaceElements(int[] arr) {
        if (arr.length == 0) return arr;
        
        int length = arr.length;
        int max = arr[length - 1];
        arr[--length] = -1;

        while (length > 0) {
            int cur = arr[length - 1];
            arr[--length] = max;
            max = Math.max(max, cur);
        }

        return arr;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
class Solution {
    public int[] sumEvenAfterQueries(int[] A, int[][] queries) {
        int S = 0;
        for (int x: A)
            if (x % 2 == 0)
                S += x;

        int[] ans = new int[queries.length];

        for (int i = 0; i < queries.length; ++i) {
            int val = queries[i][0], index = queries[i][1];
            if (A[index] % 2 == 0) S -= A[index];
            A[index] += val;
            if (A[index] % 2 == 0) S += A[index];
            ans[i] = S;
        }

        return ans;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
void duplicateZeros(int* arr, int arrSize){
    int i;
    int j;
    
    for(i = 0; i < arrSize; i++) {
        if(arr[i] == 0) {
            for(j = arrSize - 1; j > i; j--) {
                arr[j] = arr[j - 1];             
            }
            //不懂i++作用
            i++;            
        }
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public int[] sumZero(int n) {
        int[] arr = new int[n];

        for (int i = 0; i < n / 2; i++) {
            arr[i] = i + 1;
            arr[n - i - 1] = -arr[i];
        }
        
        return arr;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public int[] smallerNumbersThanCurrent(int[] nums) {
        int[] s1 = new int [nums.length]; //用来存放统计个数
		int ans =0; //计数
		int t=0;
		for(int i = 0 ; i < nums.length ; i++){
			ans =0 ; // 每次循环都要 归0
			for(int j = 0 ; j < nums.length ;j++){
				if(nums[j] < nums[i] && j != i){
					ans++;
				}
			}
			s1[t++] = ans; //t++ 用于每一位的统计的数位置
		}
		//System.out.println(Arrays.toString(s1));
	
		return s1;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
class Solution {
    public int[] arrayRankTransform(int[] arr) {
        int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
        //找最大最小值
        for(int num : arr){                        
            if(num < min) min = num;
            if(num > max) max = num;
        }
        //最多存在 max-min+1 个不同元素
        int[] count = new int[max-min+1];    
        //初次遍历，找到存在的元素
        for(int num : arr) count[num-min] = 1;    
        //二次遍历，对存在的元素进行排序
        for(int i = 1; i < count.length; i++){     
            count[i] = count[i-1] + count[i];
        }

        int[] res = new int[arr.length];
        for(int i = 0; i < arr.length; i++){
            //count数组存放着对应的排序后索引
            res[i] = count[arr[i]-min];            
        }
        
        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public List<List<Integer>> largeGroupPositions(String S) {
        List<List<Integer>> ans = new ArrayList();
        // i is the start of each group
        int i = 0, N = S.length(); 
        
        for (int j = 0; j < N; ++j) {
            if (j == N-1 || S.charAt(j) != S.charAt(j+1)) {
                // Here, [i, j] represents a group.
                if (j-i+1 >= 3)
                    ans.add(Arrays.asList(new Integer[]{i, j}));
                i = j + 1;
            }
        }

        return ans;
    }
}

1
2
3
4
5
6
7
8
9
10
class Solution {
    public int[] runningSum(int[] nums) {
        for(int i = 1; i < nums.length; ++i){
            nums[i] += nums[i - 1];
        }
        return nums;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
   public boolean isUnique(String astr) {
        if (astr.length() == 1 || astr.length() == 0) {
            return true;
        }
        
        boolean flag = true;
        for (int i = 0, len = astr.length(); i < len -1; i++){
            if (astr.indexOf(astr.charAt(i)) != astr.lastIndexOf(astr.charAt(i))){
                flag =false;
            }
        }
        return flag;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
class Solution {
    public int findShortestSubArray(int[] nums) {
        Map<Integer, Integer> left = new HashMap(),
            right = new HashMap(), count = new HashMap();

        for (int i = 0; i < nums.length; i++) {
            int x = nums[i];
            if (left.get(x) == null) left.put(x, i);
            right.put(x, i);
            count.put(x, count.getOrDefault(x, 0) + 1);
        }

        int ans = nums.length;
        int degree = Collections.max(count.values());
        for (int x: count.keySet()) {
            if (count.get(x) == degree) {
                ans = Math.min(ans, right.get(x) - left.get(x) + 1);
            }
        }

        return ans;
    }
    
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public boolean CheckPermutation(String s1, String s2) {
        if(s1.length()!=s2.length()) return false;
        
        int[] nums = new int[26];
        int len = s1.length();
        for (int i = 0; i < len; i++) {
            nums[s1.charAt(i)-97]++;
            nums[s2.charAt(i)-97]--;
        }
        for (int num : nums) {
            if (num != 0) return false;
        }
        return true;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
class Solution {
    public int[] finalPrices(int[] prices) {
        int[] result = new int[prices.length];
        int j = 0;
        
        for (int i = 0; i < prices.length; i++)
        {
            j = i + 1;
            while (j < prices.length)
            {
                if (prices[j] <= prices[i])
                {
                    result[i] = prices[i] - prices[j];
                    break;
                }
                else
                {
                    result[i] = prices[i];
                }
                j++;
            }
        }
        //检查最后一位
        result[prices.length - 1] = prices[prices.length - 1];
        return result;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int findSpecialInteger(int[] arr) {
        int threshold = arr.length / 4;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i + threshold] == arr[i]) {
                return arr[i];
            }
        }
        return 0;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public int findSpecialInteger(int[] arr) {
        Map<Integer, Integer> map = new HashMap();
        for(int i : arr){//先把数组中的数据存放在map中，key为元素值，value为出现的次数
            map.put(i, map.getOrDefault(i, 0) + 1);
        }
        for(int key : map.keySet()){
            Integer value = map.get(key);
            if(value > arr.length / 4){//如果有满足的及时输出
                return key;
            }
        }
        return -1;

    }
}