给一个String, 问里面多少个substring只有一个不同的字符.

首先一个string, 比如aaaaa, 那么里面的只有一个不同字符的是n*(n+1) / 2个子string. 然后找就行了.

class Solution {
public:
    int countLetters(string S) {
        int res = 0;
        int cur = 1;
        for(int i = 1; i < S.length(); i++) {
            if(S[i] != S[i - 1]){
                res += cur * (cur + 1) / 2;
                cur = 1;
            }else{
                cur++;
            }
        }
        res += cur * (cur + 1) / 2;
        return res;
    }
};

给一个数组, 让简单的变化一下.

class Solution {
public:
    vector<int> transformArray(vector<int>& arr) {
        bool changed = true;
        while(changed) {
            changed = false;
            vector<int> ary(arr.size());
            ary[0] = arr[0];
            ary[arr.size() - 1] = arr[arr.size() - 1];
            for(int i = 1; i < arr.size() - 1; i++) {
                if(arr[i - 1] > arr[i] && arr[i] < arr[i + 1]){
                    ary[i] = arr[i]+1;
                    changed = true;
                }else if(arr[i - 1] < arr[i] && arr[i] > arr[i + 1]){
                    ary[i] = arr[i]-1;
                    changed = true;
                }else {
                    ary[i] = arr[i];
                }
            }
            arr = ary;
        }
        return arr;
    }
};

给一个2d数组, 里面是数字是当前坐标的叠着的正方体数, 求一共多少个面.

这个题就是弄清楚两个正方体分享一个面, 所以计算的时候要先比较相邻正方体的高矮, 然后减去矮的部分共享的面数即可. 然后数组值可能为0(没有正方体)

class Solution {
public:
    int surfaceArea(vector<vector<int>>& grid) {
        int res = 0; 
        for(int i = 0; i < grid.size(); i++){
            for(int j = 0; j < grid[0].size(); j++) {
                if(grid[i][j] != 0){ //2 -> 10
                    res += grid[i][j] * 6; // total six cubes
                    res -= 2*(grid[i][j] - 1); // 2*(grid[i][j] - 1) pairs (shares 1 surface)
                    if(i != grid.size() - 1){
                        res -= 2 * min(grid[i][j], grid[i + 1][j]);
                    }
                    if(j != grid[0].size() - 1){
                        res -= 2 * min(grid[i][j], grid[i][j + 1]);
                    }
                }
            }
        }
        return res;
    }
};

给一个数组, 里面是0和1, 求里面的1互相之间是否至少隔k个数.

class Solution {
public:
    bool kLengthApart(vector<int>& nums, int k) {
        vector<int> v;
        for(int i = 0; i < nums.size(); i++) {
            if(nums[i] == 1)
                v.push_back(i);
        }
        for(int i = 1; i < v.size(); i++) { 
            if(v[i] - v[i - 1] <= k)
                return false;
        }
        return true;
    }
};

设计一个runlength压缩后的string的iterator.

class StringIterator {
public:
    deque<char> v;
    deque<int> c;
    StringIterator(string cs) {
        for(int i = 0; i < cs.length();) {
            if(i < cs.length() && '0' <= cs[i] && cs[i] <= '9'){
                int count = 0;
                while(i < cs.length() && '0' <= cs[i] && cs[i] <= '9'){
                    count = (count * 10) + (cs[i] - '0');
                    i++;
                }
                c.push_back(count);
            }else{
                v.push_back(cs[i++]);
            }
        }
    }
    
    char next() {
        if(!hasNext())
            return ' ';
        c[0]--;
        char vv = v.front();
        if(c[0] == 0){
            c.pop_front();
            v.pop_front();
        }
        return vv;
            
    }
    
    bool hasNext() {
        return c.size() != 0 && v.size() != 0;
    }
};

/**
 * Your StringIterator object will be instantiated and called as such:
 * StringIterator* obj = new StringIterator(compressedString);
 * char param_1 = obj->next();
 * bool param_2 = obj->hasNext();
 */

给一个binary的string, 求里面有多少个substring是有相同的个数1和0.

这个题直接就count, 然后sliding windows, 然后简化到了只需要记录不同的0 和1的group的最小的.

class Solution {
public:
    int countBinarySubstrings(string s) {
        int cur = 1;
        int prev = 0;
        int res = 0;
        for(int i = 1; i < s.length(); i++) {
            if(s[i] != s[i - 1]){
                res += min(prev, cur);
                prev = cur;
                cur = 1;
            }else{
                cur++;
            }
        }
        return res += min(prev, cur) ;
    }
};

给一个数字, 求基数为k的digits的和.

class Solution {
    public int sumBase(int n, int k) {
        int res = 0;
        while(n > 0){
            res += n % k;
            n /= k;
        } 
        return res;
    }
}

给一个数字maxbit和一个sorted array, 求返回一个array, 里面的数字是k个query的结果, k是一个数字, 他是数组中每个数字的xor后最大不超过2^maxbit的数的可能数字.

这个题主要先理解题目, 然后已知xor运算是互逆的, 所以先算出所有数的xor, 然后再往前逐个xor即可得到前边数字的xor的数字, 设这个数字为x. 其次, 假设x是3, maxbit是5. 3的二进制就是11, (2^5 -1)的二进制是1111. 因为后边是4位, 所以前边的3可以看做是0011, 那么问题转化成, 1111和0011的最大xor可能取值是多少, 就是1100(1111 xor 0011).

class Solution {
    public int[] getMaximumXor(int[] nums, int maximumBit) {
        int x = 0;
        for(int n : nums){
            x ^= n;
        }
        int[] res = new int[nums.length];
        for(int i = nums.length - 1; i >= 0; i--) {
            res[nums.length - i - 1] = (x ^ ((int)Math.pow(2, maximumBit) - 1));
            x ^= nums[i];
        }
        return res;
    }
}

给一个链表, 删除里面所有重复的元素, 链表本身不是已排序的.

因为没有排序, 所以要用set查重. 然后新建个链表返回即可.

/**
 * 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 deleteDuplicatesUnsorted(ListNode head) {
        Map<Integer, Integer> count = new HashMap<>();
        ListNode dummy = new ListNode(0);
        dummy.next = head;
        while(dummy.next != null) {
            count.put(dummy.next.val, count.getOrDefault(dummy.next.val, 0) + 1);
            dummy = dummy.next;
        }
        ListNode dn = new ListNode(0); 
        ListNode res = dn;
        while(head != null) {
            if(count.get(head.val) <= 1){
                dn.next = new ListNode(head.val);
                dn = dn.next;
            }
            head = head.next;
        }
        return res.next;
    }
}