给一组数字, 找山峰和山谷, 这里数字相同就认为是同在一个山峰or山谷. 求山峰山谷总数.

class Solution {
    public int countHillValley(int[] nums) {
        int res = 0;
        int n = nums.length; 
        LinkedList<Integer> list = new LinkedList<>();
        for(int nn : nums){
            if(!list.isEmpty() && list.getLast() == nn)
                continue;
            list.add(nn);
        }
        if(list.size() < 3)
            return 0;
        int[] ary = new int[list.size()];
        int j = 0;
        for(int nn : list)
            ary[j++] = nn;
        for(int i = 1; i < ary.length - 1; i++){ 
            if((ary[i - 1] < ary[i] && ary[i] > ary[i + 1]) || ary[i - 1] > ary[i] && ary[i] < ary[i + 1])
                res++; 
        }
        return res;
    }
}

给两个数字, 给一组操作, 乘2或者减1, 求能不能从start到target.

这题吧, 有点意思, 因为用greedy做, 所以找greedy的条件的时候, 会发现因为我们要最多的乘除, 但是乘法无法确定一定在最优解的路径上. 而除法可以通过判断是不是target % 2 == 0 可以确定在答案路径上, 所以则选用从target 到 start的除+加.

class Solution {
    public int brokenCalc(int startValue, int target) {
        if(startValue >= target)
            return startValue - target;
        if(target % 2 == 0) // best option (greed)
            return 1 + brokenCalc(startValue, target / 2);
        else
            return 1 + brokenCalc(startValue, target + 1);
    }
}

给一个linkedlist, 里面的数字由0分割, 求0之间的数字的和的list.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public ListNode mergeNodes(ListNode head) {
        ListNode resDummy = new ListNode();
        ListNode res = resDummy;
        int tmp = 0;
        while(head != null && head.next != null){
            if(head.next.val == 0){
                res.next = new ListNode(tmp);
                res = res.next;
                tmp = 0;
            }else
            {
                tmp += head.next.val;
            }
            head = head.next;
        }
        return resDummy.next;
    }
}

给一个数组, 求一个pair, nums[i] == nums[j] 并且 i * j 能被k整除.

class Solution {
    public int countPairs(int[] nums, int k) {
        int res = 0;
        for(int i = 0; i < nums.length; i++) {
            for(int j = i + 1; j < nums.length; j++) {
                if(nums[i] == nums[j] && (i * j) % k == 0)
                    res++;
            }
        }
        return res;
    }
}

给一个range[1,num], 求里面有多少数的digit sum是偶数.

class Solution {
    public int countEven(int num) {
        int res = 0;
        for(int i = 1; i <= num; i++){
            int even = 0;
            int cur = i;
            while(cur != 0){
                even += (cur  % 10);
                cur /= 10;
            }
            if(even % 2 == 0)
                res++;
        }
        return res;
    }
}

给一个数组, 里面是数字是灌溉i位上的植物需要的水, 给一个整数, 代表水桶的大小, 每次走一步, 没水需要回原点取水, 求一共多少步.

class Solution {
    public int wateringPlants(int[] plants, int capacity) {
        int res = 0;
        int c = capacity;
        for(int i = 0; i < plants.length; i++){
            if(plants[i] > c){
                res += (i + (i + 1));
                c = capacity;
                c -= plants[i];
            }
            else{
                res++;
                c -= plants[i];
            }
        }
        return res;
    }
}

给一个字符串和一个对应的数组, 求字符串每个不相邻的不同颜色的最大值.

class Solution {
    public int minCost(String colors, int[] neededTime) {
        int sum = 0;
        int n = neededTime.length;
        for(int m : neededTime){
            sum += m;
        } 
        if(n == 1)
            return neededTime[0];
        char cur = colors.charAt(0);
        int cur_max = neededTime[0];
        int maxSum = 0;
        for(int i = 1; i < neededTime.length; i++) {
            char c = colors.charAt(i);
            if(c == cur){
                cur_max = Math.max(cur_max, neededTime[i]);
            }
            else
            {
                cur = c;
                maxSum += cur_max;
                cur_max = neededTime[i];
            }
        }
        return sum - maxSum - cur_max;
    }
}

给一个数组和一个target, 求这个数组中有多少种数字组合可以组成这个target.

dfs + memo 模板题.

class Solution {
    Map<Integer, Integer> memo = new HashMap<>();
    public int combinationSum4(int[] nums, int target) { // dfs + memo
        if(target < 0)
            return 0;
        if(target == 0)
            return 1;
        if(memo.containsKey(target))
            return memo.get(target);
        int cur = 0;
        for(int n : nums){
            cur += combinationSum4(nums, target - n); // sum = target - 1 , target - 2, target - 3
        }
        memo.put(target, cur);
        return cur;
    }
}

给一个数组, 里面的数字是偶数个, 里面有同样数量的正数和负数, 要求按照顺序stable的排列.

class Solution {
    public int[] rearrangeArray(int[] nums) {
        int n = nums.length;        
        int[] res = new int[n];
        int k = 0;
        int p = 1;
        for(int s : nums){  
            if(s >= 0){
                res[k] = s;
                k += 2;
            }else{
                res[p] = s;
                p += 2;
            }
        }
        return res;
    }
}

给一个链表, 定义twin sum是前后对应的两个node的和, 求最大的twin sum.

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution {
    public int pairSum(ListNode head) {
        ListNode p = head;
        ListNode m = mid(head);
        ListNode r = rev(m);
        int res = 0;
        while(p != null){
            res = Math.max(res, p.val + r.val);
            p = p.next;
            r = r.next;
        }
        return res;
    }
    private ListNode rev(ListNode head) {
        ListNode newHead = null;
        while(head != null){
            ListNode next = head.next;
            head.next = newHead;
            newHead = head;
            head = next;
        }
        return newHead;
    }
    private ListNode mid(ListNode head) {
        ListNode dF = new ListNode(0);
        ListNode sF = new ListNode(0);
        dF.next = head;
        sF.next = head;
        while(dF.next != null && dF.next.next != null){
            sF = sF.next;
            dF = dF.next.next;
        }
        return sF;
    }
}