LeetCode每日打卡-April

发布于 16 天前  116 次阅读


4月16日

扰乱字符串🌟

动态规划 & 递归

class Solution {
    //记忆化搜索储存状态数组
    //-1表示false
    //1表示true
    //0表示未计算
    int[][][] memo;
    String s1, s2;

    public boolean isScramble(String s1, String s2) {
        int len = s1.length();
        this.memo = new int[len][len][len + 1];
        this.s1 = s1;
        this.s2 = s2;
        return dfs(0, 0, len);
    }

    //判断输入两个字符串是否和谐
    public boolean dfs (int i1, int i2, int length) {
        if (memo[i1][i2][length] != 0) {
            return memo[i1][i2][length] == 1;
        }
        //判断两个字串是否相等
        if (s1.substring(i1, i1 + length).equals(s2.substring(i2, i2 + length))) {
            memo[i1][i2][length] = 1;
            return true;
        }

        //判断是否存在子串c在两段字符中出现次数不同
        if (!checkIfSimilar(i1, i2, length)) {
            memo[i1][i2][length] = -1;
            return false;
        }

        //枚举不同的分割位置
        for (int i = 1; i < length; ++i) {
            //分割子串不交换位置
            if (dfs(i1, i2, i) && dfs(i1 + i, i2 + i, length - i)) {
                memo[i1][i2][length] = 1;
                return true;
            }
            //分割子串交换位置
            if (dfs(i1, i2 + length - i, i) && dfs(i1 + i, i2, length - i)) {
                memo[i1][i2][length] = 1;
                return true;
            }
        }

        memo[i1][i2][length] = -1;
        return false;
    }

    //检查两子串中相同字符出现次数是否相同
    public boolean checkIfSimilar (int i1, int i2, int length) {
        HashMap<Character, Integer> freq = new HashMap<Character, Integer>();
        //对应键值加1
        for (int i = i1; i < i1 + length; ++i) {
            //getOrDefault() 方法获取指定 key 对应对 value,如果找不到 key ,则返回设置的默认值。
            //key - 键
            //defaultValue - 当指定的key并不存在映射关系中,则返回的该默认值
            char c = s1.charAt(i);
            freq.put (c, freq.getOrDefault(c, 0) + 1);
        }
        //对应键值减1
        for (int i = i2; i < i2 + length; ++i) {
            char c = s2.charAt(i);
            freq.put(c, freq.getOrDefault(c, 0) - 1);
        }
        //遍历整个HashMap
        for (Map.Entry<Character, Integer> entry : freq.entrySet()) {
            //不为零则两字串中对应字符出现次数不同
            if (entry.getValue() != 0) return false; 
        }
        return true;
    }
}

4月15日

打家劫舍 II

动态规划

class Solution {
    public int rob(int[] nums) {

        int n = nums.length;
        if (n == 0) return 0;
        if (n == 1) return nums[0];
        if (n == 2) return Math.max(nums[0], nums[1]);

        int[] dp1 = new int[n];
        int[] dp2 = new int[n];
        //1到n
        dp1[1] = nums[1];
        dp1[2] = Math.max(nums[1], nums[2]);
        for (int i = 3; i < n; ++i) {
            dp1[i] = Math.max(dp1[i - 2] + nums[i], dp1[i - 1]);
        }

        //0到n-1
        dp2[0] = nums[0];
        dp2[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < n - 1; ++i) {
            dp2[i] = Math.max(dp2[i - 2] + nums[i], dp2[i - 1]);
        }

        return Math.max(dp1[n - 1], dp2[n - 2]);
    }
}

打家劫舍

动态规划

class Solution {
    public int rob(int[] nums) {
        if (nums.length == 0) return 0;
        if (nums.length == 1) return nums[0];
        int n = nums.length;
        int[] dp = new int[n];
        dp[0] = nums[0];
        dp[1] = Math.max(nums[0], nums[1]);
        for (int i = 2; i < n; ++i) {
            dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
        }
        return dp[n - 1];
    }
}

4月14日

实现 Trie (前缀树)

class Trie {
    private Trie[] children;
    private boolean isEnd;

    /** Initialize your data structure here. */
    public Trie() {
        children = new Trie[26];
        isEnd = false;
    }

