Range Sum Query - Mutable

307. Range Sum Query - Mutable

Difficulty: Medium

Given an integer array nums, find the sum of the elements between indices _i_ and _j_ (_i_ ≤ _j_), inclusive.

The update(i, val) function modifies nums by updating the element at index _i_ to val.

Example:

1
2
3
4
5
Given nums = [1, 3, 5]

sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8

Note:

  1. The array is only modifiable by the update function.
  2. You may assume the number of calls to update and sumRange function is distributed evenly.

Solution

一个基本考察BIT的题目 https://blog.csdn.net/Yaokai_AssultMaster/article/details/79492190

Language: Java

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
45
46
47
48
49
50
51
public class NumArray {
    public int[] nums;
    public int[] arr;
​
    public NumArray(int[] nums) {
        this.nums = nums;
        arr = new int[nums.length+1];
        for(int i=0;i<nums.length;i++){
            add(i+1, nums[i]);
        }
​
    }
    
    public void add(int i, int val){
        for(int j=i;j<arr.length;j += j&(-j)){
            arr[j]+=val;
        }
    }
​
    public void update(int i, int val) {
        add(i+1, val-nums[i]);
        nums[i] = val;
    }
​
    /**
     * 计算 nums[0]+nums[1]...+nums[i]
     * @param i
     * @return
     */
    public int preSum(int i){
        i = i+1;    // 因为要包含nums[i]
        if(i>arr.length||i<=0)return 0;
        int ret = 0;
        // 从后往前推
        for(int j=i;j>0;j-=j&(-j)){
            ret +=arr[j];
        }
        return ret;
    }
​
    /**
     *  计算 nums[i]+nums[i+1]...+nums[j]
     * @param i
     * @param j
     * @return
     */
    public int sumRange(int i, int j) {
        return preSum(j)-preSum(i-1);
    }
}
​

展开全文 >>

Word Break

139. Word Break

Difficulty: Medium

Given a non-empty string _s_ and a dictionary wordDict containing a list of non-empty words, determine if _s_ can be segmented into a space-separated sequence of one or more dictionary words.

Note:

  • The same word in the dictionary may be reused multiple times in the segmentation.
  • You may assume the dictionary does not contain duplicate words.

Example 1:

1
2
3
**Input:** s = "leetcode", wordDict = ["leet", "code"]
**Output:** true
**Explanation:** Return true because `"leetcode"` can be segmented as `"leet code"`.

Example 2:

1
2
3
4
**Input:** s = "applepenapple", wordDict = ["apple", "pen"]
**Output:** true
**Explanation:** Return true because `"`applepenapple`"` can be segmented as `"`apple pen apple`"`.
             Note that you are allowed to reuse a dictionary word.

Example 3:

1
2
**Input:** s = "catsandog", wordDict = ["cats", "dog", "sand", "and", "cat"]
**Output:** false

Solution

Language: Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
class Solution {
    public boolean wordBreak(String s, List<String> wordDict) {
        // dp[i]表示0-i可以切分
        boolean[] dp = new boolean[s.length()+1];
        //　初始化
        dp[0] = true;
        for(int i=1;i<=s.length();++i){
            for(int j=0;j<i;++j){
                // 如果0-j已经正常切分，并且j-i也是一个单词，那么 0-i可以切分
                if(dp[j] && wordDict.contains(s.substring(j, i))){
                    dp[i] = true;
                    break;
                }
            }
        }
        return dp[s.length()];
        
    }
}

展开全文 >>

Increasing Triplet Subsequence

334. Increasing Triplet Subsequence

Difficulty: Medium

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k
such that arr[i] < arr[j] < arr[k] given 0 ≤ _i_ < _j_ < _k_ ≤ _n_-1 else return false.

Note: Your algorithm should run in O(_n_) time complexity and O(_1_) space complexity.

Example 1:

1
2
**Input:** <span id="example-input-1-1" style="display: inline;">[1,2,3,4,5]</span>
**Output:** <span id="example-output-1" style="display: inline;">true</span>

Example 2:

1
2
**Input:** <span id="example-input-2-1" style="display: inline;">[5,4,3,2,1]</span>
**Output:** <span id="example-output-2" style="display: inline;">false</span>

Solution

