第五百一十六题：
class Solution {
public:
int longestPalindromeSubseq(string s) {
int n = s.size();
vector<vector<int>> f(n, vector<int>(n));
for (int len = 1; len <= n; len ++ )
for (int i = 0; i + len - 1 < n; i ++ ) {
int j = i + len - 1;
if (len == 1) f[i][j] = 1;
else {
if (s[i] == s[j]) f[i][j] = f[i + 1][j - 1] + 2;
f[i][j] = max(f[i][j], max(f[i + 1][j], f[i][j - 1]));
}
}
return f[0][n - 1];
}
};
class Solution {
public int longestPalindromeSubseq(String s) {
int n = s.length();
// 状态表示数组，两个维度分别表示区间的左右端点，数值表示区间最大回文长度
int[][] f = new int[n][n];
int res = 0;
// 先枚举区间长度
for(int len = 1; len <= n; len ++) {
// 再枚举区间左右端点
for(int i = 0; i + len - 1 < n; i++) {
int j = i + len - 1;
// 特判长度为1的情况
if(len == 1) f[i][j] = 1;
else {
// 不用当前两个端点为回文边界的情况
f[i][j] = Math.max(f[i + 1][j], f[i][j - 1]);
// 如果两个当前区间的两个端点相同，那就用
if(s.charAt(i) == s.charAt(j)) {
f[i][j] = f[i + 1][j - 1] + 2;
}
}
// 取最大值
res = Math.max(f[i][j], res);
}
}
return res;
}
}
class Solution:
def longestPalindromeSubseq(self, s: str) -> int:
n = len(s)
dp = [[0 for _ in range(n)] for _ in range(n)]
for i in range(n):
dp[i][i] = 1
for i in range(n-1, -1, -1): #遍历顺序由dp关系式所得
for j in range(i+1, n):
if s[i] == s[j]:
dp[i][j] = dp[i+1][j-1] + 2
else:
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
return dp[0][n-1] #dp处理两个端点
func longestPalindromeSubseq(s string) int {
var n = len(s)
var dp = make([][]int, n)
for i := 0; i < n; i++ {
dp[i] = make([]int, n)
dp[i][i] = 1
}
//for i := 0; i < n; i++ {
// fmt.Println(dp[i])
//}
for i := n-1; i >= 0; i-- {
for j := i + 1; j < n; j++ {
if s[i] == s[j]{
dp[i][j] = dp[i+1][j-1]+2
} else {
dp[i][j] = max(dp[i+1][j], dp[i][j-1])
}
}
}
//for i := 0; i < n; i++ {
// fmt.Println(dp[i])
//}
return dp[0][n-1]
}
func max(i1 int, i2 int) int {
if i1 > i2 {
return i1
}
return i2
}
第五百一十七题：
class Solution {
public:
int findMinMoves(vector<int>& w) {
int sum = 0, n = w.size();
for (auto x: w) sum += x;
if (sum % n) return -1;
int avg = sum / n, left = 0, right = sum;
int res = 0;
for (int i = 0; i < n; i ++ ) {
right -= w[i];
if (i) left += w[i - 1];
int l = max(avg * i - left, 0);
int r = max(avg * (n - i - 1) - right, 0);
res = max(res, l + r);
}
return res;
}
};
class Solution {
public int findMinMoves(int[] machines) {
int n = machines.length, dressTotal = 0;
for (int m : machines) dressTotal += m;
if (dressTotal % n != 0) return -1;
int dressPerMachine = dressTotal / n;
// Change the number of dresses in the machines to
// the number of dresses to be removed from this machine
// (could be negative)
for (int i = 0; i < n; i++) machines[i] -= dressPerMachine;
// currSum is a number of dresses to move at this point,
// maxSum is a max number of dresses to move at this point or before,
// m is number of dresses to move out from the current machine.
int currSum = 0, maxSum = 0, tmpRes = 0, res = 0;
for (int m : machines) {
currSum += m;
maxSum = Math.max(maxSum, Math.abs(currSum));
tmpRes = Math.max(maxSum, m);
res = Math.max(res, tmpRes);
}
return res;
}
}
class Solution:
def findMinMoves(self, machines: List[int]) -> int:
n = len(machines)
dress_total = sum(machines)
if dress_total % n != 0:
return -1
dress_per_machine = dress_total // n
for i in range(n):
# Change the number of dresses in the machines to
# the number of dresses to be removed from this machine
# (could be negative)
machines[i] -= dress_per_machine
# curr_sum is a number of dresses to move at this point,
# max_sum is a max number of dresses to move at this point or before,
# m is number of dresses to move out from the current machine.
curr_sum = max_sum = res = 0
for m in machines:
curr_sum += m
max_sum = max(max_sum, abs(curr_sum))
res = max(res, max_sum, m)
return res
func abs(a int)int{
if a< 0{
return -a
}
return a
}
func findMinMoves(machines []int) int {
sum :=0
for _, machine := range machines {
sum +=machine
}
if sum % len(machines)!=0{
return -1
}
avg := sum / len(machines)
var ans =math.MinInt32
for i, machine := range machines {
machines[i] = machine-avg
}
for i:=0;i< len(machines)-1;i++ {
if ans < abs(machines[i]){
ans = abs(machines[i])
}
if ans < machines[i+1]{
ans = machines[i+1]
}
machines[i+1]+=machines[i]
}
if ans < machines[len(machines)-1]{
return machines[len(machines)-1]
}
return ans
}
第五百一十八题：
class Solution {
public:
int change(int amount, vector<int>& coins) {
vector<int> f(amount + 1);
f[0] = 1;
for (auto x: coins)
for (int i = x; i <= amount; i ++ )
f[i] += f[i - x];
return f[amount];
}
};
class Solution {
public int change(int amount, int[] coins) {
int[] dp = new int[amount + 1];
dp[0] = 1;
for (int coin : coins) {
for (int x = coin; x < amount + 1; ++x) {
dp[x] += dp[x - coin];
}
}
return dp[amount];
}
}
class Solution:
def change(self, amount: int, coins: List[int]) -> int:
dp = [0] * (amount + 1)
dp[0] = 1
for coin in coins:
for x in range(coin, amount + 1):
dp[x] += dp[x - coin]
return dp[amount]
//由于dp[i]只和dp[i-1]有关，可以进行状态压缩
func change2(amount int, coins []int) int {
n := len(coins)
dp := make([]int, amount+1)
dp[0] = 1
for i := 1; i <= n; i++ {
for j := 1; j <= amount; j++ {
if j-coins[i-1] >= 0 {
dp[j] = dp[j] + dp[j-coins[i-1]]
}
}
}
return dp[amount]
}
第五百一十九题：
class Solution {
public:
int r, c, k;
unordered_map<int, int> hash;
Solution(int n_rows, int n_cols) {
r = n_rows, c = n_cols;
k = r * c;
}
vector<int> flip() {
int x = rand() % k;
int y = x;
if (hash.count(x)) y = hash[x];
if (hash.count(k - 1)) {
hash[x] = hash[k - 1];
hash.erase(k - 1);
} else {
hash[x] = k - 1;
}
k -- ;
return {
y / c, y % c};
}
void reset() {
k = r * c;
hash.clear();
}
};
/**
* Your Solution object will be instantiated and called as such:
* Solution* obj = new Solution(n_rows, n_cols);
* vector<int> param_1 = obj->flip();
* obj->reset();
*/
class Solution {
int nr, nc, rem, b_size;
List<Set<Integer>> buckets = new ArrayList<>();
Random rand = new Random();
public Solution(int n_rows, int n_cols) {
nr = n_rows;
nc = n_cols;
rem = nr * nc;
b_size = (int) Math.sqrt(nr * nc);
for (int i = 0; i < nr * nc; i+= b_size)
buckets.add(new HashSet<Integer>());
}
public int[] flip() {
int c = 0;
int c0 = 0;
int k = rand.nextInt(rem);
for (Set<Integer> b1 : buckets) {
if (c0 + b_size - b1.size() > k) {
while (true) {
if (!b1.contains(c)) {
if (c0 == k) {
b1.add(c);
rem--;
return new int[]{
c / nc, c % nc};
}
c0++;
}
c++;
}
}
c += b_size;
c0 += b_size - b1.size();
}
return null;
}
public void reset() {
for (Set<Integer> b1 : buckets)
b1.clear();
rem = nr * nc;
}
}
import random
class Solution:
def __init__(self, n_rows: int, n_cols: int):
self.num = n_rows * n_cols - 1
self.n_cols = n_cols
self.visited = set()
def flip(self) -> List[int]:
tmp = random.randint(0, self.num)
while tmp in self.visited:
tmp = random.randint(0, self.num)
self.visited.add(tmp)
return [tmp // self.n_cols, tmp % self.n_cols]
def reset(self) -> None:
self.visited.clear()
type Solution struct {
Cols int
TotalCnt int
Total1Cnt int
Flipped map[int]int // Key:FlippedIndex Value:RepalceIndex
}
func Constructor(n_rows int, n_cols int) Solution {
return Solution{
Cols: n_cols,
TotalCnt: n_rows * n_cols,
Total1Cnt: 0,
Flipped: map[int]int{
},
}
}
func (this *Solution) Flip() []int {
randP := rand.Intn(this.TotalCnt - this.Total1Cnt)
x := randP
this.Total1Cnt++
if _, has := this.Flipped[x]; has {
x = this.Flipped[x]
}
if v, has := this.Flipped[this.TotalCnt-this.Total1Cnt]; has {
this.Flipped[randP] = v
} else {
this.Flipped[randP] = this.TotalCnt - this.Total1Cnt
}
return []int{
x/this.Cols, x%this.Cols}
}
func (this *Solution) Reset() {
this.Total1Cnt = 0
this.Flipped = map[int]int{
}
}
/**
* Your Solution object will be instantiated and called as such:
* obj := Constructor(n_rows, n_cols);
* param_1 := obj.Flip();
* obj.Reset();
*/
第五百二十题：
class Solution {
public:
bool check(char c) {
return c >= 'A' && c <= 'Z';
}
bool detectCapitalUse(string word) {
int s = 0;
for (auto c: word)
if (check(c))
s ++ ;
return s == word.size() || !s || s == 1 && check(word[0]);
}
};
class Solution {
public boolean detectCapitalUse(String word) {
int count = 0;
//情况1 : 判断是不是全是大写
for(int i = 0;i < word.length();i++){
if(word.charAt(i) - 'A' >= 0 && word.charAt(i) - 'A' <= 25){
count++;
}
}
if(count == word.length()){
return true;
}else{
int cnt1 = 0;
//2:判断是不是全是小写
for(int j = 0;j < word.length();j++){
if(word.charAt(j) - 'a' >= 0){
cnt1++;
}
}
if(cnt1 == word.length()){
return true;
//如果不是,判断是不是首字母大写
}else if(cnt1 == word.length() - 1 && word.charAt(0) - 'A' >= 0 && word.charAt(0) - 'A' <= 25 ){
return true;
//如果还不是,就return false
}else{
return false;
}
}
}
}
class Solution:
def detectCapitalUse(self, word: str) -> bool:
return word.islower() or word.isupper() or (word[0].isupper() and word[1:].islower())
func detectCapitalUse(word string) bool {
return word == strings.ToUpper(word) || word == strings.ToLower(word) || word == strings.Title(strings.ToLower(word))
}
第五百二十一题：
class Solution {
public:
int findLUSlength(string a, string b) {
if (a == b) return -1;
return max(a.size(), b.size());
}
};
public class Solution {
public int findLUSlength(String a, String b) {
if (a.equals(b))
return -1;
return Math.max(a.length(), b.length());
}
}
class Solution:
def findLUSlength(self, a: str, b: str) -> int:
return max(len(a),len(b)) if a!=b else -1
func findLUSlength(a string, b string) int {
if a == b {
return -1
}
return len(maxString(a, b))
}
func maxString(a, b string) string {
if len(a) > len(b) {
return a
} else {
return b
}
}
第五百二十二题：
class Solution {
public:
bool check(string& a, string& b) {
int k = 0;
for (auto c: b)
if (k < a.size() && c == a[k])
k ++ ;
return k == a.size();
}
int findLUSlength(vector<string>& strs) {
int res = -1;
for (int i = 0; i < strs.size(); i ++ ) {
bool is_sub = false;
for (int j = 0; j < strs.size(); j ++ )
if (i != j && check(strs[i], strs[j])) {
is_sub = true;
break;
}
if (!is_sub) res = max(res, (int)strs[i].size());
}
return res;
}
};
public class Solution {
public boolean isSubsequence(String x, String y) {
int j = 0;
for (int i = 0; i < y.length() && j < x.length(); i++)
if (x.charAt(j) == y.charAt(i))
j++;
return j == x.length();
}
public int findLUSlength(String[] strs) {
Arrays.sort(strs, new Comparator < String > () {
public int compare(String s1, String s2) {
return s2.length() - s1.length();
}
});
for (int i = 0, j; i < strs.length; i++) {
boolean flag = true;
for (j = 0; j < strs.length; j++) {
if (i == j)
continue;
if (isSubsequence(strs[i], strs[j])) {
flag = false;
break;
}
}
if (flag)
return strs[i].length();
}
return -1;
}
}
class Solution:
def findLUSlength(self, strs: List[str]) -> int:
# 判读s1是否是s2的子序列
def check(s1, s2):
if len(s1) > len(s2): return False
if s1 == s2: return True
i, loc = 0, -1
while i < len(s1) and (loc := s2.find(s1[i], loc + 1)) != -1:
i += 1
return i == len(s1)
# 按长度从长到短排序
strs.sort(key=len, reverse=True)
for idx1, s1 in enumerate(strs):
# 看s1是否全不是其他字符串的子序列的
if all(not check(s1, s2) for idx2, s2 in enumerate(strs) if idx1 != idx2): return len(s1)
return -1
func findLUSlength(strs []string) int {
sort.Slice(strs, func(i, j int) bool {
return len(strs[i])<len(strs[j])
})
ss:=make([]string,0)
b:=make([]bool,len(strs))
for i:=len(strs)-1;i>=0;i--{
if b[i]{
continue
}
f:=true
for j:=i-1;j>=0;j--{
if strs[i]==strs[j]{
f = false
b[j] = true
}
}
if f&&isContains(ss,strs[i]){
return len(strs[i])
}
ss = append(ss,strs[i])
}
return -1
}
func isContains(ss []string,s string) bool {
for i:=0;i<len(ss);i++{
if doIsContains(ss[i],s){
return false
}
}
return true
}
func doIsContains(s,t string) bool {
if t==""{
return true
}
if s==""{
return false
}
for i:=0;i<len(s);i++{
if s[i]==t[0]{
if doIsContains(s[i+1:],t[1:]){
return true
}
}
}
return false
}
转载：https://blog.csdn.net/weixin_44169596/article/details/115741503
查看评论