    /** Inserts a word into the trie. */
    public void insert(String word) {
        Trie node = this;
        for (int i = 0; i < word.length(); ++i) {
            int idx = word.charAt(i) - 'a';
            if (node.children[idx] == null) {
                node.children[idx] = new Trie();
            }
            node = node.children[idx];
        }
        node.isEnd = true;
    }

    /** Returns if the word is in the trie. */
    public boolean search(String word) {
        Trie node = searchPrefix(word);
        return node != null && node.isEnd;
    }

    /** Returns if there is any word in the trie that starts with the given prefix. */
    public boolean startsWith(String prefix) {
        return searchPrefix(prefix) != null;

    }

    //查找指定字符串是否在字典树中存在,并返回最后一个字母所在节点
     public Trie searchPrefix(String prefix) {
        Trie node = this;
        for (int i = 0; i < prefix.length(); ++i) {
            int idx = prefix.charAt(i) - 'a';
            if (node.children[idx] == null) {
                return null;
            }
            node = node.children[idx];
        }
        return node;
    }
}

/**
 * Your Trie object will be instantiated and called as such:
 * Trie obj = new Trie();
 * obj.insert(word);
 * boolean param_2 = obj.search(word);
 * boolean param_3 = obj.startsWith(prefix);
 */

复制带随机指针的链表

回溯算法

/*
// Definition for a Node.
class Node {
    int val;
    Node next;
    Node random;

    public Node(int val) {
        this.val = val;
        this.next = null;
        this.random = null;
    }
}
*/
class Solution {
    HashMap<Node, Node> visitedHash = new HashMap<Node, Node>();
    public Node copyRandomList(Node head) {
        if (head == null) return null;
        //检查节点是否已经复制过
        if (this.visitedHash.containsKey(head)) {
            return this.visitedHash.get(head);
        }
        //复制节点
        Node node = new Node (head.val, null, null);
        //放入访问哈希表,比建立键值关系
        this.visitedHash.put(head, node);
        //递归复制其他节点,并将next和random指向新节点
        node.next = copyRandomList(head.next);
        node.random = copyRandomList(head.random);
        //返回复制节点
        return node;
    }
}

注:containsKey() 方法检查 hashMap 中是否存在指定的 key 对应的映射关系。
详见:Java HashMap

岛屿数量

DFS深度优先遍历

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; ++i) {
            for (int j = 0; j < grid[0].length; ++j) {
                //当是陆地时,进入递归,递归结束时岛屿数量加1
                if (grid[i][j] == '1') {
                    gridDfs (grid, i, j);
                    ++count;
                }
            }
        }
        return count;
    }

    public void gridDfs (char[][] grid, int i, int j) {
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') {
            return;
        }
        //标记已访问,当原图不能改时可以用visited数组代替
        grid[i][j] = '0';
        //递归周边其他节点
        gridDfs (grid, i + 1, j);
        gridDfs (grid, i, j + 1);
        gridDfs (grid, i - 1, j);
        gridDfs (grid, i, j - 1);
    }
}

DFS广度优先遍历

class Solution {
    public int numIslands(char[][] grid) {
        int count = 0;
        for (int i = 0; i < grid.length; ++i) {
            for (int j = 0; j < grid[0].length; ++j) {
                //当是陆地时,进入递归,递归结束时岛屿数量加1
                if (grid[i][j] == '1') {
                    grid[i][j] = '0';
                    gridBfs (grid, i, j);
                    ++count;
                }
            }
        }
        return count;
    }
    //广度优先遍历
    public void gridBfs (char[][] grid, int i, int j) {
        int n = grid.length;
        int m = grid[0].length;
        Queue<Integer> queue = new LinkedList<Integer>();
        queue.offer(i * m + j);
        while (!queue.isEmpty()) {
            int cur = queue.poll();
            i = cur / m; j = cur % m;
            //入队前先判断防止重复入队浪费资源
            if ((i - 1) >= 0 && grid[i - 1][j] == '1') {
                grid[i - 1][j] = '0';
                queue.offer((i - 1) * m + j);
            }
            if ((i + 1) < n && grid[i + 1][j] == '1') {
                grid[i + 1][j] = '0';
                queue.offer((i + 1) * m + j);
            }
            if ((j - 1) >= 0 && grid[i][j - 1] == '1') {
                grid[i][j - 1] = '0';
                queue.offer(i * m + j - 1);
            }
            if ((j + 1) < m && grid[i][j + 1] == '1') {
                grid[i][j + 1] = '0';
                queue.offer(i * m + j + 1);
            }
        }
    }
}