Language: Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public boolean increasingTriplet(int[] nums) {
        if (nums ==  null || nums.length < 3 ){
            return false;
        }
        int first = Integer.MAX_VALUE;
        int second = Integer.MAX_VALUE;
        
        for(int n:nums){
            if(n<=first)
            {
                first = n;
            }else if(n<=second){
                second = n;
            }else{
                return true;
            }
        }
        return false;
    }
}

展开全文 >>

Find Peak Element

162. Find Peak Element

Difficulty: Medium

A peak element is an element that is greater than its neighbors.

Given an input array nums, where nums[i] ≠ nums[i+1], find a peak element and return its index.

The array may contain multiple peaks, in that case return the index to any one of the peaks is fine.

You may imagine that nums[-1] = nums[n] = -∞.

Example 1:

1
2
3
**Input:** **nums** = `[1,2,3,1]`
**Output:** 2
**Explanation:** 3 is a peak element and your function should return the index number 2.

Example 2:

1
2
3
4
**Input:** **nums** = `[`1,2,1,3,5,6,4]
**Output:** 1 or 5 
**Explanation:** Your function can return either index number 1 where the peak element is 2, 
             or index number 5 where the peak element is 6.

Note:

Your solution should be in logarithmic complexity.

Solution

Language: Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int findPeakElement(int[] nums) {
        int l = 0;
        int r = nums.length-1;
        int ret = nums[0];
        while(l<r){
            int mid = (l+r)/2;
            int mid2 = mid+1;
            // keep the bigger one between l and r,l is bigger
            if(nums[mid]<nums[mid2]){
                l = mid2;
            }else{
                r = mid;
            }
        }
        return l;
    }
}

展开全文 >>

Palindrome Partitioning

131. Palindrome Partitioning

Difficulty: Medium

Given a string _s_, partition _s_ such that every substring of the partition is a palindrome.

Return all possible palindrome partitioning of _s_.

Example:

1
2
3
4
5
6
**Input:** "aab"
**Output:**
[
  ["aa","b"],
  ["a","a","b"]
]

在每一步都可以判断中间结果是否为合法结果，用回溯法。
一个长度为 n 的字符串，有 n − 1 个地方可以砍断，每个地方可断可不断，因此复杂度为
O(2n−1)

abc其实只有两个地方可以选择　a|b|c，但是在结束的时候，要单独考虑，把后面的结果加进去

Solution

Language: Java

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
45
class Solution {
    public List<List<String>> partition(String s) {
        List<List<String>> result = new LinkedList<>();
        // 先输出所有划分
        dfs(s, 0, "", new LinkedList<String>(), result);
        return result;
    }
    
    public void dfs(String s, int pos, String tmps, LinkedList<String> tmpl, List<List<String>>result){
        char c = s.charAt(pos);
        //System.out.println(c+" "+pos+" "+tmps+ " "+tmpl.size());
        if(pos>=s.length()-1){
            if(tmps.length()==0){
                // tmpl.addLast(tmps);
                tmpl.addLast(""+c);
            }
            else{
                if(!isPalindrome(tmps+c))return;
                tmpl.addLast(tmps+c);
            }
            result.add(new LinkedList<String>(tmpl));
            return ;
        };
​
​
        // 断开,把tmps+c加入tmpl, tmps清空
        tmpl.addLast(tmps+c);
        // 如果tmps+c是回文
        if(isPalindrome(tmps+c))dfs(s, pos+1, "", new LinkedList<String>(tmpl), result);
        tmpl.removeLast();
       // 不断开，把c加入tmps
        dfs(s, pos+1, tmps+c, new LinkedList<String>(tmpl), result);
        
    }
    
    public boolean isPalindrome(String str){
        int s = 0, e=str.length()-1;
        while(s<e){
            if(str.charAt(s)!=str.charAt(e))return false;
            s++;
            e--;
        }
        return true;
    }
}

展开全文 >>

Set Matrix Zeroes

73. Set Matrix Zeroes

Difficulty: Medium

Given a _m_ x _n_ matrix, if an element is 0, set its entire row and column to 0. Do it .

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
**Input:** 
[
  [1,1,1],
  [1,0,1],
  [1,1,1]
]
**Output:** 
[
  [1,0,1],
  [0,0,0],
  [1,0,1]
]

Example 2:

