Summary of leetcode's simulated problem brushing 2
1-remodeling matrix
Title Link: Title Link stamp here!!!
Idea: simulate the matrix remodeling process. If the number of elements of the original matrix and the remodeling matrix is different, the remodeling cannot be completed. On the contrary, the remodeling can be completed. First convert the original matrix into a one-dimensional array, and then convert the one-dimensional array into a remodeling matrix.
The AC code is as follows:
class Solution {
public int[][] matrixReshape(int[][] mat, int r, int c) {
if(r*c!=mat.length*mat[0].length){
return mat ;
}
int [] temp = new int [r*c] ;
int idx = 0 ;
int [][] res = new int [r][c] ;
for(int i=0; i<mat.length; i++){
for(int j=0; j<mat[0].length; j++){
temp[idx++] = mat[i][j] ;
}
}
idx = 0 ;
for(int i=0; i<r; i++){
for(int j=0; j<c; j++){
res[i][j] = temp[idx++] ;
}
}
return res ;
}
}
It can also be written in this way to directly convert the two-dimensional matrix into the corresponding two-dimensional matrix, which is more efficient.
class Solution {
public int[][] matrixReshape(int[][] mat, int r, int c) {
if(r*c!=mat.length*mat[0].length){
return mat ;
}
int [][] res = new int [r][c] ;
for(int i=0; i<r*c; i++){
res[i/c][i%c] = mat[i/mat[0].length][i%mat[0].length] ;
}
return res ;
}
}
2-Fizz Buzz
Title Link: Title Link stamp here!!!
Idea: for water problems, judge directly and join the set.
class Solution {
public List<String> fizzBuzz(int n) {
List<String> list = new ArrayList<>() ;
for(int i=1; i<=n; i++){
if(i%3==0 && i%5==0){
list.add("FizzBuzz") ;
}else if(i%3==0){
list.add("Fizz") ;
}else if(i%5==0){
list.add("Buzz") ;
}else{
list.add(String.valueOf(i)) ;
}
}
return list ;
}
}
3-solving equation
Title Link: Title Link stamp here!!!
Idea: add "+" in front of all "-" symbols in the string, and then divide the string into two segments according to the equal sign. The left and right strings are divided into string arrays according to "+", and then process the left and right strings to judge whether there is a solution according to the coefficient.
The AC code is as follows:
class Solution {
public String solveEquation(String equation) {
int idx = 0 ;
for(int i=0; i<equation.length(); i++){
if(equation.charAt(i)=='-'){
equation = equation.substring(0,i) + "+" + equation.substring(i) ;
i++ ;
}
}
for(int i=0; i<equation.length(); i++){
if(equation.charAt(i)=='='){
idx=i ;
}
}
String left = equation.substring(0,idx) ;
String right = equation.substring(idx+1,equation.length()) ;
String [] l = left.split("[+]") ;
String [] r = right.split("[+]") ;
int a1=0, a2=0, b1=0, b2=0 ;
for(int i=0; i<l.length; i++){
if( !l[i].equals("") && !contains(l[i]) ){
a1 += Integer.parseInt(l[i]) ;
}else if(!l[i].equals("") && contains(l[i])){
if(l[i].length()==1){
b1 += 1 ;
}else if(l[i].length()==2 && l[i].charAt(0)=='-'){
b1 -= 1 ;
}
else{
b1 += Integer.parseInt(l[i].substring(0,l[i].length()-1)) ;
}
}
}
for(int i=0; i<r.length; i++){
if(!contains(r[i]) && !r[i].equals("")){
a2 += Integer.parseInt(r[i]) ;
}else if(contains(r[i]) && !r[i].equals("")){
if(r[i].length()==1){
b2 += 1 ;
}else if(r[i].length()==2 && r[i].charAt(0)=='-'){
b2 -= 1 ;
}
else{
b2 += Integer.parseInt(r[i].substring(0,r[i].length()-1)) ;
}
}
}
if(b1!=b2){
return "x=" + (a2-a1)/(b1-b2) ;
}else if(a1!=a2){
return "No solution" ;
}else{
return "Infinite solutions" ;
}
}
public boolean contains(String s){
if(s.equals("")){
return false ;
}
if(s.charAt(s.length()-1)=='x'){
return true ;
}
return false ;
}
}
4 - can the robot return to the origin
Title Link: Title Link stamp here!!!
Idea: record the number of U, D, R and L. if and only if U is equal to D and R is equal to L, you can return to the origin. Otherwise, you cannot return to the origin.
class Solution {
public boolean judgeCircle(String moves) {
int cntU=0, cntD=0, cntL=0, cntR=0 ;
for(int i=0; i<moves.length();i++){
if(moves.charAt(i)=='U'){
cntU ++ ;
}else if(moves.charAt(i)=='D'){
cntD ++ ;
}else if(moves.charAt(i)=='L'){
cntL ++ ;
}else if(moves.charAt(i)=='R'){
cntR ++ ;
}
}
return cntR==cntL && cntD==cntU ;
}
}
5 - simulate robot walking
Title Link: Title Link stamp here!!!
Idea: use the set to store the obstacle coordinates, define four directions, simulate the motion according to the command, and calculate the maximum Euclidean distance at the same time.
The AC code is as follows:
class Solution {
public int robotSim(int[] commands, int[][] obstacles) {
Set<String> set = new HashSet<>() ;
for(int [] obstacle : obstacles){ //The set stores the obstacle coordinates
set.add(obstacle[0]+","+obstacle[1]) ;
}
//Define four directions: North, East, South and West
int [] dx = {0,1,0,-1} ;
int [] dy = {1,0,-1,0} ;
int cur=0, x=0, y=0;
int tx, ty ;
int ans = 0 ;
for(int command:commands){
if(command>0){
for(int i=0; i<command; i++){
tx = x + dx[cur] ;
ty = y + dy[cur] ;
if(set.contains(tx+","+ty)){
break ;
}
x = tx ;
y = ty ;
ans = Math.max(ans,x*x+y*y) ;
}
}else{
cur = command==-1 ? (cur+1)%4 : (cur+3)%4 ;
}
}
return ans ;
}
}
6 - baseball game
Title Link: Title Link stamp here!!!
Train of thought 1: convert the list result to complete the corresponding operation.
Because there are many types of conversion, the efficiency is not very high.
class Solution {
public int calPoints(String[] ops) {
List<String> list = new ArrayList<>() ;
for(int i=0; i<ops.length; i++){
list.add(ops[i]) ;
}
for(int i=0; i<list.size(); i++){
if(list.get(i).equals("C")){
list.remove(i) ;
list.remove(i-1) ;
i -= 2 ;
}else if(list.get(i).equals("D")){
int value = Integer.parseInt(list.get(i-1))*2 ;
list.set(i,String.valueOf(value)) ;
}else if(list.get(i).equals("+")){
int sum = Integer.parseInt(list.get(i-1))+Integer.parseInt(list.get(i-2)) ;
list.set(i,String.valueOf(sum)) ;
}
}
int s = 0 ;
for(int i=0; i<list.size(); i++){
s += Integer.parseInt(list.get(i)) ;
}
return s ;
}
}
Idea 2: directly record with integer array, which improves the efficiency a lot.
class Solution {
public int calPoints(String[] ops) {
int [] res = new int [ops.length] ;
int sum = 0 ;
int j = 0 ;
for(int i=0; i<ops.length; i++){
switch(ops[i]){
case "C": res[j-1]=0 ;j--; break ;
case "D":res[j] = 2*res[j-1]; j++; break ;
case "+":res[j] = res[j-1] + res[j-2]; j++ ; break ;
default: res[j] = Integer.parseInt(ops[i]) ; j++; break;
}
}
for(int s : res){
sum += s ;
}
return sum ;
}
}
7 - display cards in ascending order
Title Link: Title Link stamp here!!!
Idea: use the queue, simulate one side according to the reverse process, and finally output the array. It's a little windy. Just draw and understand.
class Solution {
public int[] deckRevealedIncreasing(int[] deck) {
Arrays.sort(deck) ;
Queue<Integer> queue = new LinkedList<>() ;
for(int i=deck.length-1; i>=0; i--){
if(queue.isEmpty()){
queue.add(deck[i]) ;
continue ;
}
queue.add(queue.poll()) ;
queue.add(deck[i]) ;
}
for(int i=deck.length-1; i>=0; i--){
deck[i] = queue.poll() ;
}
return deck ;
}
}
8 - even sum after query
Title Link: Title Link stamp here!!!
Idea 1: modify the num array every time, and then calculate the even sum. Although it can be AC, it wastes time and is inefficient because it requires sum every time.
class Solution {
public int[] sumEvenAfterQueries(int[] nums, int[][] queries) {
int [] res = new int [nums.length] ;
int j = 0 ;
for(int i=0; i<queries.length; i++){
int num = queries[i][0] ;
int idx = queries[i][1] ;
nums[idx] += num ;
res[j++] += getSum(nums) ;
}
return res ;
}
public int getSum(int [] nums){
int sum = 0 ;
for(int n : nums){
if((n&1)==0){
sum += n ;
}
}
return sum ;
}
}
Idea 2: sum in advance. If the current modified value affects the even sum, deal with the even sum.
The AC code is as follows:
class Solution {
public int[] sumEvenAfterQueries(int[] nums, int[][] queries) {
int [] res = new int [nums.length] ;
int sum = 0 ;
for(int num : nums){
if(num%2==0){
sum += num ;
}
}
for(int i=0; i<queries.length; i++){
int num = queries[i][0] ;
int idx = queries[i][1] ;
if(nums[idx]%2==0){
sum -= nums[idx] ;
}
nums[idx] += num ;
if((nums[idx])%2==0){
sum += nums[idx];
}
res[i] = sum ;
}
return res ;
}
}
9-stupid factorial
Title Link: Title Link stamp here!!!
Idea: divide the four into a group, using recursion and loop.
class Solution {
public int clumsy(int n) {
return f(n, 1) ;
}
public int f(int n, int prefix){
if(n==0){
return 0 ;
}
if(n==1){
return 1*prefix ;
}
if(n==2){
return 2*prefix ;
}
if(n==3){
return 6*prefix ;
}
return prefix*(n)*(n-1)/(n-2)+(n-3) + f(n-4, -1) ;
}
}
For the writing method of the loop, the first flag indicates whether to execute the loop for the first time, in groups of four at a time. If it is enough to be grouped, it will execute the loop. When it is less than 4, it will judge whether it has been executed. If it has been executed, the following will be minus, otherwise it will be plus.
class Solution {
public int clumsy(int n) {
int sum = 0 ;
boolean first = true ;
while(n-4>=0){
if(first){
sum += n*(n-1)/(n-2)+(n-3) ;
}else{
sum += -(n)*(n-1)/(n-2)+(n-3) ;
}
first = false ;
n = n-4 ;
}
if(first==false){
if(n==3){
sum -= 6 ;
}else if(n==2){
sum -= 2 ;
}else if(n==1){
sum -= 1 ;
}
}else{
if(n==1){
return 1;
}else if(n==2){
return 2 ;
}else if(n==3){
return 6 ;
}
}
return sum ;
}
}
10 - verify stack sequence
Title Link: Title Link stamp here!!!
Idea: use the stack to simulate the process of entering and leaving the stack. If all the stacks can be released at last, the requirements will be met, otherwise the requirements will not be met.
class Solution {
public boolean validateStackSequences(int[] pushed, int[] popped) {
Stack<Integer> stack = new Stack<>() ;
int j = 0 ;
for(int i=0; i<popped.length; i++){
stack.push(pushed[i]) ;
while(!stack.isEmpty() && stack.peek()==popped[j]){
stack.pop() ;
j++ ;
}
}
return stack.isEmpty() ;
}
}