BFS遍历方法的另一种写法:

public void gridBfs (char[][] grid, int i, int j) {
    Queue<int[]> queue = new LinkedList<int[]>();
    queue.add(new int[] {i, j});
    while (!queue.isEmpty()) {
        int[] cur = queue.remove();
        i = cur[0]; j = cur[1];
        if (i < 0 || j < 0 || i >= grid.length || j >= grid[0].length || grid[i][j] == '0') {
            continue;
        }
        grid[i][j] = '0';
        //未判断会出现重复入队
        queue.add(new int[] {i + 1, j});
        queue.add(new int[] {i, j + 1});
        queue.add(new int[] {i - 1, j});
        queue.add(new int[] {i, j - 1});
    }
}

队列(Queue)相关方法区别:

  1. offer,add 区别:
    • 一些队列有大小限制,因此如果想在一个满的队列中加入一个新项,多出的项就会被拒绝。这时新的 offer 方法就可以起作用了。它不是对调用 add() 方法抛出一个 unchecked 异常,而只是得到由 offer() 返回的 false。
  2. poll,remove 区别:
    • remove() 和 poll() 方法都是从队列中删除第一个元素。remove() 的行为与 Collection 接口的版本相似, 但是新的 poll() 方法在用空集合调用时不是抛出异常,只是返回 null。因此新的方法更适合容易出现异常条件的情况。
  3. peek,element区别:
    • element() 和 peek() 用于在队列的头部查询元素。与 remove() 方法类似,在队列为空时, element() 抛出一个异常,而 peek() 返回 null。

4月13日

二叉搜索树节点最小距离

对二叉搜索树进行中序遍历,将遍历的值保存到list中,再判断元素之间最小差值

/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode() {}
 *     TreeNode(int val) { this.val = val; }
 *     TreeNode(int val, TreeNode left, TreeNode right) {
 *         this.val = val;
 *         this.left = left;
 *         this.right = right;
 *     }
 * }
 */
class Solution {
    public int minDiffInBST(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        inorder (root, list);
        int min = Integer.MAX_VALUE;
        for (int i = 1; i < list.size(); ++i) {
            min = Math.min(list.get(i) - list.get(i - 1), min);
        } 
        return min;
    }
    //中序遍历
    private void inorder (TreeNode node, List<Integer> res) {
        if (node == null) return;
        inorder (node.left, res);
        res.add(node.val);
        inorder (node.right, res);
    }
}

上述方法优化

class Solution {
    int ans = Integer.MAX_VALUE;
    int pre = -1;
    public int minDiffInBST(TreeNode root) {
        return inorder(root);
    }
    //中序遍历
    private int inorder (TreeNode node) {
        if (node == null) return ans;
        inorder(node.left);
        if (pre == -1) pre = node.val;
        else {
            ans = Math.min(ans, node.val - pre);
            pre = node.val;
        }
        inorder (node.right);
        return ans;
    }
}

二叉树的中序遍历

递归

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> list = new ArrayList<Integer>();
        inorder(root, list);
        return list;
    }

    private void inorder (TreeNode node, List<Integer> list) {
        if (node == null) return;
        inorder (node.left, list);
        list.add(node.val);
        inorder (node.right, list);
    }
}

迭代

class Solution {
    public List<Integer> inorderTraversal(TreeNode root) {
        List<Integer> res = new ArrayList<>();
        Deque<TreeNode> stack = new LinkedList<>();
        while (root != null || !stack.isEmpty()) {
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            root = stack.pop();
            res.add(root.val);
            root = root.right;
        }
        return res;
    }
}

4月12日

最大数

