第一百八十七題：
class Solution {
public:
vector<string> findRepeatedDnaSequences(string s) {
unordered_map<string, int> cnt;
for (int i = 0; i + 10 <= s.size(); i ++ )
cnt[s.substr(i, 10)] ++ ;
vector<string> res;
for (auto [s, c]: cnt)
if (c > 1)
res.push_back(s);
return res;
}
};
class Solution {
public List<String> findRepeatedDnaSequences(String s) {
int L = 10, n = s.length();
if (n <= L) return new ArrayList();
// rolling hash parameters: base a
int a = 4, aL = (int)Math.pow(a, L);
// convert string to array of integers
Map<Character, Integer> toInt = new
HashMap() {{put('A', 0); put('C', 1); put('G', 2); put('T', 3); }};
int[] nums = new int[n];
for(int i = 0; i < n; ++i) nums[i] = toInt.get(s.charAt(i));
int bitmask = 0;
Set<Integer> seen = new HashSet();
Set<String> output = new HashSet();
// iterate over all sequences of length L
for (int start = 0; start < n - L + 1; ++start) {
// compute bitmask of the current sequence in O(1) time
if (start != 0) {
// left shift to free the last 2 bit
bitmask <<= 2;
// add a new 2-bits number in the last two bits
bitmask |= nums[start + L - 1];
// unset first two bits: 2L-bit and (2L + 1)-bit
bitmask &= ~(3 << 2 * L);
}
// compute hash of the first sequence in O(L) time
else {
for(int i = 0; i < L; ++i) {
bitmask <<= 2;
bitmask |= nums[i];
}
}
// update output and hashset of seen sequences
if (seen.contains(bitmask)) output.add(s.substring(start, start + L));
seen.add(bitmask);
}
return new ArrayList<String>(output);
}
}
class Solution:
def findRepeatedDnaSequences(self, s: str) -> List[str]:
d = {}
for i in range(len(s) - 9):
if s[i: i + 10] in d:
d[s[i: i + 10]] = True
else:
d[s[i: i + 10]] = False
return [*filter(lambda i: d[i], d)]
func findRepeatedDnaSequences(s string) []string {
ans, d := []string{}, map[string]bool{}
for i, n := 0, len(s) - 9; i < n; i++ {
if _, ok := d[s[i: i + 10]]; ok {
d[s[i: i + 10]] = true
} else {
d[s[i: i + 10]] = false
}
}
for si, ok := range d {
if ok {
ans = append(ans, si)
}
}
return ans
}
第一百八十八題：
int f[10001], g[10001];
class Solution {
public:
int maxProfit(int k, vector<int>& prices) {
int INF = 1e8;
int n = prices.size();
if (k > n / 2) {
int res = 0;
for (int i = 1; i < n; i ++ )
if (prices[i] > prices[i - 1])
res += prices[i] - prices[i - 1];
return res;
}
memset(f, -0x3f, sizeof f);
memset(g, -0x3f, sizeof g);
f[0] = 0;
int res = 0;
for (int i = 1; i <= n; i ++ )
for (int j = k; j >= 0; j -- ) {
g[j] = max(g[j], f[j] - prices[i - 1]);
if (j) f[j] = max(f[j], g[j - 1] + prices[i - 1]);
}
for (int i = 1; i <= k; i ++ ) res = max(res, f[i]);
return res;
}
};
class Solution {
public int maxProfit(int k, int[] prices) {
if (prices.length == 0) {
return 0;
}
int n = prices.length;
k = Math.min(k, n / 2);
int[] buy = new int[k + 1];
int[] sell = new int[k + 1];
buy[0] = -prices[0];
sell[0] = 0;
for (int i = 1; i <= k; ++i) {
buy[i] = sell[i] = Integer.MIN_VALUE / 2;
}
for (int i = 1; i < n; ++i) {
buy[0] = Math.max(buy[0], sell[0] - prices[i]);
for (int j = 1; j <= k; ++j) {
buy[j] = Math.max(buy[j], sell[j] - prices[i]);
sell[j] = Math.max(sell[j], buy[j - 1] + prices[i]);
}
}
return Arrays.stream(sell).max().getAsInt();
}
}
class Solution:
def maxProfit(self, k: int, prices: List[int]) -> int:
if not prices:
return 0
n = len(prices)
k = min(k, n // 2)
buy = [0] * (k + 1)
sell = [0] * (k + 1)
buy[0], sell[0] = -prices[0], 0
for i in range(1, k + 1):
buy[i] = sell[i] = float("-inf")
for i in range(1, n):
buy[0] = max(buy[0], sell[0] - prices[i])
for j in range(1, k + 1):
buy[j] = max(buy[j], sell[j] - prices[i])
sell[j] = max(sell[j], buy[j - 1] + prices[i]);
return max(sell)
func maxProfit(k int, prices []int) int {
n := len(prices)
if n == 0 {
return 0
}
k = min(k, n/2)
buy := make([]int, k+1)
sell := make([]int, k+1)
buy[0] = -prices[0]
for i := 1; i <= k; i++ {
buy[i] = math.MinInt64 / 2
sell[i] = math.MinInt64 / 2
}
for i := 1; i < n; i++ {
buy[0] = max(buy[0], sell[0]-prices[i])
for j := 1; j <= k; j++ {
buy[j] = max(buy[j], sell[j]-prices[i])
sell[j] = max(sell[j], buy[j-1]+prices[i])
}
}
return max(sell...)
}
func min(a, b int) int {
if a < b {
return a
}
return b
}
func max(a ...int) int {
res := a[0]
for _, v := range a[1:] {
if v > res {
res = v
}
}
return res
}
第一百八十九題：
class Solution {
public:
void rotate(vector<int>& nums, int k) {
int n = nums.size();
k %= n;
reverse(nums.begin(), nums.end());
reverse(nums.begin(), nums.begin() + k);
reverse(nums.begin() + k, nums.end());
}
};
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);
}
public void reverse(int[] nums, int start, int end) {
while (start < end) {
int temp = nums[start];
nums[start] = nums[end];
nums[end] = temp;
start += 1;
end -= 1;
}
}
}
func reverse(a []int) {
for i, n := 0, len(a); i < n/2; i++ {
a[i], a[n-1-i] = a[n-1-i], a[i]
}
}
func rotate(nums []int, k int) {
k %= len(nums)
reverse(nums)
reverse(nums[:k])
reverse(nums[k:])
}
class Solution:
def rotate(self, nums, k):
retote = []
k = k % len(nums)
retote = nums[:len(nums)-k]
for i in range(len(nums)-k):
del nums[0]
nums.extend(retote)
第一百九十題：
class Solution {
public:
uint32_t reverseBits(uint32_t n) {
uint32_t res = 0;
for (int i = 0; i < 32; i ++ )
res = res * 2 + (n >> i & 1);
return res;
}
};
public class Solution {
// you need treat n as an unsigned value
public int reverseBits(int n) {
int res = 0;
for (int i = 0; i <= 31; i++) {
// res += (n & (1 << i)) != 0 ? 1 << (31 - i) : 0;
// res |= (n & (1 << i)) != 0 ? 1 << (31 - i) : 0;
res ^= (n & (1 << i)) != 0 ? 1 << (31 - i) : 0;
}
return res;
}
}
class Solution:
# @param n, an integer
# @return an integer
def reverseBits(self, n):
ret, power = 0, 31
while n:
ret += (n & 1) << power
n = n >> 1
power -= 1
return ret
func reverseBits(num uint32) uint32 {
ret := uint32(0)
power := uint32(31)
for num != 0 {
ret += (num & 1) << power
num = num >> 1
power -= 1
}
return ret
}
第一百九十一題：
class Solution {
public:
int hammingWeight(uint32_t n) {
int res = 0;
while (n) n -= n & -n, res ++ ;
return res;
}
};
public int hammingWeight(int n) {
int sum = 0;
while (n != 0) {
sum++;
n &= (n - 1);
}
return sum;
}
class Solution:
def hammingWeight(self, n: int) -> int:
res=0
while n:
res+=n&1
n>>=1
return res
func hammingWeight(num uint32) int {
count := 0
for num > 0 {
num &= num -1
count++
}
return count
}
第一百九十八題：
class Solution {
public:
int rob(vector<int>& nums) {
int n = nums.size();
vector<int> f(n + 1), g(n + 1);
for (int i = 1; i <= n; i ++ ) {
f[i] = g[i - 1] + nums[i - 1];
g[i] = max(f[i - 1], g[i - 1]);
}
return max(f[n], g[n]);
}
};
class Solution {
public int rob(int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int length = nums.length;
if (length == 1) {
return nums[0];
}
int[] dp = new int[length];
dp[0] = nums[0];
dp[1] = Math.max(nums[0], nums[1]);
for (int i = 2; i < length; i++) {
dp[i] = Math.max(dp[i - 2] + nums[i], dp[i - 1]);
}
return dp[length - 1];
}
}
class Solution:
def rob(self, nums: List[int]) -> int:
if not nums:
return 0
size = len(nums)
if size == 1:
return nums[0]
dp = [0] * size
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i in range(2, size):
dp[i] = max(dp[i - 2] + nums[i], dp[i - 1])
return dp[size - 1]
func rob(nums []int) int {
if len(nums) == 0 {
return 0
}
if len(nums) == 1 {
return nums[0]
}
dp := make([]int, len(nums))
dp[0] = nums[0]
dp[1] = max(nums[0], nums[1])
for i := 2; i < len(nums); i++ {
dp[i] = max(dp[i-2] + nums[i], dp[i-1])
}
return dp[len(nums)-1]
}
func max(x, y int) int {
if x > y {
return x
}
return y
}
第一百九十九題：
/**
* Definition for a binary tree node.
* struct TreeNode {
* int val;
* TreeNode *left;
* TreeNode *right;
* TreeNode(int x) : val(x), left(NULL), right(NULL) {}
* };
*/
class Solution {
public:
vector<int> rightSideView(TreeNode* root) {
queue<TreeNode*> q;
vector<int> res;
if (!root) return res;
q.push(root);
while (q.size()) {
int len = q.size();
for (int i = 0; i < len; i ++ ) {
auto t = q.front();
q.pop();
if (t->left) q.push(t->left);
if (t->right) q.push(t->right);
if (i == len - 1) res.push_back(t->val);
}
}
return res;
}
};
class Solution {
public List<Integer> rightSideView(TreeNode root) {
Map<Integer, Integer> rightmostValueAtDepth = new HashMap<Integer, Integer>();
int max_depth = -1;
Queue<TreeNode> nodeQueue = new LinkedList<TreeNode>();
Queue<Integer> depthQueue = new LinkedList<Integer>();
nodeQueue.add(root);
depthQueue.add(0);
while (!nodeQueue.isEmpty()) {
TreeNode node = nodeQueue.remove();
int depth = depthQueue.remove();
if (node != null) {
// 維護二叉樹的最大深度
max_depth = Math.max(max_depth, depth);
// 由于每一層最後一個通路到的節點才是我們要的答案，是以不斷更新對應深度的資訊即可
rightmostValueAtDepth.put(depth, node.val);
nodeQueue.add(node.left);
nodeQueue.add(node.right);
depthQueue.add(depth+1);
depthQueue.add(depth+1);
}
}
List<Integer> rightView = new ArrayList<Integer>();
for (int depth = 0; depth <= max_depth; depth++) {
rightView.add(rightmostValueAtDepth.get(depth));
}
return rightView;
}
}
from collections import deque
class Solution(object):
def rightSideView(self, root):
rightmost_value_at_depth = dict() # 深度為索引，存放節點的值
max_depth = -1
queue = deque([(root, 0)])
while queue:
node, depth = queue.popleft()
if node is not None:
# 維護二叉樹的最大深度
max_depth = max(max_depth, depth)
# 由于每一層最後一個通路到的節點才是我們要的答案，是以不斷更新對應深度的資訊即可
rightmost_value_at_depth[depth] = node.val
queue.append((node.left, depth+1))
queue.append((node.right, depth+1))
return [rightmost_value_at_depth[depth] for depth in range(max_depth+1)]
/**
* Definition for a binary tree node.
* type TreeNode struct {
* Val int
* Left *TreeNode
* Right *TreeNode
* }
*/
func rightSideView(root *TreeNode) []int {
var result []int
if root == nil{
return result
}
digui(root,&result,1)
return result
}
func digui(root *TreeNode,result *[]int,i int){
if len(*result) < i{
*result = append(*result,root.Val)
}
if root.Right != nil{
digui(root.Right,result,i+1)
}
if root.Left != nil{
digui(root.Left,result,i+1)
}
return
}
![力扣每日一題：65. 有效數字題目：65. 有效數字解題思路[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)