# 参考《leetcode 题解，记录自己的 leetcode 解题之路》练脑 （一）

## Problem：number-of-1-bits

https://leetcode.com/problems/number-of-1-bits/description/

``````Write a function that takes an unsigned integer and return the number of '1' bits it has (also known as the Hamming weight).

Example 1:

Input: 00000000000000000000000000001011
Output: 3
Explanation: The input binary string 00000000000000000000000000001011 has a total of three '1' bits.
Example 2:

Input: 00000000000000000000000010000000
Output: 1
Explanation: The input binary string 00000000000000000000000010000000 has a total of one '1' bit.
Example 3:

Input: 11111111111111111111111111111101
Output: 31
Explanation: The input binary string 11111111111111111111111111111101 has a total of thirty one '1' bits.

Note:

Note that in some languages such as Java, there is no unsigned integer type. In this case, the input will be given as signed integer type and should not affect your implementation, as the internal binary representation of the integer is the same whether it is signed or unsigned.
In Java, the compiler represents the signed integers using 2's complement notation. Therefore, in Example 3 above the input represents the signed integer -3.``````

``````function hammingWeight(n) {
let count = 0;
while (n !== 0) {
count += n & 1;
n = n>>1;
}

return count;
}

// hammingWeight(3)
// =>2
// hammingWeight(4)
// =>1
// hammingWeight(11)
// =>3``````

## Problem：sum-of-two-integers

https://leetcode.com/problems/sum-of-two-integers/description/

``````Calculate the sum of two integers a and b, but you are not allowed to use the operator + and -.

Example 1:

Input: a = 1, b = 2
Output: 3
Example 2:

Input: a = -2, b = 3
Output: 1``````

``````
// References from https://github.com/azl397985856/leetcode/blob/master/problems/371.sum-of-two-integers.md
var getTwoSum = function(a, b) {
if (a === 0) return b;

if (b === 0) return a;

return getSum(a ^ b, (a & b) << 1);
};

