给一个数组和一个字符串,求在数组的位置对应的字符串的位置添加空格.
class Solution {
public String addSpaces(String s, int[] spaces) {
StringBuffer sb = new StringBuffer(s);
int count = 0;
for(int ss : spaces) {
sb.insert(ss+count,' ');
count++;
}
return sb.toString();
}
}给一个数组, 求最大循环子数组.
通过观察得知, 这题的答案是在普通的最大子数组问题和循环子数组问题的两个答案下取最大.
前者我们已经有算法可解. 后者通过观察得知, 如果循环数组的答案包含了数字中第一项或者最后一项, 那么这个答案已经在前者(普通)的计算中算过了. 故得知, 循环数组的最大子数组的答案等于数组的和在第二个元素和倒数第二个元素的最小和子数组。
class Solution {
public int maxSubarraySumCircular(int[] nums) {
int maxsub = maxSub(nums);
int sum = sum(nums);
int minsub = minSub(nums);
return Math.max(maxsub, sum - minsub);
}
public int maxSub(int[] nums){
int l = 0;
int g = Integer.MIN_VALUE/2;
for(int n : nums){
l += n;
g = Math.max(l,g);
if(l < 0)
l = 0;
}
return g;
}
public int sum(int[] nums){
int sum = 0;
for(int n : nums)
sum += n;
return sum;
}
public int minSub(int[] nums){
int l = 0;
int g = Integer.MAX_VALUE / 2;
for(int i = 1; i < nums.length - 1; i++){
l += nums[i];
g = Math.min(l,g);
if(l > 0)
l = 0;
}
return g;
}
}给一个string, 里面是数字,把string的数字每k个加起来, 然后一直这样加,直到string长度小于k.
class Solution {
public String digitSum(String s, int k) {
while(s.length() > k){
StringBuffer sb = new StringBuffer();
for(int i = 0; i < s.length();) {
int tmp = 0;
for(int j = 0; j < k;j++){
if(i >= s.length())
break;
tmp += (s.charAt(i++) - '0');
}
sb.append(tmp);
}
s = sb.toString();
}
return s;
}
}给一个数组，里面是比赛结果[winner, loser], 求两个数组, 第一个是没有输过人的比赛, 第二个是只输了一场的比赛. 要求这个人起码参赛了.
首先判断是否参赛, 用set, 然后记录比赛的loser情况, 即可.
class Solution {
public List<List<Integer>> findWinners(int[][] matches) {
int[] check = new int[200000];
Set<Integer> set = new HashSet<>();
for(int[] m : matches){
set.add(m[0]);
set.add(m[1]);
check[m[1]]++;
}
List<Integer> zero = new ArrayList<>();
List<Integer> one = new ArrayList<>();
List<List<Integer>> res = new ArrayList<>();
for(int i = 0; i < check.length; i++){
if(!set.contains(i))
continue;
if(check[i] == 1)
one.add(i);
else if(check[i] == 0)
zero.add(i);
}
res.add(zero);
res.add(one);
return res;
}
}class Solution {
public int largestInteger(int num) {
String s = ""+num;
char[] c = s.toCharArray();
int n = c.length;
LinkedList<Integer> odd = new LinkedList<>();
LinkedList<Integer> even = new LinkedList<>();
int cc = 0;
while(num != 0){
if((num % 10) % 2 == 0)
even.add(num % 10);
else
odd.add(num % 10);
cc++;
num /= 10;
}
Collections.sort(odd, Collections.reverseOrder());
Collections.sort(even, Collections.reverseOrder());
int i = 0;
int j = 0;
for(int ii = 0; ii < n; ii++) {
if((c[ii] - '0') % 2 == 0)
c[ii] =(char)('0' + even.removeFirst());
else
c[ii] =(char)('0' + odd.removeFirst());
}
return Integer.valueOf(String.valueOf(c));
}
}class Solution {
public int sum(int num1, int num2) {
return num1 + num2;
}
}/**
* Definition for a binary tree node.
* public class TreeNode {
* int val;
* TreeNode left;
* TreeNode right;
* TreeNode() {}
* TreeNode(int val) { this.val = val; }
* TreeNode(int val, TreeNode left, TreeNode right) {
* this.val = val;
* this.left = left;
* this.right = right;
* }
* }
*/
class Solution {
public boolean checkTree(TreeNode root) {
return root.val == root.left.val + root.right.val;
}
}给一个数组是一些moves， 求三连游戏的胜者。
class Solution {
public String tictactoe(int[][] moves) {
int[][] g = new int[3][3];
int cc = 0;
for(int[] m : moves){
if(cc % 2 == 0)
g[m[0]][m[1]] = 1;
else
g[m[0]][m[1]] = -100;
cc++;
}
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++) {
int r = checkRow(g, j);
int c = checkCol(g, i);
int d = checkDia(g, i, j);
int dd = checkDDia(g, i, j);
if(r == 3)
return "A";
if(r == -300)
return "B";
if(c == 3)
return "A";
if(c == -300)
return "B";
if(d == 3)
return "A";
if(d == -300)
return "B";
if(dd == 3)
return "A";
if(dd == -300)
return "B";
}
}
return cc == 9 ? "Draw" : "Pending";
}
private int checkRow(int[][] g, int j) {
int res = 0;
for(int i = 0; i < 3; i++){
res += g[i][j];
}
return res;
}
private int checkCol(int[][] g, int i) {
int res = 0;
for(int j = 0; j < 3; j++){
res += g[i][j];
}
return res;
}
private int checkDia(int[][] g, int i, int j) {
if(i != 1 || j != 1)
return 0;
int res = 0;
for(int k = 0; k < 3; k++){
res += g[k][k];
}
return res;
}
private int checkDDia(int[][]g, int i, int j){
if(i != 1 || j != 1)
return 0;
int res = 0;
i = 0;
j = 2;
for(int k = 0; k < 3; k++){
res += g[i++][j--];
}
return res;
}
}给一个数组, 代表一个队列, 里面的数字代表i人要买nums[i]张票, 人买了票后就要去队尾排队, 求多少次卖票后, 第k的人买完票.
class Solution {
public int timeRequiredToBuy(int[] tickets, int k) {
int res = 0;
while(tickets[k] > 0){
for(int i = 0; i < tickets.length; i++){
if(tickets[i] > 0){
tickets[i]--;
res++;
}
if(tickets[k] == 0) // stop looping
break;
}
}
return res;
}
}给两个数字, 求两个数字中不相同的bit的个数.
先xor, 然后counting bit.
class Solution {
public int minBitFlips(int start, int goal) {
int x = start ^ goal;
int res = 0;
for (res = 0; x != 0; x >>= 1)
{
res += x & 1;
}
return res;
}
}