class Solution {
    public String largestNumber(int[] nums) {
        int n = nums.length;

        //Arrays类提供的函数中,没有方法对int[]数组进行排序。
        //sort函数可以有第二个参数: Comparator参数,但此参数仅支持引用类型。
        //int并非引用类型,无法对int[]数组进行排序,因此需要把数组复制进Integer[]数组中。
        Integer[] numsArr = new Integer[n];
        for (int i = 0; i < n; ++i) {
            numsArr[i] = nums[i];
        }

        //使用lambda表达式重写Comparator比较器
        //返回值小于0时,排序x在y的前面;返回值大于0时,排序x在y的后面;
        Arrays.sort(numsArr, (x, y) -> {
            long sx = 10, sy = 10;
            while (sx <= x) sx *= 10;
            while (sy <= y) sy *= 10;
            return (int) (sx * y + x - sy * x - y);
        });

        //上述步骤结束后numsArr里元素已经按照要求排序完成
        //首先判断是否元素都为0
        if (numsArr[0] == 0) return "0";
        //以下进行数组结果字符串输出
        StringBuilder ret = new StringBuilder();
        for (int num : numsArr) ret.append(num);
        return ret.toString();
    }
}

4月11日

丑数II

动态规划

class Solution {
    public int nthUglyNumber(int n) {
        int[] dp = new int[n + 1];
        dp[1] = 1;
        int p2 = 1, p3 = 1, p5 = 1;
        for (int i = 2; i <= n; ++i) {
            int num2 = dp[p2] * 2;
            int num3 = dp[p3] * 3;
            int num5 = dp[p5] * 5;
            dp[i] = Math.min(Math.min(num2, num3), num5);
            if (dp[i] == num2) ++p2;
            if (dp[i] == num3) ++p3;
            if (dp[i] == num5) ++p5;
        }
        return dp[n];
    }
}

4月10日

丑数

丑数就是只包含质因数2、3、5 的正整数

class Solution {
    public boolean isUgly(int n) {
        if (n <= 0) return false;

        while (n % 2 == 0) n /= 2;
        while (n % 3 == 0) n /= 3;
        while (n % 5 == 0) n /= 5;

        if (n == 1) return true;
        else return false;
    }
}

4月9日

寻找旋转排序数组中的最小值II

二分法

class Solution {
    public int findMin(int[] nums) {
        int low = 0, high = nums.length - 1;
        while (low < high) {
            int mid = (low + high) / 2;
            if (nums[mid] < nums[high]) {
                high = mid;
            }
            else if (nums[mid] > nums[high]) {
                low = mid + 1;
            }
            else --high;
        }
        return nums[low];
    }
}

4月8日

寻找旋转排序数组中的最小值

利用规律线性查找

class Solution {
    public int findMin(int[] nums) {
        for (int i = 1; i < nums.length; ++i) {
            if (nums[i] < nums[i - 1]) return nums[i];
        }
        return nums[0];
    }
}

二分法

class Solution {
    public int findMin(int[] nums) {
        int low = 0, high = nums.length - 1;
        while (low < high) {
            int mid = (low + high) / 2;
            if (nums[mid] < nums[high]) {
                high = mid;
            }
            //不可能会有等于的情况
            else if (nums[mid] > nums[high]) {
                low = mid + 1;
            }
        }
        return nums[low];
    }
}

4月7日

搜索旋转排序数II

利用规律线性查找

class Solution {
    public boolean search(int[] nums, int target) {
        int n = nums.length;
        if (nums[0] == target || nums[n - 1] == target) return true;

        for (int i = 0; i < n - 1; ++i) {
            if (target > nums[i] && target < nums[i + 1]) {
                return false;
            }
            else if (target == nums[i]) {
                return true;
            }
        }
        return false;
    }
}

二分法

class Solution {
    public boolean search(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) return false;
        if (n == 1) return nums[0] == target;
        int low = 0, high = n - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (nums[mid] == target) return true;
            if (nums[mid] == nums[low] && nums[mid] == nums[high]) {
                ++low;
                --high;
            }
            else if (nums[low] <= nums[mid]) {
                //这里由于上面已经判断过了target == nums[mid]因此可以不需要做等于判断。
                if (target >= nums[low] && target < nums[mid]) {
                    high = mid - 1;
                }
                else {
                    low = mid + 1;
                }
            }
            else {
                if (target > nums[mid] && target <= nums[high]) {
                    low = mid + 1;
                }
                else {
                    high = mid - 1;
                }
            }
        }
        return false;
    }
}

搜索旋转排序数组

二分法