1
2
3
4
5
6
7
8
9
10
11
12
**Input:** 
[
  [0,1,2,0],
  [3,4,5,2],
  [1,3,1,5]
]
**Output:** 
[
  [0,0,0,0],
  [0,4,5,0],
  [0,3,1,0]
]

Follow up:

  • A straight forward solution using O(m__n) space is probably a bad idea.
  • A simple improvement uses O(_m_ + _n_) space, but still not the best solution.
  • Could you devise a constant space solution?

Solution

Language: Java
把第一列和第一行作为标记，如果为０表示这一行或者这一列要设置为０，此外，第一行和第一列本身是否有０用两个变量标记．

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
class Solution {
    public void setZeroes(int[][] matrix) {
        boolean fr = false,fc = false;
        for(int i = 0; i < matrix.length; i++) {
            for(int j = 0; j < matrix[0].length; j++) {
                if(matrix[i][j] == 0) {
                    if(i == 0) fr = true;
                    if(j == 0) fc = true;
                    matrix[0][j] = 0;
                    matrix[i][0] = 0;
                }
            }
        }
        for(int i = 1; i < matrix.length; i++) {
            for(int j = 1; j < matrix[0].length; j++) {
                if(matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        if(fr) {
            for(int j = 0; j < matrix[0].length; j++) {
                matrix[0][j] = 0;
            }
        }
        if(fc) {
            for(int i = 0; i < matrix.length; i++) {
                matrix[i][0] = 0;
            }
        }
    }
}

展开全文 >>

Gas Station

134. Gas Station

Difficulty: Medium

There are _N_ gas stations along a circular route, where the amount of gas at station _i_ is gas[i].

You have a car with an unlimited gas tank and it costs cost[i] of gas to travel from station _i_ to its next station (_i_+1). You begin the journey with an empty tank at one of the gas stations.

Return the starting gas station’s index if you can travel around the circuit once in the clockwise direction, otherwise return -1.

Note:

  • If there exists a solution, it is guaranteed to be unique.
  • Both input arrays are non-empty and have the same length.
  • Each element in the input arrays is a non-negative integer.

Example 1:

1
2
3
4
5
6
7
8
9
10
11
12
13
**Input:** 
gas  = [1,2,3,4,5]
cost = [3,4,5,1,2]

**Output:** 3

**Explanation:** Start at station 3 (index 3) and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 4\. Your tank = 4 - 1 + 5 = 8
Travel to station 0\. Your tank = 8 - 2 + 1 = 7
Travel to station 1\. Your tank = 7 - 3 + 2 = 6
Travel to station 2\. Your tank = 6 - 4 + 3 = 5
Travel to station 3\. The cost is 5\. Your gas is just enough to travel back to station 3.
Therefore, return 3 as the starting index.

Example 2:

1
2
3
4
5
6
7
8
9
10
11
12
**Input:** 
gas  = [2,3,4]
cost = [3,4,3]

**Output:** -1

**Explanation:** You can't start at station 0 or 1, as there is not enough gas to travel to the next station.
Let's start at station 2 and fill up with 4 unit of gas. Your tank = 0 + 4 = 4
Travel to station 0\. Your tank = 4 - 3 + 2 = 3
Travel to station 1\. Your tank = 3 - 3 + 3 = 3
You cannot travel back to station 2, as it requires 4 unit of gas but you only have 3.
Therefore, you can't travel around the circuit once no matter where you start.

Solution

Language: Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int canCompleteCircuit(int[] gas, int[] cost) {
        int sum=0; // 统计总汽油
        int tempGas = 0;
        int pos = -1;
        for(int i=0;i<gas.length;++i){
            sum += gas[i]-cost[i];
            
            tempGas += gas[i] - cost[i];　
            
            if(tempGas<0){　// 如果某一站油不够用，把下一站当起点
                pos = i+1;
                tempGas = 0;
            }
        }
        
        return sum<0?-1:pos;
        
    }
}

展开全文 >>

Subsets II

90. Subsets II

Difficulty: Medium

Given a collection of integers that might contain duplicates, nums, return all possible subsets (the power set).

Note: The solution set must not contain duplicate subsets.

Example:

1
2
3
4
5
6
7
8
9
10
**Input:** [1,2,2]
**Output:**
[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Solution

Language: Java

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
class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<List<Integer>> result = new LinkedList<>();
        if(nums.length==0)return result;
        
        Arrays.sort(nums);
        
        dfs(nums, 0, new LinkedList<Integer>(), result);
        
        return result;
    }
    
    
    
    public void dfs(int[] nums, int index, LinkedList<Integer>path, List<List<Integer>> result){
        result.add(new LinkedList<Integer>(path));
        
        for(int i=index;i<nums.length;++i){
            if(i>index&& nums[i]==nums[i-1])continue;
            path.addLast(nums[i]);
            dfs(nums, i+1, path, result);
            path.removeLast();
        }
    }
}

展开全文 >>

Combinations

77. Combinations

Difficulty: Medium

Given two integers _n_ and _k_, return all possible combinations of _k_ numbers out of 1 … _n_.

Example:

1
2
3
4
5
6
7
8
9
10
**Input:** n = 4, k = 2
**Output:**
[
  [2,4],
  [3,4],
  [2,3],
  [1,2],
  [1,3],
  [1,4],
]

Solution

Language: Java

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution {
    public List<List<Integer>> combine(int n, int k) {
        List<List<Integer>> result = new LinkedList<>();
        
        dfs(n, k, 1, new LinkedList<Integer>(), result);
        return result;
    }
    
    public void dfs(int n, int k, int pos, LinkedList<Integer>path, List<List<Integer>>result){
        if(path.size() == k){
            result.add(new LinkedList<Integer>(path));
            return;
        }
        
        for(int i=pos;i<=n;i++){
            path.addLast(i);
            dfs(n, k, i+1, path, result);
            path.removeLast();
        }
    }
}

展开全文 >>

Word Search

Difficulty: Medium

Given a 2D board and a word, find if the word exists in the grid.

The word can be constructed from letters of sequentially adjacent cell, where “adjacent” cells are those horizontally or vertically neighboring. The same letter cell may not be used more than once.

Example:

1
2
3
4
5
6
7
8
9
10
board =
[
  ['A','B','C','E'],
  ['S','F','C','S'],
  ['A','D','E','E']
]

Given word = "**ABCCED**", return **true**.
Given word = "**SEE**", return **true**.
Given word = "**ABCB**", return **false**.

Solution

Language: Java

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
45
46
47
48
49
50
51
class Solution {
    public boolean exist(char[][] board, String word) {
        if(null==board || board.length==0)return false;
        
        int h = board.length;
        int w = board[0].length;
        
        
        boolean flag = false;
        for(int i=0;i<h&&flag==false;i++){
            for(int j=0;j<w&&flag==false;j++){
                if(board[i][j]==word.charAt(0)){
                    int[][] visited = new int[h][w];
                    //System.out.println("find start:"+i+" "+j);
                    if(dfs(board, visited, i, j, word, 0)){
                        flag = true;
                        break;
                    }
                }
            }
        }
        
        return flag;
    }
    
