1
2
3
4
输入：
[2, 3, 1, 0, 2, 5, 3]
输出：2 或 3

1
2
2 <= n <= 100000

1
2
3
4
5
6
7
8
9
10
class Solution:
    def findRepeatNumber(self, nums: List[int]) -> int:
        for i, num in enumerate(nums):
            while i != num:
                if num == nums[num]:
                    return num
                nums[i], nums[num] = nums[num], nums[i]
                num = nums[i]
        return -1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
class Solution {
    public int findRepeatNumber(int[] nums) {
        for (int i = 0, n = nums.length; i < n; ++i) {
            while (nums[i] != i) {
                if (nums[i] == nums[nums[i]]) return nums[i];
                swap(nums, i, nums[i]);
            }
        }
        return -1;
    }

    private void swap(int[] nums, int i, int j) {
        int t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    fun findRepeatNumber(nums: IntArray): Int {
        for (i in nums.indices) {
            while (i != nums[i]) {
                if (nums[i] == nums[nums[i]]) {
                    return nums[i];
                }
                swap(nums, i, nums[i]);
            }
        }
        return -1;
    }

    fun swap(nums: IntArray, i: Int, j: Int) {
        var t = nums[i];
        nums[i] = nums[j];
        nums[j] = t;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
/**
 * @param {number[]} nums
 * @return {number}
 */
var findRepeatNumber = function (nums) {
  let m = {};
  for (let num of nums) {
    if (m[num]) return num;
    m[num] = 1;
  }
};

1
2
3
4
5
6
7
8
9
10
11
12
func findRepeatNumber(nums []int) int {
    for i := 0; i < len(nums); i++ {
        for nums[i] != i {
            if nums[i] == nums[nums[i]] {
                return nums[i]
            }
            nums[i], nums[nums[i]] = nums[nums[i]], nums[i]
        }
    }
    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:
    int findRepeatNumber(vector<int>& nums) {
        int len = nums.size();
        for (int i = 0; i < len; i++) {
            while (i != nums[i]) {
                // 这一位的值，不等于这一位的数字
                if (nums[i] == nums[nums[i]]) {
                    // 如果在交换的过程中，发现了相等的数字，直接返回
                    return nums[i];
                }

                swap(nums[i], nums[nums[i]]);
            }
        }

        return 0;
    }
};

1
2

1
2
3
4
5
6
7
8
[
  [1,   4,  7, 11, 15],
  [2,   5,  8, 12, 19],
  [3,   6,  9, 16, 22],
  [10, 13, 14, 17, 24],
  [18, 21, 23, 26, 30]
]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
class Solution:
    def findNumberIn2DArray(self, matrix: List[List[int]], target: int) -> bool:
        if not matrix or not matrix[0]:
            return False
        rows, cols = len(matrix), len(matrix[0])
        i, j = rows - 1, 0
        while i >= 0 and j < cols:
            if matrix[i][j] == target:
                return True
            if matrix[i][j] > target:
                i -= 1
            else:
                j += 1
        return False

1
2
3
4
5
6
7
8
9
10
11
12
13
14
class Solution {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        int m, n;
        if (matrix == null || (m = matrix.length) == 0 || matrix[0] == null || (n = matrix[0].length) == 0) return false;
        int i = 0, j = n - 1;
        while (i < m && j >= 0) {
            if (matrix[i][j] == target) return true;
            if (matrix[i][j] > target) --j;
            else ++i;
        }
        return false;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
/**
 * @param {number[][]} matrix
 * @param {number} target
 * @return {boolean}
 */
var findNumberIn2DArray = function (matrix, target) {
  let row = matrix.length;
  let col = matrix[0].length;
  function dfs(i, j) {
    if (i < 0 || j >= col) {
      return false;
    }
    if (matrix[i][j] === target) return true;
    else if (matrix[i][j] > target) {
      return dfs(i - 1, j);
    } else {
      return dfs(i, j + 1);
    }
  }
  return dfs(row - 1, 0);
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
func findNumberIn2DArray(matrix [][]int, target int) bool {
    if len(matrix) == 0 {
        return false
    }
    rows, cols := len(matrix), len(matrix[0])
    i, j := rows - 1, 0
    for i >= 0 && j < cols {
        if matrix[i][j] == target {
            return true
        }
        if matrix[i][j] > target {
            i--
        } else {
            j++
        }
    }
    return false
}

1
2

1
2
3
输入：s = "We are happy."
输出："We%20are%20happy."

1
2
3
4
class Solution:
    def replaceSpace(self, s: str) -> str:
        return s.replace(' ', '%20')

1
2
3
4
5
6
class Solution {
    public String replaceSpace(String s) {
        return s.replaceAll(" ", "%20");
    }
}

1
2
3
4
5
6
7
8
9
10
11
class Solution {
    public String replaceSpace(String s) {
        StringBuilder sb = new StringBuilder();
        char[] chars = s.toCharArray();
        for (char c : chars) {
            sb.append(c == ' ' ? "%20" : c);
        }
        return sb.toString();
    }
}

1
2
3
4
5
6
7
8
/**
 * @param {string} s
 * @return {string}
 */
var replaceSpace = function (s) {
  return s.split(" ").join("%20");
};

1
2
3
4
func replaceSpace(s string) string {
    return strings.Replace(s, " ", "%20", -1 )
}

1
2

1
2
3
输入：head = [1,3,2]
输出：[2,3,1]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
# Definition for singly-linked list.
# class ListNode:
#     def __init__(self, x):
#         self.val = x
#         self.next = None

class Solution:
    def reversePrint(self, head: ListNode) -> List[int]:
        res = []
        while head:
            res.append(head.val)
            head = head.next
        return res[::-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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        Stack<Integer> s = new Stack<>();
        while (head != null) {
            s.push(head.val);
            head = head.next;
        }
        int[] res = new int[s.size()];
        int i = 0;
        while (!s.isEmpty()) {
            res[i++] = s.pop();
        }
        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
/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode(int x) { val = x; }
 * }
 */
class Solution {
    public int[] reversePrint(ListNode head) {
        if (head == null) return new int[]{};
        // 计算链表长度n
        int n = 0;
        ListNode cur = head;
        while (cur != null) {
            ++n;
            cur = cur.next;
        }
        int[] res = new int[n];
        cur = head;
        while (cur != null) {
            res[--n] = cur.val;
            cur = cur.next;
        }
        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
/**
 * Definition for singly-linked list.
 * type ListNode struct {
 *     Val int
 *     Next *ListNode
 * }
 */
//insert to the front
func reversePrint(head *ListNode) []int {
	res := []int{}
	for head != nil {
		res = append([]int{head.Val}, res...)
		head = head.Next
	}
	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
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     ListNode *next;
 *     ListNode(int x) : val(x), next(NULL) {}
 * };
 */
class Solution {
public:
    vector<int> ret;

    void getVal(ListNode* head) {
        // 这里可以看成是一个节点的树
        if (head) {
            if (head->next) {
                getVal(head->next);
            }
            ret.push_back(head->val);
        }
    }

    vector<int> reversePrint(ListNode* head) {
        getVal(head);
        // 返回的是全局的ret信息。在getVal函数中被赋值
        return ret;
    }
};

1
2

1
2
3
前序遍历 preorder = [3,9,20,15,7]
中序遍历 inorder = [9,3,15,20,7]

1
2
3
4
5
6
    3
   / 
  9  20
    /  
   15   7

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
# Definition for a binary tree node.
# class TreeNode:
#     def __init__(self, x):
#         self.val = x
#         self.left = None
#         self.right = None

class Solution:
    indexes = {}
    def buildTree(self, preorder: List[int], inorder: List[int]) -> TreeNode:
        def build(preorder, inorder, p1, p2, i1, i2) -> TreeNode:
            if p1 > p2 or i1 > i2:
                return None
            root_val = preorder[p1]
            pos = self.indexes[root_val]
            root = TreeNode(root_val)
            root.left = None if pos == i1 else build(preorder, inorder, p1 + 1, p1 - i1 + pos, i1, pos - 1)
            root.right = None if pos == i2 else build(preorder, inorder, p1 - i1 + pos + 1, p2, pos + 1, i2)
            return root
        n = len(inorder)
        for i in range(n):
            self.indexes[inorder[i]] = i
        return build(preorder, inorder, 0, n - 1, 0, n - 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
/**
 * Definition for a binary tree node.
 * public class TreeNode {
 *     int val;
 *     TreeNode left;
 *     TreeNode right;
 *     TreeNode(int x) { val = x; }
 * }
 */
class Solution {
    private Map<Integer, Integer> indexes = new HashMap<>();

    public TreeNode buildTree(int[] preorder, int[] inorder) {
        int n = inorder.length;
        for (int i = 0; i < n; ++i) {
            indexes.put(inorder[i], i);
        }
        return build(preorder, inorder, 0, n - 1, 0, n - 1);
    }

    private TreeNode build(int[] preorder, int[] inorder, int p1, int p2, int i1, int i2) {
        if (p1 > p2 || i1 > i2) return null;
        int rootVal = preorder[p1];
        int pos = indexes.get(rootVal);
        TreeNode node = new TreeNode(rootVal);
        node.left = pos == i1 ? null : build(preorder, inorder, p1 + 1, pos - i1 + p1, i1, pos - 1);
        node.right = pos == i2 ? null : build(preorder, inorder, pos - i1 + p1 + 1, p2, pos + 1, i2);
        return node;
    }
}

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
/**
 * Definition for a binary tree node.
 * function TreeNode(val) {
 *     this.val = val;
 *     this.left = this.right = null;
 * }
 */
/**
 * @param {number[]} preorder
 * @param {number[]} inorder
 * @return {TreeNode}
 */
var buildTree = function (preorder, inorder) {
  if (!preorder || !preorder.length) return null;
  let preIdx = 0;
  let inMap = {};
  for (let i = 0; i < inorder.length; i++) {
    inMap[inorder[i]] = i;
  }
  function func(start, end) {
    if (start > end) {
      return null;
    }
    let preVal = preorder[preIdx];
    preIdx++;
    let inIdx = inMap[preVal];
    let node = new TreeNode(preVal);
    node.left = func(start, inIdx - 1);
    node.right = func(inIdx + 1, end);
    return node;
  }
  return func(0, preorder.length - 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
/**
 * Definition for a binary tree node.
 * type TreeNode struct {
 *     Val int
 *     Left *TreeNode
 *     Right *TreeNode
 * }
 */
func buildTree(preorder []int, inorder []int) *TreeNode {
    return helper(preorder, inorder, 0, 0, len(preorder)-1)
}

func helper(preorder, inorder []int, index, start, end int) *TreeNode {
    if start > end {
        return nil
    }
    root := &TreeNode{Val:preorder[index]}
    j := start
    for j < end && preorder[index] != inorder[j] {
        j++
    }
    root.Left = helper(preorder, inorder, index + 1, start, j - 1)
    root.Right = helper(preorder, inorder, index + 1 + j -start, j + 1, end)
    return root
}

1
2

1
2
3
4
5
输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]

1
2
3
4
5
输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,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
class CQueue:

    def __init__(self):
        self.s1 = []
        self.s2 = []

    def appendTail(self, value: int) -> None:
        self.s1.append(value)
        if not self.s2:
            self._move()

    def deleteHead(self) -> int:
        if not self.s2:
            self._move()
        return -1 if not self.s2 else self.s2.pop()

    def _move(self):
        while self.s1:
            self.s2.append(self.s1.pop())



# Your CQueue object will be instantiated and called as such:
# obj = CQueue()
# obj.appendTail(value)
# param_2 = obj.deleteHead()

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
class CQueue {

    private Deque<Integer> s1;
    private Deque<Integer> s2;
    public CQueue() {
        s1 = new ArrayDeque<>();
        s2 = new ArrayDeque<>();
    }

    public void appendTail(int value) {
        s1.push(value);
        if (s2.isEmpty()) {
            move();
        }
    }

    public int deleteHead() {
        if (s2.isEmpty()) {
            move();
        }
        return s2.isEmpty() ? -1 : s2.pop();
    }

    private void move() {
        while (!s1.isEmpty()) {
            s2.push(s1.pop());
        }
    }
}

/**
 * Your CQueue object will be instantiated and called as such:
 * CQueue obj = new CQueue();
 * obj.appendTail(value);
 * int param_2 = obj.deleteHead();
 */

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
var CQueue = function () {
  this.data = [];
  this.helper = [];
};
/**
 * @param {number} value
 * @return {void}
 */
CQueue.prototype.appendTail = function (value) {
  this.data.push(value);
};
/**
 * @return {number}
 */
CQueue.prototype.deleteHead = function () {
  if (this.data.length) {
    while (this.data.length > 1) {
      this.helper.push(this.data.pop());
    }
    let res = this.data.pop();
    while (this.helper.length) {
      this.data.push(this.helper.pop());
    }
    return res;
  } else {
    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
32
33
34
type CQueue struct {
	Stack1 []int
	Stack2 []int
}

// 入队都往S1压入，弹出时判定S2是否为空，S2非空则弹出S2顶，否则，S1的元素从栈顶依次入S2
//再从S2弹出

func Constructor() CQueue {
	return CQueue{Stack1: []int{}, Stack2: []int{}}
}

func (this *CQueue) AppendTail(value int) {
	this.Stack1 = append(this.Stack1, value)
}

func (this *CQueue) DeleteHead() int {
	if len(this.Stack1) == 0 && len(this.Stack2) == 0 {
		return -1
	}
	if len(this.Stack2) > 0 {
		res := this.Stack2[len(this.Stack2)-1]
		this.Stack2 = this.Stack2[0 : len(this.Stack2)-1]
		return res
	}
	for len(this.Stack1) > 0 {
		this.Stack2 = append(this.Stack2, this.Stack1[len(this.Stack1)-1])
		this.Stack1 = this.Stack1[0 : len(this.Stack1)-1]
	}
	res := this.Stack2[len(this.Stack2)-1]
	this.Stack2 = this.Stack2[0 : len(this.Stack2)-1]
	return res
}

1
2

1
2
3
F(0) = 0,   F(1) = 1
F(N) = F(N - 1) + F(N - 2), 其中 N > 1.

1
2
3
输入：n = 2
输出：1

1
2
3
输入：n = 5
输出：5

1
2
3
4
5
6
7
class Solution:
    def fib(self, n: int) -> int:
        a, b = 0, 1
        for _ in range(n):
            a, b = b, a + b
        return a % 1000000007

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int fib(int n) {
        int a = 0, b = 1;
        for (int i = 0; i < n; ++i) {
            int c = (a + b) % 1000000007;
            a = b;
            b = c;
        }
        return a;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number} n
 * @return {number}
 */
var fib = function (n) {
  if (!n) return 0;
  let pre = 0;
  let cur = 1;
  for (let i = 2; i <= n; i++) {
    let c = (pre + cur) % (1e9 + 7);
    pre = cur;
    cur = c;
  }
  return cur;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
func fib(n int) int {
    if n < 2 {
        return n
    }
    a := make([]int,n+1)
    a[0]=0
    a[1]=1
    for i := 2; i < n+1; i++ {
        a[i] = (a[i-1]+ a[i-2])%1000000007
    }
    return a[n]
}

1
2

1
2
3
输入：n = 2
输出：2

1
2
3
输入：n = 7
输出：21

1
2
3
4
5
6
7
class Solution:
    def numWays(self, n: int) -> int:
        a, b = 0, 1
        for _ in range(n):
            a, b = b, a + b
        return b % 1000000007

1
2
3
4
5
6
7
8
9
10
11
12
class Solution {
    public int numWays(int n) {
        int a = 0, b = 1;
        for (int i = 0; i < n; ++i) {
            int s = (a + b) % 1000000007;
            a = b;
            b = s;
        }
        return b;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * @param {number} n
 * @return {number}
 */
var numWays = function (n) {
  if (!n) return 1;
  let pre = 1;
  let cur = 1;
  for (let i = 2; i <= n; i++) {
    let c = (pre + cur) % (1e9 + 7);
    pre = cur;
    cur = c;
  }
  return cur;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
func numWays(n int) int {
	if n == 0 {
		return 1
	}
	if n <= 2 {
		return n
	}
	a := make([]int, n)
	a[0] = 1
	a[1] = 2
	for i := 2; i < n; i++ {
		a[i] = (a[i-1] + a[i-2]) % 1000000007
	}
	return a[n-1]
}

1
2

1
2
3
输入：[3,4,5,1,2]
输出：1

1
2
3
输入：[2,2,2,0,1]
输出：0

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution:
    def minArray(self, numbers: List[int]) -> int:
        l, r = 0, len(numbers) - 1
        while l < r:
            m = l + ((r - l) >> 1)
            if numbers[m] > numbers[r]:
                l = m + 1
            elif numbers[m] < numbers[r]:
                r = m
            else:
                r -= 1
        return numbers[l]

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
class Solution {
    public int minArray(int[] numbers) {
        int l = 0, r = numbers.length - 1;
        while (l < r) {
            int m = l + ((r - l) >> 1);
            if (numbers[m] > numbers[r]) {
                l = m + 1;
            } else if (numbers[m] < numbers[r]) {
                r = m;
            } else {
                --r;
            }
        }
        return numbers[l];
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * @param {number[]} numbers
 * @return {number}
 */
var minArray = function (numbers) {
  // return Math.min(...numbers)
  let left = 0;
  let right = numbers.length - 1;
  while (left < right) {
    let mid = left + ~~((right - left) / 2);
    if (numbers[mid] > numbers[right]) {
      left = mid + 1;
    } else if (numbers[mid] === numbers[right]) {
      right--;
    } else {
      right = mid;
    }
  }
  return numbers[left];
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
func minArray(nums []int) int {
	l, r := 0, len(nums)-1
	for l < r {
		mid := l + (r-l)>>1
		if nums[mid] > nums[r] {
			l = mid + 1
		} else if nums[mid] < nums[r] {
			r = mid //r 本身不需要被排除
		} else {
			r--
		}
	}
	return nums[l]
}

1
2

1
2
3
4
[["a","b","c","e"],
["s","f","c","s"],
["a","d","e","e"]]

1
2
3
输入：board = [["A","B","C","E"],["S","F","C","S"],["A","D","E","E"]], word = "ABCCED"
输出：true

1
2
3
输入：board = [["a","b"],["c","d"]], word = "abcd"
输出：false

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
class Solution:
    def exist(self, board: List[List[str]], word: str) -> bool:
        def dfs(i, j, cur):
            if cur == len(word):
                return True
            if i < 0 or i >= m or j < 0 or j >= n or visited[i][j] or word[cur] != board[i][j]:
                return False
            visited[i][j] = True
            next = cur + 1
            res = dfs(i + 1, j, next) or dfs(i - 1, j, next) or dfs(i, j + 1, next) or dfs(i, j - 1, next)
            visited[i][j] = False
            return res
        m, n = len(board), len(board[0])
        visited = [[False for _ in range(n)] for _ in range(m)]
        for i in range(m):
            for j in range(n):
                res = dfs(i, j, 0)
                if res:
                    return True
        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
27
28
29
30
31
class Solution {
    private boolean[][] visited;

    public boolean exist(char[][] board, String word) {
        int m = board.length, n = board[0].length;
        visited = new boolean[m][n];
        char[] chars = word.toCharArray();
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                boolean res = dfs(board, i, j, chars, 0);
                if (res) return true;
            }
        }
        return false;
    }

    private boolean dfs(char[][] board, int i, int j, char[] chars, int cur) {
        if (cur == chars.length) return true;
        if (i < 0 || i >= board.length || j < 0 || j >= board[0].length) return false;
        if (visited[i][j] || board[i][j] != chars[cur]) return false;
        visited[i][j] = true;
        int next = cur + 1;
        boolean res = dfs(board, i + 1, j, chars, next)
                || dfs(board, i - 1, j, chars, next)
                || dfs(board, i, j + 1, chars, next)
                || dfs(board, i, j - 1, chars, next);
        visited[i][j] = false;
        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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
/**
 * @param {character[][]} board
 * @param {string} word
 * @return {boolean}
 */
var exist = function (board, word) {
  let row = board.length;
  let col = board[0].length;
  let res = false;
  let isRead = [...new Array(row)].map(() => Array(col).fill(0));
  for (let i = 0; i < row; i++) {
    for (let j = 0; j < col; j++) {
      if (res) break;
      if (board[i][j] === word[0]) {
        dfs(i, j, word);
      }
    }
  }
  function dfs(i, j, word) {
    if (
      i < 0 ||
      j < 0 ||
      i >= row ||
      j >= col ||
      res ||
      isRead[i][j] ||
      board[i][j] !== word[0]
    ) {
      return;
    }
    isRead[i][j] = 1;
    word = word.substring(1);
    if (word.length) {
      dfs(i - 1, j, word);
      dfs(i + 1, j, word);
      dfs(i, j - 1, word);
      dfs(i, j + 1, word);
    } else {
      res = true;
      return;
    }
    isRead[i][j] = 0;
  }
  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
30
31
32
33
34
35
36
37
func exist(board [][]byte, word string) bool {
	if len(board) == 0 {
		return false
	}
	//标记数组
	isVisited := make([][]bool, len(board))
	for i := 0; i < len(board); i++ {
		isVisited[i] = make([]bool, len(board[0]))
	}
	for i := 0; i < len(board); i++ {
		for j := 0; j < len(board[0]); j++ {
			if board[i][j] == word[0] {
				if bfs(board, i, j, isVisited, word, 0) {
					return true
				}
			}
		}
	}
	return false
}

func bfs(board [][]byte, i, j int, isVisited [][]bool, word string, index int) bool {
	if index == len(word) {
		return true
	}
	if i < 0 || j < 0 || i == len(board) || j == len(board[0]) || isVisited[i][j] || board[i][j] != word[index] {
		return false
	}
	isVisited[i][j] = true
	res := bfs(board, i+1, j, isVisited, word, index+1) ||
		bfs(board, i, j+1, isVisited, word, index+1) ||
		bfs(board, i-1, j, isVisited, word, index+1) ||
		bfs(board, i, j-1, isVisited, word, index+1)
	isVisited[i][j] = false
	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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
class Solution {
public:
    bool dfs(vector<vector<char>>& board, string& word, int cur, int x, int y) {
        if (board[x][y] != word[cur]) {
            return false;
        }

        if (cur == word.size()-1) {
            return true;
        }

        char t = board[x][y];
        board[x][y] = '*';    // 表示查询过了这个字段
        int dx[4] = {-1, 0, 1, 0};
        int dy[4] = {0, 1, 0, -1};
        for (int k = 0; k < 4; k++) {
            // 从上、右、下、左四个方向，开始dfs
            int a = x + dx[k], b = y + dy[k];
            if (a >= 0 && a < board.size() && b >= 0 && b < board[0].size()) {
                if (dfs(board, word, cur+1, a, b)) {
                    return true;
                }
            }
        }

        board[x][y] = t;
        return false;
    }

    bool exist(vector<vector<char>>& board, string word) {
        int x = board.size();
        int y = board[0].size();
        if (0 == x || 0 == y) {
            return false;
        }

        for (int i = 0; i < x; i++) {
            for (int j = 0; j < y; j++) {
                if (dfs(board, word, 0, i, j)) {
                    return true;
                }
            }
        }

        return false;
    }
};

1
2

1
2
3
输入：m = 2, n = 3, k = 1
输出：3

1
2
3
输入：m = 3, n = 1, k = 0
输出：1

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution:
    cnt = 0
    def movingCount(self, m: int, n: int, k: int) -> int:
        def cal(m, n):
            s = str(m) + str(n)
            return sum([int(i) for i in s])
        def dfs(i, j):
            if i < 0 or i >= m or j < 0 or j >= n or cal(i, j) > k or visited[i][j]:
                return
            self.cnt += 1
            visited[i][j] = True
            dfs(i + 1, j)
            dfs(i - 1, j)
            dfs(i, j + 1)
            dfs(i, j - 1)
        self.cnt = 0
        visited = [[False for _ in range(n)] for _ in range(m)]
        dfs(0, 0)
        return self.cnt

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 {
    private int m;
    private int n;
    private boolean[][] visited;
    private int cnt;
    public int movingCount(int m, int n, int k) {
        visited = new boolean[m][n];
        this.m = m;
        this.n = n;
        cnt = 0;
        dfs(0, 0, k);
        return cnt;
    }

    private void dfs(int i, int j, int k) {
        if (i < 0 || i >= m || j < 0 || j >= n || visited[i][j] || cal(i, j) > k) return;
        ++cnt;
        visited[i][j] = true;
        dfs(i + 1, j, k);
        dfs(i - 1, j, k);
        dfs(i, j + 1, k);
        dfs(i, j - 1, k);
    }

    private int cal(int i, int j) {
        int res = 0;
        while (i != 0) {
            res += (i % 10);
            i /= 10;
        }
        while (j != 0) {
            res += (j % 10);
            j /= 10;
        }
        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
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
/**
 * @param {number} m
 * @param {number} n
 * @param {number} k
 * @return {number}
 */
var movingCount = function (m, n, k) {
  let res = 0;
  let isRead = [...new Array(m)].map(() => Array(n).fill(0));
  let moving = [
    [0, -1],
    [0, 1],
    [1, 0],
    [-1, 0],
  ];
  let queue = [[0, 0]];
  isRead[0][0] = 1;
  while (queue.length) {
    let [x, y] = queue.shift();
    for (let [dx, dy] of moving) {
      let X = x + dx;
      let Y = y + dy;
      if (
        X >= 0 &&
        Y >= 0 &&
        X < m &&
        Y < n &&
        !isRead[X][Y] &&
        isValid(X, Y)
      ) {
        queue.push([X, Y]);
        isRead[X][Y] = 1;
      }
    }
    res++;
  }
  function isValid(x, y) {
    let r = 0;
    r +=
      x
        .toString()
        .split("")
        .reduce((acc, cur) => acc + +cur, 0) +
      y
        .toString()
        .split("")
        .reduce((acc, cur) => acc + +cur, 0);
    if (r <= k) return true;
    else return false;
  }
  return res;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
func movingCount(m int, n int, k int) int {
	var visited [][]bool
	visited = make([][]bool, m)
	for i := 0; i < m; i++ {
		visited[i] = make([]bool, n)
	}
	return dfs(0, 0, m, n, k, visited)
}

func dfs(x, y, m, n, k int, visited [][]bool) int {
	if x >= m || y >= n || visited[x][y] || (x%10+x/10+y%10+y/10) > k {
		return 0
	}
	visited[x][y] = true
	return 1 + dfs(x+1, y, m, n, k, visited) + dfs(x, y+1, m, n, k, visited)
}

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 checksum(int m, int n, int target) {
        int a = 0;
        while (m > 0) {
            a += m % 10;
            m /= 10;
        }

        int b = 0;
        while (n > 0) {
            b += n % 10;
            n /= 10;
        }

        return a + b <= target;
    }

    int moving(int row, int col, vector<vector<int>>& arr, int i, int j, int target) {
        int count = 0;
        if (checksum(i, j, target)
            && i>=0 && i < row && j>=0 && j < col
            && arr[i][j] == 0) {
            arr[i][j] = 1;
            count = 1 + moving(row, col, arr, i-1, j, target)
                    + moving(row, col, arr, i, j-1, target)
                    + moving(row, col, arr, i+1, j, target)
                    + moving(row, col, arr, i, j+1, target);
        }

        return count;
    }

    int movingCount(int m, int n, int k) {
        if (m == 0 || n == 0) {
            return 0;
        }

        vector<vector<int>> arr(m, vector<int>(n, 0));
        int cnt = moving(m, n, arr, 0, 0, k);
        return cnt;
    }
};

1
2

1
2
3
4
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

1
2
3
4
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def cuttingRope(self, n: int) -> int:
        if n < 4:
            return n - 1
        res = 1
        while n > 4:
            res *= 3
            n -= 3
        if n == 4:
            return res << 2
        return res * n

1
2
3
4
5
6
7
8
9
10
11
12
13
class Solution {
    public int cuttingRope(int n) {
        if (n < 4) return n - 1;
        int res = 1;
        while (n > 4) {
            res *= 3;
            n -= 3;
        }
        if (n == 4) return res << 2;
        return res * 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
/**
 * @param {number} n
 * @return {number}
 */
var cuttingRope = function (n) {
  // 数学方法
  if (n <= 3) return n - 1;
  let a = ~~(n / 3);
  let b = n % 3;
  if (b === 1) {
    return 3 ** (a - 1) * 2 * 2;
  }
  if (b === 0) return 3 ** a;
  return 3 ** a * b;
  // dp 方法
  // let dp = new Array(n+1).fill(0)
  // dp[0] = 1
  // for(let i=1;i<n;i++) {
  //     for(let j=i;j<=n;j++) {
  //         dp[j] = Math.max(dp[j],dp[j-i] * i)
  //     }
  // }
  // return dp[n]
};

1
2
3
4
5
6
7
8
9
10
11
12
func cuttingRope(n int) int {
	if n <= 3 {
		return n - 1
	}
	sum := 1
	for n > 4 {
		sum *= 3
		n -= 3
	}
	return sum * n
}

1
2

1
2
3
4
输入: 2
输出: 1
解释: 2 = 1 + 1, 1 × 1 = 1

1
2
3
4
输入: 10
输出: 36
解释: 10 = 3 + 3 + 4, 3 × 3 × 4 = 36

1
2
3
4
5
6
7
8
9
10
11
12
class Solution:
    def cuttingRope(self, n: int) -> int:
        if n < 4:
            return n - 1
        res = 1
        while n > 4:
            res *= 3
            n -= 3
        if n == 4:
            return (res << 2) % 1000000007
        return (res * n) % 1000000007

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int cuttingRope(int n) {
        if (n < 4) {
            return n - 1;
        }
        int s1 = n / 3;
        int m = n % 3;
        if (m == 1) {
            s1 -= 1;
            m = 4;
        }
        long res = 1;
        while (s1-- > 0) {
            res *= 3;
            res %= 1000000007;
        }
        return (int) ((res * (m == 0 ? 1 : m)) % 1000000007);
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
/**
 * @param {number} n
 * @return {number}
 */
var cuttingRope = function (n) {
  if (n <= 3) return n - 1;
  let a = ~~(n / 3);
  let b = n % 3;
  const MOD = 1e9 + 7;
  function myPow(x) {
    let r = 1;
    for (let i = 0; i < x; i++) {
      r = (r * 3) % MOD;
    }
    return r;
  }
  if (b === 1) {
    return (myPow(a - 1) * 4) % MOD;
  }
  if (b === 0) return myPow(a) % MOD;
  return (myPow(a) * 2) % MOD;
};

1
2
3
4
5
6
7
8
9
10
11
12
13
func cuttingRope(n int) int {
	if n <= 3 {
		return n - 1
	}
	sum := 1
	for n > 4 {
		sum *= 3
		sum = sum % 1000000007
		n -= 3
	}
	return sum * n % 1000000007
}

1
2

1
2
3
4
输入：00000000000000000000000000001011
输出：3
解释：输入的二进制串 00000000000000000000000000001011 中，共有三位为 '1'。

1
2
3
4
输入：00000000000000000000000010000000
输出：1
解释：输入的二进制串 00000000000000000000000010000000 中，共有一位为 '1'。

1
2
3
4
输入：11111111111111111111111111111101
输出：31
解释：输入的二进制串 11111111111111111111111111111101 中，共有 31 位为 '1'。

1
2
3
4
5
6
7
8
class Solution:
    def hammingWeight(self, n: int) -> int:
        res = 0
        while n:
            n &= (n - 1)
            res += 1
        return res

1
2
3
4
5
6
7
8
9
10
11
12
public class Solution {
    // you need to treat n as an unsigned value
    public int hammingWeight(int n) {
        int res = 0;
        while (n != 0) {
            n &= (n - 1);
            ++res;
        }
        return res;
    }
}

1
2
3
4
5
6
7
8
9
10
11
12
13
/**
 * @param {number} n - a positive integer
 * @return {number}
 */
var hammingWeight = function (n) {
  let cnt = 0;
  while (n) {
    cnt += n & 1;
    n >>>= 1;
  }
  return cnt;
};

1
2
3
4
5
6
7
8
9
10
func hammingWeight(num uint32) int {
	ans := 0
	// num &=num-1 消除最右边的1
	for num != 0 {
		num &= num - 1
		ans++
	}
	return ans
}