class Solution {
    public int search(int[] nums, int target) {
        int n = nums.length;
        if (n == 0) return -1;
        if (n == 1) return nums[0] == target ? 0 : -1;
        int low = 0, high = n - 1;
        while (low <= high) {
            int mid = (low + high) / 2;
            if (nums[mid] == target) return mid;
            if (nums[0] <= nums[mid]) {
                if (nums[0] <= target && target < nums[mid]) high = mid - 1; 
                else low = mid + 1;
            } 
            else {
                if (nums[mid] < target && target <= nums[n - 1]) low = mid + 1; 
                else high = mid - 1;
            }
        }
        return -1;
    }
}

验证回文串

class Solution {
    public boolean isPalindrome(String s) {
        int n = s.length();
        int low = 0, high = n - 1;
        while (low < high) {
            while (low < high && !Character.isLetterOrDigit(s.charAt(low))) ++low;
            while (low < high && !Character.isLetterOrDigit(s.charAt(high))) --high;
            if(low < high) {
                if (Character.toLowerCase(s.charAt(low)) != Character.toLowerCase(s.charAt(high))) {
                    return false;
                }
                ++low;
                --high;
            }
        }
        return true;
    }
}
  • Character.toLowerCase()方法用于将大写字符转换为小写。
  • Character.isLetterOrDigit()方法确定指定字符(Unicode代码点)是一个字母或数字。

4月6日

删除有序数组中的重复项II

class Solution {
    public int removeDuplicates(int[] nums) {
        int len = nums.length;
        if (len <= 2) return len;
        int slow = 2, fast = 2;
        while (fast < len) {
            if(nums[slow - 2] != nums[fast]) {
                nums[slow] =  nums[fast];
                ++slow;
            }
            ++fast;
        }
        return slow;
    }
}

所有奇数长度子数组的和

计算一个数字在多少个奇数长度的数组中出现过

class Solution {
    public int sumOddLengthSubarrays(int[] arr) {
        int len = arr.length;
        int n;
        int sum = 0;
        int leftOdd, leftEven, rightOdd, rightEven;

        for (int i = 0; i < len; ++i) {
            leftOdd = (i + 1) / 2;
            leftEven = (i + 2) / 2;
            rightOdd = (len - i) / 2;
            rightEven =  (len - i + 1) / 2;
            n = leftEven*rightEven + leftOdd*rightOdd;
            sum += arr[i] * n;
        }
        return sum;
    }
}

4月5日

合并两个有序数组

class Solution {
    public void merge(int[] nums1, int m, int[] nums2, int n) {
        int i = m - 1, j = n - 1;
        int k = m + n - 1;
        while (j >= 0) {
            if (i >= 0 && nums1[i] > nums2[j]) {
                nums1[k--] = nums1[i--];
            }
            else {
                nums1[k--] = nums2[j--];
            }
        }
    }
}

二分查找

class Solution {
    public int search(int[] nums, int target) {
        int low = 0, high = nums.length - 1;
        int mid = 0;
        while (low <= high) {
            mid = (low + high) / 2;
            if (nums[mid] > target) {
                high = mid - 1;
            }
            else if (nums[mid] < target) {
                low = mid + 1;
            }
            else return mid;
        }
        return -1;
    }
}

截断句子

class Solution {
    public String truncateSentence(String s, int k) {
        StringBuilder ans = new StringBuilder();
        for (String i : s.split("\\s+")) {
            if (k-- > 0)
            ans = ans.append(i).append(' ');

        }
        ans.setLength(ans.length() - 1);
        return ans.toString();
    }
}
  • split("\s+") 按空格,制表符,等进行拆分,也就是说它是按空白部分进行拆分,不管这个空白使用什么操作留下的(如空格键 tab键);
  • split(" +") 按空格进行拆分,也就是说只有按空格键流出来的空白才会是拆分的一句。

4月4日

森林中的兔子

class Solution {
    public int numRabbits(int[] answers) {
        Map<Integer, Integer> count = new HashMap<Integer, Integer>();
        for (int y : answers) {
            //getOrDefault()方法获取指定key对应对value,如果找不到key,则返回设置的默认值。
            count.put(y, count.getOrDefault(y, 0) + 1);
        }
        int ans = 0;
        for (Map.Entry<Integer, Integer> entry : count.entrySet()) {
            int y = entry.getKey(), x = entry.getValue();
            // (x + y) / (y + 1)用来向上取整求共有多少组兔子
            ans += (x + y) / (y + 1) * (y + 1);
        }
        return ans;
    }
}