    public boolean dfs(char[][] board, int[][] visited, int i, int j, String word, int pos){
        // 退出条件
        int h = visited.length;
        int w = visited[0].length;
        if(pos>=word.length())return true;
        if(i<0||i>=h||j<0||j>=w)return false;
        
        if(visited[i][j]==1)return false;
        
        // 如果当前匹配正确
        if(word.charAt(pos) == board[i][j]){
            visited[i][j] = 1;
            //System.out.println("find "+board[i][j]+i+" "+j+" ");
            
            // 四个方向继续
            if(dfs(board, visited, i, j+1, word, pos+1))return true;
            if(dfs(board, visited, i, j-1, word, pos+1))return true;
            if(dfs(board, visited, i+1, j, word, pos+1))return true;
            if(dfs(board, visited, i-1, j, word, pos+1))return true;
            
            // 如果四个方向都没有找到，还原
            visited[i][j] = 0;
        }
        return false;      
    }
}

展开全文 >>

tag:

    缺失模块。
    1、请确保node版本大于6.2
    2、在博客根目录（注意不是yilia根目录）执行以下命令：
    npm i hexo-generator-json-content --save

    3、在根目录_config.yml里添加配置： 

      jsonContent:
    meta: false
    pages: false
    posts:
      title: true
      date: true
      path: true
      text: false
      raw: false
      content: false
      slug: false
      updated: false
      comments: false
      link: false
      permalink: false
      excerpt: false
      categories: false
      tags: true

很惭愧<br><br>只做了一点微小的工作<br>谢谢大家