// Extension: sum-of-n-integers
var getSum = function() {
const args = [...arguments]
return (
args.reduce((sum, cur) => getTwoSum(sum, cur), 0)
};
// getSum(4)
// =>4

// getSum(4, 5)
// =>9

// getSum(1, 4, 5)
// =>10

// getSum(-1, 4, 5)
// =>8``````

## Problem：longest-substring-without-repeating-characters

https://leetcode.com/problems/longest-substring-without-repeating-characters/description/

``````Given a string, find the length of the longest substring without repeating characters.

Examples:

Given "abcabcbb", the answer is "abc", which the length is 3.

Given "bbbbb", the answer is "b", with the length of 1.

Given "pwwkew", the answer is "wke", with the length of 3. Note that the answer must be a substring, "pwke" is a subsequence and not a substring.``````

``````const lengthOfLongestSubstring = function(s) {
let longestStrMapper = {}; // 记录已经出现过的charactor
let res = 0; // 记录临时结果
let start = 0; // 开始指针
let end = 0; // 结束指针
let char = '' // 临时存储每一轮用于数不重复字符个数的字符
for(let c of s) {
char = c
end = start
longestStrMapper = {}
while(!longestStrMapper[char] && char) {
longestStrMapper[char] = true
char = s.charAt(++end)
}
if(end - start > res) {
res = end - start
}
start++;
}
return res;
};

lengthOfLongestSubstring("bbbbb")
// => 1
lengthOfLongestSubstring("abcabcbb")
// => 3
lengthOfLongestSubstring("pwwkew")
// => 3``````

## Problem：partition-equal-subset-sum

https://leetcode.com/problems/partition-equal-subset-sum/description/

``````Given a non-empty array containing only positive integers, find if the array can be partitioned into two subsets such that the sum of elements in both subsets is equal.

Note:

Each of the array element will not exceed 100.
The array size will not exceed 200.

Example 1:

Input: [1, 5, 11, 5]

Output: true

Explanation: The array can be partitioned as [1, 5, 5] and [11].

Example 2:

Input: [1, 2, 3, 5]

Output: false

Explanation: The array cannot be partitioned into equal sum subsets.``````

``````/*
----问题

-----输入格式

*/

/**
* @param {number[]} nums
* @return {boolean}
*/
var canPartition = function (nums) {
let sum = 0
for (let num of nums) {
sum += num
}

if (sum & 1 === 1) return false

const half = sum >> 1

// v[ i ]为物品的体积，w[i]为物品的价值。在此题中，单个数字的体积就是其价值，也就是 v[i] ===  w[i] === nums[i-1]
let dp = Array(nums.length + 1)
dp[0] = [0, ...Array(nums.length).fill(0)] // 前0个元素，容量为0情况，最大价值都为0
// 前1个元素，容量为j情况，最大价值取决于装不装得下，如果能装得下最大价值就是第一个数
dp[1] = [0, ...Array(nums.length).fill(0)]
for (let j = 1; j < half + 1; j++) {
if (j >= nums[0]) {
dp[1][j] = nums[0]
}
}
// 前两个元素开始，当前i个容积为j的最大价值有两种情况，
// 1、第i个数装不下了，我不要了，值为dp[i - 1][j]；
// 2、装得下，我要，那么第个的值占的容积为nums[i-1]，价值也是nums[i-1]，剩下的可以留给前i-1个数来分的容积为j - nums[i-1]，也就是值为dp[i - 1][j - nums[i-1]] + nums[i-1]
// 状态转移方程 f[ i ][ j ] = max ( f[ i-1 ][ j ] , f[ i-1 ][ j-v[ i ] ] + w[ i ] )
for (let i = 2; i < nums.length + 1; i++) {
dp[i] = [0, ...Array(half).fill(0)]
for (let j = 1; j < half + 1; j++) {
// 要注意前i个数中取第i个数的值是 nums[i-1]，因为是由0开始算
// if(j >= nums[i-1]) { // 这里不注释可以把所有的值都求出来
dp[i][j] = Math.max(dp[i - 1][j], j >= nums[i-1] ? dp[i - 1][j - nums[i-1]] + nums[i-1] : 0)
// }
}
}
// console.log(dp)
return dp[nums.length][half] === half
}``````

## Problem：target-sum

https://leetcode.com/problems/target-sum/description/

``````/*
* @lc app=leetcode id=494 lang=javascript
*
* [494] Target Sum
*
* https://leetcode.com/problems/target-sum/description/
*
* algorithms
* Medium (44.86%)
* Total Accepted:    89.3K
* Total Submissions: 198.5K
* Testcase Example:  '[1,1,1,1,1]\n3'
*
*
* You are given a list of non-negative integers, a1, a2, ..., an, and a
* target, S. Now you have 2 symbols + and -. For each integer, you should
* choose one from + and - as its new symbol.
* ⁠
*
* Find out how many ways to assign symbols to make sum of integers equal to
* target S.
*
*
* Example 1:
*
* Input: nums is [1, 1, 1, 1, 1], S is 3.
* Output: 5
* Explanation:
*
* -1+1+1+1+1 = 3
* +1-1+1+1+1 = 3
* +1+1-1+1+1 = 3
* +1+1+1-1+1 = 3
* +1+1+1+1-1 = 3
*
* There are 5 ways to assign symbols to make the sum of nums be target 3.
*
*
*
* Note:
*
* The length of the given array is positive and will not exceed 20.
* The sum of elements in the given array will not exceed 1000.
* Your output answer is guaranteed to be fitted in a 32-bit integer.
*
*
*/
// 这个是我们熟悉的问题了
// 我们这里需要求解的是nums里面有多少种可以组成target的方式
var sumCount = function(nums, target) {
// 这里通过观察，我们没必要使用二维数组去存储这些计算结果
// 使用一维数组可以有效节省空间
const dp = Array(target + 1).fill(0);
dp[0] = 1; // 和为0组合只有一种，就是全部元素都不选，dp[0]为1
for (let i = 0; i < nums.length; i++) { // 其他情况每个元素都选时，要累加dp[j]，状态转移方程解释：dp[i,j]===dp[i, j - nums[i]]其实好理解，如果定了要nums[i]那么组合数dp[i, j]就变相等于求dp[i, j-nums[i]]的组合数了
for (let j = target; j >= nums[i]; j--) {
dp[j] += dp[j - nums[i]]; // 我们不需要保存所有的过程值，因此dp[i, j]写成累加dp[j] += dp[j - nums[i]]即可
}
}
return dp[target];
};
const add = nums => nums.reduce((a, b) => (a += b), 0);
/**
* @param {number[]} nums
* @param {number} S
* @return {number}
*/
var findTargetSumWays = function(nums, S) {
const sum = add(nums);
if (sum < S) return 0;
if ((S + sum) % 2 === 1) return 0;
return sumCount(nums, (S + sum) >> 1);
};``````

## Problem：maximum-sum-of-two-non-overlapping-subarrays

https://leetcode.com/problems/maximum-sum-of-two-non-overlapping-subarrays/

``````Given an array A of non-negative integers, return the maximum sum of elements in two non-overlapping (contiguous) subarrays, which have lengths L and M.  (For clarification, the L-length subarray could occur before or after the M-length subarray.)

Formally, return the largest V for which V = (A[i] + A[i+1] + ... + A[i+L-1]) + (A[j] + A[j+1] + ... + A[j+M-1]) and either:

0 <= i < i + L - 1 < j < j + M - 1 < A.length, or
0 <= j < j + M - 1 < i < i + L - 1 < A.length.

Example 1:

Input: A = [0,6,5,2,2,5,1,9,4], L = 1, M = 2
Output: 20
Explanation: One choice of subarrays is [9] with length 1, and [6,5] with length 2.
Example 2:

Input: A = [3,8,1,3,2,1,8,9,0], L = 3, M = 2
Output: 29
Explanation: One choice of subarrays is [3,8,1] with length 3, and [8,9] with length 2.
Example 3:

Input: A = [2,1,5,6,0,9,5,0,3,8], L = 4, M = 3
Output: 31
Explanation: One choice of subarrays is [5,6,0,9] with length 4, and [3,8] with length 3.

Note:

L >= 1
M >= 1
L + M <= A.length <= 1000
0 <= A[i] <= 1000``````

``````function sumNums (nums, start, end) {
return nums.slice(start, end + 1).reduce((sum, item) => {
return sum += item
}, 0)
}
function maxSumTwoNoOverlap (nums, l, m) {
let x, y, len = nums.length, maxSum = 0
// l在m左边情况
for (x = 0; x < len - m - l + 1; x++) {
y = x + l
while (y > x + l - 1 && y + m - 1 < len) {
maxSum = Math.max(maxSum, sumNums(nums, x, x + l - 1) + sumNums(nums, y, y + m - 1))
y++
}
}
if(m != l) { // 如果相等就不需要处理了，在右边与在左边结果一样
// l在m右边情况
for (x = 0; x < len - m - l + 1; x++) {
y = x + m
while (y > x + m - 1 && y + l - 1 < len) {
maxSum = Math.max(maxSum, sumNums(nums, x, x + m - 1) + sumNums(nums, y, y + l - 1))
y++
}
}
}

return maxSum
}
``````

## 作者： 博主

Talk is cheap, show me the code!

## 《参考《leetcode 题解，记录自己的 leetcode 解题之路》练脑 （一）》有一个想法

1. note说道：

DFS, BFS, 红黑树, 贪心算法, 回溯法