万一兔子说谎了呢?

排序数组

快速排序

class Solution {
    public int[] sortArray(int[] nums) {
        quickSort(nums, 0, nums.length-1);
        return nums;
    }
    public static void quickSort(int[] arr, int start, int end) {
        int mid = partition(arr, start, end); //数组分区
        quickSort(arr, start, mid - 1); //左边快排
        quickSort(arr, mid + 1, end); //右边快排
    }
    public static int partition(int[] arr, int start, int end) {
        int pivot = arr[0];
        while (start < end) {
            while (start < end && arr[end] >= pivot) --end;
            arr[start] = arr[end];
            while (start < end && arr[start] <= pivot) ++start;
            arr[end] = arr[start];
        }
        arr[start] = pivot;
        return start;
    }
}

4月3日

最长公共子序列

动态规划

class Solution {
    public int longestCommonSubsequence(String text1, String text2) {
        int m = text1.length(), n = text2.length();
        int dp[][] = new int[m+1][n+1];
        for (int i = 1; i <= m; ++i) {
            for (int j = 1; j <= n; ++j) {
                //转移方程
                if (text1.charAt(i-1) == text2.charAt(j-1)) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                }
                else dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
            }
        }
        return dp[m][n];
    }
}

4月2日

直方图的水量

动态规划 Time: O(n) Space: O(n)

class Solution {
    public int trap(int[] height) {
        int n = height.length;
        if(n == 0) return 0;
        int leftMax[] = new int[n];
        int rightMax[] = new int[n];
        //动态规划两个表示某一元素左右两边最大值的数组
        leftMax[0] = height[0];
        rightMax[n - 1] = height[n - 1];
        for (int i = 1; i < n; ++i) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }
        for (int j = n-2; j >= 0; --j) {
            rightMax[j] = Math.max(rightMax[j + 1], height[j]);
        }
        //利用求出的两个数组求水量
        int ans = 0;
        for (int i = 0; i < n; ++i) {
                ans += Math.min(leftMax[i], rightMax[i]) - height[i];
        }
        return ans;
    }
}

双指针法 Time: O(n) Space: O(1)

class Solution {
    public int trap(int[] height) {
        int ans = 0;
        int low = 0, high = height.length - 1;
        int lowMax = 0, highMax = 0;
        while (low < high) {
            lowMax = Math.max(lowMax, height[low]);
            highMax = Math.max(highMax, height[high]);

            if(height[low] < height[high]) {
                ans += lowMax - height[low];
                ++low;
            }
            else {
                ans += highMax - height[high];
                --high;
            }
        }
        return ans;
    }
}

4月1日

笨阶乘

栈模拟

class Solution {
    public int clumsy(int N) {
        Deque<Integer> stack = new LinkedList<Integer>();
        stack.push(N--);
        int index = 0;
        while(N > 0) {
            if(index % 4 == 0) stack.push(stack.pop() * N);
            else if(index % 4 == 1) stack.push(stack.pop() / N);
            else if(index % 4 == 2) stack.push(N);
            else stack.push(-N);
            --N; ++index;
        }

        int sum = 0;
        while(!stack.isEmpty()) {
            sum += stack.pop();
        }
        return sum;
    }
}

删除有序数组中的重复项

双指针法

class Solution {
    public int removeDuplicates(int[] nums) {
        if(nums == null) return 0;
        int i = 0, j = 1;
        while(j < nums.length) {
            if(nums[i] == nums[j]) ++j;
            else nums[++i] = nums[j++];
        }
        return i + 1;
    }
}

旋转数组

class Solution {
    public void rotate(int[] nums, int k) {
        k %= nums.length;
        reverse(nums, 0, nums.length-1);
        reverse(nums, 0, k - 1);
        reverse(nums, k, nums.length - 1);
    }

    private void reverse(int[] nums, int low, int high) {
        while(low < high) {
            int temp = nums[low];
            nums[low] = nums[high];
            nums[high] = temp;
            ++low; --high;
        }
    }
}

Try and fail, but don't fail to try.